Algebraic Algorithm for the Alternating Trilinear Form Equivalence Problem

Lars Ran, Simona Samardjiska, Monika Trimoska

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

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.
Original languageEnglish
Title of host publicationCode-Based Cryptography - 11th International Workshop, CBCrypto 2023, Revised Selected Papers
EditorsAndre Esser, Paolo Santini
Pages84-103
Number of pages20
DOIs
Publication statusPublished - 2023

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume14311 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).

FundersFunder number
European Research Council805031
Nederlandse Organisatie voor Wetenschappelijk OnderzoekOCNW.M.21

    Keywords

    • algebraic cryptanalysis
    • matrix codes
    • trilinear form

    Fingerprint

    Dive into the research topics of 'Algebraic Algorithm for the Alternating Trilinear Form Equivalence Problem'. Together they form a unique fingerprint.

    Cite this