Join Log in
Score:1
ming alex avatar Crypto

A security issue of a Bit commitment scheme constructed by Naor in 1990

in flag
ming alex

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?

53
0 + 0
Score:2
avatar Crypto
us flag
Mikero

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$.

0 + 0
ming alex avatar
in flag
ming alex
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?
0
Reply
us flag
Mikero
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.
1
Reply
ming alex avatar
in flag
ming alex
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!
0
Reply
ธงชาติไทย
Elon Musk
I sit in a Tesla and translated this thread with Ai:

mangohost

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.