[ Pobierz całość w formacie PDF ]
Fast Software Encryption 2003, volume 2887 of LNCS. Springer, 2003, pp. 307 329.
[17] E. Biham and J. Seberry, Py (roo): A fast and secure stream cipher using rolling arrays, IACR Cryptology ePrint Archive, vol. 2005,
p. 155, 2005.
APPENDIX
A. swrECB
Proof of theorem 3: Let G1 be the multiset of windows involved during encryption and updating
oracle accesses and let G2 be the multiset of the l windows involved during the encryption of the challenge.
Let D1 be the event that the windows of G2 are distinct from the windows of G1, and let D2 be the event
that the windows of G2 are all distinct. For simplicity, we also define S to be the event of success of A in
the game ExptI-CPA(A, k).
¨,FG
Let us now consider the event D = D1 )" D2. When the event D occurs, the challenge ciphertext is
obtained by evaluating l times the random function to distinct and new points, new in the sense that
they have not appeared during queries. Thus, the corresponding outputs of the random function are l new
random draws from {0, 1}8N. By XORing such a random value with a plaintext block of the challenge,
we obtain a ciphered block which is still a new random draw. The l ciphered blocks of the challenge are
then independently and identically distributed over {0, 1}8N. Besides, this distribution is independent of the
previous ciphered blocks obtained during queries. Consequently, the adversary can at best make a random
guess. We have Pr(S | D) = 1/2 and it follows that
1 1
|Pr(S) - 1/2| d" Pr(S | D) - Pr(D) d" Pr(D).
2 2
Before continuing, consider the windows (wi)i=1...n in the same ciphertext, the probability that wi = wi+k
for all i, k > 0 is exactly 1/2ed. In other words, the fact that two windows within a same ciphertext share
a common (but shifted) sequence of randomizers or not, the probability that they collide is still the same.
Now it remains to estimate the probability of occurrence of the event D:
c e1
" Let us denote (wi )i=1...l the windows used in the challenge ciphertext. Let us denote (wi )i=1...n ,
1
eqe
e2 u1
(wi )i=1...n , ..., (wi )i=1...n the windows used during encryption queries and (wi )i=1...2d-1,
2 qe
uqinc
u2
(wi )i=1...2d-1, ..., (wi )i=1...2d-1 the windows used during update queries. We assume update
queries of type replacement or insertion (only) since they bring more information to the adversary.
ej
c
For i " 1, l , j " 1, qe and k " 1, nj let us denote the event dijk = {wi = wk } and for i " 1, l ,
e
uj
c
j " 1, qinc and k " 1, 2d - 1 let us denote the event dijk = {wi = wk }. The event D1 is included
u
ëø öø
íø øø.
in dijk dijk We therefore have
e u
i=1...l j=1...qe k=1...nj j=1...qinc k=1...2d-1
lµ"
Pr(D1) d"
2ed
qe
where µ" = ni + qinc(2d - 1). The contribution qinc(2d - 1) corresponds to the most favourable
i=1
update queries for the adversary (insertion or replacement only).
23
c c
" We define the event dij = {wi = wj} for all i, j " 1, l with i = j. The event D2 being included in
2
dij, we can subsequently upper bound its probability of occurence as follows:
2
i=1...l j=i+1...l
l l
1 l(l - 1)
Pr(D2) d" d" .
2ed 2ed+1
i=1 j=i+1
Proof of theorem 4: Now let us consider the update secrecy game. Deletions at a same location being
obviously indistinguishable, the adversary will return in the find phase operations of type insertion or
replacement.
Let us now consider the guess phase. Notice that when the challenger applies one of the two operations
on the ciphertext, a certain amount (at most 2(d - 1)) of adjacent ciphered blocks change while the
corresponding plaintext blocks are unchanged. It is important to make clear that this is only due to the
changing of the 2(d - 1) adjacent input windows to the random function. Indeed, considering a challenge
"
update of type (insert, i, P ), the returned updated ciphertext C contains at most 2d - 1 new windows.
One of them, w , serves to cipher the inserted block and we call the other ones the adjacents . Let Gu be
the multiset of windows of G1 augmented by the new adjacent windows (wj)j=i-d+1...i and (wj)j=i+1...d-1.
We denote Du the event that w is distinct from the windows of Gu.
Now, let us consider the event Du. When the event Du occurs, whatever the operation choosed by the
challenger is, this new ciphered block is indistinguishable from a new random draw from {0, 1}8N. This is
due to the fact that the output of the random function is really a new random draw, and not a reused one. Just
as in the previous proof, by denoting again S the event of success of A in the game ExptIM-CPA(A, k),
¨,FG
we have
1
|Pr(S) - 1/2| d" Pr(Du)
2
"
We fix an arbitrary order for the elements of Gu, that is to say, we write Gu = (wi)i=1...u +2(d-1). We
"
denote di the event that w = wi for i " 1, u" + 2(d - 1) . The events (di)i=1...u +2(d-1) are not mutually
exclusive, but we can upper bound the probability of occurence of Du as follows:
µ" + 2(d - 1)
Pr(Du) d" .
2ed
Why regenerate all the random blocks in the window w : Taking the example of a replace op-
eration, assume that we do not regenerate all of them but only one, the first one. Consider the value
w = ri ri+1 . . . ri+d-1 before an update and the corresponding value w = ri ri+1 . . . ri+d-1 after an
update. The probability that w equals w is exactly 1/2e. In this case update queries are more advantageous
for the adversary than encryption queries and annihilates the indistinguishability of the scheme. We conclude
that all the random blocks that serve to encrypt the inserted (or replacement block) need to be regenerated,
implying a change in the 2(d - 1) adjacent windows. This leads to the reencryption of 2(d - 1) unchanged
plaintext blocks, a necessary overhead of encryption.
B. mcXOR
Stochastic processes background: Let X1, X2, ... be i.i.d. random variables drawn according to
T
[ Pobierz całość w formacie PDF ]