International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Private Branching Programs: On Communication-Efficient Cryptocomputing

Authors:
Helger Lipmaa
Download:
URL: http://eprint.iacr.org/2008/107
Search ePrint
Search Google
Abstract: We polish a recent cryptocomputing method that makes it possible to cryptocompute every language in $\mathbf{L/poly}$. We give several nontrivial applications, including: (a) A CPIR protocol with log-squared communication and sublinear server-computation by giving a secure function evaluation protocol for Boolean functions with similar performance, (b) A protocol that makes it possible to compute (say) how similar is client's input to an element in server's database, without revealing any information to the server, (c) A protocol for private database updating with low amortized complexity.
BibTeX
@misc{eprint-2008-17784,
  title={Private Branching Programs: On Communication-Efficient Cryptocomputing},
  booktitle={IACR Eprint archive},
  keywords={cryptographic protocols/binary decision diagrams, branching programs, computationally-private information retrieval, cryptocomputing, private database updating},
  url={http://eprint.iacr.org/2008/107},
  note={Third public draft h.lipmaa@cs.ucl.ac.uk 14014 received 10 Mar 2008, last revised 14 May 2008},
  author={Helger Lipmaa},
  year=2008
}