Score:0

How are arbitrary boolean gates constructed in homomorphic encryption using only addition and multplication?

sm flag

I've recently become interested in homomorphic encryption, specifically how boolean gates are constructed to do arbitrary circuit arithmatic on the encrypted data without decrypting it.

I have heard that all you need are arbitrary addition and multiplication operations to arbitrarily construct boolean gates that can operate on the ciphertext, specifically NAND gates, which are functionally complete, or in other words can represent any boolean gate and any combination thereof.

So how are these boolean gates constructed with just addition and multiplication operations?

kelalaka avatar
in flag
See here [Representing a function as FHE circuit](https://crypto.stackexchange.com/q/63781/18298) and we have functional completeness.
Score:3
ru flag

We write $\odot$ for multiplication in $\mathbb F_2$, this is the same as the Boolean AND operation. Likewise we write $\oplus$ for additionin $\mathbb F_2$ which is the same as the Boolean XOR operation.

These two together can produce any Boolean operation if we introduce an auxilliary (encrypted) operand set to 1. In this case the NAND gate can be implemented by $\mathrm{NAND}(a,b)=a\odot b\oplus 1$. Shannon's theorem than says that all other Boolean operations can be produced.

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.