In this note, we provide a formal proof of the fact that any protocol that is a zero-knowledge proof of knowledge for a relation R is also a secure protocol for the zero-knowledge proof of knowledge functionality, where the latter is defined according to the standard framework of stand-alone secure computation. Although this is a well-known fact, to the best of our knowledge, no full proof of this has been published. 1
Trust is a fundamental concept that enables cooperation and collaboration among the nodes in any network. Formal trust models are necessary for sharing information in a collaborative environment. Trust assessment methods that are commonly used in network applications or in social networks passively gather information about other nodes and take significant amount of time for assessing trust. Such models are not convenient for applications such as tactical airborne networks which are typically deployed for short durations of time.
Message authentication is a critical task in wireless sensor applications not only because it is a basic building block to ensure the authenticity of information but also a prerequisite for bootstrapping cryptographic secrets. Authentication has been explored extensively in the literature, however, the insecure environment within a fabric where multiple users and applications coexist, and limitations in the hardware pose new challenge for this problem. In this paper, we define a new zero knowledge proof problem in which (1) no memory of neighboring certificates is required; and (2) there is no central verification. We then discuss the properties of any potential solution, and propose a practical scheme that allows zero knowledge proof of the identity of each individual node. A notable merit of this scheme is that even if some nodes are compromised, the rest of the system remains secure. We believe this scheme can satisfy the security requirements in many emerging sensor network applications with proper parameter selection.
Rafael Pass, Wei-Lung Dustin Tseng, Douglas Wikström
We show that only languages in BPP have public-coin black-box zero-knowledge protocols that are secure under an unbounded (polynomial) number of parallel repetitions. This result holds both in the plain model (without any setup) and in the bare public key model (where the prover and the verifier have registered public keys). We complement this result by constructing a public-coin black-box zero-knowledge proof based on one-way functions that remains secure under any a priori bounded number of concurrent executions. A key step (of independent interest) in the analysis of our lower bound shows that any public-coin protocol, when repeated sufficiently in parallel, satisfies a notion of “resettable soundness” if the verifier picks its random coins using a pseudorandom function.
How to find efficient and secure member- ship revocation algorithms is one of the most important issues standing in the way of real-world applications of group signatures. In this paper, the proof of knowledge of divisibility is given and a novel membership revocation method in ACJT group signature scheme is proposed: the group manager issues the product E of the public keys of current members in the group, when a group member wants to sign, he should not only proves that he has a membership certificate, but also proves that the public key in his certificate divides exactly the public key product E with zero knowledge. The proposed method is efficient since the group manager only needs one division and one exponentiation when a group member is deleted, while the signing and verifying procedure are independent of the number of current group members and excluded members, as well as the original group public key and membership certificates needn't be changed.
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 shed some light on implementation issues of our proposed scheme.
Zero-knowledge watermark detectors presented to date 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, an efficient zero-knowledge version of the Generalized Gaussian Maximum Likelihood (ML) detector is introduced. 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. Two versions of the zero-knowledge detector are presented; the first one makes use of two new zero-knowledge proofs for modulus and square root calculation; the second is an improved version applicable when the spreading sequence is binary, and it has minimum communication complexity. Completeness, soundness and zero-knowledge properties of the developed protocols are proved, and they are compared with previous zero-knowledge watermark detection protocols in terms of receiver operating characteristic, resistance to sensitivity attacks and communication complexity.
Cryptography and Data Security
Advanced Steganography and Watermarking Techniques
The secure delivery of data between a source node and a sink node is an open problem in wireless sensor networks. We review the security model used for The University of Kansas’s SensorNet project, and discuss how it might be improved by using a secure routing protocol. In this paper we extend work done in developing multipath extensions to AODV. Unlike previous proposals on multipath extensions to AODV, the scheme proposed in this paper allows each node to use multiple disjoint paths concurrently to reach another node. Each of the paths is validated by using zero-knowledge proofs. Under the new scheme data is protected by traditional cryptography as well as using separate paths for key and data delivery. This increases the resiliency of the network as well as the security of the data.
In this paper, we propose a zero-knowledge authenticated key agreement protocol with key confirmation (AKC) in asymmetric setting. The protocol has several desirable security attributes like some classical AKCs such as STS [7] and MQV [13]. One highlight of our protocol is its zero-knowledge property, which enables succinct proofs of the claimed security attributes, while the overhead in communication and computation resulting from the special design to achieve zero-knowledge is insignificant.
Abstract. We show an efficient secure two-party protocol, based on Yao’s construction, which provides security against malicious adversaries. Yao’s original protocol is only secure in the presence of semi-honest adversaries. Security against malicious adversaries can be obtained by applying the compiler of Goldreich, Micali and Wigderson (the “GMW compiler”). However, this approach does not seem to be very practical as it requires using generic zero-knowledge proofs. Our construction is based on applying cut-and-choose techniques to the original circuit and inputs. Security is proved according to the ideal/real simulation paradigm, and the proof is in the standard model (with no random oracle model or common reference string assumptions). The resulting protocol is computationally efficient: the only usage of asymmetric cryptography is for running O(1) oblivious transfers for each input bit (or for each bit of a statistical security parameter, whichever is larger). Our protocol combines techniques from folklore (like cut-and-choose) along with new techniques for efficiently proving consistency of inputs. We remark that a naive implementation of the cut-and-choose technique with Yao’s protocol does not yield a secure protocol. This is the first paper to show how to properly implement these techniques, and to provide a full proof of security. Our protocol can also be interpreted as a constant-round black-box reduction of secure two-party com-putation to oblivious transfer and perfectly-hiding commitments, or a black-box reduction of secure two-party computation to oblivious transfer alone, with a number of rounds which is linear in a sta-tistical security parameter. These two reductions are comparable to Kilian’s reduction, which uses OT alone but incurs a number of rounds which is linear in the depth of the circuit [18]. 1
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.
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