a few questions regrading the recitation

a few questions regrading the recitation

eilon (guest) 24 Feb 2017 12:41

1.in recitation 3 slide 7 a definiton for epsilon-indistinguishable is presented,
is it equivalent to the following definiton ?
let d be choosen randomly from D0 union D1
P[A(d) gives the right answer (A answers D0 or D1)] <= 0.5 + epsilon

2. in recitation 7, slide 11 security for muliple encryptions is proven.
the adversary A2 in this proof tries to distinguish between two vectors of encrypted msgs.
as part of the proof, there is another adversary A1 who is trying to distinguish between two encrypted msgs ,
to do so he calls for A2.
according to the proof presented in the recitation A1 can compute the encryption of a given msg - this makes no sense to me,
since if A1 could compute the encryption of a single msg, he could always distinguish between two encrypted msgs. (without calling A2)

Re: a few questions regrading the recitation

oritmosk 25 Feb 2017 08:47

1. Yes
2. Note that this is a public key encryption, so the encryption key is known and he can compute the encryption of the message.
This does not mean he can distinguish between two encryptions of m_0, m_1. A public key encryption must be randomized, so two encryptions of m_0 will have two different results.
If a PKE were deterministic, then it wouldn't be secure (because then the adversary could distinguish between E(m_0) and E(m_1))