In "Multi-Prover Interactive Proofs: How to Remove Intractability Assumptions" by Ben-Or, Goldwasser, Kilian, and Wigderson, the authors introduce a bit commitment protocol as a subroutine to their Theorem 1 that every language in NP has a perfect zero-knowledge protocol in the two-prover model. The protocol is presented as a bit commitment scheme, which generalizes to a commitment scheme for arbitrary data by the well-known fact that all we are is 0s and 1s. My question is about the existence of more "direct" generalizations. Specifically, it seems to me that the protocol is based on some simple facts about the finite fields ${\bf Z}_2$ and ${\bf Z}_3$, and I was wondering whether anyone has worked out how to abstract away these facts and generalize the commitment scheme to values over larger finite fields?

  • 2
    $\begingroup$ Here's a relatively removed question (though possibly still of interest) in the same theme... Question: Has the Goldreich-Levin theorem (ie, the existence of hard-core predicates over $\mathbb{Z}_2$) been extended to larger fields? Answer: Yes, but only somewhat recently. See the TCC 2010 paper: cs.toronto.edu/~vinodv/auxinput.pdf $\endgroup$ Aug 3, 2012 at 17:20


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.