Paper 2022/1528

Graph-Theoretic Algorithms for the Alternating Trilinear Form Equivalence Problem

Ward Beullens, IBM Research - Zurich

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.

Note: 14/11/2022: Fix typo 15/11/2022: Fix more typos + add missing reference 17/08/2023: Update after submitting to crypto

Available format(s)
Attacks and cryptanalysis
Publication info
Trilinear FormsGraphs
Contact author(s)
ward @ beullens com
2023-08-17: last of 3 revisions
2022-11-04: received
See all versions
Short URL
Creative Commons Attribution


      author = {Ward Beullens},
      title = {Graph-Theoretic Algorithms for the Alternating Trilinear Form Equivalence Problem},
      howpublished = {Cryptology ePrint Archive, Paper 2022/1528},
      year = {2022},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.