Problem: Many cryptographic protocols require one party to commit to value $x$ in a way

that $($a$)$ does not leak information about $x$ to any party observing the commitment string, and $($b$)$

does not allow the commiting party to later "open" the commitment string to reveal value $x^{\text{'}}x.$

In other words, $x$ remains secret until it is opened, and the commiting party cannot cheat. This is

the job of a cryptographic commitment scheme. Here is an example.

Let $p=2q+1$ be a $($large$)$ prime, with $q$ prime. As you know, there is an order$-q$ subgroup of $Z_p^{**}$

called the quadratic residues, i$.$e$.,QR(p).$ Let $g$ be a generator of $QR(p),$ and assume that $p,q,g$

are all public.

To set up our commitment scheme, Bob samples an integer $alar{r}^{\text{\$}}\{0,1,$dots,$q-1\}$ and sends $h=g^a$

to Alice.

When Alice wants to commit to a value xin$\{0,1,$dots,$q-1\},$ she does the following. She picks an

integer $rlar{r}^{}\{0,1,$dots,$q-1\},$ and sends $clarr{g}^x{h}^r$ to Bob. $($Note that, by the definition of $h,$ we

have $c=g^{x+ra}.)$ This $c$ is her commitment to $x$; let's see why.

Part $($a$).$ Explain why Alice's commitment $c$ leaks nothing about $x$ to Bob. In particular, show

that for any $,in\{0,1,$dots,$q-1\},$ we have

$Pr[x=|c]=Pr[x=|c].$

Part $($b$).$ When Bob demands that Alice open the commitment $c,$ Alice sends him a pair of

exponents $(u,v).$ Bob checks that both $u,$vin$\{0,1,$dots,$q-1\}$ and $g^u{h}^v=c$ hold. Now, if Alice is

honest, she will send $(u,v)=(x,r).($Verify that these will pass Bob's checks!$)$ But she may try to

"cheat" by sending a $ux,$ i$.$e$.,$ she may try to trick Bob into thinking that she committed to $u,$

rather than to $x.$ Show that Alice cannot do this, unless she can break the discrete$-$log assumption

in $QR(p).$

In particular, show that if Alice knew $(x,r),(u,v)in(\{0,1,$dots,$q-1\}{)}^2$ such that $(1)xu$ and

$(2)c=g^x{h}^r=g^u{h}^v,$ then she could also compute the discrete $log$ of $h=g^a,$ i$.$e$.,$ she can compute

$lo{g}_{g}h=lo{g}_g{g}^a=a,$ where $($recall$)$ Bob had randomly chosen a during setup.

Since we believe that the DDH assumption holds in large prime$-$order groups $($e$.$g$.,$ QR $(p)$ for

sufficiently large prime $q=\frac{p-1}{2},$ and DDH implies DL$,$ Alice should not be able to cheat. If

she commits to $x,$ then she can only open $c$ to $x.$