TY - GEN
T1 - A Reduction from Hawk to the Principal Ideal Problem in a Quaternion Algebra
AU - Chevignard, Clémence
AU - Mureau, Guilhem
AU - Espitau, Thomas
AU - Pellet-Mary, Alice
AU - Pliatsok, Heorhii
AU - Wallet, Alexandre
N1 - Publisher Copyright:
© International Association for Cryptologic Research 2025.
PY - 2025/1/1
Y1 - 2025/1/1
N2 - In this article we present a non-uniform reduction from rank-2 module-LIP over Complex Multiplication fields, to a variant of the Principal Ideal Problem, in some fitting quaternion algebra. This reduction is classical deterministic polynomial-time in the size of the inputs. The quaternion algebra in which we need to solve the variant of the principal ideal problem depends on the parameters of the module-LIP problem, but not on the problem’s instance. Our reduction requires the knowledge of some special elements of this quaternion algebras, which is why it is non-uniform. In some particular cases, these elements can be computed in polynomial time, making the reduction uniform. This is the case for the Hawk signature scheme: we show that breaking Hawk is no harder than solving a variant of the principal ideal problem in a fixed quaternion algebra (and this reduction is uniform).
AB - In this article we present a non-uniform reduction from rank-2 module-LIP over Complex Multiplication fields, to a variant of the Principal Ideal Problem, in some fitting quaternion algebra. This reduction is classical deterministic polynomial-time in the size of the inputs. The quaternion algebra in which we need to solve the variant of the principal ideal problem depends on the parameters of the module-LIP problem, but not on the problem’s instance. Our reduction requires the knowledge of some special elements of this quaternion algebras, which is why it is non-uniform. In some particular cases, these elements can be computed in polynomial time, making the reduction uniform. This is the case for the Hawk signature scheme: we show that breaking Hawk is no harder than solving a variant of the principal ideal problem in a fixed quaternion algebra (and this reduction is uniform).
UR - https://www.scopus.com/pages/publications/105004790498
U2 - 10.1007/978-3-031-91124-8_6
DO - 10.1007/978-3-031-91124-8_6
M3 - Conference contribution
AN - SCOPUS:105004790498
SN - 9783031911231
T3 - Lecture Notes in Computer Science
SP - 154
EP - 183
BT - Advances in Cryptology – EUROCRYPT 2025 - 44th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Proceedings
A2 - Fehr, Serge
A2 - Fouque, Pierre-Alain
PB - Springer Science and Business Media Deutschland GmbH
T2 - 44th Annual International Conference on the Theory and Applications of Cryptographic Techniques, EUROCRYPT 2025
Y2 - 4 May 2025 through 8 May 2025
ER -