You are looking at a specific version 20190826:124035 of this paper. See the latest version.

Paper 2019/963

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

Pascal Aubry and 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
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.