Paper 2008/107

Private Branching Programs: On Communication-Efficient Cryptocomputing

Helger Lipmaa


We polish a recent cryptocomputing method of Ishai and Paskin from TCC 2007. More precisely, we show that every function can be cryptocomputed in communication, linear in the product of client's input length and the length of the branching program, and computation, linear in the size of the branching program that computes it. The method is based on the existence of a communication-efficient $(2,1)$-CPIR protocol. We give several nontrivial applications, including: (a) improvement on the communication of Lipmaa's CPIR protocol, (b) a CPIR protocol with log-squared communication and sublinear server-computation by giving a secure function evaluation protocol for Boolean functions with similar performance, (c) a protocol for PIR-writing with low amortized complexity, (d) a selective private function evaluation (SPFE) protocol. We detail one application of SPFE that makes it possible to compute how similar is client's input to an element in server's database, without revealing any information to the server. For SPFE, we design a $4$-message extension of the basic protocol that is efficient for a large class of functionalities.

Note: 19.03.08: minor update, changed title/abstract to something readable, corrected some mistakes about branching program terminology. 15.05.08: hopefully much more readable. Efficient fuzzy private matching protocol, more applications (secure vector dominance protocol, millionaire's protocol etc). 29.09.08: thoroughly rewritten, many readability changes. New application to SPFE.

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. Third public draft
branching programcryptocomputing
Contact author(s)
lipmaa @ research cyber ee
2008-09-30: last of 4 revisions
2008-03-12: received
See all versions
Short URL
Creative Commons Attribution


      author = {Helger Lipmaa},
      title = {Private Branching Programs: On Communication-Efficient Cryptocomputing},
      howpublished = {Cryptology ePrint Archive, Paper 2008/107},
      year = {2008},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.