Anzeige
Erschienen in:
2005 | OriginalPaper | Buchkapitel
Evaluating 2-DNF Formulas on Ciphertexts
verfasst von : Dan Boneh, Eu-Jin Goh, Kobbi Nissim
Erschienen in: Theory of Cryptography
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Let
ψ
be a 2-DNF formula on boolean variables
x
1
,...,
x
n
∈ {0,1}. We present a homomorphic public key encryption scheme that allows the public evaluation of
ψ
given an encryption of the variables
x
1
,...,
x
n
. In other words, given the encryption of the bits
x
1
,...,
x
n
, anyone can create the encryption of
ψ
(
x
1
,...,
x
n
). 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 of the system:
1
In a database of size
n
, the total communication in the basic step of the Kushilevitz-Ostrovsky PIR protocol is reduced from
$\sqrt{n}$
to
$\sqrt[3]{n}$
.
2
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 still efficient.
3
A protocol for universally verifiable computation.