Skip to content

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