Optimal multi-bit commitment reductions to weak bit commitments
Anderson C. A. Nascimento, Joern Mueller-Quade, Hideki Imai
Bit commitments are very fundamental protocols in modern cryptography. In this paper, we introduce a model to study bit commitment schemes with a probability of failure (we call them, weak bit commitments). We characterize when it is possible to reduce bit commitments to weak bit commitments. We introduce a new concept in cryptographic reductions called the rate. We prove that our reductions are optimal regarding the rate. Additionally, we show that, when written in the appropriate way, several reductions among cryptographic primitives are equivalent to well known problems in Shannon theory.
IEEE International Symposium on Information Theory (ISIT)•Jun 25, 2003•1 citation