0368.4162: Introduction to Cryptography Ran Canetti Lecture 5
05 December 2008
1. Warm-up theorem: Indistinguishably under multiple samples. 2. Block Ciphers.
3. Pseudo-random permutations/functions.
Copyright By PowCoder代写 加微信 powcoder
4. Feistel transform (from PRF to PRP).
1 Warm-up theorem: Indistinguishably under multiple samples. Definition 1:
Two ensembles D1 = {Dn1 }n∈N and D2 = {Dn2 }n∈N , are indistinguishable in polynomial time if for every probabilistic polynomial-time algorithm A
P robx∈Dn1 [A(1n, x) = 1] − P robx∈Dn2 [A(1n, x) = 1] < ν(n) for some negligible function ν(n).
Let D1, D2 be two indistinguishable ensembles, and consider a distinguisher A that has access to a box D that,oneachpressofabutton,transmitsavaluethatistakenfromdistributionD.
Figure1: OracleD
Definition 2:
For a distribution ensemble D={Dn}n∈N let ADn (1n) denote the output of A, having input 1n and access to the box Dn . Let AD denote the ensemble {ADn (1n)}n∈N .
Theorem 1: If D1≈cD2 then for any polynomial-time adversary A, AD1 ≈ AD2 . Remark 1: WLOG, we can restrict attention to A’s that output one bit.
(Exercise: Prove that no generality is lost here.)
Remark 2: Let D1, D2 be distribution ensembles over {0,1}. Then D1≈cD2 iff D1≈sD2.
Proof of theorem 1: We prove theorem 1 using the hybrids technique. Let q(n) (n ∈ N) be the number of samples that A receives. Definitely, q(n) is bounded by the run-time of A and, therefore, q(n) is polynomial in n. Let E = ε(t) be a distinguishing difference of A.
Scribes: S. Nemzer, A. Porat
Define experiment Ei ( the "i-th hybrid" ) : The first i queries by A are answered according to D1, and the rest of the queries are answered according to D2.
Let Hi be the probability that A outputs 1 in Ei.
By definition, E0 describes the interaction of ADn1 and Eq describes the interaction of ADn2 . So,wehaveHq -H0 >E.Thismeansthatthereisani,whereHi+1 −Hi ≥ Eq.
We will use this observation as follows: Given n and A such that Prob[AD1 ] – Prob[AD2 ] > E , we construct A′ such that P robx←D1 [A′(x) = 1] − P robx←D2 [A′(x) = 1] > Eq .
Construction of A′: On input x,
– Choose i ∈ {1..q}
– run A as follows:
– for j
The main observation is that:
– if x is drawn from D1, then A sees experiment Ei.
– if x is drawn from D2, then A sees experiment Ei−1. More precisely, we have:
P robx←D1 [A′(x) = 1] − P robx←D2 [A′(x) = 1] =
= qi=1(P robx←D1 [A′(x) = 1 i = i0] · P rob[i = i0]− P robx←D2 [A′(x) = 1 i = i0] · P rob[i = i0]) =
1q ·qi=1(Hi −Hi−1)= 1q ·(Hq −H0)≥ Eq
We got an algorithm A′ that can distinguish between D1 and D2 at probability greater then E, in
contradiction to the assumption.
2 Block Ciphers
Figure2: BlockCipher
In lecture 3 we have seen how stream ciphers are used to encrypt messages between parties that have a shared key. However, stream ciphers have a significant usability drawback: The parties need to keep local state for encryption and decryption. Moreover, the states of the sender and receiver need to be perfectly synchronized. This is problematic in many cases, e.g when the receiver is not always on line, or, when information packets get out of order ( or might get lost). In such cases (and others) it is convenient to allow for “stateless” encryption and decryption, where the encryption process depends only on the ciphertext and the key. A block cipher provides this functionality.
Definition 3:
A block cipher is a keyed invertible permutation, namely a family of functions Pk :{0,1}a ×{0,1}n →{0,1}n,
where for any k, k ∈ {0, 1}a, P (k, •) is a permutation on {0, 1}n.
An alternative notation is: P a,n = {Pk }k∈{0,1}n .
The usability requirements are:
1. Pk is a permutation on {0, 1}n .
2. There exists a polynomial-time algorithms, that efficiently computes Pk and P−1. k
In order to “encrypt” message m with key k we compute “cipher” c = Pk(m). To “decrypt”, we compute m = P−1(c).
What are the security specifications of P?
Unlike the case of stream ciphers, where the security specification were that the output is indistin- guishable from a random string, here we require that P “looks like” a random function (in fact, a random permutation on {0, 1}n ). (See figure 2)
3 Pseudo-random permutations/functions Definition 4:
A family of functions P a,n is ε(t)- pseudo random permutation (PRP) if for any adversary A that runs at time t:
|Probk∈{0,1}a[APk =1]−ProbP∈Pn[AP =1]|
1. OWF->PRG (Already proven at the last lecture) 2. PRG->PRF (We will prove today)
3. PRF->PRP (We will prove at the next lecture) 4. PRP->SPRP (will not see in class)
Theorem 3 ([Goldreich, Goldwasser, Micali 1985] – GGM:)
If there exists pseudo random generators then there exists pseudo random functions (PRG->PRF).
Proof for theorem 3:
We will show now how to construct a pseudo random function from pseudo random generator. Let G be a pseudo random generator that expands input of length n into input of length 2n.
G : {0,1}n → {0,1}2n
We Denote by G0(x) the first n bits of G(x) and by G1(x) the last n bits of G(x).
G(x) = G0(x), G1(x)
First attempt:
Given a generator G:{0, 1}n → {0, 1}2n and an input x=x1 , …, xn . A first attempt to build a pseudo random function might go as follows:
F (x) = G1(…(G1(G1(k)))…),
In words, run G(k) x times each time on the last n bits of the result of G, (figuratively, we will get an
output of size 2n ∗ n) and return the n bits at index x of the output. There are two main flaws at this implementation.
is pseudo random if for any polynomial adversary A and for large
Figure3:FGGM Tree
The first one is that computation of the PRF is not efficient, the complexity time will take 2n for input of size n. The second flaw is that it is not clear whether exponential number of activations of the generator keeps the output pseudo-random.
Second attempt:
We define a function F GGM :{0, 1}n → {0, 1}n
k 1 n xn x2 x1
FGGM(x ,…,x ) = G (…(G (G
Basically, we can look at the function F GGM as n-steps walk down on a full binary tree of depth n.
Each choice for left or right is decided by the value of the bit xi (see figure 3).
For example, at the root of the tree if x1 = 0 then f will choose left, otherwise right.
To show that FGGM is a PRP, we will use a reduction to the warm up theorem using the hybrid technique. Specifically, we will use a hybrid tree where the first i levels (from the root) will be chosen uniformly and the i+1…n last level will be computed using the function F GGM . More precisely, for every k1 , …, k2i ∈ {0, 1}n we define the function F GGM : {0, 1}n → {0, 1}n such that
k1 ,…,k2i
FGGM (x ,…,x )=G (…(G (k ))…)
k1 ,…,k2i i+1 n xn xi x1 ,…,xi
Now, given an distinguisher A for F GGM , we construct a distinguisher A′ for the underlying PRG G. (In fact, using the warm-up theorem, A′ will obtain multiple samples of either G(Un) or U2n and will use A to tell which is the case.) A’ will run A on an interaction that will look to A like an interaction with a hybrid tree. The level i of the switch in the tree will depend on whether A gets samples from G(Un) or from U2n.
We are ready to move to the actual proof of security.
Lets assume by contradiction that there exist an adversary A that can distinguish between the ensem-
ble FGGM and the ensemble Fn,n.
FGGM n F n
|Probk∈{0,1}n[A k (1 )=1]−ProbF∈Fn,n[A (1 )=1]|>ε 5
A gets input from oracle O.
We define experiment Ei:
On the first i levels A walks down on the tree randomly. Actually, since the values of the first i levels are randomly selected it is not important what is the exact path on these levels. At each node of these first i levels A sees random values and ignores them.
From levels i to n A generates G(x) on each level, and walks down the tree as described at F GGM . Let Ei be the following experiment:
1. Randomlychoosek0,…,k2i−1
2. Oninputx1,…,xn returnFGGM (xi+1,…,xn)
k1 ,…,k2i
E is exactly the experimentAF GGM (1n ) where F GGM is taken from F GGM .
En is exactly the experiment AF (1n ) where F is taken from F n,n
Let Hi be the probability that A outputs 1 in Ei.
H is the probability that AF GGM (1n ) outputs 1 where F GGM is taken from F GGM . 0kk
Hn is the probability that AF (1n) outputs 1, where F is taken from Fn,n.
Given adversary A, we will build A′ that speaks with an oracle O which gives samples from distribu-
tions G(Un) or U2n.
In order to keep on consistency of two different queries of prefixes at size i, we will use a memory M
which holds the intermediate values for the length-i prefixes of all the queries so far. A′:
• Answer each oracle query of A as follows:
• Choose randomly i from 1 to n.
• Iftheentry(x1,…,xi,k)existsinMreturnFGGM(xi+1,…,xn) k
•Otherwise,takesamples,s,M←M(x,…,x,s )andreturnFGGM(x ,…,x) 01 1ixi sxii+1n
• Whenever A outputs a value, output the same value.
If A′ receives sample from U2n then A sees exactly the experiment Ei
If A′ receives sample from G(Un) then A sees exactly the experiment Ei−1.
|Probx∈G(Un)[A′(x) = 1] − Probx∈U2n [A′(x) = 1]| =
= ni=1[P robk∈{0,1}n [AFk (1n) = 1|j = i]] · P rob[j = i]− ni=1[ProbF∈Fn,n[AF(1n)=1|j =i]]·Prob[j =i]= =1/n∗ni=1(|Hi−1 −Hi|)=1/n∗(Hn −H0)>ε/n
Using the warm up theorem, we get a contradiction with the assumption that G is a PRG. 6
Figure 4: Feistel
4 Feistel transform (from PRF to PRP):
How can we obtain a PRP from a PRF? In fact, how to obtain a permutation from a PRF, regardless of security? By definition, a PRF look completely unstructured so how to regain the permutation structure? since almost impossible by definition…
Still, there is a simple method to do so, and the price is doubling the input length. This is called the Feistel ladder:
F EF (l, r) = (r, l ⊕ F (r)) or F EF (l, r) = (r, l ⊕ F (r)). (see figure 4) Generally we can define F EFk (lk−1, rk−1) = (rk−1, lk−1 ⊕ Fk−1(rk−1)).
Where Fk is taken from a PRF family F. Each iteration of the Feistel transform uses a fresh function F chosen from the family.
Main observation, F E−1(l, r) = (r ⊕ F (l), l). F
This means that F EF (l, r) is an efficiently reversible permutation, regardless of F.
A Feistel transform is used in the construction of block ciphers, it is named after the BM cryptographer , who was one of the inventors of DES. Indeed, this structure is used there, as we will see later.
Is the Feistel permutation is a PRP (assuming the F is PRF)?
Certainly not… given (l′, r′) such that F EF1 (l, r) = (l′, r′) we can easily find (l,r). This definitely won’t happen with random permutation RP(l,r).
How about a two-step Feistel?
F e2 ( l , r )
r1 = l0 ⊕ F0(r0).
r2 = l1 ⊕ F1(r1).
Note that the two applications of F have independent keys.
Attack: Pick l, l′, r at random, set x=(l,r) and x′=(l′, r), ask for O(x) and O(x′), and obtain answers (l2,r2)and(l2′,r2′).NotethatifOisaFeistel,thenl2⊕l2′ =l⊕′.IfOisarandompermutationthen this happens only with negligible probability.
Next week we will see what happens with F EF3 .
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com