Algebraic Attacks on RAIN and AIM Using Equivalent Representations

Fukang Liu, Mohammad Mahzoun, Morten Øygarden, Willi Meier

Research output: Contribution to journalArticleAcademicpeer-review

2 Citations (Scopus)
32 Downloads (Pure)

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 2111/2170/2225 bit operations. For full-round AIM with the 128/192/256-bit key, we could break them in 2136.2/2200.7/2265 bit operations, which are equivalent to about 2115/2178/2241 calls of the underlying primitives. In particular, our analysis indicates that AIM does not reach the required security levels by the NIST competition.

Original languageEnglish
Pages (from-to)166-186
Number of pages21
JournalIACR Transactions on Symmetric Cryptology
Volume2023
Issue number4
DOIs
Publication statusPublished - 8 Dec 2023

Funding

We thank the reviewers of ToSC Issue (4) for improving the quality of this paper. Fukang Liu is supported by Grant-in-Aid for Research Activity Start-up (Grant No. 22K21282). The research results were also funded by the commissioned research (No. JPJ012368C05801) by National Institute of Information and Communications Technology (NICT), Japan. Morten Øygarden has been funded by the Research Council of Norway through the project qsIo2.

FundersFunder number
Norges Forskningsråd
National Institute of Information and Communications Technology

    Keywords

    • AIM
    • algebraic attack
    • equivalent representation
    • overdefined system
    • RAIN

    Fingerprint

    Dive into the research topics of 'Algebraic Attacks on RAIN and AIM Using Equivalent Representations'. Together they form a unique fingerprint.

    Cite this