A Study Of Precise Zero-Knowledge

Zero-knowledge proofs are a fascinating notion and have extremely wideapplications in modern cryptography. This notion reveals two seemingly para-doxical properties, i.e., a zero-knowledge proof can convince an effcient verifierto accept a valid assertion but it cannot learn anything more from the proof. Theproperty of zero-knowledge is captured by the idea that the view of polynomial-time verifiers in interaction can be reconstructed still in polynomial-time. So itcan be seen that zero-knowledge is formalized as a worst case notion. However,some literatures showed this characterization of zero-knowledge is not precise.Thus a new notion of precise zero-knowledge was introduced. This notion cap-tures the idea that what verifier sees in the interaction can be reconstructed by asimulator in almost same time. Hence it can be seen that this new notion char-acterizes the property of zero-knowledge more precisely. Further, the notion ofprecise concurrent zero-knowledge was proposed recently, which generalizes theprecise zero-knowledge from stand-alone setting to concurrent setting.In this thesis we investigate some aspects of precise zero-knowledge, whichinclude bounded-concurrent composition, communication complexity of precisezero-knowledge protocols, sequential composition of precise zero-knowledge andnew approaches towards defining precise simulation. In the first aspect, we askwhether there are precise concurrent zero-knowledge protocols with lower roundcomplexity for NP, even in bounded-concurrent setting and whether there areprecise bounded-concurrent zero-knowledge proofs for NP. In the second aspect,we ask whether there is an approach of reducing the communication complexity ofprecise zero-knowledge protocols. In the third aspect, we ask whether sequentiallycomposed precise zero-knowledge protocols can own tight precisionsff In thefourth aspect, we ask whether these is a different way to define precise simulationfrom the known notion of precise zero-knowledge.The following are the main results of this thesis, all of which employ the use of non-black-box techniques.Precise Bounded-Concurrent Zero-Knowledge Arguments Bounded con-currency means an a-priori bound on the (polynomial) number of concur-rent sessions is specified before the protocol is constructed. The known(precise) concurrent zero-knowledge protocols use super logarithmic rounds,even in bounded-concurrent setting.Since round complexity is one of the most important criteria for protocols,in this thesis we investigate whether there are precise bounded-concurrentzero-knowledge protocols with lower round complexity. We answer thisquestion affrmatively. We construct the first public-coin precise bounded-concurrent zero-knowledge argument system for NP only using almost con-stant rounds.Precise Bounded-Concurrent Zero-Knowledge Proofs All known preciseconcurrent zero-knowledge protocols are arguments, which means the sound-ness only holds against polynomial-time adversaries. We construct the firstprecise bounded-concurrent zero-knowledge proof for NP. The advantageof proofs over arguments is that the soundness property of proof systemscan resist computationally-unbounded adversarial provers.Precise Zero-Knowledge with Poly-logarithmic Effciency All known pre-cise zero-knowledge protocols use polynomial communication complexity.That is, all communicated messages of these protocols are polynomial bits.Since communication complexity is another important criterion for proto-cols, in this thesis we investigate how to reduce communication complex-ity of precise zero-knowledge protocols. We combine the new simulationtechnique introduced by Micali and Pass with a slightly modified Kilian'sconstruction of zero-knowledge arguments with poly-logarithmic commu-nicated bits, and then we show there are zero-knowledge arguments withpolynomial or linear precision and poly-logarithmic effciency. This showsfor precise zero-knowledge arguments the communicated bits can be re-duced to poly-logarithm.On Sequential Composition of Precise Zero-Knowledge The known sequen- tial composition lemma of precise zero-knowledge shows that the sequen-tial execution of any precise zero-knowledge protocol is still precise zero-knowledge. However, it cannot provide tight precisions for composed pro-tocols. In this thesis, we prove a sequential composition lemma for a classof precise zero-knowledge protocols, which are characterized by a new no-tion of emulated black-box precise zero-knowledge. Our lemma providestight precisions for composed protocols. Since many known precise zero-knowledge are emulated black-box, our result still has generality.Precise Time and Space Simulatable Zero-Knowledge The definition ofprecise zero-knowledge explicitly considers running-time used by the veri-fier and the simulator. However, as we know, there are two kinds of com-putational resources (i.e. time and space) that every algorithm consumesin computation. Since the known works didn't investigate the precise simu-lation with respect to the running-space, their simulators cannot automat-ically provide simultaneous meaningful time and space precisions.In this paper, we propose a new notion of precise time and space simulatablezero-knowledge (PTSSZK), which captures the idea that the view of anyverifier in each interaction can be reconstructed not only in the same time,but also in the same space. We construct the first PTSSZK proofs andarguments with simultaneous linear time and linear space precisions for alllanguages in NP.In the last part of this thesis we conclude our works and put forward somefuture investigations.