I was reading the paper Security Against Covert Adversaries: Efficient Protocols for Realistic Adversaries by Aumann and Lindell, and had some questions with the protocol for covert OT given errorless homomorphic encryption. This is section 5.1, and in this .pdf it's page 25. I've put just pages 25 and 26 (the ones relevant to my question) here.

The protocol itself is a little long (a little over a page for the full description). I'll mention the part I have questions about.

As part of the protocol, the ciphertext $\tilde{c}_0 = x_0\cdot_E c_0$ is computed. Later it's claimed that (if $c_0$ is an encryption of $0$) that: $$\tilde{c}_0 = x_0\cdot_E c_0 = E_{pk}(0\cdot x_0) = E_{pk}(0)$$

I have two real questions about this:

  1. It seems like it should be true that $x_0\cdot_E c_0 = Enc_{pk}(Dec_{sk}(x_0)\cdot Dec_{sk}(c_0))$. It's instead stated (implicitly) that $x_0\cdot_E c_0 = Enc_{pk}(x_0\cdot Dec_{sk}(c_0))$. Is this a typo, or a misunderstanding on my part of what homomorphic encryption is?

  2. In the part I mentioned about $\tilde{c}_0$, it seems like $0\cdot x_0$ is an operation in the message-space group. For the proof of security, it seems vital that $0\cdot x_0 = 0$. But this seems to imply that $0$ isn't invertible (as it typically isn't), so is this really occuring in a group? If not, is this ok for some other reason?

I haven't really worked with homomorphic encryption before (or much computer science to be honest), so I apologize if these questions are rather basic.


1) $x_0$ is (indeed) a plaintext. (Perhaps to guess at where confusion arose from:) the 'more modern' version of homomorphic encryption is fully homomorphic encryption (FHE) fully supporting both additive and multiplicative homomorphisms, whereas the paper you're reading was published about 2.5 years before Gentry's original FHE scheme came out. (Check out the wikipedia article on homomorphic encryption for more examples..)

This paper uses additive-homomorphic encryption, which allows the computation $Enc(pk, x_0) + Enc(pk, x_1) = Enc(pk, x_0 + x_1)$. Note that additive-homomorphic encryption schemes tend to support (must.. support?) an additional "scalar-multiplication homomorphism." That is, the computation $$x_0 \cdot Enc(pk, x_1) = Enc(pk, x_0\cdot x_1),$$ where plaintext $x_0$ is public information.

(Note that the above is different than FHE, which supports both the prior additive homomorphism, and simultaneously the "full" multiplicative homomorphism of $Enc(pk, x_0) \cdot Enc(pk, x_1) = Enc(pk, x_0\cdot x_1).$)

2) Read it as a field =)

  • 1
    $\begingroup$ Must support is correct -- given ability to add, you can multiply by a scalar constant, by using a double-and-add algorithm. (e.g., to multiply by 8, add to itself three times. to multiply by 9, multiply by 8, then add that to the original number.) $\endgroup$
    – D.W.
    May 24 '17 at 21:06
  • $\begingroup$ Yep @D.W. That'll do it =) $\endgroup$ May 25 '17 at 12:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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