Alternative variants of zero-knowledge proofs

by Pass, Rafael

Zero-knowledge proofs are one of the most important cryptographic notions. Since their introduction in the early 80's by Goldwasser, Micali and Racko , they have proven very useful in the design of cryptographic protocols. Nevertheless, many limitations (in terms of e ciency and robustness under concurrent executability of protocols) have also been noticed. In order to overcome these limitations two lines of research have been investigated in the literature: 1. Models with some limited intervention of a trusted party (for example during a set-up phase). 2. Weakenings of the notion of zero-knowledge. In this thesis we attempt to further the understanding of the notion of zero-knowledge proofs by addressing both the above lines of research. More precisely, 1. Concerning the rst line of research, we show that the de nition of zeroknowledge in certain popular models (namely the Common Reference String and Random Oracle Models) captures a somewhat di erent semantics than the standard zero-knowledge de nition. In particular, we show that there exists a certain natural security property that is captured by the standard de nition, but not by these new de nitions. This isthepropertyofdeniability, whichintuitivelymeansthataninteraction between two parties does not leave any trace . We then focus on investigating the possibility of obtaining deniable zero-knowledge protocols in these models. 2. Concerning the second line of research, we propose a new and di erent weakeningofthenotionofzero-knowledgeproofs. Thisweakeningallows us to a) overcome known impossibility results concerning the notion of zero-knowledge, while b) providing an almost as strong security guarantee. iii