We present and compare definitions 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 L/sub 1/-norm distance between probability distributions, the other on information theory. We prove that the two definitions are essentially equivalent. 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.
We present and compare definitions 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 L/sub 1/-norm distance between probability distributions, the other on information theory. We prove that the two definitions are essentially equivalent. 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.
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.
Commitment schemes are one of the basic building blocks to construct secure protocols for multi party computation. Many recent works are exploring hardware primitives like physically unclonable functions to build keyless cryptographic protocols, with minimal assumptions. The asymmetric nature and non-invertibility property of PUFs are widely exploited to build oblivious transfer protocols that are extended to build bit-commitment schemes. However, these schemes require the physical transfer of the PUF device between the interacting parties. In this work, we introduce a new class of hardware-based primitives called physically related functions that enable hardware circuits to securely communicate with each other over insecure channels. We propose a bit-commitment protocol based on this hardware primitive without needing any physical transfer. Our scheme is statistically hiding and computationally binding, requiring only one round of communication while being practically deployable. We explore the security properties of physically related functions, under which we prove the security of our scheme. We experimentally show that it is impossible to break the security of the scheme with more than negligible probability.
Non-malleable commitment is one of the most fundamental cryptographic primitives in that it is often used as a basic building block in modern cryptography. Briefly, a commitment scheme allows a sender to commit to a value while keeping the value secret from the receiver. In addition, when the commitment is opened in a later stage, the scheme guarantees that the sender can reveal only the unique value being committed to in the previous stage. A commitment scheme is said to be non-malleable if no adversary can succeed in committing to a related massage m', after seeing a commitment of a message m. In this dissertation, we study the construction of non-malleable commitments and some of their applications.A black-box construction of non-malleable commitment is presented in the first part of this dissertation. Our protocol requires only a constant number of rounds and satisfies the standard notion of non-malleability w.r.t. commitment. Our technique is based on ideas from the ``zero-knowledge from secure multi-party computation'' paradigm by Ishai, Kushilevitz, Ostrovsky, and Sahai (STOC 2007). Furthermore, our construction only uses one-way functions as a black-box and thus does not depend on the actual implementation details of the functions. Prior to our result, under the standard notion of security, no black-box construction of constant-round non-malleable commitment was known. Hence, our main result closes the gap between black-box and non-black-box constructions for the problem of non-malleable commitment.In the second part of this dissertation, we show that our technique can be applied to multiple applications. Specifically, we extend our work to obtain a constant-round concurrent non-malleable commitment, a constant-round multi-party parallel coin tossing, and a non-malleable statistically hiding commitment (according to the notion of non-malleability w.r.t. opening.) Additionally, all results mentioned above are based only on a black-box use of one-way functions.
We provide a non-interactive quantum bit commitment scheme which has statistically-hiding and computationally-binding properties from any quantum one-way function. Our protocol is basically a parallel composition of the previous non-interactive quantum bit commitment schemes (based on quantum one-way permutations, due to Dumais, Mayers and Salvail (EUROCRYPT 2000)) with pairwise independent hash functions. To construct our non-interactive quantum bit commitment scheme from any quantum one-way function, we follow the procedure below: (i) from Dumais-Mayers-Salvail scheme to a weakly-hiding and 1-out-of-2 binding commitment (of a parallel variant); (ii) from the weakly-hiding and 1-out-of-2 binding commitment to a strongly-hiding and 1-out-of-2 binding commitment; (iii) from the strongly-hiding and 1-out-of-2 binding commitment to a normal statistically-hiding commitment. In the classical case, statistically-hiding bit commitment scheme (by Haitner, Nguyen, Ong, Reingold and Vadhan (SIAM J. Comput., Vol.39, 2009)) is also constructible from any one-way function. While the classical statistically-hiding bit commitment has large round complexity, our quantum scheme is non-interactive, which is advantageous over the classical schemes. A main technical contribution is to provide a quantum analogue of the new interactive hashing theorem, due to Haitner and Reingold (CCC 2007). Moreover, the parallel composition enables us to simplify the security analysis drastically.
We study the round and communication complexities of various cryptographic protocols. We give tight lower bounds on the round and communication complexities of any fully black-box reduction of a statistically hiding commitment scheme from one-way permutations and from trapdoor permutations. As a corollary, we derive similar tight lower bounds for several other cryptographic protocols, such as single-server private information retrieval, interactive hashing, and oblivious transfer that guarantees statistical security for one of the parties. Our techniques extend the collision-finding oracle due to Simon [Advances in Cryptology---EUROCRYPT'98, Lecture Notes in Comput. Sci. 1403, Springer, Berlin, 1998, pp. 334--345] to the setting of interactive protocols and the reconstruction paradigm of Gennaro and Trevisan [Proceedings of the 41st Annual Symposium on Foundations of Computer Science (FOCS), IEEE Press, Piscataway, NJ, 2000, pp. 305--313].
Commitment schemes are fundamental building blocks in cryptography, and have wide applications in constructing various protocols. Non-malleable commitment considers concurrent executions of a commitment scheme against a man-in-the-middle adversary. In this paper, we investigate non-malleability of statistically hiding commitment schemes, and present the first concurrent non-malleable statistically hiding commitment scheme. Our protocol admits black-box simulation, and relies on the robust (stand-alone) non-malleable commitment and specially designed witness indistinguishable proofs to achieve concurrent non-malleability. Based on the one-way function assumption, the commit phase of our protocol needs polynomial rounds, and the decommit phase needs super-logarithmic rounds.