Towards a Generalization of the Algebraic Attack on Stream Ciphers: A Study of the Case with Only Extremal-Degree Monomials

Pierrick Méaux; Qingju Wang

doi:10.62056/aby7qjp10

Towards a Generalization of the Algebraic Attack on Stream Ciphers: A Study of the Case with Only Extremal-Degree Monomials

Authors

Pierrick Méaux, Qingju Wang

Pierrick Méaux

Luxembourg University, Esch-sur-Alzette, L-4365, Luxembourg
pierrick dot meaux at uni dot lu

Qingju Wang

Télécom Paris, Institut Polytechnique de Paris, Palaiseau, F-91120, France
qingju dot wang at telecom-paris dot fr

Keywords: Algebraic immunity Annihilators Boolean functions Stream ciphers

Abstract

When designing filter functions in Linear Feedback Shift Registers (LFSR) based stream ciphers, algebraic criteria of Boolean functions such as the Algebraic Immunity (AI) become key characteristics because they guarantee the security of ciphers against the powerful algebraic attacks. In this article, we abstract the algebraic attacks proposed by Courtois and Meier on filtered LFSR twenty years ago, considering how the standard algebraic attack can be generalized beyond filtered LFSR to stream ciphers that employ a Boolean filter function to an updated state. Depending on the updating process, we use different sets of annihilators than those used in the standard algebraic attack; it leads to a generalization of the concept of algebraic immunity, and in some particular cases, potentially more efficient attacks. Motivated by the filter permutator paradigm, we focus on the case where the update function is a bit-permutation, since it maintains the degree of the monomials. For example the degree of the monomials of degree up to $d$ and from $n-d$ to $n$ remains invariant, which leads us to consider annihilators having only monomials of these degrees. If this number of monomials is sufficiently low, linearization is feasible, allowing the linear system to be solved and revealing the key, as in the standard algebraic attack. This particular characteristic is restricted by the standard algebraic attacks and to analyze it we introduce a new notion called Extremal Algebraic Immunity (EAI). We perform a theoretic study of the EAI criterion and explore its relation to other algebraic criteria. We prove the upper bound of the EAI of an $n$-variable Boolean function and further show that the EAI can be lower bounded by the AI restricted to a subset, as defined by Carlet, Méaux and Rotella at FSE 2017. We also exhibit functions with EAI guaranteed to be lower than the AI, in particular we highlight a pathological case of functions with optimal algebraic immunity and EAI only $n/4$. As applications, we determine the EAI of filter functions of some existing stream ciphers and discuss how extremal algebraic attacks using EAI could apply to variations of known ciphers. The extremal algebraic attack does not give a better complexity than Courtois and Meier's result on the existing stream ciphers. However, we see this work as a study to avoid weaknesses in the construction of future stream ciphers.

References

[AD22]

Dor Amzaleg and Itai Dinur. Refined Cryptanalysis of the GPRS Ciphers GEA-1 and GEA-2. In Orr Dunkelman and Stefan Dziembowski, editors, EUROCRYPT 2022, Part III, volume 13277 of LNCS, pages 57–85. 2022. Springer. DOI: 10.1007/978-3-031-07082-2_3

Google Scholar ePrint

[AL16]

Benny Applebaum and Shachar Lovett. Algebraic attacks against random local functions and their countermeasures. In Daniel Wichs and Yishay Mansour, editors, STOC 2016, pages 1087–1100. 2016. ACM. DOI: 10.1145/2897518.2897554

Google Scholar ePrint

[App13]

Benny Applebaum. Cryptographic Hardness of Random Local Functions-Survey. In Amit Sahai, editor, TCC 2013, volume 7785 of LNCS, pages 599. 2013. Springer. DOI: 10.1007/978-3-642-36594-2_33

Google Scholar ePrint

[BDL⁺21]

Christof Beierle, Patrick Derbez, Gregor Leander, Gaëtan Leurent, Håvard Raddum, Yann Rotella, David Rupprecht, and Lukas Stennes. Cryptanalysis of the GPRS Encryption Algorithms GEA-1 and GEA-2. In Anne Canteaut and François-Xavier Standaert, editors, EUROCRYPT 2021, Part II, volume 12697 of LNCS, pages 155–183. 2021. Springer. DOI: 10.1007/978-3-030-77886-6_6

Google Scholar ePrint

[BP05a]

An Braeken and Bart Preneel. On the Algebraic Immunity of Symmetric Boolean Functions. In INDOCRYPT 2005, volume 3797 of LNCS, pages 35–48. 2005. Springer. DOI: 10.1007/11596219_4

Google Scholar ePrint

[BP05b]

Bart Braeken An and Preneel. Probabilistic Algebraic Attacks. In Nigel P. Smart, editor, Cryptography and Coding, pages 290–303, Berlin, Heidelberg. 2005. Springer Berlin Heidelberg. DOI: 10.1007/11586821_20

Google Scholar ePrint

[Car21]

Claude Carlet. Boolean Functions for Cryptography and Coding Theory. Cambridge University Press 2021. DOI: 10.1017/9781108606806

Google Scholar ePrint

[CDM⁺18]

Geoffroy Couteau, Aurélien Dupin, Pierrick Méaux, Mélissa Rossi, and Yann Rotella. On the Concrete Security of Goldreich's Pseudorandom Generator. In Thomas Peyrin and Steven D. Galbraith, editors, ASIACRYPT 2018, Part II, volume 11273 of LNCS, pages 96–124. 2018. Springer. DOI: 10.1007/978-3-030-03329-3_4

Google Scholar ePrint

[CM03]

Nicolas T. Courtois and Willi Meier. Algebraic Attacks on Stream Ciphers with Linear Feedback. In Eli Biham, editor, EUROCRYPT 2003, volume 2656 of LNCS, pages 345–359. 2003. Springer. DOI: 10.1007/3-540-39200-9_21

Google Scholar ePrint

[CM22]

Claude Carlet and Pierrick Méaux. A Complete Study of Two Classes of Boolean Functions: Direct Sums of Monomials and Threshold Functions. IEEE Trans. Inf. Theory, 68(5):3404–3425, 2022. DOI: 10.1109/TIT.2021.3139804

Google Scholar ePrint

[CMR17]

Claude Carlet, Pierrick Méaux, and Yann Rotella. Boolean functions with restricted input and their robustness; application to the FLIP cipher. IACR Trans. Symmetric Cryptol., 2017(3), 2017. DOI: 10.13154/TOSC.V2017.I3.192-227

Google Scholar ePrint

[Cou02]

Nicolas T. Courtois. Higher Order Correlation Attacks, XL Algorithm and Cryptanalysis of Toyocrypt. In Pil Joong Lee and Chae Hoon Lim, editors, Information Security and Cryptology - ICISC 2002, volume 2587 of LNCS, pages 182–199. 2002. Springer. DOI: 10.1007/3-540-36552-4_13

Google Scholar ePrint

[Cou03]

Nicolas T. Courtois. Fast Algebraic Attacks on Stream Ciphers with Linear Feedback. In Dan Boneh, editor, CRYPTO 2003, volume 2729 of LNCS, pages 176–194. 2003. Springer. DOI: 10.1007/978-3-540-45146-4_11

Google Scholar ePrint

[Did06]

Frédéric Didier. A New Upper Bound on the Block Error Probability After Decoding Over the Erasure Channel. IEEE Transactions on Information Theory, 52(10):4496-4503, 2006. DOI: 10.1109/TIT.2006.881719

Google Scholar ePrint

[DWW⁺22]

Lin Ding, Zheng Wu, Xinhai Wang, Ziyu Guan, and Mingjin Li. New Attacks on the GPRS Encryption Algorithms GEA-1 and GEA-2. IEEE Trans. Inf. Forensics Secur., 17:2878–2889, 2022. DOI: 10.1109/TIFS.2022.3197064

Google Scholar ePrint

[Fau99]

Jean-Charles Faugère. A new efficient algorithm for computing Groebner bases. Journal of Pure and Applied Algebra, 139:61-88, June 1999. DOI: 10.1016/S0022-4049(99)00005-5

Google Scholar ePrint

[Fau02]

Jean-Charles Faugère. A new efficient algorithm for computing Grobner bases without reduction to zero. In Workshop on application of Groebner Bases 2002, Catania, Spain. 2002. DOI: hal.inria.fr/inria-00100997

Google Scholar ePrint

[Gol00]

Oded Goldreich. Candidate One-Way Functions Based on Expander Graphs. Electronic Colloquium on Computational Complexity (ECCC), 7(90), 2000. https://eccc.weizmann.ac.il/eccc-reports/2000/TR00-090/index.html,

Google Scholar ePrint

[HHL⁺07]

Xiangao Huang, Wei Huang, Xiaozhou Liu, Chao Wang, Zhu jing Wang, and Tao Wang. Reconstructing the Nonlinear Filter Function of LILI-128 Stream Cipher Based on Complexity. 2007.

Google Scholar ePrint

[HMR20]

Clément Hoffmann, Pierrick Méaux, and Thomas Ricosset. Transciphering, Using FiLIP and TFHE for an Efficient Delegation of Computation. In Karthikeyan Bhargavan, abeth Oswald, and Manoj Prabhakaran, editors, INDOCRYPT 2020, volume 12578 of LNCS, pages 39–61. 2020. Springer. DOI: 10.1007/978-3-030-65277-7_3

Google Scholar ePrint

[MCJS19a]

Pierrick Méaux, Claude Carlet, Anthony Journault, and François-Xavier Standaert. Improved Filter Permutators: Combining Symmetric Encryption Design, Boolean Functions, Low Complexity Cryptography, and Homomorphic Encryption, for Private Delegation of Computations. https://eprint.iacr.org/2019/483. Cryptology ePrint Archive, Report 2019/483. 2019.

Google Scholar ePrint

[MCJS19b]

Pierrick Méaux, Claude Carlet, Anthony Journault, and François-Xavier Standaert. Improved Filter Permutators for Efficient FHE: Better Instances and Implementations. In Feng Hao, Sushmita Ruj, and Sourav Sen Gupta, editors, INDOCRYPT, volume 11898 of LNCS, pages 68–91. 2019. Springer. DOI: 10.1007/978-3-030-35423-7_4

Google Scholar ePrint

[M{\'{e}}a19]

Pierrick Méaux. On the Fast Algebraic Immunity of Majority Functions. In Peter Schwabe and Nicolas Thériault, editors, LATINCRYPT, volume 11774 of LNCS, pages 86–105. 2019. Springer. DOI: 10.1007/978-3-030-30530-7_5

Google Scholar ePrint

[MJSC16]

Pierrick Méaux, Anthony Journault, François-Xavier Standaert, and Claude Carlet. Towards Stream Ciphers for Efficient FHE with Low-Noise Ciphertexts. In Marc Fischlin and Jean-Sébastien Coron, editors, EUROCRYPT 2016, Part I, volume 9665 of LNCS, pages 311–343. 2016. Springer. DOI: 10.1007/978-3-662-49890-3_13

Google Scholar ePrint

[MPC04]

Willi Meier, Enes Pasalic, and Claude Carlet. Algebraic Attacks and Decomposition of Boolean Functions. In Christian Cachin and Jan Camenisch, editors, EUROCRYPT 2004, volume 3027 of LNCS, pages 474–491. 2004. Springer. DOI: 10.1007/978-3-540-24676-3_28

Google Scholar ePrint

[NLV11]

Michael Naehrig, Kristin Lauter, and Vinod Vaikuntanathan. Can Homomorphic Encryption Be Practical?. In Proceedings of the 3rd ACM Workshop on Cloud Computing Security Workshop, pages 113–124, New York, NY, USA. 2011. Association for Computing Machinery. DOI: 10.1145/2046660.2046682

Google Scholar ePrint

[SDGM00]

Leonie Ruth Simpson, Ed Dawson, Jovan Dj. Golic, and William Millan. LILI Keystream Generator. In Douglas R. Stinson and Stafford E. Tavares, editors, Selected Areas in Cryptography, SAC 2000, volume 2012 of LNCS, pages 248–261. 2000. Springer. DOI: 10.1007/3-540-44983-3_18

Google Scholar ePrint

[{\"{U}}na23]

Akin Ünal. Worst-Case Subexponential Attacks on PRGs of Constant Degree or Constant Locality. In Carmit Hazay and Martijn Stam, editors, EUROCRYPT 2023, Part I, volume 14004 of LNCS, pages 25–54. 2023. Springer. DOI: 10.1007/978-3-031-30545-0_2

Google Scholar ePrint

[YGJL22]

Jing Yang, Qian Guo, Thomas Johansson, and Michael Lentmaier. Revisiting the Concrete Security of Goldreich's Pseudorandom Generator. IEEE Transactions on Information Theory, 68(2):1329-1354, 2022. DOI: 10.1109/TIT.2021.3128315

Google Scholar ePrint

PDF Open access

DOI: https://doi.org/10.62056/aby7qjp10

History

Submitted: 2025-01-14
Accepted: 2025-03-11
Published: 2025-04-08

How to cite

Pierrick Méaux and Qingju Wang, Towards a Generalization of the Algebraic Attack on Stream Ciphers: A Study of the Case with Only Extremal-Degree Monomials. IACR Communications in Cryptology, vol. 2, no. 1, Apr 08, 2025, doi: 10.62056/aby7qjp10.

License

Copyright is held by the author(s)

This work is licensed under a Creative Commons Attribution (CC BY) license.

@article{10.62056/aby7qjp10,
         author={Pierrick Méaux and Qingju Wang},
         title={Towards a Generalization of the Algebraic Attack on Stream Ciphers: A Study of the Case with Only Extremal-Degree Monomials},
         volume={2},
         number={1},
         year={2025},
         date={2025-04-08},
         issn={3006-5496},
         doi={10.62056/aby7qjp10},
         journal={{IACR} Communications in Cryptology},
         publisher={International Association for Cryptologic Research}
}

TY  - JOUR
AU  - Pierrick Méaux
AU  - Qingju Wang
PY  - 2025
TI  - Towards a Generalization of the Algebraic Attack on Stream Ciphers: A Study of the Case with Only Extremal-Degree Monomials
JF  - IACR Communications in Cryptology
JA  - CIC
VL  - 2
IS  - 1
DO  - 10.62056/aby7qjp10
UR  - https://doi.org/10.62056/aby7qjp10
AB  - <p>        When designing filter functions in Linear Feedback Shift Registers (LFSR) based stream ciphers, algebraic criteria of Boolean functions such as the Algebraic Immunity (AI) become key characteristics because they guarantee the security of ciphers against the powerful algebraic attacks.         In this article, we abstract the algebraic attacks proposed by Courtois and Meier on filtered LFSR twenty years ago, considering how the standard algebraic attack can be generalized beyond filtered LFSR to stream ciphers that employ a Boolean filter function to an updated state.         Depending on the updating process, we use different sets of annihilators than those used in the standard algebraic attack; it leads to a generalization of the concept of algebraic immunity, and in some particular cases, potentially more efficient attacks.         Motivated by the filter permutator paradigm, we focus on the case where the update function is a bit-permutation, since it maintains the degree of the monomials.         For example the degree of the monomials of degree up to $d$ and from $n-d$ to $n$ remains invariant, which leads us to consider annihilators having only monomials of these degrees.         If this number of monomials is  sufficiently low, linearization is feasible, allowing the linear system to be solved and revealing the key, as in the standard algebraic attack.         This particular characteristic is restricted by the standard algebraic attacks and to analyze it we introduce a new notion called Extremal Algebraic Immunity (EAI).                  We perform a theoretic study of the EAI criterion and explore its relation to other algebraic criteria.         We prove the upper bound of the EAI of an $n$-variable Boolean function and further show that the EAI can be lower bounded by the AI restricted to a subset, as defined by Carlet, Méaux and Rotella at FSE 2017.         We also exhibit functions with EAI guaranteed to be lower than the AI, in particular we highlight a pathological case of functions with optimal algebraic immunity and EAI only $n/4$.         As applications, we determine the EAI of filter functions of some existing stream ciphers and discuss how extremal algebraic attacks using EAI could apply to variations of known ciphers.                  The extremal algebraic attack does not give a better complexity than Courtois and Meier's result on the existing stream ciphers. However, we see this work as a study to avoid weaknesses in the construction of future stream ciphers.          </p>
ER  -

Pierrick Méaux and Qingju Wang, Towards a Generalization of the Algebraic Attack on Stream Ciphers: A Study of the Case with Only Extremal-Degree Monomials. IACR Communications in Cryptology, vol. 2, no. 1, Apr 08, 2025, doi: 10.62056/aby7qjp10.