Welcome to the resource topic for 2022/1387
Title:
AIM: Symmetric Primitive for Shorter Signatures with Stronger Security
Authors: Seongkwang Kim, Jincheol Ha, Mincheol Son, Byeonghak Lee, Dukjae Moon, Joohee Lee, Sangyup Lee, Jihoon Kwon, Jihoon Cho, Hyojin Yoon, Jooyoung Lee
Abstract: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 algebraic immunity 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 estimation on the algebraic immunity 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} significantly outperforms existing signature schemes based on symmetric primitives in terms of signature size and signing time.
ePrint: https://eprint.iacr.org/2022/1387
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .