# Is it possible to design an algorithm that is based on the xor of the plaintext bits?

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)?

• Does $f$ know the $b$ values? Sep 4, 2022 at 13:20
• No, it does not. Sep 4, 2022 at 16:45
• 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. Sep 5, 2022 at 12:16
• 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. Sep 5, 2022 at 12:34
• I've removed the homomorphic encryption tag for now, as it may wrong-foot people. Sep 5, 2022 at 12:50

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$$.
• 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. Sep 8, 2022 at 6:40