Paper 2022/1075

Secure Branching Program Evaluation

Jonas Janneck, SAP SE
Anas Boudi, Zama
Anselme Tueno, SAP SE
Matthew Akram, SAP SE

We address the problem of privately evaluating a branching program on encrypted data. This scenario is a 2-party protocol consisting of a server and a client. The server privately holds a branching program which is a representation of a boolean function using a directed acyclic graph. The client holds a secret input to the branching program. The goal of the computation is to evaluate the client's input on the server program such that only the result is revealed to the client, and nothing is revealed to the server. To solve this problem Ishai-Paskin introduced a public-key encryption scheme that is based on Damgård-Jurik additively homomorphic encryption and has the property, that given a branching program $P$ and an encryption $c$ of an input $y$, it is possible to efficiently compute a succinct ciphertext $c'$ corresponding to $P(y)$. The entire computation is done by the server relying on the fact that Damgård-Jurik scheme has length-flexible ciphertexts which allows multiplications between ciphertexts of different sizes under the same encryption key. Although the decryption of the Damgård-Jurik scheme is theoretically efficient, the size of $c'$ and the decoding time depend on the depth of the branching program. In this paper, we propose a new scheme where the input is instead encrypted using fully homomorphic encryption and discuss different variants and optimizations. The entire computation is also done by the server but the size of the resulting ciphertext is independent of the depth of the program. We implement Ishai-Paskin and our scheme and show that the running time of our scheme is an order of magnitude smaller.

Available format(s)
Cryptographic protocols
Publication info
fully homomorphic encryption multi-party computation branching program
Contact author(s)
jonas janneck @ sap com
anas boudi @ zama ai
anselme tueno @ sap com
matthew akram @ sap com
2022-08-21: approved
2022-08-18: received
See all versions
Short URL
Creative Commons Attribution


      author = {Jonas Janneck and Anas Boudi and Anselme Tueno and Matthew Akram},
      title = {Secure Branching Program Evaluation},
      howpublished = {Cryptology ePrint Archive, Paper 2022/1075},
      year = {2022},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.