Blockchain Papers

Grzegorz Dobrowolski

No abstract is available for this record.

Claus Akira Matsushigue

Various types of sysfems o/ proai/istc proa/s have played a decisive role in the development of Computer Science Theory in the last decade. This can be verified through the great number of studies about interactive proofs, zero-knowledge proofs, and transparent (or holographic) proofs. These topics are guided by the robustness of the codifications and by the computational capacity of checking them. In this text, we aim at presenting a ecncal ntroduc on reZaiue fo the proabilstcaZZy checkaZe robust proa/s. Within this approach. the new characterization of the non-deterministic polynomial-time class through the Probabilistically Checkable Proofs class formulated by Arara, Lund, Motwani. Sudan e Szegedy in IALM+92], ./V'P = PCP(logo, 1), is of central importance. We intend to prove this characterization, because it encompasses the principal points of the subject and. furthermore, covers subjacently a wide set of computational, algebraic. and probabilistic tools. which are fundamental in this topic.

Ivan Damgård, Birgit Pfitzmann

<p>We study the behavior of interactive arguments under sequential iteration, in particular how this affects the error probability. This problem turns out to be more complex than one might expect from the fact that for interactive proofs, the error trivially decreases exponentially in the number of iterations.<br />In particular, we study the typical efficient case where the iterated protocol is based on a single instance of a computational problem. This is not a special case of independent<br />iterations of an entire protocol, and real exponential decrease of the error cannot be expected, but nevertheless, for practical applications, one needs concrete relations<br />between the complexity and error probability of the underlying problem and that of the iterated protocol. We show how this problem can be formalized and solved using the<br />theory of proofs of knowledge.<br /> We also prove that in the non-uniform model of complexity the error probability<br />of independent iterations of an argument does indeed decrease exponentially - to our knowledge this is the first result about a strictly exponentially small error probability in a computational cryptographic security property. <br />As an illustration of our first result, we present a very efficient zero-knowledge argument<br />for circuit satisfiability, and thus for any NP problem, based on any collision-intractable hash function. Our theory applies to show the soundness of this protocol. Using an efficient hash function such as SHA-1, the protocol can handle about 20000 binary gates per second at an error level of 2^−50.</p><p>Keywords -- Interactive proofs, arguments, proofs of knowledge, computational security,<br />efficient general primitives, multi-bit commitment, statistical zero-knowledge.</p>

Oded Goldreich

No abstract is available for this record.

Joe Kilian, Erez Petrank, Gábor Tardos

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.

Ivan B. Damg aard, R.J.F. Cramer

Assume we are given a language $L$ with an honest verifier perfect zero-knowledge proof system. Assume also that the proof system is a $\leq 3$ move Arthur-Merlin game. The class of such languages includes all random self-reducible language, and also any language with a perfect zero-knowledge non-interactive proof. We show that such a language satisfies a certain closure property, namely that languages constructed from $L$ by applying certain monotone functions to statements on membership in $L$ have perfect zero-knowledge proof systems. The new set of languages we can build includes $L$ itself, but also for example languages consisting of $n$ words of which at least $t\leq n$ are in $L$. A similar closure property is shown to hold for the complement of $L$ and for statistical zero-knowledge. The property we need for the monotone functions used to build the new languages is that there are efficient secret sharing schemes for their associated access structures. This includes (but is not necessarily limited to) all monotone functions with polynomial size monotone formulas.

Ivan Damgård, Ronald Cramer

We present a zero-knowledge proof system [19] for any NP language L, which<br />allows showing that x in L with error probability less than 2^−k using communication<br />corresponding to O(|x|^c) + k bit commitments, where c is a constant depending only<br />on L. The proof can be based on any bit commitment scheme with a particular set<br />of properties. We suggest an efficient implementation based on factoring.<br />We also present a 4-move perfect zero-knowledge interactive argument for any NP-language<br />L. On input x in L, the communication complexity is O(|x|^c) max(k; l)<br />bits, where l is the security parameter for the prover. Again, the protocol can be<br />based on any bit commitment scheme with a particular set of properties. We suggest<br />efficient implementations based on discrete logarithms or factoring.<br />We present an application of our techniques to multiparty computations, allowing<br />for example t committed oblivious transfers with error probability 2^−k to be done<br />simultaneously using O(t+k) commitments. Results for general computations follow<br />from this.<br />As a function of the security parameters, our protocols have the smallest known<br />asymptotic communication complexity among general proofs or arguments for NP.<br />Moreover, the constants involved are small enough for the protocols to be practical in<br />a realistic situation: both protocols are based on a Boolean formula Phi containing and-<br />, or- and not-operators which verifies an NP-witness of membership in L. Let n be<br />the number of times this formula reads an input variable. Then the communication<br />complexity of the protocols when using our concrete commitment schemes can be<br />more precisely stated as at most 4n + k + 1 commitments for the interactive proof<br />and at most 5nl +5l bits for the argument (assuming k <= l). Thus, if we use k = n,<br />the number of commitments required for the proof is linear in n.<br />Both protocols are also proofs of knowledge of an NP-witness of membership in<br />the language involved.

Alfredo De Santis, Giuseppe Persiano

No abstract is available for this record.

Oded Goldreich

A proof is whatever convinces me. Shimon Even (1935–2004) The glory attached to the creativity involved in finding proofs makes us forget that it is the less glorified process of verification that gives proofs their value. Conceptually speaking, proofs are secondary to the verification process, whereas technically speaking, proof systems are defined in terms of their verification procedures. The notion of a verification procedure presumes the notion of computation and furthermore the notion of efficient computation. This implicit stipulation is made explicit in the definition of NP , where efficient computation is associated with deterministic polynomial-time algorithms. However, as argued next, we can gain a lot if we are willing to take a somewhat non-traditional step and allow probabilistic verification procedures. In this chapter, we shall study three types of probabilistic proof systems, called interactive proofs, zero-knowledge proofs , and probabilistic checkable proofs . In each of these three cases, we shall present fascinating results that cannot be obtained when considering the analogous deterministic proof systems. Summary: The association of efficient procedures with deterministic polynomial-time procedures is the basis for viewing NP-proof systems as the canonical formulation of proof systems (with efficient verification procedures). Allowing probabilistic verification procedures and, moreover, ruling by statistical evidence gives rise to various types of probabilistic proof systems. Indeed, these probabilistic proof systems carry a probability of error (which is explicitly bounded and can be reduced by successive applications of the proof system), yet they offer various advantages over the traditional (deterministic and errorless) proof systems. […]

Toshiya Itoh, Atsushi Kawakubo

No abstract is available for this record.

Oded Goldreich, Eyal Kushilevitz

No abstract is available for this record.

Cynthia Dwork, Larry Stockmeyer

The zero knowledge properties of interactive proof systems (IPSs) are studied in the case that the verifier is a 2-way probabilistic finite state automaton (2pfa). The following results are proved: A new definition of zero knowledge is introduced. This definition captures a concept of “zero knowledge” for IPSs that are used for language recognition.

Mike Burmester

No abstract is available for this record.

William Aiello, Johan Håstad

No abstract is available for this record.

Gilles Brassard, Claude Crépeau, Moti Yung

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...

Oded Goldreich

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.

Cynthia Dwork, Larry Stockmeyer

No abstract is available for this record.

Oded Goldreich, Eyal Kushilevitz

No abstract is available for this record.

Joe Kilian

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.>

Joseph Y. Halpern, Yjoram Moses, Mark R. Tuttle

While the intuition underlying a zero knowledge proof system [GMR85] is that no “knowledge” is leaked by the prover to the verifier, researchers are just beginning to analyze such proof systems in terms of formal notions of knowledge. In this paper, we show how interactive proof systems motivate a new notion of practical knowledge, and we capture the definition of an interactive proof system in terms of practical knowledge. Using this notion of knowledge, we formally capture and prove the intuition that the prover does not leak any knowledge of any fact (other than the fact being proven) during a zero knowledge proof. We extend this result to show that the prover does not leak any knowledge of how to compute any information (such as the factorization of a number) during a zero knowledge proof. Finally, we define the notion of a weak interactive proof in which the prover is limited to probabilistic, polynomial-time computations, and we prove analogous security results for such proof systems. We show that, in a precise sense, any nontrivial weak interactive proof must be a proof about the prover's knowledge, and show that, under natural conditions, the notions of interactive proofs of knowledge defined in [TW87] and [FFS87] are instances of weak interactive proofs.

Johannes Sedlmeir, Steffen Schwalm

Zero knowledge protocols provide a way of proving that a statement is true without revealing anything other than the correctness of the claim. Zero knowledge protocols have practical applications in cryptography and are used in many applications. While some applications only exist on a specification level, a direction of research has produced real-world applications. Zero knowledge protocols, also referred to as zero knowledge proofs, are a type of protocol in which one party, called the prover, tries to convince the other party, called the verifier, that a given statement is true. Sometimes the statement is that the prover possesses a particular piece of information. This is a special case of zero knowledge protocol called a zero-knowledge proof of knowledge. Formally, a zero-knowledge proof is a type of interactive proof.

Yair Oren

No abstract is available for this record.

Gilles Brassard, Claude Crépeau

A perfect zero-knowledge interactive proof is a protocol by which Alice can convince Bob of the truth of some theorem in a way that yields no information as to how the proof might proceed (in the sense of Shannon's information theory). We give a general technique for achieving this goal for any problem in NP (and beyond). The fact that our protocol is perfect zero-knowledge does not depend on unproved cryptographic assumptions. Furthermore, our protocol is powerful enough to allow Alice to convince Bob of theorems for which she does not even have a proof. Whenever Alice can convince herself probabilistically of a theorem, perhaps thanks to her knowledge of some trap-door information, she can convince Bob as well without compromising the trap-door in any way. This results in a non-transitive transfer of confidence from Alice to Bob, because Bob will not be able to subsequently convince someone else that the theorem is true. Our protocol is dual to those of [GMW1, BC].

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