International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Graph-Theoretic Algorithms for the Alternating Trilinear Form Equivalence Problem

Authors:
Ward Beullens , IBM Research - Zurich
Download:
DOI: 10.1007/978-3-031-38548-3_4 (login may be required)
Search ePrint
Search Google
Presentation: Slides
Conference: CRYPTO 2023
Abstract: At Eurocrypt`22 Tang, Duong, Joux, Plantard, Qiao, and Susilo proposed a digital signature algorithm based on the hardness of the isomorphism problem of alternating trilinear forms. They propose three concrete parameters in dimensions 9,10, and 11 respectively. We give new heuristic algorithms that solve this problem more efficiently. With our new algorithms, the first parameter set can be broken in less than a day on a laptop. For the second parameter set, we show there is a $2^{-17}$ fraction of the public keys that can also be broken in less than a day. We do not break the third parameter set in practice, but we claim it falls short of the target security level of 128 bits.
BibTeX
@inproceedings{crypto-2023-33138,
  title={Graph-Theoretic Algorithms for the Alternating Trilinear Form Equivalence Problem},
  publisher={Springer-Verlag},
  doi={10.1007/978-3-031-38548-3_4},
  author={Ward Beullens},
  year=2023
}