Imad Fakhri Taha Alshaikhli, Rusydi Hasan Makarin, Siti Khairunnisa Mohd Bakri, Nur Dalilah More Yusoff · 5 authors
Much of the current innovation in advanced materials is occurring at the nanoscale, specifically in manufactured nanomaterials (MNs). MNs display unique attributes and behaviors, and may be biologically and physically unique, making them valuable across a wide range of applications. However, as the number, diversity and complexity of MNs coming to market continue to grow, assessing their health and environmental risks with traditional animal testing approaches is too time- and cost-intensive to be practical, and is undesirable for ethical reasons. New approaches are needed that meet current requirements for regulatory risk assessment while reducing reliance on animal testing and enabling safer-by-design product development strategies to be implemented. The adverse outcome pathway (AOP) framework presents a sound model for the advancement of MN decision making. Yet, there are currently gaps in technical and policy aspects of AOPs that hinder the adoption and use for MN risk assessment and regulatory decision making. This review outlines the current status and next steps for the development and use of the AOP framework in decision making regarding the safety of MNs. Opportunities and challenges are identified concerning the advancement and adoption of AOPs as part of an integrated approach to testing and assessing (IATA) MNs, as are specific actions proposed to advance the development, use and acceptance of the AOP framework and associated testing strategies for MN risk assessment and decision making. The intention of this review is to reflect the views of a diversity of stakeholders including experts, researchers, policymakers, regulators, risk assessors and industry representatives on the current status, needs and requirements to facilitate the future use of AOPs in MN risk assessment. It incorporates the views and feedback of experts that participated in two workshops hosted as part of an Organization for Economic Cooperation and Development (OECD) Working Party on Manufactured Nanomaterials (WPMN) project titled, "Advancing AOP Development for Nanomaterial Risk Assessment and Categorization", as well as input from several EU-funded nanosafety research consortia.
José Bacelar Almeida, Endre Bangerter, Manuel Barbosa, Stephan Krenn · 6 authors
Abstract. Zero-knowledge proofs of knowledge (ZK-PoK) are important building blocks for numerous cryptographic applications. Although ZK-PoK have very useful properties, their real world deployment is typically hindered by their significant complexity compared to other (noninteractive) crypto primitives. Moreover, their design and implementation is time-consuming and error-prone. We contribute to overcoming these challenges as follows: We present a comprehensive specification language and a certifying compiler for ZK-PoK protocols based on Σ-protocols and composition techniques known in literature. The compiler allows the fully automatic translation of an abstract description of a proof goal into an executable implementation. Moreover, the compiler overcomes various restrictions of previous approaches, e.g., it supports the important class of exponentiation homomorphisms with hidden-order co-domain, needed for privacy-preserving applications such as idemix. Finally, our compiler is certifying, in the sense that it automatically produces a formal proof of security (soundness) of the compiled protocol (currently covering special homomorphisms) using the Isabelle/HOL theorem prover.
Diese Dissertation befasst sich mit effizienten zero-knowledge Beweisen von Wissen für Homomorphismen. Einerseits\nuntersuchen wir die Effizienzbeschränkungen bestehender Beweise von Wissen für Homomorphismen, andererseits\nbeschreiben wir neue Protokolle, welche diese Beschränkungen zu überwinden vermögen. Die Hauptresultate der Arbeit\nsind die Folgenden:\n- Alle effizienten Beweise von Wissen wurden, vor unserer Arbeit, mittels des Sigma Protokolls erzielt. Wir zeigen auf,\ndass für das Sigma Protokoll inhärente und demnach prinzipiell nicht überwindbare Effizienzbeschränkungen bestehen.\n- Insbesondere waren für die praktisch bedeutsame Klasse von Exponentiations-Homomorphismen in Gruppen unbekannter\nOrdnung (wie z.B., RSA- oder Klassengruppen) bisher keine effizienten zero-knowledge Beweise von Wissen bekannt. Wir\nbeschreiben neue Protokolle, die erstmalig effiziente zero-knowledge Beweise von Wissen für Exponentiations-\nHomomorphismen in Gruppen unbekannter Ordnung liefern.
We prove a number of general theorems about CZK, the class of problems possessing computational zero knowledge proofs. Our results are unconditional, in contrast to most previous works on CZK which rely on the assumption that one-way functions exist. We establish several new characterizations of CZK, and use these characterizations to prove results such as: 1) Honest-verifier CZK equals general CZK. 2) Public-coin CZK equals private-coin CZK. 3) CZK is closed under union (and more generally, "monotone formula closure"). 4) CZK with imperfect completeness equals CZK with perfect completeness. 5) Any problem in CZK /spl cap/ NP can be proven in computational zero knowledge by a BPP/sup NP/ prover. 6) CZK with black-box simulators equals CZK with general, non-black-box simulators. The above equalities refer to the resulting class of problems (and do not necessarily preserve other efficiency measures such as round complexity). Our approach is to combine the conditional techniques previously used in the study of CZK with the unconditional techniques developed in the study of SZK, the class of problems possessing statistical zero knowledge proofs. To enable this combination, we prove that every problem in CZK can be decomposed into a problem in SZK together with a set of instances from which a one-way function can be constructed.
We present the first complete problem for SZK, the class of promise problems possessing statistical zero-knowledge proofs (against an honest verifier). The problem, called Statistical Difference, is to decide whether two efficiently samplable distributions are either statistically close or far apart. This gives a new characterization of SZK that makes no reference to interaction or zero knowledge .We propose the use of complete problems to unify and extend the study of statistical zero knowledge. To this end, we examine several consequences of our Completeness Theorem and its proof, such as:---A way to make every (honest-verifier) statistical zero-knowledge proof very communication efficient, with the prover sending only one bit to the verifier (to achieve soundness error 1/2).---Simpler proofs of many of the previously known results about statistical zero knowledge, such as the Fortnow and Aiello--Hεstad upper bounds on the complexity of SZK and Okamoto's result that SZK is closed under complement.---Strong closure properties of SZK that amount to constructing statistical zero-knowledge proofs for complex assertions built out of simpler assertions already shown to be in SZK.---New results about the various measures of "knowledge complexity," including a collapse in the hierarchy corresponding to knowledge complexity in the "hint" sense.---Algorithms for manipulating the statistical difference between efficiently samplable distributions, including transformations that "polarize" and "reverse" the statistical relationship between a pair of distributions.
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.
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. It is known that zero-knowledge is not necessarily preserved in such an environment. Designing concurrent zero-knowledge proofs is a fundamental issue in the study of zero-knowledge since known zero-knowledge protocols cannot be run in a realistic modern computing environment. In this paper we present a concurrent zero-knowledge proof systems for all languages in NP. Currently, the proof system we present is the only known proof system that retains the zero-knowledge property when copies of the proof are allowed to run in an asynchronous environment. Our proof system has $\tilde{O}(\log^2 k)$ rounds (for a security parameter $k$), which is almost optimal, as it is shown by Canetti Kilian Petrank and Rosen that black-box concurrent zero-knowledge requires $\tildeΩ(\log k)$ rounds. Canetti, Goldreich, Goldwasser and Micali introduced the notion of {\em resettable} zero-knowledge, and modified an earlier version of our proof system to obtain the first resettable zero-knowledge proof system. This protocol requires $k^{θ(1)}$ rounds. We note that their technique also applies to our current proof system, yielding a resettable zero-knowledge proof for NP with $\tilde{O}(\log^2 k)$ rounds.
We show simple constant-round interactive proof systems for problems capturing the approximability, to within a factor of n , of optimization problems in integer lattices, specifically, the closest vector problem (CVP) and the shortest vector problem (SVP). These interactive proofs are for the coNP direction; that is, we give an interactive protocol showing that a vector is far from the lattice (for CVP) and an interactive protocol showing that the shortest-lattice-vector is long (for SVP). Furthermore, these interactive proof systems are honest-verifier perfect zero-knowledge. We conclude that approximating CVP (resp., SVP) within a factor of n is in N P ∩co A M . Thus, it seems unlikely that approximating these problems to within a n factor is NP-hard. Previously, for the CVP (resp., SVP) problem, Lagarias et al. (1990, Combinatorica 10 , 333–348), Håstad (1988, Combinatorica 8 , 75–81), and Banaszczyk (1993, Math. Annal. 296 , 625–635) showed that the gap problem corresponding to approximating CVP (resp., SVP) within n is in N P ∩co N P . On the other hand, Arora et al. (1997, J. Comput. System Sci. 54 , 317–331) showed that the gap problem corresponding to approximating CVP within 2 log 0.999 n is quasi-NP-hard.
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.
<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>
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.
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.
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. […]
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.
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.
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