I would like to use a PRG in order to achieve the commitment properties (i.e. Hiding and Binding), however, if we look at a general PRG we cannot state that it has the Binding property.

First I show that it could be shown that it has the Hiding property: given the PRG result on a random seed $s$, i.e. given $g=PRG(s)$, the receiver cannot tell the pre-image of $g$ with more than negligible probability since if there exist a receiver that can produce the pre-image than we can construct a distinguisher to the PRG with the same probability of success.

On the other hand, if we look at the binding property, we cannot state the above, since there exist PRGs that output the same result when operating on seed $s$ and when operating on seed $s+1$ for every even $s$. This can be easily proven. (And thus, the sender surely can commit on even $s$ and later open $s+1$).

My question: Does there exist a variant of a PRG that is proven to provide the commitment properties?

  • $\begingroup$ en.wikipedia.org/wiki/… $\;$ $\endgroup$ – user991 Dec 11 '14 at 9:18
  • $\begingroup$ Thanks for the reference, this is too theoretically though. I'm looking for more practical/simple/efficient use of PRG, I mean that that the protocol is non-interactive - the only message is from the sender (committer) to the receiver , and the committed value is a bit-string rather than one bit. $\endgroup$ – Bush Dec 11 '14 at 9:30
  • $\begingroup$ There does not "exist a variant of a PRG that is proven to provide the commitment properties", since $\hspace{.13 in}$ there does not exist any plain-model protocol "that is proven to provide the commitment properties". $\hspace{.32 in}$ $\endgroup$ – user991 Dec 11 '14 at 9:39
  • $\begingroup$ I'm not sure that I understand you last comment, by "plain model" you mean that there does not exist a proven commitment scheme that is not relying on some assumption? (like one-way-function) $\endgroup$ – Bush Dec 11 '14 at 9:42
  • $\begingroup$ By "plain model", I mean without stuff like sufficiently-fair noisy channels, physical unclonable functions, tamper-evident seals, or assuming that there's sufficient noise in the receiver's quantum storage. $\hspace{.55 in}$ $\endgroup$ – user991 Dec 11 '14 at 9:51

Your Answer

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

Browse other questions tagged or ask your own question.