11
$\begingroup$

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?

Improve this question
$\endgroup$
1
  • 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$
    – Daniel Apon
    Aug 3, 2012 at 17:20

0

Reset to default

Your Answer

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