(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 n₁ and n₂ 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 n₃.
The wires are ordered so that the first n₁ wires correspond to the first input value, the next n₂ wires correspond to the second input value. The last n₃ 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
```
       w₅=XOR(w₃,w₄).
   
```

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.