Paper 2023/1436

Cryptanalysis of Elisabeth-4

Henri Gilbert, ANSSI, Paris, France, Université Paris-Saclay, UVSQ, CNRS, Laboratoire de mathématiques de Versailles, Versailles, France
Rachelle Heim Boissier, Université Paris-Saclay, UVSQ, CNRS, Laboratoire de mathématiques de Versailles, Versailles, France
Jérémy Jean, ANSSI, Paris, France
Jean-René Reinhard, ANSSI, Paris, France

Elisabeth-4 is a stream cipher tailored for usage in hybrid homomorphic encryption applications that has been introduced by Cosseron et al. at ASIACRYPT 2022. In this paper, we present several variants of a key-recovery attack on the full Elisabeth-4 that break the 128-bit security claim of that cipher. Our most optimized attack is a chosen-IV attack with a time complexity of $2^{88}$ elementary operations, a memory complexity of $2^{54}$ bits and a data complexity of $2^{41}$ bits. Our attack applies the linearization technique to a nonlinear system of equations relating some keystream bits to the key bits and exploits specificities of the cipher to solve the resulting linear system efficiently. First, due to the structure of the cipher, the system to solve happens to be very sparse, which enables to rely on sparse linear algebra and most notably on the Block Wiedemann algorithm. Secondly, the algebraic properties of the two nonlinear ingredients of the filtering function cause rank defects which can be leveraged to solve the linearized system more efficiently with a decreased data and time complexity. We have implemented our attack on a toy version of Elisabeth-4 to verify its correctness. It uses the efficient implementation of the Block Wiedemann algorithm of CADO-NFS for the sparse linear algebra.

Available format(s)
Attacks and cryptanalysis
Publication info
Published by the IACR in ASIACRYPT 2023
Contact author(s)
henri gilbert @ ssi gouv fr
heim rachelle @ gmail com
Jean Jeremy @ gmail com
jean-rene reinhard @ m4x org
2023-09-24: approved
2023-09-21: received
See all versions
Short URL
Creative Commons Attribution


      author = {Henri Gilbert and Rachelle Heim Boissier and Jérémy Jean and Jean-René Reinhard},
      title = {Cryptanalysis of Elisabeth-4},
      howpublished = {Cryptology ePrint Archive, Paper 2023/1436},
      year = {2023},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.