Hiding and binding property of Goldwasser-Micali like bit commitment scheme

pt flag

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*}

ru flag

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.

user1035648 avatar
pt flag
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?
Daniel S avatar
ru flag
@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.
user1035648 avatar
pt flag
Yes, $y$ is a quadratic $\color{red}{non}$-residue. Thank you.
I sit in a Tesla and translated this thread with Ai:


Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.