Blockchain Papers

Jiangtao Li, Ninghui Li, Rui Xue

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.

Jia Yu, Fanyu Kong, Rong Hao

In this paper, a new forward secure threshold signature scheme is presented, which is the first one from bilinear pairings. Compared with the known schemes against malicious adversary, the new scheme needs the fewest interactions and is very efficient. As an additional contribution, we present a new interactive zero-knowledge proof protocol and convert it into a non-interactive protocol to verify the validity of part signatures in this scheme. The scheme is robust against malicious adversary and forward secure in the random oracle model

Sultan Almuhammadi, Clifford Neuman

A zero-knowledge proof (ZKP) is an interactive proof that allows a prover to prove the knowledge of a secret to a verifier without revealing it. ZKPs are powerful tools to deal with critical applications in security e-commerce. Existing ZKPs are iterative in nature; their protocols require multiple communication rounds. The cost of iteration makes ZKPs unsuitable in practice. We propose a new protocol that meets all the requirements of ZKPs, yet runs in one round. The new approach substantially reduces computation and communications costs. It makes ZKPs more suitable for practical cryptographic systems for both government and commercial applications.

Baozheng Yu, Congwei Xu

Recently, M. Sekhar gave a digital signature scheme with message recovery, where only a specific verifier can directly check the validity of the signature. A third party can distinguish a valid signature through a zero-knowledge proof protocol. However we find that the proposed scheme is insecure. A forgery attack strategy on M. Sekhar's scheme has been designed; anyone who has a valid signature can forge a signature on an arbitrary message. An improved signature scheme, which can resist the forgery attack and a zero-knowledge proof protocol with which a third party can distinguish a valid signature are presented. Also, the security of the improved scheme is analyzed

Ben Soh Amitabh Saxena

In this paper we propose a two-round authenticated key agreement protocol using non-interactive zero-knowledge (NIZK) proofs. Essentially, a NIZK proof allows a prover to convince a verifier about the correctness of a statement without interaction. An obvious application of this is in a two-round key agreement protocol where each participant proves non-interactively the knowledge of the private key and a shared secret. Our key agreement protocol is based on this idea and is secure assuming the hardness of the Diffie-Hellman problem (DHP) and another related problem in bilinear maps.

Cheng Song

Traditional design of authenticated key exchange protocol considers communication security, but seldom takes into account the security threat of server compromises. Whenever an authentication server is captured, the intruder can immediately masquerade as legitimate users to successfully log into the system. Although some zero-knowledge-proof methods were designed to relieve this threat, their computation is relatively high due to computationally heavy modular exponentiations employed. A dynamic-verifier based authenticated key exchange protocol is proposed, where the server stores a dynamically changing password-verifier and no password leakage would occur even when the server’s verifier database is stolen. DV-AKE is especially useful for applications where lightweight client is required or lower server computational load is preferred.

Bo Yang

Committed oblivious transfer is the natural fusion of one-out-of-two oblivious transfer and bit commitment. Unfortunately, the protocols proposed before are not only complicated but also very inefficient. This paper describes a new committed oblivious transfer protocol based on a first two round string oblivious transfer and bit commitment with XOR. With a first two round string oblivious transfer, the protocol can avoid performing a large number of bit oblivious transfers. And with bit commitment with XOR, zero knowledge proofs are very easy. The protocol is conceptually simple and more efficient. The security and complexity of the protocol are also discussed in this paper.

Yuen-Yan Chan, Jin Li

No abstract is available for this record.

David Wagner

No abstract is available for this record.

Alejandro Hevia

No abstract is available for this record.

Hitoshi Asaeda, M. Rahman, Mohammad Hossein Manshaei, Yasuko Fukuzawa

In a mobile ad-hoc network (MANET) architecture, there is no pre-existing fixed network infrastructure, and a mobile node in this network sends data packets to a destination node directly or through its neighbor nodes. This situation is of potential security concern since the neighbor nodes cannot be always trusted. In this paper, we design a group member authentication protocol used in a MANET. It aims to allow a set of nodes to legitimately participate in group communication and then distribute a secret group key to the approved nodes to establish secure communication with group members. Our protocol provides knowledge-based group member authentication, which recognizes a list of secret group keys held in a mobile node as the node's group membership. It employs zero knowledge proof and threshold cryptography. We then introduce our actual implementation and evaluate the behavior to ensure its successful deployment

Rafail Ostrovsky, Giuseppe Persiano, Ivan Visconti

One of the central questions in Cryptography is to design round-efficient protocols that are secure under man-in-the-middle attacks. In this paper we introduce and study the notion of non-malleable witness indistinguishability (NMWI) and examine its relation with the classic notion of non-malleable zero knowledge (NMZK). Indeed, despite tremendous applicability of witness indistinguishability, while a lot of attention has been given to NMZK, very little attention has been given to witness indistinguishability in case of man-in-the-middle attacks. We initiate this study, with several (perhaps somewhat surprising) results: • We give the first definition of NMWI proof systems. Just like every NMZK proof is a zero-knowledge proof which aims to attain a very strong proof independence property, we require (and formalize) the notion that every NMWI proof is a witness indistinguishable proof system which enjoys a very strong witness independence property against any man-in-the-middle attack. • We show the existence of a constant-round NMWI argument system for NP in the standard model (i.e. without any trusted or any other setup assumptions).

Jiangtao Li, Ninghui Li

No abstract is available for this record.

Toru Nakanishi, Nobuo Funabiki

No abstract is available for this record.

Rosario Gennaro, Silvio Micali

No abstract is available for this record.

Jianzhong Zhang

A zero-knowledge proof scheme of identity authentication based on ElGamal digital signature is proposed,across zero-knowledge proof and smart card technology,we authenticate the user's identity efficiently and secretly.The scheme is secure under the assumption of the intractability of logarithm problems and the random oracle model.

Giuseppe Persiano, Ivan Visconti

No abstract is available for this record.

Jens Groth

No abstract is available for this record.

Lei Yang

The RFID tag offers a viable and powerful replacement for barcodes.The challenge in providing security for low cost RFID tags is that they are computationally weak devices,unable to perform even basic symmetrickey cryptographic operations.In this paper,the risk of security in RFID technology is discussed,so the authentication protocol is very necessary.However,there are some disadvantages in the two types of authentication protocols which are widely used at present.An authentication protocol based on zero knowledge proof which is suitable for RFID technology is put forward,and its validity and performance is analyzed.

Dengguo Feng, Dongdai Lin, Moti Yung

No abstract is available for this record.

Theodoros Balopoulos, Stefanos Gritzalis, Sokratis Katsikas

Electronic voting, as well as other privacy-preserving protocols, use special cryptographic primitives and techniques that are not widely used in other types of protocols, e.g. in authentication protocols. These include blind signatures, commitments, zero-knowledge proofs, mixes and homomorphic encryption. Furthermore, typical formalizations of the Dolev-Yao intruder's capabilities do not take into account these primitives and techniques, nor do they consider some types of attacks that e-voting as well as other types of protocols are designed to protect against, such as privacy attacks due to undesired linkability of protocol executions. This work aims to extend Typed MSR so that it is able to support the specification of privacy-preserving protocols, as well as the capabilities of a Dolev-Yao intruder designed to attack such protocols.

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.