<p>If you can do addition modulo 2 and multiplication modulo 2, you can implement XOR and AND gates, which are a universal basis for circuits, so you can implement any circuit.</p>
<p>As @holf <a href="https://cstheory.stackexchange.com/questions/51624/how-can-arbitrary-combinational-logic-be-done-with-just-addition-and-multiplicat#comment114273_51625">points out</a>, if you don't have modular arithmetic and are working with integers, alternatively you can implement NAND gates as follows: if you ensure that all inputs are 0 or 1, then <span class="math-container">$f(x,y) = 1-xy$</span> acts as a NAND gate and ensures that its output is 0 or 1.  Since NAND gates are universal for circuits, you can implement any circuit in this way.</p>

CC BY-SA 4.0
2022-06-26T07:07:33.990Z
Alternatively, $x NAND y = 1+x \times y$ modulo $2$. Or if you are working on rational numbers, $x NAND y = 1-x\times y$ for $x,y \in \{0,1\}$.
holf
CC BY-SA 4.0
2022-06-26T09:01:39.470Z
Is there a way I can “normalize” it to a 0 or a 1 for security reasons before I output?
Nic
CC BY-SA 4.0
2022-06-26T16:29:09.283Z
@Nic, if you use Nic's approach, there is no need to normalize it.  NAND is a universal basis for circuits, so all you need are NAND gates plus ensuring that the inputs are all 0-or-1.
D.W.
CC BY-SA 4.0
2022-06-26T05:07:52.287Z
2022-06-27T06:32:06.430Z
2022-06-27T06:32:06.430Z
D.W.
<p>Once when I was reading about SPDZ (a multi-party computation protocol), and once when I was reading about homomorphic encryption, it was taken for granted that since both addition and multiplication could be done, any other function could be derived from that (I am assuming this only includes combinational logic).</p>
<p>From <a href="https://nvotes.com/multiplicative-vs-additive-homomorphic-elgamal/" rel="nofollow noreferrer">this</a> explanation of fully homomorphic encryption</p>
<blockquote>
<p>The combination of addition and multiplication allows arbitrary functions to be computed on encrypted data.</p>
</blockquote>
<p>Other than the &quot;product of sums&quot;, I've never heard of boolean operations being interchangeable with arithmetic operations, and I can't think of how how to derive boolean operations from arithmetic.</p>
<p>How can this be done? Can I optimize an algorithm by multiplying integers directly but also use boolean logic?</p>

<homomorphic-encryption>
How can arbitrary combinational logic be done with just addition and multiplication?
Nic
# How can arbitrary combinational logic be done with just addition and multiplication?

(Asked by: username_0 on 2022-06-26)

Once when I was reading about SPDZ (a multi-party computation protocol), and once when I was reading about homomorphic encryption, it was taken for granted that since both addition and multiplication could be done, any other function could be derived from that (I am assuming this only includes combinational logic).

From [this](https://nvotes.com/multiplicative-vs-additive-homomorphic-elgamal/) explanation of fully homomorphic encryption

> The combination of addition and multiplication allows arbitrary functions to be computed on encrypted data.

Other than the "product of sums", I've never heard of boolean operations being interchangeable with arithmetic operations, and I can't think of how how to derive boolean operations from arithmetic.

How can this be done? Can I optimize an algorithm by multiplying integers directly but also use boolean logic?

**Tags:** homomorphic-encryption

---

## 1 answers

### Answer by username_1 on 2022-06-26. Score: 3 | Accepted answer

If you can do addition modulo 2 and multiplication modulo 2, you can implement XOR and AND gates, which are a universal basis for circuits, so you can implement any circuit.

As @holf [points out](https://cstheory.stackexchange.com/questions/51624/how-can-arbitrary-combinational-logic-be-done-with-just-addition-and-multiplicat#comment114273_51625), if you don't have modular arithmetic and are working with integers, alternatively you can implement NAND gates as follows: if you ensure that all inputs are 0 or 1, then $f(x,y) = 1-xy$ acts as a NAND gate and ensures that its output is 0 or 1. Since NAND gates are universal for circuits, you can implement any circuit in this way.

> **Comments:**
> **username_2**: Alternatively, $x NAND y = 1+x \times y$ modulo $2$. Or if you are working on rational numbers, $x NAND y = 1-x\times y$ for $x,y \in \{0,1\}$.  
> **username_0**: Is there a way I can “normalize” it to a 0 or a 1 for security reasons before I output?  
> **username_1**: @Nic, if you use Nic's approach, there is no need to normalize it.  NAND is a universal basis for circuits, so all you need are NAND gates plus ensuring that the inputs are all 0-or-1.  

---

