Security

Commitments and Efficient Zero-Knowledge Proofs From Learning Parity with Noise

Date Added: Sep 2012
Format: PDF

Commitment schemes and zero-knowledge proofs are fundamental cryptographic primitives. In this paper, the authors propose a simple string commitment scheme and show efficient zero-knowledge proofs for any relation amongst committed values. The security (more precisely, the computational hiding property) of their commitment scheme relies on the Learning Parity with Noise (LPN) assumption, or equivalently, on the hardness of decoding random linear codes. They construct a perfectly binding string commitment scheme whose security is based on the Learning Parity with Noise (LPN) assumption, or equivalently, the hardness of decoding random linear codes.