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
_{1}and n_{2}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
_{3}. - The wires are ordered so that the first n
_{1}wires correspond to the first input value, the next n_{2}wires correspond to the second input value. The last n_{3}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).

2 1 3 4 5 XOR

corresponds tow

_{5}=XOR(w_{3},w_{4}).

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 |

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:

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.