### Faster homomorphic encryption is not enough: improved heuristic for multiplicative depth minimization of Boolean circuits

Pascal Aubry, Sergiu Carpov, and Renaud Sirdey

##### Abstract

In somewhat homomorphic encryption schemes (e.g. B/FV, BGV) the size of ciphertexts and the execution performance of homomorphic operations depends heavily on the multiplicative depth. The multiplicative depth is the maximal number of consecutive multiplications for which an homomorphic encryption scheme was parameterized. 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. Smaller multiplicative depths for a benchmark of Boolean circuits are obtained when compared to a previous work found in the literature. In average, the multiplicative depth is highly improved and the new heuristic execution time is significantly lower. The proposed rewrite operator and heuristic are not limited to Boolean circuits, but can also be used for arithmetic circuits.

##### Metadata
Available format(s)
Category
Public-key cryptography
Publication info
Preprint. MINOR revision.
Keywords
somewhat homomorphic encryptionmultiplicative depthBoolean functionsheuristic
Contact author(s)
sergiu carpov @ cea fr
p aubry @ cea fr
renaud sirdey @ cea fr
sergiu carpov cea @ gmail com
History
2019-08-26: received
Short URL
https://ia.cr/2019/963
License

CC BY

BibTeX

@misc{cryptoeprint:2019/963,
author = {Pascal Aubry and Sergiu Carpov and Renaud Sirdey},
title = {Faster homomorphic encryption is not enough: improved heuristic for multiplicative depth minimization of Boolean circuits},
howpublished = {Cryptology ePrint Archive, Paper 2019/963},
year = {2019},
note = {\url{https://eprint.iacr.org/2019/963}},
url = {https://eprint.iacr.org/2019/963}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.