International Association for Cryptologic Research

Ph.D. Database

The aim of the IACR Ph.D. database is twofold. On the first hand, we want to offer an overview of Ph.D. already completed in the domain of cryptology. Where possible, this should also include a subject classification, an abstract, and access to the full text. On the second hand, it deals with Ph.D. subjects currently under investigation. This way, we provide a timely map of contemporary research in cryptology. All entries or changes need to be approved by an editor. You can contact them via phds (at)


Yi Lu (#272)
Name Yi Lu
Topic of his/her doctorate. Applied Stream Ciphers in Mobile Communications
Category secret-key cryptography
Keywords cryptanalysis, stream cipher, E0, correlation
Ph.D. Supervisor(s) Serge Vaudenay
Year of completion 2006

This dissertation is concerned with cryptanalysis of E0, the stream cipher used in the short-range wireless radio standard Bluetooth, and of its generalization by means of correlation attacks. It consists of three parts.

In the first part, we propose an E0-like combiner with memory as the core stream cipher. First, we formulate a systematic and simple method to compute the correlations. An upper bound of the correlations is given. 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 either distinguisher is analyzed for performance comparison. The keystream distinguisher is then upgraded for use in the key-recovery attack. The latter reduces to the well-known maximum likelihood decoding problem given the keystream long enough.

In the second part, the core stream cipher is transformed into the dedicated stream cipher by attaching the one-level or two-level initialization scheme. We show that the correlation attack on the core stream cipher leads to the correlation attack on the dedicated stream cipher with the one-level initialization scheme (with equal bias), but not necessarily so with the two-level initialization scheme.

In the last part, we generalize the existing concept of conditional correlations and study conditional correlation attacks against stream ciphers and other cryptosystems. A general framework is developed for smart distinguishers, which exploit those generalized conditional correlations. Based on the theory of the traditional distinguisher, we derive the number of samples necessary for a smart distinguisher to succeed. It allows to prove that the smart distinguisher improves on the traditional basic distinguisher.

As an application of all our analysis, it leads to the fastest (and only) practical known-plaintext attack on Bluetooth encryption so far. Our attack recovers the encryption key using the first 24 bits of 2^{23.8} frames and with 2^{38} computations.

E-Mail Address luyi666 (at)
Last Change 2011-02-24 23:17:39
To provide an update on this entry, please click .

Contact: phds (at)

[ IACR home page ] [ IACR PhDs page ] © IACR