A multi-start heuristic for multiplicative depth minimization of boolean circuits

Sergiu Carpov; Pascal Aubry; Renaud Sirdey

Paper 2017/483

A multi-start heuristic for multiplicative depth minimization of boolean circuits

Sergiu Carpov, Pascal Aubry, and Renaud Sirdey

Abstract

In this work we propose a multi-start heuristic which aims at minimizing the multiplicative depth of boolean circuits. The multiplicative depth objective is encountered in the field of homomorphic encryption where ciphertext size depends on the number of consecutive multiplications. The heuristic is based on rewrite operators for multiplicative depth-2 paths. Even if the proposed rewrite operators are simple and easy to understand the experimental results show that they are rather powerful. The multiplicative depth of the benchmarked circuits was hugely improved. In average the obtained multiplicative depths were lower by more than 3 times than the initial ones. The proposed rewrite operators are not limited to boolean circuits and can also be used for arithmetic circuits.

Metadata

Available format(s): PDF
Publication info: Preprint. MINOR revision.
Keywords: boolean functions homomorphic encryption multiplicative depth
Contact author(s): sergiu carpov @ cea fr
History: 2017-05-31: received
Short URL: https://ia.cr/2017/483
License: CC BY

BibTeX

@misc{cryptoeprint:2017/483,
      author = {Sergiu Carpov and Pascal Aubry and Renaud Sirdey},
      title = {A multi-start heuristic for multiplicative depth minimization of boolean circuits},
      howpublished = {Cryptology {ePrint} Archive, Paper 2017/483},
      year = {2017},
      url = {https://eprint.iacr.org/2017/483}
}