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

Valerie Gilchrist*, Laurane Marco, Christophe Petit, Gang Tang

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contribution

99 Downloads (Pure)

Abstract

The Tensor Isomorphism Problem (TIP) has been shown 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 restricted to the orbits of 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.
Original languageEnglish
Title of host publicationAdvances in Cryptology – CRYPTO 2024
Subtitle of host publication44th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 18–22, 2024, Proceedings, Part I
EditorsLeonid Reyzin, Douglas Stebila
PublisherSpringer
Pages141-173
Number of pages32
ISBN (Electronic)9783031683763
ISBN (Print)9783031683756
DOIs
Publication statusPublished - 16 Aug 2024
EventCRYPTO 2024 -
Duration: 18 Aug 202422 Aug 2024

Publication series

NameLecture Notes in Computer Science
PublisherSpringer
Volume14920
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

ConferenceCRYPTO 2024
Period18/08/2422/08/24

Fingerprint

Dive into the research topics of 'Solving the Tensor Isomorphism Problem for special orbits with low rank points: Cryptanalysis and repair of an Asiacrypt 2023 commitment scheme'. Together they form a unique fingerprint.

Cite this