Open Theses
Below we give examples for open thesis topics for bachelor and master projects. Beyond these we are always open for innovative selfproposed topics that match our research profile.
1 item found. Show all theses.

2018/02/14
Reducing the AND complexity of Boolean circuits using replacement rules for ninput gates
Bachelor Thesis, Master Thesis
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 ninput gates (the gates that map an nbit input to the corresponding 1bit output) by replacing them with the minimum number of AND gates and some amount of XOR gates in order to reduce their ANDsize.
Pinkas et al. [1] have shown that exactly half of the ninput gates (namely those where the Hamming weight of the function table is even) can be computed by at most n2 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, …, n1 AND gates on n inputs and see to which ninput functionality they correspond. go