# (Bristol Format) Circuits of Basic Functions Suitable For MPC and FHE

These are old circuits produced many years ago!

Here we collect a set of basic combinatorial circuits which may be useful for people to test our binary-circuit based MPC and FHE implementations.

The circuits consist of ANDs and XORs and inverters. The inverters themselves can be replaced either by XOR's or by ``wire switching'' depending on what type of MPC/FHE algorithm is being used.

In order to produce the files we first created flattened Verilog netlists, we started from a purely combinational HDL description of the implementation. We used Cadence Encounter RTL compiler in conjunction with the Faraday FSA0A_C 0.18 mm ASIC Standard Cell Library for synthesis. For synthesis we flattened the hardware modules hierarchy and we allowed only the use of INV1S, AN2, XOR2HS, TIE0, and TIE1 cells. After this we re-wrote the output and topologically sorted the resulting circuits. The topological sorting makes them easier to use in FHE and MPC applications.

To understand the format: Each file consists of:

• A line defining the number of gates and then the number of wires in the circuit.
• Then two numbers defining the number n1 and n2 of wires in the inputs to the function given by the circuit.
• We assume the function has at most two inputs; since most of our examples do. If the function has only one input then the second inputs size is set to zero.
• Then on the same line comes the number of wires in the output n3.
• The wires are ordered so that the first n1 wires correspond to the first input value, the next n2 wires correspond to the second input value. The last n3 wires correspond to the output of the circuit.
• After this the gates are listed in the format:
• Number input wires
• Number output wires
• List of input wires
• List of output wires
• Gate operation (XOR, AND or INV).
So for example
```      2 1 3 4 5 XOR
```
corresponds to
```       w5=XOR(w3,w4).
```
For each file we give the number of AND, XOR and INV gates in the file. We invite others to optimize these files or present better ones (please use the same format though). All ``better'' representations we will place on this website; recall that better representations means less AND gates in the context of MPC and FHE.

### Block Ciphers

 Function File No. ANDs No. XORs No. INVs AES (No Key Expansion) AES-non-expanded.txt 6800 25124 1692 AES (Key Expanded) AES-expanded.txt 5440 20325 1927 DES (No Key Expansion) DES-non-expanded.txt 18124 1340 10849 DES (Key Expanded) DES-expanded.txt 18175 1351 10875
The above present the encryption functions only. A non-expanded variant means that the input key (the second input) is assumed non-expanded; i.e. AES-128 has a 128 bit second input value. The expanded variant means that we assume that the input key has already been expanded; i.e. AES-128 has a 1408 bit second input value.

### Hash Functions

 Function File No. ANDs No. XORs No. INVs MD5 md5.txt 29084 14150 34627 SHA-1 sha-1.txt 37300 24166 45135 SHA-256 sha-256.txt 90825 42029 103258

For the hash functions we ignore padding and only allow a single-block input. Each circuit implements the compression function of the respective hash function, where the input chaining values are fixed to the IV values of the respective hash function. The input of the circuit is a full-size message block, the output consists of chaining values after invocation of the compression function (formatted in the same way as the digest value would be in the respective hash function).

In particular this means we obtain the following test vectors for each function:

### Arithmetic Functions

 Function File No. ANDs No. XORs No. INVs 32-bit Adder adder_32bit.txt 127 61 187 64-bit Adder adder_64bit.txt 265 115 379 32x32-bit Multiplier mult_32x32.txt 5926 1069 5379 Comparison 32-bit Signed LTEQ comparator_32bit_signed_lteq.txt 150 0 162 Comparison 32-bit Signed LT comparator_32bit_signed_lt.txt 150 0 150 Comparison 32-bit Unsigned LTEQ comparator_32bit_unsigned_lteq.txt 150 0 162 Comparison 32-bit Unsigned LT comparator_32bit_unsigned_lt.txt 150 0 150

Note, that the above are produced by a standard tool chain. Hand optimized circuits can achieve much smaller AND gate counts.
All current files have been produced by Stefan Tillich, with post-processing by Nigel Smart.