Let ?1 = (Gen1, Enc1, Dec1) and ?2 = (Gen2, Enc2, Dec2) be two secret-key encryp

Question

Let ?1 = (Gen1, Enc1, Dec1) and ?2 = (Gen2, Enc2, Dec2) be two secret-key encryption schemes. We know that one of them is IND-CPA secure. But we don’t know which. Nevertheless, show that we can combine the two schemes to construct a secret key encryption scheme ? = (Gen, Enc, Dec) that is definitely IND-CPA secure. You do not need to give a full proof of your scheme, but you need to justify why you think it is IND-CPA secure. (See the bonus question if you want to give a proof.)

Hint: Instead of trying to directly encrypt a message m, think about how to generate two messages m1 and m2, such that, given both of them, m can be reconstructed, but any one of them reveals no information about m.

And this is technically a sub-question:

Give a full proof that the encryption scheme you designed above is indeed IND-CPA secure. That is, if one of ?1 and ?2 is IND-CPA secure, then your scheme ? is IND-CPA secure.

Hint: For both b = 1 and b = 2, give a security reduction that if there is an adversary B breaking IND-CPA security of ? with high advantage, then there is an adversary A breaking the IND-CPA security of ?b with high advantage. These two security reductions are very similar.

Explanation / Answer

Hi below i have explained the theorem for IND-CPA secure , please understand the concept of the theorem.

To see that the scheme is IND-CPA secure, notice that thanks to the VBB property one can replace the public key P with an obfuscated version of P without the adversary noticing. Then, for every m, Enc(pk, m) = P, so in the ideal world (where the simulator only has oracle access to them) the ciphertexts contain no information at all about the messages. A formal argument follows. Proof. We prove the the theorem by an hybrid argument. Let us define the following games: Game 0: this is the same as IND-CPA0 (A, k).

Game 1: this is the same as the previous one, but in step 1 we set the public key pk to be an obfuscation (of proper size) of P.

]Game 2: this is the same as the previous one, but in step 3 instead of an encryption of m1 we give A an obfuscation of P.

Game 3: this is the same as Game 4, but in step 1 we set the public key pk O(P).

Game 4: this is the same as IND-CPA1 (A, k).

Proving that no adversary can distinguish between two consecutive games with more than negligible probability implies the security of our scheme. We first prove that Game 0 and Game 1 (and similarly Games 4 and 3) are indistinguishable assuming the VBB property of O. Assume by contradiction that there exists an adversary A such that |Game0(A, k) Game1(A, k)| is greater than any negligible function of k. Then we can build an adversary A0 against the VBB property of O for the class of circuits Pk = {Ps1|s {0, 1} k} {P} as follows. A0 gets in input a circuit pk Pk, and runs A simulating the IND-CPA game against it. Its goal is to distinguish whether pk = P (and output 1) or not (and output 0); it works as follows: A0 (pk, k) :

1. Runs A giving it pk as the public key.

2. A outputs two messages (m0, m1) of the same length.

3. A0 computes Enc(pk, m0) and gives it to A

4. When A outputs a bit b 0 , A0 outputs 1 if b 0 = 0 and 0 otherwise.

It is easy to see that, from A’s point of view, this game is exactly like Game 1 when pk = P, and exactly like Game 0 in the other case. Therefore (by contradiction) A0 can distinguish between P and any other circuit in Pk with more than negligible advantage. However, no simulator (in the ideal world) can do this given only oracle access to pk, as this would imply querying the oracle for pk on input the only random point x such that pk(x) 6= 1, which can only happen with probability 1 2 k . As a final step, we prove that no adversary can distinguish between Games 1 and 2 (2 and 3 respectively) with more than negligible probability. The distribution of the view of A is identical in both games up to step 3, where it receives a direct obfuscation of P in Game 2, and an encryption Enc(pk, m0) in Game 1. However, since we are using an obfuscation of P as a public key in both games, the ciphertexts given to the adversary are both functionally equivalent6 to (obfuscations of) P. Therefore, by the security property of the obfuscator (as in the ideal world we are giving the same oracle to the simulator in both cases), A cannot distinguish between the two distributions and therefore between the two games.

Properties of Our Scheme

The scheme (Gen, Enc, Dec) defined in the previous section has an interesting property, namely that it is possible to combine ciphertexts together in order to achieve some flavour of proxy re-encryption, namely it is possible to delegate to someone the power to transform ciphertexts encrypted under a public key P1 into ciphertexts encrypted under a different public key P2 without having to release the corresponding secret key s1. To see how this is possible, think of a proxy who is given two public keys

(P1, P2) and C12 = Enc(P2, s1)

This means that they have the same input/output behaviour on all inputs. We also note that by this property this part of the proof also works if we assume indistinguishability obfuscation instead of the VBB one.

(i.e., an encryption of secret key 2 using public key 1). It will be convenient now to say that a circuit C (not necessarily an output of Enc) is an encryption of m under key i if Dec(si , C) = m. Then the proxy, using C1 s.t. Dec(s1, C1) = m and C12 s.t. Dec(s2, C12) = s1, can compute an encryption of m under key P2 by creating an obfuscated circuit C2 O(C2) where C2 is defined as follows:

def C2(x {0, 1} k ) {0, 1} k 1.

Output C1(C12(x));

It is now easy to check that C2(s2) = m and that, due to the property of the VBB obfuscator O, nothing else can be computed from C2.

2-cycle from n-cycle: Using this property, we can go from a cycle of n encryptions to n1 cycles of length 2. Namely, let Ci(i+1) = Enc(Pi , si+1) for all i {1, . . . , n} (where all additions are modulo n). Then one can create circuits

C (i+1)i = C(i+1)(i+2) . . . C(i1)i

Note that in this case we are not even interested in re-obfuscating the concatenation of the circuits (like in the proxy re-encryption application) and the circuit C (i+1)i is a “functional ciphertext” in the sense that it is a circuit which decrypts to si on input si+1. The only difference between C and “regular” ciphertext is that the size of C grows with n. Given an obfuscator O, it is possible to find an upper bound n = poly(k, n) s.t. the size of C (i+1)i is less than n.

Related Questions

Navigate

• Browse (All)
• Browse L
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.