What are some group-theoretic properties of product ciphers?

Question Posted / guest

1 Answers
1974 Views
I also Faced
E-Mail Answers

What are some group-theoretic properties of product ciphers? ..

Answer / boss

Let E be a product cipher that maps N-bit blocks to N-bit blocks.
Let E_K(X) be the encryption of X under key K. Then, for any fixed K,
the map sending X to E_K(X) is a permutation of the set of N-bit
blocks. Denote this permutation by P_K. The set of all N-bit
permutations is called the symmetric group and is written S_{2^N}.
The collection of all these permutations P_K, where K ranges over all
possible keys, is denoted E(S_{2^N}). If E were a random mapping from
plaintexts to ciphertexts then we would expect E(S_{2^N}) to generate
a large subset of S_{2^N}.

Coppersmith and Grossman [COP74] have shown that a very simple
product cipher can generate the alternating group A_{2^N} given a
sufficient number of rounds. (The alternating group is half of the
symmetric group: it consists of all ``even'' permutations, i.e., all
permutations which can be written as an even number of swaps.)
Even and Goldreich [EVE83] were able to extend these results to show
that Feistel ciphers can generate A_{2^N}, given a sufficient number
of rounds.

The security of multiple encipherment also depends on the
group-theoretic properties of a cipher. Multiple encipherment is an
extension over single encipherment if for keys K1, K2 there does
not exist a third key K3 such that

E_K2(E_K1(X)) == E_(K3)(X) (**)

which indicates that encrypting twice with two independent keys
K1, K2 is equal to a single encryption under the third key K3. If
for every K1, K2 there exists a K3 such that eq. (**) is true then
we say that E is a group.

This question of whether DES is a group under this definition was
extensively studied by Sherman, Kaliski, and Rivest [SHE88]. In their
paper they give strong evidence for the hypothesis that DES is not a
group. In fact DES is not a group [CAM93].

Is This Answer Correct ?

0 Yes

0 No

Post New Answer