Wikipedia has some more info about ANF here: Wikipedia: Algebraic normal form Truth Tables and Lookup TablesĪ truth table is just where you specify the inputs into a boolean function and the output of that boolean function for the given input:Ī lookup table is similar in functionality, except that it has multi bit output. In homomorphic encryption, since AND is so much more costly than XOR, minimizing the ANDs is a very nice win, and worth the effort. That smaller form does 1 AND and 2 XORs, versus the ANF which does 3 ANDs and 2 XORs. In fact, ANF is not always the smallest circuit possible, you’d have to factor common ANDs to find the smallest way you could represent the circuit, like the below:
It is essentially a boolean polynomial, where AND is like multiplication, and XOR is like addition. There are other forms for writing boolean logic, but ANF suits me best for my homomorphic encryption circuit needs!Īn example of boolean logic in ANF is the below: Since it’s a normal form, two functions that do the same thing will be the same thing in ANF. If you want to know more about homomorphic encryption, here’s a post I wrote which explains a very simple algorithm: Super Simple Symmetric Leveled Homomorphic Encryption Implementation Algebraic Normal FormĪlgebraic normal form (ANF) is a way of writing a boolean function using only XOR and AND.
Converting half adder truth table to a circuit how to#
So, I’m using the information in this post to be able to turn a lookup table, or a specific boolean function, into a logic circuit that I can feed into a homomorphic encryption based digital circuit.Įssentially I want to figure out how to do a homomorphic table lookup to try and make some simple as possible circuits, that will in turn be as fast and lean as possible. However, when doing homomorphic encryption (at least currently, for the techniques I’m using), you only have XOR and AND logic operations. Lots of use cases if this can ever get fast enough to become practical, such as doing cloud computing with private data. This lets encrypted data be operated on by an untrusted source, given back to you, and then you can decrypt your data to get a result. My specific usage case for this is in my investigations into homomorphic encryption, which as you may recall is able to perform computation on encrypted data. In this post I’m going to show how you turn a truth table into a digital logic circuit that uses XOR and AND gates.
0 kommentar(er)
