Statistical Secrecy and Multi-Bit Commitments

Abstract

We present and compare definitions of the notion of "statistically
hiding" protocols, and we propose a novel statistically hiding commitment
scheme. Informally, a protocol statistically hides a secret if a
computationally unlimited adversary who conducts the protocol with
the owner of the secret learns almost nothing about it. One definition
is based on the L1-norm distance between probability distributions,
the other on information theory. We prove that the two definitions are
essentially equivalent. For completeness, we also show that statistical
counterparts of definitions of computational secrecy are essentially
equivalent 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 statistically
hiding commitment scheme allowing commitment to many
bits. The commitment and reveal protocols of this scheme are constant
round, and the size of a commitment is independent of the number of
bits committed to. This also holds for the total communication complexity,
except of course for the bits needed to send the secret when it
is revealed. The proof of the hiding property exploits the equivalence
of the two definitions.

Index terms -- Cryptology, Shannon theory, unconditional security,
statistically hiding, multi-bit commitment, similarity of ensembles
of distributions, zero-knowledge, protocols.