Follow blockchain research across journals, conferences, and preprint repositories.
486 results · page 20 of 21
Jan Camenisch, Aggelos Kiayias, Moti Yung
No abstract is available for this record.
Andrew Chi-Chih Yao, Frances Yao, Yunlei Zhao
No abstract is available for this record.
Joël Alwen, Abhi Shelat, Ivan Visconti
No abstract is available for this record.
Guomin Yang, Jing Chen, Duncan S. Wong, Xiaotie Deng · 5 authors
No abstract is available for this record.
Michael Backes, Matteo Maffei, Dominique Unruh
We devise an abstraction of zero-knowledge protocols that is accessible to a fully mechanized analysis. The abstraction is formalized within the applied pi-calculus using a novel equational theory that abstractly characterizes the cryptographic semantics of zero-knowledge proofs. We present an encoding from the equational theory into a convergent rewriting system that is suitable for the automated protocol verifier ProVerif. The encoding is sound and fully automated. We successfully used ProVerif to obtain the first mechanized analysis of (a simplified variant of) the Direct Anonymous Attestation (DAA) protocol. This required us to devise novel abstractions of sophisticated cryptographic security definitions based on interactive games. The analysis reported a novel attack on DAA that was overlooked in its existing cryptographic security proof. We propose a revised variant of DAA that we successfully prove secure using ProVerif.
Jan Camenisch, Rafik Chaabouni, Abhi Shelat
No abstract is available for this record.
Éric Filiol
This paper presents a protocol aiming at proving that an encryption system contains structural weaknesses without disclosing any information on those weaknesses. A verifier can check in a polynomial time that a given property of the cipher system output has been effectively realized. This property has been chosen by the prover in such a way that it cannot been achieved by known attacks or exhaustive search but only if the prover indeed knows some undisclosed weaknesses that may effectively endanger the cryptosystem security. This protocol has been denoted zero-knowledge-like proof of cryptanalysis. In this paper, we apply this protocol to the Bluetooth core encryption algorithm E0, used in many mobile environments and thus we suggest that its security can seriously be put into question.
Jens Groth, Rafail Ostrovsky
No abstract is available for this record.
Ivan Damgård, Jesper Buus Nielsen, Daniel Wichs
We introduce a new notion called `-isolated proofs of knowledge (`-IPoK). These are proofs of knowledge where a cheating prover is allowed to exchange up to ` bits of communication with some external adversarial environment during the run of the proof. Without any additional setup assumptions, no witness hiding protocol can be an `-IPoK for unbounded values of `. However, for any pre-defined threshold `, and any relation in NP and we construct an `-IPoK protocol for that relation. The resulting protocols are zero knowledge (ZK) in the standard sense, i.e., w.r.t. a verifier that communicates only with the prover during the proof. The cost of having a large threshold ` is a large communication complexity of the constructed protocol. We analyze these costs and present a solution that is asymptotically optimal. If a cheating verifier is allowed to communicate arbitrarily with an external environment, it is not possible to construct an `-IPoK that is also ZK with respect to such a verifier. As another new notion, we define `-isolated zero knowledge (`-IZK) where the verifier is `-isolated. For every relation in NP and every `, we construct an `-IPoK protocol that is also `-IZK. We describe several applications of `-IPoK protocols under the physical assumption that one can `isolate a prover for the duration of the proof phase. Firstly, we can use a witness indistinguishable (WI) `-IPoK to prevent “man-in-the-middle” attacks on identification schemes. Prior results for this scenario required all verifiers to register keys under a PKI, or the ability to fully isolate the prover. Secondly, a partially isolated prover can register a public key and use a WI `-IPoK to prove knowledge of the corresponding secret key to another party acting as a verifier. This allows us to set up a PKI where the key registrant does not need to trust the Certificate Authority. The PKI is not perfect since the proof is only witness indistinguishable and not zero knowledge. In a companion paper, we show how to set up such a PKI and use it to implement arbitrary multiparty computation securely in the UC framework without relying on any trusted third parties.
David Wagner
No abstract is available for this record.
Adam Wierzbicki, Aneta Zwierko, Zbigniew Kotulski
This paper describes a new protocol for authentication in ad-hoc networks. The protocol has been designed to meet specialized requirements of ad-hoc networks, such as lack of direct communication between nodes or requirements for revocable anonymity. At the same time, a ad-hoc authentication protocol must be resistant to spoofing, eavesdropping and playback, and man-in-the-middle attacks. The article analyzes existing authentication methods based on the Public Key Infrastructure, and finds that they have several drawbacks in ad-hoc networks. Therefore, a new authentication protocol, basing on established cryptographic primitives (Merkle's puzzles and zero-knowledge proofs) is proposed. The protocol is studied for a model ad-hoc chat application that provides private conversations.
Theodoros Balopoulos, Stephanos Gritzalis, Sokratis Katsikas
Esoteric protocols, such as electronic cash, electronic voting and selective disclosure protocols, use special message constructors that are not widely used in other types of protocols (for example, in authentication protocols). These message constructors include blind signatures, commitments and zero-knowledge proofs. Furthermore, a standard formalization of the Dolev-Yao intruder [6] does not take into account these message constructors, nor does it consider some types of attacks (such as privacy attacks, brute-force dictionary attacks and known-plaintext attacks) that esoteric as well as other types of protocols are designed to protect against. This paper aims to present an extension of typed MSR [3, 4] in order to formally specify the needed message constructors, as well as the capabilities of a Dolev-Yao intruder designed to attack esoteric protocols.
Jonathan Katz, Yehuda Lindell
No abstract is available for this record.
Craig Gentry, Dávid Molnár, Zulfikar Ramzan
Abstract. Most prior designated confirmer signature schemes either prove security in the random oracle model (ROM) or use general zeroknowledge proofs for NP statements (making them impractical). By slightly modifying the definition of designated confirmer signatures, Goldwasser and Waisbard presented an approach in which the Confirm and ConfirmedSign protocols could be implemented without appealing to general zero-knowledge proofs for NP statements (their Disavow protocol still requires them). The Goldwasser-Waisbard approach could be instantiated using Cramer-Shoup, GMR, or Gennaro-Halevi-Rabin signatures. In this paper, we provide an alternate generic transformation to convert any signature scheme into a designated confirmer signature scheme, without adding random oracles. Our key technique involves the use of a signature on a commitment and a separate encryption of the random string used for commitment. By adding this “layer of indirection, ” the underlying protocols in our schemes admit efficient instantiations (i.e., we can avoid appealing to general zero-knowledge proofs for NP statements) and furthermore the performance of these protocols is not tied to the choice of underlying signature scheme. We illustrate this using the Camenisch-Shoup variation on Paillier’s cryptosystem and Pedersen commitments. The confirm protocol in our resulting scheme requires 10 modular exponentiations (compared to 320 for Goldwasser-Waisbard) and our disavow protocol requires 41 modular exponentiations (compared to using a general zero-knowledge proof for Goldwasser-Waisbard). Previous schemes use the encryption of a signature paradigm, and thus run into problems when trying to implement the confirm and disavow protocols efficiently. 1
Masayuki Abe, Serge Fehr
Abstract. We propose the first distributed discrete-log key generation (DLKG) protocol from scratch which is adaptively-secure in the nonerasure model, and at the same time completely avoids the use of interactive zero-knowledge proofs. As a consequence, the protocol can be proven secure in a universally-composable (UC) like framework which prohibits rewinding. We prove the security in what we call the singleinconsistent-player UC model, which guarantees arbitrary composition as long as all protocols are executed by the same players. As an application, we propose a fully UC threshold Schnorr signature scheme. Our results are based on a new adaptively-secure Feldman VSS scheme. Although adaptive security was already addressed by Feldman in the original paper, the scheme requires secure communication, secure erasure, and either a linear number of rounds or digital signatures to resolve disputes. Our scheme overcomes all of these shortcomings, but on the other hand requires some restriction on the corruption behavior of the adversary, which however disappears in some applications including our new DLKG protocol. We also propose several new adaptively-secure protocols, which may find other applications, like a sender non-committing encryption scheme, a distributed trapdoor-key generation protocol for Pedersen’s commitment scheme, or distributed-verifier proofs for proving relations among commitments or even any NP relations in general. 1
Anna Redz
This thesis is written for the Swedish degree Licentiate ofScience, Teknisk Licentiat.It is a university degree, between that of master andthat of doctor.The main focus of the thesis is on the construction ofsecure protocols for comparing the underlying plain-texts inElGamal encryptions. The protocols make use of the malleabilityof the ElGamal encryption scheme. More specifically they usethe multiplicative homomorphic property of ElGamal.We present fully verifiable protocols for both thetwo-party setting and the multi-party setting. These protocolsare built on sub-protocols, which are specially constructed tofit the present setting. We also present full proofs forcompleteness, soundness, and zero-knowledge for all the givenprotocols, in the random oracle model.
Mario Di Raimondo, Rosario Gennaro
No abstract is available for this record.
Yong-Sork Her, 容碩 許, キョ, ヨウソク, Kouichi Sakurai · 6 authors
In this paper, we propose the absentee e-voting system based on security, completeness and verifiability. We use r-th residue cryptography for homomorphic encryption, ZKIP (Zero-Knowledge interactive proofs), RSA algorithm for the secure absentee e-voting.
Michael O’Donnell
In this paper we examine the role of Identification Protocols in the field of Cryptography. Firstly, the rationale behind the need for Identification Protocols is discussed. Secondly, we examine, in detail, challenge-response protocols, based upon zero-knowledge proofs, that form a subset of Identification Protocols in general. Thirdly, the mathematical tools necessary for the understanding of how these protocols work is given. Finally, we discuss four main Identification Protocols: Fiat-Shamir, Feige-Fiat-Shamir, Schnorr and Guillou- Quisquater. This discussion includes the theory, practical examples and the security aspects of each protocol.
Tzafrir Cohen, Joe Kilian, Erez Petrank
No abstract is available for this record.
Markus Jakobsson, Claus-Peter Schnorr
We study the notion of meta-proofs, which, as the name indicates, are proofs about proofs. We employ the notion of meta-proofs to produce a highly efficient oblivous proof of correct exponentiation. It is minimum-knowledge independently of whether the input is valid or not, a property that does not hold for many other protocols (that are zero-knowledge only for valid inputs.) This has direct security implications to multiparty protocols, where the protocols we demonstrate — one interactive and one non-interactive — can be employed to obtain protocol robustness at a low cost. As a result of potential independent interest, we show how to turn any standard discrete log signature scheme into a scheme for proving equality of discrete logarithms. We demonstrate our method using the Schnorr signature scheme.
Liqun Chen
No abstract is available for this record.
Cynthia Dwork, Moni Naor, Amit Sahai
Concurrent executions of a zero-knowledge protocol by a single prover (with one or more verifiers) may leak information and may not be zero-knowledge in toto . In this article, we study the problem of maintaining zero-knowledge.We introduce the notion of an (α, β) timing constraint : for any two processors P 1 and P 2 , if P 1 measures α elapsed time on its local clock and P 2 measures β elapsed time on its local clock, and P 2 starts after P 1 does, then P 2 will finish after P 1 does. We show that if the adversary is constrained by an (α, β) assumption then there exist four-round almost concurrent zero-knowledge interactive proofs and perfect concurrent zero-knowledge arguments for every language in NP . We also address the more specific problem of Deniable Authentication , for which we propose several particularly efficient solutions. Deniable Authentication is of independent interest, even in the sequential case; our concurrent solutions yield sequential solutions without recourse to timing , that is, in the standard model.
Ronald Cramer, Ivan Damgård
We present a 4-move zero-knowledge proof system [21] for any NP language L, which allows showing that x 2 L with error probability less than 2 \\Gammak using communication corresponding to O(jxj c )+O(k) bit commitments, where c is a constant depending only on L. We also present a 4-move perfect zero knowledge interactive argument for any NP-language L. On input x 2 L, the communication complexity is O(jxj c ) \\Delta max(k; l) bits, where l is the security parameter for the prover 1 . The protocols can be based on any bit commitment scheme with a particular set of properties. We suggest efficient implementations based on discrete logarithms or factoring. As a function of the security parameters, our protocols have the smallest known asymptotic communication complexity among general proofs or arguments for NP. Moreover, the constants involved are small enough for the protocols to be practical in a realistic situation: our protocols allows proving/arguing satisfiability of a Boo...