Spring 2005 - Home exercise #3
Instructor: Dr.
Erez Petrank, T.A.: Benny Appelbaum
To be delivered on sunday 5/6/2003 in Erez's mailbox.
Question 1:
Consider the following private key encryption scheme. It is based
on a pseudo random generator G which expands seeds of
length
n
into pseudo random strings of length p(n):
- The key generator K(1^n) tosses n
coins
uniformly
and independently at random to produce the output key s.
- The Encryption algorithm E(m) on a message of
length p(n)
computes G(s) and bit-wise xors it with the message m.
Namely, E(m)=m xor G(s).
- The decryption algorithm is equivalent to the encryption
algorithm: D(c)=c xor G(s).
The output of the generator is used only once for encryption. To
encrypt many messages, modify the above scheme so that the generator
produces
a string of length p(n) which is longer than the length
of
all messages (so now the length of each message is shorter than the
expansion
p(n) ). In this scheme, one uses separate parts of the
pseudo
random string to encrypt each of the messages. Assume that $p(n)$
is greater or equal to the number of bits in all messages. The first
message
is encrypted with the beginning of the pseudo random string, and the
bits
used are then marked "used". The second message is encrypted with
the beginning part of the unused bits in the pseudo random
string.
The bits used for the encryption are then marked used, and so
forth.
Which of these claims hold?
- This encryption scheme is robust in the sense of
indistinguishability
to
a passive attack?
- This encryption scheme is robust in the sense of
indistinguishability
to
a chosen plaintext attack?
- This encryption scheme is robust in the sense of
indistinguishability
to
a non-adaptive chosen ciphertext attack (CCA1)?
- This encryption scheme is robust in the sense of
indistinguishability
to
a adaptive chosen ciphertext attack (CCA2)?
Note that during the attack an oracle for encryption or decryption
follows
the same rule: a bit of the output of the generator is used only once
(either
for the requested decryptions/encryptions or for the challenge).
Prove the claim with the highest index that is true. If Claim
4 is not true and you have proven claim number i, show that claim
number
i+1 is not true.
Question 2:
Prove that the Blum-Goldwasser probabilistic public key encryption is
vulnerable
(in a very strong sense) to adaptive chosen ciphertext attack (CCA2).
Question 3:
Propose a modification of the definition of security in the sense of
indistinguishability so that the algorithms are not given the length of
the
plaintext. Prove that in such a case there exists no
secure
encryption schemes.
Guideline: first show that for
some polynomial p, |E(1n)| < p(n)
always holds, whereas for some x in {0,1}p(n) it must hold
that Pr[ |E(x)| < p(n) ] < 1/2 .
Question 4 :
Let (G,E,D) and (G',E',D') be two encryption schemes, i.e., the
algorithms are efficient and satisfy Dk(Ek(x))=x, for all
x's and k's. Suppose we know that one of them is (semantically) secure.
Is the composition of the two encryption schemes still semantically secure?
Answer this question first for the CCA1 attack model and then for the CCA2
attack model. Does it make a difference is the weak scheme is invoked
first or second in the composition?