Paper 2024/337

Solving the Tensor Isomorphism Problem for special orbits with low rank points: Cryptanalysis and repair of an Asiacrypt 2023 commitment scheme

Valerie Gilchrist, Université Libre de Bruxelles
Laurane Marco, École Polytechnique Fédérale de Lausanne
Christophe Petit, Université Libre de Bruxelles
Gang Tang, University of Technology Sydney
Abstract

The Tensor Isomorphism Problem (TIP) has been shown to be equivalent to the matrix code equivalence problem, making it an interesting candidate on which to build post-quantum cryptographic primitives. These hard problems have already been used in protocol development. One of these, MEDS, is currently in Round 1 of NIST's call for additional post-quantum digital signatures. In this work, we consider the TIP for a special class of tensors. The hardness of the decisional version of this problem is the foundation of a commitment scheme proposed by D'Alconzo, Flamini, and Gangemi (Asiacrypt 2023). We present polynomial-time algorithms for the decisional and computational versions of TIP for special orbits, which implies that the commitment scheme is not secure. The key observations of these algorithms are that these special tensors contain some low-rank points, and their stabilizer groups are not trivial. With these new developments in the security of TIP in mind, we give a new commitment scheme based on the general TIP that is non-interactive, post-quantum, and statistically binding, making no new assumptions. Such a commitment scheme does not currently exist in the literature.

Metadata
Available format(s)
PDF
Category
Attacks and cryptanalysis
Publication info
A minor revision of an IACR publication in CRYPTO 2024
Keywords
tensorrankmatrix equivalencecommitment schemestabilizer
Contact author(s)
valerie gilchrist @ ulb be
laurane marco @ epfl ch
christophe petit @ ulb be
g tang 1 @ bham ac uk
History
2024-06-14: last of 3 revisions
2024-02-26: received
See all versions
Short URL
https://ia.cr/2024/337
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2024/337,
      author = {Valerie Gilchrist and Laurane Marco and Christophe Petit and Gang Tang},
      title = {Solving the Tensor Isomorphism Problem for special orbits with low rank points:  Cryptanalysis and repair of an Asiacrypt 2023 commitment scheme},
      howpublished = {Cryptology {ePrint} Archive, Paper 2024/337},
      year = {2024},
      url = {https://eprint.iacr.org/2024/337}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.