Download PDFOpen PDF in browser

Improved heuristic for multiplicative depth minimization of boolean circuits

EasyChair Preprint 782

2 pagesDate: February 20, 2019

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

BibTeX entry
BibTeX does not have the right entry for preprints. This is a hack for producing the correct reference:
@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}}
Download PDFOpen PDF in browser