Improved heuristic for multiplicative depth minimization of boolean circuits

EasyChair Preprint 782

Abstract

In somewhat homomorphic encryption schemes (e.g. B/FV, BGV) the size of ciphertexts and the execution performance of homomorphic operations depend heavily on the multiplicative depth. In this work we propose an improved multiplicative depth minimization heuristic. In particular, a new circuit rewriting operator is introduced, the so called cone rewrite operator. The results we obtain using the new method are relevant in terms of accuracy and performance compared to previous works. Smaller multiplicative depths for a benchmark of boolean circuits are obtained when compared to previous work. In average, the multiplicative depth is lowered by approximatively 5 times and heuristic execution performance is significantly improved.

Keyphrases: Boolean circuits, homomorphic encryption, multiplicative depth

@booklet{EasyChair:782,
  author    = {Pascal Aubry and Sergiu Carpov and Renaud Sirdey},
  title     = {Improved heuristic for multiplicative depth minimization of boolean circuits},
  howpublished = {EasyChair Preprint 782},
  year      = {EasyChair, 2019}}