Repository logo

Infoscience

  • English
  • French
Log In
Logo EPFL, École polytechnique fédérale de Lausanne

Infoscience

  • English
  • French
Log In
  1. Home
  2. Academic and Research Output
  3. Journal articles
  4. Cryptanalysis of an E0-like Combiner with Memory
 
research article

Cryptanalysis of an E0-like Combiner with Memory

Lu, Yi  
•
Vaudenay, Serge  
2008
Journal of Cryptology

In this paper, we study an E0-like combiner with memory as the keystream generator. First, we formulate a systematic and simple method to compute correlations of the FSM output sequences (up to certain bits). An upper bound of the correlations is given, which is useful to the designer. Second, we show how to build either a uni-bias-based or multi-bias-based distinguisher to distinguish the keystream produced by the combiner from a truly random sequence, once correlations are found. The data complexity of both distinguishers is carefully analyzed for performance comparison. We show that the multi-bias-based distinguisher outperforms the uni-bias-based distinguisher only when the patterns of the largest biases are linearly dependent. The keystream distinguisher is then upgraded for use in the key-recovery attack. The latter actually reduces to the well-known Maximum Likelihood Decoding (MLD) problem given the keystream long enough. We devise an algorithm based on Fast Walsh Transform (FWT) to solve the MLD problem for any linear code with dimension L and length n within time O(n+L.2L). Meanwhile, we summarize a design criterion for our E0-like combiner with memory to resist the proposed attacks.

  • Files
  • Details
  • Metrics
Type
research article
DOI
10.1007/s00145-007-9017-3
Web of Science ID

WOS:000254259600004

Author(s)
Lu, Yi  
Vaudenay, Serge  
Date Issued

2008

Published in
Journal of Cryptology
Volume

21

Issue

3

Start page

430

End page

457

Editorial or Peer reviewed

REVIEWED

Written at

EPFL

EPFL units
LASEC  
Available on Infoscience
April 30, 2008
Use this identifier to reference this record
https://infoscience.epfl.ch/handle/20.500.14299/23541
Logo EPFL, École polytechnique fédérale de Lausanne
  • Contact
  • infoscience@epfl.ch

  • Follow us on Facebook
  • Follow us on Instagram
  • Follow us on LinkedIn
  • Follow us on X
  • Follow us on Youtube
AccessibilityLegal noticePrivacy policyCookie settingsEnd User AgreementGet helpFeedback

Infoscience is a service managed and provided by the Library and IT Services of EPFL. © EPFL, tous droits réservés