Minimalism in cryptography, or the Even – Mansour scheme

Back in 1997, Israeli scientists Shimon Even and Ishay Mansour (Yishay Mansour) asked themselves the question: how minimal can a strong block cipher have ? By minimality they meant the number of structural elements in the cipher scheme, and by persistence - any (formally correct) lower estimate of the complexity of the attacks on this cipher. As they say, under the cut - a description of the minimum (to this day) block cipher with provable strength.

Lyrical digression

~~Virtually~~ all encryption standards used today are not formally strong . No one gives, and cannot give any guarantee that there are no bookmarks, vulnerabilities or weaknesses. Just so far no one has invented (or, at least, has not published) any ways to crack these ciphers = ways to significantly reduce the exponential complexity of a complete search. Opening up ~~virtually~~ any cryptographic algorithm on which your security and privacy are based, be it symmetric, asymmetric encryption, or hashing, is reduced to solving relatively complex problems (for example, to the problem of discrete logarithmization). Complicated because no one has yet offered relatively simple solutions. Unless we learn to logarithm in a finite field or factorize numbers in polynomial time (or until we build a quantum computer more), DH and RSA will be considered stable, and only the number of bits in the key will grow in proportion to the power of personal computers.

And all because we still do not know how to get lower ratings. Friends, in mathematics (and especially in cryptography) there are not so many beautiful ideas and elegant solutions, and there are even less proven estimates from below. The cipher considered here, in my opinion, falls into the intersection: it is as simple as possible, and at the same time formally resistant.
')
I warn you at once that this publication is not a work of art for unprepared readers, although it does not contain anything more complicated than the Bayes conditional probability formula and elementary arithmetic of fractions. The inexperienced reader will remain satisfied with the description of the design of the cipher , and a strict proof of its endurance is given here for professionals and true connoisseurs of mathematics.

Israeli scientists Shiman Even (Shimon Even) and Ishei Mansour (Yishay Mansour) in [EM97] proposed a way to build a block cipher with demonstrable persistence, based on the only randomly selected permutation from $S_ {2n}$ .

Before I introduce you directly to this block cipher, let me indicate a list of the introduced symbols and basic definitions. However, you can always return to it, therefore, in the event that I managed to awaken in you a serious interest to see everything “here and now”, go directly to the description of the cipher.

Definitions and conventions

Sets, sets

$\ left \ lbrace A, B, C, \ dots \ right \ rbrace$ - unordered set of elements $A, B, C, \ dots$
$\ left \ langle A, B, C, \ dots \ right \ rangle$ - ordered set of elements $A, B, C, \ dots$

Inscriptions

$\ mathcal {P}, \ mathcal {C}, \ mathcal {K}$ - spaces used by cryptosystems
$\ mathrm {A}, \ mathrm {B}$ - algorithms, computing models
$\ mathrm {E}, \ mathrm {P}, \ mathrm {D}$ - oracles
$\ mathsf {E}, \ mathsf {P}$ - sets developed by algorithms
$\ pi, \ sigma, \ delta$ - substitutions
$\ mathsf {CP}, \ mathsf {EFP}$ - tasks

Legend

$\ mathcal {P}$ - a lot of open texts (messages)
$\ left \ lbrace P_1, P_2, \ dots \ right \ rbrace \ subseteq \ mathcal {P}$ - open texts $P_1, P_2, \ dots$
$\ mathcal {C}$ - many ciphertexts (cryptograms)
$\ left \ lbrace C_1, C_2, \ dots \ right \ rbrace \ subseteq \ mathcal {C}$ - ciphertexts $C_1, C_2, \ dots$
$\ mathcal {K}$ - many keys
$\ left \ lbrace K_1, K_2, \ dots \ right \ rbrace \ subseteq \ mathcal {K}$ - keys $K_1, K_2, \ dots$
$\ underline {K} \ in \ mathcal {K}$ - true key
$E \ colon \ mathcal {P} \ times \ mathcal {K} \ mapsto \ mathcal {C}$ - encryption function
$D \ colon \ mathcal {C} \ times \ mathcal {K} \ mapsto \ mathcal {P}$ - decryption function
$\ mathrm {P} _ {\ sigma}, \ mathrm {P} _ {\ sigma} ^ {- 1}$ - oracles that implement substitutions $\ sigma, \ sigma ^ {- 1}$
$\ mathrm {E} _ {K, \ sigma}, \ mathrm {D} _ {K, \ sigma}$ - oracles realizing functions $E, D$ on the key $K$
$p _ {\ mathrm {A}}$ - probability of success of the algorithm $\ mathrm {A}$
$T _ {\ mathrm {A}}$ - algorithm execution time $\ mathrm {A}$

Definitions

Cryptosystem $S$ is called an ordered set of five $S = \ left \ langle \ mathcal {P}, \ mathcal {C}, \ mathcal {K}, E, D \ right \ rangle$ where

$\ mathcal {P}$ - a lot of open texts ( plaintexts ),
$\ mathcal {C}$ - many ciphertexts ( ciphertexts ),
$\ mathcal {K}$ - set of keys ( keys ),
$E$ - (injective) encryption function ( encipher ):

$E \ colon \ mathcal {P} \ times \ mathcal {K} \ mapsto \ mathcal {C}; \ quad \ forall K \ in \ mathcal {K} \ implies E_K \ colon \ mathcal {P} \ mapsto \ mathcal {C};$

$D$ - decipher function:

$D \ colon \ mathcal {C} \ times \ mathcal {K} \ mapsto \ mathcal {P}; \ quad \ forall K \ in \ mathcal {K} \ implies D_K \ colon \ mathcal {C} \ mapsto \ mathcal {P}.$

Classical Even – Mansour scheme

Israeli scientists Shimon Even and Yishay Mansour in their work proposed a block cipher with provable cryptographic strength, for which only one substitution is required $\ pi$ which is randomly (or pseudo-randomly) selected from the set of all permutations $S_ {2 ^ n}$ over open texts.

It is assumed that the selected substitution is not part of the key, and is available to any attacker in the form of a “black box”.

It is argued that, from the point of view of the attacker, the proposed cipher is almost indistinguishable from the ideal random cipher, and the probability of a successful opening of the system $\ underline {K}$ ) is polynomially small (the main result is Theorem 2 , Corollary 2.1 of it, and Theorem 3 ).

It is also argued that the use of a pseudo-random substitution instead of a truly random substitution does not change the shown cipher strength.

Description

Let be $\ mathcal {P} \ equiv \ mathcal {C}$ and $\ pi \ in S _ {\ left \ vert \, {\ mathcal {P} \, \ right \ vert}$ - substitution selected from the set $S _ {\ left \ vert \, {\ mathcal {P} \, \ right \ vert}$ of all substitutions over a set of open texts, and $\ pi ^ {- 1}$ - back to her.

It is assumed that for any elements $P \ in \ mathcal {P}$ and $C \ in \ mathcal {C}$ sets of open and ciphertext values $\ pi (P)$ and $\ pi ^ {- 1} (C)$ can be easily obtained either by directly calculating the value of substitutions $\ pi$ and $\ pi ^ {- 1}$ or by referring to public oracles $\ mathrm {P} _ {\ pi}$ and $\ mathrm {P} ^ {- 1} _ {\ pi}$ .

Open spaces and ciphertexts are binary spaces. $n$ –Dimensional vectors: $\ mathcal {P} \ equiv \ mathcal {C} = \ left \ lbrace 0, 1 \ right \ rbrace ^ n = \ mathbb {Z} _ {2} ^ {n}$ and the key space of the system is the space of binary vectors of dimension $2n$ : $\ mathcal {K} = \ left \ lbrace 0,1 \ right \ rbrace ^ {2n} = \ mathbb {Z} _ {2} ^ {2n}$ .

The secret key $\ underline {K} \ in \ mathcal {K}$ is an ordered pair of two $n$ –Dimensional plug (half) $\ underline {K} _1$ and $\ underline {K} _2$ ; each subkey is selected randomly from space $n$ –Dimensional binary vectors with equal probability $2 ^ {- n}$ .

It is also assumed that the selected secret key $\ underline {K}$ known only to legitimate users, and is used by them to encrypt plaintext (messages) and decrypt ciphertexts (cryptograms).

Plain text encryption $P$ using a secret key $\ underline {K} = \ left \ langle \ underline {K} _1, \ underline {K} _2 \ right \ rangle$ and the selected substitution $\ pi$ as follows:

$E _ {\ underline {K}} (P) = E (P, \ left \ langle \ underline {K} _1, \ underline {K} _2 \ right \ rangle) = \ pi (P \ oplus \ underline {K} _1) \ oplus \ underline {K} _2,$

and decryption ciphertext $C$ with a key $K$ and the selected substitution $\ pi$ - as follows:

$D _ {\ underline {K}} (C) = D (C, \ left \ langle \ underline {K} _1, \ underline {K} _2 \ right \ rangle) = \ pi ^ {- 1} (C \ oplus \ underline {K} _2) \ oplus \ underline {K} _1.$

Really simple? They took the message, poked it with the first half of the key, replaced the plate that was open and accessible to everyone, poked it with the second half of the key, and the cryptogram was obtained. Great, right? Why does nobody use this scheme in practice? After all, it is much easier AES, and DES. The easiest block cipher. Where is the catch?

Trick

The thing is, the substitution is set to binary $n$ –Bit vectors, and storing the replacement table for a randomly selected substitution is completely unacceptable; $\ mathcal {O} \! \ left (n 2 ^ n \ right)$ of memory. The only possible solution to this problem is to build good pseudo-random substitutions (polynomially indistinguishable from random ones), whose values could be relatively easily calculated at any point; and this we do not know how.

About minimal scheme

It should be noted that the classical scheme is minimal in the sense that the removal of any of the elements of this scheme leads to a significant weakening of its durability. It is easy to show that removing any of the additions with subkeys, or substitutions $\ pi$ make the circuit vulnerable, and as a result, completely unstable.

There is no addition with the first subkey.

The encryption function is:

$E (P, \ underline {K}) = C = \ pi (P) \ oplus \ underline {K}, \ text {where} \ underline {K} \ in \ mathcal {K} \ equiv \ mathcal {P} = \ mathbb {Z} _ {2} ^ {n}.$

The attacker can easily calculate the secret key $\ underline {K}$ knowing the substitution $\ pi$ :

$\ underline {K} = C \ oplus \ pi (P).$
There is no addition with the second subkey.

The encryption function is:

$E (P, \ underline {K}) = C = \ pi (P \ oplus \ underline {K}), \ text {where} \ underline {K} \ in \ mathcal {K} \ equiv \ mathcal {P} = \ mathbb {Z} _ {2} ^ {n}.$

The attacker can easily calculate the secret key $\ underline {K}$ knowing the substitution $\ pi ^ {- 1}$ :

$\ underline {K} = \ pi ^ {- 1} (C) \ oplus P.$
Missing $S$ –Block (substitution $\ pi$ )

The encryption function is:

$E (P, \ underline {K} _1 \ oplus \ underline {K} _2) = C = P \ oplus \ underline {K} _1 \ oplus \ underline {K} _2.$

The attacker can easily calculate the secret key $\ underline {K}$ :

$\ underline {K} = \ underline {K} _1 \ oplus \ underline {K} _2 = P \ oplus C.$

About circuit durability

Assumptions of persistence, determination

The persistence of the proposed scheme is due to the following assumptions:

the attacker does not know the true key $\ underline {K} \ in \ mathcal {K}$ ;
the attacker has the ability to encrypt plaintext (messages) and decrypt ciphertexts (cryptograms) on the secret key $\ underline {K}$ ;
the attacker has the ability to calculate the permutation values $\ pi$ and reverse permutations to it $\ pi ^ {- 1}$ .

Any algorithm that uncovers a system can refer to the following four oracles. $\ mathrm {P}, \ mathrm {P} ^ {- 1}, \ mathrm {E}, \ mathrm {D}$ :

oracle $\ mathrm {P} _ {\ pi}$ calculates the permutation value $\ pi \ in S _ {\ left \ vert \, \ mathcal {P} \ right \ vert \,}$ on $n$ –Dimensional binary input set $M$ :

$\ mathrm {P} _ {\ pi} \ colon \ mathbb {Z} _ {2} ^ {n} \ mapsto \ mathbb {Z} _ {2} ^ {n}, \ quad \ operatorname {\ mathrm {P } _ {\ pi}} \ left [M \ right]} = \ pi (M);$

oracle $\ mathrm {P} ^ {- 1} _ {\ pi}$ calculates the permutation value $\ pi ^ {- 1} \ in S _ {\ left \ vert \, \ mathcal {P} \, \ right \ vert}$ on $n$ –Dimensional binary input set $M '$ :

$\ mathrm {P} ^ {- 1} _ {\ pi} \ colon \ mathbb {Z} _ {2} ^ {n} \ mapsto \ mathbb {Z} _ {2} ^ {n}, \ quad \ operatorname {\ mathrm {P} ^ {- 1} _ {\ pi}} \ left [M '\ right]} = \ pi ^ {- 1} (M');$

oracle $\ mathrm {E} _ {\ underline {K}, \ pi}$ encrypts $n$ –Dimensional binary set (clear text) $P$ on $2n$ –Dimensional key $\ underline {K}$ :

$\ mathrm {E} _ {\ underline {K}, \ pi} \ colon \ mathcal {P} \ equiv \ mathbb {Z} _ {2} ^ {n} \ mapsto \ mathcal {C} \ equiv \ mathbb { Z} _ {2} ^ {n}, \ quad \ operatorname {\ mathrm {E} _ {\ underline {K}, \ pi}} \ left [P \ right]} = \ underline {K} _2 \ oplus \ pi (P \ oplus \ underline {K} _1);$

oracle $\ mathrm {D} _ {\ underline {K}, \ pi}$ decodes $n$ –Dimensional binary set (ciphertext) $C$ on $2n$ –Dimensional key $\ underline {K}$ :

$\ mathrm {D} _ {\ underline {K}, \ pi} \ colon \ mathcal {C} \ equiv \ mathbb {Z} _ {2} ^ {n} \ mapsto \ mathcal {P} \ equiv \ mathbb { Z} _ {2} ^ {n}, \ quad \ operatorname {\ mathrm {D} _ {\ underline {K}, \ pi}} \ left [C \ right]} = \ underline {K} _1 \ oplus \ pi ^ {- 1} (C \ oplus \ underline {K} _2).$

Further, if the substitution, the value of which calculates the oracle $\ mathrm {P} _ {\ pi}$ ( $\ mathrm {P} ^ {- 1} _ {\ pi}$ ), selected, and encryption and decryption is carried out on a fixed key $\ underline {K}$ , then the index of the notation of oracles, we will omit: $\ mathrm {P}, \ mathrm {P} ^ {- 1}, \ mathrm {E}, \ mathrm {D}$ .

Addressing the oracles $\ mathrm {P}$ and $\ mathrm {P} ^ {- 1}$ with queries to calculate the value of substitutions $\ pi$ and $\ pi ^ {- 1}$ in points $M$ and $M '= \ pi (M)$ algorithm gets answers $M '$ and $M$ respectively.
Thus, the communication of any algorithm with oracles $\ mathrm {P}$ and $\ mathrm {P} ^ {- 1}$ is reduced to the formation of pairs of the form "point", "the value of the substitution $\ pi$ at this point:

$\ left \ langle M, M '\ right \ rangle = \ left \ langle M, \ pi (M) \ right \ rangle.$

Let's call such pairs $P$ –Pairs and a set of all $P$ –Pairs developed by some algorithm $\ mathrm {A}$ as a result of its implementation, we denote by $\ mathsf {P} _ {\ mathrm {A}}$ , or simply $\ mathsf {P}$ .

Addressing the oracles $\ mathrm {E}$ and $\ mathrm {D}$ with plaintext encryption requests $P$ and decryption ciphertext $C = E (P, \ underline {K})$ algorithm gets answers $C$ and $P$ respectively.
So, communication of any algorithm with oracles $\ mathrm {E}$ and $\ mathrm {D}$ is reduced to the formation of pairs of the form "clear text", "ciphertext":

$\ left \ langle P, C \ right \ rangle = \ left \ langle M, E (P, \ underline {K \ right \ rangle)}.$

Let's call such pairs $E$ –Pairs , and a set of all $E$ –Pairs developed by some algorithm $\ mathrm {A}$ as a result of its implementation, we denote by $\ mathsf {E} _ {\ mathrm {A}}$ , or simply $\ mathsf {E}$ .

Definition
$E$ –Pairs $\ left \ langle P_1, C_1 \ right \ rangle$ and $\ left \ langle P_2, C_2 \ right \ rangle$ are called intersecting if $P_1 = P_2$ either $C_1 = C_2$ .

A similar definition can be formulated for $P$ –Pair

Definition
$P$ –Pairs $\ left \ langle M_1, M_1 '\ right \ rangle$ and $\ left \ langle M_2, M_2 '\ right \ rangle$ are called intersecting if $M_1 = M_1 '$ either $M_2 = M_2 '$ .

Statement 1 (Overlapping pairs are identical)
Due to the fact that all oracles $\ mathrm {P} _ {\ sigma}, \ mathrm {P} ^ {- 1} _ {\ sigma}, \ mathrm {E} _ {K, \ sigma}, \ mathrm {D} _ {K, \ sigma}$ honest for any fixed $\ sigma$ and $K$ valid statements:

intersecting $E$ –Pairs are the same;
intersecting $P$ –Pairs are the same.

Modulo statement 1, we can assume that all pairs of sets $\ mathsf {E}$ and $\ mathsf {P}$ do not intersect with each other.

Probability of success $p _ {\ mathrm {A}}$ of the algorithm $\ mathrm {A}$ let's call the calculation probability by this algorithm $\ mathrm {A}$ correct output on arbitrary (but correct) inputs. So, for example, the probability $p _ {\ mathrm {A}}$ success of the algorithm $\ mathrm {A}$ computing the encryption key by $E$ –Pair $\ left \ langle P, C \ right \ rangle$ , there will be a probability

$\ forall P, C \ & gt; \ Longrightarrow \ & gt; p _ {\ mathrm {A}} = \ Pr {\ operatorname {A} \ left [\ left \ langle P, C \ right \ rangle \ right]} = \ underline {K}}.$

Under runtime $T _ {\ mathrm {A}}$ of the algorithm $\ mathrm {A}$ we will understand the number of queries made by this algorithm to oracles $\ mathrm {P}, \ mathrm {P} ^ {- 1}, \ mathrm {E}, \ mathrm {D}$ .

Definition
Function $f (n) \ colon \ mathbb {N} _0 \ mapsto \ left [0, 1 \ right]$ is called polynomially mall (polynomially negligable) if for any polynomial $p (n)$ there is $n_0$ such that for all $n & gt; n_0$ performed $f (n) & lt; 1 / p (n)$ :

$f (n) \ text {is polynomially negligable} \ iff \ exists n_0 \ mid \ forall n & gt; n_0 \ & gt; \ Longrightarrow \ & gt; f (n) & lt; \ frac {1} {p (n)}.$

Definition
Task $\ mathsf {T}$ we call difficult if the probability of success of any algorithm that solves it, which is polynomially limited in time, is polynomially small.

Description of the formal model

In the model proposed in [EM97], the attacker fully has knowledge of the cipher device and the selected substitution $\ pi$ . To open the system, the attacker uses some algorithm $\ mathrm {A}$ which can solve one of two tasks: the decryption task $\ mathsf {CP}$ , or the task of building a new plaintext / ciphertext pair $\ mathsf {EFP}$ .

Decryption Task ( $\ mathsf {CP}$ )

Under the task of decryption (
$\ mathsf {CP}$ , cracking problem ) is understood by the attacker to decrypt some closed text $C_0$ . However, any algorithm $\ mathrm {A}$ used by the attacker to solve the problem, can refer to the oracles $\ mathrm {P}$ , $\ mathrm {P} ^ {- 1}$ , $\ mathrm {E}$ , $\ mathrm {D} '$ where:

(limited to $C_0$ oracle $\ mathrm {D} '$ decrypts everyone $n$ –Dimensional binary set (ciphertext) $C$ , Besides $C_0$ on the key $\ underline {K}$ :

$\ mathrm {D} _ {\ underline {K}, \ pi} '\ colon \ mathcal {C} \ equiv \ mathbb {Z} _ {2} ^ {n} \ mapsto \ mathcal {P} \ equiv \ mathbb {Z} _ {2} ^ {n}, \ quad \ mathrm {D} _ {\ underline {K}, \ pi} '\ left [C \ right] = \ underline {K} _1 \ oplus \ pi ^ {-1} (C \ oplus \ underline {K} _2) \ text {with} C \ neq C_0.$

Algorithm $\ mathrm {A}$ successfully opens the system if $\ operatorname {A} \ left [C_0 \ right]} = D (C_0, \ underline {K})$ .

The task of building a new pair of plaintext / ciphertext ( $\ mathsf {EFP}$ )

Under the task of building a new pair of texts ( $\ mathsf {EFP}$ , existential forgery problem ) understand the problem of building such a pair $\ left \ langle P, C \ right \ rangle$ that would satisfy the ratio $C = E (P, \ underline {K})$ , and it did not consist of a request and response to one of the oracles $\ mathrm {E}, \ mathrm {D}$ . However, any algorithm $\ mathrm {B}$ used by an attacker to solve a problem can access all four oracles $\ mathrm {P}, \ mathrm {P} ^ {- 1}, \ mathrm {E}, \ mathrm {D}$ .

The success of the algorithm $\ mathrm {B}$ it is considered to receive a new correct pair of plain text and ciphertext $\ left \ langle P, C \ right \ rangle$ .

Reduction of the task of constructing a text / ciphertext pair to the task of opening ( $\ mathsf {EFP} \ varpropto \ mathsf {CP}$ )

Theorem 1 (EFP to CP reduction)
Let be $n \ in \ mathbb {N}$ and there is an algorithm $\ mathrm {A}$ solving the task of opening $\ mathrm {CP}$ during $T (n)$ with probability of success $\ xi (n)$ then there is an algorithm $\ mathrm {B}$ building a couple of texts $\ left \ langle P, C \ right \ rangle$ at the same time $T (n)$ with probability of success $\ xi (n) / T (n)$ :

$\ exists \ mathrm {A} \ text {for the solution} \ mathsf {CP} \ mid T _ {\ mathrm {A}} = T (n), \ p _ {\ mathrm {A}} = \ xi (n) \ & gt; \ Longrightarrow \ & gt; \ exists \ mathrm {B} \ text {for the solution} \ mathsf {EFP} \ mid T _ {\ mathrm {B}} \ leq T (n), \ p _ {\ mathrm {B}} = \ frac {\ xi (n)} {T (n)}.$

Evidence

Fix the plaintext $P_0$ key $\ underline {K}$ and ciphertext $C_0 = E (P_0, \ underline {K})$ , and consider the progress of the algorithm $\ operatorname {A} \ left [C_0 \ right]}$ .

Without loss of generality, we can assume that if the algorithm $\ mathrm {A}$ successfully decrypts $C_0$ then at some critical point in time $T '& lt; T (n)$ the execution of this algorithm, the attacker checks the plaintext found, candidate $P_0$ by sending (for the first time) a request to encrypt it to an oracle $\ mathrm {E}$ and comparing the decrypted ciphertext $C_0$ with oracle answer:

$\ operatorname {E_K} \ left [P_0 \ right]} \ stackrel {?} {=} C_0.$

Based on the algorithm $\ mathrm {A}$ let's build an algorithm $\ mathrm {B}$ solving the problem $\ mathsf {EFP}$ :

Fix ciphertext $C_0 \ in \ mathcal {C}$ ;
Let's start the execution of the algorithm $\ operatorname {A} \ left [C_0 \ right]}$ ;
Choose random $\ tau$ evenly distributed on the segment $\ left [1, t (n) \ right]$ ;
Stop the execution of the algorithm $\ operatorname {A} \ left [C_0 \ right]}$ after $\ tau - 1$ requests to oracles;
If in request $\ tau$ algorithm $\ operatorname {A} \ left [C_0 \ right]}$ requests encryption $P '$ , the execution of the algorithm is terminated, and the initial pair is $\ left \ langle P ', C_0 \ right \ rangle$ .

It is easy to see that the algorithm $\ mathrm {B}$ carries no more $T (n)$ requests to oracles $\ mathrm {E}, \ mathrm {D}$ while the desired pair $\ left \ langle P ', C_0 \ right \ rangle$ will be built only if the decryption algorithm $\ mathrm {A}$ successfully decrypts text $C_0$ (with probability $p _ {\ mathrm {A}} = \ xi (n)$ ) and $\ mathrm {A}$ will be stopped at a critical time $T '$ (with probability $1 / T (n)$ ):

$p _ {\ mathrm {B}} = p _ {\ mathrm {A}} \ cdot \ frac {1} {T (n)} = \ frac {\ xi (n)} {T (n)},$

Q.E.D.

Corollary 1.1
Let the task $\ mathsf {EFP}$ difficult (for any polynomial decision algorithm $\ mathrm {B}$ his probability of success $p _ {\ mathrm {B}}$ polynomially small), then the problem $\ mathsf {CP}$ also difficult (for any polynomial decision algorithm $\ mathrm {A}$ his probability of success $p _ {\ mathrm {A}}$ polynomially small).

It should be noted that the converse statement (reducibility $\ mathsf {CP} \ varpropto \ mathsf {EFP}$ ) not true in the general case: in some classes of cryptosystems, there are open texts, such that their corresponding ciphertexts are known in advance and do not depend on the key (for example, $P = 1$ in the RSA scheme).

Durability of the system when using random substitution $\ pi$

The main ideas of proof of persistence are as follows:

show that at any stage of a polynomially limited attack, the set of “good” keys (keys whose truth the attacker neither confirm nor deny on the basis of his data) is exponentially large ( Lemma 1 );
show that the attacker can “guess” the true key $\underline{K}$ only with a polynomially small probability ( Theorem 2 );
show that the attacker collect enough data to identify the true key $\underline{K}$ for the polynomial number of requests to oracles ( Theorem 2 ).

Definition
The first subkey of a $K_1$ key $K = \left\langle K_1, K_2 \right\rangle$ is called bad with respect to the algorithm $\mathrm{A}$ and the sets it has developed. $\mathsf{E}$ and $\mathsf{P}$ if there are a $E$ couple $\left\langle P_i, C_i \right\rangle \in \mathsf{E}$ and $P$ –Pair $\left\langle M_j, \pi(M_j) \right\rangle \in \mathsf{P}$ such that $P_i \oplus K_1 = M_j$ ;and good otherwise:

$K_1 \text{ is a bad key} \iff \exists \left\langle P_i, C_i \right\rangle \in \mathsf{E}, \left\langle M_j, \pi(M_j) \right\rangle \in \mathsf{P} \>\Longrightarrow\> P_i \oplus K_L = M_j.$

In other words, a subkey $K_1$ will be considered good if, based on the material obtained as a result of executing the algorithm, $\mathrm{A}$ it is impossible to determine if the $K_1$ subkey is a true key. $\underline{K}$ .Let us explain this informal definition by the following example: let the subkey $K_1$ be bad, then, according to the definition of a bad subkey, there are a $E$ pair $\left\langle P_i, C_i \right\rangle,$ Where $C_i = E(P_i, \left\langle \underline{K}_1, \underline{K}_2 \right\rangle)$ and $P$ –pair $\left\langle P_i \oplus K_1, \pi (P_i \oplus K_1) \right\rangle$ .Then the key $K = \left\langle K_1, K_2 \right\rangle$ is a candidate for the true key. $\underline{K}$ where

$K_2 = C_i \oplus \left( \pi (P_i \oplus K_1) \right).$

Obviously, such a key $K = \left\langle K_1, K_2 \right\rangle$ satisfies this $E$ –pare, because

$E(P_i, K) = K_2 \oplus \pi (K_1 \oplus P_i) = \big( C_i \oplus (\pi (P_i \oplus K_1))\big) \oplus \pi (K_1 \oplus P_i) = C_i.$

With the help of other collected $E$ –pairs and $P$ –pairs, the attacker has the opportunity to check whether the key constructed in this way is the $K$ true key of the $\underline{K}$ system being opened; and accept (as a subkey $\underline{K}_1$ ), or discard the subkey $K_1$ .

A similar definition can be formulated for the second subkeys. $K_2$ .

The definition of the
second $K_2$ key $K = \left\langle K_1, K_2 \right\rangle$ is called bad relative to the algorithm $\mathrm{A}$ and the sets it has developed $\mathsf{E}$ and $\mathsf{P}$ if there are a $E$ couple $\left\langle P_i, C_i \right\rangle \in \mathsf{E}$ and $P$ –Pair $\left\langle M_j, \pi(M_j) \right\rangle \in \mathsf{P}$ such that $C_i \oplus K_2 = \pi(M_j)$ ;and good otherwise:

$K_2 \text{ — } \iff \exists \left\langle P_i, C_i \right\rangle \in \mathsf{E}, \left\langle M_j, \pi(M_j) \right\rangle \in \mathsf{P} \>\Longrightarrow\> C_i \oplus K_2 = \pi(M_j).$

Definition
Key $K = \left\langle K_1, K_2 \right\rangle$ called good if both are connected $K_1$ and $K_2$ are good and bad in another case.

Statement 2 (True subkeys share goodness)
With a private key $\underline{K} = \left\langle \underline{K}_1, \underline{K}_2 \right\rangle$ and a swap $\ pi$ subkey $\underline{K}_1$ and $\underline{K}_2$ either are both good or bad:

$\underline{K}_1 \text{ is a good key} \iff \underline{K}_2 \text{ is a good key} \quad (\text{when } \underline{K}, \pi \text{ are fixed}).$

Lemma 1 (The fraction of bad keys)
Let the algorithm $\mathrm{A}$ generate sets $\mathsf{E}, \left\vert\,{\mathsf{E}\,\right\vert = l$ and $\mathsf{P}, \left\vert\,{\mathsf{P}\,\right\vert = m$ disjoint $E$ –pairs and $P$ –pairs respectively, then the proportion of $Q$ bad keys in the key space $\mathcal{K}$ does not exceed $2lm / 2^n$ .

Evidence

, $K_1$ , $E$ – $\left\langle P_{i}, C_{i} \right\rangle \in \mathsf{E}$ and $P$ – $\left\langle M_{j}, \pi(M_{j})\right\rangle \in \mathsf{P}$ , ,

$P_{i} \oplus K_1 = M_{j}, \text{ } K_1 = P_{i} \oplus M_{j}.$

, $i, j$ , , $P_{i} \mid 1 \leq i \leq l$ and $M_{j} \mid 1 \leq j \leq m$ , $\left\vert\,\mathsf{E}\,\right\vert \cdot \left\vert\,\mathsf{P} \,\right\vert = l \cdot m$ $K_1$ .

, $K_2$ $lm$ .

$\mathbb{Z}_{2}^{n}$ , :

$\# \left\lbrace K \text{ is a bad key} \right\rbrace \leq lm \cdot 2^n + lm \cdot 2^n = 2 lm 2^n,$

$\mathcal{K} = \mathbb{Z}_2^{2n}$ :

$Q \leq \frac{2 lm 2^n}{2^{2n}} = \frac{2lm}{2^n}.$

Definition
Let be $\sigma$ - substitution from $S_{\left\vert\,\mathcal{P}\,\right\vert}$ , and $K = \left\langle K_1, K_2 \right\rangle$ - some key.
We say that the pair $\left\langle \sigma, K \right\rangle$ satisfies (satisfies) sets of $E$ pairs $\mathsf{E}$ and $P$ –Pair $\mathsf{P}$ if the following conditions are met:

The substitution is $\sigma$ indistinguishable from the true substitution $\ pi$ on the resulting set – $P$ pairs:

$\forall \left\langle M, \pi(M) \right\rangle \in \mathsf{P} \>\Longrightarrow\> \sigma(M) = \pi(m),$

The substitution is $\sigma$ indistinguishable from the true substitution $\ pi$ on the resulting set – $E$ pairs:

$\forall \left\langle P, C \right\rangle \in \mathsf{E} \>\Longrightarrow\> \sigma(P \oplus K_1) = C \oplus K_2.$

The following lemma shows that all good keys are, in a sense, equal candidates for the role of a true encryption key. $\underline{K}$ .

Lemma 2 (Distribution of true key candidates)
Let be $\mathsf{E}, \left\vert\,\mathsf{E}\,\right\vert = l$ and $\mathsf{P}, \left\vert\,\mathsf{P}\,\right\vert = m$ - sets $E$ –pairs and $P$ –pairs, respectively, and $\underline{K}$ a true key, then the probability that a certain key $K_{i} \in \mathcal{K}$ is a secret key $\underline{K}$ is the same for all $i$ :

$\forall i \mid 1 \leq {i} \leq \left\vert\,{\mathcal{K}\,\right\vert \>\Longrightarrow\> \Pr{\left[\underline{K} = K_{i}\right]} = \alpha = \operatorname{const}.$

Evidence

, :

$\forall K_{i} \in \mathcal{K} \>\Longrightarrow\> \Pr{\left[K_{i} = \underline{K}\right]} = \frac{1}{2^{2n}},$

$\ pi$ :

$\forall \sigma_{i} \in S_{\left\vert\,\mathcal{P}\,\right\vert} \>\Longrightarrow\> \Pr{\left[\sigma_{i} = \pi\right]} = \frac{1}{2^n !},$

$\alpha = \Pr{\left[K_{i} = \underline{K} \mid \left\langle \pi, K_{i} \right\rangle \text{ satisfies } \mathsf{E}, \mathsf{P}\right]}.$

$\Pr{\left[K_{i} = \underline{K} \mid \left\langle \pi, K_{i \right\rangle} \text{ satisfies } \mathsf{E}, \mathsf{P}\right]} = \frac { \overbrace{ \Pr{\left[K_{i} = \underline{K}\right]} }^{\operatorname{const}} \cdot \overbrace{ \Pr{\left[\left\langle \pi, K_{i \right\rangle} \text{ satisfies } \mathsf{E}, \mathsf{P} \mid K_{i} = \underline{K}\right]} }^{\beta} } { \underbrace{ \Pr{\left[\left\langle \pi, K_{i} \right\rangle \text{ satisfies } \mathsf{E}, \mathsf{P} \right]} }_{\operatorname{const}} }.$

, $\beta = \operatorname{const}$ .

, $K_{i} = \left\langle K_{i, 1 \right\rangle, K_{i, 2}}$ $E$ – $\mathsf{E}$ $P$ – $\mathsf{P}'$ , $\ pi$ , :

$\forall \underbrace{\left\langle P_{i}, C_{i} \right\rangle}_{E \text{ pair}} \in \mathsf{E} \leadsto \underbrace{\left\langle P_{i} \oplus K_{i, 1}, C_{i} \oplus K_{i, 2} \right\rangle }_{P \text{ pair}} \in \mathsf{P}'.$

, , $\ pi$ , $K_{i}$ $P$ – $\left\langle P_{i} \oplus K_{i, 1}, C_{i} \oplus K_{i, 2} \right\rangle$ , $E$ – $\left\langle P_{i}, C_{i} \right\rangle$ . , $\left\vert\, \mathsf{E} \,\right\vert = \left\vert\,{\mathsf{P}'\,\right\vert$ , $\mathsf{E} \mapsto \mathsf{P}'$ .

, $\beta$ :

$\beta \equiv \Pr{ \left[ \left\langle \pi, K_{i} \right\rangle \text{ satisfies } \mathsf{E}, \mathsf{P} \mid K_{i} = \underline{K} \right] } = \Pr{ \left[ \left\langle \pi, K_{i} \right\rangle \text{ satisfies } \emptyset, \mathsf{P} \cup \mathsf{P}' \mid K_{i} = \underline{K} \right] }$

$K_{i}$ , $P$ – $\mathsf{P}$ and $\mathsf{P}'$ :

$K_i \text{ is a good key} \>\Longrightarrow\> \mathsf{P} \cap \mathsf{P}' = \emptyset.$

$\beta$ , ( ) $\ pi$ $\left\vert\,{\mathsf{E}\,\right\vert + \left\vert\,{\mathsf{P}\,\right\vert = l + m$ . $K_{i}$

$\beta = \Pr{\left[ \pi(M) = M' \mid \left\langle M, M' \right\rangle \in \mathsf{P} \cup \mathsf{P}' \right]} = \frac{\left( 2^n - (l + m) \right) !}{2^n !} = \prod_{j = 0}^{l + m - 1} \frac{1}{2^n - i}.$

, $K_{i}$ , .

Theorem 2 (Boundary Probability for by success of the any $\mathrm{A}$ solving $\mathsf{EFP}$ ) Let substitution $\ pi$ selected at random from $S_{\left\vert\,\mathcal{P}\,\right\vert}$ and the key $\underline{K}$ is chosen at random from $\mathbb{Z}_{2}^{2n}$ , then the probability of success of the algorithm $\mathrm{A}$ that solves the problem $\mathsf{EFP}$ , the following upper bound:

$p_{\mathrm{A}} = \mathcal{O}\!\left(\frac{lm}{2^n}\right),$

Where $l$ - number of requests to oracles $\mathrm{E}$ and $\mathrm{D}$ , and $m$ - the number of requests to the oracles $\mathrm{P}$ and $\mathrm{P}^{-1}$ .

Evidence

, $\mathrm{A}$ , $\mathsf{EFP}$ $\mathsf{E}, \left\vert\,{\mathsf{E}\,\right\vert = l$ and $\mathsf{P}, \left\vert\,{\mathsf{P}\,\right\vert$ $E$ – $P$ – . : $\underline{K}$ , $l + m$ $\mathrm{A}$ «» $\left\langle P, C \right\rangle$ , $\underline{K} \in \mathcal{K}^{(l + m)}$ .

$\mathsf{E}^{(r)}$ and $\mathsf{P}^{(r)}$ sets $E$ – $P$ –, $\mathrm{A}$ $r - 1$ :

$\mathsf{E}^{(r)} \subseteq \mathsf{E},\ \big\lvert \mathsf{E}^{(r)} \big\rvert = l^{(r)} \leq l = \left\vert\,{\mathsf{E}\,\right\vert,\quad \mathsf{P}^{(r)} \subseteq \mathsf{P},\ \big\lvert \mathsf{P}^{(r)} \big\rvert = m^{(r)} \leq m = \left\vert\,{\mathsf{P}\,\right\vert.$

$\mathcal{K}^{(r)}$ , $\mathsf{E}^{(r)}$ and $\mathsf{P}^{(r)}$ . , , :

$\big\lvert \mathcal{K}^{(r)} \big\rvert \geq 2^{2n} - 2 l^{(r)} m^{(r)} 2^n \geq 2^{2n} - 2lm 2^n.$

, $\underline{K}$ ( ). , $\mathrm{A}$ , , $r$ – $\underline{K}$ . , , , .

, $\mathrm{A}$ , $r$ – , , , , $\underline{K}$ ( $\underline{K} \notin \mathcal{K}_{i + 1}$ ):

$\mathrm{E}$ :

Let be $\left\langle P, C \right\rangle$ — $E$ –. :

- $\left\langle P, C \right\rangle \in \mathsf{E}^{(r)}$ , , $\underline{K}$ ;
- $\left\langle P, C \right\rangle \notin \mathsf{E}^{(r)}$ , :

$\mathsf{E}^{(r + 1)} = \mathsf{E}^{(r)} \cup \left\langle P, C \right\rangle; \quad \mathsf{P}^{(r + 1)} = \mathsf{P}^{(r)}.$

$\Delta_{r, r+1} Q_{\mathrm{E}, K}$ , $\left\langle P, C \right\rangle$ . Key $K = \left\langle K_1, K_2 \right\rangle$ , $K_1, K_2$ :

$\big\lvert \mathcal{K}^{(r)} \setminus \mathcal{K}^{(r + 1)} \big\rvert \leq \#{K_1 }$

Number $Q_{K_1}^{(r + 1)}$ $K_1$ ( $r$ ) $P_i \oplus M_j$ , $i$ $E$ – $\mathsf{E}^{(r + 1)}$ , $j$ — $P$ – $\mathsf{P}^{(r + 1)}$ :

$Q_{K_1}^{(r + 1)} = \#\left\lbrace K_1 \text{ is a bad key} \right\rbrace = \#\left\lbrace P_i \oplus M_j \mid \left\langle P_i, C_i \right\rangle \in \mathsf{E}^{(r + 1)}, \left\langle M_j, M_j' \right\rangle \in \mathsf{P}^{(r + 1)} \right\rbrace}.$

$\mathsf{E}^{(r + 1)}$ and $\mathsf{P}^{(r + 1)}$ , :

$Q_{K_1}^{(r + 1)} = Q_{K_1}^{(r)} + \#\left\lbrace P \oplus M_j \provided \left\langle M_j, M_j' \right\rbrace \in \mathsf{P}^{(r) \right\rangle} \leq Q_{K_1}^{(r)} + m.$

, $K_2$ $Q_{K_2}^{(r)} + m$ :

$Q_{K_2}^{(r + 1)} = Q_{K_2}^{(r)} + \#\left\lbrace C \oplus M_j' \provided \left\langle M_j, M_j' \right\rbrace \in \mathsf{P}^{(r) \right\rangle} \leq Q_{K_2}^{(r)} + m.$

$Q_K^{(r + 1)}$ $K$ $r$ :

$Q_K^{(r + 1)} \leq Q_{K_1}^{(r + 1)} \cdot 2^n + 2^n \cdot Q_{K_2}^{(r + 1)} = Q_K^{(r)} + 2 m 2^n,$

$\Delta_{r, r+1} Q_{\mathrm{E}, K} = Q_K^{(r + 1)} - Q_K^{(r)} \leq 2 m 2^n.$

, ( ) $\underline{K}$ $\Delta_{r, r+1} Q_{\mathrm{E}, K}$ , ( $\mathrm{E}$ ),

$\Pr{\left[ \underline{K} \in \mathcal{K}^{(r)} \setminus \mathcal{K}^{(r + 1)} \mid \left\langle P, C \right\rangle \right]} = \frac{ \Delta_{r, r+1} Q_{\mathrm{E}, K} }{ Q_K^{(r)} } \leq \frac{2m}{2^n - 2lm} .$

$\mathrm{D$

$\mathrm{E}$ , , $\underline{K}$ ( $\mathrm{D}$ ),

$\Pr{\left[ \underline{K} \in \mathcal{K}^{(r)} \setminus \mathcal{K}^{(r + 1)} \mid \left\langle P, C \right\rangle \right]} = \frac{ \Delta_{r, r+1} Q_{\mathrm{D}, K} }{ Q_K^{(r)} } \leq \frac{2m}{2^n - 2lm} .$

$\mathrm{P}$

Let be $\left\langle M, M' \right\rangle$ — $P$ –. :

- $\left\langle M, M' \right\rangle \in \mathsf{P}^{(r)}$ , , $\underline{K}$ ;
- $\left\langle M, M' \right\rangle \notin \mathsf{P}^{(r)}$ , :

$\mathsf{E}^{(r + 1)} = \mathsf{E}^{(r)}; \quad \mathsf{P}^{(r + 1)} = \mathsf{P}^{(r)} \cup \left\langle M, M' \right\rangle.$

$\Delta_{r, r+1} Q_{\mathrm{P}, K}$ , $\left\langle M, M' \right\rangle$ .

Number $Q_{K_1}^{(r + 1)}$ $K_1$ ( $r$ ) $P_i \oplus M_j$ , $i$ $E$ – $\mathsf{E}^{(r + 1)}$ , $j$ — $P$ – $\mathsf{P}^{(r + 1)}$ :

$\mathsf{E}^{(r + 1)}$ and $\mathsf{P}^{(r + 1)}$ , :

$Q_{K_1}^{(r + 1)} = Q_{K_1}^{(r)} + \#\left\lbrace P_i \oplus M \mid \left\langle P_i, C_i \right\rangle \in \mathsf{E}^{(r)} \right\rbrace \leq Q_{K_1}^{(r)} + l.$

, $K_2$ $Q_{K_2}^{(r)} + l$ :

$Q_{K_2}^{(r + 1)} = Q_{K_2}^{(r)} + \#\left\lbrace C \oplus M_j' \mid \left\langle M_j, M_j' \right\rangle \in \mathsf{P}^{(r)} \right\rbrace \leq Q_{K_2}^{(r)} + m.$

$Q_K^{(r + 1)}$ $K$ $r$ :

$Q_K^{(r + 1)} \leq Q_{K_1}^{(r + 1)} \cdot 2^n + 2^n \cdot Q_{K_2}^{(r + 1)} = Q_K^{(r)} + 2 l 2^n,$

$\Delta_{r, r+1} Q_{\mathrm{P}, K} = Q_K^{(r + 1)} - Q_K^{(r)} \leq 2 l 2^n.$

, ( ) $\underline{K}$ $\Delta_{r, r+1} Q_{\mathrm{P}, K}$ , ( $\mathrm{P}$ ),

$\Pr{\left[ \underline{K} \in \mathcal{K}^{(r)} \setminus \mathcal{K}^{(r + 1)} \mid \left\langle M, M' \right\rangle \right]} = \frac{\Delta_{r, r+1} Q_{\mathrm{P}, K}}{Q_K^{(r)}} \leq \frac{2l}{2^n - 2lm}.$

$\mathrm{P^{-1}}$ .

$\mathrm{P}$ , , $\underline{K}$ ( $\mathrm{P}^{-1}$ ),

$\Pr{\underline{K} \in \mathcal{K}^{(r)} \setminus \mathcal{K}^{(r + 1)} \provided \left\langle M, M' \right\rangle} = \frac{\Delta_{r, r+1} Q_{\mathrm{P}^{-1}, K}}{Q_K^{(r)}} \leq \frac{2l}{2^n - 2lm}.$

:
$E$ – $\left\langle P, C \right\rangle$ , $r$ , , $\underline{K}$ , , $2m / (2^n - 2lm)$ , $\underline{K}$ $l$ ( $l = \left\vert\,\mathsf{E}\,\right\vert$ ), $2lm / (2^n - 2lm)$ .

, $\underline{K}$ $m$ $\mathrm{P},$ $\mathrm{P}^{-1}$ , $2lm / (2^n - 2lm)$ . , $\underline{K}$ $\mathrm{A}$ :

$\Pr{\underline{K} \in \mathcal{K} \setminus \mathcal{K}^{(l + m)}} \leq \frac{4lm}{2^n - 2lm}.$

$\mathrm{A}$ «» $E$ – $\left\langle P, C \right\rangle$ :

$\pi(P \oplus \underline{K}_1) \oplus \underline{K}_2 = C$

$l + m$ , $\underline{K}$ — $\mathsf{E} \cup \left\langle P, C \right\rangle$ and $\mathsf{P}$ . , $P$ – $\mathsf{P}$ $\left\langle M, M' \right\rangle$ , $P \oplus \underline{K}_1 = M$ or $C \oplus \underline{K}_2 = M'$ .

, $\ pi$ $P \oplus \underline{K}_1$ $P$ – $\mathsf{P}$ , $\underline{K}$ $E$ – , «» $\left\langle P, C \right\rangle$ — . , $\pi(P \oplus \underline{K}_1)$ $2^n - (m + l)$ «»,

$\Pr{\left[ \pi(P \oplus \underline{K}_1) = C \oplus \underline{K}_2 \right]} = \frac{1}{2^n - (m + l)} = \mathcal{O}\!\left(\frac{lm}{2^n}\right).$

$p_{\mathrm{A}}$ $\mathrm{A}$ :

$p_{\mathrm{A}} \leq \frac{4lm}{2^n - 2lm} + \frac{1}{2^n - (m + l)} = \bigo{\frac{lm}{2^n}},$

Corollary 2.1.
Let the permutation be $\ pi$ chosen randomly from $S_{\left\vert\,\mathcal{P}\,\right\vert}$ , then the probability of success of any algorithm $\mathrm{A}$ solving the problem $\mathsf{EFP}$ and polynomially limited in the number of queries to oracles is $\mathrm{P},$ $\mathrm{P}^{-1},$ $\mathrm{E},$ $\mathrm{D},$ polynomial small.

Durability of the system using pseudo-random substitution $\ pi$

The cipher proposed in [EM97] retains the shown crypto resistance property even if the substitution is $\ pi$ chosen pseudo-randomly.

To prove this statement, it suffices to clarify the concept of a pseudo-random permutation.

Definition
Let be $\sigma$ - random substitution, and $\delta$ - some substitution, selected from $S_{\left\vert\,\mathcal{P}\,\right\vert}$ according to some non-uniform distribution law, and $\mathrm{P}_{\sigma}$ and $\mathrm{P}_{\delta}$ - implementing their oracles. We will say that a $\delta$ pseudo-random permutation if there is no polynomial query-limited algorithm that distinguishes oracles $\mathrm{P}_{\sigma}$ and $\mathrm{P}_{\delta}$ .

In other words, in the presented computation model with oracles, the pseudo-random substitution is indistinguishable from the random one. Therefore, the following theorem holds.

Theorem 3
Let the permutation be $\ pi$ chosen pseudo-randomly from $S_{\left\vert\,{\mathcal{P}\,\right\vert}$ , then the probability of success of any algorithm $\mathrm{A}$ that solves the problem $\mathsf{EFP}$ and is polynomially limited in the number of queries to oracles is $\mathrm{P},$ $\mathrm{P}^{-1},$ $\mathrm{E},$ $\mathrm{D},$ polynomial small.

In continuation

Yes, there is gunpowder in the old dog yet. If there are people interested in Habré, then in the next part I can consider modifications of this classical scheme, and various cryptographic attacks on it (which, by the way, show that the obtained estimate from the bottom is accurate and cannot be improved).

Bibliography

For those who are very interested in:

Eli Biham, Yaniv Carmeli, Itai Dinur, Orr Dunkelman, Nathan Keller, and Adi Shamir. Cryptanalysis of iterated Even-Mansour schemes with two keys. IACR Cryptology ePrint Archive, 2013:674, 2013.
Andrey Bogdanov, Lars R Knudsen, Gregor Leander, Francois-Xavier Standaert, John Steinberger, and Elmar Tischhauser. Key-alternating ciphers in a provable setting: Encryption using a small number of public permutations. In Advances in Cryptology–EUROCRYPT 2012, pages 45–62. Springer, 2012.
Alex Biryukov and David Wagner. Advanced slide attacks. In Advances in Cryptology—EUROCRYPT 2000, pages 589–606. Springer, 2000.
Shan Chen, Rodolphe Lampe, Jooyoung Lee, Yannick Seurin, and John Steinberger. Minimizing the two-round Even-Mansour cipher. In Advances in Cryptology–CRYPTO 2014, pages 39–56. Springer, 2014.
Joan Daemen. Limitations of the Even-Mansour construction. In Advances in Cryptology—ASIACRYPT'91, pages 495–498. Springer, 1993.
Itai Dinur, Orr Dunkelman, Nathan Keller, and Adi Shamir. Key recovery attacks on 3-round Even-Mansour, 8-step LED-128, and full AES2. In Advances in Cryptology-ASIACRYPT 2013, pages 337–356. Springer, 2013.
Orr Dunkelman, Nathan Keller, and Adi Shamir. Minimalism in cryptography: The Even-Mansour scheme revisited. In Advances in Cryptology–EUROCRYPT 2012, pages 336–354. Springer, 2012.
[EM97] Shimon Even and Yishay Mansour. A construction of a cipher from a single pseudorandom permutation. Journal of Cryptology, 10(3):151– 161, 1997.
Shoni Gilboa and Shay Gueron. Balanced permutations even-mansour ciphers. arXiv preprint arXiv:1409.0421, 2014.
Philip Hawkes and Luke O'Connor. Xor and non-xor differential probabilities. In Advances in Cryptology—EUROCRYPT'99, pages 272–285. Springer, 1999.
Nicky Mouha and Atul Luykx. Multi-key security: The Even-Mansour construction revisited. Technical report, Cryptology ePrint Archive, Report 2015/101, 2015.
Ivica Nikolic, Lei Wang, and Shuang Wu. Cryptanalysis of round-reduced LED. In Shiho Moriai, editor, Fast Software Encryption, volume 8424 of Lecture Notes in Computer Science, pages 112–129. Springer Berlin Heidelberg, 2014.

PS A part of this publication was written in TeX, while the layout on Habré could appear jambs, mainly in formulas. If you notice - please, fix it.

EDIT 1. Corrected the names of scientists, thanks alexyr .

Source: https://habr.com/ru/post/265607/

All Articles

Minimalism in cryptography, or the Even – Mansour scheme

Lyrical digression

Sets, sets

Inscriptions

Legend

Definitions

Classical Even – Mansour scheme

Description

About minimal scheme

About circuit durability

Assumptions of persistence, determination

Description of the formal model

Decryption Task ( )

The task of building a new pair of plaintext / ciphertext ( )

Reduction of the task of constructing a text / ciphertext pair to the task of opening ( )

Durability of the system when using random substitution

Durability of the system using pseudo-random substitution

In continuation

Bibliography

More articles:

Decryption Task ( $\ mathsf {CP}$ )

The task of building a new pair of plaintext / ciphertext ( $\ mathsf {EFP}$ )

Reduction of the task of constructing a text / ciphertext pair to the task of opening ( $\ mathsf {EFP} \ varpropto \ mathsf {CP}$ )

Durability of the system when using random substitution $\ pi$

Durability of the system using pseudo-random substitution $\ pi$