<p>1) $x_0$ is (indeed) a plaintext. (Perhaps to guess at where confusion arose from:) the 'more modern' version of homomorphic encryption is <em>fully homomorphic encryption</em> (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..)</p>

<p>This paper uses <em>additive-homomorphic encryption,</em> 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.</p>

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

<hr>

<p>2) Read it as a field =)</p>

CC BY-SA 3.0
2017-05-24T21:06:10.093Z
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.)
D.W.
CC BY-SA 3.0
2017-05-25T12:48:32.320Z
Yep @D.W. That'll do it =)
Daniel Apon
CC BY-SA 3.0
2017-05-23T23:10:18.587Z
2017-05-23T23:10:18.587Z
Daniel Apon
<p>I was reading the paper <a href="https://dl.acm.org/citation.cfm?id=1760761" rel="nofollow noreferrer">Security Against Covert Adversaries: Efficient Protocols for Realistic Adversaries</a> 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 <a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.66.7059&amp;rep=rep1&amp;type=pdf" rel="nofollow noreferrer">this .pdf</a> it's page 25.
I've put just pages 25 and 26 (the ones relevant to my question) <a href="http://docdro.id/C1MQI37" rel="nofollow noreferrer">here</a>.</p>

<p>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.</p>

<p>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)$$</p>

<p>I have two real questions about this:</p>

<ol>
<li><p>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?</p></li>
<li><p>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?</p></li>
</ol>

<p>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.</p>

<cr.crypto-security><homomorphic-encryption>
"Security Against Covert Adversaries" question
Mark Schultz-Wu
# "Security Against Covert Adversaries" question

(Asked by: username_0 on 2017-05-23)

I was reading the paper [Security Against Covert Adversaries: Efficient Protocols for Realistic Adversaries](https://dl.acm.org/citation.cfm?id=1760761) 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](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.66.7059&rep=rep1&type=pdf) it's page 25.
I've put just pages 25 and 26 (the ones relevant to my question) [here](http://docdro.id/C1MQI37).

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.

**Tags:** cr.crypto-security, homomorphic-encryption

---

## 1 answers

### Answer by username_1 on 2017-05-23. Score: 2 | Accepted answer

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

> **Comments:**
> **username_2**: 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.)  
> **username_1**: Yep @D.W. That'll do it =)  

---

