Paper 2025/1133
A Note on the Rank Defect Phenomena in The Linearization Attack on Elisabeth-4
, French Institute for Research in Computer Science and Automation, Direction Générale de l'ArmementAbstract
This note gives an explanation for a phenomenon which appeared in the cryptanalysis of the Elisabeth-4 stream cipher, a stream cipher optimized for Torus Fully Homomorphic Encryption (TFHE). This primitive was broken in 2023 by a linearization attack. The authors of this attack made an observation on the rank of the linear system they generated, which was lower than expected. They have provided a partial explanation for it using some properties of the negacyclic lookup tables (NLUT), one of the potential building block of the ciphers optimized for TFHE. NLUTs are defined as functions over integers modulo 2^n such that for all x, L(x + 2^(n−1) ) = −L(x). Their explanation of the rank defect of the linear system relies on the observation that the least significant bit of L(x) does not depend on the most significant bit of x, which prevents some monomials from appearing in the algebraic normal form (ANF) of the system. In this note, we prove a stronger property of the ANF of NLUTs and use it to give full proof of their observation on the rank of the system.
Metadata
- Available format(s)
-
PDF
- Category
- Secret-key cryptography
- Publication info
- Preprint.
- Keywords
- linearization attackElisabeth-4algebraic normal form
- Contact author(s)
- antoine bak @ inria fr
- History
- 2025-06-17: approved
- 2025-06-16: received
- See all versions
- Short URL
- https://ia.cr/2025/1133
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2025/1133,
author = {Antoine Bak},
title = {A Note on the Rank Defect Phenomena in The Linearization Attack on Elisabeth-4},
howpublished = {Cryptology {ePrint} Archive, Paper 2025/1133},
year = {2025},
url = {https://eprint.iacr.org/2025/1133}
}
