Bit Commitment Using Pseudorandomness

URL: https://link.springer.com/article/10.1007/BF00191386 Authors: Moni Naor

Abstract

We show how to construct a bit commitment protocol from any pseudorandom generator. More specifically, a sender can commit to a bit $b$ such that (1) the receiver cannot determine $b$ before the opening phase (hiding); and (2) after committing, the sender cannot change $b$ (binding). The construction is non-interactive and assumes only the existence of pseudorandom generators (and hence one-way functions). The commitment is perfectly binding and computationally hiding.