Paper 2025/287
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 Kingdom, 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 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).
Note: This article is the result of a merge between ePrint 2024/1147 (which had the same title) and ePrint 2024/1148.
Metadata
- Available format(s)
-
PDF
- Category
- Attacks and cryptanalysis
- Publication info
- A minor revision of an IACR publication in EUROCRYPT 2025
- Keywords
- HawkLattice Isomorphism ProblemModule lattice
- Contact author(s)
-
clemence chevignard @ inria fr
guilhem mureau @ math u-bordeaux fr
thomas espitau @ pqshield com
alice pellet-mary @ math u-bordeaux fr
georgiipliatsok @ icloud com
alexandre wallet @ pqshield com - History
- 2025-02-20: approved
- 2025-02-19: received
- See all versions
- Short URL
- https://ia.cr/2025/287
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2025/287,
author = {Clémence Chevignard and Guilhem Mureau and Thomas Espitau and Alice Pellet-Mary and Heorhii Pliatsok and Alexandre Wallet},
title = {A reduction from Hawk to the principal ideal problem in a quaternion algebra},
howpublished = {Cryptology {ePrint} Archive, Paper 2025/287},
year = {2025},
url = {https://eprint.iacr.org/2025/287}
}
