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.

This paper presents a new way of constructing binary cascade clock-controlled LFSR sequence generators as building blocks for stream ciphers. In these constructions the bottleneck of multiple clocking shift registers is removed, resulting in so called jump-controlled sequence generators, that operate in a single clock pulse and are most efficient to implement. The constructions make use of special properties of irreducible polynomials over finite fields. This paper also aims at giving insight into the mathematical theory behind the constructions. To this end, theory is developed and many of the rich set of properties of irreducible polynomials over GF(2), such as periods, jump indices and the number and cardinalities of various classes of polynomials are presented.

Recently, Wang, Yin, and Yu have used a low weight codeword in the SHA-1 message expansion to show a better than brute force method to find collisions in SHA-1. The codeword they used has a (bit) weight of 25 in the last 60 of the 80 expanded words. In this paper we show, using a computer assisted method, that this is indeed the smallest weight codeword. In particular, we show that the minimum weight over GF2 of any non-zero codeword in the SHA-1 (linear) message expansion code, projected on the last 60 words, is at least 25.

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.

Lal and Chaturvedi proposed two authentication sche\-mes presumably based on the difficulty of the Root Problem in the braid group. We describe a deterministic linear time algorithm to crack the first scheme, and show that the second scheme is not more secure than schemes based on the Conjugacy Search Problem, and can therefore be cracked by existing heuristic attacks with very good success probability, as long as the parameters are practical.

In this paper, we report that the "sufficient conditions" of MD5 of the modification technique for the collision search algorithm described by Wang are not sufficient. In our analysis, we show at least 4 extra-conditions for the message modification in the first block and corrections of the several conditions which are correspond to the highest (32nd) bit of the sufficient conditions in the second block should be needed. And we show the new collision message which is completely different from the message pairs showed by Wang by using our extended sufficient conditions.

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.

In this paper we examine the security criteria for a KEM and a DEM that are su±cient for the overall hybrid encryption scheme to be plaintext-aware in the standard model. We apply this theory to the Cramer-Shoup hybrid scheme acting on ¯xed length messages and deduce that the Cramer-Shoup scheme is plaintext-aware in the standard model. This answers a previously open conjecture of Bellare and Palacio on the existence of plaintext-aware encryption schemes.

In this paper, we introduce a powered Tate pairing on a supersingular elliptic curve that has the same shortened loop as the modified Tate pairing using the eta pairing approach by Barreto et al. The main significance of our approach is to remove the condition which the latter should rely on. It implies that our method is simpler and potentially general than the eta pairing approach, although they are equivalent in most practical cases.

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.

Identity based encryption (IBE) schemes have been flourishing since the very beginning of this century. In IBE it is widely believed that proving the security of a scheme in the sense of IND-ID-CCA2 is sufficient to claim the scheme is also secure in the senses of both SS-ID-CCA2 and NM-ID-CCA2. The justification for this belief is the relations among indistinguishability (IND), semantic security (SS) and non-malleability (NM). But these relations are proved only for conventional public key encryption (PKE) schemes in historical works. The fact is that between IBE and PKE, there exists a difference of special importance, i.e. only in IBE the adversaries can perform a particular attack, namely the chosen identity attack. This paper shows that security proved in the sense of IND-ID-CCA2 is validly sufficient for implying security in any other sense in IBE. This is to say the security notion, IND-ID-CCA2, captures the essence of security for all IBE schemes. To achieve this intention, we first describe formal definitions of the notions of security for IBE, and then present the relations among IND, SS and NM in IBE, along with rigorous proofs. All of these results are proposed with the consideration of the chosen identity attack.

We give three weaknesses of a recently proposed streamcipher MICKEY. A small class of weak keys is found and we show time-memory-data tradeoff is applicable. We also show that the state update function reduces entropy of the internal state as it is iterated, resulting in keystreams that start out differently but become merged together towards the end.

Traditional data authentication systems are sensitive to single bit changes and so are unsuitable for message spaces that are naturally fuzzy where similar messages are considered the same or at least indistinguishable. In this paper, we study unconditional secure approximate authentication. We generalize traditional universal hashing to fuzzy universal hashing and use it to construct secure approximate authentication for multiple messages.

We demonstrate how to prevent differential attacks on multivariate public key cryptosystems using the Plus (+) method of external perturbation. In particular, we prescribe adding as few as 10 Plus polynomials to the Perturbed Matsumoto-Imai (PMI) cryptosystem when $g=1$ and $r=6$, where $\theta$ is the Matsumoto-Imai exponent, $n$ is the message length, $g=\gcd{(\theta,n)}$, and $r$ is the internal perturbation dimension; or as few as $g+10$ when $g \neq 1$. The external perturbation does not significantly decrease the efficiency of the system, and in fact has the additional benefit of resolving the problem of finding the true plaintext among several preimages of a given ciphertext. We call this new scheme the Perturbed Matsumoto-Imai-Plus (PMI+) cryptosystem.

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.

Identity Based Encryption (IBE) has attracted a lot of attention since the publication of the scheme by Boneh and Franklin. So far, only indistinguishability based security notions have been considered in the literature, and it has not been investigated whether these definitions are appropriate. For this purpose, we define the goals of semantic security and non-malleability for IBE. We then compare the security notions resulting from combining those goals with the attacks previously considered in the literature (full and selective-identity attacks), providing either an implication or a separation. Remarkably, we show that the strongest security levels with respect to selective-identity attacks (i.e. chosen-ciphertext security) do not imply the weakest full-identity security level (i.e. one-wayness). With the aim of comprehensiveness, notions of security for IBE in the context of encryption of multiple messages and/or to multiple receivers are finally presented, as well as their relationship with the standard IBE security notion. The results obtained substantiate indistinguishability against full-identity chosen ciphertext attacks as the appropriate security notion for IBE.

The most significant pairing-based cryptographic protocol to be proposed so far is undoubtedly the Identity-Based Encryption (IBE) protocol of Boneh and Franklin. In their paper \cite{boneh-franklin} they give details of how their scheme might be implemented in practise on certain supersingular elliptic curves of prime characteristic. They also point out that the scheme could as easily be implemented on certain special non-supersingular curves for the same level of security. An obvious question to be answered is -- which is most efficient? Motivated by the work of Gallant, Lambert and Vanstone \cite{gallant-lambert-vanstone} we demonstrate that, perhaps counter to intuition, certain ordinary curves closely related to the supersingular curves originally recommended by Boneh and Franklin, provide better performance. We illustrate our technique by implementing the fastest pairing algorithm to date (on elliptic curves of prime characteristic) for contemporary levels of security. We also point out that many of the non-supersingular families of curves recently discovered and proposed for use in pairing-based cryptography can also benefit (to an extent) from the same technique.

In this paper we introduce the method of bi-linear cryptanalysis(BLC), designed specifically to attack Feistel ciphers. It allows to construct periodic biased characteristics that combine for an arbitrary number of rounds. In particular, we present a practical attack on DES based on a 1-round invariant, the fastest known based on such invariant, and about as fast as the best Matsui's attack. For ciphers similar to DES, based on small S-boxes, we claim that BLC is very closely related to LC, and we do not expect to find a bi-linear attack much faster than by LC. Nevertheless we have found bi-linear characteristics that are strictly better than the best Matsui's result for 3, 7, 11 and more rounds of DES. We also study s5DES substantially stronger than DES against LC, yet for BLC we exhibit several unexpectedly strong biases, stronger even than existing for DES itself. For more general Feistel schemes there is no reason whatsoever for BLC to remain only a small improvement over LC. We present a construction of a family of practical ciphers based on a big Rijndael-type S-box that are strongly resistant against linear cryptanalysis (LC) but can be easily broken by BLC, even with 16 or more rounds.

Often an attacker tries to disconnect a network by destroying nodes or edges, while the defender counters using various resilience mechanisms. Examples include a music industry body attempting to close down a peer-to-peer file-sharing network; medics attempting to halt the spread of an infectious disease by selective vaccination; and a police agency trying to decapitate a terrorist organisation. Albert, Jeong and Barabasi famously analysed the static case, and showed that vertex-order attacks are effective against scale-free networks. We extend this work to the dynamic case by developing a framework based on evolutionary game theory to explore the interaction of attack and defence strategies. We show, first, that naive defences don't work against vertex-order attack; second, that defences based on simple redundancy don't work much better, but that defences based on cliques work well; third, that attacks based on centrality work better against clique defences than vertex-order attacks do; and fourth, that defences based on complex strategies such as delegation plus clique resist centrality attacks better than simple clique defences. Our models thus build a bridge between network analysis and evolutionary game theory, and provide a framework for analysing defence and attack in networks where topology matters. They suggest definitions of efficiency of attack and defence, and may even explain the evolution of insurgent organisations from networks of cells to a more virtual leadership that facilitates operations rather than directing them. Finally, we draw some conclusions and present possible directions for future research.

Certificateless public key cryptography was introduced to overcome the key escrow limitation of the identity-based cryptography. Most of the existing certificateless public key encryption schemes are based on Boneh and Franklin's identity-based encryption scheme (BF-IBE). In this paper, we construct a new certificateless public key encryption scheme from the efficient SK-IBE which has been proved to be IND-ID-CCA secure. The new scheme is more efficient on computation complexity or published public key information than the existing schemes.

A series of recent papers have demonstrated collision attacks on popularly used hash functions, including the widely deployed MD5 and SHA-1 algorithm. To assess this threat, the natural response has been to evaluate the extent to which various protocols actually depend on collision resistance for their security, and potentially schedule an upgrade to a stronger hash function. Other options involve altering the protocol in some way. This work suggests a different option. We present several simple message pre-processing techniques and show how the techniques can be combined with MD5 or SHA-1 so that applications are no longer vulnerable to the known collision attacks. For some applications, this may a viable alternative to upgrading the hash function.

We develop a new computer assisted technique for lower bounding the minimum distance of linear codes similar to those used in SHA-1 message expansion. Using this technique, we prove that a modified SHA-1 like code has minimum distance at least 82, and that too in just the last 64 of the 80 expanded words. Further the minimum weight in the last 60 words (last 48 words) is at least 75 (52 respectively). We propose a new compression function which is identical to SHA-1 except for the modified message expansion code. We argue that the high minimum weight of the message expansion code makes the new compression function resistant to recent differential attacks.

We suggest an honest verifier zero-knowledge argument for the correctness of a shuffle of homomorphic encryptions. A shuffle consists of a rearrangement of the input ciphertexts and a re-encryption of them. One application of shuffles is to build mix-nets. Our scheme is more efficient than previous schemes in terms of both communication and computational complexity. Indeed, the HVZK argument has a size that is independent of the actual cryptosystem being used and will typically be smaller than the size of the shuffle itself. Moreover, our scheme is well suited for the use of multi-exponentiation techniques and batch-verification. Additionally, we suggest a more efficient honest verifier zero-knowledge argument for a commitment containing a permutation of a set of publicly known messages. We also suggest an honest verifier zero-knowledge argument for the correctness of a combined shuffle-and-decrypt operation that can be used in connection with decrypting mix-nets based on ElGamal encryption. All our honest verifier zero-knowledge arguments can be turned into honest verifier zero-knowledge proofs. We use homomorphic commitments as an essential part of our schemes. When the commitment scheme is statistically hiding we obtain statistical honest verifier zero-knowledge arguments, when the commitment scheme is statistically binding we obtain computational honest verifier zero-knowledge proofs.

In this paper, we analyse the algebraic immunity of symmetric Boolean functions. We identify a set of lowest degree annihilators for symmetric functions and propose an efficient algorithm for computing the algebraic immunity of a symmetric function. The existence of several symmetric functions with maximum algebraic immunity is proven. In this way, a new class of function which have good implementation properties and maximum algebraic immunity is found. We also investigate the existence of symmetric functions with high nonlinearity and reasonable order of algebraic immunity. Finally, we give suggestions how to use symmetric functions in a stream cipher.

The internal state of the Klimov-Shamir number generator TF-1 consists of four words of size w bits each, whereas its intended strength is 2^{2w}. We exploit an asymmetry in its output function to show that the internal state can be recovered after having 2^w outputs, using 2^{1.5w} operations. For w=32 the attack is practical, but for their recommended w=64 it is only of theoretical interest.

Sfinks is an LFSR-based stream cipher submitted to ECRYPT call for stream ciphers by Braeken, Lano, Preneel et al. The designers of Sfinks do not to include any protection against algebraic attacks. They rely on the so called "Algebraic Immunity", that relates to the complexity of a simple algebraic attack, and ignores other algebraic attacks. As a result, Sfinks is insecure.

In this paper, we consider the problem of private searching on streaming data, where we can efficiently implement searching for documents under a secret criteria (such as presence or absence of a hidden combination of hidden keywords) under various cryptographic assumptions. Our results can be viewed in a variety of ways: as a generalization of the notion of a Private Information Retrieval (to the more general queries and to a streaming environment as well as to public-key program obfuscation); as positive results on privacy-preserving datamining; and as a delegation of hidden program computation to other machines.

Klapper [1] showed that there are binary sequences of period $q^n-1$ ($q$ is a prime power $p^m$, $p$ is an odd prime) with the maximal possible linear complexity $q^n-1$ when considered as sequences over $GF(2)$, while the sequences have very low linear complexities when considered as sequences over $GF(p)$. This suggests that the binary sequences with high $GF(2)$ linear complexities and low $GF(p)$ linear complexities are note secure in cryptography. In this note we give some simple constructions of the binary sequences with high $GF(2)$ linear complexities and low $GF(p)$ linear complexities. We also prove some lower bounds on the $GF(p)$ linear complexities of binary sequences and a lower bound on the number of the binary sequences with high $GF(2)$ linear complexities and low $GF(p)$ linear complexities .

We present an attack on a new short signature scheme from bilinear pairing proposed by Okamoto $et$ $al.$ at ITCC'05. We show that any one can derive the secret key of the signer from any two message-signature pairs and so can forge the signer's signature for any message. This means the scheme is totally broken.

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 introduce a simple strong-designated verifier signature (SDVS) scheme which is much more efficient than previously proposed SDVS schemes. In addition, with only one more parameter published by the signer, this scheme can provide signer's forward security. That is, the consistency of a signature cannot be verified by any third party even if he/she knows a signer's private key. Thus the privacy of a signer's identity is protected independently in each signature, if the designated verifier's private key has not been disclosed. In addition, this scheme can be easily modified to a designated verifier signcryption scheme with virtually no additional cost. We will also show that the proposed scheme is provably secure in the random oracle model.

Much research has focused on providing RFID tags with lightweight cryptographic functionality. The HB+ authentication protocol was recently proposed and claimed to be secure against both passive and active attacks. In this note we propose a linear-time active attack against HB+.

Finding suitable non-supersingular elliptic curves becomes an important issue for the growing area of pairing-based cryptosystems. For this purpose, many methods have been proposed when embedding degree k and cofactor h are taken different values. In this paper we propose a new method to find pairing-friendly elliptic curves without restrictions on embedding degree k and cofactor h. We propose the idea of effective polynomial families for finding the curves through different kinds of Pell equations or special forms of D(x)V^2(x). In addition, we discover some efficient families which can be used to build pairing-friendly elliptic curves over extension fields, e.g. Fp^2 and Fp^4.

Nonclassical cryptographic technologies are considered in science and industry to provide alternative security solutions. They are motivated by the strong restrictions as they are often present in embedded security scenarios and in applications of pervasive computing. We investigate a low hardware-complexity cryptosystem for lightweight symmetric key exchange, based on two new Tree Parity Machine Rekeying Architectures (TPMRAs). The speed of a key exchange is basically only limited by the channel capacity. This work significantly improves and extends previously published results on TPMRAs. We evaluate characteristics of standard-cell ASIC design realizations as IP-core in 0.18-micrometer-CMOS technology.

In this note we point out that a recently published attack on the LILI-II stream cipher does not do better than generic time-memory tradeoff techniques (which generalise exhaustive search and apply to any 128-bit key cipher). Thus we assert that LILI-II remains unbroken.

This paper is a copy of IBM Research Report RZ 3019 published in 1998, which was a study of some issues related to keys of Arcfour. At the time of writing Arcfour was the common pseudonym used for RC4. Quite of a few of the results in the paper have now been superseded. We have submitted this paper to the IACR eprint archive mainly for reference purposes, since IBM research reports are not indexed in general by Google and other search engines.

Alternative security solutions are considered in science and industry, motivated by the strong restrictions as they are often present in embedded security scenarios -- especially in a RFID setting. We investigate a low hardware-complexity cryptosystem for lightweight symmetric key exchange and stream cipher based on Tree Parity Machines. The speed of a key exchange is basically only limited by the channel capacity as is the stream cipher throughput. This work significantly improves and extends previously published results on TPMRAs. Again, characteristics of standard-cell ASIC design realizations as IP-core in 0.18-micrometer-CMOS technology are evaluated.

The Diffie-Hellman key agreement protocol is based on taking large powers of a generator of a prime-order cyclic group. Some generators allow faster exponentiation. We show that to a large extent, using the fast generators is as secure as using a randomly chosen generator. On the other hand, we show that if there is some case in which fast generators are less secure, then this could be used by a malicious authority to generate a standard for the Diffie-Hellman key agreement protocol which has a hidden trapdoor.

In recent years, cryptographic protocols based on the bilinear pairings have attracted much attention. One of the most distinguished achievements in this area was the solution to design short signatures. Up to now, there exist two short signature schemes with random oracles and one without random oracles from bilinear pairings. In this paper, we describe another short signature scheme which is existentially unforgeable under a chosen message attack without using random oracles. The security of our scheme depends on a new complexity assumption we call the $k$+1 square roots assumption. We discuss the relationship between the $k$+1 square roots assumption and some related problems and give some conjectures. Further more, the $k$+1 square roots assumption gives even shorter signatures under the random oracles.

So far there is no systematic attempt to construct Boolean functions with maximum annihilator immunity. In this paper we present a construction keeping in mind the basic theory of annihilator immunity. This construction provides functions with the maximum possible annihilator immunity and the weight, nonlinearity and algebraic degree of the functions can be properly calculated under certain cases. The basic construction is that of symmetric Boolean functions and applying linear transformation on the input variables of these functions,one can get a large class of non-symmetric functions too. Moreover, we also study several other modifications on the basic symmetric functions to identify interesting non symmetric functions with maximum annihilator immunity. In the process we also present an algorithm to compute the Walsh spectra of a symmetric Boolean function with $O(n^2)$ time and $O(n)$ space complexity.

The most important and expensive operation in a hyperelliptic curve cryptosystem (HECC) is scalar multiplication by an integer k, i.e., computing an integer k times a divisor D on the Jacobian. Using some recoding algorithms for scalar $k$, we can reduce a number of divisor class additions during the process of computing scalar multiplication. So divisor doubling will account for the main part in all kinds of scalar multiplication algorithms. In order to accelerate the genus 3 HECC over binary fields we investigate how to compute faster doubling in this paper. By constructing birational transformation of variables, we derive explicit doubling formulae for all types of defining equations of the curve. For each type of curve, we analyze how many field operations are needed. So far all proposed curves are secure, though they are more special types. Our results allow to choose curves from a large enough variety which have extremely fast doubling needing only one third the time of an addition in the best case. Furthermore, an actual implementation of the new formulae on a Pentium-M processor shows its practical relevance.

The anonymity provided by the threshold ring signature scheme proposed by Bresson et al (Crypto'02) is perfect. However, its complexity is prohibitively large even for relatively small sets of signers. We propose use of threshold schemes based on covering designs that are efficient for large groups of signers. The cost we pay is non-perfect anonymity.

Identity-based encryption (IBE) is a special asymmetric encryption method where a public encryption key can be an arbitrary identifier and the corresponding private decryption key is created by binding the identifier with a system's master secret. In 2003 Sakai and Kasahara proposed a new IBE scheme, which has the potential to improve performance. However, to our best knowledge, the security of their scheme has not been properly investigated. This work is intended to build confidence in the security of the Sakai-Kasahara IBE scheme. In this paper, we first present an efficient IBE scheme that employs a simple version of the Sakai-Kasahara scheme and the Fujisaki-Okamoto transformation, which we refer to as SK-IBE. We then prove that SK-IBE has chosen ciphertext security in the random oracle model based on a reasonably well-explored hardness assumption.

In order to efficiently perform scalar multiplications on elliptic Koblitz curves, expansions of the scalar to a complex base associated with the Frobenius endomorphism are commonly used. One such expansion is the $\tau$-adic NAF, introduced by Solinas. Some properties of this expansion, such as the average weight, are well known, but in the literature there is no proof of its {\em optimality}, i.e.~that it always has minimal weight. In this paper we provide the first proof of this fact. Point halving, being faster than doubling, is also used to perform fast scalar multiplications on generic elliptic curves over binary fields. Since its computation is more expensive than that of the Frobenius, halving was thought to be uninteresting for Koblitz curves. At PKC 2004, Avanzi, Ciet, and Sica combined Frobenius operations with one point halving to compute scalar multiplications on Koblitz curves using on average 14\% less group additions than with the usual $\tau$-and-add method without increasing memory usage. The second result of this paper is an improvement over their expansion, that is simpler to compute, and optimal in a suitable sense, i.e.\ it has minimal Hamming weight among all $\tau$-adic expansions with digits $\{0,\pm1\}$ that allow one halving to be inserted in the corresponding scalar multiplication algorithm. The resulting scalar multiplication requires on average 25\% less group operations than the Frobenius method, and is thus 12.5\% faster than the previous known combination.

We describe an identity based key encapsulation mechanism (ID-KEM). It is possible to use this ID-KEM to build a secure identity based encryption scheme using the techniques of Bentahar et al. The resulting encryption scheme has a number of performance advantages over existing methods.

This dissertation has two chapters. In the first chapter we talk about the discrete logarithm problem, more specifically we concentrate on the Diffie-Hellman key exchange protocol. We survey the current state of security for the Diffie-Hellman key exchange protocol. We also motivate the reader to think about the Diffie-Hellman key exchange in terms of group automorphisms. In the second chapter we study two key exchange protocols similar to the Diffie-Hellman key exchange protocol using an abelian subgroup of the automorphism group of a nonabelian group. We also generalize group no.~92 of the Hall-Senior table, for arbitrary prime $p$ and study the automorphism group of these generalized group. We show that for those groups, the group of central automorphisms is an abelian group. We use these central automorphisms for the key exchange we are studying. We also develop a signature scheme.

Elliptic Curve Cryptography (ECC) has found wide applications in smart cards and embedded systems. Point multiplication plays a critical role in ECC. Many efficient point multiplication methods have been proposed. One of them is the comb method which is much more efficient than other methods if precomputation points are calculated in advance or elsewhere. Unfortunately, Many efficient point multiplication methods including the comb method are vulnerable to power-analysis attacks. Various algorithms to make elliptic curve point multiplication secure to power-analysis attacks have been proposed recently, such as the double-and-add-always method, Möller's window method, Okeya et al.'s odd-only window method, and Hedabou et al.'s comb method. In this paper, we first present a novel comb recoding algorithm which converts an integer to a sequence of signed, odd-only comb bit-columns. Using this recoding algorithm, we then present several comb methods, both Simple Power Analysis (SPA)-nonresistant and SPA-resistant, for point multiplication. These comb methods are more efficient than the original SPA-nonresistant comb method and Hedabou et al.'s SPA-resistant comb method. Our comb methods inherit the advantage of a comb method, running much faster than Möller's window method and Okeya et al.'s odd-only window method, as well as other window methods such as the efficient signed $m$-ary window method, if only the evaluation phase is taken into account. Combined with randomization projective coordinates or other randomization techniques and certain precautions in selecting elliptic curves and parameters, our SPA-resistant comb methods are resistant to all power-analysis attacks.

We present a fully symmetric constant round authenticated group key agreement protocol in dynamic scenario. Our proposed scheme achieves forward secrecy and is provably secure under DDH assumption in the security model of Bresson {\em et al.} providing, we feel, better security guarantee than previously published results. The protocol is efficient in terms of both communication and computation power.

The abstraction of cryptographic operations by term algebras, called Dolev-Yao models, is essential in almost all tool-supported methods for proving security protocols. Recently significant progress was made in proving that such abstractions can be sound with respect to actual cryptographic realizations and security definitions. The strongest results show this in the sense of reactive simulatability/UC, a notion that essentially means retention of arbitrary security properties under arbitrary active attacks and in arbitrary protocol environments, with only small changes to both abstractions and natural implementations. However, these results are so far restricted to cryptographic systems like encryption and signatures which essentially only have constructors and destructors, but no further algebraic properties. Typical modern tools and complexity results around Dolev-Yao models also allow more algebraic operations. The first such operation considered is typically XOR because of its clear structure and cryptographic usefulness. We show that it is impossible to extend the strong soundness results to XOR, at least not with remotely the same generality and naturalness as for the core cryptographic systems. On the positive side, we show the soundness of an XOR model and realization under passive attacks.

Nawaz, Gupta and Gong recently proposed a 32-bit RC4-like stream cipher. In this paper, we show that the keystream generated from their stream cipher is not random. The keystream can be distinguished from random with only about 100 outputs (3200 bits) in 2 milliseconds on Intel Centrino 1.6GHz processor.

We study, from a constructive computational point of view, the techniques used to solve the conjugacy problem in the "generic" lattice-ordered group Aut(R) of order automorphisms of the real line. We use these techniques in order to show that for each choice of parameters f,g in Aut(R), the equation xfx=g is effectively solvable in Aut(R).

We introduce the concept of identity based key encapsulation to multiple parties (mID-KEM), and define a security model for it. This concept is the identity based analogue of public key KEM to multiple parties. We also analyse possible mID-KEM constructions, and propose an efficient scheme based on bilinear pairings. We prove our scheme secure in the random oracle model under the Gap Bilinear Diffie-Hellman assumption.

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.

We compare four recent systems which have often been cited together, yet which have significant, subtle differences. We argue that the systems are not as interchangeable as several authors have suggested, attempt to correct common misconceptions about the systems, and suggest several potentially rich avenues of future work.

Time/memory trade-off (TMTO) was introduced by Hellman and later studied by many other authors. The effect of multiple data in Hellman TMTO was studied by Biryukov and Shamir (BS). We continue the analysis of the general multiple data TMTO started in BS. The trade-offs of Babbage and Golic (BG) and Biryukov-Shamir are obtained as special cases. Further, the general analysis is carried out under different conditions including that of Hellman optimality (online time equal to memory). Our main contribution is to identify a new class of single table multiple data trade-offs which cannot be obtained either as BG or BS trade-off. In certain cases, these new trade-offs can provide more desirable parameters than the BG or the BS methods. We consider the analysis of the rainbow method of Oechslin and show that for multiple data, the TMTO curve of the rainbow method is inferior to the TMTO curve of the Hellman method. The costs of the rainbow method and the Hellman+DP method can be comparable if the size of the search space is small and the cost of one table look-up is relatively high.

Bellare, Guerin, and Rogaway proposed a very efficient and secure message authentication scheme. By slightly modifying it, this article shows that the security is improved.

In this paper, we derive the probability distributions of difference propagation probabilities and input-output correlations for random functions and block ciphers, for several of them for the first time. We show that these parameters have distributions that are well-studied in the field of probability such as the normal, Poisson, Gamma and extreme value distributions. For Markov ciphers there exists a solid theory that expresses bounds on the complexity of differential and linear cryptanalysis in terms of average difference propagation probabilities and average correlations, where the average is taken over the keys. The propagation probabilities and correlations exploited in differential and linear cryptanalysis actually depend on the key and hence so does the attack complexity. The theory of Markov ciphers does not make statements on the distributions of these fixed-key properties but rather makes the assumption that their values will be close to the average for the vast majority of keys. This assumption is made explicit in the form of the hypothesis of stochastic equivalence. In this paper, we study the distributions of propagation properties that are relevant in the resistance of {\em key-alternating ciphers} against differential and linear cryptanalysis. Key-alternating ciphers are basically iterative ciphers where round keys are applied by an XOR operation in between unkeyed rounds and are a sub-class of Markov ciphers. We give the distributions of fixed-key difference propagation probability and fixed-key correlation of iterative ciphers. We show that for key-alternating ciphers, the hypothesis of stochastic equivalence can be discarded. In its place comes the explicit formulation of the distribution of fixed-key \emph{differential probability (DP)} of a differential in terms of its \emph{expected differential probability (EDP)} and the distribution of the fixed-key \emph{linear probability} (or rather \emph{potential}) (\emph{LP}) of a linear approximation (or hull) in terms of its \emph{expected linear probability (ELP)}. Here the ELP and EDP are defined by disregarding the key schedule of the block cipher and taking the average over independently selected round keys, instead of over all cipher keys. Proving these distributions requires no assumptions standardly made in Markov cipher theory as perfectly uniform behavior, independently acting rounds or the technique of averaging over keys. For key-alternating ciphers, we show that if the EDP is equal to $2^{-n}$ with $n$ the block length, the fixed-key DP has a distribution that is very close to that in a random $n$-bit cipher. The same holds for the ELP and the corresponding fixed-key LP. Finally we present a technique for computing bounds on the EDP based on the distribution of probabilities of differential characteristics and of the ELP based on the distribution of LP of linear characteristics.

A cryptographic primitive or a security mechanism can be specified in a variety of ways, such as a condition involving a game against an attacker, construction of an ideal functionality, or a list of properties that must hold in the face of attack. While game conditions are widely used, an ideal functionality is appealing because a mechanism that is indistinguishable from an ideal functionality is therefore guaranteed secure in any larger system that uses it. We relate ideal functionalities to games by defining the \textit{set} of ideal functionalities associated with a game condition and show that under this definition, which reflects accepted use and known examples, bit commitment, a form of group signatures, and some other cryptographic concepts do not have any realizable ideal functionality.

The Ideal-Cipher Model of a blockcipher is a well-known and widely-used model dating back to Shannon and has seen frequent use in proving the security of various cryptographic objects and protocols. But very little discussion has transpired regarding the meaning of proofs conducted in this model or regarding the model's validity. In this paper, we briefly discuss the implications of proofs done in the ideal-cipher model, then show some limitations of the model analogous to recent work regarding the Random-Oracle Model. In particular, we extend work by Canetti, Goldreich and Halevi, and a recent simplification by Maurer, Renner, and Holenstein, to exhibit a blockcipher-based hash function that is provably-secure in the ideal-cipher model but trivially insecure when instantiated by any blockcipher.

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.

For any integer $n$, some side information exists that allows roots of certain polynomials modulo $n$ to be found efficiently (in polynomial time). The quartics $q_{u,a,b}(x) = x^4 - 4ux^3 - 2ax^2 -(8b + 4ua)x + a^2 - 4ub$, where $a$ and $b$ are some fixed integers, can be solved with probability approximately $\frac{1}{4}$ over integers $u$ chosen randomly from in $\{0,1,\dots,n-1\}$. The side information depends on $a$ and $b$, and is derivable from the factorization of $n$. The side information does not necessarily seem to reveal the factorization of $n$. For certain other polynomials, such as $p_u(x) = x^3 - u$, it is an important unsolved problem of theoretical cryptology whether there exists an algorithm for finding roots that does not also reveal the factorization of $n$. Cheng's special-purpose factoring algorithm is also reviewed and some extensions suggested.

In this paper we show that Time-Memory tradeoff by Hellman may be extended to Time-Memory-Key tradeoff thus allowing attacks much faster than exhaustive search for ciphers for which typically it is stated that no such attack exists. For example, as a result AES with 128-bit key has only 85-bit security if $2^{43}$ encryptions of an arbitrary fixed text under different keys are available to the attacker. Such attacks are generic and are more practical than some recent high complexity chosen related-key attacks on round-reduced versions of AES. They constitute a practical threat for any cipher with 80-bit or shorter keys and are marginally practical for 128-bit key ciphers. We also show that UNIX password scheme even with carefully generated passwords is vulnerable to practical tradeoff attacks. Finally we also demonstrate a combination of rainbow tables with the time-memory-data tradeoff which results in a new tradeoff curve.

We examine the role of session key construction in provably- secure key establishment protocols. We revisit an ID-based key establishment protocol due to Chen & Kudla (2003) and an ID-based protocol 2P-IDAKA due to McCullagh & Barreto (2005). Both protocols carry proofs of security in a weaker variant of the Bellare & Rogaway (1993) model where the adversary is not allowed to make any Reveal query. We advocate the importance of such a (Reveal) query as it captures the known-key security requirement. We then demonstrate that a small change to the way that session keys are constructed in both protocols results in these protocols being secure without restricting the adversary from asking the Reveal queries in most situations. We point out some errors in the existing proof for protocol 2P-IDAKA, and provide proof sketches for the improved Chen & Kudla's protocol. We conclude with a brief discussion on ways to construct session keys in key establishment protocols.

HMQV is a `hashed variant' of the MQV key agreement protocol. It was recently introduced by Krawczyk, who claimed that HMQV has very significant advantages over MQV: (i) a security proof under reasonable assumptions in the (extended) Canetti-Krawczyk model for key exchange; and (ii) superior performance in some situations. In this paper we demonstrate that HMQV is insecure by presenting realistic attacks in the Canetti-Krawczyk model that recover a victim's static private key. We propose HMQV-1, a patched version of HMQV that resists our attacks (but does not have any performance advantages over MQV). We also identify the fallacies in the security proof for HMQV, critique the security model, and raise some questions about the assurances that proofs in this model can provide.

The central question in constructing a secure and efficient masking method for AES is to address the interaction between additive masking and the inverse S-box of Rijndael. All recently proposed methods to protect AES against power attacks try to avoid this problem and work by decomposing the inverse in terms of simpler operations that are more easily protected against DPA by generic methods. In this paper, for the first time, we look at the problem in the face, and show that this interaction is not as intricate as it seems. In fact, any operation, even complex, can be directly protected against DPA of any given order, if it can be embedded in a group that has a compact representation. We show that a secure computation of a whole masked inverse can be done directly in this way, using the group of homographic transformations over the projective space (but not exactly, with some non-trivial technicalities). This is used to propose a general high-level algebraic method to protect AES against power attacks of any given order.

In this paper we are interested in algebraic immunity of several well known highly-nonlinear vectorial Boolean functions (or S-boxes), designed for block and stream ciphers. Unfortunately, ciphers that use such S-boxes may still be vulnerable to so called "algebraic attacks" proposed recently by Courtois, Pieprzyk, Meier, Armknecht, et al. These attacks are not always feasible in practice but are in general very powerful. They become possible, if we regard the S-boxes, no longer as highly-nonlinear functions of their inputs, but rather exhibit (and exploit) much simpler algebraic equations, that involve both input and the output bits. Instead of complex and "explicit" Boolean FUNCTIONS we have then simple and "implicit" algebraic RELATIONS that can be combined to fully describe the secret key of the system. In this paper we look at the number and the type of relations that do exist for several well known components. We wish to correct or/and complete several inexact results on this topic that were presented at FSE 2004. We also wish to bring a theoretical contribution. One of the main problems in the area of algebraic attacks is to prove that some systems of equations (derived from some more fundamental equations), are still linearly independent. We give a complete proof that the number of linearly independent equations for the Rijndael S-box (derived from the basic equation XY=1) is indeed as reported by Courtois and Pieprzyk. It seems that nobody has so far proven this fundamental statement.

In about every book about cryptography, we learn that the plaintext complexity of differential cryptanalysis on DES is 2^47, as reported by Biham and Shamir. Yet few people realise that in a typical setting this estimation is not exact and too optimistic. In this note we show that the two "best" differentials for DES used by Biham and Shamir are NOT the best differentials that exist in DES. For approximations over many rounds such as used in the Biham-Shamir attack from the best characteristic is in fact a third, different differential already given by Knudsen. A more detailed analysis shows that on average the best differential attack on DES remains the Biham-Shamir attack, because it can exploit two differentials at the same time and their propagation probabilities are related. However for a typical fixed DES key, the attack requires on average about 2^48.34 chosen plaintexts and not 2^47 as initially claimed. In addition, if the key is changing frequently during the attack, then in fact Biham and Shamir initial figure of 2^47 is correct. We were surprised to find out that (with differential cryptanalysis) it is easier to break DES with a changing key, than for one fixed key.

McCullagh and Barreto presented an identity-based authenticated key agreement protocol in CT-RSA 2005. Their protocol was found to be vulnerable to a key-compromise impersonation attack. In order to recover the weakness, McCullagh and Barreto, and Xie proposed two variants of the protocol respectively. In each of these works, a security proof of the proposed protocol was presented. In this paper, we revisit these three security proofs and show that all the reductions in these proofs are invalid, because the property of indistinguishability between their simulation and the real world was not held. As a replacement, we slightly modify the McCullagh and Barreto's second protocol and then formally analyse the security of the modified scheme in the Bellare-Rogaway key agreement model.

We construct and analyze Feistel and SPN ciphers that have a sound design strategy against linear and differential attacks but for which the encryption process can be described by very simple polynomial equations. For a block and key size of 128 bits, we present ciphers for which practical Groebner basis attacks can recover the full cipher key requiring only a minimal number of plaintext/ciphertext pairs. We show how Groebner bases for a subset of these ciphers can be constructed with neglegible computational effort. This reduces the key recovery problem to a Groebner basis conversion problem. By bounding the running time of a Groebner basis conversion algorithm, FGLM, we demonstrate the existence of block ciphers resistant against differential and linear cryptanalysis but vulnerable against Groebner basis attacks.

We propose a formal model for security of verifiable shuffles and a new verifiable shuffle system based on the Paillier encryption scheme, and prove its security in the proposed model. The model is general, so it can be extended to verifiable shuffle decryption and provides a direction for provable security of mix-nets.

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.

In this paper we show that the password-based Diffie-Hellman key exchange protocols due to Byun and Lee suffer from dictionary attacks.

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 introduce {\em Twin RSA}, pairs of RSA moduli $(n,n+2)$, and formulate several questions related to it. Our main questions are: is Twin RSA secure, and what is it good for?

Let $N(d,d^\perp)$ denote the minimum length $n$ of a linear code $C$ with $d$ and $d^{\bot}$, where $d$ is the minimum Hamming distance of $C$ and $d^{\bot}$ is the minimum Hamming distance of $C^{\bot}$. In this paper, we show a lower bound and an upper bound on $N(d,d^\perp)$. Further, for small values of $d$ and $d^\perp$, we determine $N(d,d^\perp)$ and give a generator matrix of the optimum linear code. This problem is directly related to the design method of cryptographic Boolean functions suggested by Kurosawa et al.

We introduce VSH, {\em very smooth hash}, a new $S$-bit hash function that is provably collision-resistant assuming the hardness of finding nontrivial modular square roots of very smooth numbers modulo an $S$-bit composite. By very smooth, we mean that the smoothness bound is some fixed polynomial function of~$S$. We argue that finding collisions for VSH has the same asymptotic complexity as factoring using the Number Field Sieve factoring algorithm, i.e., subexponential in~$S$. %We show how our asymptotic argument can be turned into a practical method to %select parameters so that VSH meets a desired security level. VSH is theoretically pleasing because it requires just a single multiplication modulo the~$S$-bit composite per $\Omega(S)$ message-bits (as opposed to $O(\log S)$ message-bits for previous provably secure hashes). It is relatively practical. A preliminary implementation on a 1GHz Pentium III processor that achieves collision resistance at least equivalent to the difficulty of factoring a 1024-bit RSA modulus, runs at 1.1 MegaByte per second, with a moderate slowdown to 0.7MB/s for 2048-bit RSA security. VSH can be used to build a fast, provably secure randomised trapdoor hash function, which can be applied to speed up provably secure signature schemes (such as Cramer-Shoup) and designated-verifier signatures.

This paper builds on the multi-time signature scheme proposed by Merkle. We prove that the original scheme is existentially unforgeable under adaptive chosen message attack. Moreover, we present an improved version which has three advantages: It is provably forward secure. The number of signatures that can be made with one private key is --- in a practical sense --- unlimited. Finally, the cost for key generation is kept low. The theoretical exposition is complemented by experimental data about the efficiency of the improved Merkle signature scheme.

The public key encryption with keyword search (PEKS) scheme recently proposed by Boneh, Di Crescenzo, Ostrovsky, and Persiano enables one to search encrypted keywords without compromising the security of the original data. In this paper, we address three important issues of a PEKS scheme, ``refreshing keywords'', ``removing secure channel'', and ``processing multiple keywords'', which have not been considered in Boneh et. al.'s paper. We argue that care must be taken when keywords are used frequently in the PEKS scheme as this situation might contradict the security of PEKS. We then point out the inefficiency of the original PEKS scheme due to the use of the secure channel. We resolve this problem by constructing an efficient PEKS scheme that removes secure channel. Finally, we propose a PEKS scheme that encrypts multiple keywords efficiently.

In this paper, we prove the security of the {\sf RSA-AKE} protocol \cite{SKI05} in the random oracle model. The proof states that the {\sf RSA-AKE} protocol is secure against an adversary who gets the client's stored secret \emph{or} the server's RSA private key.\footnote{The protocol is the same as \cite{SKI05}, but we corrected the security proof partially. The attacks appeared in \cite{TM05} are no longer available in the proof since the adversary has access to either the client's stored secret or the server's private key, not both of them.} To our best knowledge, the {\sf RSA-AKE} protocol is the most efficient among their kinds (i.e., RSA and password based AKE protocols). The other security properties and efficiency measurements of the {\sf RSA-AKE} protocol remain the same as in \cite{SKI05}.

Coppersmith's heuristic algorithm for finding small roots of bivariate modular equations can be applied against low-exponent RSA-OAEP if its randomizer is weak. An adversary that knows the randomizer can recover the entire plaintext message, provided it is short enough for Coppersmith's algorithm to work. In practice, messages are symmetric cipher keys and these are potentially short enough for certain sets of key sizes. Weak randomizers could arise in constrained smart cards or in kleptographic implementations. Because RSA's major use is transporting symmetric keys, this attack is a potential concern. In this respect, OAEP's design is more fragile than necessary, because a secure randomizer is critical to prevent a total loss of secrecy, not just a loss of semantic security or chosen-ciphertext security. Countermeasures and more robust designs that have little extra performance cost are proposed and discussed.

We present the first group signature scheme with provable security and signature size $O(\lambda)$ bits where the group manager, the group members, and the Open Authority (OA) are all identity-based. We use the security model of Bellare, Shi, and Zhang, except to add three identity managers for manager, members, and OA respectively, and we discard the Open Oracle. Our construction uses identity-based signatures summarized in Bellare, Namprempre, and Neven for manager, Boneh and Franklin's IBE for OA, and we extend Bellare et al.'s group signature construction by verifiably encrypt an image of the member public key, instead of the public key itself. The last innovation is crucial in our efficiency; otherwise, Camenisch and Damgard's verifiable encryption would have to be used resulting in lower efficiency.

The original paper does not have an abstract. This is a scanned version of the original hand written manuscript of this paper. It appeared in print as a Harvard University Technical Report, but at some point the university ran out of copies. At that time copies of the hand written version started to circulate, and were the only ones available. As access to these copies has become difficult I have scanned my copy of the paper and I'm posting it on the web for others to read. *Note that the manuscript has a different title, but the paper is most commonly (if not only) cited with this title. Thus, I assume that it should continue to be cited in this manner with reference to the original technical report.

The unlinkability is an important security property that blind signature schemes should satisfy. But we find that the several blind signature schemes [1,2,3] are linkable. The Signer can derive a link between a protocol view and a valid blind signature. They are not secure.

In this paper we analyse the security of two authenticated group key agreement schemes based on the group key agreement protocol of Burmester and Desmedt. One scheme was proposed by Burmester and Desmedt, and uses a separate authentication scheme to achieve authentication among the participants. We show that this scheme suffers from a number of security vulnerabilities. The other scheme was generated using the general protocol compiler of Katz and Yung. We show that in some circumstances, even if key confirmation is implemented, this scheme still suffers from insider attacks (which are not covered by the security model used by Katz and Yung).

To protect copyrighted digital data against piracy, codes with different secure properties such as frameproof codes, secure frameproof codes, codes with identifiable parent property (IPP codes), traceability codes (TA codes) are introduced. In this paper, we study these codes together with related combinatorial objects called separating and perfect hash families. We introduce for the first time the notion of difference function families and use these difference function families to give generalized recursive techniques that can be used for any kind of secure codes and hash families. We show that some previous recursive techniques are special cases of these new techniques.

This document revisits the PEKE (Probabilistic Encryption Key Exchange) cryptosystem and proposes the enhanced PEKEv1.25 that performs a hash computation on the original PEKE output in order to improve the security assurance and to broaden the field of use. For a key establishment application where only the server side publishes a long-term public key and can adequately protect the private key counterpart from implementation attacks, we claim that PEKE is unsurpassed in security and efficiency, among the finite field arithmetic cryptosystems (e.g. RSA and finite field Diffie-Hellman). We use an original definition for the type of key encapsulation service provided by PEKE, hoping that this abstract definition captures the characteristics of the protocol and usage context. However, we only suggest that related security proofs are encouraging for the security of PEKE.

Recently, Chang et al. proposed an authenticated key agreement and protected password change scheme. They claimed that their scheme is simple and efficient. However, in this letter we point out that their protected password change protocol is insecure under the denial-of-service attack and the dictionary attack in some situations.

This paper tries to sell a potential approach to making the process of writing and verifying our cryptographic proofs less prone to errors. Specifically, I advocate creating an automated tool to help us with the mundane parts of writing and checking common arguments in our proofs. On a high level, this tool should help us verify that two pieces of code induce the same probability distribution on some of their common variables. In this paper I explain why I think that such a tool would be useful, by considering two very different proofs of security from the literature and showing the places in those proofs where having this tool would have been useful. I also explain how I believe that this tool can be built. Perhaps surprisingly, it seems to me that the functionality of such tool can be implemented using only ``static code analysis'' (i.e., things that compilers do).

Most recently, Lee B. et al proposed a key issuing protocol for ID-based cryptography to solve the key escrow problem. However in this letter, we show that a malicious key generation center (KGC) can successfully attack the protocol to obtain users¡¯ private keys. This means that in the protocol, the key escrow problem isn¡¯t really removed.

We introduce a new method of achieving intrusion-resilience in the cryptographic protocols. More precisely we show how to preserve security of such protocols, even if a malicious program (e.g. a virus) was installed on a computer of an honest user (and it was later removed). The security of our protocols relies on the assumption that the amount of data that the adversary can transfer from the infected machine is limited (however, we allow the adversary to perform any efficient computation on user's private data, before deciding on what to transfer). We focus on two cryptographic tasks, namely: authenticated key exchange and entity authentication. Our method is based on the results from the Bounded-Storage Model.

Miyaji et.al proposed a fully functional(i.e., satisfying unforgeability, exculpability,anonymity, traceability, unlinkability, and revocability.) group signature over only known-order groups, that is based only on Discrete logarithm related assumptions, specifically, multiple DLP they proposed in the same paper [MU04]. In this paper, we point out their scheme and an improved scheme [ZZW05] do not have unlinkability.

We prove that for $d>1$ the information rate of the perfect secret sharing scheme based on the edge set of the $d$-dimensional cube is exactly $2/d$. Using the technique developed, we also prove that the information rate of the infinite $d$-dimensional lattice is $1/d$.

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

In this paper we propose a new 32-bit RC4 like keystream generator. The proposed generator produces 32 bits in each iteration and can be implemented in software with reasonable memory requirements. Our experiments show that this generator is 3.2 times faster than original 8-bit RC4. It has a huge internal state and offers higher resistance against state recovery attacks than the original 8-bit RC4. We analyze the randomness properties of the generator using a probabilistic approach. The generator is suitable for high speed software encryption.

An increasingly important design constraint for software running on ubiquitous computing devices is security, particularly against physical methods such as side-channel attack. One well studied methodology for defending against such attacks is the concept of indistinguishable functions which leak no information about program control flow since all execution paths are computationally identical. However, the constructing such functions by hand is laborious and error prone as their complexity increases. We investigate techniques for automating this process and find that effective solutions can be constructed with only minor amounts of computational effort.

In this paper we demonstrate the existence of a number of weaknesses in a leakage-resilient authenticated key transport (RSA-AKE) protocol due to Shin, Kobara and Imai.

We introduce mechanisms for secure keyword searches on a document server. We propose protocols with computational privacy, query correctness assurances and minimal or no leaks: the server either correctly executes client queries or (if it behaves maliciously) is immediately detected. The client is then provided with strong assurances proving the authenticity and completeness of server replies. This is different from existing research efforts, where a cooperating, non-malicious server behavior is assumed. We also strengthen the privacy guarantees. The oblivious search protocol not only hides (from the server) the outsourced data but also does not leak client access patterns, the queries themselves, the association between previously searched keywords and returned documents or between newly added documents and their corresponding keywords (not even in encrypted form). This comes naturally at the expense of additional computation costs which we analyze in the context of today's off the shelf hardware. In a reasonable scenario, a single CPU off-the-shelf PC can easily handle hundreds of such oblivious searches per minute.

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.

We introduce and motivate the concept of unclonable group identification, that provides maximal protection against sharing of identities while still protecting the anonymity of users. We prove that the notion can be realized from any one-way function and suggest a more efficient implementation based on specific assumptions.