Paper 2024/364

Algebraic Algorithm for the Alternating Trilinear Form Equivalence Problem

Lars Ran, Radboud University Nijmegen
Simona Samardjiska, Radboud University Nijmegen
Monika Trimoska, Eindhoven University of Technology

The Alternating Trilinear Form Equivalence (ATFE) problem was recently used by Tang et al. as a hardness assumption in the design of a Fiat-Shamir digital signature scheme ALTEQ. The scheme was submitted to the additional round for digital signatures of the NIST standardization process for post-quantum cryptography. ATFE is a hard equivalence problem known to be in the class of equivalence problems that includes, for instance, the Tensor Isomorphism (TI), Quadratic Maps Linear Equivalence (QMLE) and the Matrix Code Equivalence (MCE) problems. Due to the increased cryptographic interest, the understanding of its practical hardness has also increased in the last couple of years. Currently, there are several combinatorial and algebraic algorithms for solving it, the best of which is a graph-theoretic algorithm that also includes an algebraic subroutine. In this paper, we take a purely algebraic approach to the ATFE problem, but we use a coding theory perspective to model the problem. This modelling was introduced earlier for the MCE problem. Using it, we improve the cost of algebraic attacks against ATFE compared to previously known ones. Taking into account the algebraic structure of alternating trilinear forms, we show that the obtained system has less variables but also less equations than for MCE and gives rise to structural degree-3 syzygies. Under the assumption that outside of these syzygies the system behaves semi-regularly, we provide a concrete, non-asymptotic complexity estimate of the performance of our algebraic attack. Our results show that the complexity of our attack is below the estimated security levels of ALTEQ by more than 20 bits for NIST level I (and more for the others), thus the scheme requires re-parametrization for all three NIST security levels.

Available format(s)
Attacks and cryptanalysis
Publication info
Published elsewhere. Minor revision. CBCrypto 2023
trilinear formsmatrix codesalgebraic cryptanalysis
Contact author(s)
lran @ cs ru nl
simonas @ cs ru nl
m trimoska @ tue nl
2024-03-07: revised
2024-02-28: received
See all versions
Short URL
Creative Commons Attribution


      author = {Lars Ran and Simona Samardjiska and Monika Trimoska},
      title = {Algebraic Algorithm for the Alternating Trilinear Form Equivalence Problem},
      howpublished = {Cryptology ePrint Archive, Paper 2024/364},
      year = {2024},
      doi = {10.1007/978-3-031-46495-9_5},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.