Paper 2024/368

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

Anand Kumar Narayanan, SandboxAQ
Youming Qiao, University of Technology Sydney
Gang Tang, University of Technology Sydney, University of Birmingham
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.

Metadata
Available format(s)
PDF
Category
Attacks and cryptanalysis
Publication info
Published by the IACR in EUROCRYPT 2024
Keywords
post-quantum cryptographydigital signaturescryptanalysis
Contact author(s)
anand kumar @ sandboxaq com
Youming Qiao @ uts edu au
gang tang-1 @ student uts edu au
History
2024-03-01: approved
2024-02-28: received
See all versions
Short URL
https://ia.cr/2024/368
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2024/368,
      author = {Anand Kumar Narayanan and Youming Qiao and Gang Tang},
      title = {Algorithms for Matrix Code and Alternating Trilinear Form Equivalences via New Isomorphism Invariants},
      howpublished = {Cryptology {ePrint} Archive, Paper 2024/368},
      year = {2024},
      url = {https://eprint.iacr.org/2024/368}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.