On an elliptic curve, the degree of an isogeny corresponds essentially to the degrees of the polynomial expressions involved in its application. The multiplication--by--$\ell$ map $[\ell]$ has degree~$\ell^2$, therefore the complexity to directly evaluate $[\ell](P)$ is $O(\ell^2)$. For a small prime $\ell\, (= 2, 3)$ such that the additive binary representation provides no better performance, this represents the true cost of application of scalar multiplication. If an elliptic curves admits an isogeny $\varphi$ of degree $\ell$ then the costs of computing $\varphi(P)$ should in contrast be $O(\ell)$ field operations. Since we then have a product expression $[\ell] = \hat{\varphi}\varphi$, the existence of an $\ell$-isogeny $\varphi$ on an elliptic curve yields a theoretical improvement from $O(\ell^2)$ to $O(\ell)$ field operations for the evaluation of $[\ell](P)$ by naïve application of the defining polynomials. In this work we investigate actual improvements for small $\ell$ of this asymptotic complexity. For this purpose, we describe the general construction of families of curves with a suitable decomposition $[\ell] = \hat{\varphi}\varphi$, and provide explicit examples of such a family of curves with simple decomposition for~$[3]$. Finally we derive a new tripling algorithm to find complexity improvements to triplication on a curve in certain projective coordinate systems, then combine this new operation to non-adjacent forms for $\ell$-adic expansions in order to obtain an improved strategy for scalar multiplication on elliptic curves.

We consider the problem of using untrusted components to build correlation-resistant survivable storage systems that protect file replica locations, while allowing nodes to continuously re-distribute files throughout the network. The principal contribution is a chosen-ciphertext secure, searchable public key encryption scheme which allows for dynamic re-encryption of ciphertexts, and provides for node-targeted searches based on keywords or other identifiers. The scheme is provably secure under the SXDH assumption which holds in certain subgroups of elliptic curves, and a closely related assumption that we introduce.

A secure group signature is required to be anonymous, that is, given two group signatures generated by two different members on the same message or two group signatures generated by the same member on two different messages, they are indistinguishable except for the group manager. In this paper we prove the equivalence of a group signature's anonymity and its indistinguishability against chosen ciphertext attacks if we view a group signature as an encryption of member identity. Particularly, we prove ACJT's group signature is IND-CCA2 secure, so ACJT's scheme is anonymous in the strong sense. The result is an answer to an open question in literature.

In this article, we examine how the index calculus approach for computing discrete logarithms in small genus hyperelliptic curves can be improved by introducing a double large prime variation. Two algorithms are presented. The first algorithm is a rather natural adaptation of the double large prime variation to the intended context. On heuristic and experimental grounds, it seems to perform quite well but lacks a complete and precise analysis. Our second algorithm is a considerably simplified variant, which can be analyzed easily. The resulting complexity improves on the fastest known algorithms. Computer experiments show that for hyperelliptic curves of genus three, our first algorithm surpasses Pollard's Rho method even for rather small field sizes.

The successful application to elliptic curve cryptography of side-channel attacks, in which information about the secret key can be recovered from the observation of side channels like power consumption or timing, has motivated the recent development of unified formulæ for elliptic curve point operations. In this paper, we give a version of a previously-developed family of unified point addition formulæ that uses projective coordinates for improved efficiency. We discuss the applicability of a recent attack by Walter on this family of projective formulæ and describe how the field arithmetic can be implemented to obtain fully unified formulæ and avoid this type of attack.

Digital signature is one of the most important primitives in public key cryptography. It provides authenticity, integrity and non-repudiation to many kinds of applications. On signer privacy however, it is generally unclear or suspicious of whether a signature scheme itself can guarantee the anonymity of the signer. In this paper, we give some affirmative answers to it. We formally define the signer anonymity for digital signature and propose some schemes of this type. We show that a signer anonymous signature scheme can be very useful by proposing a new anonymous key exchange protocol which allows a client Alice to establish a session key with a server Bob securely while keeping her identity secret from eavesdroppers. In the protocol, the anonymity of Alice is already maintained when Alice sends her signature to Bob in clear, and no additional encapsulation or mechanism is needed for the signature. We also propose a method of using anonymous signature to solve the collusion problem between organizers and reviewers of an anonymous paper review system.

We deal with the radix-r representation used for the scalar multiplication of pairing-based cryptosystems with characteristic r. Our goal of this paper is to present some invariant properties about the signed radix-r representation; (1) approximation formulae for the average significant length and the average hamming weight of gNAF and wrNAF representation, (2) some classification formulae of equivalent classes called as Cutting Lemma, Collision Lemma, and Search Space Theorem. We also analyze the security of signed radix-r representations in the sense of side channel attacks, and to this end we propose a secure countermeasure.

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?

This thesis gives an overview of Multivariate Quadratic polynomial equations and their use in public key cryptography. In the first chapter, some general terms of cryptography are introduced. In particular, the need for public key cryptography and alternative schemes is motivated, i.e., systems which neither use factoring (like RSA, Rivest-Shamir-Adleman) nor the discrete logarithm (like ECC, elliptic curve cryptography). This is followed by a brief introduction of finite fields and a general discussion about Multivariate Quadratic systems of equations and ways of representing them. In this context, affine transformations and their representations are also discussed. After these tools are introduced, they are used to show how Multivariate Quadratic equations can be used for signature and encryption applications. In addition, the problem of Multivariate Quadratic polynomial equations is put into perspective and a link with the theory of NP-completeness is established. The second chapter concludes with the two related problems "isomorphism of polynomials" and "minimal rank" of the sum of matrices. Both prove useful in the cryptanalysis of Multivariate Quadratic systems. The main part of this thesis is about concrete trapdoors for the problem of Multivariate Quadratic public key systems. We can show that all such systems fall in one of the following four classes: unbalanced oil and vinegar systems (UOV), stepwise triangular systems (STS), Matsumoto-Imai Scheme A (MIA), and hidden field equations (HFE). Moreover, we demonstrate the use of several modifiers. In order to evaluate the security of these four basic trapdoors and their modifiers, we review some cryptanalytic results. In particular, we were able to develop our own contributions in this field by demonstrating an affine approximation attack and an attack using Gr"obner base computations against the UOV class. Moreover, we derived a key recovery and inversion attack against the STS class. Using our knowledge of the HFE class, we develop two secure versions of the signature scheme Quartz. Another important part of this thesis is the study of the key space of Multivariate Quadratic public key systems. Using special classes of affine transformations, denoted ``sustainers", we are able to show that all four basic classes have some redundancy in their key spaces and hence, have a smaller key space than previously expected. In particular for the UOV and the STS class, this reduction proves quite dramatic. For HFE and MIA, we only find some minor redundancies. Moreover, we are able to show that our results for MIA are the only ones possible, i.e., there are no other redundancies than the one we describe in this thesis. In addition, we extend our results to several important variations of HFE and MIA, namely HFE-, HFEv, HFEv-, and MIA-. They have been used in practice for the construction of signature schemes, namely Quartz and Sflash. In order to demonstrate the practical relevance of Multivariate Quadratic constructions and also of our taxonomy, we show some concrete examples. In particular, we consider the NESSIE submissions Flash, Sflash, and Quartz and discuss their advantages and disadvantages. Moreover, we describe some more recent developments, namely the STS-based schemes enhanced TTS, Tractable Rational Maps, and Rainbow. Then we move on to some application domains for Multivariate Quadratic public key systems. In particular, we see applications in the area of product activation keys, electronic stamps and fast one-way functions. Finally, we suggest some new schemes. In particular, we give a generalisation of MIA to odd characteristics and also investigate some other trapdoors like STS and UOV with the branching and the homogenisation modifiers. All in all, we believe that Multivariate Quadratic polynomial systems are a very practical solution to the problem of public key cryptography. At present, it is not possible to use them for encryption. However, we are confident that it will be possible to overcome this problem soon and use Multivariate Quadratic constructions both for encrypting and signing.

A generic or KEM-DEM hybrid construction is a formal method of combining a asymmetric and symmetric encryption techniques to give an efficient, provably secure public-key encryption scheme. This method combines an asymmetric KEM with a symmetric DEM, and each of these components must satisfy their own security conditions. In this paper we describe generic constructions for provably secure KEMs based on lower level primitives such as one-way trapdoor functions and weak key-agreement protocols.

This paper shows the first practical semantically secure public-key encryption scheme such that its one-wayness is equivalent to {\it general} factoring in the {\it standard} model (in the sense of IND-CPA). Next our proof technique is applied to Rabin-Paillier encryption scheme and a variant of RSA-Paillier encryption scheme to prove their exactly tight one-wayness.

We compute Tate pairing over supersingular elliptic curves via the generic BGhES\cite{BGES} method for $p=5,7$. In those cases, the point multiplication by $p$ is efficiently computed by the Frobenius endomorphism. The function in a cycle can be efficiently computed by the method of continued fraction.

In this paper, we present a variant of Waters' Identity-Based Encryption scheme with a much smaller public-key size (only a few kilobytes). We show that this variant is semantically secure against passive adversaries in the standard model.\smallskip In essence, the new scheme divides Waters' public key size by a factor $\ell$ at the cost of (negligibly) reducing security by $\ell$ bits. Therefore, our construction settles an open question asked by Waters and constitutes the first fully secure {\sl practical} Identity-Based Encryption scheme.

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.

Motivated by the needs of the {\it pairing based cryptography\/}, Miyaji, Nakabayashi and Takano have suggested a construction of so-called MNT elliptic curves with low embedding degree. We give some heuristic arguments which suggest that there are only about $z^{1/2+o(1)}$ of MNT curves with complex multiplication discriminant up to $z$. We also show that there are very few finite fields over which elliptic curves with small embedding degree and small complex multiplication discriminant may exist (regardless of the way they are constructed).

In a recent letter, Cui, Duan and Chan propose a generalisation of the Scott-Barreto method to build a larger family of MNT curves, and they claim that their proposal is also applicable to other curve construction methods. Here we show that the Cui-Duan-Chan technique is irrecoverably flawed.

ID-based encryption allows for a sender to encrypt a message to an identity without access to a public key certificate. Based on the bilinear pairing, Boneh and Franklin proposed the first practical ID-based encryption scheme and used the padding technique of Fujisaki-Okamto to extend it to be a chosen ciphertext secure version. In this letter, we would like to use another padding technique to propose a new ID-based encryption scheme secure against chosen ciphertext attacks. The security of our scheme is based on the Gap bilinear Diffie-Hellman assumption in the random oracle model.

Constructing non-supersingular elliptic curves for pairing-based cryptosystems have attracted much attention in recent years. The best previous technique builds curves with p = lg(q)/lg(r) = 1 (k = 12) and p = lg(q)/lg(r) = 1.25 (k = 24). When k > 12, most of the previous works address the question by representing r(x) as a cyclotomic polynomial. In this paper, we propose a new method to find more pairing-friendly elliptic curves with arbitrary embedding degree k by certain special polynomial families. The new method generates curves with lg(q)/lg(r) = 1 (k > 48) by random forms of r(x). Different representations of r(x) allow us to obtain many new families of pairing-friendly elliptic curves. In addition, we propose a equation to illustrate how to obtain small values of p by choosing appropriate forms of discriminant D and trace t. Numerous parameters of certain pairing-friendly elliptic curves are presented with support for the theoretical conclusions.

We describe the group structure underlying several popular homomorphic public-key systems and the problems they are based on. We prove several well-known security results using only the group structure and assumptions about the related problems. Then we provide examples of two new instances of this group structure and analyse their security.

In [2], Stanislav Bulygin presents a chosen-ciphertext attack against certain instances of noncommutative polly cracker-type cryptosystems which were proposed in [7] and [9]. In this article, we present generalized versions of this attack, which can be used against virtually all polly cracker-type cryptosystems. We then present a simple but effective techique to counter these attacks. We also present a technique to counter an adaptive chosen-ciphertext attack which was first described by Neil Koblitz in [8].

In the classic Diffie-Hellman protocol based on a generic group $\G$, Alice and Bob agree on a common secret $K_{AB}$ (master secret) which is indistinguishable from another element of $\G$ but not from a random bits-string of the same length. In this paper, we present a new deterministic method to extract bits from $K_{AB}$ when $\G$ is an elliptic curve defined over a quadratic extension of a finite field. In the last section, we show that it is also possible to extract a few bits when $\G$ is an elliptic curve defined over a prime field.

To help motivate the Weil pairing, we discuss it in the context of elliptic curves over the field of complex numbers.

Public-key cryptosystem (PKC) is one of inevitable key technologies in order to accomplish fruitful security applications in ubiquitous computing systems. The ubiquitous computer only has scarce computational resources (like Smart cards, RFID, Sensor Network), however, so that the light weight PKC is necessary for those miniaturized low-power devices. Recently, XTR is considered as one of good candidates for more energy efficient cryptosystems. Among XTR exponentiation algorithms, the most efficient one is the Improved XTR Single Exponentiation (XTR-ISE) proposed by Stam-Lenstra. Thus among the family of XTR algorithms, XTR-ISE is the most efficient one suitable for ubiquitous computer. Even though the security of such devices against side channel attacks is very dangerous, there are few works on side channel attacks against XTR-ISE. In this paper we propose a new collision attack on XTR-ISE, derived from the structural properties of XTR-ISE. The analysis complexity of the proposed one is about 2^{40} where the key size is 160-bit, which is 55% improvement from the previously best known analysis of Page-Stam. We also propose a novel countermeasure using a fixed pattern which is secure against SPA. We deploy a variant of Euclidean algorithm whose one of the registers is a monotone decreasing function with odd value. From our estimation of the efficiency of the proposed method, XTR exponentiation, computing Tr(g^n) with Tr(g) and n, takes 11.2log_2n multiplications in F_{p^2}. In the sense of both efficiency and security the proposed countermeasure is the best one among the previous countermeasures- it is about 30% faster.

In 1986, D. V. Chudnovsky and G. V. Chudnovsky proposed to use formulae coming from Theta functions for the arithmetic in Jacobians of genus 2 curves. We follow this idea and derive fast formulae for the scalar multiplication in the Kummer surface associated to a genus 2 curve, using a Montgomery ladder. Our formulae can be used to design very efficient genus 2 cryptosystems that should be faster than elliptic curve cryptosystems in some hardware configurations.

A new type of signature is presented in this paper, named adaptable group-oriented signature. In contrast with traditional group-oriented signature, the new one laid a strong emphasis on how to improve the signer¡¯s efficiency. In fact, this new type of group-oriented signature can be seen as a type of designated verifier signature. In contrast with the ordinary designated verifier signature, it does not designate one member but several members to independently verify the signature. The designated members, who can independently verify the signature, come into a group. This scheme can ensure the anonymity of the verifiers. This type of signature can be used in such system that the compute resource is limited, such as the broadcast protocols of the mobile telephone in the mobile networks.

The theoretical equivalence between the DLP and DHP problems was shown by Maurer in 1994. His work was then reexamined by Muzereau et al. for the special case of elliptic curves used in practical cryptographic applications. This paper improves on the latter and tries to get the tightest possible reduction in terms of computational equivalence, using Maurer's method.

In Sept.1990, the present authors firstly discussed DLP over composite number and presented an ID-based Key Sharing Scheme referred to as MK1. In 1991, Maurer and Yacobi presented a scheme, referred to as MY, which is similar to our scheme, MK1. Unfortunately the schemes MK1 and MY are not secure. In Dec.1990, the present authors presented a secure ID-based key sharing scheme referred to as MK2. With a rapid progress of computer power for the last 15 years, our proposed scheme would have more chance to be applied practically. Regrettably, it has not been widely known that (i) the schemes MY and MK1 are not secure, (ii) there exists a secure scheme, MK2. In this paper, we shall review MK2 and clarify the difference between MK2 and other schemes from the standpoint of security.

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.

We present a general technique for the efficient computation of pairings on supersingular Abelian varieties. This formulation, which we call the eta pairing, generalises results of Duursma and Lee for computing the Tate pairing on supersingular elliptic curves in characteristic three. We then show how our general technique leads to a new algorithm which is about twice as fast as the Duursma-Lee method. These ideas are then used for elliptic and hyperelliptic curves in characteristic 2 with very efficient results. In particular, the hyperelliptic case is faster than all previously known pairing algorithms.

In this paper we propose a variant of RSA public key scheme, called ``Hidden Exponent RSA''. Based on this new scheme, we devised an efficient key distribution/management scheme for secure communication among devices in the context of pervasive computing, with emphasis on the simplicity and efficiency of the protocol. We show the new scheme is secure under the strong RSA assumption.

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.

We present novel realizations of the transitive signature primitive introduced by Micali and Rivest, enlarging the set of assumptions on which this primitive can be based, and also providing performance improvements over existing schemes. More specifically, we propose new schemes based on factoring, the hardness of the one-more discrete logarithm problem, and gap Diffie-Hellman groups. All these schemes are proven transitively unforgeable under adaptive chosen-message attack. We also provide an answer to an open question raised by Micali and Rivest regarding the security of their RSA-based scheme, showing that it is transitively unforgeable under adaptive chosen-message attack assuming the security of RSA under one-more-inversion. We then present hash-based modifications of the RSA, factoring and gap Diffie-Hellman based schemes that eliminate the need for ``node certificates'' and thereby yield shorter signatures. These modifications remain provably secure under the same assumptions as the starting scheme, in the random oracle model.

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.

Public key cryptography has been invented to overcome some key management problems in open networks. Although nearly all aspects of public key cryptography rely on the existence of trapdoor one-way functions, only a very few candidates of this primitive have been observed yet. In this paper, we introduce a new trapdoor one-way permutation based on the hardness of factoring integers of $p^2q$-type. We also propose a variant of this function with a different domain that provides some advantages for practical applications. To confirm this statement, we develop a simple hybrid encryption scheme based on our proposed trapdoor permutation that is CCA-secure in the random oracle model.

The original presentation of the NTRUSign signature scheme gave a set of parameters that were claimed to give 80 bits of security, but did not give a general recipe for generating parameter sets to a specific level of security. In line with recent research on NTRUEncrypt, this paper presents an outline of such a recipe for NTRUSign. We also present certain technical advances upon which we intend to build in subsequent papers.

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.

In this article, we investigate the question of equivalent keys for two $\mathcal{M}$ultivariate $\mathcal{Q}$uadratic public key schemes HFE and C$^{*--}$ and improve over a previously known result, to appear at PKC 2005. Moreover, we show a new non-trivial extension of these results to the classes HFE-, HFEv, HFEv-, and C$^{*--}$, which are cryptographically stronger variants of the original HFE and C$^*$ schemes. In particular, we are able to reduce the size of the private --- and hence the public --- key space by at least one order of magnitude. While the results are of independent interest themselves, we also see applications both in cryptanalysis and in memory efficient implementations.

In this article, we investigate the class of multivariate quadratic (\MQ) public key systems. These systems are becoming a serious alternative to RSA or ECC based systems. After introducing the main ideas and briefly sketching some relevant systems, we deal with the advantages and disadvantages of these kind of schemes. Based on our observations, we determine application domains in which \MQ-schemes have advantages over RSA or ECC. We concentrate on product activation keys, electronic stamps and fast one-way functions.

In this paper, we study the new class step-wise Triangular Schemes (STS) of public key cryptosystems (PKC) based on multivariate quadratic polynomials. In these schemes, we have $m$ the number of equations, $n$ the number of variables, $L$ the number of steps/layers, $r$ the number of equations/variables per step, and $q$ the size of the underlying field. We present two attacks on the STS class by exploiting the chain of the kernels of the private key polynomials. The first attack is an inversion attack which computes the message/signature for given ciphertext/message in $O(mn^3Lq^r + n^2Lrq^r)$, the second is a structural attack which recovers an equivalent version of the secret key in $O(mn^3Lq^r + mn^4)$ operations. Since the legitimate user has workload $q^r$ for decrypting/computing a signature, the attacks presented in this paper are very efficient. As an application, we show that two special instances of STS, namely RSE(2)PKC and RSSE(2)PKC, recently proposed by Kasahara and Sakai, are insecure.

The Unbalanced Oil and Vinegar scheme (UOV) is a signature scheme based on multivariate quadratic equations. It uses $m$ equations and $n$ variables. A total of $v$ of these are called ``vinegar variables". In this paper, we study its security from several points of view. First, we are able to demonstrate that the constant part of the affine transformation does not contribute to the security of UOV and should therefore be omitted. Second, we show that the case $n \geq 2m$ is particularly vulnerable to Gröbner basis attacks. This is a new result for UOV over fields of odd characteristic. In addition, we investigate a modification proposed by the authors of UOV, namely to chose coefficients from a small subfield. This leads to a smaller public key. But due to the smaller key-space, this modification is insecure and should therefore be avoided. Finally, we demonstrate a new attack which works well for the case of small $v$. It extends the affine approximation attack from Youssef and Gong against the Imai-Matsumoto Scheme~B for odd characteristic and applies it against UOV. This way, we point out serious vulnerabilities in UOV which have to be taken into account when constructing signature schemes based on UOV.

The most popular public key cryptosystems rely on assumptions from algebraic number theory, e.g., the difficulty of factorisation or the discrete logarithm. The set of problems on which secure public key systems can be based is therefore very small: e.g., a breakthrough in factorisation would make RSA insecure and hence affect our digital economy quite dramatically. This would be the case if quantum-computer with a large number of qbits were available. Therefore, a wider range of candidate hard problems is needed. In 1996, Patarin proposed the ``Hidden Field Equations" (HFE) as a base for public key cryptosystems. In a nutshell, they use polynomials over finite fields of different size to disguise the relationship between the private key and the public key. In these systems, the public key consists of multivariate polynomials over finite fields with up to 256 elements for practical implementations. Over finite fields, solving these equations has been shown to be an NP-complete problem. In addition, empirical results show that this problem is also hard on average, i.e., it can be used for a secure public key signature or encryption scheme. In this article, we outline HFE, and its the variations HFE-, HFEv. Moreover, we describe the signature scheme Quartz, which is based on Hidden Field Equations. In addition, we describe the most recent attacks against HFE and sketch two versions of Quartz which are immune against these 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.

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 identity-based (ID-based) cryptosystems, a local registration authority (LRA) is responsible for authentication of users while the key generation center (KGC) is responsible for computing and sending the private keys to users and therefore, a secure channel is required. For privacy-oriented applications, it is important to keep in secret whether the private key corresponding to a certain identity has been requested. All of the existing ID-based key issuing schemes have not addressed this anonymity issue. Besides, the separation of duties for authentication and private key computation has not been discussed as well. In this paper, based on a signature scheme similar to a short blind signature, we propose a novel separable and anonymous ID-based key issuing scheme without secure channel. Our protocol supports the separation of duties between LRA and KGC. The private key computed by the KGC can be sent to the user in an encrypted form such that only the legitimate key requester authenticated by LRA can decrypt it, and any eavesdropper cannot know the identity corre-sponding to the secret key.

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.

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.

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 propose a variant of the Paillier cryptosystem that improves efficiency in encryption, re-encryption and decryption while preserving the homomorphic property. We then use this variant to construct a new verifiable shuffle system and prove its security. We show that the new shuffle scheme has the least number of rounds and exponentiations compared to all known shuffle schemes. Finally, we show how to construct a publicly verifiable mix-net using the shuffle system.

k-times anonymous authentication (k-TAA) schemes allow members of a group to be anonymously authenticated by application providers for a bounded number of times. k-TAA has application in e-voting, e-cash, electronic coupons and anonymous trial browsing of content. In this paper, we extend k-TAA model to dynamic k-TAA in which application providers can independently grant or revoke users from their own groups and so have the required control on their clients. We give a formal model for dynamic k-TAA, propose a dynamic k-times anonymous authentication scheme from bilinear pairing, and prove its security. We also construct an ordinary k-TAA from the dynamic scheme and show communication efficiency of the schemes compared to the previously proposed schemes.

The static Diffie-Hellman problem (SDHP) is the special case of the classic Diffie-Hellman problem where one of the public keys is fixed. We establish that the SDHP is almost as hard as the associated discrete logarithm problem. We do this by giving a reduction that shows that if the SDHP can be solved then the associated private key can be found. The reduction also establishes that certain systems have less security than anticipated. The systems affected are based on static Diffie-Hellman key agreement and do not use a key derivation function. This includes some cryptographic protocols: basic ElGamal encryption; Chaum and van Antwerpen's undeniable signature scheme; and Ford and Kaliski's key retrieval scheme, which is currently being standardized in IEEE P1363.2.

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.

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.

ID-based cryptosystem has been, for a few years, the most active area of research and currently is of great interest to the cryptographic society. In this work we survey three fundamental ID-based cryptographic primitives Digital Signature, Encryption and Key Agreement, which are based on the mathematical concepts Integer Factorization, Quadratic Residues and Bilinear Pairings. We review several schemes along with their efficiency and security considerations. The survey helps in understanding the research work carried out in the area of ID-based cryptosystems from the year 1984 to 2004.

We present a new probabilistic algorithm to compute modular polynomials modulo a prime. Modular polynomials parameterize pairs of isogenous elliptic curves and are useful in many aspects of computational number theory and cryptography. Our algorithm has the distinguishing feature that it does not involve the computation of Fourier coefficients of modular forms. We avoid computing the exponentially large integral coefficients by working directly modulo a prime and computing isogenies between elliptic curves via Velu's formulas.

This paper should be considered as a draft. Part of it is an extended version of the paper Generic Attacks and the Security of Quartz presented at PKC 2003 and at the second Nessie workshop. It also contains a lot of new material that is not published elsewhere: -(yet another) discussion about what is and what isn't a secure signature scheme -up-to-date security results fo Sflash and Quartz -new results on computational security of Sflash w.r.t algebraic relation attacks in the light of Faugère-Joux Crypto 2003 paper. -and more... Comments are welcome !

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.

In [3] Al-Riyami and Paterson introduced the notion of "Certificateless Public Key Cryptography" and presented an instantiation. In this paper, we revisit the formulation of certificateless public key encryption and construct a more efficient scheme and then extend it to an authenticated encryption.

Attack is possible upon all three RSA analogue PKCs based on singular cubic curves given by Koyama. While saying so, Seng et al observed that the scheme become insecure if a linear relation is known between two plaintexts. In this case, attacker has to compute greatest common divisor of two polynomials corresponding to those two plaintexts. However, the computation of greatest common divisor of two polynomials is not efficient. For the reason, the degree e of both polynomials, an encryption exponent, is quite large. In this paper, we propose an algorithm, which makes the attack considerably efficient. Subsequently we identify isomorphic attack on the Koyama schemes by using the isomorphism between two singular cubic curves.

Recently Kurosawa and Desmedt presented a new hybrid encryption scheme which is secure against adaptive chosen-ciphertext attack. Their scheme is a modification of the Cramer-Shoup encryption scheme. Its major advantage with respect to Cramer-Shoup is that it saves the computation of one exponentiation and produces shorter ciphertexts. However, the proof presented by Kurosawa and Desmedt relies on the use of information-theoretic key derivation and message authentication functions. In this note we present a different proof of security which shows that the Kurosawa-Desmedt scheme can be instantiated with any computationally secure key derivation and message authentication functions, thus extending the applicability of their paradigm, and improving its efficiency.

We introduce two new left-to-right integer recodings which can be used to perform scalar multiplication with a fixed sequence of operations. These recodings make it possible to have a simple power analysis resistant implementation of a group-based cryptosystem without using unified formulas or introducing dummy operations. This approach is very useful for groups in which the doubling step are less expensive than the addition step, for example with hyperelliptic curves over binary fields or elliptic curves with mixed coordinates.

In recent years cryptographic protocols based on the Weil and Tate pairings on elliptic curves have attracted much attention. A notable success in this area was the elegant solution by Boneh and Franklin of the problem of efficient identity-based encryption. At the same time, the security standards for public key cryptosystems are expected to increase, so that in the future they will be capable of providing security equivalent to 128-, 192-, or 256-bit AES keys. In this paper we examine the implications of heightened security needs for pairing-based cryptosystems. We first describe three different reasons why high-security users might have concerns about the long-term viability of these systems. However, in our view none of the risks inherent in pairing-based systems are sufficiently serious to warrant pulling them from the shelves. We next discuss two families of elliptic curves E for use in pairing-based cryptosystems. The first has the property that the pairing takes values in the prime field F_p over which the curve is defined; the second family consists of supersingular curves with embedding degree k=2. Finally, we examine the efficiency of the Weil pairing as opposed to the Tate pairing and compare a range of choices of embedding degree k, including k=1 and k=24.

A blind signature scheme is a protocol for obtaining a digital signature from a signer, but the signer can neither learn the messages he/she sign nor the signatures the recipients obtain afterwards. Partially blind signature is a variant such that part of the message contains pre-agreed information (agreed by the signer and the signature requester) in unblinded form, while threshold blind signature distributes the signing power to a group of signers such that a signature can only be produced by interacting with a predetermined numbers of signers. In this paper, we propose a threshold partially blind signature scheme from bilinear pairings and an ID-based partially blind signature scheme, which are provably secure in the random oracle model. To the best of authors' knowledge, we give the first discussion on these two notions.

Identity-based (ID-based) cryptosystems eliminate the need for validity checking of the certificates and the need for registering for a certificate before getting the public key. These two features are desirable especially for the efficiency and the real spontaneity of ring signature, where a user can anonymously sign a message on behalf of a group of spontaneously conscripted users including the actual signer. In this paper, we propose a novel construction of ID-based ring signature which only needs two pairing computations for any group size. The proposed scheme is proven to be existential unforgeable against adaptive chosen message-and-identity attack under the random oracle model, using the forking lemma for generic ring signature schemes. We also consider its extension to support the general access structure.

We present a novel index calculus algorithm for the discrete logarithm problem (DLP) in degree 0 class groups of curves over finite fields. A heuristic analysis of our algorithm indicates that asymptotically for varying q, ``essentially all'' instances of the DLP in degree 0 class groups of curves represented by plane models of a fixed degree d over $\mathbb{F}_q$ can be solved in an expected time of $\tilde{O}(q^{2 -2/(d-2)})$. A particular application is that heuristically, ``essentially all'' instances of the DLP in degree 0 class groups of non-hyperelliptic curves of genus 3 (represented by plane curves of degree 4) can be solved in an expected time of $\tilde{O}(q)$. We also provide a method to represent ``sufficiently general'' (non-hyperelliptic) curves of genus $g \geq 3$ by plane models of degree $g+1$. We conclude that on heuristic grounds the DLP in degree 0 class groups of ``sufficiently general'' curves of genus $g \geq 3$ (represented initially by plane models of bounded degree) can be solved in an expected time of $\tilde{O}(q^{2 -2/(g-1)})$.

The first practical identity based encryption (IBE) scheme was proposed by Boneh and Franklin. In this work we point out that there is a flawed step in the security reduction exhibited by the authors. Fortunately, it is possible to fix it without changing the scheme or the underlying assumption. In the second place, we introduce a variant of the seminal IBE scheme which allows a more efficient security reduction. The new scheme is simpler, and has more compact ciphertexts than Boneh-Franklin's proposal, while keeping the computational cost. Finally, we observe that the flawed step pointed out here is present in several works, and that our techniques can be applied to obtain tighter reductions for previous relevant schemes.

We propose a new secure communication primitive called an \emph{Intrusion-Resilient Channel (IRC)} that limits the damage resulting from key exposures and facilitates recovery. We define security against passive but mobile and highly adaptive adversaries capable of exposing even expired past secrets. We describe an intuitive channel construction using (as a black box) existing public key cryptosystems. The simplicity of the construction belies the technical challenges in its security proof. Additionally, we outline a general strategy for proving enhanced security for two-party protocols when an IRC is employed to secure all communication. Specifically, given a protocol proved secure against adversaries with restricted access to protocol messages, we show how the use of an IRC allows some of these adversary restrictions to be lifted. Once again, proving the efficacy of our intuitive approach turns out to be non-trivial. We demonstrate the strategy by showing that the intrusion-resilient signature scheme of [IR02] can be made secure against adversaries that expose even expired secrets.

A new technique is proposed in which bandwidth and memory are together used to reduce both the number of point additions and doublings required in computing random point multiplication. Using the proposed technique, we show that a significant speed-up can be obtained at the cost of slightly increased bandwidth. In addition, we show that the proposed technique is well-suited for parallel processing.

In1985, Shmuley proposed a theorem about intractability of Composite Diffie-Hellman [Sh85]. The Theorem of Shmuley may be paraphrased as saying that if there exist a probabilistic poly-time oracle machine which solves the Diffie-Hellman modulo an RSA-number with odd-order base then there exist a probabilistic algorithm which factors the modulo. In the other hand factorization of the module obtained only if we can solve the Diffie-Hellman with odd-order base. In this paper we show that even if there exist a probabilistic poly-time oracle machine which solves the problem only for even-order base and abstain answering the problem for odd-order bases still a probabilistic algorithm can be constructed which factors the modulo in poly-time for more than 98% of RSA-numbers.

An efficient and semantically secure public key cryptosystem based on singular cubic curve is proposed in this paper. It is about two times faster than the cryptosystem of David at the same security label and more efficient than the Koyama scheme at high security level. Further, the partially known plaintext attack and the linearly related plaintext attacks are analyzed and concluded that those are not possible in the proposed scheme.

This report explicitly refutes the analysis behind a recent claim that NTRUEncrypt has a bit security of at most 74 bits. We also sum up some existing literature on NTRU and lattices, in order to help explain what should and what should not be classed as an improved attack against the hard problem underlying NTRUEncrypt. We also show a connection between Schnorr's RSR technique and exhaustively searching the NTRU lattice.

We provide a new security proof for a variant of ElGamal proposed by Damgård, showing that it is secure against non-adaptive chosen ciphertext. Unlike previous security proofs for this cryptosystem, which rely on somewhat problematic assumptions, our computational problem is similar to accepted problems such the Gap and Decision Diffie-Hellman problems.

Blind signature is the concept to ensure anonymity of e-coins. Untracebility and unlinkability are two main properties of real coins, which require mimicking electronically. Whenever a user is permitted to spend an e-coin, he is in need to fulfill above requirements of blind signature. This paper proposes a proxy blind signature scheme with which a proxy is able to make proxy blind signature which verifier is able to verify in a way similar to proxy signature schemes.

At Crypto 2004, van Dijk and Woodruff introduced a new way of using the algebraic tori T_n in cryptography, and obtained an asymptotically optimal n/phi(n) savings in bandwidth and storage for a number of cryptographic applications. However, the computational requirements of compression and decompression in their scheme were impractical, and it was left open to reduce them to a practical level. We give a new method that compresses orders of magnitude faster than the original, while also speeding up the decompression and improving on the compression factor (by a constant term). Further, we give the first efficient implementation that uses T_30, compare its performance to XTR, CEILIDH, and ECC, and present new applications. Our methods achieve better compression than XTR and CEILIDH for the compression of as few as two group elements. This allows us to apply our results to ElGamal encryption with a small message domain to obtain ciphertexts that are 10% smaller than in previous schemes.

We describe two new public key broadcast encryption systems for stateless receivers. Both systems are fully secure against any number of colluders. In our first construction both ciphertexts and private keys are of constant size (only two group elements), for any subset of receivers. The public key size in this system is linear in the total number of receivers. Our second system is a generalization of the first that provides a tradeoff between ciphertext size and public key size. For example, we achieve a collusion resistant broadcast system for n users where both ciphertexts and public keys are of size O(sqrt(n)) for any subset of receivers. We discuss several applications of these systems.

We propose a practical sampling reduction algorithm for lattice bases based on work by Schnorr as well as two even more effective generalizations. We report the empirical behaviour of these algorithms. We describe how Sampling Reduction allows to stage lattice attacks against the NTRU cryptosystem with smaller BKZ parameters than before and conclude that therefore the recommeded NTRU security parameters offer $\leq 74$ Bit security.

We introduce a new type of Identity-Based Encryption (IBE) scheme that we call Fuzzy Identity-Based Encryption. In Fuzzy IBE we view an identity as set of descriptive attributes. A Fuzzy IBE scheme allows for a private key for an identity, $\omega$, to decrypt a ciphertext encrypted with an identity, $\omega'$, if and only if the identities $\omega$ and $\omega'$ are close to each other as measured by the ``set overlap'' distance metric. A Fuzzy IBE scheme can be applied to enable encryption using biometric inputs as identities; the error-tolerance property of a Fuzzy IBE scheme is precisely what allows for the use of biometric identities, which inherently will have some noise each time they are sampled. Additionally, we show that Fuzzy-IBE can be used for a type of application that we term ``attribute-based encryption''. In this paper we present two constructions of Fuzzy IBE schemes. Our constructions can be viewed as an Identity-Based Encryption of a message under several attributes that compose a (fuzzy) identity. Our IBE schemes are both error-tolerant and secure against collusion attacks. Additionally, our basic construction does not use random oracles. We prove the security of our schemes under the Selective-ID security model.

We analyze and critique the public-key cryptosystem, based on combinatorial group theory, that was proposed by Wagner and Magyarik in 1984. This idea is actually not based on the word problem but on another, generally easier, premise problem. Moreover, the idea of the Wagner-Magyarik system is vague, and it is difficult to find a secure realization of this idea. We describe a public-key cryptosystem inspired in part by the Wagner-Magyarik idea, but we also use group actions on words.

We extend the concept of key encapsulation mechanisms to the primitives of ID-based and certificateless encryption. We show that the natural combination of ID-KEMs or CL-KEMs with data encapsulation mechanisms results in encryption schemes which are secure in a strong sense. In addition, we give generic constructions of ID-KEMs and CL-KEMs, as well as specific instantiations, which are provably secure.

We derive some tight equivalence reductions between several Strong Diffie-Hellman (SDH) assumptions.

A deniable authentication scheme using RSA is described and proven secure in the random oracle model. A countermeasure to a well-known attack on efficient deniable authentication to multiple recipients is describe and proven secure.

Based on the Chinese Remainder Theorem (CRT), Quisquater and Couvreur proposed an RSA variant, RSA-CRT, to speedup RSA decryption. According to RSA-CRT, Wiener suggested another RSA variant, Rebalanced RSA-CRT, to further speedup RSA-CRT decryption by shifting decryption cost to encryption cost. However, such an approach will make RSA encryption very time-consuming because the public exponent e in Rebalanced RSA-CRT will be of the same order of magnitude as £p(N). In this paper we study the following problem: does there exist any secure variant of Rebalanced RSA-CRT, whose public exponent e is much shorter than £p(N)? We solve this problem by designing a variant of Rebalanced RSA-CRT with d_{p} and d_{q} of 198 bits. This variant has the public exponent e=2^511+1 such that its encryption is about 3 times faster than that of the original Rebalanced RSA-CRT.

In this paper, we first introduce a new kind of adversarial goal called {\em forge-and-impersonate} in undeniable signature schemes. Note that forgeability does not necessarily imply impersonation ability. We then classify the security of the FDH variant of Chaum's undeniable signature scheme according to three dimensions, the goal of adversaries, the attacks and the ZK level of confirmation and disavowal protocols. We finally relate each security to some well-known computational problem. In particular, we prove that the security of the FDH variant of Chaum's scheme with NIZK confirmation and disavowal protocols is equivalent to the CDH problem, as opposed to the GDH problem as claimed by Okamoto and Pointcheval.

Much of today's distributed computing takes place in a client/server model. Despite advances in fault tolerance -- in particular, replication and load distribution -- server overload remains to be a major problem. In the Web context, one of the main overload factors is the direct consequence of expensive Public Key operations performed by servers as part of each SSL handshake. Since most SSL-enabled servers use RSA, the burden of performing many costly decryption operations can be very detrimental to server performance. This paper examines a promising technique for re-balancing RSA-based client/server handshakes. This technique facilitates more favorable load distribution by requiring clients to perform more work (as part of encryption) and servers to perform commensurately less work, thus resulting in better SSL throughput. Proposed techniques are based on careful adaptation of variants of Server-Aided RSA originally constructed by Matsumoto, et al. Experimental results demonstrate that suggested methods (termed Client-Aided RSA) can speed up processing by a factor of between 11 to 19, depending on the RSA key size. This represents a considerable improvement. Furthermore, proposed techniques can be a useful companion tool for SSL Client Puzzles in defense against DoS and DDoS attacks.

Pairing-based cryptosystems depend on the existence of groups where the Decision Diffie-Hellman problem is easy to solve, but the Computational Diffie-Hellman problem is hard. Such is the case of elliptic curve groups whose embedding degree is large enough to maintain a good security level, but small enough for arithmetic operations to be feasible. However, the embedding degree is usually enormous, and the scarce previously known suitable elliptic groups had embedding degree $k \leqslant 6$. In this note, we examine criteria for curves with larger $k$ that generalize prior work by Miyaji et al. based on the properties of cyclotomic polynomials, and propose efficient representations for the underlying algebraic structures.

We present, for the first time, an algorithm to choose parameter sets for NTRUEncrypt that give a desired level of security. Note: This is an expanded version of a paper presented at CT-RSA 2005.

We show how to recover the affine parts of the secret key for a certain class of HFE-Cryptosystems. Further we will show that any system build on branches can be decomposed in its single branches in polynomial time on average. The first part generalizes the result from \cite{geisel} to a bigger class of systems and is achieved by a different approach. Dispite the fact that systems with branches are not used anymore (see \cite{patarin1, goubin}), our second result is a still of interest as it applies to a very general class of HFE-cryptosystems and thus is a contribution to the list of algebraic properties, which cannot be hidden by composition with the secret affine transformations. We derived both algorithms by considering the cryptosystem as objects from the theory of nonassociative algebras and applying classical techniques from this theory. This general framework might be useful for future investigations of HFE-Cryptosysstems or to generalize other attacks known so far.

In many situations we want to enjoy confidentiality, authenticity and non-repudiation of message simultaneously. One approach to achieve this objective is to "sign-then-encrypt" the message, or we can employ special cryptographic scheme like signcryption. Two open problems about identity-based (ID-based) signcryption were proposed in \cite{CryptoePrint:2003:023}. The first one is to devise an efficient forward-secure signcryption scheme with public verifiability and public ciphertext authenticity, which is promptly closed by \cite{LNCS2971:ICISC2003:CYHC}. Another one which still remains open is to devise a hierarchical ID-based signcryption scheme that allows the user to receive signcrypted messages from sender who is under another sub-tree of the hierarchy. This paper aims at solving this problem by proposing two concrete constructions of hierarchical ID-based signcryption.

A ring signature scheme can be viewed as a group signature scheme with no anonymity revocation and with simple group setup. A \emph{linkable} ring signature (LRS) scheme additionally allows anyone to determine if two ring signatures have been signed by the same group member. Recently, Dodis et al. \cite{DKNS04} gave a short (constant-sized) ring signature scheme. We extend it to the first short LRS scheme, and reduce its security to a new hardness assumption, the Link Decisional RSA (LD-RSA) Assumption. We also extend \cite{DKNS04}'s other schemes to a generic LRS scheme and a generic linkable group signature scheme. We discuss three applications of our schemes. Kiayias and Yung \cite{KY04} constructed the first e-voting scheme which simultaneously achieves efficient tallying, public verifiability, and write-in capability for a typical voter distribution under which only a small portion writes in. We construct an e-voting scheme based on our short LRS scheme which achieves the same even for all worst-case voter distribution. Direct Anonymous Attestation (DAA) \cite{BCC04} is essentially a ring signature scheme with certain linking properties that can be naturally implemented using LRS schemes. The construction of an offline anonymous e-cash scheme using LRS schemes is also discussed.

Verifiable Pairing and its Applications. In Chae Hoon Lim and Moti Yung, editors, Information Security Applications: 5th International Workshop, WISA 2004, Jeju Island, Korea, August 23-25, 2004, Revised Selected Papers, volume 3325 of Lecture Notes in Computer Science, pp. 170-187. (http://www.springerlink.com/index/C4QB7C13NL0EY5VN) which contains an improved and generalized result of this paper.

The group of m-torsion points on an elliptic curve, for a prime number m, forms a two-dimensional vector space. It was suggested and proven by Yoshida that under certain conditions the vector decomposition problem (VDP) on a two-dimensional vector space is at least as hard as the computational Diffie-Hellman problem (CDHP) on a one-dimensional subspace. In this work we show that even though this assessment is true, it applies to the VDP for m-torsion points on an elliptic curve only if the curve is supersingular. But in that case the CDHP on the one-dimensional subspace has a known sub-exponential solution. Furthermore, we present a family of hyperelliptic curves of genus two that are suitable for the VDP.

This paper explores the idea of partially exposing sections of the private key in public-key cryptosystems whose security is based on the intractability of factorising large integers. It is proposed to allow significant portions of the private key to be publicly available, reducing the amount of data which must be securely hidden. The ``secret'' data could be XORed with an individual's biometric reading in order to maintain a high level of security, and we suggest using iris templates for this purpose. Finally, we propose an implementation of this system for RSA, and consider the potential risks and advantages associated with such a scheme.

In threshold ring signature schemes, any group of $t$ entities spontaneously conscripting arbitrarily $n-t$ entities to generate a publicly verifiable $t$-out-of-$n$ signature on behalf of the whole group, yet the actual signers remain anonymous. The spontaneity of these schemes is desirable for ad-hoc groups such as mobile ad-hoc networks. In this paper, we present an identity based (ID-based) threshold ring signature scheme. The scheme is provably secure in the random oracle model and provides trusted authority compatibility. To the best of authors' knowledge, our scheme is the first ID-based threshold ring signature scheme which is also the most efficient (in terms of number of pairing operations required) ID-based ring signature scheme (when $t = 1$) and threshold ring signature scheme from pairings.

In this paper, we present a new class of public-key cryptosystem (PKC) using algebraic coding on the basis of superimposition and randomness. The proposed PKC is featured by a generator matrix, in a characteristic form, where the generator matrix of an algebraic code is repeatedly used along with the generator matrix of a random code, as sub-matrices. This generator matrix, in the characteristic form, will be referred to as $K$-matrix. We show that the $K$-matrix yields the following advantages compared with the conventional schemes: \begin{description} \item [(i)] It realizes an abundant supply of PKCs, yielding more secure PKCs. \item [(i\hspace{-.1em}i)] It realizes a fast encryption and decryption process. \end{description}

In this article, we show that public key schemes based on multivariate quadratic equations allow many equivalent, and hence superfluous private keys. We achieve this result by investigating several transformations to identify these keys and show their application to Hidden Field Equations (HFE), C$^*$, and Unbalanced Oil and Vinegar schemes (UOV). In all cases, we are able to reduce the size of the private --- and hence the public --- key space by at least one order of magnitude. We see applications of our technique both in cryptanalysis of these schemes and in memory efficient implementations.

The present survey deals with the recent research in side channel analysis and related attacks on implementations of cryptographic primitives. The focus is on software contermeasures for primitives built around algebraic groups. Many countermeasures are described, together with their extent of applicability, and their weaknesses. Some suggestions are made, conclusion are drawn, some directions for future research are given. An extensive bibliography on recent developments concludes the survey.

In this paper, we present a chosen ciphertext attack against a public key cryptosysten based on Lyndon words \cite{sm}. We show that, provided that an adversary has access to a decryption oracle, a key equivalent to the secret key can be constructed efficiently, i.e. in linear time.

SFLASH-v2 is one of the three asymmetric signature schemes recommended by the European consortium for low-cost smart cards. The latest implementation report published at PKC 2003 shows that SFLASH-v2 is the fastest signature scheme known. This is a detailed specification of SFLASH-v3 produced in 2003 for fear of v2 being broken. HOWEVER after detailed analysis by Chen Courtois and Yang [ICICS04], Sflash-v2 is not broken and we still recommend the previous version Sflash-v2, already recommended by Nessie, instead of this version.