In the Section 3.12 of book writen by Boneh and Shoup, a Bit commitment from secure PRGs is presented as follow:

Bob commits to bit $b_0\in_R\{0,1\}$:

Step 1: Alice chooses a random $r\in R$ and sends $r$ to Bob.

Step 2: Bob chooses a random $s\in S$ and computes $c=com(s,r,b_0)$, where $com(s,r,b_0)$ is the ollowing function: $c=com(s,r,b_0):=\left\{ \begin{array}{rcl}G(s) & \mbox{if}& b_0=0 \\ G(s)\oplus r & \mbox{if} & b_0=1 \\ \end{array}\right.$, where $G:S\to R$ is a secure PRG and $|R|\geq |S|^3$.

Bob outputs $c$ as the commitment string and uses $s$ as the opening string.

At the reveal stage, when receiving $s$ and $b_0$ from Bob, Alice can check that indeed $c=com(s,r,b_0)$.

So, my question is that if we remove the value $r$ from the above scheme, which means:

  1. In Step 1. Alice does not have to send a random value to Bob, that makes the scheme non-interactive.
  2. In Step 2. if $b_0=1$ then Bob computes $c=G(s)\oplus k$, where $k=0...01\in R$ is a well-known constant and the first $|k|-1$ bits of $k$ are all zero.

is the modified version still secure or not? or in other words, can Bob cheat Alice?


1 Answer 1


You're asking specifically about the binding property ("can Bob cheat Alice?"). It's helpful to recall how binding is proven in Naor's scheme.

Suppose an adversary generates some commitment $c$. If they can open the commitment to 0 then there must exist $s_0$ such that $G(s_0) = c$. If they can open the commitment to 1 then there must exist $s_1$ such that $G(s_1) \oplus r = c$. Therefore, if they can open $c$ to both values then there must exist $s_0, s_1$ such that $G(s_0) \oplus G(s_1) = r$. If an adversary can equivocate, then it reflects something funny about $r$ more than it reflects something funny about $c$.

If a value of $r$ has the property above, let's call it "problematic." There are $2^{2\lambda}$ pairs $(s_0,s_1)$, and so at most $2^{2\lambda}$ problematic values of $r$. If $G$ is length-tripling then there are $2^{3\lambda}$ possible values of $r$ that Alice could choose. So when Alice chooses $r$ uniformly, she gets a problematic one with negligible probability $1/2^\lambda$. And as long as she avoids a problematic $r$, the commitment will be perfectly binding.

Now you propose to fix a specific $r$, for example as $r=0\cdots01$. The question is whether this $r$ can be problematic. Can there exist $s_0, s_1$ such that $G(s_0) \oplus G(s_1) = 0\cdots 01$? Sure! Just take your favorite PRG, and your two favorite strings $s_0$ and $s_1$, and redefine the PRG's output on $s_0$ and $s_1$ to have the property above. The modified function is still a PRG, but your modified Naor's scheme is insecure with this PRG (the adversary can depend on $s_0$ and $s_1$ because the adversary can depend on the choice of PRG of course).

So no, Naor's scheme is not secure in general when $r$ is fixed. For any $r$ that you'd like to fix, I can build a secure PRG that causes this modified Naor's scheme to be insecure. For extra credit, construct a secure PRG $G$ such that, for every possible output $G(s)$, the value $G(s)\oplus 0\cdots01$ is also a possible output of $G$.

  • $\begingroup$ A huge thank you for your answer. You solved many of my doubts on security proof in Naor's paper. However, I still have two problems: one is that if they both used a public secure PRG, such as the Salsa PRG, I think finding two distinct $s_0,s_1$ s.t. $G(s_0)=G(s_1)\oplus r$, where $r$ is a fixed value and well known, is infeasible in probability polynomial time. The other question is that does your last sentence imply that such modified commitment exists by using the secure PRG you describe? $\endgroup$
    – ming alex
    May 6 at 4:33
  • 1
    $\begingroup$ If the PRG is "natural" (non-pathological) and $r$ is chosen after the PRG is fixed then it might be reasonable to make that assumption (that it's hard to find $s_0$ and $s_1$ with that property). But it would be highly non-standard, especially if $r$ is something simple like $0\cdots 01$. My last sentence implies that there is a secure PRG for which every honest Naor commitment (with fixed $r=0\cdots01$) can be equivocated easily. $\endgroup$
    – Mikero
    May 6 at 5:26
  • $\begingroup$ Ok, I see what you mean. The assumption of my proposal is too strong to be pratical. so, it is not a general method. Thank you again! $\endgroup$
    – ming alex
    May 6 at 6:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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