Paper 2024/1147
A reduction from Hawk to the principal ideal problem in a quaternion algebra
, Univ Bordeaux, CNRS, Inria, Bordeaux INP, IMB, UMR 5251, Talence, France, PQ Shield Ltd., United KingdomAbstract
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 in particular 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).
Metadata
- Available format(s)
-
PDF
- Category
- Attacks and cryptanalysis
- Publication info
- Preprint.
- Contact author(s)
-
clemence chevignard @ inria fr
pierre-alain fouque @ irisa fr
guilhem mureau @ math u-bordeaux fr
alice pellet-mary @ math u-bordeaux fr
alexandre wallet @ pqshield com - History
- 2024-07-19: approved
- 2024-07-15: received
- See all versions
- Short URL
- https://ia.cr/2024/1147
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2024/1147,
author = {Clémence Chevignard and Pierre-Alain Fouque and Guilhem Mureau and Alice Pellet-Mary and Alexandre Wallet},
title = {A reduction from Hawk to the principal ideal problem in a quaternion algebra},
howpublished = {Cryptology ePrint Archive, Paper 2024/1147},
year = {2024},
note = {\url{https://eprint.iacr.org/2024/1147}},
url = {https://eprint.iacr.org/2024/1147}
}
