Abstract. Zero-knowledge proofs of knowledge (ZK-PoK) for discrete logarithms and related problems are indispensable for practical cryptographic protocols. At Eurocrypt 2009, Camenisch, Kiayias, and Yung provided a specification language (the CKY-language) for such protocols, which allows one to modularly design and analyze cryptographic protocols: protocol designers just need to specify the statement they want to prove in zero-knowledge and are ensured that an efficient proof protocol exists and indeed proves the specified statement, provided that the specification was in the CKY-language. However, as specifications in the CKY-language are realized by so-called Σ-protocols, the resulting protocols only satisfy the classical notion of zero-knowledge proofs of knowledge, which not retained if they are composed with themselves or with other protocols, e.g., when used as building blocks for higher-level applications. This problem can be tackled by moving to the Universal Composability (UC) framework, which guarantees retention of security when composing protocols and, in particular, when using them as building blocks in arbitrary contexts. While there exists generic transformations from Σ-protocols to protocols that are secure under this stronger security notion, these transformation are often not efficient enough for the design of practical protocols. In this paper we are aiming for practically efficient ZK-PoK in the UC-framework by introducing
An identity-based threshold key management scheme without secure channel is proposed for ad hoc network. The master private key, which is shared among all nodes by the Shamir's secret sharing scheme, is produced by all nodes when network is formed. The nodes' public keys are derived from their identities. In order to get the private key, each node needs to prove their identity to distributed CAs using a zero-knowledge proof protocol to get the share of private key. Compared with former schemes, our scheme doesn't need any local registration authority(LRA), which is easy to be compromised by adversary. When a node leaves the network, shares of the master private key would be renewed. In the end, we prove our scheme is correct and secure.
Pervasive computing is an exciting and blooming research field, in which innovative techniques and applications are continuously emerging and aim to provide ambient and personalized services to users with high quality. Ad hoc networks are wireless, self-organizing systems formed by co-operating nodes within communication range of each other that form temporary networks. Their topology is dynamic, decentralized, ever changing and the nodes may move around arbitrarily. The last few years have witnessed a wealth of research ideas on ad hoc networking that are moving rapidly into implemented standards. Technology under development for ad hoc networks and pervasive computing is making important steps toward this end goal possible. However, the security concerns remain a serious impediment to widespread adoption. The underlying radio communication medium for wireless network provides serious exposure to attacks against wireless networks. Wireless ad hoc networks usually cannot depend on traditional infrastructure found in enterprise environments such as dependable power sources, high bandwidth, continuous connectivity, common network services, well-known membership, static configuration, system administration, and physical security. Finally, throw in malicious adversaries with Byzantine collusion threats and you have a very interesting and challenging problem. Without adequate security, enterprises will not be able to profit from the use of wireless ad hoc networks and pervasive computing environment, defense organizations might be unable to guarantee the safety of their personnel in battlefield scenarios, and wireless ad hoc networks and pervasive computing will remain on the drawing board even if the other problems associated with them are solved. This special issue is focused on various aspects of security in ad hoc networks and pervasive computing research and development to report both in-depth research and applications-oriented works. The special issue is intended to foster state-of-the-art research in the area of security in ad hoc networks and pervasive computing. The aim of this special issue is to present a collection of high quality research papers that report the latest research advances in security of ad hoc. In this special issue, we selected seven papers, which can demonstrate advanced works in this field. A detailed overview of the selected works is given below. The first paper, An RC4-Based Lightweight Protocol for Secure Data Transmission on Resource-Constrained Devices, presents a simple, lightweight, but robust security protocol based on the backward property of RC4 stream cipher. The proposed protocol provides data confidentiality, data authentication, data integrity, and data freshness with low overhead and simple operation, allows packets be received in an arbitrary order, achieves semantic security, and does not require frequent key renew. The second paper, PAPA-UIC: A Design Approach and a Framework for Secure Mobile Ad-hoc Networks, proposes a new design approach and a framework for securing a practical type of MANETs. The framework is named PAPA-UIC. The paper proposes a secure routing protocol and solutions to general problems of identity-based cryptography. The routing protocol has several improvements over existing ones. The third paper, RFIDGuard: A Lightweight Privacy and Authentication Protocol for Passive RFID Tags, introduces a protocol which requires little computation and achieves both privacy and authentication simultaneously. The lightweight and secure nature of the RFIDGuard protocol make it particularly suitable for supply chain management. The fourth paper, Using Hidden Markov Model to Detect Rogue Access Points, proposes a statistical based approach to detect rogue access points using a Hidden Markov Model, which is applied to passively measure packet-header data collected at a gateway router. The main idea is to process the sequence of packet traces in order to distinguish the normal packets from the abnormal ones. The approach is scalable and non-intrusive, requiring little deployment cost and effort, and is easy to manage and maintain. The fifth paper, Defending Sybil Attacks Based on Neighboring Relations in Wireless Sensor Networks, develops a mechanism to protect a WSN from Sybil attacks without using any authentication-based method. Furthermore, the detection approach requires no specialized hardware or support devices. The feature that a malicious node creates many fake identities is exploited to distinguish legitimate nodes from Sybil/malicious nodes. Since all of the fake identities forged by the same malicious node are associated with the same physical device, they will have the same legitimate neighbors. Therefore, by collecting the neighboring information of the suspected victim of the Sybil attacks, the legitimate nodes which are the neighbors of the malicious nodes can be determined. In contrast to existing protection schemes, this approach has no requirement for shared keys, secret information, or special hardware support. The sixth paper, An Autonomous Attestation Token to Secure Mobile Agents in Disaster Response, introduces the Autonomous Attestation Token (AAT), a hardware token for mobile computing devices that is capable of guaranteeing the trusted state of a limited set of devices without relying on a networked service. The paper proposes a Local Attestation protocol with user interaction that in conjunction with the AAT prevents unauthorized access to an emergency mobile agent platform. In addition, the paper sketches a possible solution which integrates trusted computing to leverage ad hoc networks and peer-to-peer systems to provide a robust communication platform. The seventh paper, Building Advanced Applications with the Belgian eID, introduces the Belgian Electronic Identity Card. The card enables Belgian citizens to digitally prove their identity and to sign electronic documents. This paper presents two reusable extensions to the Belgian eID technology that opens up new opportunities for application developers. First, a secure and ubiquitously accessible remote storage service is presented. Second, it is shown how the eID card can be used to issue new certificates. The feasibility and reusability of both extensions are validated through the development of several applications in different domains. In conclusion, this issue of Security in Ad hoc offers a groundbreaking view into the recent advances in secure ad hoc networks. This issue offers both academic and industry appeal the former as a basis toward future research directions, and the latter toward viable commercial applications. Finally, we would like to express our gratitude to the Editor-in-Chief, Professor HsiaoHwa Chen for his advice, patience, and encouragements since the beginning until the final stage. Special thanks go to Michelle in Wiley during the production. We thank all anonymous reviewers who spent much of their precious time reviewing all the papers. Their timely reviews and comments greatly helped us select the best papers in this special issue. We also thank all authors who have submitted their papers for consideration for this issue. We hope you will enjoy reading the great selection of papers in this issue.
A sensor network typically refers to a collection of sensor nodes equipped with sensing, communication and processing capabilities. It brings an opportunity to solve many difficult problems including real time monitoring, tracking, and controlling. While the applications of sensor networking become many and varied, security has always been one of the major concerns in real deployments. In this dissertation, we design physical primitives for secure communication in wireless sensor networks, and develop a wireless security framework to provide conventional security services. We investigate the feasibility of achieving perfect secrecy and information authenticity without shared secrets via two physical primitives: (i) cooperative jamming primitive, where we introduce a secure coding problem in which not only the sender but also the receiver participates in the coding. In essence, the receiver’s role is to selectively jam the sender’s transmission at the level of bits, bytes, or packets. We then design a class of secure codes, called “dialog codes”, for diverse channel models and receiver models. (ii) spatial verification primitive, where we exploit the spatial signature induced by the radio communications of a node on its neighboring nodes, and design a spatial primitive that robustly and efficiently validates the authenticity of the source of messages. To address trust initialization, we propose a zero knowledge proof alternative that allows bootstrapping trust among individuals in a distributed way.
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
Apr 13, 2009·Proceedings of the 5th Annual Workshop on Cyber Security and Information Intelligence Research: Cyber Security and Information Intelligence Challenges and Strategies
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
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.