You are looking at a specific version 20121218:162455 of this paper. See the latest version.

Paper 2011/514

Milder Definitions of Computational Approximability: The Case of Zero-Knowledge Protocols

Mohammad Sadeq Dousti and Rasool Jalili

Abstract

Many cryptographic primitives---such as pseudorandom generators, encryption schemes, and zero-knowledge proofs---center around the notion of \emph{approximability}. For instance, a pseudorandom generator is an expanding function which on a random seed, \emph{approximates} the uniform distribution. In this paper, we classify different notions of computational approximability in the literature, and provide several new types of approximability. More specifically, we identify two hierarchies of computational approximability: The first hierarchy ranges from \emph{strong} approximability---which is the most common type in the cryptography---to the \emph{weak} approximability---as defined by Dwork \emph{et al.} (FOCS 1999). We define semi-strong, mild, and semi-weak types as well. The second hierarchy, termed $K$-approximability, is inspired by the $\varepsilon$-approximability of Dwork \emph{et al.} (STOC 1998). $K$-approximability has the same levels as the first hierarchy, ranging from strong $K$-approximability to weak $K$-approximability. While both hierarchies are general and can be used to define various cryptographic constructs with different levels of security, they are best illustrated in the context of zero-knowledge protocols. Assuming the existence of (trapdoor) one-way permutations, and exploiting the random oracle model, we present a separation between two definitions of zero knowledge: one based on strong $K$-approximability, and the other based on semi-strong $K$-approximability. Especially, we present a protocol which is zero knowledge only in the latter sense. The protocol is interesting in its own right, and can be used for efficient identification. Next, we show that our model for zero knowledge was \emph{not} closed under sequential composition, and change the model to resolve this issue. After proving a composition theorem, we finally provide a version of the identification protocol which satisfies the requirements of the new model. Some techniques provided in this paper are of independent interest, such as proving a composition theorem in the presence of both simulator and knowledge extractor.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Published elsewhere. Revised version is submitted to IEEE TC.
Keywords
ApproximabilityIndistinguishabilityZero KnowledgeRandom OracleTrapdoor One-Way PermutationSequential Composition.
Contact author(s)
msdousti @ gmail com
dousti @ ce sharif edu
History
2014-06-17: last of 2 revisions
2011-09-22: received
See all versions
Short URL
https://ia.cr/2011/514
License
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.