FREE ELECTRONIC LIBRARY - Abstracts, online materials

Pages:   || 2 | 3 | 4 |

«Lower Bounds for Zero Knowledge on the Internet Joe Kilian ∗ Erez Petrank † Charles Rackoff‡ arXiv:cs/0107003v1 [cs.CR] 2 Jul 2001 February 26, ...»

-- [ Page 1 ] --

Lower Bounds for Zero Knowledge on the Internet

Joe Kilian ∗ Erez Petrank † Charles Rackoff‡

arXiv:cs/0107003v1 [cs.CR] 2 Jul 2001

February 26, 2008


We consider zero knowledge interactive proofs in a richer, more realistic communication

environment. In this setting, one may simultaneously engage in many interactive proofs, and

these proofs may take place in an asynchronous fashion. It is known that zero-knowledge is

not necessarily preserved in such an environment; we show that for a large class of protocols, it cannot be preserved. Any 4 round (computational) zero-knowledge interactive proof (or argument) for a non-trivial language L is not black-box simulatable in the asynchronous setting.

1 Introduction Zero knowledge [20] turned out to be a useful tool for many cryptographic applications. Many works have studied the numerous uses of zero knowledge proofs, and many other works have suggested how to improve the efficiency of these proofs. However, most of these works considered only the case where the proof stands alone, disconnected from the computing environment. An interesting question, which naturally arises these days, is how robust the notion of zero knowledge is in a broader setting. In particular, many computers today are connected through networks (from small local area networks to the entire Internet) in which connections are maintained in parallel asynchronous sessions. It is common to find several connections (such as FTP, Telnet, An internet browser, etc.) running together on a single workstation. Can zero knowledge protocols be trusted in such an environment?

The robustness of zero knowledge has been studied before in the “simple” case of parallel repetitions. It is often desirable to run a probabilistic protocol many times in parallel, usually in order to reduce the expected error of a single run. The alternative of running these protocols sequentially has a cost of increasing the number of rounds and is considered inefficient. It had been noted by several researchers that even in the parallel repetitions case the zero knowledge

property does not necessarily hold. Goldreich and Krawczyk [16] proved a general lower bound:

Any language that has a three round (black-box) zero-knowledge interactive proof with a small error probability (as can be obtained by parallel repetitions) is in BPP. Thus, for example, unless ∗ Yianilos Labs, joe@pnylab.com. Work done in part while at the NEC Research Institute.

Dept. of Computer Science, Technion - Israel Institute of Technology, Haifa 32000, Israel. Email:


Dept. of Computer Science, University of Toronto, Toronto, Ontario, Canada M5S 3G4. Email:


Graph Isomorphism is in BPP, the protocol of [17] for Graph Isomorphism does not remain zero knowledge when run many times in parallel. Several papers have dealt with this problem, usually by letting the verifier commit on it’s (non-adaptive) questions in advance [1, 3, 15, 12].

Our initial feeling was that the protocols that keep their zero knowledge property when run in parallel should also remain zero knowledge even in a multi-session asynchronous environment.

However, in this paper, we give some indications that this is not always the case.

Let us say a few words about what we need to show. In order to show that a protocol is zero knowledge in a modern networking environment, one must provide a proof that even within this complicated environment the protocol is still zero knowledge. But for us matters are simpler. We don’t need to cover all facets of a networking environment. We only have to show that zero knowledge may fail in a specific setting that is part of this environment. Namely, the environment may be more hostile to the protocol than the specific case we study, but since a protocol fails even with a benign setting, it is definitely not zero knowledge when we extend the power of the environment.

In particular, a networking environment may have various protocols running, multiple sessions, more than two parties involved, asynchronous setting, etc.

We show that zero knowledge may fail for a large class of protocols, even if we only run a single protocol between only two parties. We exploit the asynchronicity and the existence of multiple sessions. Clearly, if we also add other features, such as additional parties and other protocols running in parallel, then the security problems can only be amplified.

We show that any four-round black-box zero-knowledge proof with perfect completeness is not zero knowledge even in a very benign setting: The setting in which the protocol is run many times in an asynchronous environment, and an adversary (or the verifier) gets to choose which message gets to be delivered next. Actually, the setting is even more benign: We set a specific schedule, known in advance to both prover and verifier. Still, if the protocol can be (black-box) simulated, then the language must be in BPP.

Theorem 1 Suppose that (P, V ) is a 4-message interactive proof or argument for L with perfect completeness and error at most 1 and suppose that (P, V ) can be black-box simulated in the asynchronous setting. Then L ∈ BP P.

The 2 in the above statement may be replaced by any constant less than 1, with essentially no change to our proofs; with slight care, any error bounded away from 1 by a non-negligible factor may be accommodated.

The above result holds for all extensions of concurrent zero-knowledge. In particular, it holds for resettable zero-knowledge [5].

Note that we get a separation between protocols that remain zero knowledge even under parallel repetition and protocols that remain zero knowledge in an asynchronous setting. Assuming the existence of one-to-one one-way functions, there exist 4-message (computational) zero knowledge arguments for all NP languages [12]. However, there are no 4-message zero knowledge arguments for languages outside of BPP that are black box simulatable in the asynchronous setting.

Some words on the terminology we are using. By zero knowledge we mean computational zero knowledge, i.e., the distribution output by the simulation is polynomial-time indistinguishable from the distribution of the views of the verifier in the original interaction. (Of-course, as the result is a lower bound, it holds also for perfect and statistical zero knowledge.) The prover may be infinitely powerful (i.e., an interactive proof) or it may be computationally bounded (i.e., an argument). We consider black box zero knowledge as defined by Goldreich and Oren [24, 18], and refined in [16].

1.1 Related work Dwork, Naor, and Sahai [10] were the first to explore zero-knowledge in the asynchronous setting.

They denoted zero-knowledge protocols that are robust to asynchronous composition concurrent zero-knowledge protocols. It was noticed in [10] that several known zero-knowledge proofs, with a straightforward adaptation of their original simulation to the asynchronous environment, may cause the simulator to work exponential time. Thus, it seems that the zero-knowledge property does not necessarily carry over to the asynchronous setting. In order to provide a protocol that may be used in a modern environment, they presented a compromise: a protocol that is not zeroknowledge in a fully asynchronous setting, but is zero-knowledge in an environment with bounds on the asynchronisity. In particular, they present a 4 round zero-knowledge argument for NP assuming that there are two constants α and β such that the fastest message arrives within time at least α and the slowest message arrives within time at most β.

Dwork and Sahai [11] reduced the limitation on the asynchronisity. They presented a proof which has a preprocessing phase and a proof-body phase. Their proof is concurrent zero-knowledge argument for NP such that the (α, β) limitation is required only during the preprocessing stage.

Then, the body of the proofs can be run in a fully asynchronous environment.

Our result is complementary to theirs, illustrating why it is difficult to achieve zero-knowledge in the asynchronous setting without using such an augmented model.

Several subsequent works have already appeared since the first publication of this paper [23].

One question that was raised was: does there exist a fully asynchronous (concurrent) zero-knowledge proof for NP?

The answer was given by Richardson and Kilian [25] who presented concurrent zero-knowledge arguments for all languages in NP, that is robust in the fully asynchronous setting. However, this protocol is not practical. It requires a polynomial number in k of rounds, which makes it unacceptable in practice. k here is the security parameter: the length of the input and the number of proofs that may run concurrently are bounded by a polynomial in k.

The upper bound on the number of rounds has been drastically improved by Kilian and Petrank [22]. It turns out that the number of rounds that suffices for constructing concurrent zero knowledge is any m satisfying m = ω(log2 k).

Rosen [26] has improved the result described in this paper, i.e., the lower bound on the number of rounds required for concurrent zero-knowledge from 5 to 8. Canetti, Kilian, Petrank and Rosen [6] have substantially improved the lower bound to Ω(logk / log log k). The parameter k is the security parameter. A polynomial in k bounds the length of the inputs, the number of proofs that may start concurrently, and the time complexity that the parties spend in the protocol.

Other researchers have concentrated on presenting efficient concurrent zero-knowledge protocols for NP with weaker compromises on the asynchronisity of the environment. Crescenzo and Ostrovsky [8] presented a concurrent zero-knowledge argument for NP with a preprocessing phase. They removed the (α, β) constraint of [11], and the only requirement is that there must be a separating point in time between all preprocessing of all concurrent proofs, and all bodies of all proofs. Namely, the first body of any proof may start only after all preprocessing phases in all the proofs have completed. D˚ mgard [9] and Canetti et. al. [5] have further reduced the limits on a asynchronisity. They require that prior to the beginning of the proofs, all verifiers have deposited a public key in a public database. In [9] it is required that the public key is valid, i.e., that the verifier must know the secret key associated with it. In [5] this requirement is relaxed. The verifier only has to have a deposited string in the public database. Thus, these proofs are efficient, and make only the following compromise over full asynchronisity: all verifiers must be previously registered before any of them can engage in a proof. A verifier that has not been registered cannot join until all proofs are completed and then it must register itself before any new proof begins.

As an extension to concurrent zero-knowledge, Canetti et. al. presented resettable zeroknowledge proofs [5]. These are zero-knowledge proofs that on top of being concurrent, they remain zero-knowledge also when the verifier is allowed to run the prover repeatedly on a fixed (yet, randomly chosen) random tape. Our lower bound applies, of-course, also to resettable zeroknowledge.

Feige and Shamir have suggested to give up achieving full zero-knowledge in the asynchronous setting and presented a property of proofs called witness indistinguishability. They showed that witness indistinguishability is preserved also in the asynchronous setting [13].

The basic framework of the proof in this paper uses the ideas developed by Goldreich and Krawczyk [16]. Following their technique, we use a good simulator S of an interactive proof (or argument) (P, V ) for a language L to create an efficient prover PS that causes V to accept reasonably often on inputs in L.

1.2 Guide to the paper In Section 2 we discuss black-box simulatability and the framework used by Goldreich and Krawczyk.

In Section 3 we show how to convert an asynchronous simulator into an efficient prover. In Sections 4 and 5 we analyze the success probability of this prover.

–  –  –

2.2 Black-box verifiers with private random functions ˆ In this paper, as in [16], we note that it is enough to consider deterministic V, i.e., even determinˆ istic (yet, cheating) verifiers are hard to simulate. Also, following [16], we consider verifiers V that have access to a private random hash function H, that is wired into them and is not directly ˆ accessible to the simulator (note that V is deterministic in that it doesn’t use an external source of randomness; its construction is randomized). That is, the simulator may gain only indirect access ˆ to H, by observing V ’s input/output behavior. For convenience, we assume that for any polynomially bounded n and m, H will take an n-bit input and return an m-bit output. In practice, H will be defined for big enough n and m, and its inputs (if short) will be padded to fit the length of H’s inputs. Pedantically, we can view H as a family {Hm,n } of hash functions; we suppress these subscripts for clarity.

As in [16], we will think of H as being randomly chosen from a family of hash functions [7].

And as in [16] we do not use the standard pairwise independent family. Instead we use families of hash functions that achieve p(n)-independence, for some sufficiently large polynomial p. A member H in this family can be described by a string of polynomial length, and it is this string that is wired into the verifier. The polynomial p is set to exceed the running time of the simulator times the length of V ’s answers. Thus, even if the simulator poses to V a different query in each of its steps, and if for each query V generates the hash of the query, using H, then the simulator will face a verifier that uses a completely random string for each of its (different) queries. Of course, As one slight exception, [21] proves security against space-bounded verifiers by considering the internal state of the verifiers. However, these techniques do not seem applicable to more standard classes of verifiers.

Pages:   || 2 | 3 | 4 |

Similar works:

«COMMONWEALTH OF PENNSYLVANIA PUBLIC SCHOOL EMPLOYEES’ RETIREMENT SYSTEM Public Investment Memorandum The Värde Scratch and Dent Fund I-A, L.P. High Yield Commitment James F. Del Gaudio Senior Investment Professional May 16, 2016 COMMONWEALTH OF PENNSYLVANIA PUBLIC SCHOOL EMPLOYEES’ RETIREMENT SYSTEM Recommendation: Staff, together with Aksia, LLC, recommends the Board commit an additional $75 million to Värde via The Värde Scratch and Dent Fund I-A, L.P. (the “Fund” or “Fund...»

«The Buddha and Omniscience Anålayo∗ Omniscience has regularly been ascribed to the Buddha in the different Buddhist traditions. An examination of the early discourses found in the Påli Nikåyas and the Chinese Ógamas, however, suggests a different perspective. The term used in the Påli Nikåyas to qualify someone as omniscient is sabbaññu, with its counterpart in the Chinese Ógamas in the expression, (yi qie zhi). The term 知切一 sabbaññu and its equivalent are made up of two...»

«Complex Dynamics in Romantic Relationships Gragnani, A., Rinaldi, S. and Feichtinger, G. IIASA Working Paper WP-96-074 July 1996 Gragnani, A., Rinaldi, S. and Feichtinger, G. (1996) Complex Dynamics in Romantic Relationships. IIASA Working Paper. IIASA, Laxenburg, Austria, WP-96-074 Copyright © 1996 by the author(s). http://pure.iiasa.ac.at/4953/ Working Papers on work of the International Institute for Applied Systems Analysis receive only limited review. Views or opinions expressed herein do...»

«ISIS 1D Quick Start Guide Cost effective, integrated software solutions ch2mhill.com/isis softwaresupport@ch2m.com ISIS 1D v3.7 Quick Start Guide Cost Effective, Integrated Software Solutions Table of Contents Overview 1. Starting ISIS and Basic Concepts 2. How to Run an Existing Model 3. How to Build a Single Channel 4. How to Build a Simple Network 5. How to Add Weirs to the River Model 6. How to Run a Flow Model 7. How to View the Simulation Results 8. Further Information 9. e-Learning River...»

«USING THE GROUP FUNCTIONS QUESTIONS http://www.tutorialspoint.com/sql_certificate/using_the_group_functions_questions.htm Copyright © tutorialspoint.com 1. Which of the following is NOT a GROUP BY function? A. MAX B. MIN C. NVL D. AVG Answer: C. NVL is a general function used to provide alternate value to the NULL values. The functions MAX, MIN and AVG can be used as GROUP BY functions.2. Which of the following functions can be used without GROUP BY clause in SELECT query? A. COUNT B. MAX C....»

«Social Research Update 37: Citizens Juries 11/26/2005 10:22 AM Issue 37 Summer 2002 Social Research Update is published quarterly by the Department of Sociology, University of Surrey, Guildford GU7 7XH, England. Subscriptions for the hardcopy version are free to researchers with addresses in the UK. Apply to SRU subscriptions at the address above, or email sru@soc.surrey.ac.uk. A PDF version of this article is available here. Citizens Juries: a radical alternative for social research Tom...»

«Scouting East The Journal of East Belfast Scouting No. 350 APRIL 2014 From the Editor Hello everyone, Firstly, apologies for the delay in distributing the April issueI’m just back from a short trip to Scotland via the Larne Troon ferry – a particularly rough crossing requiring the services of a tug boat to pull us into the safety of the harbour! The purpose of my visit was to deliver the hospital patient packs, carpentry tools and Scout tents collected over the last few months to the Raven...»

«PUBLISHED UNITED STATES COURT OF APPEALS FOR THE FOURTH CIRCUIT  UNITED STATES OF AMERICA, Plaintiff-Appellee,  v. No. 09-4601 CHRISTOPHER JUDE BLAUVELT,  Defendant-Appellant. Appeal from the United States District Court for the District of Maryland, at Baltimore. William D. Quarles, Jr., District Judge. (1:08-cr-00269-WDQ-1) Argued: December 10, 2010 Decided: March 9, 2011 Before Sandra Day O’CONNOR, Associate Justice (Retired), Supreme Court of the United States, sitting by...»

«latina/chicana mothering edited by Dorsía Smith Silva toronto, canada table of contents Acknowledgments xi Introduction: Conceptualizing Latina/Chicana Mothering Dorsía Smith Silva I: Telling Our Tales: Testimonios Are Hunters Born or Made? Ana Castillo My Mother’s Memory Mayra Santos-Febres How (In a Time of Trouble) I Discovered My Mom and Learned to Live Junot Díaz Journey to Motherhood Dorsía Smith Silva vii latina/chicana mothering Learning the Hard Way Angie Cruz Mi Madre, Mi Hija y...»

«Skyline Umbrella Fund plc INTERIM REPORT & CONDENSED UNAUDITED FINANCIAL STATEMENTS For the period from 1 May 2015 to 31 October 2015 Skyline Umbrella Fund plc Interim Report and Unaudited Financial Statements 2015 Contents Page Organisation 1 Background to the Company 4 Investment Managers’ Reports 14 Statement of Comprehensive Income 21 Statement of Financial Position 23 Statement of Changes in Net Assets Attributable to Holders of Redeemable Participating Shares 25 Statement of Cash Flows...»

«FOIA #HQ-FOI-01268-12 (Note: Emails to/from Richard Windsor are to/from EPA Administrator Lisa P. Jackson) Betsaida To Brendan Gilfillan, Richard Windsor Alcantara/DC/USEPA/US cc Seth Oster 08/25/2011 03:37 PM bcc Subject Re: Fw: WSJ: SEC Bears Down on Fracking We're reaching out to her to fix it. She left one voicemail, so if she really wanted a response she would have followed up with at least an email. Brendan Gilfillan Original Message From: Brendan Gilfillan Sent: 08/25/2011 03:34 PM EDT...»

«OFFICE OF THE INSPECTOR GENERAL SOCIAL SECURITY ADMINISTRATION ANNUAL REPRESENTATIVE PAYEE ACCOUNTING REPORT NON-RESPONDERS March 2011 A-06-10-11069 AUDIT REPORT Mis s io n By c o n d u c tin g in d e p e n d e n t a n d o b je c tive a u d its, e va lu a tio n s a n d in ve s tig a tio n s, we in s p ire p u b lic c o nfid e n c e in th e in te g rity a n d s e c u rity o f S S A’s p ro g ra m s a n d o p e ra tio n s a n d p ro te c t th e m a g a ins t fra u d, wa s te a n d a b us e....»

<<  HOME   |    CONTACTS
2017 www.abstract.dislib.info - Abstracts, online materials

Materials of this site are available for review, all rights belong to their respective owners.
If you do not agree with the fact that your material is placed on this site, please, email us, we will within 1-2 business days delete him.