Trilinear Form Equivalence Problems: from Algorithm and Complexity to Post-Quantum Cryptography

Tang, Gang

Trilinear Form Equivalence Problems: from Algorithm and Complexity to Post-Quantum Cryptography

Tang, Gang

Permalink

Publication Type:: Thesis
Issue Date:: 2024

Open Access

Copyright Clearance Process

Recently Added
In Progress
Open Access

This item is open access.

Adobe PDF

Download thesisAdobe PDF (1.26 MB)

View statistics

Full metadata record

Field	Value	Language
dc.contributor.author	Tang, Gang
dc.date.accessioned	2025-05-13T04:22:10Z
dc.date.available	2025-05-13T04:22:10Z
dc.date.issued	2024
dc.identifier.uri	http://hdl.handle.net/10453/187341
dc.description	University of Technology Sydney. Faculty of Engineering and Information Technology.	en_US.UTF-8
dc.description.abstract	In this thesis, we present new results on alternating trilinear form equivalence (ATFE), a problem that arises in both mathematics and cryptography. ATFE is of particular interest due to its connections to various hard problems in cryptography, which makes it a promising candidate for post-quantum cryptographic schemes. We show that testing ATFE is polynomial-time equivalent to testing symmetric trilinear form equivalence, establishing both as Tensor Isomorphism-complete problems. Building on this foundation, we introduce ALTEQ, a post-quantum signature scheme based on ATFE, optimized for practical use and submitted to the NIST PQC standardization as a first round candidate. We further investigate the QROM security of group action based signatures under the GMW-FS framework and a general construction extending this framework to ring signatures. Our cryptanalysis of matrix code equivalence (MCE) and ATFE includes novel algorithms that improve on the state-of-the-art algorithms by introducing new isomorphism invariants. These advances enhance the security understanding of related schemes such as MEDS and ALTEQ.	en_US.UTF-8
dc.format	Thesis (PhD)
dc.language.iso	en_US	en_US.UTF-8
dc.relation	https://opus.lib.uts.edu.au/bitstream/10453/187341/1/thesis.pdf
dc.rights	info:eu-repo/semantics/openAccess
dc.rights	The author owns the copyright in this thesis including all reproduction and reuse rights for the work. The work may not be altered without the permission of the copyright owner. Attribution is essential when quoting or paraphrasing from this thesis.
dc.rights	© 2024 Gang Tang
dc.rights	au.edu.uts.lib/cph
dc.title	Trilinear Form Equivalence Problems: from Algorithm and Complexity to Post-Quantum Cryptography	en_US.UTF-8
dc.type	Thesis
utslib.copyright.status	open_access	*

Abstract:

In this thesis, we present new results on alternating trilinear form equivalence (ATFE), a problem that arises in both mathematics and cryptography. ATFE is of particular interest due to its connections to various hard problems in cryptography, which makes it a promising candidate for post-quantum cryptographic schemes. We show that testing ATFE is polynomial-time equivalent to testing symmetric trilinear form equivalence, establishing both as Tensor Isomorphism-complete problems. Building on this foundation, we introduce ALTEQ, a post-quantum signature scheme based on ATFE, optimized for practical use and submitted to the NIST PQC standardization as a first round candidate. We further investigate the QROM security of group action based signatures under the GMW-FS framework and a general construction extending this framework to ring signatures. Our cryptanalysis of matrix code equivalence (MCE) and ATFE includes novel algorithms that improve on the state-of-the-art algorithms by introducing new isomorphism invariants. These advances enhance the security understanding of related schemes such as MEDS and ALTEQ.

Please use this identifier to cite or link to this item:

http://hdl.handle.net/10453/187341