PKE ⇒ COM

Fully-black-box reduction · standard model · folklore

Statement

Committing to $m$ as $(\mathsf{pk},c)$, where $(\mathsf{sk},\mathsf{pk})\leftarrow \mathsf{KeyGen}(1^{\lambda })$ and $c\leftarrow \mathsf{Enc}(\mathsf{pk},m;r)$, and opening with $(m,r)$, turns any perfectly correct CPA-secure PKE into a non-interactive commitment: hiding reduces tightly to CPA security, and binding is perfect for every $\mathsf{pk}$ in the support of $\mathsf{KeyGen}$. A malicious committer may choose a malformed $\mathsf{pk}$ unless keys are certifiable — folklore.

Sketch

A hiding distinguisher sees exactly $(\mathsf{pk},\mathsf{Enc}(\mathsf{pk},m_b))$, so it is a CPA adversary with the same advantage. Perfect correctness makes $c$ determine its plaintext: openings $(m_0,r_0),(m_1,r_1)$ of $c$ with $m_0\ne m_1$ would force $\mathsf{Dec}(\mathsf{sk},c)$ to equal both.

Notes

• Without perfect correctness or certifiable keys, PKE still yields commitments: PKE implies a one-way function IL89, hence a PRG HILL99, hence a two-message statistically binding commitment Naor91.