In this paper, a non-interactive zero-knowledge proof scheme is proposed for secure identification in wireless networks, and it uses a timed oblivious transfer technique to enable a single verifier to identify multiple provers. The verifier and the prover do not need to be synchronized in this scheme. This scheme also enjoys the distance bounding property which makes the proposed scheme invulnerable to the relay attack. We propose to use the order statistic for the detection of relay attackers. We show that it is optimal in terms of minimum variance. Finally, we will shed some light on implementation issues of our proposed scheme.
A multi-signature scheme enables a group of signers to produce a compact, joint signature on a common document, and has many potential uses. However, existing schemes impose key setup or PKI requirements that make them impractical, such as requiring a dedicated, distributed key generation protocol amongst potential signers, or assuming strong, concurrent zero-knowledge proofs of knowledge of secret keys done to the CA at key registration. These requirements limit the use of the schemes. We provide a new scheme that is proven secure in the plain public-key model, meaning requires nothing more than that each signer has a (certified) public key. Furthermore, the important simplification in key management achieved is not at the cost of efficiency or assurance: our scheme matches or surpasses known ones in terms of signing time, verification time and signature size, and is proven secure in the random-oracle model under a standard (not bilinear map related) assumption. The proof is based on a simplified and general Forking Lemma that may be of independent interest.
Juan Ramón Troncoso-Pastoriza, Fernando Pérez‐González
Current zero-knowledge watermark detectors are based on a linear correlation between the asset features and a given secret sequence.This detection function is susceptible of being attacked by sensitivity attacks,for which zero-knowledge does not provide protection.In this paper a new zero-knowledge watermark detector robust to sensitivity attacks is presented,using the Generalized Gaussian Maximum Likelihood (ML)detector as basis.The inherent robustness that this detector presents against sensitivity attacks,together with the security provided by the zero-knowledge protocol that conceals the keys that could be used to remove the watermark or to produce forged assets,results in a robust and secure protocol.Additionally,two new zero-knowledge proofs for modulus and square root calculation are presented;they serve as building blocks for the zero-knowledge implementation of the Generalized Gaussian ML detector,and also open new possibilities in the design of high level protocols.
Advanced Steganography and Watermarking Techniques
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.
A small size group signature scheme based on RSA cryptosystem is described in this paper. Due to the special algebraic structure of RSA, one public key and two corresponding private keys are available. The two private keys are used as signature keys for group members. The signature operation includes an ordinary RSA signature and a zero knowledge proof about signature key. Compared with most group schemes, it has low computational cost as to signature and verification.
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
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.
Authentication forms the basis for most applications on the Internet. However, at the IP level, no solid mechanism yet exists for detecting 'spoofed' IP packets. The need for authenticating source IP addresses has become eminent with the advent of many ingenious DDoS attacks. In this paper, we propose a type of authentication scheme based on group (or multi party) signatures and discuss applications of such a scheme in preventing and detecting many types of DDoS attacks found on the Internet. Group signatures authenticate groups of senders rather than individuals and using such a scheme, senders can prove membership of a particular group without having to reveal their individual identity. The main idea behind our approach is to combine senders into large groups to reduce the amount of keying information kept in core routers. Our scheme also presents a method for secure routing protocols in general. Using our scheme, several autonomous networks can exercise policies on granting or denying routing privileges to other interconnected networks. Essentially, our protocol uses the concept of 'Non-interactive zero knowledge proofs of membership'
J. Hammell, André Weimerskirch, J. Girão, Dirk Westhoff
This paper formally defines recognition as a new security principle closely related to authentication. Low-power sensor networks with no pre-deployment information require the less authoritative security of recognition. We give general properties of recognition protocols based on the method of key disclosure. We examine previously proposed low-power protocols according to the environment and security model presented. Finally, we give measurements from an implementation of a recognition protocol called zero common-knowledge and discuss how well this proof-of-concept satisfies the properties of the environment.
The restrictions of resources present in the environment of mobile ad hoc networks (MANETs) have forced the adaptation of the existing tools for guaranteeing security basic services in this new framework. The set of restrictions associated to computational, communication and power supply resources is the main barrier when providing them with security mechanisms. The solutions outlined so far for authentication based on classical tools have result non satisfactory for this setting. That is why examining the possibility of using advanced protocols should be explored. Following this trend, a new authentication protocol specifically designed for this setting is proposed in this work. A hard on average problem and an NP-complete one, belonging both to graph theory, are combined in order to design simultaneously an admission control protocol (ACP) and a node authentication protocol (NAP) using identification schemes belonging to the set of zero-knowledge interactive proofs (ZKIP). Using this technique is a way to avoid the nuisances derived from the utilization of PKT.
A distributed conference key distribution system is introduced. The system utilizes secure multi-party computation scheme by virtue of Feldman's (t+1, n) VSS to perform the conference key computation such that a key can be obtained in a distributed fashion in which any key of servers is required to perform the computation. By runing the protocal, every honest user of a given conference can get a common key, even if a minority of servers malfunction or misbehave. This scheme does not rely on any unproven cryptographic assumptions or on the availability of any tamper -proof hardware. By using zero knowledge proof, any corrupted information and incorrect results can be detected. And by distributing the sensitive security information across several servers and never reconstructing and key at a single location, the compromise of a few servers will not compromise the privacy of any key. The scheme is implemented in a distributed environment. By conducting a number of experiments in the fault-free case and various fault scenarios, it is shown that the scheme is practicable and efficient.
Zero knowledge set is a set that has zero knowledge quality.The structure of the set makes that a prover can commit to any arbitrary finite set of strings and for any string,reveal with a proof whether a given element is in the set without revealing any knowledge beyond the verity of these membership assertions.In this paper,we propose a new Group Key Distribution protocol based on zero knowledge set and Peterson commitment so that the identity and number of the group members can be concealed and realize key distribution at the same time.The protocol not only provides a dynamic distribution on a group key,but also guarantees nobody can get additional information about other members except the group key.Compared with previous work,our protocol can provide more security,and is suitable for some special network application,such as secret network meeting.
It is shown in this paper that a kind of new cryptographic primitive proposed by Zheng in 1997, Signcryption, may be applied to construct distributed cryptographic protocols. In fact, the protocols based on Signcryption have the following two properties: Each message exchanged between two participants can be transferred in short data packet, and messages that carry key materials are unforgeable and non-repudiatable without the involvement of a trusted key distribution center. Firstly, based on the modified signcryption scheme of Zheng and Verifiable Secret Sharing(VSS) idea, this paper gives a kind of threshold signcryption scheme without any trusted center for the first time. Furthermore, this scheme can gain its ends of both threshold signature and threshold encryption simultaneously and the costs is much cheaper. In addition, non-repudiation is also offered. Secondly, by analyzing recent distributed key generation protocols, especially Naor’s idea, it put forward a new protocol mainly based on signcryption, called SC-DKDS. Compared with others, SC-DKDS does not need any additional costs, such as authentication channels, private channels or any complicated zero knowledge proofs. The security proofs of the protocols mentioned above are given in RO(Random Oracle) model.
In identification protocols with public verifier coins (like Fiat-Shamir), a passive adversary watching the communication gains information intended only for the verifier. On the other hand, private coin protocols with fewer than three rounds cannot be zero-knowledge. In this paper, we introduce the notion of bounded-prover zero-knowledge proofs which require only two rounds and can be considered perfectly zero-knowledge under certain intractibility assumptions. Specifically, we exploit the gap between two computational problems to achieve zero-knowledge in a dishonest verifier scenario.
We introduce the first El Gamal based mix-net in which each mix-server partially decrypts and permutes its input, i.e., no reencryption is necessary. An interesting property of the construction is that a sender can verify non-interactively that its message is processed correctly. We call this sender verifiability. The mix-net is provably UC-secure against static adversaries corrupting any minority of the mix-servers. The result holds under the decision Diffie-Hellman assumption, and assuming an ideal bulletin board and an ideal zero-knowledge proof of knowledge of a correct shuffle. Then we construct the first proof of a decryption-permutation shuffle, and show how this can be transformed into a zero-knowledge proof of knowledge in the UC-framework. The protocol is sound under the strong RSA-assumption and the discrete logarithm assumption. Our proof of a shuffle is not a variation of existing methods. It is based on a novel idea of independent interest, and we argue that it is at least as efficient as previous constructions.
An original approach to establish a computationally secure and robust conference key between multiple users is presented, which is built on known secret sharing schemes and requires the authenticated and encrypted point-to-point channels between servers and users. By running of the protocol, every honest user of a given conference can get a common key, even if a minority of the servers malfunction or misbehave. This scheme does not rely on any unproven cryptographic assumptions or on the availability of any tamper-proof hardware. By using zero knowledge proof, any corrupted information and incorrect results can be detected. And by distributing the sensitive security information across several servers and never reconstructing any key at a single location, the compromise of a few servers will not compromise the privacy of any key. Analysis shows that under the assumption of a Diffie-Hellman decisional problem, a passive adversary gets zero knowledge about the conference key, and in the random oracle model, an active adversary cannot impersonate successfully. We have implemented the scheme in a distributed environment. By conducting a number of experiments in the fault-free case and various fault scenarios, we show that it has an acceptable performance of practicability.
This paper proposes a computationally secure and fault-tolerant conference key distribution scheme, which only requires the authenticated and encrypted point-to-point channels between each server and each user. By the combined use of knowledge proof and verifiable secret sharing, the scheme has the properties of simple structure and high security. Analysis shows that every honest user of a conference can get a common key after the running of the protocol, even if a minority of the servers malfunction or misbehave. We also show that on the assumption of a Diffie-Hellman decisional problem, a passive adversary gets zero knowledge about the conference key, and the active adversary cannot impersonate someone successfully. Because the knowledge proof method we adopt is non-interactive, both operation and communication overheads are reduced, thus making the schemes very efficient.
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