Cryptology ePrint Archive: Report 2016/942

Optimizing Secure Computation Programs with Private Conditionals

Peeter Laud and Alisa Pankova

Abstract: Secure multiparty computation platforms are often provided with a programming language that allows to write privacy-preserving applications without thinking of the underlying cryptography. The control flow of these programs is expensive to hide, hence they typically disallow branching on private values. The application programmers have to specify their programs in terms of allowed constructions, either using ad-hoc methods to avoid such branchings, or the general methodology of executing all branches and obliviously selecting the effects of one at the end. There may be compiler support for the latter.

The execution of all branches introduces significant computational overhead. If the branches perform similar private operations, then it may make sense to compute repeating patterns only once, even though the necessary bookkeeping also has overheads. In this paper, we propose a program optimization doing exactly that, allowing the overhead of private conditionals to be reduced. The optimization is quite general, and can be applied to various privacy-preserving platforms.

Category / Keywords: languages for secure computation, static analysis, graph theory, mixed integer programming

Original Publication (with major differences): Proceedings of the International Conference on Information and Communications Security (ICICS 2016), to appear

Date: received 29 Sep 2016

Contact author: alisa at cyber ee

Available format(s): PDF | BibTeX Citation

Version: 20161001:183833 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]