Let $N=pq$ be an RSA modulus, that is, $p$ and $q$ are large, distinct primes.
Let $J_{N}=\{y\in\mathbb{Z}^{*}_{N}:(\frac{y}{N})_{J}=1\}$ denote the set of all integers in $\mathbb{Z}^{*}_{N}$ with Jacobi symbol $1$.
The Quadratic Residuosity (QR) problem is to decide whether a given $y\in J_{N}$ is a quadratic residue modulo $N$ or not, that is, whether $y\in QR_{N}$, where $QR_{N}=\{y\in\mathbb{Z}^{*}_{N}:\exists z\in\mathbb{Z}^{*}_{N}, y=z^{2}\mod N\}$.
Consider the following bit commitment scheme: \begin{equation*}commit(u,x)=u^{2}y^{x}\mod N,\end{equation*} where $u\in_{R}\mathbb{Z}^{*}_{N}$, $y\in J_N$ is a quadratic non-residue and $x\in\{0,1\}$.
The commitment corresponds to ciphertexts in the Goldwasser–Micali public key cryptosystem.
The scheme is information-theoretically binding and computationally hiding.
The Question: Isn't this scheme computationally binding based on quadratic residue hardness assumption, and information theoretically hiding?
Reference: [Lecture Notes Cryptographic Protocols,: pages 33&101, Version 1.8, February 4, 2023, Berry Schoenmakers]
An attempt to show that the scheme is not binding if the sender be able to compute quadratic residue:
Let $y=r^{2}\mod N$, for sum $r\in\mathbb{Z}_{N}$ and the sender knows $r$.
Now the sender does the following: \begin{equation*}commit(ur,\color{blue}{x=0})=(ur)^{2}y^{x=0}=u^{2}r^{2}=u^{2}y^{x=1}=commit(u,\color{blue}{x=1})\mod N\end{equation*}


1 Answer 1


The answer in the notes is correct.

The ability to solve the quadratic residue problem would not enable an adversary to generate evidence of $x$ being other than the value committed to and so the binding property is stronger than this computational assumption.

The scheme is not information theoretically hiding, otherwise for any possible commitment value $c$ there would exist two numbers $u_0$ and $u_1$ such that $\mathrm{commit}(u_0,0)=c$ and $\mathrm{commit}(u_1,1)=c$. This would mean that $c$ is both a quadratic residue and a quadratic non-residue, which is not possible.

  • $\begingroup$ I've edited the question and have added a way to breaking the binding property if the sender knows how to solve the quadratic residue problem. Is that correct? $\endgroup$ Commented Jun 9, 2023 at 14:15
  • 1
    $\begingroup$ @user1035648 No, because as is explicitly stated in the exercise $y$ is a quadratic non-residue and so no such $r$ can exist. Further note that exhibiting such an $r$ (in the case where it does exist) is not known to be possible even when the quadratic residue problem is solvable. $\endgroup$
    – Daniel S
    Commented Jun 9, 2023 at 14:51
  • $\begingroup$ Yes, $y$ is a quadratic $\color{red}{non}$-residue. Thank you. $\endgroup$ Commented Jun 9, 2023 at 21:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.