PRG ⇒ COM

Fully-black-box reduction · standard model · Naor91 · security loss: hiding: at most twice the PRG advantage; binding: statistical, error at most $2^{-\lambda }$

Statement

A length-tripling PRG $G:\{0,1{\}}^{\lambda }\to \{0,1{\}}^{3\lambda }$ yields a statistically binding bit commitment, computationally hiding for every $\mathsf{pp}$: the receiver sends $\mathsf{pp}\stackrel{\$}{\leftarrow }\{0,1{\}}^{3\lambda }$; the committer samples $s\stackrel{\$}{\leftarrow }\{0,1{\}}^{\lambda }$ and sends $G(s)$ to commit to $0$ or $G(s)\oplus \mathsf{pp}$ to commit to $1$; opening reveals $(b,s)$ — Naor91.

Sketch

Hiding: $G(s)$ and $G(s)\oplus \mathsf{pp}$ are each one PRG hybrid from uniform, so commitments to $0$ and $1$ are two hybrids apart. Binding: opening to both bits requires seeds $s_0,s_1$ with $G(s_0)\oplus G(s_1)=\mathsf{pp}$; at most $2^{2\lambda }$ of the $2^{3\lambda }$ strings $\mathsf{pp}$ admit such a pair, so binding fails with probability at most $2^{-\lambda }$ over the receiver’s message.

Notes

• The commit phase is interactive: the receiver sends $\mathsf{pp}$ first, so binding uses that an honest receiver samples $\mathsf{pp}$ uniformly, while hiding holds for every $\mathsf{pp}$ — Naor91.
• Efficiency: committing to one bit costs one evaluation of $G$ and $3\lambda$ bits of communication. One receiver message $\mathsf{pp}$ serves any number of commitments, since binding fails only for the at most $2^{-\lambda }$ fraction of strings $\mathsf{pp}$ that admit two openings — standard.