Evaluating 2-DNF Formulas on Ciphertexts¶
Authors: Dan Boneh; Eu-Jin Goh; Kobbi Nissim
Year: 2005
Venue: TCC 2005
type: scheme collection: schemes status: auto
Links: DOI
Visual lesson: BGN (one multiplication) · Scheme table row: BGN (one multiplication)
Summary¶
Auto-extracted summary (unreviewed)
Boneh, Goh and Nissim construct a public-key homomorphic encryption scheme over composite-order bilinear groups that supports unlimited additions and a single multiplication, so anyone can evaluate 2-DNF formulas (and more generally degree-2 polynomials with small-range outputs) directly on encrypted bits. They apply the scheme to cut the communication of the basic Kushilevitz-Ostrovsky PIR step from sqrt(n) to cube-root(n), to build an election system without NIZK ballot-validity proofs that is secure without random oracles, and to a universally verifiable computation protocol.
Abstract¶
Let ψ be a 2-DNF formula on boolean variables x1, . . . , xn ∈ {0, 1}. We present a homomorphic public key encryption scheme that allows the public evaluation of ψ 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 ψ(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 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 √n to 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.
Source: pdf
Extracted details¶
| Field | Value | Source | Confidence |
|---|---|---|---|
| contribution | BGN homomorphic public-key encryption from composite-order bilinear groups | llm | 0.85 |
| contribution | arbitrary additions plus one multiplication on ciphertexts | llm | 0.85 |
| contribution | public evaluation of 2-DNF formulas and degree-2 multivariate polynomials | llm | 0.85 |
| contribution | PIR with basic-step communication reduced from sqrt(n) to cube-root(n) | llm | 0.85 |
| contribution | election system without NIZK proofs of ballot validity, secure without random oracles | llm | 0.85 |
| contribution | protocol for universally verifiable computation | llm | 0.85 |
| schemes | BGN | llm | 0.85 |
| schemes | bilinear pairings | llm | 0.85 |
| schemes | Paillier-style additive homomorphism | llm | 0.85 |
| tasks | private information retrieval | llm | 0.85 |
| tasks | electronic voting | llm | 0.85 |
| tasks | verifiable computation | llm | 0.85 |
| threat model | semantically secure public-key encryption in the standard model (no random oracles) | llm | 0.85 |
| interaction | non-interactive FHE | llm | 0.85 |
| limitations | only one multiplication supported (degree-2 polynomials) | llm | 0.85 |
| limitations | decryption requires the resulting value to lie in a small set | llm | 0.85 |
| llm relevance | low | llm | 0.85 |
| key result | PIR communication: reduced from sqrt(n) to cube-root(n) (basic step of Kushilevitz-Ostrovsky PIR, database of size n) | llm | 0.85 |
Scheme card: BGN (one multiplication)¶
| Group | 8. Partially homomorphic encryption |
| Kind | Scheme |
| Hardness assumption | Subgroup decision (pairings) |
| Plaintext type | Small integers, unlimited + and one × |
| SIMD packing | No |
| Bootstrapping | n/a |
| Post-quantum | No |
| Status | Foundational |
| Fit for LLM inference | Can do quadratic forms, enough for one quadratic layer only. |
Keyword mentions¶
Counts of vocabulary terms in the full text (first page of occurrence in brackets).
- scheme: PIR 17 [p.1], MPC 6 [p.1], Garbled circuits 6 [p.1], Leveled / somewhat HE 5 [p.8], Paillier 3 [p.2], ElGamal 2 [p.11], Threshold HE 2 [p.12]
- technique: Semi-honest model 8 [p.7], Non-interactive 3 [p.1]
- topic: Homomorphic encryption 8 [p.1]
Files¶
| Path (under papers/) | Collection | Pages | Size | SHA-256 | Note |
|---|---|---|---|---|---|
references/schemes/s48-0_evaluating-2-dnf-formulas-on-ciphertexts.pdf |
schemes | 17 | 224.9 KB | ce176fcea51d |
Database key: evaluating-2-dnf-formulas-on-ciphertexts · created 2026-11-05 · updated 2026-11-05 · edit with python3 tools/paperdb.py set evaluating-2-dnf-formulas-on-ciphertexts COLUMN VALUE