Reducing the AND complexity of Boolean circuits using replacement rules for n-input gates

Reducing the AND complexity of Boolean circuits using replacement rules for n-input gates

Bachelor Thesis, Master Thesis

Motivation

Many protocols for secure computation represent the function to be computed as a Boolean circuit consisting of XOR and AND gates. Here, the XOR gates can be computed locally without the use of cryptographic operations, whereas the AND gates require interaction between the parties and are thus expensive. The goal of this thesis is to optimize n-input gates (the gates that map an n-bit input to the corresponding 1-bit output) by replacing them with the minimum number of AND gates and some amount of XOR gates in order to reduce their AND-size.

Pinkas et al. [1] have shown that exactly half of the n-input gates (namely those where the Hamming weight of the function table is even) can be computed by at most n-2 AND gates and free XORs for n<4. The research question is if this holds true also for n=4, 5, etc. The idea is to enumerate all circuits consisting of up to i=0,1, 2, .., n-1 AND gates on n inputs and see to which n-input functionality they correspond.

Tasks

The student will design an algorithm for finding the replacement rules for n-input gates. In the next step, he/she will integrate the replacement rules into the look-up table-based precomputations [2] in the ABY framework [3] for secure computation. Potentially, replacement rules for n-input gates can also be applied to 3-valued logic, e.g., for the protocols in the very recent paper by Lindell and Yanai [4] which uses 4-input gates. This has to be investigated, and the improvement has to be compared with [4].

Requirements

  • Good programming skills in C/C++
  • At least basic knowledge of cryptography and Boolean algebra
  • High motivation + ability to work independently
  • Knowledge of the English language, Git, LaTeX, etc.

References

  • [1] Benny Pinkas, Thomas Schneider, Nigel P. Smart, Stephen C. Williams. Secure Two-Party Computation is Practical. In 15th Advances in Cryptology – ASIACRYPT'09
  • [2] Ghada Dessouky, Farinaz Koushanfar, Ahmad-Reza Sadeghi, Thomas Schneider, Shaza Zeitouni, Michael Zohner. Pushing the communication barrier in secure computation using lookup tables. In: 24. Annual Network and Distributed System Security Symposium (NDSS'17).
  • [3] ABY (https://github.com/encryptogroup/ABY)
  • [4] Yehuda Lindell, Avishay Yanai. Fast Garbling of Circuits over 3-Valued Logic. In Cryptology ePrint Archive: Report 2017/1225

Supervisor