# How many bits are needed to commit one bit non-interactively in the standard model?

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.

• 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?
– fgrieu
Dec 11 '18 at 6:04
• @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) Dec 11 '18 at 6:51

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.