Welcome to the resource topic for 2023/911
Title:
General Results of Linear Approximations over Finite Abelian Groups
Authors: Zhongfeng Niu, Siwei Sun, Hailun Yan, Qi Wang
Abstract:In recent years, progress in practical applications of secure multi-party computation (MPC), fully homomorphic encryption (FHE), and zero-knowledge proofs (ZK) motivate people to explore symmetric-key cryptographic algorithms, as well as corresponding cryptanalysis techniques (such as differential cryptanalysis, linear cryptanalysis), over general finite fields \mathbb{F} or the additive group induced by \mathbb{F}^n. This investigation leads to the break of some MPC/FHE/ZK-friendly symmetric-key primitives, the United States format-preserving encryption standard FF3-1 and the South-Korean standards FEA-1 and FEA-2. In this paper, we revisit linear cryptanalysis and give general results of linear approximations over arbitrary finite Abelian groups. We consider the nonlinearity, which is the maximal non-trivial linear approximation, to characterize the resistance of a function against linear cryptanalysis. The lower bound of the nonlinearity of a function F:G\rightarrow H over an arbitrary finite Abelian group was first given by Pott in 2004. However, the result was restricted to the case that the size of G divides the size of H due to its connection to relative difference sets. We complete the generalization from \mathbb{F}_2^n to finite Abelian groups and give the lower bound of \lambda_F for all different cases. Our result is deduced by the new links that we established between linear cryptanalysis and differential cryptanalysis over general finite Abelian groups.
ePrint: https://eprint.iacr.org/2023/911
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 .