Paper 2022/1387

AIM: Symmetric Primitive for Shorter Signatures with Stronger Security (Full Version)

Seongkwang Kim, Samsung SDS
Jincheol Ha, Korea Advanced Institute of Science and Technology
Mincheol Son, Korea Advanced Institute of Science and Technology
Byeonghak Lee, Samsung SDS
Dukjae Moon, Samsung SDS
Joohee Lee, Sungshin Women's University
Sangyub Lee, Samsung SDS
Jihoon Kwon, Samsung SDS
Jihoon Cho, Samsung SDS
Hyojin Yoon, Samsung SDS
Jooyoung Lee, Korea Advanced Institute of Science and Technology

Post-quantum signature schemes based on the MPC-in-the-Head (MPCitH) paradigm are recently attracting significant attention as their security solely depends on the one-wayness of the underlying primitive, providing diversity for the hardness assumption in post-quantum cryptography. Recent MPCitH-friendly ciphers have been designed using simple algebraic S-boxes operating on a large field in order to improve the performance of the resulting signature schemes. Due to their simple algebraic structures, their security against algebraic attacks should be comprehensively studied. In this paper, we refine algebraic cryptanalysis of power mapping based S-boxes over binary extension fields, and cryptographic primitives based on such S-boxes. In particular, for the Gröbner basis attack over $\mathbb{F}_2$, we experimentally show that the exact number of Boolean quadratic equations obtained from the underlying S-boxes is critical to correctly estimate the theoretic complexity based on the degree of regularity. Similarly, it turns out that the XL attack might be faster when all possible quadratic equations are found and used from the S-boxes. This refined cryptanalysis leads to more precise algebraic analysis of cryptographic primitives based on algebraic S-boxes. Considering the refined algebraic cryptanalysis, we propose a new one-way function, dubbed $\mathsf{AIM}$, as an MPCitH-friendly symmetric primitive with high resistance to algebraic attacks. The security of $\mathsf{AIM}$ is comprehensively analyzed with respect to algebraic, statistical, quantum, and generic attacks. $\mathsf{AIM}$ is combined with the BN++ proof system, yielding a new signature scheme, dubbed $\mathsf{AIMer}$. Our implementation shows that $\mathsf{AIMer}$ outperforms existing signature schemes based on symmetric primitives in terms of signature size and signing time.

Available format(s)
Public-key cryptography
Publication info
Published elsewhere. ACM CCS 2023
post-quantumdigital signatureMPC-in-the-headalgebraic analysisGröbner basispower mapping
Contact author(s)
sk39 kim @ samsung com
smilecjf @ kaist ac kr
encrypted def @ kaist ac kr
byghak lee @ samsung com
dukjae moon @ samsung com
jooheelee @ sungshin ac kr
sangyub0 lee @ samsung com
jihoon kwon @ samsung com
jihoon1 cho @ samsung com
hj1230 yoon @ samsung com
hicalf @ kaist ac kr
2023-03-25: last of 2 revisions
2022-10-13: received
See all versions
Short URL
Creative Commons Attribution


      author = {Seongkwang Kim and Jincheol Ha and Mincheol Son and Byeonghak Lee and Dukjae Moon and Joohee Lee and Sangyub Lee and Jihoon Kwon and Jihoon Cho and Hyojin Yoon and Jooyoung Lee},
      title = {AIM: Symmetric Primitive for Shorter Signatures with Stronger Security (Full Version)},
      howpublished = {Cryptology ePrint Archive, Paper 2022/1387},
      year = {2022},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.