2
$\begingroup$

I'm wondering the state-of-art result about how many bits are needed to commit a single-bit non-interactively? I noticed in the paper of Naor's bit commitment: http://www.wisdom.weizmann.ac.il/~naor/PAPERS/bit.pdf this paper says assured amortized O(1) bits of communication per bit commitment. However, it seems Naor's bit commitment has interactive commitment phase. Thus I'm wondering the state-of-art result about this research direction. How many bits of communication per bit commitment should be sent non-interactively in the standard model?

I'm only interested in non-interactive bit commitment assuming one-way function not assuming DDH like Pedersen commitment.

$\endgroup$
  • $\begingroup$ The answer is not a constant number of bits, but a function of the security level. I'm not sure about what is asked: results for practical conjecturally secure systems like Pedersen commitment using an Elliptic Curve, or some theoretical bound? $\endgroup$ – fgrieu Dec 11 '18 at 6:04
  • 1
    $\begingroup$ @fgrieu I'm curious about the theoretical bound. Sorry for unclear question. Actually I meant the number of bits of communication for non-interactive bit commitment from one-way function in the standard model (i.e., without assuming random oracle or common reference string .etc) $\endgroup$ – CryptoLover Dec 11 '18 at 6:51
2
$\begingroup$

The state of the art regarding non-interactive bit commitment from OWF is quite simple: it is known to be impossible (at least using black box reductions) to build non-interactive commitments from one-way functions (see e.g. this paper).

Are you specifically interested in constructions from generic one-way function, or are you ok with more structured assumptions, such as one-way permutations (which do imply non-interactive commitments)? If you are also interested in OWP (or even one-to-one OWF), then I think the state-of-the-art generic construction of a NIBC is the direct application of the Goldreich-Levin theorem: to commit to $b$, given any OWP $f:\{0,1\}^n\mapsto \{0,1\}^n$, pick random $(x,r)$ and return $(f(x), r, \langle x, r\rangle \oplus b)$. The communication is $2n+1$ bit per bit committed. If you want to commit to a single bit, I do not know of any better solution. When amortizing, however, there might be better approaches - for example, you can at least commit to $\log(n)$ bits at once using a single $x$ and $\log(n)$ different $r$'s, lowering the communication to $n(1+o(1))$. I don't know if there is anything better generically (getting more hardcore bits from the Goldreich-Levin construction seems hopeless, but perhaps a completely different approach can help).

From collision resistant hash functions, at least, this papers provides a construction of a non-interactive commitment with $O(1)$ amortized communication - but their construction still requires a one-time interactive setup phase, the commitment scheme only becomes non-interactive after that.

$\endgroup$

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.