Paper 2024/1147 Original: eprint.iacr.org/2024/1147 ↗
A reduction from Hawk to the principal ideal problem in a quaternion algebra
Abstract
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).
Metadata
- Available format(s)
PDF- Category
- Attacks and cryptanalysis
- Publication info
- Preprint.
- History
- 2024-10-09: last updated
- 2024-07-15: published
- Short URL
- https://ia.cr/2024/1147
- License
- https://creativecommons.org/licenses/by/4.0/
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},
url = {https://eprint.iacr.org/2024/1147}
}