KEA is a Diffie-Hellman based key-exchange protocol developed by NSA which provides mutual authentication for the parties. It became publicly available in 1998 and since then it was neither attacked nor proved to be secure. We analyze the security of KEA and find that the original protocol is susceptible to a class of attacks. On the positive side, we present a simple modification of the protocol which makes KEA secure. We prove that the modified protocol, called KEA+, satisfies the strongest security requirements for authenticated key-exchange and that it retains some security even if a secret key of a party is leaked. Our security proof is in the random oracle model and uses the Gap Diffie-Hellman assumption. Finally, we show how to add a key confirmation feature to KEA+ (we call the version with key confirmation KEA+C) and discuss the security properties of KEA+C.

Web services are an important series of industry standards for adding semantics to web-based and XML-based communication, in particular among enterprises. Like the entire series, the security standards and proposals are highly modular. Combinations of several standards are put together for testing as interoperability scenarios, and these scenarios are likely to evolve into industry best practices. In the terminology of security research, the interoperability scenarios correspond to security protocols. Hence, it is desirable to analyze them for security. In this paper, we analyze the security of the new Secure WS-ReliableMessaging Scenario, the first scenario to combine security elements with elements of another quality-of-service standard. We do this both symbolically and cryptographically. The results of both analyses are positive. The discussion of actual cryptographic primitives of web services security is a novelty of independent interest in this paper.

We develop a compositional method for proving cryptographically sound security properties of key exchange protocols, based on a symbolic logic that is interpreted over conventional runs of a protocol against a probabilistic polynomial-time attacker. Since key indistinguishability and other previous specifications of secure key exchange suffer from specific compositionality problems, we develop a suitable specification of acceptable key generation. This definition is based on a simple game played by an adversary against a key exchange protocol and a conventional challenger characterizing secure encryption (or other primitives of interest). The method is illustrated using a sample protocol.

In a variety of group-oriented applications cryptographic primitives like group signatures or ring signatures are valuable methods to achieve anonymity of group members. However, in their classical form, these schemes cannot be deployed for applications that simultaneously require (i) to avoid centralized management authority like group manager and (ii) the signer to be anonymous only against non-members while group members have rights to trace and identify the signer. The idea of recently introduced {\it democratic group signatures} is to provide these properties. Based on this idea we introduce a group-oriented signature scheme that allows the group members to trace the identity of any other group member who issued a signature while non-members are only able to link the signatures issued by the same signer without tracing. For this purpose the signature scheme assigns to every group member a unique pseudonym that can be used by any non-member verifier to communicate with the anonymous signer from the group. We present several group-oriented application scenarios where this kind of linkability is essential. We propose a concrete linkable democratic group signature scheme for two-parties, prove its security in the random oracle model, and describe how to modularly extend it to the multi-party case.

We propose an efficient anonymous authentication scheme which might be deployed in the setting of trusted computing platform. Our construction implements features such as total anonymity, variable anonymity, and rogue TPM tagging. The new scheme is significantly simpler, and more efficient than the current solution that has been adopted in the standard specification. We have proved the new scheme is secure under the strong RSA assumption, and the decisional Diffie-Hellman assumption.

Abstract. We show two ways of recovering all matching documents, in the Ostrovsky et al. Private Search [3], while requiring considerably shorter buffers. Both schemes rely on the fact that documents colliding in a buffer position provide the sum of their plaintexts. Efficient decoding algorithms can make use of this property to recover documents never present alone in a buffer position.

We propose constructing provable collision resistant hash functions from expander graphs. As examples, we investigate two specific families of optimal expander graphs for provable hash function constructions: the families of Ramanujan graphs constructed by Lubotzky-Phillips-Sarnak and Pizer respectively. When the hash function is constructed from one of Pizer's Ramanujan graphs, (the set of supersingular elliptic curves over ${\FF}_{p^2}$ with $\ell$-isogenies, $\ell$ a prime different from $p$), then collision resistance follows from hardness of computing isogenies between supersingular elliptic curves. We estimate the cost per bit to compute these hash functions, and we implement our hash function for several members of the LPS graph family and give actual timings.

When communicating over a noisy channel, it is typically much easier to deal with random, independent errors with a known distribution than with adversarial errors. This paper looks at how one can use schemes designed for random errors in an adversarial context, at the cost of relatively few additional random bits and without using unproven computational assumptions. The basic approach is to permute the positions of a bit string using a permutation drawn from a $t$-wise independent family, where $t=o(n)$. This leads to two new results: 1. We construct *computationally efficient* information reconciliation protocols correcting $pn$ adversarial binary Hamming errors with optimal communication and entropy loss $n(h(p)+o(1))$ bits, where $n$ is the length of the strings and $h()$ is the binary entropy function. Information reconciliation protocols are important tools for dealing with noisy secrets in cryptography; they are also used to synchronize remote copies of large files. 2. We improve the randomness complexity (key length) of efficiently decodable capacity-approaching "private codes" from $\Theta(n\log n)$ to $n+o(n)$. We also present a simplified proof of an existential result on private codes due to Langberg (FOCS '04).

In 2005, Wen et al. proposed the first provably secure three-party password-based authenticated key exchange using Weil pairings, and provided their proof in a modified Bellare-Rogaway model (BR-model). Here, we show an impersonation attack on Wen et al.¡¦s scheme and point out a main flaw of their model that allows a man-in-the-middle adversary easily violate the security.

Formal verification is getting more and more important in computer science. However the state of the art formal verification methods in cryptography are very rudimentary. This paper is one step to provide a tool box allowing the use of formal methods in every aspect of cryptography. In this paper we give a formal specification of the RSA probabilistic signature scheme (RSA-PSS) [4] which is used as algorithm for digital signatures in the PKCS #1 v2.1 standard [7]. Additionally we show the correctness of RSA-PSS. This includes the correctness of RSA, the formal treatment of SHA-1 and the correctness of the PSS encoding method. Moreover we present a proof of concept for the feasibility of verification techniques to a standard signature algorithm.

We report on a man-in-the-middle attack on PKINIT, the public key extension of the widely deployed Kerberos 5 authentication protocol. This flaw allows an attacker to impersonate Kerberos administrative principals (KDC) and end-servers to a client, hence breaching the authentication guarantees of Kerberos. It also gives the attacker the keys that the KDC would normally generate to encrypt the service requests of this client, hence defeating confidentiality as well. The discovery of this attack caused the IETF to change the specification of PKINIT and Microsoft to release a security update for some Windows operating systems. We discovered this attack as part of an ongoing formal analysis of the Kerberos protocol suite, and we have formally verified several fixes to PKINIT that prevent our attack.

Over the last 30 years the study of group key agreement has stimulated much work. And as a result of the increased popularity of ad hoc networks, some approaches for the group key establishment in such networks are proposed. However, they are either only for static group or the memory, computation and communication costs are unacceptable for ad-hoc networks. In this thesis some protocol suites from the literature (2^d-cube, 2^d-octopus, Asokan-Ginzboorg, CLIQUES, STR and TGDH) shall be discussed. We have optimized STR and TGDH by reducing the memory, communication and computation costs. The optimized version are denoted by µSTR and µTGDH respectively. Based on the protocol suites µSTR and µTGDH we present a Tree-based group key agreement Framework for Ad-hoc Networks (TFAN). TFAN is especially suitable for ad-hoc networks with limited bandwidth and devices with limited memory and computation capability. To simulate the protocols, we have implemented TFAN, µSTR and µTGDH with J2ME CDC. The TFAN API will be described in this thesis.

In 1999, Yang and shieh proposed two password authentication schemes using smart cards. But in 2003, Sun and Yeh indicated that their schemes are subject to the forgery attack. So in 2005, Yang and Wang proposed an improvement of Yang and Shieh¡¦s schemes to resist against Sun and Yeh¡¦s attack. However in this paper, we will point out that Yang and Wang¡¦s schemes still suffer from the forgery attack. Because in their schemes, one can masquerade as a legal user and cheat the remote server successfully in the authentication phase.

A prompting protocol permits users to securely retrieve secrets with greater entropy than passwords. The retrieved user secrets can have enough entropy to be used to derive cryptographic keys.

In 2003, Boyd and Mao proposed two deniable authenticated key establishment protocols using elliptic curve pairings for Internet protocols, one is based on Diffie-Hellman key exchange and the other is based on Public-Key Encryption approach. For the use of elliptic curve pairings, they declared that their schemes could be more efficient than the existing Internet Key Exchange (IKE), nowadays. However in this paper, we will show that both of Boyd-Mao¡¦s protocols suffer from the key-Compromise Impersonation attack.

In 2005, Manik et al. propose a novel remote user authentication scheme using bilinear pairings which allows a valid user to login to the remote system but prohibits too many users to login with the same login-ID. It also provides a flexible password change function. In this paper, we will show that this remote user authentication scheme is not secure, an adversary can always pass the authentication.

The Trusted Computing Platform is the industrial initiative to implement computer security. However, privacy protection is a critical problem that must be solved in Trusted Computing Platform. In this paper, we propose a simple and efficient method to implement anonymous authentication in such setting. The new scheme is proved to be secure under the strong RSA assumption and decisional Diffie-Hellman assumption.

We show that an adversary can over-spend a coin n(n+1)! times without being detected and identified in the n-spendable extension of Ferguson's single-term off-line coin, simply by permuting the witness messages in the three-move zero-knowledge proof payment protocol. We repair the detection scheme by adding a simple verification rule in the payment protocol. We repair the identification scheme by restricting the identity format.

Logcrypt provides strong cryptographic assurances that data stored by a logging facility before a system compromise cannot be modified after the compromise without detection. We build on prior work by showing how log creation can be separated from log verification, and describing several additional performance and convenience features not previously considered.

In 1982, Chaum \cite{Chaum82} pioneered the anonymous e-cash which finds many applications in e-commerce. In 1993, Brands \cite{Brands93apr,Brands93,Brands93tm} and Ferguson \cite Ferguson93c,Ferguson93} published on single-term offline anonymous e-cash which were the first practical e-cash. Their constructions used blind signatures and were inefficient to implement multi-spendable e-cash. In 1995, Camenisch, Hohenberger, and Lysyanskaya \cite{CaHoLy05} gave the first compact $2^\ell$-spendable e-cash, using zero-knowledge-proof techniques. They left an open problem of the simultaneous attainment of $O(1)$-unit wallet size and efficient coin tracing. The latter property is needed to revoke {\em bad} coins from over-spenders. In this paper, we solve \cite{CaHoLy05}'s open problem, and thus enable the first practical compact e-cash. We use a new technique whose security reduces to a new intractability Assumption: the {\em Decisional Harmonic-Relationed Diffie-Hellman (DHRDH) Assumption}.

In the newest and strongest security models for group signatures \cite{BMW03,BellareShZh05,KiayiasYu04}, attackers are given the capability to query an Open Oracle, $\oo$, in order to obtain the signer identity of the queried signature. This oracle mirrors the Decryption Oracle in security experiments involving encryption schemes, and the security notion of CCA2-full-anonymity for group signatures mirrors the security notion of IND-CCA2-security for encryption schemes. Most group signatures escrows the signer identity to a TTP called the {\em Open Authority (OA)} by encrypting the signer identity to OA. Methods to efficiently instantiate $O(1)$-sized CCA2-fully-anonymous group signatures using IND-CCA2-secure encryptions, such as the Cramer-Shoup scheme or the twin encryption scheme, exist \cite{BMW03,BellareShZh05,KiayiasYu04,NguyenSN04}. However, it has long been suspected that IND-CCA2-secure encryption to OA is an overkill, and that CCA2-fully-anonymous group signature can be constructed using only IND-CPA-secure encryptions. Here, we settle this issue in the positive by constructing CCA2-fully-anonymous group signatures from IND-CPA-secure encryptions for the OA, without ever using IND-CCA2-secure encryptions. Our technique uses a single ElGamal or similar encryption plus Dodis and Yampolskiy \cite{DodisYa05}'s VRF (Verifiable Random Function). The VRF provides a sound signature with zero-knowledge in both the signer secret and the signer identity, while it simultaneously defends active $\oo$-query attacks. The benefits of our theoretical advance is improved efficiency. Instantiations in pairings result in the shortest CCA2-fully-anonymous group signature at 11 rational points or $\approx 1870$ bits for 170-bit curves. It is 27\% shorter (and slightly faster) than the previous fastest \cite{BBS04,KiayiasYu04} at 15 rational points. Instantiations in the strong RSA framework result in the fastest CCA2-fully-anonymous group signature at 4 multi-base exponentiations for 1024-bit RSA. It is 25\% faster than the previous fastest at 5 multi-base exponentiations \cite{ACJT00,CL02,KiayiasYu04}.

This paper addresses the problem of making signatures of one domain (an ad-hoc network) available in another domain (the Internet). Universal verifiability is a highly desirable property when signed documents need to be permanently non-repudiable so as to prevent dishonest signers from disavowing signatures they have produced. As a practical solution, we construct a new signature scheme where a valid signature should be generated by a couple of distinct signing keys. In the random oracle model, the signature scheme is provably secure in the sense of existential unforgeability under adaptive chosen message attacks assuming the hardness of the computational Diffie-Hellman problem in the Gap Diffie-Hellman groups.

In this paper, we present a broadcast encryption scheme with efficient transmission cost under the \emph{log-key} restriction. Given $n$ users and $r$ revoked users, our scheme has the transmission cost of $O(r)$ and requires the storage of $O(\log n)$ keys at each receiver. These are optimal complexities in broadcast encryptions using one-way hash functions (or pseudo-random generators.) To achieve these complexities, the stratified subset difference (SSD) scheme and the $\overline{B1}$ scheme were introduced by Goodrich et al. and Hwang et al. respectively. However, their schemes have the disadvantage that transmission cost increases linearly according to the number of stratifications. By assigning the related keys between stratifications, our scheme remedies the defect and achieves very efficient transmission cost even in an environment where the key storage is restricted. To the best of our knowledge, our scheme has the most efficient transmission cost in the existing schemes with log-key storage. In addition, our result is comparable to other schemes that allow a large key storage.

At ACISP 2003 conference, Narayanan, Rangan and Kim proposed a secret-key traitor tracing scheme used for pay TV system. In this note, we point out a flaw in their scheme.

We introduce the notion of {\em resource-fair} protocols. Informally, this property states that if one party learns the output of the protocol, then so can all other parties, as long as they expend roughly the same amount of resources. As opposed to similar previously proposed definitions, our definition follows the standard simulation paradigm and enjoys strong composability properties. In particular, our definition is similar to the security definition in the universal composability (UC) framework, but works in a model that allows any party to request additional resources from the environment to deal with dishonest parties that may prematurely abort. In this model we specify the ideally fair functionality as allowing parties to ``invest resources'' in return for outputs, but in such an event offering all other parties a fair deal. (The formulation of fair dealings is kept independent of any particular functionality, by defining it using a ``wrapper.'') Thus, by relaxing the notion of fairness, we avoid a well-known impossibility result for fair multi-party computation with corrupted majority; in particular, our definition admits constructions that tolerate arbitrary number of corruptions. We also show that, as in the UC framework, protocols in our framework may be arbitrarily and concurrently composed. Turning to constructions, we define a ``commit-prove-fair-open'' functionality and design an efficient resource-fair protocol that securely realizes it, using a new variant of a cryptographic primitive known as ``time-lines.'' With (the fairly wrapped version of) this functionality we show that some of the existing secure multi-party computation protocols can be easily transformed into resource-fair protocols while preserving their security.

Several identity based and authenticated key agreement protocols have been proposed in recent years and all of them have been shown to be non-secure. It remains an open question to design secure identity based and authenticated key agreement protocols. In this paper, we propose an efficient identity-based and authenticated key agreement protocol IDAK using Weil/Tate pairing. A security model for identity based key agreement protocol is established and the security properties of IDAK are proved in this model with random oracle. In particular, it is shown that the IDAK protocol possesses all characteristics that a secure key agreement should have.

We propose a scheme for electronic cash based on symmetric primitives. The scheme is secure in the framework for universal composability assuming the existence of a symmetric CCA2-secure encryption scheme, a CMA-secure signature scheme, and a family of one-way, collision-free hash functions. In particular, the security proof is not in the random-oracle model. Due to its high efficiency, the scheme is well-suited for devices such as smart-cards and mobile phones. We also show how the proposed scheme can be used as a group signature scheme with one-time keys.

In this paper we propose two compilers which are designed to transform a group key exchange protocol secure against any passive adversary into an authenticated group key exchange protocol with key confirmation which is secure against any passive adversary, active adversary, or malicious insider. We show that the first proposed compiler gives protocols that are more efficient than those produced by the compiler of Katz and Yung. The second proposed compiler further reduces the computational complexity of the output protocols by using a Trusted Third Party (TTP). We moreover show that, although the protocols produced by the novel compilers have lower computational complexity than the protocols produced by the Katz-Yung compiler, the protocols nevertheless achieve key confirmation, unlike the protocols output by the Katz-Yung compiler.

Recently, a number of ID-based two-party authenticated key agreement protocols which make of bilinear pairings have been proposed \cite {CJL,MB,Sh,S,X}. In this paper, we show that the Xie's protocol \cite {X} does not provide implicit key authentication and key-compromise impersonation resilience. Also, we point out the vulnerability of the Choi {\it et al}'s protocol \cite {CJL} against signature forgery attacks.

To achieve secure data communications, two parties should be authenticated by each other and agree on a secret session key by exchanging messages over an insecure channel. In this paper, based on the bilinear pairing, we present a new two-party authenticated key agreement protocol, and use the techniques from provable security to examine the security of our protocol within Bellare-Rogaway model.

We examine various indistinguishability-based proof models for key establishment protocols, namely the Bellare & Rogaway (1993, 1995), the Bellare, Pointcheval, & Rogaway (2000), and the Canetti & Krawczyk (2001) proof models. We then consider several variants of these proof models, identify several subtle differences between these variants and models, and compare the relative strengths of the notions of security between the models. For each of the pair of relations between the models (either an implication or a non-implication), we provide proofs or counter-examples to support the observed relations. We also reveal a drawback with the original formulation of the Bellare, Pointcheval, & Rogaway (2000) model, whereby the Corrupt query is not allowed. As a case study, we use the Abdalla & Pointcheval (2005) three-party password-based key exchange protocol (3PAKE), which carries a proof of security in the Bellare, Pointcheval, & Rogaway (2000) model. We reveal a previously unpublished flaw in the protocol, and demonstrate that this attack would not be captured in the model due to the omission of the Corrupt query.

The emphasis of this paper is to focus on key agreement. To this aim, we address a self-contained, up-to-date presentation of key agreement protocols at high level. We have attempted to provide a brief but fairly complete survey of all these schemes.

In most of the existing identity-based key agreement schemes, it is usually assumed that either the communicated parties know each other's identifier before the protocol starts or their identifiers are transferred along with the protocol messages. However, these schemes are not suitable for use in many real-world applications aimed to achieve unilateral identity privacy, which means that one communicating party does not want to expose his identifier to an outsider while his partner cannot know his identifier in advance. In this paper, we propose an efficient identity-based two-party key agreement scheme with unilateral identity privacy using pairing, and formally analyze its security in a modified Bellare-Rogaway key agreement security model.

A group signature is a basic privacy mechanism. The group joining operation is a critical component of such a scheme. To date all secure group signature schemes either employed a trusted-party aided join operation or a complex joining protocol requiring many interactions between the prospective user and the Group Manager (GM). In addition no efficient scheme employed a join protocol proven secure against adversaries that have the capability to dynamically initiate multiple concurrent join sessions during an attack. This work presents the first efficient group signature scheme with a simple Joining protocol that is based on a ``single message and signature response'' interaction between the prospective user and the GM. This single-message and signature-response registration paradigm where no other actions are taken, is the most efficient possible join interaction and was originally alluded to in 1997 by Camenisch and Stadler, but its efficient instantiation remained open till now. The fact that joining has two short communication flows and does not require secure channels is highly advantageous: for example, it allows users to easily join by a proxy (i.e., a security officer of a company can send a file with all registration requests in his company and get back their certificates for distribution back to members of the company). It further allows an easy and non-interactive global system re-keying operation as well as straightforward treatment of multi-group signatures. We present a strong security model for group signatures (the first explicitly taking into account concurrent join attacks) and an efficient scheme with a single-message and signature-response join protocol. The present manuscript is a full version containing proofs, minor corrections as well as a more flexible and efficient protocol construction compared to the proceedings version.

With respect to a special class of access structures based on connectivity of graphs, we start from a linear secret sharing scheme and turn it into a secret sharing scheme with perfect security and exponentially small error probability by randomizing the reconstruction algorithm through random walks on graphs. It reduces the polynomial work space to logarithmic. Then we build the corresponding statistical multiparty computation protocol by using the secret sharing scheme. The results of this paper also imply the inherent connections and influences among secret sharing, randomized algorithms, and secure multi-party computation.

We propose four different public-key identification schemes that make use of bilinear pairings, and prove their security under certain computational assumptions. Each of the schemes is more efficient and/or more secure than any known pairing-based identification scheme.

In 1999, Juels and Wattenberg introduce an effective construction of Fuzzy Sketch, i.e. a way of handling errors into string verification. This allows them to consider data varying into time, such as, for instance, answers to a list of subjective questions. To this end, they utilize an Error Correcting Code. We here show how to embed a trapdoor into Fuzzy Sketches, reducing to authorized people the ability to correct errors and thus to verify the fuzzy equality to the Fuzzy Sketch.

We present a cryptographically sound formal method for proving correctness of key exchange protocols. Our main tool is a fragment of a symbolic protocol logic. We demonstrate that proofs of key agreement and key secrecy in this logic imply simulatability in Shoup's secure multi-party framework for key exchange. As part of the logic, we present cryptographically sound abstractions of CMA-secure digital signatures and a restricted form of Diffie-Hellman exponentiation, which is a technical result of independent interest. We illustrate our method by constructing a proof of security for a simple authenticated Diffie-Hellman protocol.

The ability to link two different sightings of the same Radio Frequency Identification (RFID) tag enables invasions of privacy. The problem is aggravated when an item, and the tag attached to it, changes hands during the course of its lifetime. After such an ownership transfer, the new owner should be able to read the tag but the old owner should not. We address these issues through an RFID pseudonym protocol. Each time it is queried, the RFID tag emits a different pseudonym using a pseudo-random function. Without consent of a special Trusted Center that shares secrets with the tag, it is infeasible to map the pseudonym to the tag's real identity. We present a scheme for RFID pseudonyms that works with legacy, untrusted readers, requires only one message from tag to reader, and is scalable: decoding tag pseudonyms takes work logarithmic in the number of tags. Our scheme further allows for time-limited delegation, so that we can give an RFID reader the power to disambiguate a limited number of pseudonyms without further help from the Trusted Center. We show how RFID pseudonyms facilitate the transfer of ownership of RFID tags between mutually distrustful parties. Our scheme requires only limited cryptographic functionality from the tag: we need a pseudo-random function (PRF) and the ability to update tag state or to generate random numbers. Tag storage and communication requirements are modest: we give example parameters for a deployment of one million tags in which each tag stores only $128$ bits, makes $6$ PRF evaluations, and sends $158$ bits each time it is read.

In this paper, we propose a new concept ``Meta Ring Signature''. Suppose that a signature text work as a public key, we may achive a new digital signature ``Meta Signature'' such that, the signer of a signature text, in this paper we call basic signature, can sign on to another message by using the basic signature text as the public key of Meta signature scheme. First, we present a concept of Meta Ring Signature such that both basic signature and meta signature are Ring Signature.

Recently Eun-Kyung Ryu, Eun-Jun Yoon, and Kee-Young Yoo proposed an efficient ID-based authenticated key agreement with paring.They argued that it is secure and efficient. In this paper, we show this protocol is doesn't satisfy the Key-Compromise Impersonate property and it is not secure against key reveal attack. Then we propose our protocol from this protocol and shim's protocol, its security and efficiency was analyzed.

We first present a new security 2-AK protocol, which is more secure and more efficient than previously proposed ones. Meanwhile, we point that Xie's ID-2-AK protocol modified from McCullagh-Barreto in CT-RSA 2005 doesn't provide protection against KCI attack likewise, and finally utilize the modular arithmetic, first proposed in MQV and also used in Kim, to get a modified new ID-2-AK protocol. On second thoughts, we give another ID-2-AK protocol utilizing the operation of addition in finite field like our forenamed 2-AK protocol. The two ID-2-AK protocols are in possession of all the desired security attributes. We also compare our new protocols with others in terms of computational cost and security properties.

A mobile agent is a mobile program capable of maintaining its execution states as it migrates between different execution platforms. A key security problem in the mobile agent paradigm is that of trust: How to ensure that the past itinerary (of execution platforms) claimed by the agent is correct. This is necessary in order to establish a reasonable level of trust for the agent before granting execution privileges. In this paper we describe a protocol using bilinear pairings that enables trust relationships to be formed between agent platforms in an ad-hoc manner without actively involving any trusted third party. This protocol can be used to authenticate agents before granting execution privileges. The main idea behind our approach is the concept of `one-way' chaining. Our scheme has chosen ciphertext security assuming the hardness of the Bilinear Diffie Hellman Problem (BDHP).

We consider the problem of overcoming (Distributed) Denial of Service (DoS) attacks by realistic adversaries that have knowledge of their attack's successfulness, e.g., by observing service performance degradation, or by eavesdropping on messages or parts thereof. A solution for this problem in a high-speed network environment necessitates lightweight mechanisms for differentiating between valid traffic and the attacker's packets. The main challenge in presenting such a solution is to exploit existing packet filtering mechanisms in a way that allows fast processing of packets, but is complex enough so that the attacker cannot efficiently craft packets that pass the filters. We show a protocol that mitigates DoS attacks by adversaries that can eavesdrop and (with some delay) adapt their attacks accordingly. The protocol uses only available, efficient packet filtering mechanisms based mainly on (addresses and) port numbers. Our protocol avoids the use of fixed ports, and instead performs `pseudo-random port hopping'. We model the underlying packet-filtering services and define measures for the capabilities of the adversary and for the success rate of the protocol. Using these, we provide a novel rigorous analysis of the impact of DoS on an end-to-end protocol, and show that our protocol provides effective DoS prevention for realistic attack and deployment scenarios.

We initiate the study of two-party cryptographic primitives with unconditional security, assuming that the adversary's {\em quantum}memory is of bounded size. We show that oblivious transfer and bit commitment can be implemented in this model using protocols where honest parties need no quantum memory, whereas an adversarial player needs quantum memory of size at least $n/2$ in order to break the protocol, where $n$ is the number of qubits transmitted. This is in sharp contrast to the classical bounded-memory model, where we can only tolerate adversaries with memory of size quadratic in honest players' memory size. Our protocols are efficient, non-interactive and can be implemented using today's technology. On the technical side, a new entropic uncertainty relation involving min-entropy is established.

Secure, anonymous and unobservable communication is becoming increasingly important due to the gradual erosion of privacy in many aspects of everyday life. This prompts the need for various anonymity- and privacy-enhancing techniques, e.g., group signatures, anonymous e-cash and secret handshakes. In this paper, we investigate an interesting and practical cryptographic construct Oblivious Signature-Based Envelopes (OS-BEs) recently introduced in [15]. OSBEs are very useful in anonymous communication since they allow a sender to communicate information to a receiver such that the receiver s rights (or roles) are unknown to the sender. At the same time, a receiver can obtain the information only if it is authorized to access it. This makes OSBEs a natural fit for anonymity-oriented and privacy-preserving applications, such as Automated Trust Negotiation and Oblivious Subscriptions. Previous results yielded three OSBE constructs: one based on RSA and two based on Identity-Based Encryption (IBE). Our work focuses on the ElGamal signature family: we succeed in constructing practical and secure OSBE schemes for several well-known signature schemes, including: Schnorr, Nyberg-Rueppel, ElGamal and DSA. As experiments with the prototype implementation il-lustrate, our schemes are more efficient than previous techniques. Furthermore, we show that some OSBE schemes, despite offering affiliation privacy for the receiver, introduce no additional cost over schemes that do not offer this feature.

Certificateless public key cryptography was introduced to overcome the key escrow limitation of the identity-based cryptography. It combines the advantages of the identity-based cryptography and the traditional PKI. Recently, Dae Hyun Yum1 and Pil Joong Lee have proposed a generic series construction model of certificateless public key encryption (CL-PKE) which is built from generic primitives: identity-based encryption and public key encryption. However, this model pays much attention on the generic construction and neglects the nice properties of the bilinear pairings. In this paper, we propose an efficient CL-PKE scheme which is based on the nice algebraic properties of Weil pairing. The scheme works in a kind of parallel model and it is more efficient on computation or published public key information than the existing schemes.

Imagine there is certain content we want to maintain private until some particular event occurs, when we want to have it automatically disclosed. Suppose furthermore, that we want this done in a (possibly) malicious host. Say, the confidential content is a piece of code belonging to a computer program that should remain ciphered and then ``be triggered'' (i.e., deciphered and executed) when the underlying system satisfies a preselected condition which must remain secret after code inspection. In this work we present different solutions for problems of this sort, using different ``declassification'' criteria, based on a primitive we call {\em secure triggers}. We establish the notion of secure triggers in the universally-composable security framework of [Canetti~2001] and introduce several examples. Our examples demonstrate that a new sort of obfuscation is possible. Finally, we motivate its use with applications in realistic scenarios.

We first present a protocol which reduces 1-out-of-$n$ oblivious transfer OT$_l^m$ to 1-out-of-$n$ oblivious transfer OT$_m^k$ for $n>2$ in random oracle model, and show that the protocol is secure against malicious sender and semi-honest receiver. Then, by employing a cut-and-choose technique, we obtain a variant of the basic protocol which is secure against a malicious receiver.

Recently, Wen, Lee, and Hwang proposed a three-party password-authenticated key exchange protocol making use of the Weil pairing. The protocol was claimed to be provably secure. But despite the claim of provable security, the protocol is in fact insecure in the presence of an active adversary. We demonstrate this by presenting an attack that completely compromises the authentication mechanism of the protocol. Consequently, the proof of security for the protocol is invalidated.

This paper focuses on human-computer identification systems against peeping attacks, in which adversaries can observe (and even control) interactions between humans (provers) and computers (verifiers). Real cases on peeping attacks were reported by Ross J. Anderson ten years before. Fixed passwords are insecure to peeping attacks since adversaries can simply replay the observed passwords. Some identification techniques can be used to defeat peeping attacks, but auxiliary devices must be used and such devices are also insecure against peeping attacks if they are lost or stolen. Although more and more people get to know risks from peeping attacks, a practical solution has not been found. This paper first gives a comprehensive review on peeping attacks and related issues, and then points out some basic design principles. Two general structures of secure human-computer identification systems are proposed against peeping attacks. A concrete SecHCI protocol and its various implementations are given, and a real Web service is developed for demonstration. The security and usability of the proposed protocol are investigated in detail. Although the usability of the proposed protocol is not yet sufficiently good, we believe that some design skills of the proposed protocol are useful for future work on SecHCI.

We present a constant-round protocol for general secure multiparty computation which makes a {\em black-box} use of a pseudorandom generator. In particular, the protocol does not require expensive zero-knowledge proofs and its communication complexity does not depend on the computational complexity of the underlying cryptographic primitive. Our protocol withstands an active, adaptive adversary corrupting a minority of the parties. Previous constant-round protocols of this type were only known in the semi-honest model or for restricted classes of functionlities.

Pairing computation requires a lot of efforts for portable small devices such as smart cards. It was first considered concretely by Chevallier-Mames et al. that the cards delegate computation of pairings to a powerful device. In this paper, we propose more efficient protocols than those of Chevallier-Mames et al. in two cases, and provide two new variants that would be useful in real applications.

We identify and fill some gaps with regard to consistency (the extent to which false positives are produced) for public-key encryption with keyword search (PEKS). We define computational and statistical relaxations of the existing notion of perfect consistency, show that the scheme of Boneh et al. in Eurocrypt 2004 is computationally consistent, and provide a new scheme that is statistically consistent. We also provide a transform of an anonymous IBE scheme to a secure PEKS scheme that, unlike the previous one, guarantees consistency. Finally, we suggest three extensions of the basic notions considered here, namely anonymous HIBE, public-key encryption with temporary keyword search, and identity-based encryption with keyword search.

Verifiable secret sharing schemes proposed so far can only allow participants to verify whether their shares are correct or not. In this paper, we propose a new protocol which can allow participants not only to verify the correctness of their shares but also to revise the faulty shares. It is achieved in a cooperative way by participants, but without any assistance from the dealer. This protocol, to the best of our knowledge, is the first one providing such kind of ability. Correcting shares by participants instead of the dealer is important in many situations. In addition, this protocol is also useful for adding new participants without the dealer's assistance.

In this paper, we propose a secret sharing scheme which prevents the cheaters from recovering the secret when the honest participants cannot, with high probability. The scheme is a (k, n) threshold scheme providing protection against less than k cheaters. It is efficient in terms of share sizes for the participants. Furthermore the total size of the individual shares per participant is less than twice the size of the secret itself. The cheaters can do successful cheating with a probability 1/t, which can be adjusted without significantly increasing the total size of the individual shares. Such a scheme can be deployed in thin client fat server systems where the server has reasonable computational power and there is a high level of mistrust among the users.

The MQV protocol of Law, Menezes, Qu, Solinas and Vanstone is possibly the most efficient of all known authenticated Diffie-Hellman protocols that use public-key authentication. In addition to great performance, the protocol has been designed to achieve a remarkable list of security properties. As a result MQV has been widely standardized, and has recently been chosen by the NSA as the key exchange mechanism underlying ``the next generation cryptography to protect US government information." One question that has not been settled so far is whether the protocol can be proven secure in a rigorous model of key-exchange security. In order to provide an answer to this question we analyze the MQV protocol in the Canetti-Krawczyk model of key exchange. Unfortunately, we show that MQV fails to a variety of attacks in this model that invalidate its basic security as well as many of its stated security goals. On the basis of these findings, we present HMQV, a carefully designed variant of MQV, that provides the same superb performance and functionality of the original protocol but for which all the MQV's security goals can be formally proved to hold in the random oracle model under the computational Diffie-Hellman assumption. We base the design and proof of HMQV on a new form of ``challenge-response signatures", derived from the Schnorr identification scheme, that have the property that both the challenger and signer can compute the {\em same} signature; the former by having chosen the challenge and the latter by knowing the private signature key. REVISION: In http://eprint.iacr.org/2005/205, Menezes [32] describes some shortcomings in our analysis that lead to the need for a prime-order verification of public DH values in the protocol. Some of Menezes's claims are correct and some other are not. We keep the originally posted paper here but add a {\em Preface} section (preceding the introduction) that briefly explains these findings and their implications to our results. In essence, the provability of HMQV and its security superiority relative to MQV remain valid; even computation-wise, after adding the verification steps where needed, HMQV is as efficient as (and in some cases even more efficient than) MQV

We propose a one-round $1$-out-of-$n$ computationally-private information retrieval protocol for $\ell$-bit strings with low-degree polylogarithmic receiver-computation, linear sender-computation and communication $\Theta(k\cdot\log^2{n}+\ell\cdot\log{n})$, where $k$ is a possibly non-constant security parameter. The new protocol is receiver-private if the underlying length-flexible additively homomorphic public-key cryptosystem is IND-CPA secure. It can be transformed to a one-round computationally receiver-private and information-theoretically sender-private $1$-out-of-$n$ oblivious-transfer protocol for $\ell$-bit strings, that has the same asymptotic communication and is private in the standard complexity-theoretic model.

Time-stamping protocols, which assure that a document was existed at a certain time, are applied to some useful and practical applications such as electronic patent applications and so on. There are two major time-stamping protocols, the simple protocol and the linking protocol. In the former, a time-stamp authority issues a time-stamp token that is the digital signature of the concatenated value of a hashed message and the present time. In the latter, the time-stamp authority issues a time-stamp token that is the hash value of the concatenated value of a hashed message and the previous hash value. Although security requirements and analysis for above time-stamping protocols has been discussed, there are no strict cryptographic security notions for them. In this paper, we reconsider the security requirements for time-stamping protocols and define security notions for them, in a universally composable security sense, which was proposed by Canetti. We also show that these notions can be achieved using combinations of a secure key exchange protocol, a secure symmetric encryption scheme, and a secure digital signature scheme.

In [3], Tang presented two password guessing attacks such as off-line and undetectable on-line dictionary attacks against password-based group Diffie-Hellman key exchange protocols by Byun and Lee [2]. In this paper, we present countermeasures for two attacks by Tang.

We present a universally composable time-stamping scheme based on universal one-way hash functions. The model we use contains an ideal auditing functionality (implementable in the Common Reference String model), the task of which is to check that the rounds' digests are correctly computed. Our scheme uses hash-trees and is just a slight modification of the known schemes of Haber-Stornetta and Benaloh-de Mare, but both the modifications and the audit functionality are crucial for provable security. The scheme turns out to be nearly optimal -- we prove that in every universally composable auditable time-stamping scheme, almost all time stamp requests must be communicated to the auditor.

We propose and realize a definition of security for password-based key exchange within the framework of universal composability (UC), thus providing security guarantees under arbitrary composition with other protocols. In addition, our definition captures some aspects of the problem that were not adequately addressed by most prior notions. For instance, our definition does not assume any underlying probability distribution on passwords, nor does it assume independence between passwords chosen by different parties. We also formulate a definition of password-based secure channels, and show how to realize such channels given any password-based key exchange protocol. The password-based key exchange protocol shown here is in the common reference string model and relies on standard number-theoretic assumptions. The components of our protocol can be instantiated to give a relatively efficient solution which is conceivably usable in practice. We also show that it is impossible to satisfy our definition in the "plain" model (e.g., without a common reference string).

We show that if a set of players hold shares of a value $a\in Z_p$ for some prime $p$ (where the set of shares is written $[a]_p$), it is possible to compute, in constant round and with unconditional security, sharings of the bits of $a$, i.e.~compute sharings $[a_0]_p, \ldots, [a_{l-1}]_p$ such that $l = \lceil \log_2(p) \rceil$, $a_0, \ldots, a_{l-1} \in \{0,1\}$ and $a = \sum_{i=0}^{l-1} a_i 2^i$. Our protocol is secure against active adversaries and works for any linear secret sharing scheme with a multiplication protocol. This result immediately implies solutions to other long-standing open problems, such as constant-round and unconditionally secure protocols for comparing shared numbers and deciding whether a shared number is zero. The complexity of our protocol is $O(l \log(l))$ invocations of the multiplication protocol for the underlying secret sharing scheme, carried out in $O(1)$.

In this paper we try to shed a new insight on Verifiable Secret Sharing Schemes (VSS). We first define a new ``metric" (with slightly different properties than the standard Hamming metric). Using this metric we define a very particular class of codes that we call {\it error-set correcting codes}, based on a set of forbidden distances which is a monotone decreasing set. Next we redefine the packing problem for the new settings and generalize the notion of error-correcting capability of the error-set correcting codes accordingly (taking into account the new metric and the new packing). Then we consider burst-error interleaving codes proposing an efficient burst-error correcting technique, which is in fact the well known VSS and Distributed Commitments (DC) pair-wise checking protocol and we prove the error-correcting capability of the error-set correcting interleaving codes. Using the known relationship, due to Van Dijk, between a Monotone Span Program (MSP) and a generator matrix of the code generated by the suitable set of vectors, we prove that the error-set correcting codes in fact has the allowed (opposite to forbidden) distances of the dual access structure of the access structure that the MSP computes. We give an efficient construction for them based on this relation and as a consequence we establish a link between Secret Sharing Schemes (SSS) and the error-set correcting codes. Further we give a necessary and sufficient condition for the existence of linear SSS (LSSS), to be secure against $(\Delta,\Delta_A)$-adversary expressed in terms of an error-set correcting code. Finally, we present necessary and sufficient conditions for the existence of a VSS scheme, based on an error-set correcting code, secure against $(\Delta,\Delta_A)$-adversary. Our approach is general and covers all known linear VSS/DC. It allows us to establish the minimal conditions for security of VSSs. Our main theorem states that the security of a scheme is equivalent to a pure geometrical (coding) condition on the linear mappings describing the scheme. Hence the security of all known schemes, e.g. all known bounds for existence of unconditionally secure VSS/DC including the recent result of Fehr and Maurer, can be expressed as certain (geometrical) coding conditions.

The main result of this paper is that the Dolev-Yao model is a safe abstraction of the computational model for security protocols including those that combine asymmetric and symmetric encryption, signature and hashing. Moreover, message forwarding and private key transmission are allowed. To our knowledge this is the first result that deals with hash functions and the combination of these cryptographic primitives. A key step towards this result is a general definition of correction of cryptographic primitives, that unifies well known correctness criteria such as IND-CPA, IND-CCA, unforgeability etc.... and a theorem that allows to reduce the correctness of a composition of two cryptographic schemes to the correctness of each one.

We consider secure multi-party computation in the asynchronous model and present an efficient protocol with optimal resilience. For $n$ parties, up to $t<n/3$ of them being corrupted, and security parameter $\kappa$, a circuit with $c$ gates can be securely computed with communication complexity $O(c n^3 \kappa)$ bits. In contrast to all previous asynchronous protocols with optimal resilience, our protocol requires access to an expensive broadcast primitive only $O(n)$ times --- independently of the size $c$ of the circuit. This results in a practical protocol with a very low communication overhead. One major drawback of a purely asynchronous network is that the inputs of up to $t$ honest parties cannot be considered for the evaluation of the circuit. Waiting for all inputs could take infinitely long when the missing inputs belong to corrupted parties. Our protocol can easily be extended to a hybrid model, in which we have one round of synchronicity at the end of the input stage, but are fully asynchronous afterwards. In this model, our protocol allows to evaluate the circuit on the inputs of every honest party.

In this paper we show that two potential security vulnerabilities exist in the strong password-only authenticated key exchange scheme due to Jablon. Two standardised schemes based on Jablon's scheme, namely the first password-based key agreement mechanism in ISO/IEC FCD 11770-4 and the scheme BPKAS-SPEKE in IEEE P1363.2 also suffer from one or both of these security vulnerabilities. We further show that other password-based key agreement mechanisms, including those in ISO/IEC FCD 11770-4 and IEEE P1363.2, also suffer from these two security vulnerabilities. Finally, we propose means to remove these security vulnerabilities.

Since Bellare and Rogway's work [15], the indistinguishability-based security models of authenticated key agreement protocols in simple cases have been evolving for ten years. In this report, we review and organize the models under a unified framework with some new extensions. By providing a new ability (the Coin query) to adversaries and redefining two key security notions, the framework fully exploits an adversary's capability and can be used to prove all the commonly required security attributes of key agreement protocols with key confirmation. At the same time, the Coin query is also used to define a model which can be used to heuristically evaluate the security of a large category of authenticated protocols without key confirmation. We use the models to analyze a few pairing-based authenticated key agreement protocols.

In this paper we describe a simple protocol for securely delegating elliptic-curve pairings. A computationally limited device (typically a smart-card) will delegate the computation of the pairing e(A,B) to a more powerful device (for example a PC), in such a way that: 1. the powerful device learns nothing about the points being paired (A and B), nor about the pairing’s result e(A,B), 2. and the limited device is able to detect when the powerful device is cheating. We also describe more efficient variants of our protocol when one of the points or both are already known, and further efficiency gains when constant points are used.

We introduce the notion of tamper-evidence for digital signature generation in order to defend against attacks aimed at covertly leaking secret information held by corrupted network nodes. This is achieved by letting observers (which need not be trusted) verify the absence of covert channels by means of techniques we introduce herein. We call our signature schemes tamper-evident since any deviation from the protocol is immediately detectable. We demonstrate our technique for RSA-PSS and DSA signature schemes and how the same technique can be applied to Feige-Fiat-Shamir (FFS) and Schnorr signature schemes. Our technique does not modify the distribution of the generated signature transcripts, and has only a minimal overhead in terms of computation, communication, and storage. Keywords. covert channel, malware, observer, subliminal channel, tamper-evident, undercover

In this paper we are interested in efficient and secure constant round multi-party protocols which provide unconditional security against so called honest-but-curious adversaries. In particular, we design a novel constant round protocol that converts from shares over Z_q to shares over the integers working for all shared inputs from Z_q. Furthermore, we present a constant round protocol to securely evaluate a shared input on a public polynomial whose running time is linear in the degree of the polynomial. The proposed solution makes use of Chebyshev Polynomials. We show that the latter two protocols can be used to design efficient constant round protocols for the following natural problems: (i) Equality: Computing shares of the bit indicating if a shared input value equals zero or not. This provides the missing building blocks for many constant round linear algebra protocols from the work of Cramer and Damgaard [CrDa01]. (ii) Comparison: Computing shares of a bit indicating which of two shared inputs is greater. (iii) Bits: Computing shares of the binary representation of a shared input value. (iv) Exponentiation: Computing shares of x^a mod q given shares of x, a and q. Prior to this paper, for all the above mentioned problems, there were in general no efficient constant round protocols known providing unconditional security.

In this paper, we contribute the construction of practical perfect multiparty computation protocols based on the connectivity of graphs.

In IEEE INFOCOM 2004, Chan proposed a distributed key management scheme for mobile ad hoc networks, and deduced the condition under which the key sets distributed to the network nodes can form a cover-free family (CFF), which is the precondition that the scheme can work. In this paper, we indicate that the condition is falsely deduced. Furthermore, we discuss whether CFF is capable for key distributions in ad hoc networks.

We present a provably secure tree based authenticated group key agreement protocol in dynamic scenario. Bilinear pairing and multi-signature are at the heart of our protocol. We prove that our protocol is provably secure in the standard security model of Bresson et al. An appropriate modification of Katz-Yung approach to tree based setting is adopted while proving its security against active adversaries. The protocol has an in-built hierarchical structure that makes it desirable for certain applications.

Since Boneh and Franklin published their seminal paper on identity based encryption (IBE) using the Weil pairing , there has been a great deal of interest in cryptographic primitives based on elliptic-curve pairings. One particularly interesting application has been to control access to data, via possibly complex policies. In this paper we continue the research in this vein. We present an encryption scheme such that the receiver of an encrypted message can only decrypt if it satisfies a particular policy chosen by the sender at the time of encryption. Unlike standard IBE, our encryption scheme is escrow free in that no key-issuing authority (or colluding set of key-issuing authorities) is able to decrypt ciphertexts itself. In addition we describe a security model for the scenario in question and provide proofs of security for our scheme (in the random oracle model).

Group signature schemes allow a member of a group to sign messages anonymously on behalf of the group. In the case of later dispute, a designated group manager can revoke the anonymity and identify the originator of a signature. In Asiacrypt 2004, Nguyen and Safavi-Naini proposed a group signature scheme that has a constant-size public key and signature length, and more importantly, their group signature scheme does not require trapdoor. Their scheme is very efficient and the sizes of signatures are shorter compared to the existing schemes that were proposed earlier. In this paper, we point out that Nguyen and Safavi-Naini's scheme is insecure. In particular, we provide a cryptanalysis of the scheme that allows a non-member of the group to sign on behalf of the group. The resulting group signature can convince any third party that a member of the group has indeed generated such a signature, although none of the members has done it. Therefore, in the case of dispute, the group manager cannot identify who has signed the message. We also provide a new scheme that does not suffer against this problem.

Routing is one of the most basic networking functions in mobile ad hoc networks. Hence, an adversary can easily paralyze the operation of the network by attacking the routing protocol. This has been realized by many researchers, and several ``secure'' routing protocols have been proposed for ad hoc networks. However, the security of those protocols have mainly been analyzed by informal means only. In this paper, we argue that flaws in ad hoc routing protocols can be very subtle, and we advocate a more systematic way of analysis. We propose a mathematical framework in which security can be precisely defined, and routing protocols for mobile ad hoc networks can be analyzed rigorously. Our framework is tailored for on-demand source routing protocols, but the general principles are applicable to other types of protocols too. Our approach is based on the simulation paradigm, which has already been used extensively for the analysis of key establishment protocols, but to the best of our knowledge, it has not been applied in the context of ad hoc routing so far. We also propose a new on-demand source routing protocol, called endairA, and we demonstrate the usage of our framework by proving that it is secure in our model.

We introduce the notion of \emph{hierarchical group signatures}. This is a proper generalization of group signatures, which allows multiple group managers organized in a tree with the signers as leaves. For a signer that is a leaf of the subtree of a group manager, the group manager learns which of its children that (perhaps indirectly) manages the signer. We provide definitions for the new notion and construct a scheme that is provably secure given the existence of a family of trapdoor permutations. We also present a construction which is relatively practical, and prove its security in the random oracle model under the strong RSA assumption and the DDH assumption.

Recently, it has been proved that computational security can be automatically verified using the Dolev-Yao abstraction. We extend these results by adding a widely used component for cryptographic protocols: Diffie-Hellman exponentiation. Thus our main result is: if the Decisional Diffie-Hellman assumption is verified and the cryptographic primitives used to implement the protocol are secure, then safety in the symbolic world implies safety in the computational world. Therefore, it is possible to prove automatically safety in the computational world.

In the setting of concurrent self composition, a single protocol is executed many times concurrently by a single set of parties. In this paper, we prove lower bounds and impossibility results for secure protocols in this setting. First and foremost, we prove that there exist large classes of functionalities that {\em cannot} be securely computed under concurrent self composition, by any protocol. We also prove a {\em communication complexity} lower bound on protocols that securely compute a large class of functionalities in this setting. Specifically, we show that any protocol that computes a functionality from this class and remains secure for $m$ concurrent executions, must have bandwidth of at least $m$ bits. The above results are unconditional and hold for any type of simulation (i.e., even for non-black-box simulation). In addition, we prove a severe lower bound on protocols that are proven secure using black-box simulation. Specifically, we show that any protocol that computes the blind signature or oblivious transfer functionalities and remains secure for $m$ concurrent executions, where security is proven via {\em black-box simulation}, must have at least $m$ rounds of communication. Our results hold for the plain model, where no trusted setup phase is assumed. While proving our impossibility results, we also show that for many functionalities, security under concurrent {\em self} composition (where a single secure protocol is run many times) is actually equivalent to the seemingly more stringent requirement of security under concurrent {\em general} composition (where a secure protocol is run concurrently with other arbitrary protocols). This observation has significance beyond the impossibility results that are derived by it for concurrent self composition.

Key derivation refers to the process by which an agreed upon large random number, often named master secret, is used to derive keys to encrypt and authenticate data. Practitioners and standardization bodies have usually used the random oracle model to get key material from a Diffie-Hellman key exchange. However, proofs in the standard model require randomness extractors to formally extract the entropy of the random master secret into a seed prior to derive other keys. This paper first deals with the protocol $\Sigma_0$, in which the key derivation phase is (deliberately) omitted, and security inaccuracies in the analysis and design of the Internet Key Exchange (IKE version 1) protocol, corrected in IKEv2. They do not endanger the practical use of IKEv1, since the security could be proved, at least, in the random oracle model. However, in the standard model, there is not yet any formal global security proof, but just separated analyses which do not fit together well. The first simplification is common in the theoretical security analysis of several key exchange protocols, whereas the key derivation phase is a crucial step for theoretical reasons, but also practical purpose, and requires careful analysis. The second problem is a gap between the recent theoretical analysis of HMAC as a good randomness extractor (functions keyed with public but random elements) and its practical use in IKEv1 (the key may not be totally random, because of the lack of clear authentication of the nonces). Since the latter problem comes from the probabilistic property of this extractor, we thereafter review some \textit{deterministic} randomness extractors and suggest the \emph{'Twist-AUgmented'} technique, a new extraction method quite well-suited for Diffie-Hellman-like scenarios.

This paper suggests an improvement to the BB84 scheme in Quantum key distribution. The original scheme has its weakness in letting quantifiably more information gain to an eavesdropper during public announcement of unencrypted bases lists. The security of the secret key comes at the expense of the final key length. We aim at exploiting the randomness of preparation (measurement) basis and the bit values encoded (observed), so as to randomize the bases lists before they are communicated over the public channel. A proof of security is given for our scheme and proven that our protocol results in lesser information gain by Eve in comparison with BB84 and its other extensions. Moreover, an analysis is made on the feasibility of our proposal as such and to support entanglement based QKD. The performance of our protocol is compared in terms of the upper and lower bounds on the tolerable bit error rate. We also quantify the information gain (by Eve) mathematically using the familiar approach of the concept of Shannon entropy. The paper models the attack by Eve in terms of interference in a multi-access quantum channel. Besides, this paper also hints at the invalidation of a separate privacy amplification step in the "prepare-and-measure" protocols in general.

A class of efficient key agreement protocols proposed by Boyd is examined. An attack is demonstrated on a round-optimal example protocol of this class, and a simple countermeasure is suggested. The whole class is known to be vulnerable to an attack proposed by Bauer, Berson and Feiertag. A new class of key agreement protocols without this vulnerability but having the same advantages in efficiency is identified, and a number of concrete protocols are suggested.

A group signature scheme allows a group member of a given group to sign messages on behalf of the group in an anonymous fashion. In case of a dispute, however, a designated group manager can reveal the signer of a valid group signature. In the paper, we show the untraceability of two group signatures in [1, 5] by new and very simple attacks. Although those flaws, such as, forgeability, untraceability and linkability have been shown in [2, 7, 8, 9], we should point out that our attacks are more simple.

In a hierarchical structure, an entity has access to another if and only if the former is a superior of the later. The access control scheme for a hierarchy represented by a partially ordered set (poset) has been researched intensively in the past years. In this paper, we propose a new scheme that achieves the best performance of previous schemes and is provably secure under a comprehensive security model.

In this document, we provide an exposition of David Chaum's voter verification method that uses encrypted paper receipts. This document provides simply an exposition of the protocol, and does not address any of the proofs covered in Chaum's papers.

Two identification schemes based on the Maurer-Yacobi ID-based cryptosystem are analysed and shown to suffer from serious security problems.

In this paper we analyse an anonymous wireless authentication and conference key distribution scheme which is also designed to provide mobile participants with user identification privacy during the conference call. The proposed scheme consists of three sub-protocols: the Call Set-Up Authentication Protocol, the Hand-Off Authentication Protocol, and the Anonymous Conference Call Protocol. We show that the proposed scheme suffers from a number of security vulnerabilities.

Recently, Nenadić \emph{et al.} (2004) proposed the RSA-CEGD protocol for certified delivery of e-goods. This is a relatively complex scheme based on verifiable and recoverable encrypted signatures (VRES) to guarantee properties such as strong fairness and non-repudiation, among others. In this paper, we demonstrate how this protocol cannot achieve fairness by presenting a severe attack and also pointing out some other weaknesses.

A group signature scheme allows a group member of a given group to sign messages on behalf of the group in an anonymous and unlinkable fashion. In case of a dispute, however, a designated group manager can reveal the signer of a valid group signature. Many applications of group signatures require that the group manager can be split into a membership manager and a revocation manager. Such a group signature scheme with strong separability was proposed in paper [1]. Unfortunately, the scheme is insecure which has been shown in [2][3][4]. In this paper we show that the scheme is untraceable by a simple and direct attack. Besides, we show its universal forgeability by a general attack which only needs to choose five random numbers. We minutely explain the technique to shun the challenge in the scheme.

This paper describes an adaptive-chosen-ciphertext attack on the Cipher Feedback (CFB) mode of encryption as used in OpenPGP. In most circumstances it will allow an attacker to determine 16 bits of any block of plaintext with about $2^{15}$ oracle queries for the initial setup work and $2^{15}$ oracle queries for each block. Standard CFB mode encryption does not appear to be affected by this attack. It applies to a particular variation of CFB used by OpenPGP. In particular it exploits an ad-hoc integrity check feature in OpenPGP which was meant as a "quick check" to determine the correctness of the decrypting symmetric key.

We investigate the definition of statistical security (i.e., security against unbounded adversaries) in the framework of reactive simulatability. This framework allows to formulate and analyze multi-party protocols modularly by providing a composition theorem for protocols. However, we show that the notion of statistical security, as defined by Backes, Pfitzmann and Waidner for the reactive simulatability framework, does not allow for secure composition of protocols. This in particular invalidates the proof of the composition theorem. We give evidence that the reason for the non-composability of statistical security is no artifact of the framework itself, but of the particular formulation of statistical security. Therefore, we give a modified notion of statistical security in the reactive simulatability framework. We prove that this notion allows for secure composition of protocols. As to the best of our knowledge, no formal definition of statistical security has been fixed for Canetti's universal composability framework, we believe that our observations and results can also help to avoid potential pitfalls there.

We present a new two-party identity-based key agreement that is more efficient than previously proposed schemes. It is inspired on a new identity-based key pair derivation algorithm first proposed by Sakai and Kasahara. We show how this key agreement can be used in either escrowed or escrowless mode. We also describe conditions under which users of different Key Generation Centres can agree on a shared secret key. We give an overview of existing two-party key agreement protocols, and compare our new scheme with existing ones in terms of computational cost and storage requirements.

We present session-key generation protocols in a model where the legitimate parties share {\em only} a human-memorizable password, and there is no additional setup assumption in the network. Our protocol is proven secure under the assumption that trapdoor permutations exist. The security guarantee holds with respect to probabilistic polynomial-time adversaries that control the communication channel (between the parties), and may omit, insert and modify messages at their choice. Loosely speaking, the effect of such an adversary that attacks an execution of our protocol is comparable to an attack in which an adversary is only allowed to make a constant number of queries of the form ``is $w$ the password of Party $A$''. We stress that the result holds also in case the passwords are selected at random from a small dictionary so that it is feasible (for the adversary) to scan the entire directory. We note that prior to our result, it was not known whether or not such protocols were attainable without the use of random oracles or additional setup assumptions.

Recently, Cheng et al. proposed two tripartite key agreement protocols from pairings: one is certificate-based and the other is identity-based (ID-based). In this article, we show that the two schemes are vulnerable to the insider impersonation attack and the ID-based scheme even discloses the entities¡¦ private keys. Solutions to this problem are discussed.

In a distributed ring signature scheme, a subset of users cooperate to compute a distributed anonymous signature on a message, on behalf of a family of possible signing subsets. The receiver can verify that the signature comes from a subset of the ring, but he cannot know which subset has actually signed. In this work we use the concept of dual access structures to construct a distributed ring signature scheme which works with general families of possible signing subsets. The length of each signature is linear on the number of involved users, which is desirable for some families with many possible signing subsets. The scheme achieves the desired properties of correctness, anonymity and unforgeability. The reduction in the proof of unforgeability is tighter than the reduction in the previous proposals which work with general families. We analyze the case in which our scheme runs in an identity-based scenario, where public keys of the users can be derived from their identities. This fact avoids the necessity of digital certificates, and therefore allows more efficient implementations of such systems. But our scheme can be extended to work in more general scenarios, where users can have different types of keys.

A delegateable signature scheme is a signature scheme where the owner of the signing key(Alice) can securely delegate to another party(Bob) the ability to sign on Alice's behalf on a restricted subset $S$ of the message space. Barak first defined and constructed this signature scheme using non-interactive zero-knowledge proof of knowledge(NIZKPK)\cite{Barak}. In his delegateable signature scheme, the function of NIZKPK is to prevent the signing verifier from tell which witness(i.e. restricted subset) is being used. Witness indistinguishable(WI) and witness hiding(WH) proof systems are weaker proof model than zero-knowledge proof and were proposed by Feige and Shamir in \cite{FS}, however, the verifier cannot also distinguish the witness which is being used in these two protocols. In this paper, we construct delegateable signature scheme using WI and WH proof protocols.

Current hash chain traversal techniques require that the intermediate links of the hash chain be stored secretly on a trusted storage. This requirement is undesirable in several applications. We propose a new construction of hash chains based on inserting a ‘breakpoint’ after fixed number of links in the chain. We also propose a method with which the current hash chain traversal techniques can be applied to our construction without any significant changes in the storage and computation requirements and with the added advantage that the intermediate links may be stored on a public and non-trusted storage. We are also able to prove the security of our construction by replacing the hash function with a MAC function.

In this paper we analyse three improved authenticated group key agreement schemes, all of which are based on the conference key distribution systems proposed by Burmester and Desmedt. We show that all the schemes suffer from a type of impersonation attack, although these schemes are claimed to be secure.

In recent years there has been massive progress in the development of technologies for storing and processing of data. If statistical analysis could be applied to such data when it is distributed between several organisations, there could be huge benefits. Unfortunately, in many cases, for legal or commercial reasons, this is not possible. The idea of using the theory of multi-party computation to analyse efficient algorithms for privacy preserving data-mining was proposed by Pinkas and Lindell. The point is that algorithms developed in this way can be used to overcome the apparent impasse described above: the owners of data can, in effect, pool their data while ensuring that privacy is maintained. Motivated by this, we describe how to securely compute the mean of an attribute value in a database that is shared between two parties. We also demonstrate that existing solutions in the literature that could be used to do this leak information, therefore underlining the importance of applying rigorous theoretical analysis rather than settling for ad hoc techniques.