Paper 2017/483

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

Sergiu Carpov, Pascal Aubry, and Renaud Sirdey


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.

Available format(s)
Publication info
Preprint. MINOR revision.
boolean functionshomomorphic encryptionmultiplicative depth
Contact author(s)
sergiu carpov @ cea fr
2017-05-31: received
Short URL
Creative Commons Attribution


      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{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.