TY - JOUR
AU - Ivan Damgård
AU - Torben Pedersen
AU - Birgit Pfitzmann
PY - 1996/06/15
Y2 - 2019/10/15
TI - Statistical Secrecy and Multi-Bit Commitments
JF - BRICS Report Series
JA - BRICS
VL - 3
IS - 45
SE - Articles
DO - 10.7146/brics.v3i45.20047
UR - https://tidsskrift.dk/brics/article/view/20047
AB - We present and compare definitions of the notion of "statisticallyhiding" protocols, and we propose a novel statistically hiding commitmentscheme. Informally, a protocol statistically hides a secret if acomputationally unlimited adversary who conducts the protocol withthe owner of the secret learns almost nothing about it. One definitionis based on the L1-norm distance between probability distributions,the other on information theory. We prove that the two definitions areessentially equivalent. For completeness, we also show that statisticalcounterparts of definitions of computational secrecy are essentiallyequivalent to our main definitions. Commitment schemes are an important cryptologic primitive. Their purpose is to commit one party to a certain value, while hiding this value from the other party until some later time. We present a statisticallyhiding commitment scheme allowing commitment to manybits. The commitment and reveal protocols of this scheme are constantround, and the size of a commitment is independent of the number ofbits committed to. This also holds for the total communication complexity,except of course for the bits needed to send the secret when itis revealed. The proof of the hiding property exploits the equivalenceof the two definitions.Index terms -- Cryptology, Shannon theory, unconditional security,statistically hiding, multi-bit commitment, similarity of ensemblesof distributions, zero-knowledge, protocols.
ER -