DCR ⇒ COM

Fully-black-box reduction · standard model · folklore

Statement

DCR implies a non-interactive commitment scheme of either flavour, both of Paillier form: for a well-formed RSA modulus $n$ and a base $g\in {\mathbb{Z}}_{n^2}^{\ast }$ in the public parameters, a commitment to $m\in {\mathbb{Z}}_n$ is $c=g^m\cdot r^n\mathrm{mod}{n}^2$ for $r\stackrel{\$}{\leftarrow }{\mathbb{Z}}_n^{\ast }$, opened by revealing $(m,r)$. With $g=1+n$ it is perfectly binding and computationally hiding; with $g$ a random $n$-th residue it is perfectly hiding and computationally binding — folklore.

Sketch

With $g=1+n$, $(m,r)\mapsto c$ is a bijection ${\mathbb{Z}}_n\times {\mathbb{Z}}_n^{\ast }\to {\mathbb{Z}}_{n^2}^{\ast }$, so binding is perfect, and hiding is IND-CPA security of Paillier encryption under DCR (Pai99). With $g$ a random $n$-th residue, $c$ is a uniform $n$-th residue independent of $m$; under a uniform $g$ binding is statistical, so a committer that opens one $c$ two ways distinguishes the DCR challenge $g$ from uniform.

Notes

• In the perfectly hiding flavour, $g$ is a common reference string, or is chosen by the receiver with a proof that it is an $n$-th residue — folklore.