(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:

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.