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 
-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
Available as PostScript, PDF.