Paper 2022/1528 Original: eprint.iacr.org/2022/1528 ↗
Graph-Theoretic Algorithms for the Alternating Trilinear Form Equivalence Problem
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.
Metadata
- Available format(s)
PDF- Category
- Attacks and cryptanalysis
- Publication info
- Preprint.
- History
- 2023-08-17: last updated
- 2022-11-04: published
- Short URL
- https://ia.cr/2022/1528
- License
- https://creativecommons.org/licenses/by/4.0/
BibTeX
@misc{cryptoeprint:2022/1528,
author = {Ward Beullens},
title = {Graph-Theoretic Algorithms for the Alternating Trilinear Form Equivalence Problem},
howpublished = {Cryptology {ePrint} Archive, Paper 2022/1528},
year = {2022},
url = {https://eprint.iacr.org/2022/1528}
}