50
V. Mikhalev et al.
practical issues and limitations on their implementation in hardware[421], we
describe the stream cipher Sprout which was designed in order to demonstrate
the feasibility of the approach [27], and its improvement Plantlet where the
security weaknesses of Sprout were fixed [421]. In Sect. 3.3 we present a generic
attack [314] against such KSGs that implies a design criterion. Section 3.4 presents
an approach to security enhancement of certain encryption schemes employing universal homophonic coding [397] and a randomized encryption paradigm [503]. The
approach summarized in this section has been reported and discussed in a number
of references including [413, 418, 452] and [420]. A security evaluation of this
encryption scheme has been reported in [452] from an information-theoretic point
of view, and a computational-complexity evaluation approach is given in [420].
3.2 Keystream Generators with Keyed Update Functions
3.2.1 Design Approach
Stream ciphers usually provide a higher throughput than block ciphers. However,
due to the existence of certain TMDTO [47, 91, 237] attacks, the area size required
to implement secure stream ciphers is often higher. The reason is the following. The
effort of TMDTO attacks against stream ciphers is O(2 σ/2 ), where σ is the internal
state size. Therefore, a rule of thumb says that to achieve κ-bit security level, the
state size should be at least σ = 2 · κ. This results in the fact that a stream cipher
requires at least 2 · κ memory gates which are the most costly hardware elements in
terms of area and power-consumption. In this section we discuss an extension [27,
421] of the common design principle, which allows for secure lightweight stream
ciphers with internal state size below this bound.
We start the description of the new approach for stream ciphers design by giving
the definition of the KSG with KUF [27]:
Definition 1 (Keystream Generator with Keyed Update Function) A keystream
generator with a keyed update function comprises three sets, namely the key space
K = GF(2) κ , the IV space I V = GF(2) ν , and the variable state space S =
GF(2) σ . Moreover, it uses the following three functions
• an initialization function Init : I V × K → S
• an update function Upd : K × S → S such that Upd k : S → S ,
Upd k (st) := Upd(k, st), is bijective for any k ∈ K , and
• an output function Out : S → GF(2).
The internal state ST is composed of a variable part st ∈ S and a fixed part
k ∈ K . A KSG operates in two phases. In the initialization phase, the KSG
takes as input a secret key k and a public IV iv and sets the internal state to
V. Mikhalev et al.
practical issues and limitations on their implementation in hardware[421], we
describe the stream cipher Sprout which was designed in order to demonstrate
the feasibility of the approach [27], and its improvement Plantlet where the
security weaknesses of Sprout were fixed [421]. In Sect. 3.3 we present a generic
attack [314] against such KSGs that implies a design criterion. Section 3.4 presents
an approach to security enhancement of certain encryption schemes employing universal homophonic coding [397] and a randomized encryption paradigm [503]. The
approach summarized in this section has been reported and discussed in a number
of references including [413, 418, 452] and [420]. A security evaluation of this
encryption scheme has been reported in [452] from an information-theoretic point
of view, and a computational-complexity evaluation approach is given in [420].
3.2 Keystream Generators with Keyed Update Functions
3.2.1 Design Approach
Stream ciphers usually provide a higher throughput than block ciphers. However,
due to the existence of certain TMDTO [47, 91, 237] attacks, the area size required
to implement secure stream ciphers is often higher. The reason is the following. The
effort of TMDTO attacks against stream ciphers is O(2 σ/2 ), where σ is the internal
state size. Therefore, a rule of thumb says that to achieve κ-bit security level, the
state size should be at least σ = 2 · κ. This results in the fact that a stream cipher
requires at least 2 · κ memory gates which are the most costly hardware elements in
terms of area and power-consumption. In this section we discuss an extension [27,
421] of the common design principle, which allows for secure lightweight stream
ciphers with internal state size below this bound.
We start the description of the new approach for stream ciphers design by giving
the definition of the KSG with KUF [27]:
Definition 1 (Keystream Generator with Keyed Update Function) A keystream
generator with a keyed update function comprises three sets, namely the key space
K = GF(2) κ , the IV space I V = GF(2) ν , and the variable state space S =
GF(2) σ . Moreover, it uses the following three functions
• an initialization function Init : I V × K → S
• an update function Upd : K × S → S such that Upd k : S → S ,
Upd k (st) := Upd(k, st), is bijective for any k ∈ K , and
• an output function Out : S → GF(2).
The internal state ST is composed of a variable part st ∈ S and a fixed part
k ∈ K . A KSG operates in two phases. In the initialization phase, the KSG
takes as input a secret key k and a public IV iv and sets the internal state to