Several Multi-Prover Interactive Proofs (MIPs) found in the literature contain proofs of soundness that are lacking. This was first observed [1] in which a notion of Prover isolation is defined to partly address the issue. Furthermore, some existing Zero-Knowledge MIPs suffer from a catastrophic flaw: they outright allow the Provers to communicate via the Verifier. Consequently, their soundness claims are now seriously in doubt, if not plain wrong. This paper outlines the lack of isolation and numerous other issues found in the (ZK)MIP literature. A follow-up paper will resolve most of these issues in detail.
The concept of a Turing machine has been well defined. It would be sufficient to show that Bitcoin uses a dual stack architecture that acts as a dual counter machine. Such systems have already been demonstrated as being Turing complete. We demonstrate that Bitcoin script is a minimal family of which λ and R are members. Further using the compositional product rule and the iteration rule we demonstrate that Bitcoin scripting is Turing complete with the limitations imposed on any realworld computer. This limitation is that there cannot be an infinite tape. Iterations can be simulated using an “unrolled” loop function with allocation to the “Alt” stack. As the product rule states that if A, B are machines, then A.B is also a machine. The iteration rule shows that if A is a machine then (A) is also a machine. Further the minimum power of A under which the observed square of the final configuration is blank. The consequence of these rules is that for every partial recursive function of in variables we can show that it can be evaluated by machine of the proposed family.
When constructing practical zero-knowledge proofs based on the hardness of the Ring-LWE or the Ring-SIS problems over polynomial rings \(\mathbb {Z}_p[X]/(X^n+1)\), it is often necessary that the challenges come from a set \(\mathcal {C}\) that satisfies three properties: the set should be large (around \(2^{256}\)), the elements in it should have small norms, and all the non-zero elements in the difference set \(\mathcal {C}-\mathcal {C}\) should be invertible. The first two properties are straightforward to satisfy, while the third one requires us to make efficiency compromises. We can either work over rings where the polynomial \(X^n+1\) only splits into two irreducible factors modulo p, which makes the speed of the multiplication operation in the ring sub-optimal; or we can limit our challenge set to polynomials of smaller degree, which requires them to have (much) larger norms.
Eli Ben‐Sasson, Alessandro Chiesa, Michael A. Forbes, Ariel Gabizon · 6 authors
We present the first constructions of single-prover proof systems that achieve perfect zero knowledge (PZK) for languages beyond NP, under no intractability assumptions: 1. The complexity class #P has PZK proofs in the model of Interactive PCPs (IPCPs) [KR08], where the verifier first receives from the prover a PCP and then engages with the prover in an Interactive Proof (IP). 2. The complexity class NEXP has PZK proofs in the model of Interactive Oracle Proofs (IOPs) [BCS16,RRR16], where the verifier, in every round of interaction, receives a PCP from the prover. Our constructions rely on succinct simulators that enable us to "simulate beyond NP", achieving exponential savings in efficiency over [BCGV16]. These simulators crucially rely on solving a problem that lies at the intersection of coding theory, linear algebra, and computational complexity, which we call the succinct constraint detection problem, and consists of detecting dual constraints with polynomial support size for codes of exponential block length. Our two results rely on solutions to this problem for fundamental classes of linear codes: * An algorithm to detect constraints for Reed--Muller codes of exponential length. * An algorithm to detect constraints for PCPs of Proximity of Reed--Solomon codes [BS08] of exponential degree. The first algorithm exploits the Raz--Shpilka [RS05] deterministic polynomial identity testing algorithm, and shows, to our knowledge, a first connection of algebraic complexity theory with zero knowledge. Along the way, we give a perfect zero knowledge analogue of the celebrated sumcheck protocol [LFKN92], by leveraging both succinct constraint detection and low-degree testing. The second algorithm exploits the recursive structure of the PCPs of Proximity to show that small-support constraints are "locally" spanned by a small number of small-support constraints.
We prove new results regarding the complexity of various complexity classes under randomized oracle reductions. We first prove that BPPPSZK⊆ AM ∩ coAM, where PSZK is the class of promise problems having statistical zero knowledge proofs. This strengthens the previously known facts that PSZK is closed under NC1truth-table reductions (Sahai and Vadhan, J. ACM '03) and that PPSZK⊆ AM ∩ coAM (Vadhan, personal communication). Our proof relies on showing that a certain class of real-valued functions that we call ℝ-TUAM can be approximated using an AM protocol. Then we investigate the power of randomized oracle reductions with relation to the notion of instance checking (Blum and Kannan, J. ACM '95). We observe that a theorem of Beigel implies that if any problem in TFNP such as Nash equilibrium is NP-hard under randomized oracle reductions, then SAT is checkable. We also observe that Beigel's theorem can be extended to an average-case setting by relating checking to the notion of program testing (Blum et al., JCSS '93). From this, we derive that if one-way functions can be based on NP-hardness via a randomized oracle reduction, then SAT is checkable. By showing that NP has a non-uniform tester, we also show that worst-case to average-case randomized oracle reduction for any relation (or language) R E NP implies that R has a nonuniform instance checker. These results hold even for adaptive randomized oracle reductions.
The abstraction of cryptographic operations by term algebras, called Dolev–Yao models, is essential in almost all tool-supported methods for proving security protocols. Recently significant progress was made in proving that Dolev–Yao models offering the core cryptographic operations such as encrypt ion and digital signatures can be sound with respect to actual cryptographic realizations and security definitions. Recent work, however, has started to extend Dolev–Yao models to more sophisticated operations with unique security features. Zero-knowledge proofs arguably constitute the most amazing such extension. In this paper, we first identify which additional properties a cryptographic (non-interactive) zero-knowledge proof needs to fulfill in order to serve as a computationally sound implementation of symbolic (Dolev–Yao style) zero-knowledge proofs; this leads to the novel definition of a symbolically-sound zero-knowledge proof system. We prove that even in the presence of arbitrary active adversaries, such proof systems constitute computationally sound implementations of symbolic zero-knowledge proofs. This yields the first computational soundness result for symbolic zero-knowledge proofs and the first such result against fully active adversaries of Dolev–Yao models that go beyond the core cryptographic operations.
Interactive proof and zero-knowledge proof systems are two important concepts in cryptography and complexity theory. In the past two decades, a great number of interactive proof and zero-knowledge proof protocols have been designed and applied in practice. In this paper, a simple memorizable zero-knowledge protocol is proposed for graph non-isomorphism problem, based on the memorizable interactive proof system,which is extended from the original definition of interactive proof and is more applicable in reality.
The cipher (or athbash, under which name Web3 defines it) is a Hebrew substitution cipher which replaces the first letter of the Hebrew alphabet (aleph, 1\) by the last (tav, ) the second (beth, J) by the last but one (shin, IJI), and so on, unti I we get to the last (ta , n), which i replaced by the first (aleph, 1\). Jan Anderson described it in Fledge Ledge Edge (WW 8. 1997229). Naturally, the idea can be applied to our alphabet; following the precedent set by atbash I name it the azby cipher.
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//).
An investigation of interactive proof systems (IPSs) where the verifier is a 2-way probabilistic finite state automaton (2pfa) is initiated. In this model, it is shown: Additional results concern two other classes of verifiers: 2pfa's that halt in polynomial expected time, and 2-way probabilistic pushdown automata that halt in polynomial time. In particular, IPSs with verifiers in the latter class are as powerful as IPSs where verifiers are polynomial-time probabilistic Turing machines. In a companion paper [7], zero knowledge IPSs with 2pfa verifiers are investigated.
A hierarchy of probabilistic complexity classes generalizing NP has recently emerged in the work of [Ba], [GMR], and [GS]. The IP hierarchy is defined through the notion of an interactive proof system, in which an all powerful prover tries to convince a probabilistic polynomial time verifier that a string w is in a language L. The verifier tosses coins and exchanges messages back and forth with the prover before he decides whether to accept w. This proof-system yields "probabilistic" proofs: the verifier may erroneously accept or reject w with small probability. In [GMR] such a protocol was defined to be a zero-knowledge protocol if at the end of the interaction the verifier has learned nothing except that w ∈ L. We study complexity theoretic implications of a language having this property. In particular we prove that if L admits a zeroknowledge proof then L can also be recognized by a two round interactive proof. This complements a result by Fortnow [F] where it is proved that the complement of L has a two round interactive proof protocol. The methods of proof are quite similar to those of Fortnow [F]. As in his case the proof works under the assumption that the original protocol is only zero-knowledge with respect to a specific verifier.
A Perfect Zero-Knowledge interactive proof system convinces a verifier that a string is in a language without revealing any additional knowledge in an information-theoretic sense. We show that for any language that has a perfect zero-knowledge proof system, its complement has a short interactive protocol. This result implies that there are not any perfect zero-knowledge protocols for NP-complete languages unless the polynomial time hierarchy collapses. This paper demonstrates that knowledge complexity can be used to show that a language is easy to prove.
Ruy de Queiroz, Luiz Carlos Pereira, Edward Hermann Hæusler
This volume contains the Proceedings of the 10th Workshop on Logic, Language, Information and Computation (WoLLIC'2003). The Workshop was held in Ouro Preto, Minas Gerais, Brazil from July 29 to August 1, 2003, in the Escola de Minas of the Universidade Federal de Ouro Preto ( UFOP ). WoLLIC is a series of workshops which started in 1994 with the aim of fostering interdisciplinary research in pure and applied logic . The idea is to provide a forum which is large enough in the number of possible interactions between logic and the sciences related to information and computation, and yet is small enough to allow for concrete and useful interaction among participants. Previous versions were held at: Recife (Pernambuco, Brazil) in 1994 and 1995; Salvador (Bahia, Brazil) in 1996; Fortaleza (Ceará, Brazil) in 1997; São Paulo (Brazil) in 1998; Itatiaia (Rio de Janeiro, Brazil) in 1999; Natal (Rio Grande do Norte) in 2000; Brasília (Distrito Federal, Brazil) in 2001; Rio de Janeiro (Brazil) in 2002. Scientific sponsorship comes from the Interest Group in Pure and Applied Logics ( IGPL ), the European Association for Logic, Language and Information ( FoLLI ), the Association for Symbolic Logic ( ASL ), European Association for Theoretical Computer Science ( EATCS ), the Sociedade Brasileira de Computação ( SBC ), and the Sociedade Brasileira de Lógica ( SBL ). Funding was kindly given by:(i) CNPq ( Conselho Nacional de Desenvolvimento Científico e Tecnológico , the scientific and technological development council of the Brazilian Ministério da Ciência e Tecnologia ) (grant 450709/2003-5);(ii) CAPES ( Fundação Coordenação de Apoio ao Aperfeiçoamento de Pessoal de Nível Superior , a Foundation for the Development of Higher-Education under the Brazilian Ministério da Educação e do Desporto ) (grant PAEP0565/03);(iii) FAPEMIG ( Fundação de Amparo à Pesquisa do Estado de Minas Gerais , the Minas Gerais state foundation for the support of scientific research);(iv) Escola de Minas da UFOP ( Universidade Federal de Ouro Preto ). Contributions were received in the form of short papers in all areas related to logic, language, information and computation, including:pure logical systems, proof theory, model theory, algebraic logic, type theory, category theory, constructive mathematics, lambda and combinatorial calculi, program logic and program semantics, logics and models of concurrency, logic and complexity theory, proof complexity, foundations of cryptography (zero-knowledge proofs), descriptive complexity, nonclassical logics, nonmonotonic logic, logic and language, discourse representation, logic and artificial intelligence, automated deduction, foundations of logic programming, logic and computation, and logic engineering. Apart from the contributed papers (15), and the invited talks (5), the programme includes 5 tutorial lectures: 1. Algorithmic Randomness and Derandomization by Eric Allender (Department of Computer Science, Rutgers, the State University of New Jersey, USA) 2. Generalized Quantifiers by Lauri Hella (Department of Mathematics, Statistics and Philosophy, University of Tampere, Finland) 3. Implicit computational complexity by Jean-Baptiste Joinet (Preuves-Programmes-Systèmes, Université Paris 7, France) 4. Proof search foundations for logic programming by Dale Miller (INRIA/Futurs/Saclay, and Laboratoire d'Informatique, École Polytechnique, France) 5. Iterated theory change by Hans Rott (Institut für Philosophie, Universität Regensburg, Germany) All papers in the volume were reviewed by the program committee consisting of Mauricio Ayala-Rinóon ( Departamento de Matemática, Universidade de Brasília, Brazil ) Argimiro Arratia ( Depto. Matematicas, Universidad Simon Bolivar, Venezuela ) Alessandra Carbone ( Institut des Hautes Études Scientifiques, and Université de Paris XII, France ) Marcelo Coniglio ( Centro de Lógica e Epistemologia, Universidade Estadual de Campinas, Brazil ) Gilles Dowek ( INRIA, France ) Arnaud Fleury ( Facoltà di Scienze, Università di Verona, Italy ) Dexter Kozen ( Cornell University, USA ) Maarten Marx ( ILLC, Faculty of Science, Universiteit Amsterdam, The Netherlands ) Anto˚nio Carlos da Rocha Costa ( Escola de Informática, Universidade Católica de Pelotas, Brazil ) Dieter Spreen ( Fachbereich Mathematik, Theoretische Informatik, Universität Siegen, Germany ) Luiz Carlos Pereira ( Departamento de Filosofia, PUC-Rio and UFRJ, Brazil ) Jouko Väänänen ( Department of Mathematics, University of Helsinki, Finland ) Renata Wassermann ( Departamento de Cie˚ncia da Computação, Instituto de Matemática e Estatística, Universidade de São Paulo, Brazil ) The organising committee consisted of Lucília Figueiredo ( Departamento de Computação, Universidade Federal de Ouro Preto, Brazil ) Fred Ulisses Maranhão ( Centro de Informática, Universidade Federal de Pernambuco, Brazil ) Anjolina Grisi de Oliveira ( Center of Informatics, Universidade Federal de Pernambuco, Brazil ) Elaine Pimentel ( Departamento de Matemática, Universidade Federal de Minas Gerais, Brazil ) (Co-Chair) Ruy de Queiroz ( Center of Informatics, Universidade Federal de Pernambuco, Brazil ) (Co-Chair) Maria Angela Weiss ( Departamento de Matemática, Universidade de São Paulo, Brazil ) The volume will be published as volume 84 in the series Electronic Notes in Theoretical Computer Science ( ENTCS ). This series is published electronically through the facilities of Elsevier B.V. and its auspices. The volumes in the ENTCS series can be accessed at the URL http://www.elsevier.nl/locate/entcs A printed version of the current volume has been distributed to the participants at the workshop in Ouro Preto. We are very grateful to the following persons, whose help has been crucial for the success of WoLLIC'2003: Mike Mislove, one of the Managing Editors of the ENTCS series, for his assistance with the use of the ENTCS style files; Thanks are also due to the Department of Mathematics of Universidade Federal de Minas Gerais and the Department of Computing of the Universidade Federal de Ouro Preto, which has provided the logistic support to the organising committee. August 2, 2003 Ruy de Queiroz, Elaine Pimentel, Lucilia Figueiredo