STATISTICAL SECRECY AND MULTIBIT COMMITMENTS

We present and compare definitions of ''statistically hiding'' protoco ls, and we propose a novel statistically hiding commitment scheme. Inf ormally, a protocol statistically hides a secret if a computationally unlimited adversary who conducts the protocol with the owner of the se cret learns almost nothing about it. One definition is based on the L- 1-norm distance between probability distributions, the other on inform ation theory. We prove that the two definitions are essentially equiva lent. We also show that statistical counterparts of definitions of com putational secrecy are essentially equivalent to our main definitions; Commitment schemes are an important cryptologic primitive. Their purp ose is to commit one party to a certain value, while hiding this value from the other party until some later time. We present a statisticall y hiding commitment scheme allowing commitment to many bits. The commi tment 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 co urse for the bits needed to send the secret when it is revealed. The p roof of the hiding property exploits the equivalence of the two defini tions.