'Bristol Fashion' MPC Circuits

If you are looking for the old 'Bristol Format' circuits please see here. We call this new format 'Bristol Fashion' as it is related to the old format, which was called 'Bristol Format' by some others (as they were originally hosted in Bristol). The new format is tidier than the old format, which also is a justification for the new name of Bristol Fashion.

Our new format is utilized in the SCALE-MAMBA software system to define the circuits for garbling. The new format is designed to be independent of the number of parties, and to capture more the nature of the function we are evaluating.

The format is defined by a list of gates. Eac gate has one or two input wires (INV/NOT/EQ/EQW gates have only one input wire, XOR and AND have two input wires). A gate can have only one output wire. Each file is of the following format:

Note:
  1. The wire numbering is ordered so that the first i_0 wires correspond to the first input value, the next i_1 wires correspond to the second input value and so on.
  2. With the last (o_0+...+o_{n-1}) wires corresponding to the outputs of the function, where n=no_1+...+no_nov
Currently we only have a few circuits available, more will be added as time goes by.

Arithmetic Functions

Function File No. ANDs No. XORs No. INVs
64-bit Adder adder64.txt 63 313 0
64-bit Subtract sub64.txt 63 313 63
64-bit Negation neg64.txt 62 63 64
64x64 -> 64 bit Multiplier mult64.txt 4033 9642 0
64x64 -> 128 bit Multiplier mult2_64.txt 8128 19904 0
64x64-bit Division (Signed) divide64.txt 4664 24817 445
64x64-bit Division (Unsigned) udivide64.txt 4094 24063 127
64-bit Equal to Zero Test zero_equal.txt 63 0 64

Cryptographic Functions

Function File No. ANDs No. XORs No. INVs
AES-128(k,m) aes_128.txt 6400 28176 2087
AES-192(k,m) aes_192.txt 7168 32080 2317
AES-256(k,m) aes_256.txt 8832 39008 2826
Keccak-f Keccak_f.txt 38400 115200 38486
SHA-256 sha256.txt 22573 110644 1856
SHA-512 sha512.txt 57947 286724 4946
Note for AES-128 the wire orders are in the reverse order as used in the examples given in our earlier `Bristol Format', thus bit 0 becomes bit 127 etc, for key, plaintext and message.

For AES we created a design using the Boyar-Peralta S-Boxes, which have 32 AND gates per S-Box.

For SHA-256 and SHA-512 we give a circuit which maps an input buffer and an input chaining state to the next chaining state.

To get the nice gate counts for SHA-256 and SHA-512 we thank Steven Goldfeder who provided advice and help from his work in the paper:

In particular he pointed out the 'correct' method for addition circuits which means an n-bit adder only uses n-1 AND gates. Whilst this addition method was well known to us turned out our VHDL synthesis tools would spot we were doing an adder and then substitute in the usual circuit used in real hardware (which uses more AND gates). Fixing this required some VHDL trickery from Danilo. Finally, the same trick was then then factored into the improved 64-bit arithmetic circuits above.

IEEE Floating Point Operations

We also provide some circuits for IEEE floating point operations. These operations deal with the IEEE rounding and NaN etc correctly. An 64-bit IEEE double is represented in the following format; in particular
  1. Bit 63 is the sign bit
  2. Bits 52-62 are the exponent, with 62 being the msb.
  3. Bits 0-51 are the mantissa, with 51 being the msb.
Function File No. ANDs No. XORs No. INVs
add FP-add.txt 5385 8190 2062
mul FP-mul.txt 19626 21947 3326
div FP-div.txt 82269 84151 17587
eq FP-eq.txt 315 65 837
f2i FP-f2i.txt 1467 1625 840
f2i FP-f2i.txt 2416 3605 1115
sqrt FP-sqrt.txt 91504 100120 19900
Note the function f2i implements the `round nearest-even' convention which is equivalent to the C++ code
  double xx=....;
  unsigned long zz;
  zz=(long) nearbyint(xx);

Most of the circuits were created using Synposis tools from VHDL source. The VHDL can be found in the release of SCALE-MAMBA if you are interested. The current circuits above were produced from the VHDL in SCALE-MAMBA version 1.7. After the associated NetList was produced we post-processed them into the format described above, for use within the SCALE-MAMBA engine.

The floating point circuits were created by using the Berkeley SoftFloat library (version 2), then the output was passed through CBMC-GC to produce Bristol Format files with no OR's. We then manually edited the result to produce Bristol Fashion files.

David Archer
Victor Arribas Abril
Pieter Maene
Nele Mertens
Danilo Sijacic
Nigel Smart