We prove a number of general theorems about CZK, the class of problems possessing computational zero knowledge proofs. Our results are unconditional, in contrast to most previous works on CZK which rely on the assumption that one-way functions exist. We establish several new characterizations of CZK, and use these characterizations to prove results such as: 1) Honest-verifier CZK equals general CZK. 2) Public-coin CZK equals private-coin CZK. 3) CZK is closed under union (and more generally, "monotone formula closure"). 4) CZK with imperfect completeness equals CZK with perfect completeness. 5) Any problem in CZK /spl cap/ NP can be proven in computational zero knowledge by a BPP/sup NP/ prover. 6) CZK with black-box simulators equals CZK with general, non-black-box simulators. The above equalities refer to the resulting class of problems (and do not necessarily preserve other efficiency measures such as round complexity). Our approach is to combine the conditional techniques previously used in the study of CZK with the unconditional techniques developed in the study of SZK, the class of problems possessing statistical zero knowledge proofs. To enable this combination, we prove that every problem in CZK can be decomposed into a problem in SZK together with a set of instances from which a one-way function can be constructed.
Jung Min Park, Edwin K. P. Chong, Howard Jay Siegel
Applications such as e-commerce payment protocols, elec-tronic contract signing, and certified e-mail delivery require that fair exchange be assured. A fair-exchange protocol al-lows two parties to exchange items in a fair way so that either each party gets the other's item, or neither party does. We describe a novel method of constructing very ef-ficient fair-exchange protocols by distributing the computa-tion of RSA signatures. Specifically, we employ multisig-natures based on the RSA-signature scheme. To date, the vast majority of fair-exchange protocols require the use of zero-knowledge proofs, which is the most computationally intensive part of the exchange protocol. Using the intrinsic features of our multisignature model, we construct protocols that require no zero-knowledge proofs in the exchange proto-col. Use of zero-knowledge proofs is needed only in the pro-tocol setup phase--this is a one-time cost. Furthermore, our scheme uses multisignatures that are compatible with the underlying standard (single-signer) signature scheme, which makes it possible to readily integrate the fair-exchange fea-ture with existing e-commerce systems.
We present the first complete problem for SZK, the class of promise problems possessing statistical zero-knowledge proofs (against an honest verifier). The problem, called Statistical Difference, is to decide whether two efficiently samplable distributions are either statistically close or far apart. This gives a new characterization of SZK that makes no reference to interaction or zero knowledge .We propose the use of complete problems to unify and extend the study of statistical zero knowledge. To this end, we examine several consequences of our Completeness Theorem and its proof, such as:---A way to make every (honest-verifier) statistical zero-knowledge proof very communication efficient, with the prover sending only one bit to the verifier (to achieve soundness error 1/2).---Simpler proofs of many of the previously known results about statistical zero knowledge, such as the Fortnow and Aiello--Hεstad upper bounds on the complexity of SZK and Okamoto's result that SZK is closed under complement.---Strong closure properties of SZK that amount to constructing statistical zero-knowledge proofs for complex assertions built out of simpler assertions already shown to be in SZK.---New results about the various measures of "knowledge complexity," including a collapse in the hierarchy corresponding to knowledge complexity in the "hint" sense.---Algorithms for manipulating the statistical difference between efficiently samplable distributions, including transformations that "polarize" and "reverse" the statistical relationship between a pair of distributions.
A. Kilkerry Neto, Gerson Zaverucha, Luı́s Alfredo Vidal de Carvalho
Pinkas defined (1991, 1992) a bi-directional mapping between propositional logic formulas and energy functions of symmetric neural networks. He showed that determining whether a propositional logic formula is satisfiable is equivalent to finding whether the global minimum of its associated energy function is equal to zero. He also defined how to transform a first-order resolution-based theorem proof of a formula (query Q) from a given set of formulas (knowledge base KB) into a set of constraints described by a set of propositional logic formulas C. Then he showed that the satisfaction of C is sound and complete with respect to a first-order resolution-based proof of Q from KB. Therefore finding that the global minimum of the energy function associated to C is equal to zero is sound and complete with respect to a first-order resolution-based proof of Q from KB. The proof itself could be extracted from the state of the neurons when the network stops in the global minimum. Pinkas did not implement his system. In this work we point out some adjustments to C and we present an implementation of the revised system. We also show some experimental results and point out some future works.
We develop a formal multi-agent system based on a modal algebra enabling us to preserve the essential characteristics of its autonomous software agents (autonomy, mobility, etc.), as well as to explore the formal properties and management of the cooperations (non-hierarchical or flat structures) and coordinations (hierarchical structures) among those simple agents, that can be constructed through the operations of the model. We show the potential of these operations that allow us to construct different cooperations and coordinations based on the same set of autonomous agents (as alternative solutions with respect to the same given problem), while, in parallel we provide the means in order to explicitly specify different types of coordinated flows of information specified and governed by these structures. We illustrate all the above via a number of algorithms referring to the development of a simple (in structure) data mining system. We simply selected an adequate application area with no purpose to compare data mining methods and techniques. The various algorithmic solutions we suggest, unveil the resilience of the alternative design approaches aiming at improving issues like decentralization of services, as well as enhancing performance through concurrent organization by thus exploiting the different possibilities of the model.
M. Oku, M. Omura, J. Kann, Mario Perrone · 5 authors
An automation system architecture for implementing autonomous decentralized systems (ADSs) called Hi-Cell is described. A project model of human organization featuring activities such as teaming is proposed as an analog for Hi-Cell behavior. Familiar team behaviors such as task allocation, learning, and cooperation are explored in the automation domain.>
If one-way functions exist, then there are zero-knowledge proofs for every language in PSPACE. The authors prove that unless very weak one-way functions exist, zero-knowledge proofs can be given only for languages in BPP. For average-case definitions of BPP they prove an analogous result under the assumption that uniform one-way functions do not exist. Thus, very loosely speaking, zero-knowledge is either useless (exists only for 'easy' languages), or universal (exists for every provable language).>
Alfredo De Santis, Giovanni Di Crescenzo, Giuseppe Persiano, Moti Yung
We investigate structural properties of statistical zero knowledge (SZK) both in the interactive and in the non-interactive model. Specifically, we look into the closure properties of SZK languages under monotone logical formula composition. This gives rise to new protocol techniques. We show that interactive SZK for random self reducible languages (RSR) (and for co-RSR) is closed under monotone Boolean operations. Namely, we give SZK proofs for monotone Boolean formulae whose atoms are statements about an SZK language which is RSR (or a complement of RSR). All previously known languages in SZK are in these classes. We then show that if a language L has a non-interactive SZK proof system then honest-verifier interactive SZK proof systems exist for all monotone Boolean formulae whose atoms are statements about the complement of L. We also discuss extensions and generalizations.>
Concerns use of spacecraft as autonomous coordinated teams. Generalized reasoning capability offered by advanced distributed software technology and AI can cope with unexpected events and uncertainty, and so close the loop of perception, decision and eventually deliberation. The team members play interchangeable roles and negotiate about the task. We present a multi-agent system to provide a high degree of autonomy and support for coordination among team members. We use JPL formation flying mission initial architectures as benchmark. Our target is to avoid inconsistencies/disagreements between two or more participants in a collaborative context, increase the system's fault tolerance in cases such as loss of a member while the system still operates reliably. We address cooperation between collaborating independent autonomous agents. In a top-down organization agents are coordinated hierarchically, where the agents at the top of the hierarchy make the majority of the intelligent group decisions. In a more structured but still hierarchical organization, lower-level agents exercise more intelligence. A lower-level agent can advance a plan for the others to follow, and a higher-rank agent decides on the best plans. Although more rigid, the centralized intelligence organization allows for less communication among agents, so is more straightforward to implement. The decentralized approach requires more communication, but the intelligence is truly distributed, which makes for a more flexible, adaptive and efficient organization.
Argumentation is receiving an increasing attention as a technique for practical and uncertain reasoning underlying the realization of intelligent autonomous agents. Since a decentralized organization has been proposed by several authors as an appropriate paradigm for the design of agent architectures, we propose in this article, a distributed approach to argumentation, in which several independent asynchronous processes carry out argumentation activity, by exploiting local information only. The final result of this process is the computation of the defeat status of the arguments: we devise a general distributed algorithm, which does not rely on any specific notion of defeat between arguments. The issue of coordination has been explicitly tackled by ensuring the property of self-stabilization for the algorithm. A proof of its correctness, as well as an analysis of its complexity, is provided.
This paper presents a perfect zero knowledge proof system for a decision problem which is computationally equivalent to the Discrete Root Problem,and its zero knowledge property does not rely on any assumptions.Thus we provide additional evidence to the belief that perfect zero knowledge proof systems exist in a non trivial manner (i.e.,for language not in BPP).
Summary A summary is not available for this content so a preview has been provided. Please use the Get access link above for information on how to access this content.
A proof is concurrent zero-knowledge if it remains zero-knowledge when many copies of the proof are run in an asynchronous environment, such as the Internet. It is known that zero-knowledge is not necessarily preserved in such an environment. Designing concurrent zero-knowledge proofs is a fundamental issue in the study of zero-knowledge since known zero-knowledge protocols cannot be run in a realistic modern computing environment. In this paper we present a concurrent zero-knowledge proof systems for all languages in NP. Currently, the proof system we present is the only known proof system that retains the zero-knowledge property when copies of the proof are allowed to run in an asynchronous environment. Our proof system has $\tilde{O}(\log^2 k)$ rounds (for a security parameter $k$), which is almost optimal, as it is shown by Canetti Kilian Petrank and Rosen that black-box concurrent zero-knowledge requires $\tildeΩ(\log k)$ rounds. Canetti, Goldreich, Goldwasser and Micali introduced the notion of {\em resettable} zero-knowledge, and modified an earlier version of our proof system to obtain the first resettable zero-knowledge proof system. This protocol requires $k^{θ(1)}$ rounds. We note that their technique also applies to our current proof system, yielding a resettable zero-knowledge proof for NP with $\tilde{O}(\log^2 k)$ rounds.
We present a new technique, inspired by zero-knowledge proof systems, for proving lower bounds on approximating the chromatic number of a graph. To illustrate this technique we present simple reductions from max-3-coloring and max-3-sat, showing that it is hard to approximate the chromatic number within /spl Omega/(N/sup /spl delta//), for some /spl delta/>0. We then apply our technique in conjunction with the probabilistically checkable proofs of Bellare, Goldreich and Sudan (1995), and of Hastad (1996), and show that it is hard to approximate the chromatic number to within /spl Omega/(N/sup 1-/spl epsiv//) for any E>0, assuming NP/spl sub/ ZPP. Here, ZPP denotes the class of languages decidable by a random expected polynomial-time algorithm that makes no errors. Our result matches (up to low order terms) the known gap for approximating the size of the largest independent set. Previous 0(N/sup /spl delta//) gaps for approximating the chromatic number (such as those by Lund and Yannakakis (1994), and by Furer (1995)) did not match the gap for independent set, and do not extend beyond /spl Omega/(N/sup 1/2-/spl epsiv//).
We study the computational complexity of languages which have interactive proofs of logarithmic knowledge complexity. We show that all such languages can be recognized in ${\cal BPP}^{\cal NP}$. Prior to this work, for languages with greater-than-zero knowledge complexity only trivial computational complexity bounds were known. In the course of our proof, we relate statistical knowledge complexity to perfect knowledge complexity; specifically, we show that, for the honest verifier, these hierarchies coincide up to a logarithmic additive term.
The study of probabilistically verifiable proofs originated in the mid 1980s with the introduction of Interactive Proof Systems (IPs). The primary focus of research in this area in the '80s has been twofold: the role of zero-knowledge interactive proofs within cryptographic protocols, and characterizing which languages are efficiently interactively provable. In the 1990s, the focus of research on the topic shifted. Extensions of the interactive proof model, such as Multiprover Interactive Proofs (MIPs) and Probabilistically Checkable Proofs (PCPs), were considered with the intention of expanding our notion of what should be considered efficiently verifiable. In addition, researchers have taken a closer look at the exact resources (and tradeoffs amongst them) needed to verify a proof using various proof systems. This culminated in the important discovery that it is possible to verify NP statements (with a constant error probability) by only examining a constant number of bits of a PCP and using logarithmic amount of randomness. Perhaps, however, the most dramatic development has been the connection which was found between probabilistically verifiable proofs and proving hardness of approximation for optimization problems. It has been shown that a large variety of optimization versions of NP-hard problems (e.g., the maximum size of a clique in a graph, the minimum number of colors necessary to color a graph, and the maximum number of clauses satisfiable in a CNF formula) are not only NP-hard to solve exactly but also NP-hard to approximate in a very strong sense. The tools to establish hardness of approximation came directly from results on MIPs and PCPs. Indeed, almost every improvement in the efficiency of these proof systems translates directly into showing larger factors within which these optimization problems are hard to approximate. In 1994--1995 two exciting workshops were held at the Weizmann Institute in Israel on the new developments in probabilistically verifiable proofs and their applications to approximation problems, cryptography, program checking, and complexity theory at large. Over 60 papers were presented in the workshop series, and we are proud to include three of them in this special section. "On the Power of Finite Automata with Both Nondeterministic and Probabilistic States" by Anne Condon, Lisa Hellerstein, Samuel Pottle, and Avi Wigderson, considers constant round interactive proof systems where the verifier is restricted to use constant space and public coins. An equivalent characterization is finite automata with both nondeterministic and random states (npfa's), which accept their languages with a small probability of error. The paper shows that npfa's restricted to run in polynomial expected time accept only the regular languages in the case of npfa with 1-way input head, and that if Lis a nonregular language, then either L or its complement is not accepted by any npfa with a 2-way input head. "A Parallel Repetition Theorem" by Ran Raz, addresses and resolves the Parallel Repetition Conjecture which has eluded researchers for some time. The broader topic is what happens to the error probability of proof systems when they are composed. It has been known for awhile that sequential composition of proof systems (both single and multiprover interactive proofs) reduces the error exponentially, but this increases the number of rounds. For interactive proof systems, parallel repetition is known to reduce the error exponentially, and the Parallel Repetition Conjecture asserts that the same holds in a one-round two-prover proof system. Raz proves a constructive bound on the probability of error which indeed reduces at an exponential rate. The constant in the exponent is logarithmic in the total number of possible answers of the two provers, which means one can achieve two-prover one-round MIPs for NP statements with arbitrarily small constant error probability. This, in turn, has played a crucial role in further developments in the area and in particular in those reported in the next paper. "Free Bits, PCPs, and Nonapproximability---Towards Tight Results" by Mihir Bellare, Oded Goldreich, and Madhu Sudan, continues the investigation of PCPs and nonapproximability with emphasis on trying to get closer to tight results. The work consists of three parts. The first part presents several PCP proof systems for NP, based on a new error-correcting code called the Long Code. The second part shows that the connection between PCPs and hardness of approximation is not accidental. In particular, it shows that the transformation of a PCP for NP into hardness results for MaxClique can be reversed. Finally, the third part initiates a systematic investigation of the properties of PCPs as a function of the various parameters: randomness, query complexity, free-bit complexity, amortized free-bit complexity, proof size, etc. Two more papers submitted for this special section were not ready at this time for publication. They will appear in future issues of the SIAM Journal on Computing.
We show simple constant-round interactive proof systems for problems capturing the approximability, to within a factor of n , of optimization problems in integer lattices, specifically, the closest vector problem (CVP) and the shortest vector problem (SVP). These interactive proofs are for the coNP direction; that is, we give an interactive protocol showing that a vector is far from the lattice (for CVP) and an interactive protocol showing that the shortest-lattice-vector is long (for SVP). Furthermore, these interactive proof systems are honest-verifier perfect zero-knowledge. We conclude that approximating CVP (resp., SVP) within a factor of n is in N P ∩co A M . Thus, it seems unlikely that approximating these problems to within a n factor is NP-hard. Previously, for the CVP (resp., SVP) problem, Lagarias et al. (1990, Combinatorica 10 , 333–348), Håstad (1988, Combinatorica 8 , 75–81), and Banaszczyk (1993, Math. Annal. 296 , 625–635) showed that the gap problem corresponding to approximating CVP (resp., SVP) within n is in N P ∩co N P . On the other hand, Arora et al. (1997, J. Comput. System Sci. 54 , 317–331) showed that the gap problem corresponding to approximating CVP within 2 log 0.999 n is quasi-NP-hard.