0
$\begingroup$

Due to a comment stating "... QR-PKE is secure (CPA)..." I've been thinking of how to prove that it's not CCA secure, and would like to understand whether my proof is correct.

Here's the QR-PKE scheme:

  • $KeyGen(1^n)$ produces:

    $sk = (p,q)$ - two large n-bit primes

    $pk = (n, x)$ where $N=pq$ and $x$ is a random $QNR \in_R \mathbb{Z}^*_N$.

  • $Enc_{pk}(b) = x^br^2 \mod N$ , where $r \in_R \mathbb{Z}^*_N$ (random)

  • $Dec_{sk}(c)=0$ iff $c$ is a $QR$

I thought of the following interaction in the CCA security game (key points) - the adversary sends the two challenge options: $0,1$. The challenger chooses one of them, $b$, and sends its encryption, $c$. The adversary randomly chooses $r \in \mathbb{Z}^*_N$ and asks to decrypt $c x^0r^2$. If the response is $1$ he knows that the second option (i.e. $1$) was chosen, otherwise $0$ was chosen, and responds accordingly. The correctness follows from the fact that the group product of two encryptions is the encryption of the XOR, in this scheme.

Have I got it right?

$\endgroup$
4
  • $\begingroup$ "the XOR of two encryptions is the encryption of the XOR" seems incorrect. Can you show it? $\endgroup$
    – erth
    Sep 18, 2022 at 9:11
  • $\begingroup$ @erth Right - just fixed it now - I meant for it to be: "the group product of two encryptions is the encryption of the XOR" - this I proved separately, but stems from the fact that QRxQR is QR, QRxQNR is QNR and QNRxQNR is a QNR. $\endgroup$
    – Anon
    Sep 18, 2022 at 9:36
  • $\begingroup$ The last one should be QR (QNRxQNR=QR) $\endgroup$
    – Anon
    Sep 18, 2022 at 9:43
  • 1
    $\begingroup$ Yes, I think you can write an answer based on this. I think it is perhaps more to the point to phrase it as that multiplying by $r^2$ preserves the decryption result. $\endgroup$
    – erth
    Sep 18, 2022 at 10:12

1 Answer 1

1
$\begingroup$

For the sake of completion, I'm posting the answer here, with help from @erth :

The following is the interaction in the CCA security game (key points):

  • The adversary sends the two challenge options: $0,1$.

  • The challenger chooses one of them, $b$, and sends its encryption, $c$, to the adversary.

  • The adversary randomly chooses $r \in \mathbb{Z}^*_N$ and asks to decrypt $c x^0r^2$. If the response is $1$ he knows that the second option (i.e. $1$) was chosen, otherwise $0$ was chosen, and responds accordingly.

The correctness follows from the fact that, in this scheme, the group product of two encryptions is the encryption of the XOR of the message (in other words, multiplying by $r^2$ preserves the decryption result). This is because it can be shown that: $QR\times QR = QR$, and $QR \times QNR = QNR$.

$\endgroup$

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.