Cryptology ePrint Archive: Report 2017/483

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

Sergiu Carpov and 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.

Category / Keywords: boolean functions, homomorphic encryption, multiplicative depth

Date: received 29 May 2017, last revised 30 May 2017

Contact author: sergiu carpov at cea fr

Available format(s): PDF | BibTeX Citation

Version: 20170531:180240 (All versions of this report)

Short URL:

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]