Paper 2023/1133
Algebraic Attacks on RAIN and AIM Using Equivalent Representations
Abstract
Designing novel symmetric-key primitives for advanced protocols like secure multiparty computation (MPC), fully homomorphic encryption (FHE) and zero-knowledge proof systems (ZK), has been an important research topic in recent years. Many such existing primitives adopt quite different design strategies from conventional block ciphers. Notable features include that many of these ciphers are defined over a large finite field, and that a power map is commonly used to construct the nonlinear component due to its efficiency in these applications as well as its strong resistance against the differential and linear cryptanalysis. In this paper, we target the MPC-friendly ciphers AIM and RAIN used for the post-quantum signature schemes AIMer (CCS 2023 and NIST PQC Round 1 Additional Signatures) and Rainier (CCS 2022), respectively. Specifically, we can find equivalent representations of 2-round RAIN and full-round AIM, respectively, which make them vulnerable to either the polynomial method, or the crossbred algorithm, or the fast exhaustive search attack. Consequently, we can break 2-round RAIN with the 128/192/256-bit key in only $2^{111}/2^{170}/2^{224}$ bit operations. For full-round AIM with the 128/192/256-bit key, we could break them in $2^{136.2}/2^{200.7}/2^{265}$ bit operations, which are equivalent to about $2^{115}/2^{178}/2^{241}$ calls of the underlying primitives. In particular, our analysis indicates that AIM does not reach the required security levels by the NIST competition.
Note: This is the version accepted by FSE 2024.
Metadata
- Available format(s)
-
PDF
- Category
- Attacks and cryptanalysis
- Publication info
- Published by the IACR in TOSC 2024
- Keywords
- RAINAIMequivalent representationoverdefined systemalgebraic attack
- Contact author(s)
-
liufukangs @ gmail com
m mahzoun @ tue nl
morten oygarden @ simula no
willimeier48 @ gmail com - History
- 2023-11-22: last of 4 revisions
- 2023-07-20: received
- See all versions
- Short URL
- https://ia.cr/2023/1133
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2023/1133,
author = {Fukang Liu and Mohammad Mahzoun and Morten Øygarden and Willi Meier},
title = {Algebraic Attacks on RAIN and AIM Using Equivalent Representations},
howpublished = {Cryptology ePrint Archive, Paper 2023/1133},
year = {2023},
note = {\url{https://eprint.iacr.org/2023/1133}},
url = {https://eprint.iacr.org/2023/1133}
}
