Open Thesis Topics

Below we give examples for open thesis topics for bachelor and master projects. Beyond these we are always open for innovative self-proposed topics that match our research profile.

1 item found. Show all theses.

• Reducing the AND complexity of Boolean circuits using replacement rules for n-input 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 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. go