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 functionshomomorphic encryptionmultiplicative depth
Contact author(s)
sergiu carpov @ cea fr
History
2017-05-31: received
Short URL
https://ia.cr/2017/483
License
Creative Commons Attribution
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},
      note = {\url{https://eprint.iacr.org/2017/483}},
      url = {https://eprint.iacr.org/2017/483}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.