## Abstract

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 inter-

est, 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 reparametrization for all three NIST security levels.

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 inter-

est, 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 reparametrization for all three NIST security levels.

Original language | English |
---|---|

Title of host publication | Code-Based Cryptography - 11th International Workshop, CBCrypto 2023, Revised Selected Papers |

Editors | Andre Esser, Paolo Santini |

Pages | 84-103 |

Number of pages | 20 |

DOIs | |

Publication status | Published - 2023 |

### Publication series

Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|

Volume | 14311 LNCS |

ISSN (Print) | 0302-9743 |

ISSN (Electronic) | 1611-3349 |

### Funding

This research is supported by the NWO grant OCNW.M.21. 193 (ALPaQCa) and the ERC Starting Grant 805031 (EPOQUE).

Funders | Funder number |
---|---|

European Research Council | 805031 |

Nederlandse Organisatie voor Wetenschappelijk Onderzoek | OCNW.M.21 |

## Keywords

- algebraic cryptanalysis
- matrix codes
- trilinear form