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 language | English |
---|---|
Pages (from-to) | 166-186 |
Number of pages | 21 |
Journal | IACR Transactions on Symmetric Cryptology |
Volume | 2023 |
Issue number | 4 |
DOIs | |
Publication status | Published - 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.
Funders | Funder number |
---|---|
Norges Forskningsråd | |
National Institute of Information and Communications Technology |
Keywords
- AIM
- algebraic attack
- equivalent representation
- overdefined system
- RAIN