We show how a polynomial-time prover can commit to an arbitrary finite set S of strings so that, later on, he can, for any string x, reveal with a proof whether x /spl isin/ S or x /spl notin/ S, without revealing any knowledge beyond the verity of these membership assertions. Our method is non interactive. Given a public random string, the prover commits to a set by simply posting a short and easily computable message. After that, each time it wants to prove whether a given element is in the set, it simply posts another short and easily computable proof, whose correctness can be verified by any one against the public random string. Our scheme is very efficient; no reasonable prior way to achieve our desiderata existed. Our new primitive immediately extends to providing zero-knowledge databases.

We develop a framework for trading in compound securities: financial instruments that pay off contingent on the outcomes of arbitrary statements in propositional logic. Buying or selling securities---which can be thought of as betting on or against a particular future outcome---allows agents both to hedge risk and to profit (in expectation) on subjective predictions. A compound securities market allows agents to place bets on arbitrary boolean combinations of events, enabling them to more closely achieve their optimal risk exposure, and enabling the market as a whole to more closely achieve the social optimum.The tradeoff for allowing such expressivity is in the complexity of the agents' and auctioneer's optimization problems.We develop and motivate the concept of a compound securities market, presenting the framework through a series of formal definitions and examples. We then analyze in detail the auctioneer's matching problem. We show that, with numevents events, the matching problem is co-NP-complete in the divisible case and complete in the indivisible case. We show that the latter hardness result holds even under severe language restrictions on bids. With events, and numevents securities, the problem is polynomial in the divisible case and NP-complete in the indivisible case. We briefly discuss matching algorithms and tractable special cases.

We show how to determine whether the edit distance between two given strings is small in sublinear time. Specifically, we present a test which, given two n-character strings A and B, runs in time o(n) and with high probability returns "CLOSE" if their edit distance is O(nΑ), and "FAR" if their edit distance is Ω(n), where Α is a fixed parameter less than 1. Our algorithm for testing the edit distance works by recursively subdividing the strings A and B into smaller substrings and looking for pairs of substrings in A, B with small edit distance. To do this, we query both strings at random places using a special technique for economizing on the samples which does not pick the samples independently and provides better query and overall complexity. As a result, our test runs in time Õ(nmax(Α/2, 2Α - 1\)) for any fixed Α < 1. Our algorithm thus provides a trade-off between accuracy and efficiency that is particularly useful when the input data is very large.We also show a lower bound of Ω(nΑ/2) on the query complexity of every algorithm that distinguishes pairs of strings with edit distance at most nΑ from those with edit distance at least n/6.

We show that any concurrent zero-knowledge protocol for a nontrivial language (i.e., for a language outside ${\cal BPP}$), whose security is proven via black-box simulation, must use at least $\tilde\Omega(\log n)$ rounds of interaction. This result achieves a substantial improvement over previous lower bounds and is the first bound to rule out the possibility of constant-round concurrent zero-knowledge when proven via black-box simulation. Furthermore, the bound is polynomially related to the number of rounds in the best known concurrent zero-knowledge protocol for languages in ${\cal NP}$ (which is established via black-box simulation).

We show that any concurrent zero-knowledge protocol for a non-trivial language (i.e., for a language outside $\BPP$), whose security is proven via black-box simulation, must use at least \tildeΩ(log n) rounds of interaction. This result substantially improves over previous lower bounds, and is the first bound to rule out the possibility of constant-round black-box concurrent zero-knowledge. Furthermore, the bound is polynomially related to the number of rounds in the best known concurrent zero-knowledge protocol for languages in ~$\NP$.

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. Richardson and Kilian have shown that there exists a concurrent zero-knowledge proof for any language in NP, but with round complexity polynomial in the maximum number of concurrent proofs. In this paper, we present a concurrent zero-knowledge proof for all languages in NP with a poly-logarithmic round complexity: specifically, ω(log^2 k) rounds given at most k concurrent proofs. Finally, we show that a simple modification of our proof is a resettable zero-knowledge proof for NP, with ω(log^2 k) rounds; previously known protocols required a polynomial number of rounds.

We consider the power of cryptographic primitives, denoted f-cryptogates, defined as follows: Alice and Bob have inputs x and y, respectively.Given a possibly probabilistic function, f(x,y), the f-cryptogate computes z +--f(x,y) and either broadcasts z to both parties (the symmetric case) or sends z exclusively to Bob (the asymmetric case); neither party learns more than what is provided by the fcryptogate.We say that an f-cryptogate is complete if, using information-theoretic notions of reductions, security and privacy, one can use the cryptogate to perform secure two-party computation.We give a number of characterizations of the complete fcryptogates, depending on the adversary model, whether the output of f is probabilistic or deterministic, and whether the cryptogate is symmetric or asymmetric.For active adversaries, who may violate the protocol, we characterize the complete asymmetric f-cryptogates for deterministic f.For passive adversaries, who always follow the protocol, we characterize the complete symmetric and asymmetric f-cryptogates for all deterministic and probabilistic f.Our characterizations for asymmetric cryptogates generalizes a recent theorem of Beimel, Malkin and Micali.abilistic) function f(x, y), the goal of secure function evaluation is to provide Bob with the value of z +--f(x, y) (for

We introduce the miss-match form for two-prover one-round proof systems. Any two-prover one-round proof system can be easily modified so as to be in miss-match form. Proof systems in miss-match form have the "projection" property that is important for deriving hardness of approximation results for NP-hard combinatorial optimization problems. Our main result is an upper bound on the number of parallel repetitions that suffice in order to reduce the error of miss-match proof systems from p to $\epsilon$. This upper bound depends only on p and on $\epsilon$ (polynomial in 1/(1-p) and in $1/\epsilon$). Based on previous work, it follows that for any $\epsilon >0,$ NP has two-prover one-round proof systems with logarithmic-sized questions, constant-sized answers, and error at most $\epsilon$. As part of our proof we prove upper bounds on the influence of random variables on multivariate functions, which may be of independent interest.

We define the notions of reducibility and completeness in (two-party and multiparty) private computations. Let g be an n-argument function. We say that a function f is reducible to a function g if n honest-but-curious players can compute the function fn -privately, given a black box for g (for which they secretly give inputs and get the result of operating g on these inputs). We say that g is complete (for private computations) if every function f is reducible to g. In this paper, we characterize the complete boolean functions: we show that a boolean function g is complete if and only if g itself cannot be computed n-privately (when there is no black box available). Namely, for n-argument boolean functions, the notions of completeness and n-privacy are complementary. This characterization provides a huge collection of complete functions any nonprivate boolean function!) compared to very few examples that were given (implicitly) in previous work. On the other hand, for nonboolean functions, we show that these two notions are not complementary.

We present a primality proving algorithm—a probablistic primality test that produces short certificates of primality on prime inputs. We prove that the test runs in expected polynomial time for all but a vanishingly small fraction of the primes. As a corollary, we obtain an algorithm for generating large certified primes with distribution statistically close to uniform. Under the conjecture that the gap between consecutive primes is bounded by some polynomial in their size, the test is shown to run in expected polynomial time for all primes, yielding a Las Vegas primality test. Our test is based on a new methodology for applying group theory to the problem of prime certification, and the application of this methodology using groups generated by elliptic curves over finite fields. We note that our methodology and methods have been subsequently used and improved upon, most notably in the primality proving algorithm of Adleman and Huang using hyperelliptic curves and in practical primality provers using elliptic curves.

We study a semi-random graph model for finding independent sets. For /spl alpha/>0, an n-vertex graph with an independent set S of site /spl alpha/n is constructed by blending random and adversarial decisions. Randomly and independently with probability p, each pair of vertices, such that one is in S and the other is not, is connected by an edge. An adversary can then add edges arbitrarily (provided that S remains an independent set). The smaller p is, the larger the control the adversary has over the semi-random graph. We design heuristics that with high probability recover S when p>(1+/spl epsiv/)ln n/|S|, for any constant /spl epsiv/>0. We show that when p<(1-/spl epsiv/) In n/|S|, an independent set of size |S| cannot be recovered, unless NP/spl sube/BPP. We use our remits to obtain greatly improved coloring algorithms for the model of k-colorable semi-random graphs introduced by A. Blum and J. Spencer (1995).

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.

We study the complexity of refereed games, in which two computationally unlimited players play against each other, and a polynomial time referee monitors the game and announces the winner.The players may exchange messages with the referee in private, resulting in a game of perfect recall but incomplete information.We show that any EXPTIME statement can be efficiently transformed into a refereed game in which if the statement is true, the first player wins with overwhelming probability y, and if the statement is false, the second player wins with overwhelming probability.We also prove matching PSPACE upper and lower bounds on the complexity of statements that have refereed games that take one round of communication.

We construct PCPS with strong zero-knowledge properties.First, we construct polynomially bounded (in size) PCP'S for NP which can be checked using poly-Iogarithmic queries, with polynomially low error, yet are statistical zero-knowledge against an adversary that makes U arbitrary queries, where U can be set to any polynomial.Second, we construct PCPS for NEXPTIME that can be checked using polynomially many queries, yet are statistically zero-knowledge against any polynomial y bounded adversary.These PCPS are exponential in size and have exponentially low error.Previously, it was only known how to construct zero-knowledge PCPS with a constant error probability.In the course of constructing these PCP'S we abstract a tool we call locking systems.We provide the definition and also a locking system with very efficient parameters.This mechanism may be useful in other settings as well.

This paper presents a secure (tamper-resistant) algorithm for watermarking images, and a methodology for digital watermarking that may be generalized to audio, video, and multimedia data. We advocate that a watermark should be constructed as an independent and identically distributed (i.i.d.) Gaussian random vector that is imperceptibly inserted in a spread-spectrum-like fashion into the perceptually most significant spectral components of the data. We argue that insertion of a watermark under this regime makes the watermark robust to signal processing operations (such as lossy compression, filtering, digital-analog and analog-digital conversion, requantization, etc.), and common geometric transformations (such as cropping, scaling, translation, and rotation) provided that the original image is available and that it can be successfully registered against the transformed watermarked image. In these cases, the watermark detector unambiguously identifies the owner. Further, the use of Gaussian noise, ensures strong resilience to multiple-document, or collusional, attacks. Experimental results are provided to support these claims, along with an exposition of pending open problems.

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 describe a digital watermarking method for use in audio, image, video and multimedia data. We argue that a watermark must be placed in perceptually significant components of a signal if it is to be robust to common signal distortions and malicious attack. However, it is well known that modification of these components can lead to perceptual degradation of the signal. To avoid this, we propose to insert a watermark into the spectral components of the data using techniques analogous to spread spectrum communications, hiding a narrow band signal in a wideband channel that is the data. The watermark is difficult for an attacker to remove, even when several individuals conspire together with independently watermarked copies of the data. It is also robust to common signal and geometric distortions such as digital-to-analog and analog-to-digital conversion, resampling, quantization, dithering, compression, rotation, translation, cropping and scaling. The same digital watermarking algorithm can be applied to all three media under consideration with only minor modifications, making it especially appropriate for multimedia products. Retrieval of the watermark unambiguously identifies the owner, and the watermark can be constructed to make counterfeiting almost impossible. We present experimental results to support these claims.

Recycling random bits (that is, replacing independent random bits by dependent random bits extracted from a pseudo-random bit generator) has been a successful enterprise in many scenarios, including cryptography, NC computations, space bounded computation, RP and BPP algorithms, and interactive proofs. A wide variety of techniques have been introduced for this purpose. Recycling random bits is highly motivated in the context of parallel repetition of two-prover one-round proof systems, where (if it were possible) it would lead to stronger hardness results for approximating NP-hard optimization problems. In this paper we show that the great success enjoyed by general techniques for recycling random bits in other contexts meets its limits when MIP(2,1) proof systems are concerned. That is, there are natural MIP(2,1) proof systems for 3-SAT for which parallel repetition using independent random bits can reduce the error to be polynomially small, but parallel repetition using pseudo-random bits cannot reduce the error below a constant, regardless of the nature of the pseudo-random source.

The best previous algorithm for the matching shoulders lob-pass game, ARTHUR (Abe and Takeuchi 1993), suffered O(t1/2) regret. We prove that this is the best possible performance for any algorithm that works by accurately estimating the opponent's payoff lines. Then we describe an algorithm which beats that bound and meets the information-theoretic lower bound of O(logt) regret by converging to the best lob rate without accurately estimating the payoff lines. The noise-tolerant binary search procedure that we develop is of independent interest.

We consider the basic cryptographic primitive known as zero-knowledge proofs on committed bits. In this primitive, a prover P commits to a set of bits, and then at a later time convinces a verifier V that some property /spl Pscr/ holds for a subset of these bits. It is known how to implement this primitive based on an ordinary bit-committal primitive, but the standard implementations involve a great deal of interaction between the prover and the verifier. We introduce new implementations that require markedly less interaction. We implement bounded-interaction proofs on committed bits, generalizing a model of A. De Micali et al. (1988). For all security parameters, our implementations require only a lg/sup 2/ (n) overhead over the best known circuit-based interactive implementations; for sufficiently large security parameters this gap drops to a lg(n) factor.>

We introduce the miss-match form for two-prover one-round proof systems.Any two-prover one-round proof system can be easily modified so as to be in miss-match form.Proof systems in miss-match form have the projection property that is important for deriving hardness of approximation results for NP-hard combinatorial optimization problems. Our main result is an upper bound on the number of parallel repetitions that suffice in order to reduce the error of miss-match proof systems from p to � .This upper bound depends only on p and on � (polynomial in 1/(1 − p) and in 1/� ).Based on previous work, it follows that for any �> 0, NP has two-prover one-round proof systems with logarithmic-sized questions, constant-sized answers, and error at most � . As part of our proof we prove upper bounds on the influence of random variables on multivariate functions, which may be of independent interest.

We consider a minimal scenario for secure computation: Parties A and B have private inputs x and y and a shared random string r.A and B are each allowed to send a single message to a third party C, from which C is to learn the value of ~(z, y) for some function ~, but nothing else.We show that this model is surpris-Permission to copywithout fee all or part of this material is granted provided that the copies are not made or distributed for direct eommarcial advantaqe, tha ACM copyrioht notice a?d the title of the publicatiort 'and Its date appear, and notice is gwen that copying is by permission of the Association of Computing Machinery.

We investigate the power of recurrent neural networks that apply the standard sigmoid activation function: a(z) = [2/(1 + e-”)] -1. We show that in the noiseless model, there exists a universal architecture that can be used to compute any recursive function. As a result, basic convergence questions concerning these architectures are shown to be undecidi~ble even for fixed-size networks. This is the first result of its kind for the standard sigmoid activation function; previous techniques only applied to linearized and truncated versions of this function. The significance of our result, besides the proving technique itself, lies in the popularity of the sigmoidal function both in applications of artificial neural networks and in models of biological neural networks. Our techniques can be applied to a much more general class of “sigmoid-like” activation functions, suggesting that Turing universality is a relatively common property of recurrent neural network models.

In this note, we present new zero-knowledge interactive proofs and arguments for languages in NP. To show that x ε L, with an error probability of at most 2-k, our zero-knowledge proof system requires O(|x|c1)+O(lgc2|x|)k ideal bit commitments, where c1 and c2 depend only on L. This construction is the first in the ideal bit commitment model that achieves large values of k more efficiently than by running k independent iterations of the base interactive proof system. Under suitable complexity assumptions, we exhibit zero knowledge arguments that require O(lgc|x|kl bits of communication, where c depends only on L, and l is the security parameter for the prover. This is the first construction in which the total amount of communication can be less than that needed to transmit the NP witness. Our protocols are based on efficiently checkable proofs for NP[4].

We consider 2-party cryptographic games of the following form.Alice and Bob choose inputs i and j, respectively, from some finite domain D.

The problem of efficiently permuting data stored in VLSI chips in accordance with a predetermined set of permutations is explored. By connecting chips with shared bus interconnections, as opposed to point-to-point interconnections, it is shown that the number of pins per chip can often be reduced. As an example, for infinitely many n, the authors exhibit permutation architectures that can realize any of the n cyclic shifts on n chips in one clock tick, where the upper limit on the number of pins per chip is the greatest integer>

Several resources relating to zero-knowledge protocols are considered. They are the number of envelopes used in the protocol, the number of oblivious transfer protocols executed during the protocol, and the total amount of communication required by the protocol. It is shown that after a preprocessing stage consisting of O(k) executions of oblivious transfer, any polynomial number of NP-theorems of any polysize can be proved noninteractively and in zero knowledge, on the basis of the existence of any one-way function, so that the probability of accepting a false theorem is less than 1/2/sup k/.>

The authors present some general techniques for establishing the cryptographic strength of a wide variety of games. As case studies, they analyze some weakened versions of the standard forms of oblivious transfer. They also consider variants of oblivious transfer that are motivated by coding theory and physics. Among their results, they show that a noisy telephone line is in fact a very sophisticated cryptographic device. They also present an application to quantum cryptography.>

Interactive proof systems are considered in which the best set of possible verifiers is restricted to the class of probabilistic log-space automata. A. Condon (1988) introduced this model and showed that if the protocols are allowed to run for arbitrarily many rounds, exponential-time languages can be proved to a log-space verifier. To better approximate the usual notion of interactive proof systems, a number of researchers have considered a more realistic, further restricted model in which protocols are polynomially bounded, both in the number of rounds of communication and in the number of computational steps allowed to the verifier. A notion of language-recognition zero-knowledge is defined for this model, and it is shown that anything provable in this model can be proved in language-recognition zero-knowledge.>

Quite complex cryptographic machinery has been developed based on the assumption that one-way functions exist, yet we know of only a few possible such candidates. It is important at this time to find alternative foundations to the design of secure cryptography. We introduce a new model of generalized interactive proofs as a step in this direction. We prove that all NP languages have perfect zero-knowledge proof-systems in this model, without making any intractability assumptions.

Suppose your netmail is being erratically censored by Captain Yossarian. Whenever you send a message, he censors each bit of the message with probability 1/2, replacing each censored bit by some reserved character. Well versed in such concepts as redundancy, this is no real problem to you. The question is, can it actually be turned around and used to your advantage? We answer this question strongly in the affirmative. We show that this protocol, more commonly known as oblivious transfer, can be used to simulate a more sophisticated protocol, known as oblivious circuit evaluation([Y]). We also show that with such a communication channel, one can have completely noninteractive zero-knowledge proofs of statements in NP. These results do not use any complexity-theoretic assumptions. We can show that they have applications to a variety of models in which oblivious transfer can be done.

This paper explores the problem of efficiently permuting data stored in VLSI chips in accordance with a predetermined set of permutations. By connecting chips with shared bus interconnections, as opposed to point-to-point interconnections, we show that the number of pins per chip can often be reduced. For example, for infinitely many n, we exhibit permutation architectures with ⌈√n⌉ pins per chip that can realize any of the n cyclic shifts on n chips in one clock tick. When the set of permutations forms a group with p elements, any permutation in the group can be realized in one clock tick by an architecture with O(√p lg p) pins per chip. When the permutation group is abelian, O(√p) pins suffice. These results are all derived from a mathematical characterization of uniform permutation architectures based on the combinatorial notion of a difference cover.

We consider the problem of computing with encrypted data. Player A wishes to know the value ƒ(x) for some x but lacks the power to compute it. Player B has the power to compute ƒ and is willing to send ƒ(y) to A if she sends him y, for any y. Informally, an encryption scheme for the problem ƒ is a method by which A, using her inferior resources, can transform the cleartext instance x into an encrypted instance y, obtain ƒ(y) from B, and infer ƒ(x) from ƒ(y) in such a way that B cannot infer x from y. When such an encryption scheme exists, we say that ƒ is encryptable.

This paper presents a new probabilistie primality test.Upon termination the test outputs "composite" or "prime", along with a short proof of correctness, which can be verified in deterministic polynomial time.The test is different from the tests of Miller [M], Solovay-Strassen [SSI, and Rabin [R] in that its assertions of primality are certain, rather than being correct with high probability or dependent on an unproven assumption.Thc test terminates in expected polynomial time on all but at most an exponentially vanishing fraction of the inputs of length k, for every k.This result implies:• There exist an infinite set of primes which can be recognized in expected polynomial time.• Large certified primes can be generated in expected polynomial time.Under a very plausible condition on the distribution of primes in "small" intervals, the proposed algorithm can be shown'to run in expected polynomial time on every input.