Joachim von zur Gathen, Oded Goldreich, Madhu Sudan
The workshop Complexity Theory was organized by Joachim von zur Gathen (Universität Bonn), Oded Goldreich (Weizmann Institute), and Madhu Sudan (MIT). The workshop was held on June 24th–30th 2007, and attended by approximately 50 participants spanning a wide range of interests within the field of Computational Complexity. The plenary program, attended by all participants, featured eight long lectures as well as short (10-minute) reports by almost all participants. In addition, extensive interaction took place in smaller groups. The Oberwolfach Meeting on Complexity Theory is marked by a long tradition and a continuous transformation. Originally starting with a focus on algebraic and Boolean complexity, the meeting has continuously evolved to cover a wide variety of areas, most of which were not even in existence at the time of the first meeting (in 1972). While inviting many of the most prominent researchers in the field, the organizers try to identify and invite a fair number of promising young researchers. Computational complexity (a.k.a. complexity theory) is a central field of computer science with a remarkable list of celebrated achievements as well as a vibrant research activity. The field is concerned with the study of the intrinsic complexity of computational tasks, and this study tends to aim at generality : it focuses on natural computational resources, and considers the effect of limiting these resources on the class of problems that can be solved. Computational complexity is related to and has substantial interaction with other areas of mathematics such as number theory, algebra, combinatorics, coding theory, and optimization. The workshop focused on several sub-areas of complexity theory and its nature may be best illustrated by a brief survey of some of the meeting's highlights. Connections to the Theory of Error-Correcting Codes. The interplay between coding theory and complexity theory first emerged in the context of “hardness amplification” (almost two decades ago) and other connections are less than a decade old (e.g., the connection to probabilistic checking of proofs and extraction of pure randomness). Several applications of the known connections were presented in the current meeting, and in addition a new connection to algebraic complexity was presented. While previous applications of the aforementioned connections went in the direction of coding theory to complexity theory, a recent result reported by Venkat Guruswami goes in the opposite direction. This work, by Guruswami and his graduate student (Rudra), resolves a decades-old central problem in coding theory by presenting an explicit error-correcting code of constant-size alphabet that approaches the capacity bound (under worst-case errors, using list decoding). Extracting randomness. Extracting almost-perfect randomness from weak sources of (imperfect) randomness is crucial for the actual use of randomized procedures. Typical analyses of randomized procedures assume that the procedures have access to a perfect random source. However, in reality one only has access to sources of weak randomness (e.g., having constant entropy rate). Indeed, the problem has attracted a lot of attention in the last couple of decades. In the meeting, Chris Umans has presented recent work with Guruswami and Vadhan, which utilizes recent algebraic and coding theoretic techniques to the construction of (single-source) randomness extractors. This construction meets (and actually improves) the best known parameters for the problem (which are almost optimal), but does so by a relatively simple construction rather than by a complex combination of numerous constructs (as done in prior work). Furthermore, the new work introduces improved constructions for an intermediate primitive (called randomness condenser), which is of independent interest. While single-source randomness extractors must utilize an auxiliary random seed (which may be very short), some applications do not allow for such a seed. In this case, extraction from several (e.g., two) independent sources of weak randomness is called for. An important step in the study of this direction was made by Anup Rao, and presented by him in the meeting. Algebraic complexity and modular polynomial composition. An important task in algebraic computation is modular polynomial composition; that is, given three univariate polynomials f,g and h , one is required to obtain the coefficients of the polynomial f \circ g \bmod h . This task has many applications, most notably as an ingredient in algorithms for polynomial factorization. The previously best algorithm was presented 30 years ago and uses O(n^{1.7}) arithmetic operations, where n denotes the maximum degree of the polynomials. In the meeting, Chris Umans presented significant progress on this celebrated open problem in the form of an almost linear-time algorithm that works for fields of small characteristic. This major progress on a purely algebraic problem is essentially based on methods that were introduced into coding theory by Guruswami and Rudra, and then applied to complexity theory in the context of randomness extractors (see foregoing paragraphs). All three results, which are major achievements in their respective areas, were presented at the meeting. Cryptography and Zero-Knowledge. Zero-knowledge proofs are fascinating concepts and extremely useful constructs. Their fascinating nature is due to their seemingly contradictory definition that mandates that they be convincing and yet yield nothing beyond the validity of the assertion being proved. Their applicability in the domain of cryptography is vast; they are typically used to force malicious parties to behave according to a predetermined protocol. In addition to their direct applicability in cryptography, zero-knowledge proofs serve as a good bench-mark for the study of various problems regarding cryptographic protocols. Zero-knowledge proofs come in many flavors, and it is of great theoretical and practical importance to investigate the relationship among them. A central problem in this area, which has been open since 1986, refers to the gap between the known results regarding two dual notions: the notion of general zero-knowledge proofs (in which the secrecy condition holds with respect to feasible adversaries) and the notion of statistical zero-knowledge arguments (in which the soundness condition holds with respect to feasible adversaries). This gap was bridged in a recent work of Salil Vadhan, jointly with his graduate students (Nguyen and Ong), and was presented by Vadhan in this meeting. A problem related to both cryptography and coding theory is the problem of constructing private information retrieval schemes and/or locally decodable codes. In the context of error-correcting codes, such schemes should allow the recovery of any bit in the original message based on a constant number (e.g., three) probes to the corrupted codeword. For more than a decade it was believed that the length of such codewords must be (weakly) exponential in the length of the message. In the meeting, Sergey Yekhanin (PhD student) presented his recent result that refutes this belief. Delegating your work to an untrusted entities. Needless to say, it is nice to delegate your work to others, but what if you don't trust the others? The very definition of a proof system refers to such a possibility – the hard task of finding a proof is delegated to the outside while you make sure that the proof is valid by performing the easier task of verification. However, facilitating verification may mean making the task of finding adequate proofs even harder. In the context of program checking this phenomenon is explicitly disallowed: wishing to solve some problem you may use an untrusted program that supposedly solves this problem (but not a program that solve more complex problems). Needless to say, the aim is allowing the delegator, called a checker, to use significantly few
The interplay of randomness and computation is at the heart of modern Cryptography and plays a fundamental role in the design of algorithms and in the study of computation at large.Specifically, this interplay is pivotal to several intriguing notions of probabilistic proof systems (e.g., interactive proofs, zero-knowledge proofs, and probabilistically checkable proofs), is the focal of the computational approach to randomness, and is essential for various types of sub-linear time algorithms.This essay provides a brief outline of these connections.
In quantum zero knowledge, the assumption was made that the verifier is only using unitary operations. Under this assumption, many nice properties have been shown about quantum zero knowledge, including the fact that Honest-Verifier Quantum Statistical Zero Knowledge ($HVQSZK$) is equal to Cheating-Verifier Quantum Statistical Zero Knowledge ($QSZK$) (see ~\cite{Wat02,Wat06}). In this paper, we study what happens when we allow an honest verifier to flip some coins in addition to using unitary operations. Flipping a coin is a non-unitary operation but doesn\'t seem at first to enhance the cheating possibilities of the verifier since a classical honest verifier can flip coins. In this setting, we show an unexpected result: any classical Interactive Proof has an Honest-Verifier Quantum Statistical Zero Knowledge proof with coins. Note that in the classical case, honest verifier $SZK$ is no more powerful than $SZK$ and hence it is not believed to contain even $NP$. On the other hand, in the case of cheating verifiers, we show that Quantum Statistical Zero Knowledge where the verifier applies any non-unitary operation is equal to Quantum Zero-Knowledge where the verifier uses only unitaries. One can think of our results in two complementary ways. If we would like to use the honest verifier model as a means to study the general model by taking advantage of their equivalence, then it is imperative to use the unitary definition without coins, since with the general one this equivalence is most probably not true. On the other hand, if we would like to use quantum zero knowledge protocols in a cryptographic scenario where the honest-but-curious model is sufficient, then adding the unitary constraint severely decreases the power of quantum zero knowledge protocols.
A zero-knowledge interactive proof is a protocol by which Alice can convince a polynomially-bounded Bob of the truth of some theorem without giving him any hint as to how the proof might proceed. Under cryptographic assumptions, we give a general technique for achieving this goal for every problem in NP. This extends to a presumably larger class, which combines the powers of non-determinism and randomness. Our protocol is powerful enough to allow Alice to convince Bob of theorems for which she does not even have a proof: it is enough for Alice to convince herself probabilistically of a theorem, perhaps thanks to her knowledge of some trap-door information, in order for her to be able to convince Bob as well, without compromising the trap-door in any way. These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
This work addresses the subject of mathematics education at secondary schools from a current and stimulating point of view intimately related to computational science. Cryptology is a captivating way of introducing into the classroom different mathematical subjects such as functions, matrices, modular arithmetic, combinatorics, equations, statistics and proofs, which usually are recognized as difficult for many students. Special attention is paid here to the concepts of proof and verification through the definition of zero-knowledge cryptographic protocols. Many other different cryptographic and cryptanalytic activities (building and breaking ciphers, respectively) and modern cryptographic applications such as secret-sharing protocols are also proposed as resources for motivating mathematics learning and for achieving a significant improvement in student understanding of several algebraic, analytical and statistical concepts.
The existing protocols that are used to prove that a committed number x lies in a specific interval mostly prove that the integer x is no less than a and then repeat the same method to prove that b is no less than x.In order to delete the repetition in these methods a new protocol is proposed by integrating the protocol that two committed numbers are equal with the protocol of the CFT proof.A verifier can be convinced that the committed number x is neither less than the integer a nor more than the integer b after the protocol is operated only once,and hence the exact proof that x lies in the interval is achieved.The proposed protocol is a statistical zero-knowledge proof.In contrast to Boudot's protocol,our method reduces an exponentiation operation;the communication quantity decreases from(16 176) bits to(13 222) bits,and the communication efficiency increases by 18.26 percent.
This paper proves that several interactive proof systems are zero-knowledge against general quantum attacks. This includes the well-known Goldreich–Micali–Wigderson classical zero-knowledge protocols for graph isomorphism and graph 3-coloring (assuming the existence of quantum computationally concealing commitment schemes in the second case). Also included is a quantum interactive proof system for a complete problem for the complexity class of problems having honest verifier quantum statistical zero-knowledge proofs, which therefore establishes that honest verifier and general quantum statistical zero-knowledge are equal: $\mathrm{QSZK}= \mathrm{QSZK}_{\mathrm{HV}}$. Previously no nontrivial interactive proof systems were known to be zero-knowledge against quantum attacks, except in restricted settings such as the honest verifier and common reference string models. This paper therefore establishes for the first time that true zero-knowledge is indeed possible in the presence of quantum information and computation.
We consider a continuous-time version of fictitious play (FP), in which interacting players evolve their strategies in reaction to their opponents' actions without knowledge of their opponents' utilities. It is known that FP need not converge, but that convergence is possible in certain special cases including zero-sum games, identical interest games, and two-player/two-move games. We provide a unified proof of convergence in all of these cases by showing that a Lyapunov function previously introduced for zero-sum games also can establish stability in the other special cases. We go on to consider a two-player game in which only one player has two-moves and use properties of planar dynamical systems to establish convergence.
Jan 20, 2003·Proceedings. Fourteenth Annual IEEE Conference on Computational Complexity (Formerly: Structure in Complexity Theory Conference) (Cat.No.99CB36317)
We consider the following (promise) problem, denoted ED (for Entropy Difference): The input is a pair of circuits, and YES instances (resp., NO instances) are such pairs in which the first (resp., second) circuit generates a distribution with noticeably higher entropy. On one hand we show that any language having a (honest-verifier) statistical zero-knowledge proof is Karp-reducible to ED. On the other hand, we present a public-coin (honest-verifier) statistical zero-knowledge proof for ED. Thus, we obtain an alternative proof of Okamoto's result by which HVSZK: (i.e., honest-verifier statistical zero knowledge) equals public-coin HVSZK. The new proof is much simpler than the original one. The above also yields a trivial proof that HVSZK: is closed under complementation (since ED easily reduces to its complement). Among the new results obtained is an equivalence of a weak notion of statistical zero knowledge to the standard one.
The author studies connections among one-way functions, hard on the average problems, and statistical zero-knowledge proofs. In particular, he shows how these three notions are related and how the third notion can be better characterized, assuming the first one.>
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.
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.
An interactive proof involves two parties, the prover and the verifier. The goal of the proof is for the prover to convince the verifier that some instance of a decision problem is true. A zero-knowledge proof is an interactive proof where the only information learned by the verifier of the proof is the outcome of the proof. This thesis contains a theoretical overview of interactive and zero-knowledge proofs and describes experiments with implementations of some of them. Two examples of interactive proofs from number theory are given, a protocol for quadratic non-residues and a protocol for subgroup non-membership. The third example of an interactive proof is a protocol for determining the truth value of a quantified Boolean formula. This interactive proof was implemented and the details of that implementation, plus a test of the implementation derived from game theory, are included. There is also a discussion of quantum interactive proofs. The two examples of perfect zero-knowledge proofs that are included are protocols for quadratic residues and for subgroup membership. These protocols were also implemented, and those details are included. For each protocol, there is a discussion of the complexity status of the problems addressed by the protocol. There is also a brief discussion of the history and applications of interactive and zero-knowledge proofs.