0
$\begingroup$

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?

Improve this question
$\endgroup$
1

1 Answer 1

Reset to default
3
$\begingroup$

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.

Improve this answer
$\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.