Team for Research in
Ubiquitous Secure Technology

Citation
D. Boneh, E.-J. Goh, X. Boyen. "Evaluating 2-DNF Formulas on Ciphertexts". Theory of Cryptography, 325-341, 2005.

Abstract
Let F be a 2-DNF formula on boolean variables x1,...,xn. We present a homomorphic public key encryption system that allows the public evaluation of F given an encryption of the variables x1,...,xn. In other words, given the encryption of the bits x1,...,xn, anyone can create the encryption of F(x1,...,xn). More generally, we can evaluate quadratic multi-variate polynomials on ciphertexts provided the resulting value falls within a small set. We present a number of applications for this system. First, it leads to improved PIR algorithms: In a database of size n, the total communication in the basic step of the Kushilevitz-Ostrovsky PIR protocol is reduced from n^(1/2) to n^(1/3). Second, it gives an efficient election system based on homomorphic encryption where voters do not need to include non-interactive zero knowledge proofs that their ballots are valid. The election system is proved secure without random oracles but is still efficient. Third, it gives a protocol for universally verifiable computation. Our constructions are based on bilinear maps in groups of composite order.

Electronic downloads

• http://crypto.stanford.edu/~dabo/papers/2dnf.pdf

• HTML

  D. Boneh, E.-J. Goh, X. Boyen. <a
  href="http://www.truststc.org/pubs/607.html"
  >Evaluating 2-DNF Formulas on Ciphertexts</a>,
  Theory of Cryptography, 325-341, 2005.

• Plain text

  D. Boneh, E.-J. Goh, X. Boyen. "Evaluating 2-DNF
  Formulas on Ciphertexts". Theory of Cryptography,
  325-341, 2005.

• BibTeX

  @inproceedings{BonehGohBoyen05_Evaluating2DNFFormulasOnCiphertexts,
      author = {D. Boneh and E.-J. Goh and X. Boyen},
      title = {Evaluating 2-DNF Formulas on Ciphertexts},
      booktitle = {Theory of Cryptography},
      pages = {325-341},
      year = {2005},
      abstract = {Let F be a 2-DNF formula on boolean variables
                x1,...,xn. We present a homomorphic public key
                encryption system that allows the public
                evaluation of F given an encryption of the
                variables x1,...,xn. In other words, given the
                encryption of the bits x1,...,xn, anyone can
                create the encryption of F(x1,...,xn). More
                generally, we can evaluate quadratic multi-variate
                polynomials on ciphertexts provided the resulting
                value falls within a small set. We present a
                number of applications for this system. First, it
                leads to improved PIR algorithms: In a database of
                size n, the total communication in the basic step
                of the Kushilevitz-Ostrovsky PIR protocol is
                reduced from n^(1/2) to n^(1/3). Second, it gives
                an efficient election system based on homomorphic
                encryption where voters do not need to include
                non-interactive zero knowledge proofs that their
                ballots are valid. The election system is proved
                secure without random oracles but is still
                efficient. Third, it gives a protocol for
                universally verifiable computation. Our
                constructions are based on bilinear maps in groups
                of composite order. },
      URL = {http://www.truststc.org/pubs/607.html}
  }
  

Posted by Jessica Gamble on 16 Mar 2009.
For additional information, see the Publications FAQ or contact webmaster at www truststc org.