On stream ciphers with provable beyond-the-birthday-bound security against time-memory-data tradeoff attacks

Abstract

Most stream ciphers are vulnerable against generic time-memory-data tradeoff (TMD-TO) attacks, which reduce their effective key length to the birthday bound $n/2$, where n denotes the inner state length of the underlying keystream generator. This implies the necessity of a comparatively large inner state length for practical stream ciphers (e.g., $n = 288$ and $n = 160$ for the eSTREAM portfolio members Trivium and Grain v1, respectively). In this paper, we propose and analyze the Lizard-construction, a new way to build stream ciphers. We prove a tight $2n/3$ bound on its security against TMD-TO key recovery attacks, where the security lower bound refers to chosen-IV attacks. The security against TMD-TO distinguishing attacks remains at the birthday-bound level $n/2$. The lower bound refers to a random oracle model which allows to derive formal security results w.r.t. generic TMD-TO attacks. While similar frameworks have already been widely used for analyzing the security of block cipher, MAC, and hash function constructions, to the best of our knowledge this is the first time that such a model is considered in the context of stream ciphers. The security analysis presented in this paper is also of immediate practical relevance as, with the stream cipher Lizard, a first instantiation of our new design principle (which we hence named Lizard-construction) was introduced at FSE 2017. Lizard has an inner state length of only 121 bits and surpasses Grain v1, the most hardware efficient member of the eSTREAM portfolio, in important metrics for lightweight ciphers such as chip area and power consumption.

1 Introduction

Stream ciphers are, besides block ciphers, the most popular family of modern symmetric encryption algorithms. They are intended for encrypting, in an online manner, plaintext bitstreams X which have to pass an insecure channel. The encryption is performed via bitwise addition of a keystream S to X, which depends on a secret symmetric key k and a public initial value $\mathit {IV}$. The legal recipient, who also knows k, decrypts the encrypted bitstream $Y=X\oplus S$ by generating S and computing $X=Y\oplus S$. An important use case for stream ciphers is the encryption of over-the-air communication for mobile devices, which implies that lightweight aspects play a dominant role in the design of stream ciphers.

In our framework, we suppose that the communication between legal users is organized in sessions, where in the first phase of each session, the secret session key k is generated by executing a key establishment protocol. This session key generation phase will not be considered in this paper. In practice, a session can, e.g., be a phone call, where at the beginning of the call, a key establishment protocol between the mobile phone and the nearest base station is performed.

Following [8], each stream cipher is associated with a well-defined set of inner states and its keystream generation process can be divided into the following two phases: (A) The key and IV setup phase, where an initial state is derived from the secret session key k and an initial value $\mathit {IV}$, and (B) the keystream generation phase, in which the keystream is generated based on the initial state derived in phase (A).

In this paper, we consider keystream generator-based stream ciphers, for which the main algorithmic component for performing phases (A) and (B) is a so-called keystream generator (KSG). KSGs are clock-controlled devices which can be formally specified by finite automata, defined by an inner state length n, the set of inner states $\left \{0,1\right \}^{n}$, a state update function $\pi :\left \{0,1\right \}^{n}\longrightarrow \left \{0,1\right \}^{n}$, and an output function $\mathit {outbit}:\left \{0,1\right \}^{n}\longrightarrow \left \{0,1\right \}$. Starting from an initial state $q_{0}$, in each clock cycle $t\ge 0$, the KSG produces an output bit $z_{t}=\mathit {outbit}(q_{t})$ and changes the inner state according to $q_{t + 1}=\pi (q_{t})$. The keystream $S(q_{0})$ corresponding to the initial state $q_{0}$ is defined by concatenating all the output bits $z_{0} z_{1} z_{2}\cdots$.

The key and IV setup phase (A) of a KSG-based stream cipher is typically performed by a KSG-based state initialization algorithm, which computes the initial state $q_{\text {init}}$ from the session key k and the initial value $\mathit {IV}$. It always contains the following two subphases:

• (A.1) The loading phase defines how the session key k and the initial value $\mathit {IV}$ are loaded into the inner state registers and results in a load state $q_{\text {load}}= q_{\text {load}}(k,\mathit {IV})$.

• (A.2) The mixing phase runs an appropriate KSG-based mixing algorithm $\mathit {MIX}:\left \{0,1\right \}^{n}\longrightarrow \left \{0,1\right \}^{n}$ on $q_{\text {load}}$ and yields a state $q_{\text {mixed}}=\mathit {MIX}(q_{\text {load}})$.

The aim of the mixing phase (A.2) is to ensure that each initial state bit depends on many session key bits and IV bits and that this dependency, expressed as a multivariate $GF(2)$-polynomial over the session key bits and IV bits, has large degree. In many cases, an essential part of the mixing algorithm consists in running the KSG a certain number of times without producing keystream bits. Moreover, for many ciphers (Grain, Trivium, $E_{0}$, A5/1 etc.) it holds that q_init = q_mixed.

In this paper, with the Lizard-construction, we propose a state initialization algorithm of type

$$ q_{\text{init}}=\mathit{MIX}\left(q_{\text{load}}\right)\oplus k, $$

(1)

where $q_{\text {load}}=k\oplus \mathit {IV}$, (see Fig. 1) and show that this state initialization algorithm (together with a certain mode of operation) guarantees a beyond-the-birthday-bound security against time-memory-data tradeoff (TMD-TO) attacks.

Fig. 1

The key and IV setup phase (A) of the Lizard-construction. The XOR symbol denotes the addition of the corresponding n-bit vectors over GF(2)

As in [8, 9], and many other papers, we consider the keystream generation phase (B) of KSG-based stream ciphers as being defined by the output block function $\mathit {OUTBLOCK}:\left \{0,1\right \}^{n}\longrightarrow \left \{0,1\right \}^{n}$, which assigns each inner state $q\in \left \{0,1\right \}^{n}$ to the first n keystream bits produced on q. We give now the exact definition of $\mathit {OUTBLOCK}$:

Definition 1

We consider a KSG with output bit function $\mathit {outbit}:\left \{0,1\right \}^{n}\longrightarrow \left \{0,1\right \}$ and state transition function $\pi :\left \{0,1\right \}^{n}\longrightarrow \left \{0,1\right \}^{n}$. For all $q\in \left \{0,1\right \}^{n}$, let

$$\mathit{OUTBLOCK}(q)=(\tilde{z}_{0},\cdots,\tilde{z}_{n-1}), $$

where for all r, $0\le r\le n-1$,

$$\tilde{z}_{r}=\mathit{outbit}(\pi^{r}(q)). $$

Here, $\pi ^{r}$ means applying the state transition function r times, so $\pi ^{r}(q)$ denotes the state obtained from q after clocking the cipher r times.

Note that the keystream $S(q_{\text {init}}(k,\mathit {IV}))=(z_{0},z_{1},\cdots )$ generated on a key-IV pair $(k,\mathit {IV})$ can now be expressed as follows (see also Fig. 2). For each n-bit subblock $(z_{r},\cdots ,z_{r+n-1})$, it holds

$$ (z_{r},\cdots,z_{r+n-1})=\mathit{OUTBLOCK}\left(\pi^{r}\left(q_{\text{init}}\right)\right). $$

Fig. 2

The keystream generation phase (B) in terms of our model

One can distinguish the following two operation modes of stream ciphers.

In the one-stream mode, the key and IV setup phase (A) is performed only once at the beginning of the session and produces an initial state $q_{\text {init}}=q_{\text {init}}(k,\mathit {IV})$. The corresponding keystream $S=S(q_{\text {init}})$ is used for the whole session. Note that due to their extremely large limits (e.g., $2^{64}$ bits for Trivium) on the amount of keystream generated under a single key-IV pair, Trivium [12] and Grain [25] can be considered to work in one-stream mode.

In contrast to this, in the packet mode, the communication and encryption process during a session is divided into packet steps $i = 1,2,\cdots$, where in each packet step, a piece of message of a certain maximal packet length R is encrypted and sent. Corresponding to this, the keystream of a session is the concatenation of the keystream packets $S^{1}S^{2}S^{3}\cdots$, where for all $i\ge 1$, $S^{i}$ denotes the keystream packet generated in packet step i. The stream cipher is equipped with an additional mechanism which generates for each packet step i an initial value $\mathit {IV}^{i}$. Each packet step i starts with performing the key and IV setup phase (A), which computes a packet initial state $q_{\text {init}}^{i}=q_{\text {init}}^{i}(k,\mathit {IV}^{i})$, followed by the generation of the keystream packet $S^{i}$, which is defined to be the prefix of length R of $S(q_{\text {init}}^{i})$. As in many communication scenarios data streams are encrypted and transmitted packet-wise (Bluetooth, WLAN, cellular networks etc.), it seems natural to run a stream cipher in packet mode. Typical examples are the GSM cipher A5/1 and the Bluetooth cipher $E_{0}$ (see [22] for more practical examples of stream ciphers running in packet mode and more information about the practical relevance of such ciphers). Clearly, Trivium and Grain could also be used in packet mode but, in contrast to, e.g., Lizard [22], their design is not specifically optimized for such scenarios. More precisely, all current small-state stream ciphers (i.e., stream ciphers targeting beyond-the-birthday-bound security; see [23] for an overview) impose some additional restriction about their application context in order to reach this improved security level. For example, Sprout-like small-state stream ciphers (see below) assume that it is feasible to continuously access the secret key not only during initialization but also during keystream generation. Lizard, on the other hand, uses the secret key only during initialization but assumes that per IV, at most $2^{18}$ keystream bits need to be generated. As explained in [22], this limit fits well for many prominent communication scenarios and allows, due to Lizard’s beyond-the-birthday-bound security, for a more efficient hardware implementation (w.r.t. important cost factors such as chip area and power consumptions) than, e.g., the general-purpose stream ciphers Trivium and Grain. This is particularly relevant in the context of ultra-constrained devices like low-cost radio-frequency identification (RFID) tags, where virtually every hardware gate matters and corresponding restrictions often hinder cryptographic schemes from being used in practice (see, e.g., [3]).

During the last decades, many stream ciphers have been suggested and many different techniques for cryptanalyzing stream ciphers have been developed (correlation attacks, fast correlation attacks, guess-and-verify attacks, BDD attacks, cube attacks etc.). Attacks on stream ciphers typically suppose that the attacker knows a piece $S^{\prime }$ of keystream which was generated under a secret session key k and a set of known or actively chosen initial values. Standard goals of attacks are to distinguish $S^{\prime }$ from a truly random bitstream, to recover the inner states responsible for $S^{\prime }$, to predict a new keystream packet on the basis of $S^{\prime }$, or to recover the secret session key.

In this paper, we focus on time-memory-data tradeoff (TMD-TO) attacks, which are for many stream ciphers the most powerful known attacks. TMD-TO attacks have a generic nature in the sense that they access the security-relevant components $\mathit {MIX}$ and $\mathit {OUTBLOCK}$ only in a black-box manner. This implies that from the attacker’s point of view, these components are ideally designed in the sense of [19]. Hence, the aim of TMD-TO attacks is to analyze the way how the components $\mathit {MIX}$ and $\mathit {OUTBLOCK}$ interact in computing the keystream from the secret session key k and an initial value $\mathit {IV}$ and to check if this way opens the door for nontrivial attacks.

In consequence, such TMD-TO attacks can usually be formulated for variable inner state length n. Correspondingly, we express upper and lower security bounds for stream cipher constructions against TMD-TO attacks in an asymptotic manner. For instance, we say that a stream cipher construction has, for some number a, $0\le a\le 1$, the security level $a\cdot n$ w.r.t. TMD-TO attacks if there is a TMD-TO attack of cost behavior $O(2^{a\cdot n})$ with significant success probability and, for all $\alpha <a$, all TMD-TO attacks of cost behavior $O(2^{\alpha \cdot n})$ have only negligibly small success probability. We will discuss the cost behavior of TMD-TO attacks in more detail at the beginning of Section 3.

The vulnerability against generic TMD-TO attacks such as those of Babbage [5] or Biryukov and Shamir [9] represents an inherent weakness of KSG-based stream ciphers. This vulnerability implies that for KSG-based stream ciphers working in one-stream mode, the effective key length is bounded by $\frac {n}{2}$, where n denotes the inner state length of the underlying KSG. As a consequence, modern practical stream ciphers have comparatively large inner state lengths (e.g., 288 bits for the eSTREAM portfolio member Trivium [12] or 160 bits for the eSTREAM portfolio member Grain v1 [25]).

In this paper, we propose a construction principle to design KSG-based stream ciphers with a provable beyond-the-birthday-bound security of $\frac {2}{3}n$ against generic TMD-TO key recovery attacks: taking a stream cipher with a state initialization algorithm as described in Relation (1) and using it in packet mode. We give this construction principle the name Lizard-construction, as it underlies the stream cipher Lizard [22] introduced at FSE 2017.

The Lizard-construction can be motivated as follows. Babbage’s TMD-TO attack [5] implies that if a KSG-based stream cipher runs in one-stream mode, then it is possible to predict the keystream of the whole session with a TMD-TO attack of cost behavior $O(2^{n/2})$ (see Theorem 1 in Section 3). Moreover, if the state initialization algorithm is efficiently invertible (as it is the case, e.g., with Trivium, Grain v1, A5/1), then this attack even yields the secret session key.

The question is if KSG-based stream ciphers running in packet mode can have beyond-the-birthday-bound resistance against TMD-TO attacks. The following observation shows that packet mode alone is not enough for reaching this goal. Many stream ciphers (e.g., A5/1, $E_{0}$, Trivium, Grain v1) employ a state initialization algorithm of type

$$ q_{\text{init}} = \mathit{MIX}\left(q_{\text{load}}\right) $$

(2)

with $q_{\text {load}} = q_{\text {load}}(k,\mathit {IV})$, instead of

$$q_{\text{init}}=\mathit{MIX}\left(q_{\text{load}}\right)\oplus k $$

with $q_{\text {load}} = q_{\text {load}}(k,\mathit {IV}) = k \oplus \mathit {IV}$, as used by the Lizard-construction (cf. Relation (1)). We show in Theorem 3 that even if a stream cipher runs in packet mode and even if the state initialization algorithm is not efficiently invertible (as, e.g., that of $E_{0}$), a state initialization algorithm of the type in Relation (2) provides only a security level of $\frac {n}{2}$ w.r.t. session key recovery attacks.

In contrast to this, we show a tight $\frac {2}{3}n$ bound on the security of the Lizard-construction against TMD-TO attacks. More precisely, in Theorem 4 we describe a TMD-TO session key recovery attack of TMD-cost $\tilde {O}(2^{(2/3)n})$ against the Lizard-construction, which is based on the Slidex attack of Dunkelman, Keller, and Shamir [16] against the one-key Even-Mansour cipher [18].

The main contribution of this paper is to show that for the Lizard-construction, this $\frac {2}{3}n$ security bound is sharp.

The proof of the matching security lower bound result is done, in the spirit of [19], in a random oracle model corresponding to the components $\mathit {MIX}$ and $\mathit {OUTBLOCK}$ of the Lizard-construction. We prove an information-theoretic lower bound on the security of the Lizard-construction against generic chosen-IV attackers, who have black-box access to the component primitives $\mathit {MIX}$ and $\mathit {OUTBLOCK}$, and to the stream cipher construction itself. Due to their generic nature, all known TMD-TO attacks against stream ciphers can be formulated as attacks in this model in a straightforward way.

The proof of our security lower bound follows the typical structure of similar information-theoretic proofs in the context of iterated Even-Mansour ciphers (see, e.g., [2, 11, 13, 14, 18, 26]). In particular, it is inspired by the (much shorter) security lower bound proof in [18]. As in [18], the lower bound against key recovery attacks follows from a lower bound against the weaker type of attack in which the goal of the attacker is to predict a new keystream packet, and which we call packet prediction attack in the following. The rough idea consists in proving that if Eve poses significantly less than at most $2^{(2/3) n}$ component and construction queries, then, with high probability, the entropy of the secret session key will still be at least $n-1$. This immediately implies an exponentially small success probability for recovering the session key and we will show that this is also the case for predicting a correct new packet.

Note that the $\frac {2}{3}n$ security bound for the Lizard-construction cannot hold against distinguishing attacks. We show in Theorem 2 that there is a TMD-TO distinguishing attack of TMD-cost $\tilde {O}(2^{(1/2)n})$ against any KSG-based stream cipher working in packet mode if the packet length exceeds the inner state length n.

To the best of our knowledge, this is the first time that a formal random oracle model for the security of stream ciphers against generic TMD-TO attacks is considered. So far, similar models were used, e.g., for analyzing the security of operation modes of key-alternating block cipher constructions (see the framework of iterated Even-Mansour ciphers), or of cryptographic hash functions, or of MAC algorithms, but not for stream ciphers.

Note that in [8], another way of formally analyzing the security of stream cipher constructions was proposed, namely in the complexity-theoretic framework of pseudorandom number generators and pseudorandom function generators.

In 2015, Armknecht and Mikhalev suggested with Sprout [4] another construction method for stream ciphers with beyond-the-birthday-bound security against TMD-TO attacks. In Sprout, the symmetric secret key is not only accessed during the state initialization but also continuously used as part of the state update during the subsequent keystream generation phase. The hope here was to obtain stream ciphers with the maximal possible resistance against TMD-TO attacks.

Although Sprout was broken soon after publication via non-generic attacks (see, e.g., [6, 17, 27, 33]), it has raised interest in the design principle and a number of related ciphers have been suggested since, including Fruit [20] and Plantlet [30]. Very recently, however, it has been shown in [23] that this whole class of Sprout-like ciphers is susceptible to generic TMD-TO distinguishing attacks (with complexity about $2^{n/2}$) and, hence, does not meet the original expectation of providing full TMD-TO security. This emphasizes the importance of provable resistance against TMD-TO attacks as a design criterion for new stream cipher constructions.

As already mentioned, the Lizard-construction, offering provable beyond-the-birthday-bound security against TMD-TO key recovery attacks, has inspired the design of the recently published lightweight stream cipher Lizard [22]. Lizard works in packet mode with a packet length of $R\le 2^{18}$ bits, has a state initialization algorithm of type (1), and an inner state length of 121 bits. The design features of Lizard presented in [22] show that the Lizard-construction allows for practical instantiations which are competitive w.r.t. important hardware metrics for lightweight devices such as chip area and power consumption. The maximum packet length of $R\le 2^{18}$ bits was chosen by the designers as large as necessary, but as small as possible. More precisely, in [22], an overview over the most prominent packet-based (encrypted) communication scenarios (such as cellular networks, Bluetooth, WLAN, HTTPS etc.) is given. While Bluetooth packets contain at most $2^{12}$ bits for the so-called basic rate and in WLAN connections, at most $2^{16}$ bits are encrypted under the same key/IV pair, the current TLS version 1.2 [15] (underlying HTTPS) requires to encrypt at most $2^{17} + 2^{13} < 2^{18}$ bits per packet, hence the limit of $R\le 2^{18}$ for Lizard. Based on the principle as small as possible, the limit was not chosen larger in order to keep the impact of distinguishing attacks to a tolerable level. For an in-depth discussion of this, we refer the reader to Section 4.2 of [22], where a concrete example based on the maximum packet length of $2^{18}$ for Lizard is given.

Recently, interesting cryptanalytic results for Lizard have been published in [7, 29, 31]. Please note, however, that none of these papers violates the security claims made in the Lizard specification and, hence, breaks the ciphers. In particular, the analysis provided in [7, 29, 31] does not indicate any weakness of the general Lizard-construction design principle. To avoid potential misconceptions, it is especially important to realize that the algorithms in [7] for computing key-IV pairs which produce identical initial states (and, hence, identical keystreams) do not lead to actual attacks. This is due to the fact that in these algorithms, the attacker chooses the keys himself. This way, he is able to invert Phase 3 (the second key addition) of Lizard’s state initialization and generate some key-IV pair that leads to a given initial state. However, the algorithms in [7] do not provide any indication on how to efficiently find the actual secret key if the attacker is only given an initial state together with the IV that was used to generate it (under this secret key).

Structure of the paper

In Section 2, we discuss security-relevant properties of the stream cipher components $\mathit {MIX}$ and $\mathit {OUTBLOCK}$ and describe the structure of some existing stream ciphers in terms of these components. In Section 3, we describe three TMD-TO attacks against KSG-based stream ciphers, including one against the Lizard-construction. In Section 4, we introduce the random oracle model for stream ciphers. Section 5 contains the corresponding lower bound results. Section 6 concludes the paper by summarizing our results and showing some directions of further research.

2 More on stream ciphers

In this section, we first discuss some concrete security-relevant issues of the components $\mathit {MIX}$ and $\mathit {OUTBLOCK}$ of KSG-based stream ciphers. After this, we describe the state initialization algorithms of some concrete stream ciphers in terms of our formalism.

Let us fix a KSG of inner state length n, and let $\pi$ and $\mathit {outbit}$ define its state transition and output bit function, respectively. Observe first that the corresponding function $\mathit {OUTBLOCK}$ is $\pi$-iterative in the following sense:

Definition 2

A function $F:\left \{0,1\right \}^{n}\longrightarrow \left \{0,1\right \}^{n}$ is called $\pi$-iterative if for all inputs $y\in \left \{0,1\right \}^{n}$ it holds that the suffix of length n − 1 of $F(y)$ equals the prefix of length $n-1$ of $F(\pi (y))$.

Observe next that $\mathit {OUTBLOCK}$ should be preimage resistant in the sense that it is infeasible to compute, for given $z\in \left \{0,1\right \}^{n}$, a value $y\in \left \{0,1\right \}^{n}$ fulfilling $\mathit {OUTBLOCK}(y)=z$. Otherwise, it would be feasible to predict, on the basis of the first n keystream bits of a packet, all remaining keystream bits of this packet.

Concerning $\mathit {MIX}$, observe that standard efficiency and security assumptions on KSGs imply that $\mathit {MIX}$ should be an efficiently computable function which behaves like a random function with respect to important properties such as correlation immunity, algebraic degree, or resistance against conditional differential cryptanalysis. Moreover, in most stream ciphers, $\mathit {MIX}$ is bijective and can be inverted efficiently (see the examples below).

These properties will be reflected in our security analysis in the way that $\mathit {OUTBLOCK}$ is assumed to be a randomly chosen $\pi$-iterative function and that $\mathit {MIX}$ is assumed to be a randomly chosen permutation which can be inverted efficiently.

Note here that for many practical KSG-based stream ciphers, the component $\mathit {OUTBLOCK}$ may deviate from behaving like a random function in the following respect. For efficiency reasons, the state transition function $\pi$ and the output bit function $\mathit {outbit}$ are oftenly defined to be of low degree. According to Definition 1, this implies that a small number of output bits of $\mathit {OUTBLOCK}$ (namely the leftmost ones) can have a lower degree than expected for a random function, and consequently that the stream cipher can have a lowered sampling resistance in the sense of [9] and [10]. As described there, this could be used for reducing the cost of certain TMD-TO attacks in a non-generic manner. This allowed, e.g., a very efficient attack on the A5/1-cipher (see [10]). As for the asymptotic behavior of TMD-TO attacks the cost reductions of techniques like BSW-sampling (see [10]) are rather negligible, we do not consider this effect in our security model. However, the possibility of a lowered sampling resistance has to be considered in the design of concrete stream ciphers.

We conclude this section by describing the state initialization algorithm of some relevant stream ciphers and expressing them by our formalism.

Trivium

The stream cipher Trivium has an inner state of length 288 bits, distributed over three nonlinear feedback shift registers (NFSRs) of lengths 93 bits, 84 bits, and 111 bits. The state update function consists of the corresponding three feedback functions, which in each case are quadratic and take their inputs from two of the three NFSRs. The linear output function XORs six inner state bits, two from each NFSR. The loading state $q_{\text {load}}(k,\mathit {IV})=(k||\mathit {IV}||\mathit {CONST})$ is defined to be the concatenation of the 80-bit session key k, the 80-bit IV $\mathit {IV}$ and a predefined 128-bit constant $\mathit {CONST}$. In the mixing phase, the KSG is clocked $4\cdot 288$ times without producing output (see [12] for more details). Consequently,

$$ q_{\text{init}}=q_{\text{mixed}}=\mathit{MIX}(k||\mathit{IV}||\mathit{CONST}). $$

(3)

Grain v1

The stream cipher Grain v1 has an inner state of length 160 bits, distributed over one NFSR and one linear feedback shift register (LFSR), both of length 80 bits. The state update function consists of the corresponding two feedback functions, where the NFSR feedback function depends also on one of the LFSR bits. The output function produces one keystream bit per clock cycle and depends nonlinearly on five LFSR bits and one NFSR bit and linearly on further seven NFSR bits. The loading state $q_{\text {load}}(k,\mathit {IV},\mathit {CONST})$ is defined to be the concatenation of the 80-bit session key k, a 64-bit IV $\mathit {IV}$ and a predefined 16-bit constant $\mathit {CONST}$. In the mixing phase, the Grain-KSG is clocked 160 times, where, in each clock cycle, the corresponding output keystream bit is XORed to the result of each of the two feedback functions (see [25] for more details). Consequently, we have again

$$ q_{\text{init}}=q_{\text{mixed}}=\mathit{MIX}(k||\mathit{IV}||\mathit{CONST}). $$

(4)

E ₀ (Bluetooth)

Bluetooth works in packet mode with a packet length $R\le 2745$ bits.¹ The inner state length of $E_{0}$ is 132 bits, distributed over four LFSRs of overall length 128 bits and an extra finite state machine of inner state length four bits. The state update function updates all LFSRs separately. The state transition of the 4-bit finite state machine additionally depends on four bits from the LFSRs. The output function XORs the output bits of the LFSRs with the nonlinear 1-bit output of the finite state machine.

For each packet i, the initial value $\mathit {IV}^{i}$ is composed of the 48-bit Bluetooth address of the master device, 26 bits of the master’s clock (to which both devices are synchronized) at the time of the first transmission slot of this packet, and two 3-bit constants. The $E_{0}$ cipher loads k and $\mathit {IV}^{i}$ stepwise to the register cells of the KSG, resulting in the inner state $q_{\text {load}}^{i}=L(k)\oplus \tilde {L}(\mathit {IV}^{i})$, where $L,\tilde {L}$ denote linear functions defined by the four linear feedback shift registers of the $E_{0}$-KSG. Subsequently, the generator is clocked 56 times and the output is discarded. Based on the resulting inner state of the $E_{0}$-KSG, 128 keystream bits are then computed without outputting them. Instead, they are copied into the LFSR register cells, overwriting the old inner state (see [32] for more details). Consequently, the state initialization algorithm of $E_{0}$ can be modeled as

$$ q_{\text{init}}^{i}=q_{\text{mixed}}^{i}=\mathit{MIX}\left(L\left(k\right)\oplus \tilde{L}\left(\mathit{IV}^{i}\right)\right). $$

(5)

For a more precise description of the rather involved structure and key/IV loading of $E_{0}$, we refer the reader to, e.g., Section 3.1 of [21]. Note that $E_{0}$ has to be considered broken as, e.g., in [28], a key recovery attack which only requires the first 24 bits of $2^{23.8}$ frames and $2^{38}$ computations is presented.

LIZARD

The definition of Lizard is inspired by the Grain family [24] of stream ciphers. It employs 120-bit keys and 64-bit IVs, targeting a security level of 80 bits against key recovery and 60 bits against distinguishing. In opposite to Grain, Lizard is designed for working in packet mode with a packet length of $2^{18}$ bits. It has an inner state length of 121 bits, distributed over two NFSRs of lengths 90 bits and 31 bits, and a nonlinear output function (see [22] for more details). The prominent innovation of Lizard is that the state initialization algorithm is designed according to the scheme in Relation (1), i.e.,

$$ q_{\text{init}}^{i}=q_{\text{mixed}}^{i}\oplus k=\mathit{MIX}\left(k\oplus \mathit{IV}^{i}\right)\oplus k. $$

(6)

Obviously, the above numbers w.r.t. key size, IV size, and inner state size do not directly match Relation 6. In particular, for efficiency reasons, in Lizard the IV is only of size 64 bits and corresponds to the 120-bit string ${\mathit {IV}^{i}_{0}},\ldots ,\mathit {IV}^{i}_{63},0,\ldots ,0$ in terms of the general Lizard-construction. In Section 4, we explain why the general security promise of the Lizard-construction still carries over to its concrete instantiation Lizard. For further details, e.g., relating the fact that in Lizard, the state size is one bit larger than the key size, we refer the reader to the Section 3.5 of [22].

In Table 1, an overview of the above stream ciphers in terms of our model is presented. For $E_{0}$ (used in Bluetooth), we give the IV size as 74 bits based on the contained 48-bit Bluetooth address of the master device and the 26 bits of the master’s clock at the time of the first transmission slot of the respective packet (as described above). Note, however, that an attacker targeting a specific connection between two devices will only have to deal with the changing 26 bits of the master’s clock as part of the IV, as, in this situation, the 48-bit Bluetooth address of the master device is constant. Furthermore, for $E_{0}$, we do not list any security claims in the column Security Level of Table 1, as the Bluetooth specification [32] does not provide any such specific commitments. However, despite the fact that already non-generic attacks (such as [28]) exists for $E_{0}$, through Theorem 3 in Section 3 we emphasize that, in general, such a construction can only reach a security level of $n/2$, where $n = 132$ bits in the case of $E_{0}$.

Table 1 An overview of the some prominent stream ciphers in terms of our model. Key Rec. stands for key recovery and Dist. for distinguishing

3 Time-Memory-Data tradeoff attacks

In this section, we first make some general remarks on TMD-TO attacks against KSG-based stream ciphers and then describe four such attacks. As already mentioned, we consider KSG-based stream ciphers to be defined by the inner state length n, the key length $\mathit {KL}$, the IV length $\mathit {IVL}$, and the algorithmic components $\mathit {LOAD}:\left \{0,1\right \}^{\mathit {KL}}\times \left \{0,1\right \}^{\mathit {IVL}}\longrightarrow \left \{0,1\right \}^{n}$, $\mathit {MIX}:\left \{0,1\right \}^{n}\longrightarrow \left \{0,1\right \}^{n}$, and $\mathit {OUTBLOCK}:\left \{0,1\right \}^{n}\longrightarrow \left \{0,1\right \}^{n}$. A TMD-TO attacker is supposed to know a certain amount of keystream (usually called data), which has its origin in one session, i.e., it was generated under one secret session key k. TMD-TO attacks are generic in the sense that they assume that the security-relevant components $\mathit {MIX}$ and $\mathit {OUTBLOCK}$ are ideally designed, which is reflected by the assumption that the attacker has only black-box access to $\mathit {MIX}$ and $\mathit {OUTBLOCK}$. One distinguishes passive TMD-TO attacks, in which the attacker knows a certain amount of keystream generated w.r.t. to one or several IVs known to her, and active TMD-TO attacks, in which the attacker gets keystream packets generated w.r.t. to IVs of her choice. Note that the TMD-TO attacks discussed in this section are passive, while our security lower bound in Section 5 refers to active TMD-TO attacks.

Depending on the goal of the attack, we distinguish four types of TMD-TO attacks, namely 1.) session key recovery attacks, 2.) inner state recovery attacks, 3.) packet prediction attacks, and 4.) distinguishing attacks. The goal of attacks of type 1.) is to recover the secret session key under which the given data was generated, where the goal of attacks of type 2.) is to recover at least one inner state q for which the corresponding piece of keystream $\mathit {OUTBLOCK}(q)$ belongs to the given data. Attacks of type 3.) refer to ciphers working in packet mode. Here the goal is to compute a pair $(IV,z)\in \left \{0,1\right \}^{\mathit {IVL}}\times \left \{0,1\right \}^{n}$, where IV denotes a new initial value which is not associated with the given data, and $z=\mathit {OUTBLOCK}(q_{\text {init}}(IV,k))$ is the prefix of length n of the packet generated on initial value IV under the given secret session key k. The goal of a distinguishing attack against a given cipher is to decide if the given data is generated in a pseudorandom scenario or in a random scenario. In the pseudorandom scenario, the data is generated by the cipher on the basis of a randomly chosen secret session key, while in the random scenario the data is generated by a random bit generator. Besides the running time, a relevant cost parameter of distinguishing attacks is the advantage, which is defined to be the difference of two conditional probabilities, namely that the attacker outputs pseudorandom in the pseudorandom scenario, and that the attacker outputs pseudorandom in the random scenario. TMD-TO attacks are usually randomized algorithms. The success probability of an attack is the probability of the event that the attacker reaches her goal, where the underlying probability space is defined by the random choice of the secret information and the internal randomization of the attacker.

Following [9] and [10], TMD-TO attacks are considered to be divided into a (key-independent) precomputation phase, in which, based on the components of the cipher, some search data structure is constructed, and the online phase, in which the now given data (e.g., passively or actively obtained keystream) is used for reaching the attack goal based on the previously computed search data structure. Corresponding to this, TMD-TO attacks are associated with the cost metrics P (time of the precomputation phase), M (memory), T (time of the online phase), and D (data), which are scalable in the sense that a smaller amount of one resource (e.g., data) can be compensated by a larger amount of other resources (e.g., memory and time). This implies that the cost behavior of TMD-TO attacks is usually expressed as a so-called tradeoff curve of type $f(P,M,T,D)=B$, where f is some real function depending on $P,M,T,D$ and B is some real number. The interpretation is that if one invests precomputation time P, online time T, memory M, and data D such that $f(P,M,T,D)=B$, then the attack reaches its goal with significant success probability. For instance, the tradeoff curve of Babbage’s attack is $T\cdot D = 2^{n}$.

In our context, we concentrate on the overall time $P+T$ needed by both phases. We understand under the minimum TMD-cost of a TMD-TO attack the minimal number C for which the relation $f(P,M,T,D)=B$ can be fulfilled under the condition that $P+T$ does not exceed C. Note that $P+T\le C$ implies $D\le C$ and $M\le C$. This is due to the fact that the relations $P+T\ge M$ and $T\ge D$ always hold. Note that the tradeoff curve $T\cdot D = 2^{n}$ of Babbage’s attack implies a minimum TMD-cost of $C = 2^{n/2}$.

The typical basic operations of TMD-TO attacks are operations over n-bit blocks (inner states or n-bit blocks of keystream bits) such as comparing them or searching for them in a data base, where n denotes the inner state length of the underlying cipher. This is the reason why usually the $\tilde {O}(\cdot )$-notation is used for expressing the asymptotic cost behavior of TMD-TO attack algorithms. Running time $\tilde {O}(f(n))$ means that the attack performs $O(f(n))$ basic operations over n-bit blocks.

At some places, we use the relation $\lim _{N\rightarrow \infty } (1-\frac {1}{N})^{N}=e^{-1}$. This relation implies that the probability that at least one of N independent trials with success probability $\frac {1}{N}$ is successful, is greater than $\frac {1}{4}$ if $N>2$ and around $1-e^{-1}$ if N is large enough.

Let us start with the the traditional inner state recovery attack of Babbage in [5]:

Theorem 1

We consider a KSG-based stream cipher of inner state length n working in packet mode or in one-stream mode. Suppose that attacker Eve knows D different keystream sequences (which may be from different packets) of length at least n. Then Eve can compute the initial state of at least one packet in time $\tilde {O}(2^{n}/D)$ with success probability greater than $\frac {1}{4}$ if $n>1$(and close to $1-e^{-1}$ if n is large enough), which implies a tradeoff curve $T\cdot D = 2^{n}$ and minimum TMD-cost $2^{n/2}$.

Proof of Theorem 1

Eve generates $T = 2^{n}/D$ times a pair $(y,\mathit {OUTBLOCK}(y))$ for randomly and independently chosen inner states $y \in \left \{0,1\right \}^{n}$. As $T\cdot D = 2^{n}$, with probability around $1-e^{-1}$ there is some pair $(y,\mathit {OUTBLOCK}(y))$ such that y equals one of the inner states behind the D keystream subsequences of length n known to Eve. As the state transition function $\pi$ is efficiently invertible, this allows to efficiently compute the secret initial state $q_{\text {init}}^{i}$ of the corresponding packet, respectively of the only initial state $q_{\text {init}}$ if the cipher runs in one-stream mode. Setting $T=D = 2^{n/2}$ implies an attack of time and data $\tilde {O}(2^{n/2})$. □

In one-stream mode, the attack in Theorem 1 discovers the only initial state $q_{\text {init}}$ and, thus, the whole keystream of this session. In packet mode, the initial state of at least one packet is discovered and, thus, the whole packet can be computed.

In the following, we show that the attack in Theorem 1 can be converted into a distinguishing attack of the same minimal TMD-cost against ciphers working in packet mode if the packet length is greater than the inner state length.

Theorem 2

We consider a KSG-based stream cipher of inner state length n working in packet mode with packet length $R=n + 1$. Suppose that Eve knows data consisting of D different keystream packets. Then Eve can distinguish the pseudorandom scenario from the random scenario in time $\tilde {O}(2^{n}/D)$ with advantage around $\sqrt {e^{-1}}-e^{-1}$.

Proof of Theorem 2

For each inner state $y \in \left \{0,1\right \}^{n}$, we denote by $Z(y)\in \left \{0,1\right \}^{n + 1}$ the sequence of the first $n + 1$ keystream bits generated on initial state y. Moreover, let ${\mathcal D}^{*}$ denote the set of all those packets $Z\in \left \{0,1\right \}^{n + 1}$ contained in the data for which there is some inner state $y\in \left \{0,1\right \}^{n}$ with $Z(y)=Z$. We know that in the pseudorandom case all D packets contained in the data belong to ${\mathcal D}^{*}$, while in the random case the probability that $|{\mathcal D}^{*}|$ deviates significantly from $D/2$ is negligibly small.

Eve now generates at most $T = 2^{n}/D$ times a pair $(y,Z(y))$ for randomly and independently chosen inner states $y \in \left \{0,1\right \}^{n}$ and stops with output pseudorandom if she gets a collision, i.e., if she generated some y for which $Z(y)$ coincides with one of the D packets contained in the data. If after $T = 2^{n}/D$ rounds no collision happened, she stops and outputs random.

By the same arguments as in the proof of Theorem 1 it follows that in the pseudorandom case the probability that Eve outputs pseudorandom is around $1-e^{-1}$. In the random case, the probability that Eve outputs pseudorandom is around $1-(1-\frac {D/2}{2^{n}})^{2^{n}/D} \approx 1-\sqrt {e^{-1}}$. This implies an advantage of

$$\begin{array}{@{}rcl@{}} \left|\left(1-e^{-1}\right) - \left(1-\sqrt{e^{-1}}\right)\right| = \sqrt{e^{-1}}-e^{-1}. \end{array} $$

□

Theorem 2 shows that with respect to distinguishing attacks, KSG-based stream ciphers, even if they run in packet mode, cannot reach beyond-the-birthday-bound security. But what about the security against attacks with more complex goals such as packet prediction attacks and session key recovery attacks? Theorem 1 shows that for achieving a higher resistance than $\tilde {O}(2^{n/2})$ it must be hard to compute the secret session key from a given packet initial state. Note that this is not true for Trivium, Grain, and A5/1, as for all these ciphers $\mathit {MIX}$ is efficiently invertible and its result is taken directly as the initial state. The following theorem shows that even if the mixing algorithm is presumably preimage resistant (as in the case of the Bluetooth cipher $E_{0}$), the security against session key recovery attacks will be only $n/2$ if the state initialization algorithm implies that the packet initial states are equal to the packet mixing states (as it is the case for $E_{0}$).

Theorem 3

We consider a KSG-based stream cipher working in packet mode with a state initialization for which the packet initial states are equal to the packet mixing states. Then, with probability around $1-e^{-1}$, Eve can compute the secret session key in time $\tilde {O}(2^{n}/D)$ if she knows D different n-bit keystream packet prefixes (which implies a tradeoff curve $T\cdot D = 2^{n}$ andminimum TMD-cost $2^{n/2}$).

Proof of Theorem 3

By the assumption it holds that

$$q_{\text{init}}^{i}=\mathit{MIX}\left(q_{\text{load}}\left(k,\mathit{IV}^{i}\right)\right) $$

for all packets i.

Eve generates $T = 2^{n}/D$ times a pair $(q,\mathit {OUTBLOCK}(\mathit {MIX}(q)))$ for randomly and independently chosen inner states $q \in \left \{0,1\right \}^{n}$. As $T\cdot D = 2^{n}$, with probability around $1-e^{-1}$, for some q, $\mathit {MIX}(q)$ equals the initial state of one of the D prefixes known to Eve, which implies q = q_load(k,IV ⁱ). This allows to compute k from q as $\mathit {IV}^{i}$ is public. Here we assumed that k can be efficiently computed from $q_{\text {load}}(k,\mathit {IV}^{i})$ and $\mathit {IV}^{i}$, which is true for all KSG-based stream ciphers which are known to us. □

Theorem 3 shows that for achieving beyond-the-birthday-bound security against generic TMD-TO attacks, the state initialization algorithm has to provide

$$q_{\text{init}}^{i}\neq \mathit{MIX}(q_{\text{load}}(k,\mathit{IV}^{i})). $$

The main result of this paper is to show that beyond-the-birthday-bound security against packet prediction and session key recovery TMD-TO attacks can be achieved if the packet initial states are computed according to the Lizard-construction (see Relation (1)), i.e., as

$$q_{\text{init}}^{i}=\mathit{MIX}\left(q_{\text{load}}^{i}\right)\oplus k, $$

where $q_{\text {load}}^{i}=k\oplus \mathit {IV}^{i}$. But before we go into the details of the corresponding lower bound proof, the next theorem will first show a respective upper bound, namely a session key recovery TMD-TO attack with minimal TMD-cost $\tilde {O}(2^{(2/3)n})$ against the Lizard-construction.

Theorem 4

We consider a KSG-based stream cipher working in packet mode for which the inner state length n equals the initial value length and the session key length, and we assume that for all $i\ge 1$ the packet initial states $q_{\text {init}}^{i}$ are generated according to Relation(1), see above. Suppose thatEve knows a set of D packet prefixes of length n, i.e., a set of pairs $\{(\mathit {IV}^{i},\mathit {PREFIX}(\mathit {IV}^{i}));i\in I^{*}\}$ for a set $I^{*}\subseteq \mathbb {N}$, where $D=|I^{*}| \geq 2^{n/2}$ and, for each $i\in I^{*}$,

$$\mathit{PREFIX}\left(\mathit{IV}^{i}\right)=\mathit{OUTBLOCK}\left(\mathit{MIX}\left(\mathit{IV}^{i}\oplus k\right)\oplus k\right). $$

Then, with constant positive probability, Eve can compute the secret session key in time $\tilde {O}(D+\frac {2^{2n}}{D^{2}})$, which implies TMD-cost of $\tilde {O}(2^{(2/3)n})$.

Proof of Theorem 4

Our attack uses the idea of the Slidex attack of Dunkelman, Keller, and Shamir [16] against the one-key Even-Mansour cipher. We describe the attack but only sketch the analysis of the success probability. For an exact specification of the success probabilities we refer to [16]. Note that our attack does not have a preprocessing phase.

Let $Q^{*}$ denote the set of all initial states corresponding to the indices in I^∗, i.e.,

$$Q^{*}=\left\{\mathit{MIX}\left(\mathit{IV}^{i}\oplus k\right)\oplus k;i\in I^{*}\right\}. $$

Observe that before starting the attack, $Q^{*}$ is unknown to Eve. The attack now consists of two phases.

In the first phase, Eve generates D times a pair $(q,\mathit {OUTBLOCK}(q))$ for randomly and independently chosen inner states $q\in \left \{0,1\right \}^{n}$. Whenever q falls into $Q^{*}$, which happens with probability $\frac {D}{2^{n}}$, Eve sees a collision of $\mathit {OUTBLOCK}(q)$ with $\mathit {PREFIX}(\mathit {IV}^{i})$ for some $i\in I^{*}$ and it holds $\mathit {MIX}(\mathit {IV}^{i}\oplus k)\oplus k=q$. Consequently, after the first phase, a standard Chernoff bound argument yields that Eve knows with constant positive probability a set of pairs {(IV ⁱ,q_init(IV ⁱ));i ∈ I^∗∗} for some $I^{**}\subseteq I^{*}$ with $|I^{**}|\ge \frac {D^{2}}{2^{n}}$.

In a second phase, Eve generates $\frac {2^{n}}{D^{2}/2^{n}}=\frac {2^{2n}}{D^{2}}$ times a pair $(u,\mathit {MIX}(u))$ for randomly and independently chosen inner states $u\in \left \{0,1\right \}^{n}$. Eve stops with u if

$$ u \oplus \mathit{IV}^{i} =\mathit{MIX}(u)\oplus q_{\text{init}}(\mathit{IV}^{i}) $$

(7)

for some $i\in I^{**}$ and publishes the hypothesis that $u\oplus \mathit {IV}^{i}$ equals the secret session key k.

In [16], it is shown that the event that Relation (7) holds implies the event $k=u\oplus \mathit {IV}^{i}$ with positive constant probability if $\mathit {MIX}$ is supposed to behave like a random permutation. Note further that, as $\frac {2^{2n}}{D^{2}}\cdot |I^{**}|\geq \frac {2^{2n}}{D^{2}}\cdot \frac {D^{2}}{2^{n}}= 2^{n}$, the event that Relation (7) is fulfilled during the second phase happens with probability around $1-e^{-1}$. □

4 A random oracle model for the LIZARD-Construction

In this section, we introduce a random oracle model which allows to prove information-theoretic lower bounds on the security of KSG-based stream ciphers against TMD-TO attacks. In this model we suppose that the components $\mathit {MIX}$ and $\mathit {OUTBLOCK}$ of a given KSG-based stream cipher are ideally designed and that an attacker has only black-box oracle access to these components. In this sense, random oracle models allow to analyze the power of generic attacks, which do not exploit possible cryptographic weaknesses of the components $\mathit {MIX}$ and $\mathit {OUTBLOCK}$, but concentrate on the way how these components interact in computing the keystream from the secret session key and public initial values. Note that all TMD-TO attacks presented in Section 3 have this generic nature and can be formulated in our random oracle model in a straightforward way.

We start with a formal definition which gives an exact specification of the notion Lizard-construction.

Definition 3

A KSG-based stream cipher is called to be designed according to the Lizard-construction if it fulfills the following criteria:

• (L1) The construction refers to three auxiliary parameters $n,\pi ,R$, where n denotes the inner state length, $\pi :\left \{0,1\right \}^{n}\longrightarrow \left \{0,1\right \}^{n}$ denotes the state transition function of the underlying KSG, and R denotes the packet length. It is required that $R\ge n$, that $\pi$ is bijective, and that for all inner states $q\in \left \{0,1\right \}^{n}$ the period of the sequence $(\pi ^{r}(q))_{r = 0}^{\infty }$ is greater than R.

• (L2) The construction refers to a set of secret session keys and a set of public initial values, which are both defined to be $\left \{0,1\right \}^{n}$. Moreover, the construction refers to an ideal bijective state mixing function $\mathit {MIX}:\left \{0,1\right \}^{n}\longrightarrow \left \{0,1\right \}^{n}$, which behaves like a random permutation over $\left \{0,1\right \}^{n}$, and an ideal $\pi$-iterative output block function $\mathit {OUTBLOCK}:\left \{0,1\right \}^{n}\longrightarrow \left \{0,1\right \}^{n}$, which behaves like a random $\pi$-iterative function over $\left \{0,1\right \}^{n}$ (see Definition 2 for the definition of $\pi$-iterativeness). MIX and $\mathit {OUTBLOCK}$ are considered to be the main components of the cipher.

• (L3) The construction consists in the following rules how to generate from a secret key $k\in \left \{0,1\right \}^{n}$ and a packet initial value $\mathit {IV}\in \left \{0,1\right \}^{n}$ the packet initial state $q_{\text {init}}(k,\mathit {IV})\in \left \{0,1\right \}^{n}$ and the corresponding keystream packet $\mathit {PACKET}\left (k,\mathit {IV}\right ) = \mathit {PACKET}\left (q_{\text {init}}\left (k,\mathit {IV}\right )\right )\in \left \{0,1\right \}^{R}.$ Let

  $$ q_{\text{init}}\left(k,\mathit{IV}\right)=\mathit{MIX}\left(k\oplus \mathit{IV}\right)\oplus k $$

  (8)

  and

  $$\mathit{PACKET}\left(q_{\text{init}}\left(k,\mathit{IV}\right)\right)=\left(z_{0},z_{1},\cdots,z_{R-1}\right), $$

  where for all r, $0\le r\le R-n$, it holds

  $$ \left(z_{r},z_{r + 1},\cdots,z_{r+n-1}\right)=\mathit{OUTBLOCK}\left(\pi^{r}\left(q_{\text{init}}\left(k,\mathit{IV}\right)\right)\right). $$

  (9)

Note that Relation (9) corresponds to the usual keystream generation definition (see Section 2, especially Definition 1). Note further that the stream cipher Lizard, as defined in [22], differs from the design features of the Lizard-construction in some minor points, which do not harm our security bounds. For instance, in contrast to condition (L2), the IV length of Lizard is smaller than the inner state length. Observe that a smaller IV length means that an attacker can use only a smaller set of possible IVs as inputs of oracle queries in his attack. Thus, a smaller IV length lowers the power of a chosen-IV attacker, i.e., our security lower bounds also hold for a modified Lizard-construction of IV length smaller than n.

We model the security of the Lizard-construction against generic TMD-TO attacks by the adversary Eve’s success probability to win the following packet prediction game with a limited number of oracle queries against Alice, who holds a secret session key k. Eve has black-box access to the ideal components $\mathit {MIX}$ and $\mathit {OUTBLOCK}$, and is allowed to ask for keystream packets $\mathit {PACKET}(k,\mathit {IV}^{i})$ generated w.r.t. the secret session key k held by Alice and IVs $\mathit {IV}^{i}$ of Eve’s choice. Eve wins the game if, after asking a certain number of oracle queries, she is able to predict the keystream packet w.r.t. to a new IV, which has not been asked before.

From now on, we denote the component functions $\mathit {MIX}$ and $\mathit {OUTBLOCK}$ by P and F, respectively, the construction function $\mathit {PACKET}$ by E, and initial values by $x\in \left \{0,1\right \}^{n}$ (respectively $x^{\prime }$, $x^{*}$ etc.).

Definition 4 (The Packet Prediction Game)

• (i) The game depends on the global parameters $n,\pi ,R$, which satisfy the rules in Definition 3, and a parameter M, which bounds the number of oracle queries. The game is divided into a query phase and a prediction phase.

• (ii) At the beginning, Alice chooses randomly and w.r.t. the uniform distribution a secret triple $\omega =(k_{\omega },P_{\omega },F_{\omega })$, where

  • $k_{\omega }\in \left \{0,1\right \}^{n}$ denotes the secret session key,

  • $P_{\omega }:\left \{0,1\right \}^{n}\longrightarrow \left \{0,1\right \}^{n}$ denotes a random permutation (corresponding to $\mathit {MIX}$),

  • $F_{\omega }:\left \{0,1\right \}^{n}\longrightarrow \left \{0,1\right \}^{n}$ denotes a random $\pi$-iterative function (corresponding to $\mathit {OUTBLOCK}$).

  We denote by ${\Omega }$ the corresponding probability space of all such triples together with the uniform distribution.

• (iii) The adversary Eve is a randomized oracle algorithm of potentially unbounded computational power, who is allowed to pose component oracle queries of type $P(u)=?$, or $P^{-1}(v)=?$, or $F(y)=?$ for inputs $u,v\in \left \{0,1\right \}^{n}$ and $y\in \left \{0,1\right \}^{n}$, which are correctly answered by Alice by $P_{\omega }(u)$, $(P_{\omega })^{-1}(v)$, or $F_{\omega }(y)$, respectively.

• (iv) Moreover, Eve is allowed to pose construction queries of the form $E(x)=?$, where $x\in \left \{0,1\right \}^{n}$, which will be answered by Alice with the keystream packet $E_{\omega }(x)$ corresponding to the initial state

  $$y:=P_{\omega}(x\oplus k_{\omega})\oplus k_{\omega} $$

  induced by the session key $k_{\omega }$ and the initial value x (see Relation (8)). Note that this keystream packet $E_{\omega }(x)$ is the concatenation of $R/n$ F-values. In particular,

  $$E_{\omega}\left(x\right)=\left.F_{\omega}\left(y\right) \middle|\middle| F_{\omega}\left(\pi^{n}\left(y\right)\right) \middle|\middle| F_{\omega}\left(\pi^{2n}\left(y\right)\right) \middle|\middle| {\cdots} \middle|\middle| F_{\omega}\left(\pi^{(R/n-1)n}\left(y\right)\right)\right. . $$

  W.l.o.g., for the sake of simplicity we assume in our proof that n divides R.

• (v) In the query phase, Eve poses exactly M oracle queries. In the prediction phase, Eve has to submit a pair $(x^{*},z^{*})\in \left \{0,1\right \}^{n}\times \left \{0,1\right \}^{n}$, where $x^{*}$ does not occur as input of an E-query in the query phase. Eve wins if $z^{*}=F_{\omega }(P_{\omega }(x^{*}\oplus k_{\omega })\oplus k_{\omega })$, i.e., if $z^{*}$ equals the block of the first n bits of the keystream packet $E_{\omega }(x^{*})$ corresponding to the initial state $P_{\omega }(x^{*}\oplus k_{\omega })\oplus k_{\omega }$, i.e., the keystream packet corresponding to session key $k_{\omega }$ and initial value $x^{*}$.

• (vi) Besides the number M of oracle queries, the essential cost parameter is the winning probability of Eve, which is measured with respect to the uniform distribution on ${\Omega }$ and the internal randomization of Eve.

Observe that generic TMD-TO attacks (as described in Section 3) against the Lizard-construction can be formulated in a straightforward way as packet prediction or key recovery games in the sense of Definition 4. Here, the cost metric data (i.e., D) corresponds to the number of E-queries (possibly multiplied by the packet length), while each evaluation of the cipher components $\mathit {MIX}$ and $\mathit {OUTBLOCK}$ corresponds to a P-, $P^{-1}$-, or F-query in the sense of Definition 4. Note here that in a possible precomputation phase of a TMD-TO attack, only P-, $P^{-1}$-, or F-queries will be posed. Hence, the overall number of oracle queries in our game is a lower bound for the cost metric overall time (i.e., $T+P$; cf. Section 3) of the online phase and a possible precomputation phase of a corresponding generic TMD-TO attack against the Lizard-construction. Consequently, a lower bound on the number of oracle queries also lower bounds the minimum TMD-cost of TMD-TO attacks against the Lizard-construction.

Note here that evaluations of the state transition function $\pi$ by Eve do not count in our security analysis; it is supposed that $\pi$ is completely known to Eve. The function $\pi$ has to satisfy rule (L1) of Definition 3, but apart from that, no further security-relevant properties are required. Our lower bound arguments even work in the case that $\pi$ is linear.

We conclude this section by describing how a random uniformly distributed $\pi$-iterative function can be generated.

Generating a random π-iterative function F

Note that, as $\pi$ is bijective, the strongly connected components of the directed graph $G_{\pi }=(\left \{0,1\right \}^{n},E_{\pi })$, where $E_{\pi }=\{(v,\pi (v));v\in \left \{0,1\right \}^{n}\}$, are simple cycles $C^{1},\cdots ,C^{s}$ of sizes $d_{1},\cdots ,d_{s}$, which we call $\pi$-cycles.

For each $\pi$-cycle $C^{j}$, $1\le j\le s$, fix a starting point ${v^{j}_{0}}\in C^{j}$. Note that $C^{j}=\{{v^{j}_{0}},\cdots ,v^{j}_{d_{j}-1}\}$, where for all i, $1\le i\le d_{j}-1$, it holds ${v^{j}_{i}}=\pi ^{i}({v^{j}_{0}})$.

A uniformly distributed $\pi$-iterative function F can be defined by choosing for all j, $1\le j\le s$, randomly and independently a uniformly distributed bitstring

$$b^{j}=\left({b^{j}_{0}},\cdots,b^{j}_{d_{j}-1}\right)\in\left\{0,1\right\}^{d_{j}} $$

and defining $F({v^{j}_{i}})$ for all i, $0\le i\le d_{j}-1$, by

$$F\left({v^{j}_{i}}\right)=\left({b^{j}_{i}},b^{j}_{(i + 1) \bmod d_{j}},\cdots,b^{j}_{(i+n-1) \bmod d_{j}}\right). $$

Here we took into account that, by Definition 3, the sizes of the cycles are each larger than $R\ge n$. Note that the entropy of a random $\pi$-iterative function is $2^{n}$.

5 The security lower bound proof

5.1 Preliminaries

In this section, we show the main result of this paper, a sharp security lower bound for the Lizard-construction. At one essential point, our lower bound proof uses a combinatorial result proved by Chen, Lampe, Lee, Seurin, Steinberger in [13], namely Theorem 1 in Section 3, which is known as Sum-Capture Theorem.

For motivating the use of this result, let us consider the situation that Alice holds a secret triple $\omega =(k_{\omega },P_{\omega },F_{\omega })$ and that Eve asked a number of queries, where $U,X,Y\subseteq \left \{0,1\right \}^{n}$ denote the sets of inputs of the P-queries, E-queries and F-queries asked by Eve so far, respectively.

Definition 5 (Critical Triples)

A triple $(u,x,y)\in U\times X\times Y$ is called

• $\omega$-critical if $x\oplus u=P_{\omega }(u)\oplus y$,

• $\omega$-dangerous if $(u,x,y)$ is $\omega$-critical and $(x,y)$ form an $\omega$-collision in the sense that $F_{\omega }(y)$ equals the prefix of length n of the packet $E_{\omega }(x)$, and

• $\omega$-sudden death if $x\oplus u=P_{\omega }(u)\oplus y=k_{\omega }$.

It can be easily derived from Definition 4 that from $(u,x,y)$ is $\omega$-sudden death it follows that $(u,x,y)$ is $\omega$-dangerous and ω-critical. Note that Eve can immediately check if a given triple $(u,x,y)\in U\times X\times Y$ is $\omega$-critical or even $\omega$-dangerous. Note further that in our lower bound proof we will use a more general definition of collision than in Definition 5.

The following lemma shows that from Eve’s point of view it is desirable that the choice of $U,X,Y$ implies a sufficiently large set of $\omega$-critical triples.

Lemma 1

For all $\omega$ -critical triples $(u,x,y)\in U\times X\times Y$, it holds that if $(u,x,y)$ is not $\omega$-dangerous, then $x\oplus u\neq k_{\omega }$. If $(u,x,y)$ is $\omega$-dangerous, then $x\oplus u=k_{\omega }$ holds with significant probability.

Consequently, if Eve manages to construct an $\omega$-dangerous triple, then she wins with significant success probability. Note that the aim of the attack in Theorem 4 against the Lizard-construction is to construct an $\omega$-dangerous triple.

Proof of Lemma 1

If $x\oplus u=P_{\omega }(u)\oplus y$ and $x\oplus u=k_{\omega }$, then $y=P_{\omega }(x\oplus k_{\omega })\oplus k_{\omega }$, which implies that, by definition, $F_{\omega }(y)$ equals the prefix of length n of $E_{\omega }(x)$. Consequently, if $F_{\omega }(y)$ does not equal the prefix of length n of $E_{\omega }(x)$, then $x\oplus u\neq k_{\omega }$.

For the other direction, we sketch only the proof; the complete proof can be found in [16]. We suppose that $x\oplus u=P_{\omega }(u)\oplus y$ and that $F_{\omega }(y)$ equals the prefix of length n of $E_{\omega }(x)$. As $F_{\omega }$ is randomly chosen, it follows with high probability that $y=P_{\omega }(x\oplus k_{\omega })\oplus k_{\omega }$. Now let $M_{\omega }(u)$ denote the set of all $u^{\prime }\in \left \{0,1\right \}^{n}$ for which $u^{\prime }\oplus P_{\omega }(u^{\prime })=u\oplus P_{\omega }(u)$. As $P_{\omega }$ is randomly chosen, it can be shown that $|M_{\omega }(u)|\le n$ with high probability. Now observe that the events $x\oplus u=P_{\omega }(u)\oplus y$ and $y=P_{\omega }(x\oplus k_{\omega })\oplus k_{\omega }$ imply that $x\oplus k_{\omega }\in M_{\omega }(u)$. Consequently, $x\oplus k_{\omega }=u$ with probability $|M_{\omega }(u)|^{-1}$. □

Note that as Eve knows $P_{\omega }(u)$ for all $u\in U$ and as Eve has unbounded computational power, she is able to compute from $U,X,Y$ the set of all $\omega$-critical and all $\omega$-dangerous triples without further oracle queries.

Lemma 1 shows that Eve wins the game with high probability if she manages to pose the queries in such a way that for almost all keys $k\in \left \{0,1\right \}^{n}$ there is some $\omega$-critical triple $(u,x,y)\in U\times X\times Y$ fulfilling $x\oplus u=P_{\omega }(u)\oplus y=k$. We mention here that there is an algorithm which reaches this goal with high probability with $\tilde {O}(2^{(2/3)n})$ oracle queries. As the time cost of the corresponding TMD-TO attack is much worse than that of the attack described in Theorem 4, we omit the description of this algorithm.

The Sum-Capture Theorem from [13], which we present in a slightly modified form, shows that reaching this goal with significantly less than $\tilde {O}(2^{(2/3)n})$ oracle queries succeeds only with exponentially small success probability.

Theorem 5

Let P denote a uniformly random permutation over $\left \{0,1\right \}^{n}$, let $N = 2^{n}$ and fix an arbitrary number M, $9n\le M\le N/2$. Suppose that Eve (who is supposed to be a probabilistic algorithm) poses a sequence $U=\{u_{1},\cdots ,u_{M}\}$ of M P-queries. For any subsets $X,Y\subseteq \left \{0,1\right \}^{n}$ let

$$\mu(P,U,X,Y)=\left|\{(u,x,y)\in U\times X\times Y; x\oplus u=y\oplus P(u)\}\right|. $$

Then the probability for the event that there are subsets $X,Y\subseteq \left \{0,1\right \}^{n}$ such that

$$ \mu(P,U,X,Y)\ge \frac{M\cdot |X|\cdot |Y|}{N}+\frac{2M^{2}\cdot \sqrt{|X|\cdot |Y|}}{N}+ 3\sqrt{n\cdot M\cdot |X|\cdot |Y|} $$

(10)

is at most $\frac {2}{N}$, where the probability is taken over the random choice of P and the internal randomization of Eve. □

5.2 The main theorem

In this subsection, we formulate our main technical result (Theorem 6) and start with a technical definition:

Definition 6 (The Number[[spiespace)

]$B(M,R,n)$] For natural numbers $M,R,n$, with $R\ge n$, let

$$B(M,R,n)= 2^{-n}\cdot M^{3}\cdot \left(R+n-1 + 2\sqrt{R+n-1}\right)+ 3\cdot \sqrt{n\cdot M^{3}\cdot (R+n-1)}. $$

Note that $B(M,R,n)$ equals the term on the right-hand side of Relation (10) for $|X|=M$ and $|Y|=(R+n-1)M$.

Theorem 6 (Main Theorem)

Suppose that the parameters M, n, R satisfy the following rules for some number ${\Delta }$:

• (1) $B(M,R,n)+ 2\cdot {\Delta }\cdot M+\frac {(R+n)\cdot M^{2}}{{\Delta }}\le \left (1-\frac {1}{\sqrt {2}}\right )\cdot 2^{n}$,

• (2) $22\cdot 2^{-(n-1)}\cdot R\cdot M^{2}+\sqrt {\frac {n\cdot M}{2}}\le \frac {{\Delta }-(R+n-1)}{R+n-1}$,

• (3) ${\Delta }\cdot ((n+R)\cdot M)\le \ln {2}\cdot 2^{n-3}$.

Then Eve’s success probability to win the packet prediction game with parameters ${\Delta }$, R, n with M oracle queries is bounded by

$$ 34\cdot 2^{-n}+M\cdot e^{-n}+M\cdot ({\Delta}+ 2)\cdot 2^{-(n-1)}+ 11\cdot (R + 4n)\cdot M\cdot 2^{-(n-1)}. $$

This implies the following asymptotic lower bound result, which can be derived straightforwardly from Theorem 6.

Corollary 1 (Main Corollary)

Let $\epsilon >0$ and $a>1$ be constants and suppose that $M\le 2^{(\frac {2}{3}-\epsilon )n}$, $R\le n^{a}$ and ${\Delta }=\lfloor 2^{\frac {1}{3}n}\rfloor$. Then M, R, n, ${\Delta }$ satisfy all rules in Theorem6 and Eve’s success probability to win the packet prediction game with parameters ${\Delta }$, R, n with M oracle queries is bounded by $3\cdot 2^{-\epsilon \cdot n}$, if n is large enough. □

The remaining part of this paper is devoted to the proof of Theorem 6.

A first overview over the idea and the structure of the proof

We prove the security bound of Theorem 6 for deterministic adversaries. This is justified by the fact that each upper bound on the success probability of deterministic adversaries posing M queries also holds for randomized adversaries posing M queries. We give a proof of this folklore result at the beginning of Section 5.4. The fact that Eve is assumed to be deterministic allows to assign to each elementary event $\omega =(k_{\omega },P_{\omega },F_{\omega })$ a computation $\tau _{\omega }$, which is performed by Eve on $\omega$, and which is either successful (i.e., Eve wins), or not. Let us denote by ${\Omega }^{\text {succ}}\subseteq {\Omega }$ the set of all elementary events for which $\tau _{\omega }$ is successful. For showing that $\Pr _{{\Omega }}[{\Omega }^{\text {succ}}]$ fulfills the relation claimed in Theorem 6, we partition ${\Omega }$ into a set ${\Omega }^{\text {bad}}$ of bad events and a set ${\Omega }^{\text {good}}$ of good events, where bad events $\omega$ will have the property that the corresponding computation $\tau _{\omega }$ yields some nontrivial information on the secret key $k_{\omega }$, which helps Eve to win the game. An elementary event is called to be good if it is not bad.

This partition into bad and good elementary events allows to express the success probability of Eve as

$$\begin{array}{@{}rcl@{}} \Pr\limits_{{\Omega}}[{\Omega}^{\text{succ}}]&=&\Pr\limits_{{\Omega}}[{\Omega}^{\text{succ}}|{\Omega}^{\text{bad}}]\cdot \Pr\limits_{{\Omega}}[{\Omega}^{\text{bad}}]+ \Pr\limits_{{\Omega}}[{\Omega}^{\text{succ}}|{\Omega}^{\text{good}}]\cdot \Pr\limits_{{\Omega}}[{\Omega}^{\text{good}}]\\ &\le& \Pr\limits_{{\Omega}}[{\Omega}^{\text{bad}}]+\Pr\limits_{{\Omega}}[{\Omega}^{\text{succ}}|{\Omega}^{\text{good}}]. \end{array} $$

(11)

We prove Theorem 6 by deriving bounds for $\Pr _{{\Omega }}[{\Omega }^{\text {bad}}]$ and $\Pr _{{\Omega }}[{\Omega }^{\text {succ}}|{\Omega }^{\text {good}}]$. In particular, we will distinguish four sorts of bad events, namely sudden death events, black events, red events, and blue events, and denote the remaining sort of good elementary events to be green events. Corresponding to this, the proof Theorem 6 rests upon four pillars consisting in proving small upper bounds for the probability of 1.) the set of sudden death events, 2.) the set of black events, 3.) the event that a green elementary event determines a successful computation, and 4.) the set of red and blue events.

The proof of Theorem 6 is divided into three phases. In the first phase, which comprises Sections 5.3, 5.4, and 5.5, we slightly modify the operation mode of Alice, formalize the computational behavior of Eve, and discuss a number of basic properties of elementary events and computations of Eve. This enables us to give a more detailed overview about the remaining two phases of the proof, and to formulate our main lemma (Lemma 2). This lemma consists of four items corresponding to the formulation of the concrete bounds determining the four pillars of the proof mentioned above.

In the second phase, we develop the mathematical tools which are necessary for proving the items of Lemma 2 (Section 5.6 and Section 5.8). The intention of these tools, which we call basic methods, is to analyze and formalize Eve’s knowledge about the secret elementary event held by Alice under the condition that a certain computation $\tau$ has already happened, i.e., that a certain number of oracle queries has been posed and answered. This knowledge corresponds to the probability space ${\Omega }(\tau )$ formed by all elementary events which are consistent with the computation $\tau$. In the Consistency Lemma (Lemma 3 in Section 5.6) and the Smoothness Lemma (Lemma 5 in Section 5.8) the structure of this probability space ${\Omega }(\tau )$ is analyzed, especially that of the induced probability space $K(\tau )$ of all keys $k\in \left \{0,1\right \}^{n}$ which are consistent with $\tau$. The six items forming Corollary 2 in Section 5.8, which result from this analysis, can be seen as a toolbox of methods for handling all the different situations occurring in the proofs of the items of Lemma 2.

Moreover, in the second phase we give the definitions of sudden death, black, red, blue, and green elementary events and discuss basic properties of these definitions (Section 5.7). Informally, an elementary event $\omega$ is defined to fulfill the sudden death rule if during the computation $\tau _{\omega }$ an $\omega$-sudden death triple will be generated (see Definition 5 and Lemma 1). We have seen already in Lemma 1 that a sudden death event allows to determine the secret key with high probability.

The elementary event $\omega$ is defined to be black if during $\tau _{\omega }$ too many $\omega$-critical triples are generated. Lemma 1 showed that black events are dangerous for Alice as a large number of $\omega$-critical triples implies an $\omega$-dangerous triple (i.e., a sudden death event) with high probability.

The elementary event $\omega$ is called red if during $\tau _{\omega }$ too many $\omega$-collisions are generated. The danger of red events follows by Theorem 4, where it is shown how to recover the secret key on the basis of a large set of $\omega$-collisions.

Finally, $\omega$ is defined to be blue if the probability distribution corresponding to $K(\tau )$ differs too much from the uniform distribution. We have to exclude this case as our techniques for bounding the probability of certain bad events rest on the assumption that the keys in $K(\tau )$ are nearly uniformly distributed.

As the proofs of one part of Lemma 5 and some parts of Corollary 2 are quite long and tedious, we shifted them into Appendix C and B, respectively. In Appendix A, we derive a further basic method, a modified Chernoff bound technique, which is necessary for bounding the probability of red and blue elementary events.

In the third phase of the proof of Theorem 6, consisting of the Sections 5.9, 5.10, 5.11, and 5.12, we prove the four items of Lemma 2. As mentioned above, all these four proofs use the methods contained in Corollary 2.

We illustrate the modular structure of the proof of Theorem 6 in Fig. 3.

Fig. 3

The modular structure of the proof of the Main Theorem (Theorem 6)

5.3 Structural collisions, the friendly Alice, and sudden death

We will prove our security bound for a modified game, in which Alice is supposed to be friendly to Eve in the sense that in certain situations Alice provides some additional information to Eve. These situations will have to do with collisions, which can occur, e.g., between E-queries and F-queries, i.e., the E-query with an input x yields the same answer as the F-query with an input y. The reason for such a collision can be twofold. The first possible reason is that $y=P_{\omega }(x\oplus k_{\omega })\oplus k_{\omega }$. We will call this type of collision a structural EF-collision. Another reason can be that the values y and $P_{\omega }(x\oplus k_{\omega })\oplus k_{\omega }$ are a collision of the function $F_{\omega }$. Note that in the case of a structural collision, Eve obtains the valuable information that $y=P_{\omega }(x\oplus k_{\omega })\oplus k_{\omega }$. We have seen in Theorem 4 that the secret key can be computed by Eve on the basis of $2^{n/2}$ such pairs $(x,y)$, which highlights the importance of structural collisions. Another type of collisions are EE-collisions $(x,x^{\prime })$ of E-queries with inputs $x\neq x^{\prime }$. Here, too, we distinguish between structural collisions, where $P_{\omega }(x\oplus k_{\omega })\oplus k_{\omega }=P_{\omega }(x^{\prime }\oplus k_{\omega })\oplus k_{\omega }$, and non-structural collisions, where this is not the case but $P_{\omega }(x\oplus k_{\omega })\oplus k_{\omega }$ and $P_{\omega }(x^{\prime }\oplus k_{\omega })\oplus k_{\omega }$ are a collision of $F_{\omega }$. The friendly Alice will inform Eve if Eve managed to discover a structural collision. Moreover, she follows a sudden-death rule (see Definition 9), which has to do with structural collisions.

Definition 7 (Structural Collisions)

• A pair $(x,y)$, where $x,y\in \left \{0,1\right \}^{n}$, is called a structural EF-collision w.r.t. to an elementary event $\omega =(k_{\omega },P_{\omega },F_{\omega })$ if

  $$ y=\pi^{r}(P_{\omega}(x\oplus k_{\omega})\oplus k_{\omega}), $$

  (12)

  for some r, $-(n-1)\le r\le R-1$. Note that this implies that the n-bit block $F_{\omega }(y)$ is a subblock of packet $E_{\omega }(x)$ or has at least a nonempty intersection with packet $E_{\omega }(x)$.

• If $(x,y)$ is a structural EF-collision w.r.t. $\omega$, then the point $\bar {y}=P_{\omega }(x\oplus k_{\omega })\oplus k_{\omega }$ is called the reference point of this collision.

• A pair $(x,x^{\prime })$, where $x\neq x^{\prime }\in \left \{0,1\right \}^{n}$, is called a structural EE-collision w.r.t. to $\omega$ if the initial states of the packets $E_{\omega }(x)$ and $E_{\omega }(x^{\prime })$ come so close that these packets have a nonempty intersection, i.e., there is some number r, $1\le r\le R-1$, such that

  $$\begin{array}{@{}rcl@{}} \pi^{r}(P_{\omega}(x\oplus k_{\omega})\oplus k_{\omega})&=&P_{\omega}(x^{\prime}\oplus k_{\omega})\oplus k_{\omega}\text{ or }\\ \pi^{r}(P_{\omega}(x^{\prime}\oplus k_{\omega})\oplus k_{\omega})&=&P_{\omega}(x\oplus k_{\omega})\oplus k_{\omega}. \end{array} $$

  (13)

  Note that this implies that the suffix of packet $E_{\omega }(x)$ starting at position r equals the prefix of packet $E_{\omega }(x^{\prime })$ ending at position $R-(r-1)$, or that the suffix of packet $E_{\omega }(x^{\prime })$ starting at position r equals the prefix of packet $E_{\omega }(x)$ ending at position $R-(r-1)$.

Note here again that structural EF-collisions are exactly those collisions which are exploited in the TMD tradeoff attacks against the Lizard-construction described in Theorem 4.

Suppose that Alice holds the elementary event $\omega =(k_{\omega },P_{\omega },F_{\omega })$ and communicates with Eve. Note that if Eve detects a collision in the answers to her questions, she is not able to decide if it is a structural collision, and, in the case of a structural collision, she is not able to compute the reference point. The friendly Alice helps her in such situations in the following way:

Definition 8 (The Friendly Alice)

• Whenever Eve poses an F-query with some input $y\in \left \{0,1\right \}^{n}$ which forms a structural EF-collision $(x,y)$ w.r.t. $\omega$ for some $x\in \left \{0,1\right \}^{n}$ which already occurred as input of an E-query posed before, then, besides publishing $F_{\omega }(y)$, Alice confirms a structural collision, publishes a pointer to the input x and publishes the reference point $P_{\omega }(x\oplus k_{\omega })\oplus k_{\omega }$ of this collision.

• Whenever Eve poses an E-query with some input $x\in \left \{0,1\right \}^{n}$ which forms a structural EF-collision $(x,y)$ w.r.t. $\omega$ for some y which already occurred as input of an F-query posed before, then, besides publishing $E_{\omega }(x)$, Alice confirms a structural collision, publishes a pointer to y and publishes the reference point $P_{\omega }(x\oplus k_{\omega })\oplus k_{\omega }$ of this collision.

• Suppose that Eve poses an E-query with some input $x\in \left \{0,1\right \}^{n}$ which forms a structural EE-collision $(x,x^{\prime })$ w.r.t. $\omega$ for some $x^{\prime }$ which already occurred as input of another E-query posed before. Suppose w.l.o.g. that $\pi ^{r}(P_{\omega }(x\oplus k_{\omega })\oplus k_{\omega })=P_{\omega }(x^{\prime }\oplus k_{\omega })\oplus k_{\omega }$ for some r, $1\le r\le R-1$. Then, besides publishing $E_{\omega }(x)$, Alice confirms a structural EE-collision and publishes a pointer to $x^{\prime }$. Moreover, Alice publishes the value $y=\pi ^{r}(P_{\omega }(x\oplus k_{\omega })\oplus k_{\omega })=P_{\omega }(x^{\prime }\oplus k_{\omega })\oplus k_{\omega }$, the value $F_{\omega }(y)$, and the reference points $\bar {y}=P_{\omega }(x\oplus k_{\omega })\oplus k_{\omega }$ and y of the resulting structural EF-collisions $(x,y)$ and $(x^{\prime },\bar {y})$.

Next we formulate the sudden-death rule.

Definition 9 (Sudden Death)

Suppose that Alice holds an elementary event $\omega =(k_{\omega },P_{\omega },F_{\omega })$ and consider a situation in which Eve already posed a number of queries. A pair $(x,u)$, where $x,u\in \left \{0,1\right \}^{n}$, is called a sudden-death pair w.r.t. $\omega$ if the following conditions are fulfilled:

• Eve has already discovered a structural EF-collision $(x,y)$ (which implies that Eve has asked an E-query with input x).

• Eve has already asked a P-query with input u or a $P^{-1}$-query with output u.

• It holds $x\oplus u=k_{\omega }$.

Whenever Eve asks a query which causes a sudden-death pair w.r.t. to the secret $\omega$ held by Alice, then Alice immediately gives up, the game stops and Eve wins.

The motivation for considering sudden death pairs is given with Lemma 1. There it is proved that for each sudden death pair $(x,u)$ it holds with significant probability that $x\oplus u$ equals the secret session key $k_{\omega }$. Note that the TMD-TO attack described in Theorem 4 consists in generating a sudden-death pair.

Looking at the remarks motivating the consideration of structural collisions and sudden death pairs, it should be clear the the additional information given by a friendly Alice helps Eve in winning the game. The friendliness of Alice increases Eve’s chances to win the prediction game (any additional information which is provided for free does so). Consequently, it is sufficient to show the security lower bound of Theorem 6 for an adversary Eve who plays the packet prediction game with a friendly Alice. Note that the reason for considering a friendly Alice instead of an unrestricted one is to simplify the proof of Theorem 6.

5.4 Formalizing the computational behavior of Eve

First note the well-known fact, proved, e.g., in [13] and many other papers, that it is sufficient to prove our security lower bound for deterministic adversaries. For showing this suppose that Eve is randomized and that the randomization is organized by a number B of random bits. Then Eve’s success probability can be written as

$$ \Pr[\text{Eve successful}]=\sum\limits_{b\in\left\{0,1\right\}^{B}} 2^{-B} \Pr[\text{Eve successful} \mid b], $$

(14)

where $\Pr [\text {Eve successful} \mid b]$ denotes the success probability of the deterministic algorithm obtained by assigning b to Eve’s random bits.

Consequently, if we show an upper bound on the success probability of all deterministic adversaries then, by (14), this bound also holds for randomized adversaries.

Therefore, we assume from now on that Eve is deterministic.

Remember that, during each computation, Eve poses at most M oracle queries, where she either wins via sudden death of Alice or she stops after M queries with the publication of a pair consisting of an initial value $x^{*}\in \left \{0,1\right \}^{n}$ and a keystream prefix $z^{*}\in \left \{0,1\right \}^{n}$ as final output.

We identify such computations with transcripts

$$\tau=\left((\mathit{type}_{1},\mathit{input}_{1},\mathit{output}_{1}),\cdots,(\mathit{type}_{j},\mathit{input}_{j},\mathit{output}_{j})\right), $$

j ≤ M, which are defined to be sequences of query triples corresponding to the oracle queries posed during the computation.

Here, $\mathit {type}_{r}\in \{F,P^{-1},P,E\}$, $\mathit {input}_{r}$, and $\mathit {output}_{r}$ denote the type, the input, and the output of the r-th oracle query, $r = 1,\cdots ,j$, respectively. Note that the output of an oracle query can, besides the output function values of $P_{\omega }$, or $P_{\omega }^{-1}$, or $F_{\omega }$, or $E_{\omega }$, contain additional information about structural collisions discovered by this query (see Definition 8).

If $\tau$ has length M, then $(x^{*}(\tau ),z^{*}(\tau ))\in \left \{0,1\right \}^{n}\times \left \{0,1\right \}^{n}$ denotes the (initial value, keystream prefix) pair published after $\tau$ based on $\tau$.

For transcripts $\tau$ of length j, $1\le j\le M$, and numbers i, $1\le i\le j$, we denote by $\tau ^{\le i}$ the subtranscript corresponding to the first i queries along $\tau$.

Each elementary event $\omega \in {\Omega }$ defines a unique transcript $\tau _{\omega }$ corresponding to the computation of Eve on $\omega$.

The length of $\tau _{\omega }$ can be smaller than M. This is the case if and only if the next query after the last query of $\tau _{\omega }$ produces a sudden-death pair w.r.t. $\omega$ (see Definition 9). In this case, this next query is not counted to be a part of $\tau _{\omega }$.

Let us denote by ${\Omega }^{\mathrm {s.death}}$ the set of all elementary events $\omega$ for which $\tau _{\omega }$ leads to the generation of a sudden-death pair w.r.t. $\omega$, and note that this is equivalent to $\tau _{\omega }$ having length smaller than M.

Eve’s computation $\tau _{\omega }$ on an elementary event $\omega$ is successful if and only if either the length of $\tau _{\omega }$ is smaller than M (i.e., $\omega \in {\Omega }^{\mathrm {s.death}}$) or the first n bits of the keystream packet corresponding to $x^{*}(\tau _{\omega })$ via $\omega$ coincide with $z^{*}(\tau _{\omega })$, i.e.,

$$F_{\omega}\left(P_{\omega}\left(x^{*}(\tau_{\omega})\oplus k_{\omega}\right)\oplus k_{\omega}\right)=z^{*}(\tau_{\omega}). $$

We denote by ${\Omega }^{\text {succ}}\subseteq {\Omega }$ the set of all elementary events leading to a successful computation. Note that ${\Omega }^{\mathrm {s.death}}\subseteq {\Omega }^{\text {succ}}$.

5.5 Further basic definitions and the idea of the proof of Theorem 6

For all j, $1\le j\le M$, we denote by ${\mathcal T}^{j}$ the set of all transcripts $\tau$ of length j (i.e. consisting of j query triples) which occur with positive probability, i.e., for which there is some $\omega \in {\Omega }$ such that $\tau$ is the prefix of length j of $\tau _{\omega }$. With the following definition for each j, $1\le j\le M$, and each transcript $\tau \in {\mathcal T}^{j}$, we define the following sets corresponding to the queries along $\tau$. Moreover, we define the notions $\tau$-consistent elementary event and $\tau$-consistent key.

Definition 10 (Components of Transcripts)

• $X(\tau )=\{x\in \left \{0,1\right \}^{n};$ $\tau$ contains an E-query with input $x\}$,

• $Y(\tau )=\{y\in \left \{0,1\right \}^{n};$ $\tau$ contains an F-query with input $y\}$. Note that we put also those y to $Y(\tau )$ which occur at the right side of a structural EF-collision that was disclosed by Alice as additional information to an EE-collision, see Definition 8.

• $U(\tau )=\{u\in \left \{0,1\right \}^{n};$ $\tau$ contains a P-query with input u, or a $P^{-1}$-query with output $u\}$,

• $V(\tau )=\{v\in \left \{0,1\right \}^{n};$ $\tau$ contains a P-query with output v, or a $P^{-1}$-query with input $v\}$,

• $X^{*}(\tau )=\{x\in X(\tau );$ x there is a $y\in Y(\tau )$ such that $(x,y)$ is a structural EF-collision discovered during $\tau \}$,

• $\bar {Y}^{*}(\tau )=\{\bar {y}\in \left \{0,1\right \}^{n};\ \bar {y}$ is the reference point of some structural EF-collision discovered during $\tau \}$,

• $\mathit {Coll}(\tau )=\{(x,\bar {y});$ where $x\in X^{*}(\tau )$, and $\bar {y}\in \bar {Y}^{*}(\tau )$ is the reference point of a structural EF-collision $(x,y)$ discovered during $\tau \}$,

• $\bar {Y}^{(r)}(\tau )=\{\bar {y}\in \left \{0,1\right \}^{n};\ \pi ^{r}(\bar {y})\in Y(\tau )\}$,

• $\bar {Y}(\tau )=\bigcup _{r=-(n-1)}^{R-1} \bar {Y}^{(r)}(\tau )$.

• For all j, $1\le j\le M$, and transcripts $\tau \in {\mathcal T}^{j}$, we denote by ${\Omega }(\tau )$ the set of all $\tau$-consistent elementary events $\omega$, i.e.,

  $${\Omega}(\tau)=\{\omega;\tau_{\omega}^{\leq j}=\tau\}. $$

• ${\Omega }(\tau )$ defines the set $K(\tau )\subseteq \left \{0,1\right \}^{n}$ of $\tau$-consistent keys, i.e.,

  $$K(\tau)=\{k_{\omega};\omega\in{\Omega}(\tau)\}. $$

Important Note

Remember that we suppose Alice to be friendly in the sense of Definition 8. This implies that the oracle answers of Alice along $\tau$ yield the complete knowledge about possible structural collisions, i.e., this knowledge is part of $\tau$ (see Section 5.4). This implies that if some $(x,y)\in X(\tau )\times Y(\tau )$ is a structural EF-collision for some elementary event in ${\Omega }(\tau )$, then it is a structural EF-collision with the same reference point for all elementary events in ${\Omega }(\tau )$. The same is true for structural EE-collisions. This justifies the definitions of $\mathit {Coll}(\tau )$ and $\bar {Y}^{*}(\tau )$ and $X^{*}(\tau )$.

Observe that $X(\tau )$ corresponds to the set of all initial values for which Eve gets the corresponding keystream packet from Alice during $\tau$, and that $X^{*}(\tau )$ corresponds to the set of all those initial values for which Eve even knows the initial state of the corresponding packet. These known initial states are contained in the set $\bar {Y}^{*}(\tau )$.

The set $\bar {Y}(\tau )$ corresponds to the set of all initial states for which a part of the corresponding keystream packet has been discovered during $\tau$.

Note further that $\mathit {Coll}(\tau )$ yields all information also about structural EE-collisions discovered during $\tau$. This is because, due to Definition 8, for each structural EE-collisions $(x,x^{\prime })$ discovered during $\tau$, there is some $y\in Y(\tau )$ such that $(x,y)$ and $(x^{\prime },y)$ are structural EF-collisions discovered during $\tau$.

Moreover, $\mathit {Coll}(\tau )$ defines a one-to-one correspondence between $X^{*}(\tau )$ and $\bar {Y}^{*}(\tau )$, which is established by the bijection $P_{\omega }(x \oplus k_{\omega })\oplus k_{\omega }$ for an $\omega \in {\Omega }(\tau )$. (Note that, by definition, this bijection is the same for all $\tau$-consistent elements $\omega \in {\Omega }(\tau )$.)

Note that ${\Omega }(\tau )$ defines a probability distribution $\Pr _{\tau }$ on $K(\tau )$. For all $k\in K(\tau )$, it holds

$$\Pr_{\tau}[k]=\frac{|\{\omega\in{\Omega}(\tau);k_{\omega}=k\}|}{|{\Omega}(\tau)|}. $$

After the computation $\tau$ has happened, Eve’s knowledge about the secret $\omega$ can be identified with the probability space ${\Omega }(\tau )$ with the uniform distribution. Note that the induced probability distribution $\Pr _{\tau }$ on $K(\tau )$ does not need to be uniform. Actually, the analysis of the distribution $\Pr _{\tau }$ on $K(\tau )$ will be the key ingredient for proving Theorem 6.

For describing the main idea of the proof, let us consider the situation that Alice holds a secret $\omega =(k_{\omega },P_{\omega },F_{\omega })$ and that Eve performed M queries without generating a sudden-death pair. Let us denote by $\tau$ the corresponding transcript $\tau _{\omega }$.

Clearly, during $\tau$ the set of $\tau$-consistent keys becomes smaller and smaller. For getting a first impression how key candidates $k\in \left \{0,1\right \}^{n}$ are discarded during $\tau$, suppose that $\tau$ contains query triples $(P,u,v)$, $(E,x,p)$, $(F,y,z)$ for which $x\oplus u=k$ and $\pi ^{r}(v\oplus k)=y$ for some r, $0\le r\le R-1$. Then there are three possibilities:

• 1.) z does not equal the substring of packet $p\in \left \{0,1\right \}^{R}$ starting at position $r + 1$, or, if $r>R-n$, the prefix of z of length $R-r$ does not equal the suffix of length $R-r$ of packet p. Then k can not be the right key, i.e., $k\not \in K(\tau )$.

• 2.) z equals the substring of packet $p\in \left \{0,1\right \}^{R}$ starting at position $r + 1$, or, if $r>R-n$, the prefix of z of length $R-r$ equals the suffix of length $R-r$ of packet p, but $(x,v\oplus k)$ does not belong to $\mathit {Coll}(\tau )$. This implies that $(x,y)$ does not form a structural EF-collision (which would be the case if k was the right key $k_{\omega }$) and that the collision of z with p is caused by a (nonstructural) internal collision of $F_{\omega }$. Consequently, $k\not \in K(\tau )$.

• 3.) z equals the substring of packet $p\in \left \{0,1\right \}^{R}$ starting at position $r + 1$, or, if $r>R-n$, the prefix of z of length $R-r$ equals the suffix of length $R-r$ of packet p and $(x,v\oplus k)\in \mathit {Coll}(\tau )$. Then it also holds that $k\not \in K(\tau )$. Otherwise, if $k=k_{\omega }$, then $(x,u)$ would form a sudden-death pair and the computation would have stopped before $\tau$ was completed.

After $\tau$ is completed, Eve has to choose a pair $(x^{*}(\tau ),z^{*}(\tau ))$. She is in a promising position if one of the following two conditions is fulfilled.

Condition-1

K(τ) contains only a small number of keys. In this case, Eve can choose one of the few keys in $K(\tau )$, say $k^{\prime }$, and check the hypothesis $k^{\prime }=k_{\omega }$ as follows. She looks for some $y\in Y(\tau )$ and some r, $0\le r\le R-n$, such that $v=\pi ^{-1}(y)\oplus k^{\prime }\in V(\tau )$. In this case let $u=P_{\omega }^{-1}(v)$. If $x=u\oplus k^{\prime }\in X(\tau )$, then $k^{\prime }\neq k_{\omega }$, as otherwise Alice would have indicated before that $(x,u)$ is a sudden-death pair. If there is no such pair $(y,r)$, then Eve fixes an arbitrary $y\in Y(\tau )$ and poses one additional $P^{-1}$ query with input $y\oplus k^{\prime }$ and obtains $u=P_{\omega }^{-1}(y\oplus k^{\prime })$. If $k^{\prime }=k_{\omega }$ and $u\oplus k^{\prime }\in X(\tau )$, then $(x,u)$ is a sudden-death pair and Eve wins immediately. If $x=u\oplus k^{\prime }\not \in X(\tau )$ and $k^{\prime }=k_{\omega }$, then Eve wins with $x^{*}(\tau )=x$ and $z^{*}(\tau )=F_{\omega }(y)$.

Condition-2

The key $k_{\omega }$ belongs to a small set $K^{\prime }\subseteq K(\tau )$ such that $\Pr _{\tau }[k^{\prime }]$ is nontrivially large for all $k^{\prime }\in K^{\prime }$. In this case, Eve tests for all $k^{\prime }\in K^{\prime }$ the hypothesis $k^{\prime }=k_{\omega }$ as in Condition-1.

The structure of the remaining part of the proof of Theorem 6

Remember that we denote by ${\Omega }^{\text {succ}}$ the set of all elementary events $\omega \in {\Omega }$ for which the computation $\tau _{\omega }$ is successful. We have to bound the probability $\Pr _{{\Omega }}[{\Omega }^{\text {succ}}]$ according to the relation in Theorem 6. Our proof starts with a combinatorial characterization of $\tau$-consistency of elementary events and keys (see Section 5.6). This characterization will lead to the formulation of three properties of elementary events $\omega$, for which the following holds. Event $\omega$ has one of these properties if and only if $K(\tau _{\omega })$ satisfies Condition-1 or Condition-2 (see Lemma 5). We will identify these three properties with the colors black, red and blue and denote by ${\Omega }^{\text {black}}$, resp. ${\Omega }^{\text {red}}$, resp. ${\Omega }^{\text {blue}}$ the sets of elementary events having the corresponding property (see Section 5.7). We will further define an elementary event $\omega$ to be green, if it is neither red, nor black, nor blue, nor belongs to ${\Omega }^{\mathrm {s.death}}$, and will denote the set of all green elementary events by ${\Omega }^{\text {green}}$.

We prove Theorem 6 by using the following relation:

$$\begin{array}{@{}rcl@{}} \Pr\limits_{{\Omega}}\left[{\Omega}^{\text{succ}}\right]&\le &\Pr\limits_{{\Omega}}\left[{\Omega}^{\text{black}}\cap {\Omega}^{\text{succ}}\right]+\Pr\limits_{{\Omega}}\left[\left({\Omega}^{\text{red}}\cup {\Omega}^{\text{blue}}\right)\cap {\Omega}^{\text{succ}}\right]\\ &&+\Pr\limits_{{\Omega}}\left[\left({\Omega}^{\mathrm{s.death}}\setminus\left({\Omega}^{\text{black}}\cup {\Omega}^{\text{red}}\cup {\Omega}^{\text{blue}}\right)\right)\cap {\Omega}^{\text{succ}}\right]\\ &&+\Pr\limits_{{\Omega}}\left[{\Omega}^{\text{green}}\cap {\Omega}^{\text{succ}}\right]. \end{array} $$

Consequently, $\Pr _{{\Omega }}[{\Omega }^{\text {succ}}]$ can be upper bounded by

$$\begin{array}{@{}rcl@{}} \Pr\limits_{{\Omega}}\left[{\Omega}^{\text{succ}}\right]&\le&\Pr\limits_{{\Omega}}\left[{\Omega}^{\text{black}}\right]+\Pr\limits_{{\Omega}}\left[{\Omega}^{\text{red}}\cup {\Omega}^{\text{blue}}\right]\\ &&+\Pr_{{\Omega}}\left[{\Omega}^{\mathrm{s.death}}\setminus\left({\Omega}^{\text{black}}\cup {\Omega}^{\text{red}}\cup {\Omega}^{\text{blue}}\right)\right]\\ &&+\Pr\limits_{{\Omega}}\left[{\Omega}^{\text{succ}}\cap {\Omega}^{\text{green}}\right]. \end{array} $$

(15)

Black and red elementary events will have the important property that for all transcripts $\tau$ the following holds: if one event $\omega \in {\Omega }(\tau )$ is black (resp. red), then all events in ${\Omega }(\tau )$ are black (resp. red). This justifies to define transcripts $\tau$ to be black (resp. red) if at least one $\tau$-consistent elementary event is black (resp. red). All transcripts which are neither red nor black are called to be green. Note that for green transcripts $\tau$, the set ${\Omega }(\tau )$ can contain green elementary events and blue elementary events.

This allows to rewrite the probability $\Pr _{{\Omega }}[{\Omega }^{\text {succ}}\cap {\Omega }^{\text {green}}]$ as

$$\begin{array}{@{}rcl@{}} \Pr\limits_{{\Omega}}[{\Omega}^{\text{succ}}\cap {\Omega}^{\text{green}}]&=&\Pr\limits_{{\Omega}}[{\Omega}^{\text{green}}]\cdot \Pr\limits_{{\Omega}^{\text{green}}}[{\Omega}^{\text{succ}}]\\ &\le& \Pr\limits_{{\Omega}^{\text{green}}}[{\Omega}^{\text{succ}}], \end{array} $$

(16)

where $\Pr _{{\Omega }^{\text {green}}}[{\Omega }^{\text {succ}}]$ can be written as

$$\begin{array}{@{}rcl@{}} \Pr\limits_{{\Omega}^{\text{green}}}[{\Omega}^{\text{succ}}]&=&\sum\limits_{\tau\in{\mathcal T}^{M}_{\text{green}}} \Pr\limits_{{\Omega}^{\text{green}}}[{\Omega}^{\text{succ}}\cap {\Omega}^{\text{green}}(\tau)]\\ &=&\sum\limits_{\tau\in{\mathcal T}^{M}_{\text{green}}} \Pr\limits_{{\Omega}^{\text{green}}}[\tau]\cdot \Pr\limits_{{\Omega}^{\text{green}}(\tau)}[{\Omega}^{\text{succ}}]. \end{array} $$

(17)

Here, ${\mathcal T}^{M}_{\text {green}}$ denotes the set of all green transcripts that have length M, and ${\Omega }^{\text {green}}(\tau )$ denotes the set of all green elementary events in ${\Omega }(\tau )$.

Note that we occasionally use the following denotation for conditional probabilities. Let $A,B$ be subsets (events) of the probability space ${\Omega }$. Then we write

$$\Pr_{B}[A]:=\Pr_{{\Omega}}[A \mid B]=\frac{\Pr_{{\Omega}}[A\cap B]}{\Pr_{{\Omega}}[B]}. $$

By relations (15), (16) and (17), Theorem 6 follows directly from:

Lemma 2 (Main Lemma)

• (i) It holds that

  $$\Pr_{{\Omega}}\left[{\Omega}^{\mathrm{s.death}}\setminus\left({\Omega}^{\text{black}}\cup {\Omega}^{\text{red}}\cup {\Omega}^{\text{blue}}\right)\right]\le 2^{-(n-1)}\cdot ({\Delta}+ 2)\cdot M. $$

• (ii) It holds that $\Pr _{{\Omega }}[{\Omega }^{\text {black}}]\le 34\cdot 2^{-n}$.

• (iii) For all $\tau \in {\mathcal T}^{M}_{\text {green}}$, it holds that

  $$\Pr_{{\Omega}^{\text{green}}(\tau)}[{\Omega}^{\text{succ}}]\le 11\cdot (R + 4n)\cdot M\cdot 2^{-(n-1)}. $$

• (iv) It holds that $\Pr _{{\Omega }}[{\Omega }^{\text {red}}\cup {\Omega }^{\text {blue}}]\le M\cdot e^{-n}$.

We will prove Lemma 2 in Section 5.8 and the sections following it.

5.6 Basic methods I: The characterization of τ-consistency

Definition 11 (Critical Points)

Let $k\in \left \{0,1\right \}^{n}$. A point $u\in U(\tau )$ is called $(\tau ,k)$-critical if at least one of the following conditions is fulfilled.

• C1: $u\oplus k\in X(\tau )\setminus X^{*}(\tau )$ and $P_{\tau }(u)\oplus k\in \bar {Y}(\tau )\setminus \bar {Y}^{*}(\tau )$.

• C2: $u\oplus k\in X^{*}(\tau )$.

• C3: $P_{\tau }(u)\oplus k\in \bar {Y}^{*}(\tau )$.

Here, $P_{\tau }(u)$ denotes the output of the P-query on input u along $\tau$, resp. the input of the $P^{-1}$-query with output u.

The notion of $(\tau ,k)$-critical points allows to characterize $\tau$-consistency.

Lemma 3 (Consistency Lemma)

A key $k\in \left \{0,1\right \}^{n}$ is not $\tau$-consistent (i.e., $k\not \in K(\tau )$), if and only if there is a $(\tau ,k)$-critical point $u\in U(\tau )$.

Proof of Lemma 3

We first prove the if-direction.

Let $k\in \left \{0,1\right \}^{n}$ and suppose that there is some $u\in U(\tau )$ which is $(\tau ,k)$-critical.

For deriving a contradiction we assume that $k\in K(\tau )$, i.e., that there is some $\omega \in {\Omega }(\tau )$ with $k_{\omega }=k$.

Suppose first that u is $(\tau ,k)$-critical via condition C1 of Definition 11.

By definition, $P_{\tau }(u)\oplus k=P_{\omega }(u)\oplus k_{\omega }\in \bar {Y}(\tau )$, which implies the existence of some r, $-(n-1)\le r\le R-1$ such that $\pi ^{r}(P_{\omega }(u)\oplus k_{\omega })\in Y(\tau )$. This implies, that $(u\oplus k_{\omega },\pi ^{r}(P_{\omega }(u)\oplus k_{\omega }))$ has to be classified as a structural EF-collision with reference point $P_{\omega }(u)\oplus k_{\omega }$ along $\tau$. But this can not be true, as, by Definition 9, $(u\oplus k,u)$ would form a sudden-death pair w.r.t. $\omega$, which implies that $\omega \not \in {\Omega }(\tau )$.

Suppose now that u is $(\tau ,k)$-critical via condition C2 of Definition 11. If $u\oplus k=u\oplus k_{\omega }\in X^{*}(\tau )$, then $(u\oplus k,u)$ is again a sudden-death pair w.r.t. $\omega$, which implies that $\omega \not \in {\Omega }(\tau )$.

If $P_{\tau }(u)\oplus k\in \bar {Y}^{*}(\tau )$ (condition C3), then $(u\oplus k,P_{\tau }(u)\oplus k)\in \mathit {Coll}(\tau )$, which again implies that $(u\oplus k,u)$ is a sudden-death pair and that $\omega \not \in {\Omega }(\tau )$.

Let us now show the only-if direction of Lemma 3.

We fix some j, $1\le j\le M$, some transcript $\tau \in {\mathcal T}^{j}$ with $\Pr _{{\Omega }}[\tau ]>0$ and some key $k\in \left \{0,1\right \}^{n}$ for which there do not exist $(\tau ,k)$-critical points $u\in U(\tau )$ in the sense of Definition 11.

We have to show that k is $\tau$-consistent.

We do this by constructing a permutation $P^{\prime }$ over $\left \{0,1\right \}^{n}$ and a $\pi$-iterative function $F^{\prime }:\left \{0,1\right \}^{n}\longrightarrow \left \{0,1\right \}^{n}$ such that $\omega ^{\prime }=(k,P^{\prime },F^{\prime })\in {\Omega }(\tau )$.

For all inputs $x\in X(\tau )$, $u\in U(\tau )$, $v\in V(\tau )$, $y\in Y(\tau )$ of oracle queries posed during $\tau$, we denote by $E_{\tau }(x)$, $P_{\tau }(u)$, $P^{-1}_{\tau }(v)$, and $F_{\tau }(y)$, resp., the corresponding oracle answers given by Alice during $\tau$. $P^{\prime }$ and $F^{\prime }$ have to satisfy the condition that $P^{\prime }(u)=P_{\tau }(u)$ and $F^{\prime }(y)=F_{\tau }(u)$ for all $u\in U(\tau )$ and $y\in Y(\tau )$, respectively.

We now have to define $P^{\prime }$ and $F^{\prime }$ outside of $U(\tau )$ and $Y(\tau )$, respectively, in such a way that $\omega ^{\prime }$ is $\tau$-consistent.

We do this by defining $P^{\prime }$ and $F^{\prime }$ along the $(k,P^{\prime })$-paths $(u\oplus k,u,P^{\prime }(u)\oplus k)$ for all $u\in \left \{0,1\right \}^{n}$, where we go with u through $\left \{0,1\right \}^{n}$ in a certain order.

Hereby, we dynamically maintain a set $\textit {Target}(P^{\prime })$, which is initially set to $\left \{0,1\right \}^{n}\setminus V(\tau )$. Whenever we define $P^{\prime }(u)$ for a new u, we delete $P^{\prime }(u)$ from $\textit {Target}(P^{\prime })$.

• Phase 1: Here we consider all $u\in \left \{0,1\right \}^{n}$ for which $u\oplus k\in X^{*}(\tau )$.

  Then it holds $u\not \in U(\tau )$ as otherwise u would be $(\tau ,k)$-critical via condition C2 of Definition 11.

  We define $P^{\prime }(u)=\bar {y}\oplus k$, where $\bar {y}$ denotes the unique point in $\bar {Y}^{*}(\tau )$ for which $(u\oplus k,\bar {y})\in \mathit {Coll}(\tau )$. Note that the point $\bar {y}\oplus k$ does not belong to $V(\tau )$. Otherwise, if $\bar {y}\oplus k$ would equal $P_{\tau }(u^{\prime })$ for some $u^{\prime }\neq u\in U(\tau )$, then $u^{\prime }$ would be $(\tau ,k)$-critical via condition C3.

  We define $F^{\prime }$ on the set $\{\pi ^{r}(P^{\prime }(u)\oplus k);r=-(n-1),\cdots ,R-1\}$ according to the packet $E_{\tau }(u\oplus k)$. Note here that if $-(n-1)\le r<0$, then $E_{\tau }(u\oplus k)$ determines only a suffix of $F^{\prime }(\pi ^{r}(P^{\prime }(u)\oplus k))$, and that if $R-n-1<r\le R-1$, then $E_{\tau }(u\oplus k)$ determines only a prefix of $F^{\prime }(\pi ^{r}(P^{\prime }(u)\oplus k))$.

• Phase 2 concerns the $(k,P^{\prime })$-paths through those $u\in U(\tau )$ for which $u\oplus k\in X(\tau )\setminus X^{*}(\tau )$. Note that for these $u\in U(\tau )$, as they are not $(\tau ,k)$-critical, it holds $\bar {y}:=P_{\tau }(u)\oplus k\not \in \bar {Y}(\tau )$.

  This implies that for all r, $-(n-1)\le r\le R-1$, it holds that $\pi ^{r}(\bar {y})$ is not in $Y(\tau )$, which allows us to define $F^{\prime }(\pi ^{r}(\bar {y}))$ according to the packet $E_{\tau }(u\oplus k)$.

• Phase 3 considers all $u\not \in U(\tau )$ for which $u\oplus k\in X(\tau )\setminus X^{*}(\tau )$.

  Here, $P^{\prime }(u)$ has to be chosen in such a way that $P^{\prime }(u)\oplus k\not \in \bar {Y}(\tau )$. Otherwise, there would exist some r, $-(n-1)\le r\le R-1$, such that $(u\oplus k,\pi ^{r}(P^{\prime }(u)\oplus k))$ is an EF-collision discovered during $\tau$, which would imply that $u\oplus k\in X^{*}(\tau )$ and contradict the assumption made for phase 3.

  Corresponding to this, we define a set

  $$\textit{Forbidden}(u)=\{v\in \left\{0,1\right\}^{n}; v\oplus k\in \bar{Y}(\tau)\}, $$

  and choose

  $$P^{\prime}(u)\in \textit{Target}(P^{\prime})\setminus \textit{Forbidden}(u). $$

Note that for all remaining $u\in \left \{0,1\right \}^{n}$ the values of $P^{\prime }(u)$ can be freely chosen in $\textit {Target}(P^{\prime })$. For all remaining $y\in \left \{0,1\right \}^{n}$, the values of $F^{\prime }(y)$ can also be freely chosen $\left \{0,1\right \}^{n}$ in such a way that the $\pi$-iterativeness of $F^{\prime }$ is maintained. □

5.7 Assigning colors to elementary events, transcripts, and keys

We will now assign the colors red, black, blue and green to transcripts, elementary events, and keys. There will be three colors, namely black, red, and blue, which have to be considered as bad in the sense that if $\omega$ has a bad color, then $\tau _{\omega }$ yields some nontrivial information which helps Eve to win the game.

Let us start with the definition of black elementary events, which is partly based on considering the following equivalence relation $\equiv _{P}$, induced by a permutation P over $\left \{0,1\right \}^{n}$.

Definition 12 (The Relation $\equiv _{P}$)

Let P denote a permutation of $\left \{0,1\right \}^{n}$ and let U be an arbitrary subset of $\left \{0,1\right \}^{n}$.

• For all $u,u^{\prime }\in U$ let $u\equiv _{P} u^{\prime }$ if and only if $u\oplus P(u)=u^{\prime }\oplus P(u^{\prime })$.

• Let $\mathit {Max}(P,U)$ denote the maximal size of an equivalence class w.r.t. $\equiv _{P}$ in U.

Definition 13 (Critical Keys)

A key $k\in \left \{0,1\right \}^{n}$ is called to be $\tau$-critical if there is some $u\in U(\tau )$ such that $u\oplus k\in X(\tau )$ and $P_{\tau }(u)\oplus k\in \bar {Y}(\tau )$.

Note that $k\in \left \{0,1\right \}^{n}$ is called to be $\tau$-critical if there is some $u\in U(\tau )$ such that u is $(\tau ,k)$-critical with regard to condition C1 in Definition 11.

Definition 14 (Alive Elementary Events)

For all numbers j, $1\le j\le M$, we call an elementary event $\omega \in {\Omega }$ to be j-alive if $\tau _{\omega }$ contains at least j queries, i.e., the first $j-1$ queries and answers and the j-th query along $\tau _{\omega }$ do not generate a sudden death pair with respect to $\omega$.

Definition 15 (Black Transcripts and Elementary Events)

• For all j, $1\le j\le M$, we call a transcript $\tau \in {\mathcal T}^{j}$ to be black if the number of $\tau$-critical keys (see Definition 13) exceeds

  $$\begin{array}{@{}rcl@{}} B(M,R,n)&= &2^{-n}\cdot M^{3}\cdot\left(R+n-1 + 2\sqrt{R+n-1}\right)\\ &&+\,3\sqrt{n\cdot M^{3}\cdot (R+n-1)} \end{array} $$

  or if

  $$\mathit{Max}(P_{\tau},U(\tau))> 5, $$

  where $P_{\tau }:U(\tau )\longrightarrow \left \{0,1\right \}^{n}$ denotes the injective mapping corresponding to the P- and $P^{-1}$-queries in $\tau$.

• For all j, $1\le j\le M$, an elementary event $\omega$ is called j-black if ω is j-alive and the transcript $\tau _{\omega }^{\le j}$, corresponding to the first j queries along $\tau _{\omega }$, is black.

• Let ${\Omega }^{j}_{\text {black}}$ denote the set of all j-black elementary events and ${\mathcal T}^{j}_{\text {black}}$ the set of all black transcripts $\tau \in {\mathcal T}^{j}$.

• Let ${\Omega }^{\text {black}}=\bigcup _{j = 1}^{M} {\Omega }^{j}_{\text {black}}$.

Let us next define red transcripts.

Definition 16 (Red Transcripts and Elementary Events)

• For all j, $1\le j\le M$, we call a transcript $\tau \in {\mathcal T}^{j}$ to be red if it is not black and $|X^{*}(\tau )|>{\Delta }$. (Remember that ${\Delta }$ denotes some balancedness parameter, which was introduced in Theorem 6).

• An elementary event $\omega$ is called j-red if ω is j-alive and the transcript $\tau _{\omega }^{\le j}$ is red.

• Let ${\Omega }^{j}_{\text {red}}$ denote the set of all j-red elementary events and ${\mathcal T}^{j}_{\text {red}}$ the set of all red transcripts $\tau \in {\mathcal T}^{j}$.

• Let ${\Omega }^{\text {red}}=\bigcup _{j = 1}^{M} {\Omega }^{j}_{\text {red}}$.

Note that one strategy of Eve could be to pose queries in a first phase in such a way that for the resulting transcript $\tau$ it holds that the set $K(\tau )$ of $\tau$-consistent keys is small, and then to try each key in $K(\tau )$ if it fits. Redness and blackness of transcripts $\tau$ cover exactly the case in which this strategy could be successful:

Lemma 4

For all j, $1\le j\le M$, and $\tau \in {\mathcal T}^{j}$ the following holds. If $\tau$ is neither red nor black, then

$$|K(\tau)|\ge 2^{n}-B(M,R,n)-2\cdot {\Delta}\cdot j. $$

Proof of Lemma 4

From Definition 11 and Lemma 3 we know that $k\in \left \{0,1\right \}^{n}\setminus K(\tau )$ if and only if there is some $u\in U(\tau )$ such that u is $(\tau ,k)$-critical via condition C1 or via condition C2. Condition C1 implies that k is $\tau$-critical in the sense of Definition 13. As $\tau$ is not black, the number of such keys is bounded by $B(M,R,n)$. Condition C2 implies that $k\in X^{*}(\tau )\oplus U(\tau )$ or $k\in \bar {Y}^{*}(\tau )\oplus V(\tau )$. ²

As $\tau$ is not red, it holds that $|X^{*}(\tau )\oplus U(\tau )|\le {\Delta }\cdot j$ and $|\bar {Y}^{*}(\tau )\oplus U(\tau )|\le {\Delta }\cdot j$. □

The motivation for considering blue elementary events is as follows. We have seen above that ${\Omega }(\tau )$, the set of all possible events if Eve sees $\tau$, defines a probability distribution on $K(\tau )$, the set of all keys which are consistent with $\tau$. This distribution is known to Eve. This is due to the assumption that Eve has unbounded computational power, i.e., she knows the complete probability space ${\Omega }(\tau )$ and can compute the corresponding distribution on $K(\tau )$. Thus, Eve can test the hypothesis that the secret key belongs to the set of most probable keys in $K(\tau )$ in the sense of Condition 2 in Section 5.5.

Blue elementary events $\tilde {\omega }=(k_{\tilde {\omega }},P_{\tilde {\omega }},F_{\tilde {\omega }})$ will have the property that for $\tau =\tau _{\tilde {\omega }}$ it holds that $\Pr _{{\Omega }(\tau )}[k_{\tilde {\omega }}]$ is large, i.e., if Alice chooses a blue elementary event, then the success probability of Eve will be nontrivially high.

Definition 17 (Blue Elementary Events)

• For all numbers j, $1\le j\le M$, we call an elementary event $\omega \in {\Omega }$ to be j-blue if $\omega$ is j-alive and not black and if

  $$|(X(\tau^{\le j}_{\omega})\oplus k_{\omega})\cap U(\tau^{\le j}_{\omega})|> {\Delta} $$

  or

  $$|(\bar{Y}(\tau^{\le j}_{\omega})\oplus k_{\omega})\cap V(\tau^{\le j}_{\omega})|> {\Delta}. $$

• Let ${\Omega }^{j}_{\text {blue}}$ denote the set of all j-blue elementary events.

• Let ${\Omega }^{\text {blue}}=\bigcup _{j = 1}^{M} {\Omega }^{j}_{\text {blue}}$.

Definition 18 (Green Elementary Events and Transcipts)

• For all numbers j, $1\le j\le M$, an elementary event $\omega \in {\Omega }$ is called to be j-green if $\omega$ is j-alive and neither j-blue, nor j-red, nor j-black.

• Let ${\Omega }^{j}_{\text {green}}$ denote the set of all j-green elementary events.

• Let ${\Omega }^{\text {green}}={\Omega }^{M}_{\text {green}}$.

• For all numbers j, $1\le j\le M$, a transcript $\tau \in {\mathcal T}^{j}$ is called green, if it is neither red nor black.

• Let ${\mathcal T}^{j}_{\text {green}}$ denote the set of green transcripts in ${\mathcal T}^{j}$.

It is important to note the following difference between red and black events on the one side, and green and blue events on the other side. If, for a transcript $\tau$, one elementary event in ${\Omega }(\tau )$ is black (resp. red), then all elementary events in ${\Omega }(\tau )$ are black (resp. red), which justifies to define $\tau$ to be black (resp. red).

On the other side, if a transcript $\tau$ is green, then the elementary events in ${\Omega }(\tau )$ are either blue or green. This is because blueness of an elementary event $\omega \in {\Omega }(\tau )$ does not only depend on $\tau$ but also on the key-component $k_{\omega }$.

We will prove Theorem 6 by showing that the probabilities of black, red, and blue elementary events are exponentially small, that the probability of sudden-death events is exponentially small, and that for green transcripts $\tau \in {\mathcal T}^{M}_{\text {green}}$, the probability that Eve publishes a correct (initial value, keystream prefix) pair is exponentially small (see Lemma 2 in Section 5.8).

Therefore, let us take more insight into the structure of ${\Omega }(\tau )$ for green transcripts $\tau$.

We know that for some green transcript $\tau$ the decision if an elementary event $\omega \in {\Omega }(\tau )$ is green or blue depends only on $k_{\omega }$. This justifies the following definition.

Definition 19 (Green Keys)

• Let $\tau$ denote a green transcript. We call a $\tau$-consistent key $k\in K(\tau )$ to be $\tau$-green if $|(X(\tau )\oplus k)\cap U(\tau )|\le {\Delta }$ and $|(\bar {Y}(\tau )\oplus k)\cap V(\tau )|\le {\Delta }$, and $\tau$-blue otherwise.

• We denote by $K^{\text {green}}(\tau )$ (resp. $K^{\text {blue}}(\tau )$) the set of all $\tau$-consistent keys which are $\tau$-green (resp. $\tau$-blue).

Note that, by definition, for green transcripts $\tau$ it holds:

$$K(\tau)=K^{\text{green}}(\tau)\cup K^{\text{blue}}(\tau). $$

5.8 Basic methods II: Estimating probabilities

Remember that for proving Lemma 2 we have to show the following claims.

• (i) It holds that

  $$\Pr_{{\Omega}}\left[{\Omega}^{\mathrm{s.death}}\setminus\left({\Omega}^{\text{black}}\cup {\Omega}^{\text{red}}\cup {\Omega}^{\text{blue}}\right)\right]\le 2^{-(n-1)}\cdot ({\Delta}+ 2)\cdot M. $$

• (ii) It holds that $\Pr _{{\Omega }}[{\Omega }^{\text {black}}]\le 34\cdot 2^{-n}$.

• (iii) For all $\tau \in {\mathcal T}^{M}_{\text {green}}$, it holds that

  $$\Pr_{{\Omega}^{\text{green}}(\tau)}[{\Omega}^{\text{succ}}]\le 11\cdot (R + 4n)\cdot M\cdot 2^{-(n-1)}. $$

• (iv) It holds that $\Pr _{{\Omega }}[{\Omega }^{\text {red}}\cup {\Omega }^{\text {blue}}]\le M\cdot e^{-n}$.

The proofs of parts (i), (ii), (iii), and (iv) will be given in Sections 5.10, 5.12, 5.9, and 5.11, respectively.

All these proofs use the following Smoothness Lemma, which shows that for all green transcripts $\tau$, there is a sufficiently large number of green $\tau$-consistent keys and that the probabilities of these green keys do not differ too much.

Lemma 5 (Smoothness Lemma)

For all green transcripts $\tau$, the following is true if n is large enough:

• (I) $|K^{\text {green}}(\tau )|\ge \frac {1}{\sqrt {2}}\cdot 2^{n}$.

• (II) For all $k,k^{\prime }\in K^{\text {green}}(\tau )$ , it holds that

  $$\Pr_{{\Omega}^{\text{green}}(\tau)}[k]\le \sqrt{2}\cdot \Pr_{{\Omega}^{\text{green}}(\tau)}[k^{\prime}]. $$

Lemma 5 implies the following corollary, which will be an important tool for proving Lemma 2.

Corollary 2 (Main Tool Box)

For all green transcripts $\tau$ the following is true:

• (a) For all $k\in \left \{0,1\right \}^{n}$ it holds

  $$\Pr_{{\Omega}^{\text{green}}(\tau)}[k]\le 2^{-(n-1)}. $$

• (b) For all $x,\bar {y}\in \left \{0,1\right \}^{n}$ the following holds:

  • b.1 If $(x,\bar {y})\in \mathit {Coll}(\tau )$ then

    $$\Pr_{{\Omega}^{\text{green}}(\tau)}[P_{\omega}(x\oplus k_{\omega})\oplus k_{\omega}=\bar{y}]= 1. $$

  • b.2 If $(x,\bar {y})\not \in \mathit {Coll}(\tau )$ but $x\in X^{*}(\tau )$ or $\bar {y}\in \bar {Y}^{*}(\tau )$ then

    $$\Pr_{{\Omega}^{\text{green}}(\tau)}[P_{\omega}(x\oplus k_{\omega})\oplus k_{\omega}=\bar{y}]= 0. $$

  • b.3 If $x\in X(\tau )\setminus X^{*}(\tau )$ and $\bar {y}\in \bar {Y}\setminus \bar {Y}^{*}(\tau )$ then

    $$\Pr_{{\Omega}^{\text{green}}(\tau)}[P_{\omega}(x\oplus k_{\omega})\oplus k_{\omega}=\bar{y}]= 0. $$

  • b.4 In all other cases, i.e., if $x\not \in X^{*}(\tau )$ and $\bar {y}\not \in \bar {Y}^{*}(\tau )$ and (x∉X(τ) or $\bar {y}\not \in \bar {Y}(\tau )$) it holds

    $$\Pr_{{\Omega}^{\text{green}}(\tau)}[P_{\omega}(x\oplus k_{\omega})\oplus k_{\omega}=\bar{y}]\le 9\cdot 2^{-(n-1)}. $$

• (c) For all $x,x^{\prime }\in \left \{0,1\right \}^{n}$, where $x\not \in X(\tau )$ and $x^{\prime }\in X(\tau )$, and all r, $-(R+n)\le r\le R+n$, it holds

  $$\Pr_{{\Omega}^{\text{green}}(\tau)}\left[\pi^{r}\left(P_{\omega}(x\oplus k_{\omega})\oplus k_{\omega}\right)=P_{\omega}(x^{\prime}\oplus k_{\omega})\oplus k_{\omega}\right]\le 11\cdot 2^{-(n-1)}. $$

Note here that part (a) of Corollary 2 follows directly from Lemma 5. Parts (b.1), (b.2), (b.3) follow directly from the definition of $\tau$-consistent keys. Parts (b.4) and (c) will be proved in Appendix B.

In the following, we prove part (I) of Lemma 5. The proof of part (II) is quite technical and long, thus it was shifted to Appendix C.

Proof of Part (I) of Lemma 5

We fix some number j, $1\le j\le M$, and some transcript $\tau \in {\mathcal T}^{j}_{\text {green}}$.

By Lemma 4 it holds that

$$|K^{\text{green}}(\tau)|=|K(\tau)|-|K^{\text{blue}}(\tau)|\ge 2^{n}-B(M,R,n)-2\cdot{\Delta}\cdot j-|K^{\text{blue}}(\tau)|. $$

We show that

$$|K^{\text{blue}}(\tau)|\le \frac{(R+n)\cdot j^{2}}{{\Delta}}. $$

This is because

$$\begin{array}{@{}rcl@{}} \sum\limits_{k\in\left\{0,1\right\}^{n}} \left|\left(X(\tau)\oplus k\right)\cap U(\tau)\right| &=&\sum\limits_{k\in\left\{0,1\right\}^{n}} \left|\left\{(x,u)\in X(\tau)\times U(\tau);\ x\oplus u=k\right\}\right|\\ &=&|X(\tau)\times U(\tau)|=|X(\tau)|\cdot |U(\tau)|, \end{array} $$

which implies that

$$\left|\left\{k \in \{0,1\}^{n};\ \left|\left(X(\tau)\oplus k\right)\cap U(\tau)\right|>{\Delta}\right\}\right|\le \frac{|X(\tau)|\cdot |U(\tau)|}{{\Delta}}\le \frac{j^{2}}{{\Delta}}. $$

In exactly the same way one can prove that

$$\begin{array}{@{}rcl@{}} \left|\left\{k \in \{0,1\}^{n};\ \left|\left(\bar{Y}(\tau)\oplus k\right)\cap V(\tau)\right|>{\Delta}\right\}\right|&\le& \frac{ |\bar{Y}(\tau)|\cdot |V(\tau)|}{{\Delta}}\\ &\le& \frac{(R+n-1)\cdot j^{2}}{{\Delta}}. \end{array} $$

Consequently,

$$|K^{\text{green}}(\tau)|\ge 2^{n}-B(M,R,n)-2\cdot{\Delta}\cdot j-\frac{(R+n)j^{2}}{{\Delta}}\ge \frac{1}{\sqrt{2}}\cdot 2^{n} $$

if n is large enough. The last inequation follows from Theorem 6, (1). □

5.9 Bounding the probability of sudden death (part (i) of Lemma 2)

In this subsection, we prove part (i) of Lemma 2, namely that

$$ \Pr_{{\Omega}}\left[{\Omega}^{\mathrm{s.death}}\setminus\left({\Omega}^{\text{black}}\cup {\Omega}^{\text{red}}\cup {\Omega}^{\text{blue}}\right)\right]\le 2^{-(n-1)}\cdot ({\Delta}+ 2)\cdot M. $$

Let us denote by ${\mathcal T}^{\text {all}}_{\text {green}}=\bigcup _{j = 1}^{M} {\mathcal T}^{j}_{\text {green}}$ the set of all green transcripts which occur with nonzero probability. Note that ${\mathcal T}^{\text {all}}_{\text {green}}$ has the structure of a partially ordered set, where a transcript $\tau$ is smaller than $\tau ^{\prime }$ if $\tau$ is a prefix of $\tau ^{\prime }$.

We denote by ${\mathcal T}^{*}_{\text {green}}$ the set of maximal elements in this partially ordered set ${\mathcal T}^{\text {all}}_{\text {green}}$. Observe that

$${\mathcal T}^{*}_{\text{green}}={\mathcal T}^{M}_{\text{green}}\cup {\mathcal T}^{\text{strange}}_{\text{green}}, $$

where ${\mathcal T}^{\text {strange}}_{\text {green}}$ contains all green transcripts $\tau$ of length smaller than M for which all transcripts $\tau ^{\prime }$ which contain $\tau$ as a prefix are black or red.

Let us denote by $\tilde {{\Omega }}$ the set

$$\tilde{{\Omega}}=\left({\Omega}^{\mathrm{s.death}}\setminus\left({\Omega}^{\text{black}}\cup {\Omega}^{\text{red}}\cup {\Omega}^{\text{blue}}\right)\right)\cup\bigcup\limits_{\tau\in {\mathcal T}^{*}_{\text{green}} }{\Omega}^{\text{green}}(\tau), $$

where for all j, $1\le j\le M$, and all $\tau \in {\mathcal T}^{j}_{\text {green}}$ it holds

$${\Omega}^{\text{green}}(\tau)=\{\omega\in {\Omega}_{\text{green}}^{j};\tau_{\omega}^{\le j}=\tau\}. $$

For all $\tau \in {\mathcal T}^{\text {all}}_{\text {green}}$, we denote by ${\Omega }^{\mathrm {s.death}}_{\text {green}}(\tau )$ the set of all elementary events $\omega \in {\Omega }^{\text {green}}(\tau )$ for which the next query after $\tau$ generates a sudden-death pair w.r.t. $\omega$. Note that ${\Omega }^{\mathrm {s.death}}_{\text {green}}(\tau )=\emptyset$ if the length of $\tau$ is M.

Observe that $\omega \in {\Omega }^{\mathrm {s.death}}\setminus \left ({\Omega }^{\text {black}}\cup {\Omega }^{\text {red}}\cup {\Omega }^{\text {blue}}\right )$ if and only if there is some $\tau \in {\mathcal T}^{\text {all}}_{\text {green}}$ such that $\omega \in {\Omega }^{\mathrm {s.death}}_{\text {green}}(\tau )$. Consequently,

$$\begin{array}{@{}rcl@{}} &&\Pr\limits_{{\Omega}}\left[{\Omega}^{\mathrm{s.death}}\setminus\left({\Omega}^{\text{black}}\cup {\Omega}^{\text{red}}\cup {\Omega}^{\text{blue}}\right)\right]\\ &\le& \Pr\limits_{\tilde{{\Omega}}}\left[{\Omega}^{\mathrm{s.death}}\setminus\left({\Omega}^{\text{black}}\cup {\Omega}^{\text{red}}\cup {\Omega}^{\text{blue}}\right)\right] =\sum\limits_{\tau\in {\mathcal T}^{\text{all}}_{\text{green}} }\Pr\limits_{\tilde{{\Omega}}}[{\Omega}^{\mathrm{s.death}}_{\text{green}}(\tau)]. \end{array} $$

We fix for all transcripts $\tau \in {\mathcal T}^{*}_{\text {green}}$ a natural number $i(\tau )$, $1\le i(\tau )\le j$, where j denotes the length of $\tau$. We do this in such a way that the sets

$$T(\tau)=\{\tau^{\le i(\tau)},\tau^{\le i(\tau)+ 1},\cdots,\tau^{\le j}\} $$

form a partition of the set ${\mathcal T}^{\text {all}}_{\text {green}}$ into pairwise disjoints subsets.³ Note that the sets $T(\tau )$ correspond to prefixes of the transcript $\tau$.

Now define for all transcripts $\tau \in {\mathcal T}^{*}_{\text {green}}$ subsets $A(\tau )$ and $B(\tau )$ of $\tilde {{\Omega }}$:

$$A(\tau)=\bigcup\limits_{\tilde{\tau}\in T(\tau)}{\Omega}^{\mathrm{s.death}}_{\text{green}}(\tilde{\tau}), $$

$$B(\tau)={\Omega}^{\text{green}}(\tau)\cup A(\tau). $$

Note that the set system $\{B(\tau );\tau \in {\mathcal T}^{*}_{\text {green}}\}$ defines a partition of $\tilde {{\Omega }}$ into pairwise disjoint subsets, that the set system $\{A(\tau );\tau \in {\mathcal T}^{*}_{\text {green}}\}$ defines a partition of the set ${\Omega }^{\mathrm {s.death}}\setminus \left ({\Omega }^{\text {black}}\cup {\Omega }^{\text {red}}\cup {\Omega }^{\text {blue}}\right )$ into pairwise disjoint subsets, and that for all $\tau \in {\mathcal T}^{*}_{\text {green}}$ it holds $A(\tau )\subseteq B(\tau )$. Consequently,

$$\begin{array}{@{}rcl@{}} \Pr\limits_{\tilde{{\Omega}}}\left[{\Omega}^{\mathrm{s.death}}\setminus\left({\Omega}^{\text{black}}\cup {\Omega}^{\text{red}}\cup {\Omega}^{\text{blue}}\right)\right] &=&\sum\limits_{\tau\in {\mathcal T}^{*}_{\text{green}} } \Pr\limits_{\tilde{{\Omega}}}[A(\tau)\cap B(\tau)]\\ &=&\sum\limits_{\tau\in {\mathcal T}^{*}_{\text{green}} } \Pr\limits_{\tilde{{\Omega}}}[B(\tau)]\cdot \Pr\limits_{B(\tau)}[A(\tau)]\\ &\le& \max_{\tau\in {\mathcal T}^{*}_{\text{green}}} \Pr_{B(\tau)}[A(\tau)]. \end{array} $$

(18)

We fix some arbitrary $\tau \in {\mathcal T}^{*}_{\text {green}}$ and denote by j the length of $\tau$. Note that for all transcripts $\tilde {\tau }\in T(\tau )$ it holds that $\omega \in {\Omega }^{\mathrm {s.death}}_{\text {green}}(\tilde {\tau })$ if and only if $\omega \in {\Omega }^{\text {green}}(\tilde {\tau })$ and the key $k_{\omega }$ falls into the set $D(\tilde {\tau })$, which is defined as follows:

$$D(\tilde{\tau})=\left(X^{*}_{\text{new}}(\tilde{\tau})\oplus U_{\text{new}}(\tilde{\tau})\right)\setminus \left(X^{*}(\tilde{\tau})\oplus U(\tilde{\tau})\right), $$

where $X^{*}_{\text {new}}(\tilde {\tau })$ and $U_{\text {new}}(\tilde {\tau })$ denote the new sets $X^{*}(\cdot )$ and $U(\cdot )$ after posing the uniquely determined next query after $\tilde {\tau }$.

According to Corollary 2, part (a), the probability of this event is bounded by $2^{-(n-1)}\cdot |D(\tilde {\tau })|$.

Now observe that $\bigcup _{\tilde {\tau }\in T(\tau )}D(\tilde {\tau })$ is a subset of $X^{*}_{\text {new}}(\tau )\oplus U_{\text {new}}(\tau )$ if $j<M$ and of $X^{*}(\tau )\oplus U(\tau )$ if $j=M$.

If $j<M$, then $|X^{*}_{\text {new}}(\tau )|\le |X^{*}(\tau )|+ 2\le {\Delta }+ 2$, as $\tau$ is green, and $|U_{\text {new}}(\tau )|\le |U(\tau )|+ 1\le M$. We obtain that

$$\Pr_{B(\tau)}[A(\tau)]\le 2^{-(n-1)}\cdot |X^{*}_{\text{new}}(\tau)\oplus U_{\text{new}}(\tau)|\le 2^{-(n-1)}\cdot ({\Delta}+ 2)\cdot M, $$

which proves part (i) of Lemma 2 by Relation (18).

5.10 Bounding the probability of black transcripts (part (ii) of Lemma 2)

In this subsection, we prove part (ii) of Lemma 2, namely that

$$\begin{array}{@{}rcl@{}} \Pr\limits_{{\Omega}}\left[{\Omega}^{\text{black}}\right] \le 34\cdot 2^{-n}. \end{array} $$

(19)

Proof of Relation (19)

From Definition 15, it follows straightforwardly that for any elementary event $\omega \in {\Omega }$, it holds that the transcript $\tau _{\omega }$ is black if and only if it has some black prefix (where $\tau _{\omega }$ is considered to be its own prefix). This, in turn, implies that $\omega \in {\Omega }^{\text {black}}$ if and only if $\tau _{\omega }$ is black. Consequently, it is sufficient here to assess the probability that for an $\omega \in {\Omega }$ chosen uniformly and at random (see Definition 4), the number of $\tau _{\omega }$-critical keys exceeds $B(M,R,n)$ or it holds $\mathit {Max}(P_{\tau _{\omega }},U(\tau _{\omega }))> 5$.

Remember from Definition 13 that a key $k \in \left \{0,1\right \}^{n}$ is called $\tau _{\omega }$-critical if there is some $u\in U(\tau _{\omega })$ such that $x:=u\oplus k\in X(\tau _{\omega })$ and $y:=P_{\tau _{\omega }}(u)\oplus k\in \bar {Y}(\tau _{\omega })$, which implies that for the corresponding triple $(u,x,y)$ it holds that $x\oplus u=y\oplus P_{\tau _{\omega }}(u)$. Moreover, remember from Theorem 5 the definition of $\mu (P,U,X,Y)$ for permutations P over $\left \{0,1\right \}^{n}$ and subsets $U,X,Y$ of $\left \{0,1\right \}^{n}$:

$$\begin{array}{@{}rcl@{}} \mu(P,U,X,Y)=\left|\left\{(u,x,y)\in U\times X\times Y; x\oplus u=y\oplus P(u)\right\}\right|. \end{array} $$

(20)

Consequently, $\mu (P_{\tau _{\omega }},U(\tau _{\omega }),X(\tau _{\omega }),\bar {Y}(\tau _{\omega }))$ is an upper bound for the number of $\tau _{\omega }$-critical keys.

Theorem 5 implies that the probability that for a randomly chosen $\omega \in {\Omega }$, it holds that

$$\mu(P_{\tau_{\omega}},U(\tau_{\omega}),X(\tau_{\omega}),\bar{Y}(\tau_{\omega}))\ge B(M,R,n), $$

is at most $2\cdot 2^{-n}$. Here, we took into account that $|U(\tau _{\omega })|\le M$, $|X(\tau _{\omega })|\le M$, and $|\bar {Y}(\tau _{\omega })|\le M\cdot (R+n-1)$.

So, the probability that for a randomly chosen $\omega \in {\Omega }$, $\omega$ falls into ${\Omega }^{\text {black}}$ because the number of $\tau _{\omega }$-critical keys exceeds $B(M,R,n)$, is bounded from above by $2\cdot 2^{-n}$.

We complete the proof by showing that

$$\Pr_{{\Omega}}\left[\mathit{Max}\left(P_{\tau_{\omega}},U(\tau_{\omega})\right)\ge 6\right]\le 32\cdot 2^{-n}. $$

According to Definition 12, the event $\mathit {Max}(P_{\tau _{\omega }},U(\tau _{\omega }))\ge 6$ implies the existence of some $U^{\prime }\subseteq U(\tau _{\omega })$, $|U^{\prime }|= 6$, such that $u^{\prime }_{1}\oplus P_{\tau _{\omega }}(u^{\prime }_{1})=u^{\prime }_{2}\oplus P_{\tau _{\omega }}(u^{\prime }_{2})$ for all $u^{\prime }_{1},u^{\prime }_{2}\in U^{\prime }$. Given a subset $U^{\prime }\subseteq U(\tau _{\omega })$, $|U^{\prime }|= 6$, the probability that $u^{\prime }_{1}\oplus P_{\tau _{\omega }}(u^{\prime }_{1})=u^{\prime }_{2}\oplus P_{\tau _{\omega }}(u^{\prime }_{2})$ holds for all $u^{\prime }_{1},u^{\prime }_{2}\in U^{\prime }$, equals

$$\prod\limits_{i = 1}^{5}\frac{1}{2^{n}-i}\le \left(\frac{1}{1/2\cdot 2^{n}}\right)^{5}= 2^{5}\cdot 2^{-5\cdot n}. $$

Consequently,

$$\begin{array}{@{}rcl@{}} \Pr\limits_{{\Omega}}\left[\mathit{Max}\left(P_{\tau_{\omega}},U(\tau_{\omega})\right)\ge 6\right] &\le& \left|U(\tau_{\omega})\right|^{6}\cdot 2^{5}\cdot 2^{-5\cdot n}\\ &\le& 2^{6\cdot (2/3)n} \cdot 2^{5} \cdot 2^{-5\cdot n}= 32\cdot 2^{-n}. \end{array} $$

Here, for the sake of simplicity, we upper bounded the number of subsets with six elements of $U(\tau _{\omega })$ by $|U(\tau _{\omega })|^{6}$. $|U(\tau _{\omega })|$, in turn, is upper bounded by $2^{(2/3)n}$ as the underlying transcript $\tau _{\omega }$ consists of at most $2^{(2/3)n}$ queries. □

5.11 Bounding the success probability on green elementary events (part (iii) of Lemma 2)

Let $\tau$ be a green transcript of length M, i.e., $\tau \in {\mathcal T}^{M}_{\text {green}}$. We have to bound the probability that Eve is successful under the condition that Alice has chosen a green elementary event $\omega =(k_{\omega },P_{\omega },F_{\omega })\in {\Omega }^{\text {green}}(\tau )$.

Depending on $\tau$, Eve publishes a pair $(x^{*}(\tau ),z^{*}(\tau ))\in \left \{0,1\right \}^{n}\times \left \{0,1\right \}^{n}$, where $x^{*}(\tau )\not \in X(\tau )$. Eve wins if and only if $z^{*}(\tau )$ equals the block of the first n keystream bits of the packet generated on input $x^{*}(\tau )$ under $\omega$, i.e.,

$$z^{*}(\tau)=F_{\omega}(P_{\omega}(x^{*}(\tau)\oplus k_{\omega})\oplus k_{\omega}). $$

For all $\omega \in {\Omega }^{\text {green}}(\tau )$, let $y_{\omega }$ denote the value

$$y_{\omega}=P_{\omega}(x^{*}(\tau)\oplus k_{\omega})\oplus k_{\omega}. $$

We have to bound the probability

$$\Pr_{{\Omega}^{\text{green}}(\tau)}[F_{\omega}(y_{\omega})=z^{*}(\tau)]. $$

We do this by dividing ${\Omega }^{\text {green}}(\tau )$ into two disjoint subsets $\mathit {IND}$ and $\mathit {DEP}$, where $\mathit {IND}$ contains all those elementary events $\omega \in {\Omega }^{\text {green}}(\tau )$ for which $F_{\omega }(y_{\omega })$ is independent from the queries and answers contained in $\tau$, and $\mathit {DEP}={\Omega }^{\text {green}}(\tau )\setminus \mathit {IND}$.

Note that $\omega \in \mathit {DEP}$ if and only if

• (I) there is some i, $-(n-1)\le i\le n-1$, such that $\pi ^{i}(y_{\omega })\in Y(\tau )$, or

• (II) there is some i, $-(n-1)\le i\le n-1$, some $x\in X(\tau )$, and some r, $0\le r\le R-1$, such that $\pi ^{i}(y_{\omega })=\pi ^{r}(P_{\omega }(x\oplus k_{\omega })\oplus k_{\omega })$.

In case (I), $F_{\omega }(y_{\omega })$ is not independent from the answer of the F-query with input $\pi ^{i}(y_{\omega })$; in case (II), $F_{\omega }(y_{\omega })$ is not independent from the answer of the E-query with input x (in particular, from the block starting at position r in packet $E_{\omega }(x)$).

Corresponding to this, $\mathit {DEP}$ can be written as

$$\mathit{DEP}=\mathit{DEP}_{1}\cup \mathit{DEP}_{2}, $$

where $\mathit {DEP}_{1}$ contains all $\omega \in {\Omega }^{\text {green}}(\tau )$ for which case (I) is fulfilled and $\mathit {DEP}_{2}$ contains all $\omega \in {\Omega }^{\text {green}}(\tau )$ for which case (II) is fulfilled.

Note that

$$\begin{array}{@{}rcl@{}} \Pr\limits_{{\Omega}^{\text{green}}(\tau)}[F_{\omega}(y_{\omega})=z^{*}(\tau)] &=& \Pr\limits_{{\Omega}^{\text{green}}(\tau)}[\mathit{DEP}]\cdot \Pr\limits_{{\Omega}^{\text{green}}(\tau)}[F_{\omega}(y_{\omega})=z^{*}(\tau)\mid\mathit{DEP}]\\ &&+\, \Pr\limits_{{\Omega}^{\text{green}}(\tau)}[\mathit{IND}]\cdot \Pr\limits_{{\Omega}^{\text{green}}(\tau)}[F_{\omega}(y_{\omega})=z^{*}(\tau)\mid\mathit{IND}]\\ &\le& \Pr\limits_{{\Omega}^{\text{green}}(\tau)}[\mathit{DEP}]+\Pr\limits_{{\Omega}^{\text{green}}(\tau)}[F_{\omega}(y_{\omega})=z^{*}(\tau)\mid\mathit{IND}], \end{array} $$

i.e.,

$$\begin{array}{@{}rcl@{}} \Pr\limits_{{\Omega}^{\text{green}}(\tau)}[F_{\omega}(y_{\omega})=z^{*}(\tau)] &\le& \Pr\limits_{{\Omega}^{\text{green}}(\tau)}[\mathit{DEP}_{1}]+\Pr\limits_{{\Omega}^{\text{green}}(\tau)}[\mathit{DEP}_{2}]\\ &&+ \Pr\limits_{{\Omega}^{\text{green}}(\tau)}[F_{\omega}(y_{\omega})=z^{*}(\tau)\mid\mathit{IND}]. \end{array} $$

(21)

It is quite obvious that

$$ \Pr_{{\Omega}^{\text{green}}(\tau)}[F_{\omega}(y_{\omega})=z^{*}(\tau) \mid \mathit{IND}]= 2^{-n}, $$

(22)

as $\omega \in \mathit {IND}$ implies that $F_{\omega }(y_{\omega })$ can take all values in $\left \{0,1\right \}^{n}$ with the same probability.

Next observe that for all $\omega \in {\Omega }^{\text {green}}(\tau )$ it holds that $\omega \in \mathit {DEP}_{1}$ if and only if

$$y_{\omega}\in \bigcup\limits_{y\in Y(\tau)} \{\pi^{i}(y);-(n-1)\le i\le n-1\}, $$

where the set at the right hand side has size at most $(2n-1)M$.

As $x^{*}(\tau )\not \in X(\tau )$, it follows by Corollary 2, part (b), that

$$ \Pr_{{\Omega}^{\text{green}}(\tau)}[\mathit{DEP}_{1}]\le (2n-1)\cdot M\cdot 9\cdot 2^{-(n-1)}. $$

(23)

Observe further that for all $\omega \in {\Omega }^{\text {green}}(\tau )$ it holds that $\omega \in \mathit {DEP}_{2}$ if and only if

$$\pi^{i}\left(P_{\omega}(x^{*}(\tau)\oplus k_{\omega})\oplus k_{\omega}\right)=P_{\omega}(x\oplus k_{\omega})\oplus k_{\omega} $$

for some $x\in X(\tau )$ and number i, $-(R+n-2)\le i\le n-1$.

As $x^{*}(\tau )\not \in X(\tau )$, it follows by Corollary 2, part (c), that

$$ \Pr_{{\Omega}^{\text{green}}(\tau)}[\mathit{DEP}_{2}]\le (R + 2n-2)\cdot M\cdot 11\cdot 2^{-(n-1)}. $$

(24)

Putting relations (21), (22), (23), and (24) together yields

$$\begin{array}{@{}rcl@{}} \Pr_{{\Omega}^{\text{green}}(\tau)}[{\Omega}^{\text{succ}}]&\le& (2+(2n-1)\cdot M\cdot 9+(R + 2n-2)\cdot M\cdot 11)\cdot 2^{-(n-1)}\\ &<&11\cdot (R + 4n)\cdot M\cdot 2^{-(n-1)}. \end{array} $$

□

5.12 Bounding the probability of red and blue transcripts (part (iv) of Lemma 2)

We have to show that

$$ \Pr_{{\Omega}}\left[{\Omega}^{\text{red}}\cup {\Omega}^{\text{blue}}\right]\le M\cdot e^{-n}. $$

(25)

In the proof, we will use a Chernoff bound argument, which is described in Appendix A.

Proof of Relation (25)

Note first that for all $\omega \in {\Omega }^{\text {red}}\cup {\Omega }^{\text {blue}}$, there is some j, $1\le j\le M$, such that the j-th query makes $\omega$ red or blue. Consequently,

$${\Omega}^{\text{red}}\cup {\Omega}^{\text{blue}}=\bigcup\limits_{j = 1}^{M} {\Omega}_{\text{green}}^{j-1}\cap \left({\Omega}_{\text{red}}^{j}\cup {\Omega}_{\text{blue}}^{j}\right), $$

which implies

$$\begin{array}{@{}rcl@{}} \Pr\limits_{{\Omega}}\left[{\Omega}^{\text{red}}\cup {\Omega}^{\text{blue}}\right] &\le& \sum\limits_{j = 1}^{M} \Pr\limits_{{\Omega}}\left[{\Omega}_{\text{green}}^{j-1}\cap \left({\Omega}_{\text{red}}^{j}\cup {\Omega}_{\text{blue}}^{j}\right) \right]\\ &=&\sum\limits_{j = 1}^{M} \Pr\limits_{{\Omega}}\left[{\Omega}_{\text{red}}^{j}\cup {\Omega}_{\text{blue}}^{j} \mid {\Omega}_{\text{green}}^{j-1}\right]\cdot \Pr\limits_{{\Omega}}\left[{\Omega}_{\text{green}}^{j-1}\right]\\ &\le& \sum\limits_{j = 1}^{M} \Pr\limits_{{\Omega}}\left[{\Omega}_{\text{red}}^{j}\cup {\Omega}_{\text{blue}}^{j} \mid {\Omega}_{\text{green}}^{j-1}\right]. \end{array} $$

Hence, for proving Relation (25), it is sufficient to show that for all j, $1\le j\le M$, it holds

$$ \Pr_{{\Omega}_{\text{green}}^{j-1}}\left[{\Omega}_{\text{red}}^{j}\cup {\Omega}_{\text{blue}}^{j}\right]=\Pr_{{\Omega}}\left[{\Omega}_{\text{red}}^{j}\cup {\Omega}_{\text{blue}}^{j} \mid {\Omega}_{\text{green}}^{j-1}\right]< e^{-n}. $$

(26)

We show Relation (26): Note first that Relation (26) is true if $j<\frac {{\Delta }}{R+n-1}$, as then for all transcripts $\tau$ with j queries it holds that the cardinalities of $X(\tau )$ and $\bar {Y}(\tau )$ are smaller than ${\Delta }$.

We fix some arbitrary number j, $\frac {{\Delta }}{R+n-1}\le j\le M$.

For all J, $1\le J\le j-1$, we define a random variable $DB_{J}\in \left \{0,1\right \}$ over ${\Omega }$, where $DB_{J}(\omega )= 1$ if and only if $\omega$ is J-alive and the J-th query along $\tau _{\omega }$ increases $(X(\tau _{\omega })\oplus k_{\omega })\cap U(\tau _{\omega })$ or increases $(\bar {Y}(\tau _{\omega })\oplus k_{\omega })\cap V(\tau _{\omega })$ or increases $X^{*}(\tau _{\omega })$. Formally,

$$\begin{array}{@{}rcl@{}} &&DB_{J}(\omega)= 1\ \Longleftrightarrow\\ &&|(X(\tau_{\omega}^{\le J})\oplus k_{\omega})\cap U(\tau_{\omega}^{\le J})|>|(X(\tau_{\omega}^{\le J-1})\oplus k_{\omega})\cap U(\tau_{\omega}^{\le J-1})|\ \text{or}\\ &&|(\bar{Y}(\tau_{\omega}^{\le J})\oplus k_{\omega})\cap V(\tau_{\omega}^{\le J})|>|(\bar{Y}(\tau_{\omega}^{\le J-1})\oplus k_{\omega})\cap V(\tau_{\omega}^{\le J-1})|\ \text{or}\\ &&|X^{*}(\tau_{\omega}^{\le J})|>|X^{*}(\tau_{\omega}^{\le J-1})|. \end{array} $$

Note that the event $\omega \in {\Omega }_{\text {red}}^{j}\cap {\Omega }_{\text {blue}}^{j}$ implies the event that

$$ \sum\limits_{J = 1}^{j-1} DB_{J}(\omega)\ge \frac{{\Delta}-(R+n-1)}{R+n-1}. $$

(27)

This is because each query along $\tau _{\omega }$ increases $(X(\tau _{\omega })\oplus k_{\omega })\cap U(\tau _{\omega })$ by at most one and $(\bar {Y}(\tau _{\omega })\oplus k_{\omega })\cap V(\tau _{\omega })$ by at most $R+n-1$ and $X^{*}(\tau _{\omega })$ by at most two.

In particular, each E-query can increases $(X(\tau _{\omega })\oplus k_{\omega })\cap U(\tau _{\omega })$ by at most one and $X^{*}(\tau _{\omega })$ by at most two, each P- or $P^{-1}$-query can increase $(X(\tau _{\omega })\oplus k_{\omega })\cap U(\tau _{\omega })$ and $(\bar {Y}(\tau _{\omega })\oplus k_{\omega })\cap V(\tau _{\omega })$ by at most one, and each F-query can increase $(\bar {Y}(\tau _{\omega })\oplus k_{\omega })\cap V(\tau _{\omega })$ by at most $R+n-1$ and $X^{*}(\tau _{\omega })$ by at most one.

We bound the probability of the event in Relation (27) over ${\Omega }_{\text {green}}^{j-1}$. We do this by bounding the probability of the event $DB_{J}(\omega )= 1$ over ${\Omega }_{\text {green}}^{j-1}$ for all $J = 1,\cdots ,j-1$. Let us fix a number J, $1\le J\le j-1$.

Note that

$$ \Pr_{{\Omega}_{\text{green}}^{j-1}}[DB_{J}(\omega)= 1]=\sum\limits_{\tau\in {\mathcal T}^{J}_{\text{green}}} \Pr_{{\Omega}_{\text{green}}^{j-1}}[\tau]\cdot \Pr_{{\Omega}_{\text{green}}^{j-1}(\tau)}[DB_{J}(\omega)= 1]. $$

Note further that for all $\tau \in {\mathcal T}^{J}_{\text {green}}$ and $\omega \in {\Omega }_{\text {green}}^{j-1}(\tau )$ it holds that $DB_{J}(\omega )= 1$ if and only if at least one of the following conditions is fulfilled.

• (A) The J-th query in $\tau$ is a P-query with input u or a $P^{-1}$-query with output u and $k_{\omega }\in u\oplus X(\tau )$.

• (B) The J-th query in $\tau$ is a P-query with output v or a $P^{-1}$-query with input v and $k_{\omega }\in v\oplus \bar {Y}(\tau )$.

• (C) The J-th query in $\tau$ is an F-query with input y and there is some r, $-(n-1)\le r\le R-1$, such that $k_{\omega }\in \pi ^{-r}(y)\oplus V(\tau )$.

• (D) The J-th query in $\tau$ is an E-query with input x and $k_{\omega }\in x\oplus U(\tau )$.

• (E) The J-th query in $\tau$ is an E-query with input x and $P_{\omega }(x\oplus k_{\omega })\oplus k_{\omega }=\bar {y}$ for some $\bar {y}\in \bar {Y}(\tau )$.

• (F) The J-th query in $\tau$ is an F-query with input y and $y=\pi ^{r}(P_{\omega }(x\oplus k_{\omega })\oplus k_{\omega })$ for some $x\in X(\tau )\setminus X^{*}(\tau )$ and some number r, $-(n-1)\le r\le R-1$.

• (G) The J-th query in $\tau$ is an E-query with input x and there is some r, $-(R-1)\le r\le R-1$, and some $x^{\prime }\in X(\tau )$ such that $\pi ^{r}(P_{\omega }(x\oplus k_{\omega })\oplus k_{\omega })=P_{\omega }(x^{\prime }\oplus k_{\omega })\oplus k_{\omega }$.

Note that (A) and (D) are the situations in which query J increases $(X(\tau _{\omega })\oplus k_{\omega })\cap U(\tau _{\omega })$, that (B) and (C) are the situations in which query J increases $(\bar {Y}(\tau _{\omega })\oplus k_{\omega })\cap V(\tau _{\omega })$, that (E) and (F) are the situations in which query J generates a new structural EF-collision (i.e., increases $X^{*}(\tau _{\omega })$ by one), and that (G) is the situation in which query J generates a new structural EE-collision (i.e., increases $X^{*}(\tau _{\omega })$ by one or two).

Note further that conditions (A,D) imply that $k_{\omega }$ belongs to a set of at most $J-1$ elements. Conditions (B,C) imply that $k_{\omega }$ belongs to a set of at most $(R+n-1)\cdot (J-1)$ elements. From Corollary 2, part (a), it follows that these events have probability at most $2^{-(n-1)}\cdot (R+n-1)\cdot (J-1)$.

From Corollary 2, part (b), it follows that condition $(E)$ has probability at most $9\cdot |\bar {Y}(\tau _{\omega })|\cdot 2^{-(n-1)}\le 9\cdot (R+n-1)\cdot (J-1)\cdot 2^{-(n-1)}$, and that condition $(F)$ has probability at most $9\cdot (R+n-1)\cdot |X(\tau _{\omega })|\cdot 2^{-(n-1)}\le 9\cdot (R+n-1)\cdot (J-1)\cdot 2^{-(n-1)}$.

From Corollary 2, part (c), it follows that condition $(G)$ has probability at most 11 ⋅ (2R − 1) ⋅|X(τ _ω )|⋅ 2^{−(n− 1)} ≤ 11 ⋅ (2R − 1) ⋅ (J − 1) ⋅ 2^{−(n− 1)}.

We obtain that for all J, $1\le J\le j-1$,

$$\begin{array}{@{}rcl@{}} \Pr\limits_{{\Omega}_{\text{green}}^{j-1}}[DB_{J}(\omega)= 1]&\le& 11\cdot 2^{-(n-1)}\cdot (2R-1)\cdot (J-1)\\ &<& 22\cdot 2^{-(n-1)}\cdot R\cdot (j-1). \end{array} $$

(28)

Relation (28) now enables us to apply the Chernoff bound method from Lemma 7 in Appendix A with $N=j-1$, p = 22 ⋅ 2^{−(n− 1)} ⋅ R ⋅ (j − 1) and $D=n$, and to obtain directly that

$$ \Pr_{{\Omega}^{j-1}_{\text{green}}}\left[\sum\limits_{J = 1}^{j-1} DB_{J}(\omega) > 22\cdot 2^{-(n-1)}\cdot R\cdot (j-1)^{2}+\sqrt{\frac{n\cdot (j-1)}{2}} \right]<e^{-n}. $$

(29)

Note that item (2) of Theorem 6 yields that

$$\begin{array}{@{}rcl@{}} &&22\cdot 2^{-(n-1)}\cdot R\cdot (j-1)^{2}+\sqrt{\frac{n\cdot (j-1)}{2}}\\ &<& 22\cdot 2^{-(n-1)}\cdot R\cdot M^{2}+\sqrt{\frac{n\cdot M}{2}}\\ &\le& \frac{{\Delta}-(R+n-1)}{R+n-1}. \end{array} $$

(30)

Thus, Relation (29) together with Relation (30) proves relations (26) and (25), and, consequently, Lemma 2, part (iv). □

6 Conclusion

In this paper, we introduced for the first time a random oracle model for KSG-based stream ciphers and proved a sharp asymptotic $(2/3)n$ bound on the security of the Lizard-construction, which underlies the stream cipher Lizard [22], against generic chosen-IV key recovery and packet prediction TMD tradeoff attacks. We hope that the security model and the lower bound techniques developed in this paper help to prove similar sharp security bounds for other stream cipher constructions such as the concatenation method underlying the state initialization of Trivium and Grain (see relations (3) and (4)). We have further shown that for a packet length $R>n$, where n denotes the inner state length of the underlying KSG, KSG-based stream ciphers can be only $n/2$-secure w.r.t. generic TMD tradeoff distinguishing attacks (see Corollary 2). From a theoretical point of view, it would be interesting to analyze the case $R=n$. Our conjecture is that for $R=n$, the Lizard-construction is $(2/3)n$-secure even against distinguishing attacks.

Appendices

Appendix A: Basic Methods III: A Short Excursion to Chernoff Bounds

At several places of our proof, we have to apply a technique called Chernoff bounds in the literature. The basic Chernoff bound argument is the following.

Theorem 7

Let N be a positive integer, $p\in (0,1)$, and $A_{1},\cdots ,A_{N}$ be a set of mutually independent random variables, where, for all $i = 1,\cdots ,N$, it holds that $\Pr [A_{i}= 1-p]=p$ and $\Pr [A_{i}=-p]= 1-p$. Let $A={\sum }_{i = 1}^{N} A_{i}$. Then

$$\Pr[A>a]<e^{-2\cdot a^{2} / N} $$

for all $a>0$.

For a proof see, e.g., Alon, Spencer, Erdos, The Probabilistic Method, Wiley Interscience 1992, Theorem A4 on page 235 [1].

We derive from Theorem 7 a corresponding result for random $\left \{0,1\right \}$-variables.

Lemma 6

Let $p,N$, and $A_{i}$ for $i = 1,\cdots ,N$ be defined as in Theorem 7, and let $B_{i}=A_{i}+p$. Note that $B_{i}\in \left \{0,1\right \}$ and $\Pr [B_{i}= 1]=p$. Let $B={\sum }_{i = 1}^{N} B_{i}$. Then, for all $d>0$, it holds

$$\Pr[B>(p+d)N]<e^{-{2\cdot d^{2}\cdot N}}. $$

Proof of Lemma 6

By definition, $B=A+N\cdot p$. The proof is completed by putting $a=d\cdot N$ into the relation in Theorem 7. □

We will apply Chernoff bound arguments in the following modified scenario. Before doing this we introduce a denotation.

Definition 20

Let $N\ge 1$ and $X_{1},\cdots ,X_{N}$ denote a collection of random $\left \{0,1\right \}$-variables. For all i, $1\le i\le N$, and for all $b=(b_{1},\cdots ,b_{i})\in \left \{0,1\right \}^{i}$ let $X(b)$ denote the event that $X_{j}=b_{j}$ for all $j = 1,\cdots ,i$.

Lemma 7

Let $C_{1},\cdots ,C_{N}$ denote a collection of random $\left \{0,1\right \}$-variables fulfilling the following two conditions for some probability bound p, $0<p<1$:

• (a) $\Pr [C_{1}= 1]=p_{1}<p$.

• (b) For all i, $2\le i\le N$,and all $b\in \left \{0,1\right \}^{i-1}$, there is some number $p(b)<p$, which can be computed from b, and for which it holds that

  $$\Pr[C_{i}= 1\mid C(b)]=p(b). $$

Let $C={\sum }_{i = 1}^{N} C_{i}$. Then, for all $d>0$, it holds

$$ \Pr[C>(p+d)N]<e^{-{2\cdot d^{2}\cdot N}}. $$

(31)

Comment 1

Note that $C_{1},\cdots ,C_{N}$ are allowed to be statistically dependent. However, conditions (a) and (b) imply that only a weak sort of dependence is allowed.

For illustrating this, observe that for satisfying Relation (31) it is not sufficient to require condition

• (a’) $\Pr [C_{j}= 1]<p$ for all $j = 1,\cdots ,N$.

A counterexample is given by the case that $C_{1}=C_{2}=\cdots =C_{N}$, which satisfies (a’) if $\Pr [C_{1}= 1]<p$, but which does not satisfies Relation (31).

Condition (a’) only implies condition (a) and the condition

• (b’) For all i, $2\le i\le N$,

  $$\sum\limits_{b\in\left\{0,1\right\}^{i-1}} \Pr[C(b)]\cdot \Pr[C_{i}= 1\mid C(b)]< p. $$

Note that condition (b’) is much weaker than condition (b), as condition (b) requires that $\Pr [C_{i}= 1\mid C(b)]< p$ holds not only in the average but for all $b\in \left \{0,1\right \}^{i-1}$.

Comment 2

At several places we will take $d=\sqrt {D/(2N)}$ and obtain

$$ \Pr[C>(p+d)N] =\Pr\left[C>pN+\sqrt{\frac{D\cdot N}{2}}\right] <e^{-D}. $$

Proof of Lemma 7

We construct a collection of mutually independent binary random variables $B_{1},\cdots ,B_{N}$ satisfying

• $C_{i}= 1$ implies $B_{i}= 1$,

• $\Pr [B_{i}= 1]=p$

for all i, $1\le i\le N$.

This proves our Lemma 7, as ${\sum }_{i = 1}^{N} C_{i}\le {\sum }_{i = 1}^{N} B_{i}$ with probability one, and as Lemma 6 can be applied to $B={\sum }_{i = 1}^{N} B_{i}$.

We first describe the experiment behind the random $\{0,1\}$-variables $C_{1},\cdots ,C_{N}$ and $B_{1},\cdots ,B_{N}$. Suppose that the experiments behind $C_{1},\cdots ,C_{N}$ and $B_{1},\cdots ,B_{N}$ are performed by a person named Tom. Tom uses a device with the following input/output behavior: If Tom inputs a number q, $0\le q\le 1$, into the device, then the device outputs a random bit $D\in \{0,1\}$ with $\Pr [D = 1]=q$. The device has no memory, i.e., if we contact the device at different times, then the corresponding outputs are mutually independent.

The experiments behind $C_{1},\cdots ,C_{N}$ and $B_{1},\cdots ,B_{N}$ refer to a probability bound p, $0< p< 1$, a probability value $p_{1}<p$, and an algorithm which assigns for each j, $1\le j\le N-1$, and each $\{0,1\}$-vector $b\in \{0,1\}^{j}$ a probability value $p(b)<p$.

□

The generation of the random {0, 1}-values $C_{1},\cdots ,C_{N}$

Tom generates $C_{1}$ by inputting $p_{1}$ into the device and taking the output as $C_{1}$. This implies $\Pr [C_{1}= 1]=p_{1}$. Moreover, Tom stores the result $C_{1}$ in his personal memory.

Now fix some j, $2\le j\le N$, and suppose that Tom has already generated the random $\{0,1\}$-values $C_{1},\cdots ,C_{j-1}$ and stored the outcomes $C_{1}=b_{1},\cdots ,C_{j-1}=b_{j-1}$ in his personal memory. This defines the $\{0,1\}$-vector $b=(b_{1},\cdots ,b_{j-1})\in \{0,1\}^{j-1}$.

Then Tom computes the probability value $p(b)<p$, inputs $p(b)$ to the device, takes the output as $C_{j}$, and stores the result for $C_{j}$ in his personal memory.

This implies $\Pr [C_{j}= 1 \mid C(b)]=p(b)$.

Moreover, this implies that

$$\Pr[C_{j}= 1]=\sum\limits_{b\in\left\{0,1\right\}^{j-1}} \Pr[C(b)]\cdot p(b)< p. $$

Note that there may exist $\{0,1\}$-vectors $b\in \{0,1\}^{j-1}$ such that $\Pr [C_{j}= 1]\neq \Pr [C_{j}= 1 \mid C(b)]=p(b)$, i.e., it may happen that $C_{j}$ is not statistically independent from $C_{1},\cdots ,C_{j-1}$.

However, if the $p(b)$-values are equal for all $b\in \{0,1\}^{j-1}$, then $C_{j}$ is statistically independent from $C_{1},\cdots ,C_{j-1}$.

The generation of the random {0, 1}-values $B_{1},\cdots ,B_{N}$

Tom generates $B_{1}$ as follows. First, he generates again $C_{1}$ by inputting $p_{1}$ into the device, taking the output as $C_{1}$, and stores $C_{1}$ in his personal memory. If $C_{1}= 1$, then he defines $B_{1}= 1$. If $C_{1}= 0$, then Tom inputs the probability value $\frac {p-p_{1}}{1-p_{1}}$ into the device and takes the output as $B_{1}$.

Note that

$$ \Pr[B_{1}= 1]=\Pr[C_{1}= 1]+\Pr[C_{1}= 0]\cdot \frac{p-p_{1}}{1-p_{1}}=p_{1}+\left(1-p_{1}\right)\frac{p-p_{1}}{1-p_{1}}=p. $$

(32)

Now we fix some j, $2\le j\le N$, and describe how Tom generates $B_{j}$. Suppose that Tom has already generated the random $\{0,1\}$-values $C_{1},\cdots ,C_{j-1}$ and the $\{0,1\}$-values $B_{1},\cdots ,B_{j-1}$, and that he has stored the outcomes $C_{1}=b_{1},\cdots ,C_{j-1}=b_{j-1}$, corresponding to the $\{0,1\}$-vector $b=(b_{1},\cdots ,b_{j-1})\in \{0,1\}^{j-1}$, in his personal memory.

Then Tom first generates $C_{j}$ by computing the probability value $p(b)<p$, inputting $p(b)$ to the device, taking the output as $C_{j}$, and stores the result for $C_{j}$ in his personal memory.

If $C_{j}= 1$, then he defines $B_{j}= 1$.

If $C_{j}= 0$, then Tom inputs the probability value $\frac {p-p(b)}{1-p(b)}$ into the device and takes the output as $B_{j}$.

By the same argument as in Relation (32), it holds that

$$\begin{array}{@{}rcl@{}} \Pr[B_{j}= 1 \mid C(b)]&=&\Pr[C_{j}= 1 \mid C(b)]+\Pr[C_{j}= 0 \mid C(b)]\cdot \frac{p-p(b)}{1-p(b)}\\ &=&p(b)+\left(1-p(b)\right)\frac{p-p(b)}{1-p(b)}=p. \end{array} $$

(33)

This implies that

$$\begin{array}{@{}rcl@{}} \Pr[B_{j}= 1]&=&\sum\limits_{b\in\left\{0,1\right\}^{j-1}} \Pr[C(b)]\cdot \Pr[B_{j}= 1 \mid C(b)]=\sum\limits_{b\in\left\{0,1\right\}^{j-1}} \left(\Pr[C(b)]\cdot p\right)\\ &=&p \cdot \sum\limits_{b\in\left\{0,1\right\}^{j-1}} \Pr[C(b)] = p \cdot 1 = p. \end{array} $$

The proof that B ₁,⋯ ,B _N are mutually independent

For all j, $1\le j\le N$, and $\{0,1\}$-vectors $b,b^{\prime }\in \{0,1\}^{j}$, we write $b^{\prime }\le b$ if $b^{\prime }_{i}\le b_{i}$ for all $i = 1,\cdots ,j$.

The way the random variables $B_{j}$ and $C_{j}$, $1\le j\le N$, are generated, implies the following two facts:

• (1) For all j, $2\le j\le N$, and $\{0,1\}$-vectors $b\in \{0,1\}^{j-1}$, the event $B(b)$ implies the event $\bigcup _{b^{\prime }\in \{0,1\}^{j-1},b^{\prime }\le b} C(b^{\prime })$. This implies that

  $$\Pr[B(b)]=\sum\limits_{b^{\prime}\in\{0,1\}^{j-1},b^{\prime}\le b} \Pr[B(b)\wedge C(b^{\prime})]. $$

• (2) For all j, $2\le j\le N$, and $\{0,1\}$-vectors $b,b^{\prime }\in \{0,1\}^{j-1}$ with $b^{\prime }\le b$, it holds that

  $$\Pr[B_{j}= 1 \mid B(b)\wedge C(b^{\prime})]=\Pr[B_{j}= 1 \mid C(b^{\prime})]=p. $$

Item (2) follows from the fact that the behavior of Tom when generating $B_{j}$ depends only on $b^{\prime }$.

For showing the mutual independence of $B_{1},\cdots ,B_{N}$, it is sufficient to show that for all j, $2\le j\le N$, and all $\{0,1\}$-vectors $b\in \{0,1\}^{j-1}$, it holds

$$\Pr[B_{j}= 1\mid B(b)]=\Pr[B_{j}= 1]=p. $$

Note that

$$\begin{array}{@{}rcl@{}} &&\Pr[B_{j}= 1\mid B(b)]=\frac{\Pr[B_{j}= 1\wedge B(b)]}{\Pr[B(b)]}\\ &=&\sum\limits_{b^{\prime}\in\{0,1\}^{j-1},b^{\prime}\le b}\frac{\Pr[B_{j}= 1\wedge B(b)\wedge C(b^{\prime})]}{\Pr[B(b)]}\\ &=&\sum\limits_{b^{\prime}\in\{0,1\}^{j-1},b^{\prime}\le b}\frac{\Pr[B(b)\wedge C(b^{\prime})]}{\Pr[B(b)]}\cdot \frac{\Pr[B_{j}= 1\wedge B(b)\wedge C(b^{\prime})]}{\Pr[B(b)\wedge C(b^{\prime})]}\\ &=&\sum\limits_{b^{\prime}\in\{0,1\}^{j-1},b^{\prime}\le b}\frac{\Pr[B(b)\wedge C(b^{\prime})]}{\Pr[B(b)]}\cdot \Pr[B_{j}= 1\mid B(b)\wedge C(b^{\prime})]\\ &=&p\cdot \frac{1}{\Pr[B(b)]}\cdot \sum\limits_{b^{\prime}\in\{0,1\}^{j-1},b^{\prime}\le b} \Pr[B(b)\wedge C(b^{\prime})]=p. \end{array} $$

Appendix B: The Proof of Corollary 2, Parts (b.4) and (c)

Let us fix an arbitrary number j, $1\le j\le M$, and a green transcript $\tau \in {\mathcal T}^{j}_{\text {green}}$. We assume that part (a) of Corollary 2 holds, i.e., that for all $k\in K^{\text {green}}(\tau )$

$$ \Pr_{{\Omega}^{\text{green}}(\tau)}[k]\le 2^{-(n-1)}. $$

(34)

Let us first prove part (b.4) of Corollary 2. We fix some $x,\bar {y}\in \left \{0,1\right \}^{n}$, where $x\not \in X^{*}(\tau )$ and $\bar {y}\not \in \bar {Y}^{*}(\tau )$ and (x∉X(τ) or $\bar {y}\not \in \bar {Y}(\tau )$). We have to show

$$ \Pr_{{\Omega}^{\text{green}}(\tau)}[P_{\omega}(x\oplus k_{\omega})\oplus k_{\omega}=\bar{y}]\le 9\cdot 2^{-(n-1)}. $$

(35)

Proof of Relation (35)

We divide ${\Omega }^{\text {green}}(\tau )$ into two subsets ${\Omega }_{1}$ and ${\Omega }_{2}$, where

$$\begin{array}{@{}rcl@{}} {\Omega}_{1}&=&\{\omega\in {\Omega}^{\text{green}}(\tau);x\oplus k_{\omega}\not \in U(\tau)\},\\ {\Omega}_{2}&=&\{\omega\in {\Omega}^{\text{green}}(\tau);x\oplus k_{\omega}\in U(\tau)\} \end{array} $$

(36)

and denote

$$\begin{array}{@{}rcl@{}} K_{1}&=&\{k\in K^{\text{green}}(\tau);x\oplus k\not\in U(\tau)\},\\ K_{2}&=&\{k\in K^{\text{green}}(\tau);x\oplus k\in U(\tau)\}. \end{array} $$

(37)

The sets ${\Omega }_{2}$ and $K_{2}$ define another set $W\subseteq \left \{0,1\right \}^{n}$ by

$$W=\{P_{\omega}(x\oplus k_{\omega})\oplus k_{\omega};\omega\in{\Omega}_{2} \}=\{P_{\tau}(x\oplus k)\oplus k; k\in K_{2}\}. $$

Here, $P_{\tau }$ denotes the restriction of $P_{\omega }$ to $U(\tau )$ which, by definition, is equal for all $\omega \in {\Omega }(\tau )$.

Note that $|W|\le |K_{2}|\le |U(\tau )|\le j\le M$.

Let us now define an equivalence relation on $K_{2}$. For keys $k,k^{\prime }\in K_{2}$ we define that $k\equiv k^{\prime }$ if $P_{\tau }(x\oplus k)\oplus k=P_{\tau }(x\oplus k^{\prime })\oplus k^{\prime }$.

Let $L_{1},\cdots ,L_{s}$ denote the equivalence classes corresponding to the equivalence relation $\equiv$ on $K_{2}$.

Clearly, $s=|W|$ and for each class $L_{l}$, $1\le l\le s$, there is exactly one $w\in W$ such that $P_{\tau }(x\oplus k)\oplus k=w$ for all $k\in L_{l}$.

Note that $k\equiv k^{\prime }$ implies that $x\oplus k\equiv _{P_{\tau }} x\oplus k^{\prime }$ in the sense of Definition 12 and remember that, as $\tau$ is not black, $\mathit {Max}(P_{\tau },U(\tau ))\le 5$. This implies that for all $w\in W$

$$ |\{k\in K_{2};P_{\tau}(x\oplus k)\oplus k=w\}|\le 5. $$

(38)

Note that

$$\begin{array}{@{}rcl@{}} &&\Pr\limits_{{\Omega}^{\text{green}}(\tau)}[P_{\omega}(x\oplus k_{\omega})\oplus k_{\omega}=\bar{y}]\\ &=& \Pr\limits_{{\Omega}^{\text{green}}(\tau)}[{\Omega}_{1}]\cdot \Pr\limits_{{\Omega}^{\text{green}}(\tau)}[P_{\omega}(x\oplus k_{\omega})\oplus k_{\omega}=\bar{y} \mid {\Omega}_{1}]\\ &&+ \Pr\limits_{{\Omega}^{\text{green}}(\tau)}[{\Omega}_{2}]\cdot \Pr\limits_{{\Omega}^{\text{green}}(\tau)}[P_{\omega}(x\oplus k_{\omega})\oplus k_{\omega}=\bar{y} \mid {\Omega}_{2}], \end{array} $$

i.e.,

$$\begin{array}{@{}rcl@{}} &&\Pr\limits_{{\Omega}^{\text{green}}(\tau)}[P_{\omega}(x\oplus k_{\omega})\oplus k_{\omega}=\bar{y}]\\ &\le& \Pr\limits_{{\Omega}^{\text{green}}(\tau)}[P_{\omega}(x\oplus k_{\omega})\oplus k_{\omega}=\bar{y} \mid {\Omega}_{1}]\\ &&+\Pr\limits_{{\Omega}^{\text{green}}(\tau)}[{\Omega}_{2}]\cdot \Pr\limits_{{\Omega}^{\text{green}}(\tau)}[P_{\omega}(x\oplus k_{\omega})\oplus k_{\omega}=\bar{y} \mid {\Omega}_{2}]. \end{array} $$

(39)

For estimating $\Pr _{{\Omega }^{\text {green}}(\tau )}[P_{\omega }(x\oplus k_{\omega })\oplus k_{\omega }=\bar {y} \mid {\Omega }_{1}]$ note that if $x\oplus k_{\omega }\not \in U(\tau )$ and $x\in X(\tau )$, then $P_{\omega }(x\oplus k_{\omega })$ takes all values in $\left \{0,1\right \}^{n}$ which are outside of $V(\tau )$ and which are outside of $\bar {Y}(\tau )\oplus k_{\omega }$ with the same probability (see the proof of Lemma 3).⁴ If $x\not \in X(\tau )$ then $P_{\omega }(x\oplus k_{\omega })$ takes all values in $\left \{0,1\right \}^{n}$, which are outside of $V(\tau )$ with the same probability (see the proof of Lemma 3).

This implies that

$$ \Pr_{{\Omega}^{\text{green}}(\tau)}[P_{\omega}(x\oplus k_{\omega})\oplus k_{\omega}=\bar{y} \mid {\Omega}_{1}]\le \frac{1}{2^{n}-(R+n)M}\le 2^{-(n-1)} $$

(40)

if n is large enough.

Observe next that by Relation (34) it holds that

$$ \Pr_{{\Omega}^{\text{green}}(\tau)}[{\Omega}_{2}]\le 2^{-(n-1)}\cdot |K_{2}|. $$

(41)

For estimating $\Pr _{{\Omega }^{\text {green}}(\tau )}[P_{\omega }(x\oplus k_{\omega })\oplus k_{\omega }=\bar {y} \mid {\Omega }_{2}]$ we first consider the case that $\bar {y}\not \in W$. Then, by the definition of W, it holds that

$$\Pr_{{\Omega}^{\text{green}}(\tau)}[P_{\omega}(x\oplus k_{\omega})\oplus k_{\omega}=\bar{y} \mid {\Omega}_{2}]= 0. $$

Assume now that $\bar {y}\in W$. From Relation 38 and the Smoothness Lemma (Lemma 5) it follows that

$$ \Pr_{{\Omega}^{\text{green}}(\tau)}[P_{\omega}(x\oplus k_{\omega})\oplus k_{\omega}=\bar{y} \mid {\Omega}_{2}]\le \sqrt{2}\frac{5}{|K_{2}|}\le \frac{8}{|K_{2}|}. $$

(42)

Inserting relations (40), (41), and (42) into Relation (39) yields

$$\begin{array}{@{}rcl@{}} \Pr\limits_{{\Omega}^{\text{green}}(\tau)}[P_{\omega}(x\oplus k_{\omega})\oplus k_{\omega}=\bar{y}]&\le& 2^{-(n-1)}+ 2^{-(n-1)}\cdot |K_{2}|\cdot \frac{8}{|K_{2}|}\\ &=&9\cdot 2^{-(n-1)}. \end{array} $$

□

Let us now prove part (c) of Corollary 2. We fix some $x\neq x^{\prime }\in \left \{0,1\right \}^{n}$, where $x\not \in X(\tau )$ and $x^{\prime }\in X(\tau )$, and some number i, $-(R+n)\le i\le R+n$. We have to show

$$ \Pr_{{\Omega}^{\text{green}}(\tau)}[Ev(x,x^{\prime},i)]\le 11\cdot 2^{-(n-1)}, $$

(43)

where the event $Ev(x,x^{\prime },i)\subseteq {\Omega }^{\text {green}}(\tau )$ is defined to be

$$Ev(x,x^{\prime},i)=\left\{\omega\in {\Omega}^{\text{green}}(\tau);\pi^{i}\left(P_{\omega}(x\oplus k_{\omega})\oplus k_{\omega}\right)=P_{\omega}(x^{\prime}\oplus k_{\omega})\oplus k_{\omega}\right\}. $$

Proof of Relation (43)

Let us first handle the case that $x^{\prime }\in X^{*}(\tau )$ and denote by $y^{\prime }$ the unique value for which $(x^{\prime },y^{\prime })\in \mathit {Coll}(\tau )$. Then, by the definition of structural EF-collisions, it holds that

$$P_{\omega}(x^{\prime}\oplus k_{\omega})\oplus k_{\omega}=y^{\prime} $$

for all $\omega \in {\Omega }^{\text {green}}(\tau )$.

Consequently, for all $\omega \in {\Omega }^{\text {green}}(\tau )$ it holds that $\omega \in Ev(x,x^{\prime },i)$ if and only if

$$P_{\omega}(x\oplus k_{\omega})\oplus k_{\omega}=\pi^{-i}(y^{\prime}). $$

From part (b) of Corollary 2 it follows that if $x^{\prime }\in X^{*}(\tau )$, then

$$\Pr_{{\Omega}^{\text{green}}(\tau)}[Ev(x,x^{\prime},i)]\le 9\cdot 2^{-(n-1)}<11\cdot 2^{-(n-1)}. $$

Now let us consider the case that $x^{\prime }\in X(\tau )\setminus X^{*}(\tau )$.

For arbitrary points $z\in \left \{0,1\right \}^{n}$ we define

$${\Omega}^{\text{green}}(\tau,z)=\{\omega\in {\Omega}^{\text{green}}(\tau);P_{\omega}(x\oplus k_{\omega})\oplus k_{\omega}=z\} $$

and

$$K^{\text{green}}(\tau,z)=\{k\in \left\{0,1\right\}^{n};\exists \omega\in{\Omega}^{\text{green}}(\tau,z): k_{\omega}=k\}. $$

Moreover, for $b\in \{1,2\}$ we define

$${\Omega}_{b}(z)={\Omega}^{\text{green}}(\tau,z)\cap {\Omega}_{b} $$

and

$$K_{b}(z)=K^{\text{green}}(\tau,z)\cap K_{b}, $$

where the sets ${\Omega }_{1}$ and ${\Omega }_{2}$ and the sets $K_{1}$ and $K_{2}$ are defined as in relations (36) and (37).

Let us clarify how the keys in elementary events in ${\Omega }_{1}(z)$ and ${\Omega }_{2}(z)$ and the keys in $K_{1}(z)$ and $K_{2}(z)$ look like.

It can be easily checked that for all $\omega =(k_{\omega },P_{\omega },F_{\omega })\in {\Omega }_{1}$ it holds $\omega \in {\Omega }_{1}(z)$ if and only if z ⊕ k _ω ∉V (τ) and $P_{\omega }(x\oplus k_{\omega })=z\oplus k_{\omega }$.

Moreover, for all $\omega =(k_{\omega },P_{\omega },F_{\omega })\in {\Omega }_{2}$ it holds $\omega \in {\Omega }_{2}(z)$ if and only if P _τ (x ⊕ k _ω ) ⊕ k _ω = z, which implies by Relation 38 that

$$ |K_{2}(z)|\le 5. $$

(44)

We obtain that

$$\begin{array}{@{}rcl@{}} |K^{\text{green}}(\tau,z)|\ge |K_{1}(z)|&\ge& |K_{1}|-|V(\tau)|\\ &=&|K^{\text{green}}(\tau)|-|K_{2}|-|V(\tau)|\\ &\ge& |K^{\text{green}}(\tau)|-2\cdot |V(\tau)|\\ &\ge& |K^{\text{green}}(\tau)|-2M\ge \frac{1}{\sqrt{2}}\cdot 2^{n} \end{array} $$

(45)

if n is large enough. The last inequation follows from $M < 2^{(2/3) n}$ and the proof of the Smoothness Lemma (Lemma 5): It is a straightforward consequence of relations (52) and (53) in Appendix C that for all green transcripts $\tau$ and all constants $\delta <1$ it holds that $|K^{\text {green}}(\tau )|\ge \delta \cdot 2^{n}$ if n is large enough. Lemma 5 states this only for $\delta =\frac {1}{\sqrt {2}}$.

By exactly the same arguments as in the Smoothness Lemma (Lemma 5) one can show that for all $k,k^{\prime }\in K^{\text {green}}(\tau ,z)$ it holds that

$$ \Pr_{{\Omega}^{\text{green}}(\tau,z)}[k]\le \sqrt{2}\cdot \Pr_{{\Omega}^{\text{green}}(\tau,z)}[k^{\prime}]. $$

(46)

if n is large enough.

Relations (45) and (46) imply directly that for all $k\in K^{\text {green}}(\tau ,z)$ it holds

$$ \Pr_{{\Omega}^{\text{green}}(\tau,z)}[k]\le 2^{-(n-1)} $$

(47)

if n is large enough.

Note that

$$\begin{array}{@{}rcl@{}} &&\Pr\limits_{{\Omega}^{\text{green}}(\tau)}[Ev(x,x^{\prime},i)]\\ &=&\sum\limits_{z\in\left\{0,1\right\}^{n}}\Pr\limits_{{\Omega}^{\text{green}}(\tau)}[P_{\omega}(x\oplus k_{\omega})\oplus k_{\omega}=z] \cdot \Pr\limits_{{\Omega}^{\text{green}}(\tau,z)}[Ev(x,x^{\prime},i)]. \end{array} $$

(48)

For deriving an upper bound for $\Pr _{{\Omega }^{\text {green}}(\tau ,z)}[Ev(x,x^{\prime },i)]$ we write

$$\begin{array}{@{}rcl@{}} \Pr\limits_{{\Omega}^{\text{green}}(\tau,z)}[Ev(x,x^{\prime},i)] &=&\Pr\limits_{{\Omega}^{\text{green}}(\tau,z)}[{\Omega}_{1}(z)]\cdot \Pr\limits_{{\Omega}_{1}(z)}[Ev(x,x^{\prime},i)]\\ &&+\Pr\limits_{{\Omega}^{\text{green}}(\tau,z)}[{\Omega}_{2}(z)]\cdot \Pr\limits_{{\Omega}_{2}(z)}[Ev(x,x^{\prime},i)]\\ &\le& \Pr\limits_{{\Omega}_{1}(z)}[Ev(x,x^{\prime},i)]+\Pr\limits_{{\Omega}^{\text{green}}(\tau,z)}[{\Omega}_{2}(z)]\\ &\le& \Pr\limits_{{\Omega}_{1}(z)}[Ev(x,x^{\prime},i)]+ 5\cdot 2^{-(n-1)}, \end{array} $$

(49)

where the last inequality follows from relations (44) and (47).

We write $K_{1}(z)$ as

$$K_{1}(z)=K_{3}(z)\cup K_{4}(z)\cup K_{5}(z), $$

where

• $K_{3}(z)=\{k\in K_{1}(z); x^{\prime }\oplus k\in U(\tau ),\ P_{\tau }(x^{\prime }\oplus k)\oplus k=\pi ^{i}(z)\}$,

• $K_{4}(z)=\{k\in K_{1}(z); x^{\prime }\oplus k\in U(\tau ),\ P_{\tau }(x^{\prime }\oplus k)\oplus k\neq \pi ^{i}(z)\}$,

• $K_{5}(z)=\{k\in K_{1}(z); x^{\prime }\oplus k\not \in U(\tau )\}$.

From Relation 38 we know that $|K_{3}(z)|\le 5$. Moreover, for all $k\in K_{4}(z)$ it holds

$$\Pr_{{\Omega}_{1}(z)}[Ev(x,x^{\prime},i)\cap(k_{\omega}\in K_{4}(z))]= 0. $$

Consequently,

$$ \Pr_{{\Omega}_{1}(z)}[Ev(x,x^{\prime},i)] \le \Pr_{{\Omega}_{5}(z)}[Ev(x,x^{\prime},i)]+ 5\cdot 2^{-(n-1)}, $$

(50)

where ${\Omega }_{5}(z)=\{\omega \in {\Omega }_{1}(z);k_{\omega }\in K_{5}(z)\}$.

Note that for all $\omega \in {\Omega }_{5}(z)$, the condition that $\omega \in Ev(x,x^{\prime },i)$ is equivalent to

$$P_{\omega}(x^{\prime}\oplus k_{\omega})=\pi^{i}(z)\oplus k_{\omega}, $$

which has probability 0 if $\pi ^{i}(z)\oplus k_{\omega }\in V(\tau )$ and probability at most

$$\frac{1}{2^{n}-(|V(\tau)|+ 1)-|\bar{Y}(\tau)|}\le 2^{-(n-1)} $$

if $\pi ^{i}(z)\oplus k_{\omega }\not \in V(\tau )$ and n is large enough, see Relation (40) and the comment before Relation (40).

We obtain that

$$ \Pr_{{\Omega}_{5}(z)}[Ev(x,x^{\prime},i)]\le 2^{-(n-1)} $$

(51)

if n is large enough.

Putting relations (51), (50), and (49) together, we obtain that for all $z\in \left \{0,1\right \}^{n}$

$$\Pr\limits_{{\Omega}^{\text{green}}(\tau,z)}[Ev(x,x^{\prime},i)]\le 11\cdot 2^{-(n-1)}, $$

which implies by Relation (48) that

$$\begin{array}{@{}rcl@{}} \Pr\limits_{{\Omega}^{\text{green}}(\tau)}[Ev(x,x^{\prime},i)]\le 11\cdot 2^{-(n-1)}. \end{array} $$

□

Appendix C: The Proof of the Smoothness Lemma (Lemma 5), Part (II)

We fix an arbitrary number j, $1\le j\le M$, and a green transcript $\tau \in {\mathcal T}^{j}_{\text {green}}$. We analyze the probability distribution $\Pr _{{\Omega }(\tau )}$ on $K^{\text {green}}(\tau )$ by showing that for all $k\in K^{\text {green}}(\tau )$ it holds that this distribution is close to the uniform distribution on $K^{\text {green}}(\tau )$. More precisely,

$$\begin{array}{@{}rcl@{}} &&\Pr\limits_{{\Omega}(\tau)}[k]\le \delta\cdot |K^{\text{green}}(\tau)|^{-1}\\ &&\text{for } \delta=\left(\frac{2^{n-1}}{2^{n-1}-(R+n)j}\right)^{2{\Delta}}. \end{array} $$

(52)

Note that part (3) of Theorem 6 implies $\delta \le \sqrt {2}$. This is because for $\theta =(R+n)j$ and $N = 2^{n-1}$ we can write $\delta$ as

$$ \delta=\left(\frac{N}{N-\theta}\right)^{2{\Delta}}=\left(\frac{1}{1-\theta/N}\right)^{2{\Delta}}=\left(\left(\frac{1}{1-\theta/N}\right)^{N/\theta}\right)^{\frac{2{\Delta} \theta}{N}} \approx e^{\frac{2{\Delta} \theta}{N}}. $$

(53)

Part (3) of Theorem 6 implies that ${\Delta }\cdot \theta \le \frac {\ln (2)\cdot N}{4}$, which is equivalent to

$$\frac{2{\Delta} \theta}{N}\le \frac{\ln{2}}{2}. $$

The Proof of Relation (52)

The proof of Lemma 3 shows how, for keys $k\in K(\tau )$, completions $P^{\prime }$ of $P_{\tau }$ on $\left \{0,1\right \}^{n}\setminus U(\tau )$ and $F^{\prime }$ of $F_{\tau }$ on $\left \{0,1\right \}^{n}\setminus Y(\tau )$ have to be constructed such that $(k,P^{\prime },F^{\prime })$ belongs to ${\Omega }(\tau )$. In particular:

• (1) The function values of $P^{\prime }$ on $X^{*}(\tau )\oplus k$, a set of size $|X^{*}(\tau )|$, are determined.

• (2) The function values of $P^{\prime }$ on the set $((X(\tau )\setminus X^{*}(\tau ))\oplus k)\setminus U(\tau )$ are forbidden to fall into the set $\bar {Y}(\tau ) \oplus k$.

• (3) We assume that $P^{\prime }$ is an arbitrarily fixed completion of $P_{\tau }$ satisfying (1) and (2) and describe how a completion $F^{\prime }$ of $F_{\tau }$ has to be constructed in such a way that $(k,P^{\prime },F^{\prime })$ belongs to ${\Omega }(\tau )$. The function values $F^{\prime }(y)$ are determined or partly determined on a set $Z(k)=Z_{1}(k)\cup Z_{2}(k)$, where $Z_{1}(k)$ contains all those $y\in \left \{0,1\right \}^{n}$ for which there is some r, $-(n-1)\le r\le R-1$, such that $\pi ^{-r}(y)=P^{\prime }(x\oplus k)\oplus k$ for some $x\in X(\tau )\setminus X^{*}(\tau )$, and $Z_{2}(k)$ contains all those $y\in \left \{0,1\right \}^{n}$ for which there is some i, $-(n-1)\le i\le n-1$, such that $\pi ^{i}(y)\in Y(\tau )$. Note that $Z_{1}(k)\cap Z_{2}(k)=\emptyset$ and $|Z_{1}(k)|=|Z_{1}(k^{\prime })|$ and $|Z_{2}(k)|=|Z_{2}(k^{\prime })|$ for all $k,k^{\prime }\in K^{\text {green}}(\tau )$. This implies that $Z(k)$ has the same size for all $k\in K^{\text {green}}(\tau )$.

We use the following fact. Let $A_{1},B_{1},A_{2},B_{2}$ be finite sets fulfilling $A_{1}\cap A_{2}=B_{1}\cap B_{2}=\emptyset$, $|A_{1}\cup A_{2}|=|B_{1}\cup B_{2}|$, $|A_{2}|<|B_{1}|$ and $|B_{2}|<|A_{1}|$. Then the number of bijective mappings $f:A_{1}\cup A_{2}\longrightarrow B_{1}\cup B_{2}$ for which $f(A_{2})\subseteq B_{1}$ is

$$ \frac{|A_{1}|!\cdot |B_{1}|!}{(|A_{1}|-|B_{2}|)!}=\frac{|A_{1}|!\cdot |B_{1}|!}{(|B_{1}|-|A_{2}|)!}. $$

(54)

In the following, $A_{1}$ corresponds to the set $\left \{0,1\right \}^{n}\setminus (U(\tau )\cup (X(\tau )\oplus k))$, $A_{2}$ to the set $((X(\tau )\setminus X^{*}(\tau ))\oplus k)\setminus U(\tau )$, B₁ to the set $\left \{0,1\right \}^{n}\setminus (V(\tau )\cup (\bar {Y}(\tau )\oplus k))$ and $B_{2}$ to the set $((\bar {Y}(\tau )\setminus \bar {Y}^{*}(\tau ))\oplus k)\setminus V(\tau )$. We denote

• $T = 2^{n}-|X(\tau )|-|U(\tau )|$,

• $t=|X(\tau )\setminus X^{*}(\tau )|$,

• $S = 2^{n}-|\bar {Y}(\tau )|-|V(\tau )|$,

• $s=|\bar {Y}(\tau )\setminus \bar {Y}^{*}(\tau )|$.

It holds that $S>2^{n-1}$ and $T>2^{n-1}$ if n is large enough.

Note that for proving Lemma 5 it is sufficient to show that for all pairs $k,k^{\prime }\in K^{\text {green}}(\tau )$

$$\frac{\Pr_{{\Omega}(\tau)}[k]}{\Pr_{{\Omega}(\tau)}[k^{\prime}]}\le \delta. $$

This is because $\tau$ is green, which, together with $\Pr _{{\Omega }^{\text {blue}}(\tau )}[k] = \Pr _{{\Omega }^{\text {blue}}(\tau )}[k^{\prime }] = 0$ for $k,k^{\prime }\in K^{\text {green}}(\tau )$, implies

$$\begin{array}{@{}rcl@{}} \frac{\Pr_{{\Omega}(\tau)}[k]}{\Pr_{{\Omega}(\tau)}[k^{\prime}]} &=& \frac{\Pr_{{\Omega}(\tau)}[{\Omega}^{\text{green}}(\tau)] \cdot \Pr_{{\Omega}^{\text{green}}(\tau)}[k] + \Pr_{{\Omega}(\tau)}[{\Omega}^{\text{blue}}(\tau)] \cdot \Pr_{{\Omega}^{\text{blue}}(\tau)}[k]}{\Pr_{{\Omega}(\tau)}[{\Omega}^{\text{green}}(\tau)] \cdot \Pr_{{\Omega}^{\text{green}}(\tau)}[k^{\prime}] + \Pr_{{\Omega}(\tau)}[{\Omega}^{\text{blue}}(\tau)] \cdot \Pr_{{\Omega}^{\text{blue}}(\tau)}[k^{\prime}]}\\ &=& \frac{\Pr_{{\Omega}^{\text{green}}(\tau)}[k]}{\Pr_{{\Omega}^{\text{green}}(\tau)}[k^{\prime}]}. \end{array} $$

For this purpose, let us denote by $\mathit {ConsP}_{\tau }(k)$ the set of all $\tau$-consistent completions $P^{\prime }$ of $P_{\tau }$ on $\left \{0,1\right \}^{n}\setminus U(\tau )$, i.e., of all completions $P^{\prime }$ of $P_{\tau }$ for which there is some completion $F^{\prime }$ of $F_{\tau }$ on $\left \{0,1\right \}^{n}\setminus Y(\tau )$ such that $(k,P^{\prime },F^{\prime })\in {\Omega }(\tau )$.

The above statement (3) implies that for all $k\in K(\tau )$ and completions $P^{\prime }\in \mathit {ConsP}_{\tau }(k)$, the number of such completions $F^{\prime }$ is the same, i.e., does not depend on k.

This implies that

$$\frac{\Pr_{{\Omega}(\tau)}[k]}{\Pr_{{\Omega}(\tau)}[k^{\prime}]}=\frac{|\mathit{ConsP}_{\tau}(k)|}{|\mathit{ConsP}_{\tau}(k^{\prime})|}. $$

Note that due to requirement (2) (see above), the size of $\mathit {ConsP}_{\tau }(k)$ depends on the sizes of the sets $((X(\tau )\setminus X^{*}(\tau ))\oplus k)\setminus U(\tau )$ and $((\bar {Y}(\tau )\setminus \bar {Y}^{*}(\tau ))\oplus k)\setminus V(\tau )$. As k is not blue, the sizes of the corresponding intersections $((X(\tau )\setminus X^{*}(\tau ))\oplus k)\cap U(\tau )$ and $((\bar {Y}(\tau )\setminus \bar {Y}^{*}(\tau ))\oplus k)\cap V(\tau )$ can vary only between 0 and ${\Delta }$ (see Definition 19).

Thus, for $k\in K^{\text {green}}(\tau )$, the value $|\mathit {ConsP}_{\tau }(k)|$ is minimal if

$$|((X(\tau)\setminus X^{*}(\tau))\oplus k)\cap U(\tau)|=|((\bar{Y}(\tau)\setminus \bar{Y}^{*}(\tau))\oplus k)\cap V(\tau)|= 0. $$

By Relation (54) this implies

$$ |\mathit{ConsP}_{\tau}(k)|=\frac{S!\cdot T!}{(T-s)!}=\frac{S!\cdot T!}{(S-t)!}. $$

(55)

The value $|\mathit {ConsP}_{\tau }(k)|$ is maximal if

$$\begin{array}{@{}rcl@{}} &&|((X(\tau)\setminus X^{*}(\tau))\oplus k)\cap U(\tau)|=\min\{{\Delta},t\}\\ \text{and } &&|((\bar{Y}(\tau)\setminus \bar{Y}^{*}(\tau))\oplus k)\cap V(\tau)|=\min\{{\Delta},s\}. \end{array} $$

(56)

We now have to distinguish three cases corresponding to whether $|X(\tau )\setminus X^{*}(\tau )|>{\Delta }$ or not and whether $|\bar {Y}(\tau )\setminus \bar {Y}^{*}(\tau )|>{\Delta }$ or not.

Case 1 :

$|X(\tau )\setminus X^{*}(\tau )|>{\Delta }$ and $|\bar {Y}(\tau )\setminus \bar {Y}^{*}(\tau )|>{\Delta }$.

In this case, it follows from relations (54) and (56) that

$$ |\mathit{ConsP}_{\tau}(k)|\le \frac{(S+{\Delta})!\cdot (T+{\Delta})!}{(S+{\Delta}-(t-{\Delta}))!}=\frac{(S+{\Delta})!\cdot (T+{\Delta})!}{(S + 2{\Delta}-t)!}. $$

(57)

Relations (55) and (57) imply that the $\Pr _{{\Omega }(\tau )}$-values of elements from $K^{\text {green}}(\tau )$ can differ by a factor $\delta$ which is at most $\delta _{1}\cdot \delta _{2}$, where

$$\begin{array}{@{}rcl@{}} \delta_{1} &=& \frac{(T + 1)(T + 2){\cdots} (T+{\Delta})}{(S-(t-1))(S-(t-1)+ 1){\cdots} (S-(t-1)+{\Delta}-1)}\\ &\le& \left(\frac{T}{S-t}\right)^{{\Delta}} \end{array} $$

(58)

and

$$\begin{array}{@{}rcl@{}} \delta_{2} &=& \frac{(S + 1)(S + 2){\cdots} (S+{\Delta})}{(S-(t-1)+{\Delta})(S-(t-1)+{\Delta}+ 1){\cdots} (S-(t-1)+ 2{\Delta}-1)}\\ &\le& \left(\frac{S}{S-(t-{\Delta})}\right)^{{\Delta}}\le \left(\frac{S}{S-j}\right)^{{\Delta}}\le \left(\frac{2^{n-1}}{2^{n-1}-j}\right)^{{\Delta}}. \end{array} $$

Here we used the fact that from $a\geq b$ it follows that $\frac {a}{b}\geq \frac {a + 1}{b + 1}$.

For upper bounding $\delta _{1}$ we have to distinguish the two cases $S\ge T$ and $S<T$.

If $S\ge T$, then, by Relation (58),

$$\begin{array}{@{}rcl@{}} \delta_{1}\le \left(\frac{S}{S-t}\right)^{{\Delta}}\le \left(\frac{2^{n-1}}{2^{n-1}-j}\right)^{{\Delta}}. \end{array} $$

(59)

If $S< T$, then observe that $S\ge T-(R+n-1)j$. This holds because $|\bar {Y}(\tau )|\le (R+n-1)j$. Consequently,

$$\begin{array}{@{}rcl@{}} \delta_{1}&\le& \left(\frac{T}{T-t-(R+n-1)j}\right)^{{\Delta}}\\ &\le& \left(\frac{T}{T-j-(R+n-1)j}\right)^{{\Delta}}\\ &=&\left(\frac{T}{T-(R+n)j}\right)^{{\Delta}} \le \left(\frac{2^{n-1}}{2^{n-1}-(R+n)j}\right)^{{\Delta}}. \end{array} $$

(60)

Case 2 :

$|X(\tau )\setminus X^{*}(\tau )|\le {\Delta }$, i.e., $t\le {\Delta }$.

Here, $|\mathit {ConsP}_{\tau }(k)|$ is maximal if $(X(\tau )\setminus X^{*}(\tau ))\oplus k$ is a subset of $U(\tau )$, which implies that $|\mathit {ConsP}_{\tau }(k)|$ is $(T+t)!$ and that, by Relation (55), the $|\mathit {ConsP}_{\tau }(k)|$-values for $k\in K^{\text {green}}(\tau )$ cannot differ by a factor larger than

$$\begin{array}{@{}rcl@{}} &&\frac{(T+t)!\cdot (S-t)!}{T!\cdot S!}=\frac{(T + 1)\cdot\ldots\cdot(T+t)}{(S-t + 1)\cdot\ldots\cdot S}\\ &\le& \left(\frac{T}{S-t}\right)^{t} \le \left(\frac{T}{S-t}\right)^{{\Delta}} \le \left(\frac{2^{n-1}}{2^{n-1}-(R+n)j}\right)^{{\Delta}}. \end{array} $$

Note that the last inequation follows from the same case distinction (i.e., $S \geq T$ and $S < T$) that was already performed as part of Case 1 above (see relations (59) and (60)).

Case 3 :

$|\bar {Y}(\tau )\setminus \bar {Y}^{*}(\tau )|\le {\Delta }$, i.e., $s\le {\Delta }$.

Here, $|\mathit {ConsP}_{\tau }(k)|$ is maximal if $(\bar {Y}(\tau )\setminus \bar {Y}^{*}(\tau ))\oplus k$ is a subset of $V(\tau )$, which implies that $|\mathit {ConsP}_{\tau }(k)|$ is $(S+s)!$ and that, by Relation (55), the $|\mathit {ConsP}_{\tau }(k)|$-values for $k\in K^{\text {green}}(\tau )$ cannot differ by a factor larger than

$$\begin{array}{@{}rcl@{}} &&\frac{(S+s)!\cdot (T-s)!}{T!\cdot S!} =\frac{(S + 1)\cdot\ldots\cdot(S+s)}{(T-s + 1)\cdot\ldots\cdot T}\\ &\le& \left(\frac{S}{T-s}\right)^{s} \le \left(\frac{S}{T-s}\right)^{{\Delta}} \le \left(\frac{S}{S-j-s}\right)^{{\Delta}}\\ &\le& \left(\frac{S}{S-j-(R+n-1)j}\right)^{{\Delta}} = \left(\frac{S}{S-(R+n)j}\right)^{{\Delta}} \le \left(\frac{2^{n-1}}{2^{n-1}-(R+n)j}\right)^{{\Delta}}. \end{array} $$

Summarizing all three cases we obtain that

$$\begin{array}{@{}rcl@{}} \delta\le \left(\frac{2^{n-1}}{2^{n-1}-(R+n)j}\right)^{2{\Delta}}. \end{array} $$

□

Appendix D: A List of Denotations used in the Proof of Theorem 6

• Elementary Events $\omega =(k_{\omega },P_{\omega },F_{\omega })$ and the Probability Space ${\Omega }$: Definition 4 in Section 4.

• $\omega$-critical Triples: Definition 5 in Section 5.1.

• $\omega$-dangerous Triples: Definition 5 in Section 5.1.

• $\omega$-sudden death Triples: Definition 5 in Section 5.1.

• The number $B(M,R,n)$: Definition 6 in Section 5.2.

• Chernoff Bounds: Appendix A.

• Structural EF- and EE-Collisions: Definition 7 in Section 5.3.

• The Friendly Alice: Definition 8 in Section 5.3.

• Sudden Death: Definition 9 in Section 5.3.

• Transcripts $\tau$: Section 5.4.

• ${\Omega }^{\text {succ}}$, ${\Omega }^{\mathrm {s.death}}$: Section 5.4.

• Set of transcripts ${\mathcal T}^{j}$: beginning of Section 5.5.

• The sets $X(\tau )$, $Y(\tau )$, $U(\tau )$, $V(\tau )$, $X^{*}(\tau )$, $\bar {Y}^{*}(\tau )$, $\bar {Y}^{(r)}(\tau )$, $\bar {Y}(\tau )$, $Coll(\tau )$, ${\Omega }(\tau )$, $K(\tau )$ for transcripts $\tau$: Definition 10 in Section 5.5.

• $\tau$-consistency: Definition 10 in Section 5.5.

• $(\tau ,k)$-critical Points: Definition 11 in Section 5.6.

• The relation $\equiv _{P}$: Definition 12 in Section 5.7.

• $\tau$-critical Keys: Definition 13 in Section 5.7.

• Black Transcripts and Events, ${\Omega }^{j}_{\text {black}}$, ${\Omega }^{\text {black}}$, ${\mathcal T}^{j}_{\text {black}}$: Definition 15 in Section 5.7.

• Restrictions $\tau _{\omega }^{\le j}$ of transcripts: Definition 15 in Section 5.7.

• Red Transcripts and Events: Definition 16 in Section 5.7.

• Blue Events: Definition 17 in Section 5.7.

• j-alive Elementary Events: Definition 14 in Section 5.7.

• Green and j-green Elementary Events and Green Transcripts: Definition 18 in Section 5.7.

• $\tau$-green resp. $\tau$-blue Keys, $K^{\text {green}}(\tau )$ resp. $K^{\text {blue}}(\tau )$: Definition 19 in Section 5.7.