Algorithms for Matrix Code and Alternating Trilinear Form Equivalences via New Isomorphism Invariants

Narayanan, AK; Qiao, Y; Tang, G

Algorithms for Matrix Code and Alternating Trilinear Form Equivalences via New Isomorphism Invariants

Narayanan, AK Qiao, Y

Tang, G

Permalink

Publisher:: Springer Nature
Publication Type:: Chapter
Citation:: Advances in Cryptology – EUROCRYPT 2024, 2024, 14653 LNCS, pp. 160-187
Issue Date:: 2024-01-01

Closed Access

	Filename	Description	Size
	A.pdf	Published version	413.42 kB	Adobe PDF	View/Open

Copyright Clearance Process

Recently Added
In Progress
Closed Access

This item is closed access and not available.

Full metadata record

Field	Value	Language
dc.contributor.author	Narayanan, AK
dc.contributor.author	Qiao, Y https://orcid.org/0000-0003-4334-1449
dc.contributor.author	Tang, G
dc.date.accessioned	2024-09-02T04:34:37Z
dc.date.available	2024-09-02T04:34:37Z
dc.date.issued	2024-01-01
dc.identifier.citation	Advances in Cryptology – EUROCRYPT 2024, 2024, 14653 LNCS, pp. 160-187
dc.identifier.isbn	9783031587337
dc.identifier.uri	http://hdl.handle.net/10453/180587
dc.description.abstract	We devise algorithms for finding equivalences of trilinear forms over finite fields modulo linear group actions. Our focus is on two problems under this umbrella, Matrix Code Equivalence (MCE) and Alternating Trilinear Form Equivalence (ATFE), since their hardness is the foundation of the NIST round-1 signature candidates MEDS and ALTEQ respectively. We present new algorithms for MCE and ATFE, which are further developments of the algorithms for polynomial isomorphism and alternating trilinear form equivalence, in particular by Bouillaguet, Fouque, and Véber (Eurocrypt 2013), and Beullens (Crypto 2023). Key ingredients in these algorithms are new easy-to-compute distinguishing invariants under the respective group actions. For MCE, we associate new isomorphism invariants to corank-1 points of matrix codes, which lead to a birthday-type algorithm. We present empirical justifications that these isomorphism invariants are easy-to-compute and distinguishing, and provide an implementation of this algorithm. This algorithm has some implications to the security of MEDS. The invariant function for ATFE is similar, except it is associated with lower rank points. Modulo certain assumptions on turning the invariant function into canonical forms, our algorithm for ATFE improves on the runtime of the previously best known algorithm of Beullens (Crypto 2023). Finally, we present quantum variants of our classical algorithms with cubic runtime improvements.
dc.language	en
dc.publisher	Springer Nature
dc.relation	http://purl.org/au-research/grants/arc/DP200100950
dc.relation	http://purl.org/au-research/grants/arc/LP220100332
dc.relation.ispartof	Advances in Cryptology – EUROCRYPT 2024
dc.relation.ispartofseries	Lecture Notes in Computer Science
dc.relation.isbasedon	10.1007/978-3-031-58734-4_6
dc.rights	info:eu-repo/semantics/closedAccess
dc.subject.classification	Artificial Intelligence & Image Processing
dc.subject.classification	46 Information and computing sciences
dc.title	Algorithms for Matrix Code and Alternating Trilinear Form Equivalences via New Isomorphism Invariants
dc.type	Chapter
utslib.citation.volume	14653 LNCS
pubs.organisational-group	University of Technology Sydney
pubs.organisational-group	University of Technology Sydney/Faculty of Engineering and Information Technology
pubs.organisational-group	University of Technology Sydney/Strength - QSI - Centre for Quantum Software and Information
pubs.organisational-group	University of Technology Sydney/Faculty of Engineering and Information Technology/School of Computer Science
pubs.organisational-group	University of Technology Sydney/Strength - CQSI - Centre for Quantum Software and Information
pubs.organisational-group	University of Technology Sydney/All Manual Groups
pubs.organisational-group	University of Technology Sydney/All Manual Groups/Centre for Quantum Software and Information (QSI)
utslib.copyright.status	closed_access	*
dc.date.updated	2024-09-02T04:34:36Z
pubs.publication-status	Published
pubs.volume	14653 LNCS

Abstract:

We devise algorithms for finding equivalences of trilinear forms over finite fields modulo linear group actions. Our focus is on two problems under this umbrella, Matrix Code Equivalence (MCE) and Alternating Trilinear Form Equivalence (ATFE), since their hardness is the foundation of the NIST round-1 signature candidates MEDS and ALTEQ respectively. We present new algorithms for MCE and ATFE, which are further developments of the algorithms for polynomial isomorphism and alternating trilinear form equivalence, in particular by Bouillaguet, Fouque, and Véber (Eurocrypt 2013), and Beullens (Crypto 2023). Key ingredients in these algorithms are new easy-to-compute distinguishing invariants under the respective group actions. For MCE, we associate new isomorphism invariants to corank-1 points of matrix codes, which lead to a birthday-type algorithm. We present empirical justifications that these isomorphism invariants are easy-to-compute and distinguishing, and provide an implementation of this algorithm. This algorithm has some implications to the security of MEDS. The invariant function for ATFE is similar, except it is associated with lower rank points. Modulo certain assumptions on turning the invariant function into canonical forms, our algorithm for ATFE improves on the runtime of the previously best known algorithm of Beullens (Crypto 2023). Finally, we present quantum variants of our classical algorithms with cubic runtime improvements.

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

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