Follow blockchain research across journals, conferences, and preprint repositories.
240 results · page 8 of 10
Gregor Pavlin, Patrick de Oude, Marinus Maris, Jan Nunnink · 5 authors
No abstract is available for this record.
David Xiao
Learning is a central task in computer science, and there are various formalisms for capturing the notion. One important model studied in computational learning theory is the PAC model of Valiant (CACM 1984). On the other hand, in cryptography the notion of "learning nothing'' is often modelled by the simulation paradigm: in an interactive protocol, a party learns nothing if it can produce a transcript of the protocol by itself that is indistinguishable from what it gets by interacting with other parties. The most famous example of this paradigm is zero knowledge proofs, introduced by Goldwasser, Micali, and Rackoff (SICOMP 1989). Applebaum et al. (FOCS 2008) observed that a theorem of Ostrovsky and Wigderson (ISTCS 1993) combined with the transformation of one-way functions to pseudo-random functions (Hastad et al. SICOMP 1999, Goldreich et al. J. ACM 1986) implies that if there exist non-trivial languages with zero-knowledge arguments, then no efficient algorithm can PAC learn polynomial-size circuits. They also prove a weak reverse implication, that if a certain non-standard learning task is hard, then zero knowledge is non-trivial. This motivates the question we explore here: can one prove that hardness of PAC learning is equivalent to non-triviality of zero-knowledge? We show that this statement cannot be proven via the following techniques: 1. Relativizing techniques: there exists an oracle relative to which learning polynomial-size circuits is hard and yet the class of languages with zero knowledge arguments is trivial. 2. Semi-black-box techniques: if there is a black-box construction of a zero-knowledge argument for an NP-complete language (possibly with a non-black-box security reduction) based on hardness of PAC learning, then NP has statistical zero knowledge proofs, namely NP is contained in SZK. Under the standard conjecture that NP is not contained in SZK, our results imply that most standard techniques do not suffice to prove the equivalence between the non-triviality of zero knowledge and the hardness of PAC learning. Our results hold even when considering non-uniform hardness of PAC learning with membership queries. In addition, our technique relies on a new kind of separating oracle that may be of independent interest.
Ning Ding, Dawu Gu
Traditionally, the definition of zero-knowledge states that an interactive proof of x â L provides zero (additional) knowledge if the view of any polynomial-time verifier can be reconstructed by a polynomial-time simulator. Since this definition only requires that the worst-case running-time of the verifier and simulator are polynomials, zero-knowledge becomes a worst-case notion. In STOCâ06, Micali and Pass proposed a new notion of precise zero-knowledge, which captures the idea that the view of any verifier in every interaction can be reconstructed in (almost) the same time (i.e., the view can be âindistinguishably reconstructedâ). This is the strongest notion among the known works towards precislization of the definition of zero-knowledge. However, as we know, there are two kinds of computational resources (i.e. time and space) that every algorithm consumes in computation. Although the view of a verifier in the interaction of a precise zero-knowledge protocol can be reconstructed in almost the same time, the simulator may run in very large space while at the same time the verifier only runs in very small space. In this case it is still doubtful to take indifference for the verifier to take part in the interaction or
Daoshun Wang
Polynomial functions are frequently used in mathematics and computer science. The zero-knowledge proof of the roots of a polynomial function is an important application of zero-knowledge, with both theoretical and practical significance. The zero-knowledge proof of the roots of a polynomial function based on the intractablity of computing the discrete logarithm to solve the multi discrete logarithm problem. The solution to the multi discrete logarithm problem is used as a building block to construct the zero-knowledge proof protocol for the roots of polynomial functions. A theoretical analysis shows that the protocol is secure and reliable.
Cristiano Castelfranchi
This chapter presents organizations as a macro-micro notion and device; they presuppose autonomous proactive entities (agents) playing the organizational roles. Agents may have their own powers, goals, relationships (of dependence, trust, etc.). This opens important issues to be discussed: Does cooperation require mentally shared plans? Which is the relationship between individual powers and role powers; personal dependencies and role dependencies; personal goals and assigned goals; personal beliefs and what we have to assume when playing our role; individual actions and organizational actions? What about possible conflicts, deviations, power abuse, given the agentsâ autonomy? MultiAgentSystems discipline should both aim at scientifically modeling human organizations, and at designing effective artificial organizations. Our claim is that for both those aims, one should model a high (risky) degree of flexibility, exploiting autonomy and pro-activity, intelligence and decentralized knowledge of roleplayers, allowing for functional violations of requests and even of rules.Request access from your librarian to read this chapter's full text.
Daoshun Wang
The multi discrete logarithm problem and the zero-knowledge proolf protocol were proposed to efficiently solve the zero-knowledge proof of the roots of polynomials,based on the hardness of computing the discrete logarithms.In the protocol,the prover computes the discrete logarithms of each term of the polynomial and obtains A1,A2,âŠ,An,which are sent to the verifier.Based on the value of(A1A2âŠAn)modp,the verifier verifies the prover's ownership of the root.The protocol needs to be executed several rounds to reduce the possibility of cheating.Theoretical analyses show that the chance of successfully cheating decays exponentially with increasing number of rounds,so the protocol is secure and reliable.
ćä» ç°äž, Keisuke Tanaka, æ”ć€Ș èć·, Keita Xagawa
No abstract is available for this record.
Justin Bledin
No abstract is available for this record.
Jonathan Katz
No abstract is available for this record.
Alfredo De Santis, Giovanni Di Crescenzo, Giuseppe Persiano, Moti Yung
We investigate structural properties of interactive perfect zero-knowledge (PZK) proofs. Specifically, we look into the closure properties of PZK languages under monotone boolean formula composition. This gives rise to new protocol techniques. We show that interactive PZK for random self-reducible (RSR) (and for co-RSR) languages is closed under monotone boolean formula composition. Namely, we present PZK proofs for monotone boolean formulae whose atoms are statements about membership in a PZK language which is RSR (or whose complement is RSR). We also discuss extensions, recent applications, and generalizations of the techniques.
Denis Vald
No abstract is available for this record.
Yi Deng, Vipul Goyal, Amit Sahai
Canetti, Goldreich, Goldwasser, and Micali (STOC 2000) introduced the notion of resettable zero-knowledge proofs, where the protocol must be zero-knowledge even if a cheating verifier can reset the prover and have several interactions in which the prover uses the same random tape. Soon afterwards, Barak, Goldreich, Goldwasser, and Lindell (FOCS 2001) studied the closely related notion of resettable soundness, where the soundness condition of the protocol must hold even if the cheating prover can reset the verifier to have multiple interactions with the same verifier's random tape. The main problem left open by this work was whether it is possible to have a single protocol that is simultaneously resettable zero knowledge and resettably sound. We resolve this question by constructing such a protocol. At the heart of our construction is a new non-black-box simulation strategy, which we believe to be of independent interest. This new strategy allows for simulators which "marry'' recursive rewinding techniques (common in the context of concurrent simulation) with non-black-box simulation. Previous non-black-box strategies led to exponential blowups in computational complexity in such circumstances, which our new strategy is able to avoid.
Hongda Li, Dengguo Feng, Bao Li, Haixia Xue
It is well known that all the known black-box zero-knowledge proofs of knowledge for NP are nonconstant-round. Whether there exit constant-round black-box zero-knowledge proofs of knowledge for all NP languages under certain standard assumptions is a open problem. This paper focuses on the problem and give a positive answer by presenting two constructions of constant-round (black-box) zero-knowledge proofs of knowledge for the HC (Hamiltonian Cycle) problem. By the recent result of Katz, our second construction which relies on the existence of claw-free functions has optimal round complexity (5-round) assuming the polynomial hierarchy does not collapse.
Michael Backes, Dominique Unruh
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.
Ning Ding, Dawu Gu
We present a stronger notion of zero-knowledge: precise concurrent zero-knowledge. Our notion captures the idea that the view of any verifier in concurrent interaction can be reconstructed in the almost same time (within a constant/polynomial factor). Precise zero-knowledge in stand-alone setting was introduced by Micali and Pass in STOCâ06 (The original work used the term âlocal zero-knowledgeâ.). Their notion shows that the view of any verifier can be reconstructed in the almost same time in stand-alone setting. Hence our notion is the generalization of their notion in concurrent setting. Furthermore, we propose a Ï(log 2 n)-round concurrent zero-knowledge argument for NP with linear precision, which shows that the view of any verifier in concurrent interaction can be reconstructed by the simulator with linear-time overhead. Our argument is Feige-Lapidot-Shamir type which consists of a proof-preamble and a proof-body for a modified NP statement. Our result assumes the restriction of adversarial scheduling the communication that the concurrent interaction of preambles of all sessions will be scheduled before any proof-body by the adversarial verifier. 1
Shien Jin Ong, Salil Vadhan
No abstract is available for this record.
Enrico Pontelli
One of the main goals of the Semantic Web initiative [3] is to extend the current Web technology to allow for the development of intelligent agents, which can automatically and unambiguously process the information available on millions of web pages. It has been recognized very early in the development of the Semantic Web that rules are essential for the Web3 and for Semantic Web applicationsâe.g., description of semantic web services, rules interchange for e-business applications. The RuleML initiative is a response to the need of a shared rule markup language using XML markup, which has a precisely defined semantics and efficient implementations. In recent years, a significant amount of work has been devoted to develop knowledge representation languages suitable for the task and a variety of languages for rule markup has been proposed. The initial design [4] included a distinction (in terms of distinct DTDs) between reaction rules and derivation rules. The first type of rules is used for the encoding of event-condition-action (ECA) rules while the second is meant for the encoding of implicational/inference rules. Despite the fact that many different proposals for ECA rules encoding have appeared the work on ECA rules is still very vague. The most recent modularized description of RuleML [6] reports this area (indicated as PR RuleML in that document) as work in progress. The derivation rules component of the RuleML initiative has originated a family of languages.4, Datalog plays the role of a core language, with simplified versions (unary and binary Datalog) developed for combining RuleML with OWL (as in SWRL). Various sublanguages have been created to include features like explicit equality (e.g., fologeq), negation as failure (e.g., naffolog), and Hilog layers (e.g., hohornlog). Various authors [7] have argued that any realistic architecture for the Semantic Web must be based on various independent but interoperable languages, including logic programming languages with and without negation-as-failure. The need for these languages and their interaction have been discussed (e.g., [8, 7]). It is also of
Rudolf Barczi
No abstract is available for this record.
Satoshi Hada, Teruo Tanaka
The notion of correlation intractable function ensembles (CIFEs) was introduced in an attempt to capture the unpredictability property of random oracles [12]: If O is a random oracle then it is infeasible to find an inputx such that the input-output pair (x,O(x)) has some desired property. In this paper, we observe relationships between zero-knowledge protocols and CIFEs. Specifically, we show that, in the non-uniform model, the existence of CIFEs implies that 3-round auxiliary-input zero-knowledge (AIZK) AM interactive proofs exist only for BPP languages. In the uniform model, we show that 3-round AIZK AM interactive proofs with perfect completeness exist only for easy-to-approximate languages. These conditional triviality results extend to constant-round AIZK AM interactive proofs assuming the existence of CIFEs, where multi-input means that the correlation intractability is satisfied with respect to multiple input-output pairs. Also, as a corollary, we show that any construction of uniform CIFEs from uniform one-way functions proves unconditionally that constant-round AIZK AM interactive proofs with perfect completeness only for easy-to-approximate languages.
Giorgi Japaridze
No abstract is available for this record.
Koji Chida, Go Yamamoto
No abstract is available for this record.
V. Arvind, Bireswar Das
No abstract is available for this record.
Endre Bangerter
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.
Hoeteck Wee
No abstract is available for this record.