Paper 2019/963
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)
-
PDF
- 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},
url = {https://eprint.iacr.org/2019/963}
}
