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].
Manuel Blum, Alfredo De Santis, Silvio Micali, Giuseppe Persiano
This paper investigates the possibility of disposing of interaction between prover and verifier in a zero-knowledge proof if they share beforehand a short random string. Without any assumption, it is proven that noninteractive zero-knowledge proofs exist for some number-theoretic languages for which no efficient algorithm is known. If deciding quadratic residuosity (modulo composite integers whose factorization is not known) is computationally hard, it is shown that the NP-complete language of satisfiability also possesses noninteractive zero-knowledge proofs.
Control system design is considered for attitude control and vibration suppression of flexible space structures. The problem addressed is that of controlling both the zero-frequency rigid-body modes and the elastic modes. Model-based compensators, which employ observers tuned to the plant parameters, are first investigated. Such compensators are shown to generally exhibit high sensitivity to the knowledge of the parameters, especially the elastic mode frequencies. To overcome this problem a class of dynamic dissipative compensators is next proposed, which robustly stabilize the plant in the presence of unmodeled dynamics and parametric uncertainties. An analytical proof of robust stability is given, and a method of implementing the controller as a strictly proper compensator is given. Methods of designing such controllers to obtain optimal performance and robust stability are presented. Numerical and experimental results of application of the methods are presented, which indicate that dynamic dissipative controllers can simultaneously provide excellent performance and robustness.
In this paper the generality and wide applicability of Zero-knowledge proofs, a notion introduced by Goldwasser, Micali, and Rackoff is demonstrated. These are probabilistic and interactive proofs that, for the members of a language, efficiently demonstrate membership in the language without conveying any additional knowledge. All previously known zero-knowledge proofs were only for number-theoretic languages in NP fl CONP. Under the assumption that secure encryption functions exist or by using "physical means for hiding information," it is shown that all languages in NP have zero-knowledge proofs. Loosely speaking, it is possible to demonstrate that a CNF formula is satisfiable without revealing any other property of the formula, in particular, without yielding neither a
A perfect zero-knowledge interactive protocol allows a prover to convince a verifier of the validity of a statement in a way that does not give the verifier any additional information [GMR,GMW]. Such protocols take place by the exchange of messages back and forth between the prover and the verifier. An important measure of efficiency for these protocols is the number of rounds in the interaction. In previously known perfect zero-knowledge protocols for statements concerning NP--complete problems [BCC], at least k rounds were necessary in order to prevent one party from having a probability of undetected cheating greater than 2 \\Gammak . In this paper, we give the first perfect zero-knowledge protocol that offers arbitrarily high security for any statement in NP with a constant number of rounds. The protocol is computationally convincing (rather than statistically convincing as would have been an interactive proof--system in the sense of Goldwasser, Micali and Rackoff) because the ver...
The notion of non-malleable cryptography, an extension of semantically secure cryptography, is defined. Informally, the additional requirement is that given the ciphertext it is impossible to generate a different ciphertext so that the respective plaintexts are related. The same concept makes sense in the contexts of string commitment and zero-knowledge proofs of possession of knowledge. Non-malleable schemes for each of these three problems are presented. The schemes do not assume a trusted center; a user need not know anything about the number or identity of other system users. Keywords: cryptography, cryptanalysis, randomized algorithms, nonmalleability AMS subject classifications: 68M10, 68Q20, 68Q22, 68R05, 68R10 A preliminary version of this work appeared in STOC '91 Hebrew University Jerusalem, Israel y IBM Research Division, Almaden Research Center, 650 Harry Road, San Jose, CA 95120. E-mail: dwork@almaden.ibm.com. z Incumbent of the Morris and Rose Goldman Career Devel...
Abstract Abstract. Recent approaches to the notions of randomness and proofs are surveyed. The new notions differ from the traditional ones in being subjective to the capabilities of the observer rather than reflecting âidealâ entities. The new notion of randomness regards probability distributions as equal if they cannot be told apart by efficient procedures. This notion is constructive and is suited for many applications. The new notion of a proof allows the introduction of the notion of zero-knowledge proofs: convincing arguments which yield nothing but the validity of the assertion. The new approaches to randomness and proofs are based on basic concepts and results from the theory of resource-bounded computation. Elements of this theory are presented only to the extent required for the description of the new approaches. This survey is not intended to provide an account of the more traditional approaches to randomness (e.g., Kolmogorov Complexity; see also Bennettâs account in this volume) and proofs (i.e., traditional logic systems). Whenever these approaches are described it is only in order to confront them with the new approaches.
We study two sets of models: independent percolation models in half spaces Zá”â»Âč x Zâ, and Ising/Potts models as well as the Fortuin-Kasteleyn (FK) random cluster models on branching planes T x Z, where Z is the one-dimensional lattice, Zâ = {0,1,2,...} and T is a Bethe lattice. We prove that for independent percolation in half spaces, the infinite cluster is unique whenever it exists. For the Ising/Potts models on branching planes, there are (at least) two phase transitions; that is, there exist(s) a unique Gibbs state, tree-like nonunique Gibbs states or plane-like nonunique Gibbs states corresponding to high temperature, intermediate temperature or low temperature. In the low temperature plus phase, the plus infinite cluster is unique and it "traps" the space T x Z and prevents co-existence of the minus infinite cluster. For the FK random cluster models (which are dependent percolation models) on T x Z, the number of infinite (open) clusters may be zero, infinity or one depending on the value of p--the probability of each bond being open. This is an extension of Grimmett and Newman's results for independent percolation on T x Z. We also prove that both the independent percolation model and the FK random cluster models satisfy a finite island property when p is close to 1. Chapter 1 is an introduction. Chapter 2 contains the proof of the uniqueness theorem for independent percolation in half spaces. The proof utilizes only a large deviation estimate and translation invariance of the models along the hyperplane Zá”â»Âč x {0}. The Ising/Potts models and the FK random cluster models on the branching planes are studied in Chapter 3. The methods are to use the FK representation of Ising/Potts systems as dependent percolation models to carry over Grimmett and Newman's results for independent percolation to the Ising/Potts models. However, in order to prove the plane-like behavior of the Ising/Potts models, the corresponding results for independent percolation are not sufficient and this led us to investigate independent percolation again and prove a new finite island property. Chapters 2 and 3 are independent. Readers with basic knowledge of percolation and Ising models can omit chapter 1 and read chapters 2 and 3 directly.