1
$\begingroup$

I have a question regarding the scheme below. PSI using homomorphic encryption appears to subtract the plaintext into the ciphertext. I understand that homomorphism is maintained in operations between ciphertexts. Is homomorphism maintained even if calculated as below?

If 3. (b) operation is correct, c=[c0,c1] and x is a single element. How 3.(b) operation can be possible?

h

$\endgroup$
2
  • 1
    $\begingroup$ It would help to know what paper this is from. However, my guess is that it's just sloppy notation to refer to "homomorphically compute the polynomial $r_i\prod_{x \in X} (m_i - x)$", where $m_i$ is the plaintext message encoded in $c_i$. Specifically, note that the sender and receiver "agree on an FHE scheme" so there is no guarantee that the ciphertext is even of the form $c=[c0,c1]$ or that the arithmetic operations on the ciphertexts translate to the plaintext space. $\endgroup$ Jan 29 at 9:17
  • $\begingroup$ Alternatively, assuming a specific scheme (e.g., BGV), $x$ can first be encrypted by the sender using the public key (to have the form $[c_0, c_1]$) and then used to compute the operations as described. However, this would assume the arithmetic operations translate to plaintext space. $\endgroup$ Jan 29 at 9:20

2 Answers 2

0
$\begingroup$

The paper omit the details that they had to encode the plaintexts into RLWE formats. In RLWE form, you could add ciphertexts and plaintexts (Note that you can do this addition without encrypting the plaintexts first).

$\endgroup$
0
$\begingroup$

To generalize vince.h's answer, homomorphic encryption schemes can allow certain operations between ciphertext and plaintext (c.f., https://en.wikipedia.org/wiki/Paillier_cryptosystem for another one that allows both ciphertext operations and ciphertext-plaintext operations).

$\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.