1
$\begingroup$

Let E be some IND-CPA public key encryption scheme. Given two users with public keys $pk_0,pk_1$ respectively, each user $i$ selects a nonce $r_i$ at random and computes an encryption $c_i = E_{pk_i,r_i}(b_i)$ of some secret bit $b_i\in\{0,1\}$ selected by the user. Is it possible to construct an algorithm A such that

$ \begin{array}{ c l } A(c_1,c_2)= \begin{cases} (E_{pk_0,r'}(0),E_{pk_1,r''}(1)) & \text{if } b_0 \oplus b_1 = 1\\ (E_{pk_0,r'}(1),E_{pk_1,r''}(0)), & \text{if } b_0 \oplus b_1 = 0 \end{cases} \end{array} $ where r' and r'' are random nonces that might be chosen by A, by the users (r' is chosen by user 0 and r'' is chosen by user 1), or it can be a result of some computation of A. This should be without the knowledge of the secret keys associated with $pk_0,pk_1$ (in particular, A is not a constructed based on the knowledge of the secret keys of the users)?

$\endgroup$
8
  • $\begingroup$ Does $f$ know the $b$ values? $\endgroup$
    – kelalaka
    Sep 4, 2022 at 13:20
  • $\begingroup$ No, it does not. $\endgroup$
    – Doron
    Sep 4, 2022 at 16:45
  • 1
    $\begingroup$ Good comment, I tried to simplify things, but perhaps it makes it less understandable. $b_0$ and $b_1$ are not input of A,but only the encryptions of them are inputs. The more elaborative setting is that there are two users with public keys $pk_0$ and $pk_1$ who encrypt these bits. E is in fact IND-CPA. I tagged it as homomorphic because I thought that the encryption scheme need to satisfy some homomorphic property. I will edit the question so that it will be more understandable. $\endgroup$
    – Doron
    Sep 5, 2022 at 12:16
  • 1
    $\begingroup$ Anyway, I had some thought on that and it seems that it may actually be trivial. The algorithm simply selects a bit, encrypt it, and set it as the first argument of the algorithm. The it checks if the first ciphertext of result is an encryption of 0 or 1. This will reveal the other user's bit because of the xor. Then, A can do it to the other user and reveal the other user's bit. Then it can compute the desired function. $\endgroup$
    – Doron
    Sep 5, 2022 at 12:34
  • 1
    $\begingroup$ I've removed the homomorphic encryption tag for now, as it may wrong-foot people. $\endgroup$
    – Maarten Bodewes
    Sep 5, 2022 at 12:50

1 Answer 1

1
$\begingroup$

If I get the question correctly, what's asked is impossible.

Argument: Assume $A$ exists. We'll use it, and the three algorithms of the public key encryption scheme, in order to tell if a cryptogram $c=E_{pk,r}(x)$ is for $x=0$ or $x=1$, in an experiment where we are given $pk$ and $c$ (but not the private key $sk$ matching $pk$, nor $x$). This contradicts the given that $E$ is IND-CPA, hence the assumption does not hold.

We compute $x$ in 4 steps:

  1. We use the key generation algorithm to build one known $(pk',sk')$ pair.
  2. We use the encryption algorithm to compute $c'=E_{pk',\hat r}(0)$ for some $\hat r$ that we select arbitrarily within the constraints set by the encryption algorithm.
  3. We compute $A(c,c')$ using $A$ (giving it $pk$ and $pk'$ as auxiliary input, replacing $pk_0$ and $pk_1$ if $A$ needs such input; we know $pk$ because that's a given, and we know $pk'$ from step 1). $A$ outputs a pair $(d,d')$. We extract $d'$.
  4. We use the decryption algorithm to decipher $d'$ per private key $sk'$ that we know from step 1. The defining property of $A$ implies that the deciphered plaintext is the desired $x$, by examination of the two cases:
    • if $x=1$, then $x\oplus 0=1$, thus the top case applies, thus $d'$ must be $E_{pk',r''}(1)$ for some $r''$, thus $d'$ must decipher to $1$.
    • if $x=0$, then $x\oplus 0=0$, thus the bottom case applies, thus $d'$ must be $E_{pk',r''}(0)$ for some $r''$, thus $d'$ must decipher to $0$.
$\endgroup$
1
  • $\begingroup$ Thanks @fgrieu. Exactly. That also what I tried to say in my comment (I wrote trivial, though I meant that it should not be possible). You wrote it formally with much better and precise explanation. $\endgroup$
    – Doron
    Sep 8, 2022 at 6:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.