In a (t, n) proxy signature scheme, the original signer can delegate his/her signing capability to n proxy signers such that any t or more proxy singers can sign messages on behalf of the former, but t-1 or less of them cannot do the same thing. Such schemes have been suggested for use in a number of applications, particularly in distributed computing where delegation of rights is quite common. Based on the RSA cryptosystem, Hwang et al. recently proposed an efficient (t, n) threshold proxy signature scheme. In this paper we identify several security weaknesses in their scheme and show that their scheme is insecure.

The notion of key privacy for encryption schemes was defined formally by Bellare, Boldyreva, Desai and Pointcheval in Asiacrypt 2001. This notion seems useful in settings where anonymity is important. In this short note we describe a (very simple) sufficient condition for key privacy. In a nutshell, a scheme that provides data privacy is guaranteed to provide also key privacy if the distribution of a *random encryption of a random message* is independent of the public key that is used for the encryption.

The conjugacy search problem in a group $G$ is the problem of recovering an $x \in G$ from given $g \in G$ and $h=x^{-1}gx$. This problem is in the core of several recently suggested public key exchange protocols, most notably the one due to Anshel, Anshel, and Goldfeld, and the one due to Ko, Lee at al. In this note, we make two observations that seem to have eluded most people's attention. The first observation is that solving the conjugacy search problem is not necessary for an adversary to get the common secret key in the Ko-Lee protocol. It is sufficient to solve an apparently easier problem of finding $x, y \in G$ such that $h=ygx$ for given $g, h \in G$. Another observation is that solving the conjugacy search problem is not sufficient for an adversary to get the common secret key in the Anshel-Anshel-Goldfeld protocol.

We propose a new concept, named piece in hand, which can be applicable to a wide class of multivariate type public key cryptosystems to enhance their security. The piece in hand provides such cryptosystems with a new type of trapdoor which is compatible with the trapdoor originally equipped in them. The piece in hand concept is based on a new paradigm for public key cryptosystem in general. On the one hand, in most traditional public key cryptosystems such as the RSA and ElGamal schemes, the public key contains all the information of the secret key. On the other hand, in our scheme, the piece in hand, which is a part of the secret key, is not contained in the public key but is taken from outside of the public key to plug in during the decryption. In this paper, we illustrate how to apply the piece in hand concept to enhance the security of multivariate type public key cryptosystems, by presenting the general theory for the use of the concept.

Miyaji, Nakabayashi and Takano (MNT) gave families of group orders of ordinary elliptic curves with embedding degree suitable for pairing applications. In this paper we generalise their results by giving families corresponding to non-prime group orders. We also consider the case of ordinary abelian varieties of dimension 2. We give families of group orders with embedding degrees 5, 10 and 12.

Recently Landau and Diffie gave in a series of articles in the Notices of the American Mathematical Society and in the American Mathematical Monthly excellent expositions on how the theory of multivariable polynomials are used in cryptography. However they covered only half of the story. They covered only the theory of polynomials in symmetric or secret cryptography. There is another half of the story, namely the story about the theory of multivariable polynomials in asymmetric or public key cryptosystems. We give an overview of the families of public key cryptosystems, which have been developed in the last ten years.

We introduce the concept of Modified Parameter Attacks, a natural extension of the idea of Adapative Chosen Ciphertext Attacks (CCA2) under which some CCA2 secure systems can be shown to be insecure. These insecurities can be addressed at the application level, but can also be addressed when cryptographic schemes are being designed. We survey some existing CCA2 secure systems which are vulnerable to this attack and suggest practical countermeasures.

We construct two efficient Identity Based Encryption (IBE) systems that are selective identity secure {\em without the random oracle model} in groups equipped with a bilinear map. Selective identity secure IBE is a slightly weaker security model than the standard security model for IBE. In this model the adversary must commit ahead of time to the identity that it intends to attack, whereas in the standard model the adversary is allowed to choose this identity adaptively. The first system is based on the decisional bilinear Diffie-Hellman assumption, and extends to give a selective identity Hierarchical IBE secure without random oracles. The second system is based on a related assumption called the bilinear Diffie-Hellman inversion assumption. Applications of either system include an efficient CCA2 public key cryptosystem that supports non-interactive threshold decryption in the standard model, and a simple and practical IBE system that remains secure against full adaptive-ID attacks, under some security penalty, without random oracles.

We present a closed formula for the Tate pairing computation for supersingular elliptic curves defined over the binary field F_{2^m} of odd dimension. There are exactly three isomorphism classes of supersingular elliptic curves over F_{2^m} for odd m and our result is applicable to all these curves. Moreover we show that our algorithm and also the Duursma-Lee algorithm can be modified to another algorithm which does not need any inverse Frobenius operation (square root or cube root extractions) without sacrificing any of the computational merits of the original algorithm. Since the computation of the inverse Frobenius map is not at all trivial in a polynomial basis and since a polynomial basis is still a preferred choice for the Tate pairing computation in many situations, this new algorithm avoiding the inverse Frobenius operation has some advantage over the existing algorithms.

Several signcryption schemes proposed in the literature are known to lack semantic security, and semantically secure signcryption schemes tend to be more computationally expensive. In fact, devising an efficient signcryption scheme providing both public verifiability and forward security was until now an open problem. In this paper, we show how a particular kind of signcryption scheme may become completely insecure when implemented with certain efficient instantiations of the Tate or Weil pairing. We also address the drawbacks of the secure schemes by proposing efficient, semantically and forward-secure signcryption schemes, in both transferable and non-transferable form, that can be realised on top of any pairing instantiation. As a bonus, we also derive from them a new, efficient identity-based signature scheme.

A ring signature scheme is a group signature scheme with no group manager to setup a group or revoke a signer. A linkable ring signature, introduced by Liu, et al. \cite{LWW04}, additionally allows anyone to determine if two ring signatures are signed by the same group member (a.k.a. they are \emph{linked}). In this paper, we present the first separable linkable ring signature scheme, which also supports an efficient thresholding option. We also present the security model and reduce the security of our scheme to well-known hardness assumptions. In particular, we introduce the security notions of {\em accusatory linkability} and {\em non-slanderability} to linkable ring signatures. Our scheme supports ``event-oriented'' linking. Applications to such linking criterion is discussed.

Proxy signature is an important cryptographic primitive and has been suggested in numerous applications. In this paper, we present an attack on the aggregate-signature-based proxy signature schemes, then point out there are two flaws in BPW notion of security for proxy signature. Furthermore, we give arguments for partial delegation with warrant proxy signature schemes. We construct a new proxy signature scheme and prove that it is secure against existentially forgery on adaptively chosen-message attacks and adaptively chosen-warrant attacks under the random oracle model.

Digital signatures have become a key technology for making the Internet and other IT infrastructures secure. But in 1994 Peter Shor showed that quantum computers can break all digital signature schemes that are used today and in 2001 Chuang and his coworkers implemented Shor s algorithm for the first time on a 7-qubit NMR quantum computer. This paper studies the question: What kind of digital signature algorithms are still secure in the age of quantum computers?

We herein discuss two modes of attack on multivariate public-key cryptosystems. A 2000 Goubin-Courtois article applied these techniques against a special class of multivariate PKC's called ``Triangular-Plus-Minus'' (TPM), and may explain in part the present dearth of research on ``true'' multivariates -- multivariate PKC's in which the middle map is not really taken in a much larger field. These attacks operate by finding linear combinations of matrices with a given rank. Indeed, we can describe the two attacks very aptly as ``high-rank'' and ``low-rank''. However, TPM was not general enough to cover all pertinent true multivariate PKC's. \emph{Tame-like} PKC's, multivariates with relatively few terms per equation in the central map and an easy inverse, is a superset of TPM that can enjoy both fast private maps and short set-up times. However, inattention can still let rank attacks succeed in tame-like PKCs. The TTS (Tame Transformation Signatures) family of digital signature schemes lies at this cusp of contention. Previous TTS instances (proposed at ICISC '03) claim good resistance to other known attacks. But we show how careless construction in current TTS instances (TTS/4 and TTS/$2'$) exacerbates the security concern of rank, and show two different cryptanalysis in under $2^{57}$ AES units. TTS is not the only tame-like PKC with these liabilities -- they are shared by a few other misconstructed schemes. A suitable equilibrium between speed and security must be struck. We suggest a generic way to craft tame-like PKC's more resistant to rank attacks. A demonstrative TTS variant with similar dimensions is built for which rank attack takes $>2^{80}$ AES units, while remaining very fast and as resistant to other attacks. The proposed TTS variants can scale up. In short: We show that rank attacks apply to the wider class of tame-like PKC's, sometimes even better than previously described. However, this is relativized by the realization that we can build adequately resistant tame-like multivariate PKC's, so the general theme still seem viable compared to more traditional or large-field multivariate alternatives.

Based on ideas in an earlier paper by Mark Bauer, Edlyn Teske and myself and ideas of Pierrick Gaudry and Eric Schost, we present an algorithm for counting the number of elements in the Jacobian of a random Picard curve over a finite prime field of cryptosize. We give two examples of curves with a Jacobian of prime group order.

Current side-channel analytic attacks against public key cryptography focus on traditional schemes such as RSA and ECC, and to a lesser extent primitives such as XTR. However, bilinear maps, or pairings, have presented theorists with a new and increasingly popular way of constructing cryptographic protocols. Most notably, this has resulted in efficient methods for Identity Based Encryption (IBE). Since identity based cryptography seems an ideal partner for identity aware devices such as smart-cards, in this paper we examine the security of concrete pairing instantiations in terms of side-channel analysis.

Recently, Canetti, Halevi, and Katz showed a general method for constructing CCA-secure encryption schemes from identity-based encryption schemes in the standard model. We improve the efficiency of their construction, and show two specific instantiations of our resulting scheme which offer the most efficient encryption (and, in one case, key generation) of any CCA-secure encryption scheme to date.

This paper introduces a new radix-2 representation with the same average weight as the width-$w$ nonadjacent form ($w$-NAF). In both $w$-NAF and the proposed representations, each nonzero digit is an odd integer with absolute value less than $M$. However, for $w$-NAF, $M$ is of the form $2^{w-1}$, while for the proposed representation it can be any positive integer. Therefore, using the proposed integer representation we can use the available memory efficiently, which is attractive for devices with limited memory. Another advantage of the proposed representation over $w$-NAF is that it can be obtained by scanning the bits from left-to-right. This property is also useful for memory-constrained devices because it can reduce both time and space complexityof fast point multiplication techniques.

Identity-based (ID-based) public key cryptosystem can be a good alternative for certificate-based public key setting, especially when efficient key management and moderate security are required. In a $(t,n)$ threshold proxy signature scheme, the original signer delegates the power of signing messages to a designated proxy group of $n$ members. Any $t$ or more proxy signers of the group can cooperatively issue a proxy signature on behalf of the original signer, but $t-1$ or less proxy signers cannot. In this paper, we present an ID-based threshold proxy signature scheme using bilinear pairings. We show the scheme satisfies all security requirements in the random oracle model. To the best of authors' knowledge, our scheme is the first ID-based threshold proxy signature scheme.

This paper shows that many of elliptic curve cryptosystems over quartic extension fields of odd characteristics are reduced to genus two hyperelliptic curve cryptosystems over quadratic extension fields. Moreover, it shows that almost all of the genus two hyperelliptic curve cryptosystems over quadratic extension fields of odd characteristics come under Weil descent attack. This means that many of elliptic curve cryptosystems over quartic extension fields of odd characteristics can be attacked by Weil descent uniformly.

We present a new type of fault attacks on elliptic curve scalar multiplications: Sign Change Attacks. These attacks exploit different number representations as they are often employed in modern cryptographic applications. Previously, fault attacks on elliptic curves aimed to force a device to output points which are on a cryptographically weak curve. Such attacks can easily be defended against. Our attack produces points which do not leave the curve and are not easily detected. The paper also presents a revised scalar multiplication algorithm that provably protects against Sign Change Attacks.

This paper proposes a new scheme for partially blind signature based on the difficulty in solving the discrete logarithm problem. Under the assumption of the generic model, random oracle model, and intractable ROS-problem, this paper formally proves that the proposed scheme is secure against one-more signature forgery under the adaptively parallel attack. Previous schemes using two signing equations for plain information and commitment. The proposed scheme uses two secret keys to combine these two signing equations, thus it is more efficient than previous schemes in both communicational and computational cost.

We propose a new security class, called plaintext-simulatability, defined over the public-key encryption schemes. The notion of plaintext simulatability (denoted PS) is similar to the notion of plaintext awareness (denoted PA), but it is, ``properly'', a weaker security class for public-key encryption. In most cases, PA is ``unnecessarily'' strong, --- only used to prove that a public-key encryption scheme is CCA2-secure, because it looks much easier than to prove ``directly'' that the scheme meets IND-CCA2. We show that PS also implies IND-CCA2, while preserving a good view of the security proofs as well as PA. PS looks ``properly'' stronger than IND-CCA2. So far, however, it is not sure how to prove this, which remains open.

We construct a short group signature scheme. Signatures in our scheme are approximately the size of a standard RSA signature with the same security. Security of our group signature is based on the Strong Diffie-Hellman assumption and a new assumption in bilinear groups called the Decision Linear assumption. We prove security of our system, in the random oracle model, using a variant of the security definition for group signatures recently given by Bellare, Micciancio, and Warinschi.

This paper revisits a public key cryptosystem which is based on finite Church-Rosser string-rewriting systems. We consider some ideas for cryptanalysis and discuss issues concerning practical usage. It turns out that without changing crucial details of key generation this cryptosystem does not offer acceptable cryptographic security. We also provide the source code of our rudimentary implementation, if someone would like to use it for further cryptanalysis.

Recently, Augot and Finiasz presented a coding theoretic public key cryptosystem that suggests a new approach for designing such systems based on the Polynomial Reconstruction Problem. Their cryptosystem is an instantiation of this approach under a specific choice of parameters which, given the state of the art of coding theory, we show in this work to be sub-optimal. Coron showed how to attack the Augot and Finiasz cryptosystem. A question left open is whether the general approach suggested by the cryptosystem works or not. In this work, we show that the general approach (rather than only the instantiation) is broken as well. Our attack employs the recent powerful list-decoding mechanisms.

It is already known that the Weil and Tate pairings can be used to solve many decision-Diffie-Hellman (DDH) problems on elliptic curves. A natural question is whether all DDH problems are easy on supersingular curves. To answer this question it is necessary to have suitable distortion maps. Verheul states that such maps exist, and this paper gives methods to construct them. The paper therefore shows that all DDH problems on supersingular elliptic curves are easy. We also discuss the issue of which DDH problems on ordinary curves are easy. A related contribution is a discussion of distortion maps which are not isomorphisms. We give explicit distortion maps for elliptic curves with complex multiplication of discriminants $D=-7$ and $D=-8$.

A forward-secure encryption scheme protects secret keys from exposure by evolving the keys with time. Forward security has several unique requirements in Hierarchical Identity-Based Encryption (HIBE) scheme: (1) users join dynamically; (2) encryption is joining-time-oblivious; (3) users evolve secret keys autonomously. We present a scalable forward-secure HIBE scheme satisfying the above properties. Note that a naive combination of Gentry-Silverberg HIBE scheme with the forward-secure Public-Key Encryption scheme by Canetti, Halevi and Katz would not meet the requirements. We also show how our fs-HIBE scheme can be used to construct a forward-secure public-key Broadcast Encryption scheme, which protects the secrecy of prior transmissions in the Broadcast Encryption setting. We further generalize fs-HIBE into a collusion-resistant Multiple Hierarchical ID-Based Encryption scheme, which can be used for secure communications with entities having multiple roles in Role-Based Access Control. The security of our schemes is based on the Bilinear Diffie-Hellman assumption in the random oracle model.

Recently, Chang \textit{et al}. \cite{Chang} proposed a new digital signature scheme with message recovery and claimed that neither one-way hash functions nor message redundancy schemes were employed in their scheme. However, in this letter, two forgery attacks are proposed to show that Chang \textit{et al.}'s signature scheme is not secure. To resist these attacks, the message redundancy schemes may be still used.

We report experiments on the security of the GGH-like cryptosystem proposed by Micciancio. Based on these experiments, we conclude that the system can be securely used only in lattice dimensions > 781. Further experiments on the efficiency of the system show that it requires key sizes of 1 MByte and more and that the key generation as well as the decryption take inacceptibly long. Therefore, Micciancio's cryptosystem seems currently far from being practical.

We address one of the most fundamental problems concerning the RSA cryptosystem: does the knowledge of the RSA public and secret key-pair (e,d) yield the factorization of N=pq in polynomial time? It is well-known that there is a probabilistic polynomial time algorithm that on input (N,e,d) outputs the factors p and q. We present the first deterministic polynomial time algorithm that factors N provided that e,d<N. Our approach is an application of Coppersmith's technique for finding small roots of univariate modular polynomials.

In this paper, we present a new parallel architecture to avoid side-channel analyses such as: timing attack, simple/differential power analysis, fault induction attack and simple/differential electromagnetic analysis. We use a Montgomery Multiplication based on Residue Number Systems. Thanks to RNS, we develop a design able to perform an RSA signature in parallel on a set of identical and independent coprocessors. Of independent interest, we propose a new DPA countermeasure in the framework of RNS. It is only (slightly) memory consuming (1.5 KBytes). Finally, we synthesized our new architecture on FPGA and it presents promising performance results. Even if our aim is to sketch a secure architecture, the RSA signature is performed in less than 160 ms, with competitive hardware resources. To our knowledge, this is the first proposal of an architecture counteracting electromagnetic analysis apart from hardware countermeasures reducing electromagnetic radiations.

In this paper, we present two forward secure signature schemes based on gap Diffie-Hellman groups and prove these schemes to be secure in the sense of slightly stronger security notion than that by Bellare and Miner in the random oracle model. Both schemes use the same key update strategy as the encryption scheme presented by Canetti, Halevi and Katz. Hence, our schemes outperform the previous tree-based forward secure signature scheme by Bellare and Miner in the key generation and key update time, which are only constant in the number of time periods. Specifically, we describe a straightforward scheme following from the encryption scheme, and then improve its efficiency for signature verification algorithm which needs only 3 pairing computations independent of the total time periods.

We describe an identity based signature scheme that uses biometric information to construct the public key. Such a scheme would be beneficial in a legal dispute over whether a contract had been signed or not by a user. A biometric reading provided by the alleged signer would be enough to verify the signature. We make use of Fuzzy extractors to generate a key string from a biometric measurement. We use this biometric based key string and an elliptic curve point embedding technique to create the public key and corresponding private key. We then make use of a pairing based signature scheme to perform signing and verification with these keys. We describe a possible attack on this system and suggest ways to combat it. Finally we describe how such a biometric signature scheme can be developed by reusing existing components in our Java Identity Based Encryption implementation. The design allows traditional as well as biometric identity based signatures.

We present a fully secure identity based encryption scheme whose proof of security does not rely on the random oracle heuristic. Security is based on the decisional bilinear Diffie-Hellman assumption. Previous constructions of this type incurred a large penalty factor in the security reduction from the underlying complexity assumption. The security reduction of the present system is polynomial in all the parameters.

We describe a 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 {\em Strong Diffie-Hellman} assumption. This assumption has similar properties to the Strong RSA assumption, hence the name. Strong RSA was previously used to construct signature schemes without random oracles. However, signatures generated by our scheme are much shorter and simpler than signatures from schemes based on Strong RSA. Furthermore, our scheme provides a limited form of message recovery.

Computing the order of the Jacobian group of a hyperelliptic curve over a finite field is very important to construct a hyperelliptic curve cryptosystem (HCC), because to construct secure HCC, we need Jacobian groups of order in the form $l(J\(Bcdot c$ where $l$ is a prime greater than about $2^{160}$ and $c$ is a very small integer. But even in the case of genus two, known algorithms to compute the order of a Jacobian group for a general curve need a very long running time over a large prime field. In the case of genus three, only a few examples of suitable curves for HCC are known. In the case of genus four, no example has been known over a large prime field. In this article, we give explicit formulae of the order of Jacobian groups for hyperelliptic curves over a finite prime field of type $y^2=x^{2k+1}+a x$, which allows us to search suitable curves for HCC. By using these formulae, we can find many suitable curves for genus-4 HCC and show some examples.

Gaudry present a variation of index calculus attack for solving the DLP in the Jacobian of hyperelliptic curves. Harley and Thériault improve these kind of algorithm. Here, we will present a variation of these kind of algorithm, which is faster than previous ones. Its complexity is $O(2-\frac{2}{g}+\epsilon)$. Recently, P. Gaudry and E. Thomé http://eprint.iacr.org/2004/153/ present the algorithm, whose complexity is same as our results. So I submit my manuscript to this eprint archive.

In this paper, we first show that previous proxy signature schemes by delegation with certificate are not provably secure under adaptive-chosen message attacks and adaptive-chosen warrant attacks. The schemes do not provide the strong undeniability. Then we construct a proxy signature scheme by delegation with certificate based on Co-GDH group from bilinear map. Our proxy signature scheme is existentially unforgeable against adaptive-chosen message attacks and adaptive-chosen warrant attacks in random oracle model. We adopt a straight method of security reduction in which our scheme's security is reduced to hardness of the computational co-Diffie-Hellem problem. The proposed signature scheme is the first secure delegation-by-certificate proxy signature based on co-GDH groups from bilinear maps under the formal security model in random oracle model.

This paper analyzes a key recovery method for RSA signature generation or decryption implementations using the Chinese Remainder Theorem (CRT) speed up. The CRT-based RSA implementation is common in both low computing power devices and high speed cryptographic acceleration cards. This recovery method is designed to work in conjunction with a side-channel attack where the CRT exponents are discovered from a message decryption or signature generation operation, the public exponent is assumed small and the public modulus is unknown. Since many RSA implementations use the small, low hamming weight public exponent 65537 this turns out to be a realistic method. An algorithm for recovering the private key, modulus and prime factorization candidates is presented with a proof of correctness. Runtime estimates and sample source code is given.

An aggregate signature scheme (recently proposed by Boneh, Gentry, Lynn and Shacham) is a method for combining $n$ signatures from $n$ different signers on $n$ different messages into one signature of unit length. We propose \emph{sequential aggregate signatures}, in which the set of signers is ordered. The aggregate signature is computed by having each signer, in turn, add his signature to it. We show how to realize this in such a way that the size of the aggregate signature is independent of $n$. This makes sequential aggregate signatures a natural primitive for certificate chains, whose length can be reduced by aggregating all signatures in a chain. We give a construction based on families of certified trapdoor permutations, and show how to instantiate our scheme based on RSA.

Many problems have been solved by protocols using discrete-logarithm based threshold cryptosystems. Such protocols require a random joint public key for which the secret key is shared among the parties. A multiparty protocol that generates such a key is called a DKG protocol. Until now no DKG protocol is known to be universally composable. We extend Feldman's original verifiable secret sharing scheme to construct a DKG protocol, and prove that it is universally composable. Our result holds in a common random string model under the Decision Diffie-Hellman assumption. We stress that we do not need any trapdoor for the common random string. Our protocol is optimistic. If all parties behave honestly, each party computes only $O(3k)$ exponentiations, where $k$ is the number of parties. In the worst case each party computes $O(k^2)$ exponentiations. This should be contrasted with previous constructions in which each party computes $\Omega(k^2)$ exponentiations regardless of if they behave honestly or not. In the optimistic case the number of bits sent in our protocol is essentially equal to the number of bits sent in $k$ independent copies of Feldman's original protocol.

We present a fast addition algorithm in the Jacobian of a genus $3$ non-hyperelliptic curve over a field of any characteristic. When the curve has a rational flex and $\textrm{char}(k) > 5$, the computational cost for addition is $148M+15SQ+2I$ and $165M+20SQ+2I$ for doubling. An appendix focuses on the computation of flexes in all characteristics. For large odd $q$, we also show that the set of rational points of a non-hyperelliptic curve of genus $3$ can not be an arc.

Hidden credentials are useful in protecting sensitive resource requests, resources, policies and credentials. We propose a significant improvement in decryption performance when implementing hidden credentials using the Franklin/Boneh IBE. We also propose a substantially improved secret splitting scheme for enforcing complex policies, and show how it improves concealment of policies from nonsatisfying recipients.

To obtain efficient cryptosystems based on hyperelliptic curves, we studied genus 2 isomorphism classes of hyperelliptic curves in characteristic 2. We found general and optimal form for these curves, just as the short Weierstrass form for elliptic curves. We studied the security and the arithmetic on their jacobian. We also rewrote and optimized the formulas of Lange in characteristic 2, and we introduced a new system of coordinate. Therefore, we deduced the best form of hyperelliptic curves of genus 2 in characteristic 2 to use in cryptography.

Sflash is a fast multivariate signature scheme. Though the first version Sflash-v1 was flawed, a second version, Sflash-v2 was selected by the Nessie Consortium and was recommended for implementation of low-end smart cards. Very recently, due to the security concern, the designer of Sflash recommended that Sflash-v2 should not be used, instead a new version Sflash-v3 is proposed, which essentially only increases the length of the signature. The Sflash family of signature schemes is a variant of the Matsumoto and Imai public key cryptosystem. The modification is through the Minus method, namely given a set of polynomial equations, one takes out a few of them to make them much more difficult to solve. In this paper, we attack the Sflash-v3 scheme by combining an idea from the relinearization method by Kipnis and Shamir, which was used to attack the Hidden Field Equation schemes, and the linearization method by Patarin. We show that the attack complexity is less than 2^80, the security standard required by the Nessie Consortium.

Chameleon hash function is a trapdoor one-way hash function. The ID-based chameleon hash function was first introduced by Ateniese and Medeiros \cite{AM03}. As discussed by \cite{AM03}, the general advantages of ID-based cryptography over conventional cryptography with respect to key distribution are even more pronounced in a chameleon hashing scheme, because the owner of a public key does not necessarily need to retrieve the associated secret key. In this paper, we propose two new ID-based Chameleon hashing schemes from bilinear pairings. Also we analyze their security and efficiency. Based on these ID-based chameleon hashes, ID-based chameleon signature schemes can be designed.

We point out several security flaws in the cryptosystem based on tree replacement systems proposed by Samuel, Thomas, Abisha and Subramanian at INDOCRYPT 2002. Due to the success of (among others) very simple ciphertext-only attacks, we evidence that this system does not, in its present form, offer acceptable security guarantees for cryptographic applications.

At Eurocrypt'91, Chaum and van Heyst introduced the concept of group signature. In such a scheme, each group member is allowed to sign messages on behalf of a group anonymously. However, in case of later disputes, a designated group manager can open a group signature and identify the signer. In recent years, researchers have proposed a number of new group signature schemes and improvements with different levels of security. In this paper, we present a security analysis of five group signature schemes proposed in [25,27,18,30,10]. By using the same method, we successfully identify several universally forging attacks on these schemes. In our attacks, anyone (not necessarily a group member) can forge valid group signatures on any messages such that the forged signatures cannot be opened by the group manager. We also discuss the linkability of these schemes, and further explain why and how we find the attacks.

A group signature scheme allows a group member of a given group to sign messages on behalf of the group in an anonymous and unlinkable way. In case of a dispute, however, a designated group manager can reveal the signer of a valid group signature. Based on Song's forward-secure group signature schemes, Zhang, Wu, and Wang proposed a new group signature scheme with forward security at ICICS 2003. Their scheme is very efficient in both communication and computation aspects. Unfortunately, their scheme is insecure. In this paper we present a security analysis to show that their scheme is linkable, untraceable, and forgeable.

A proxy signature scheme allows an entity to delegate his/her signing capability to another entity in such a way that the latter can sign messages on behalf of the former. Such schemes have been suggested for use in a number of applications, particularly in distributed computing where delegation of rights is quite common. Followed by the first schemes introduced by Mambo, Usuda and Okamoto in 1996, a number of new schemes and improvements have been proposed. In this paper, we present a security analysis of four such schemes newly proposed in [15,16]. By successfully identifying several interesting forgery attacks, we show that all the four schemes are insecure. Consequently, the fully distributed proxy scheme in [11] is also insecure since it is based on the (insecure) LKK scheme [14,15]. In addition, we point out the reasons why the security proofs provided in [15] are invalid.

This paper gives a survey of some ways to improve the efficiency of discrete log-based cryptography by using the restriction of scalars and the geometry and arithmetic of algebraic tori and abelian varieties.

We study the problem of searching on data that is encrypted using a public key system. Consider user Bob who sends email to user Alice encrypted under Alice's public key. An email gateway wants to test whether the email contains the keyword `urgent' so that it could route the email accordingly. Alice, on the other hand does not wish to give the gateway the ability to decrypt all her messages. We define and construct a mechanism that enables Alice to provide a key to the gateway that enables the gateway to test whether the word `urgent' is a keyword in the email without learning anything else about the email. We refer to this mechanism as <I>Public Key Encryption with keyword Search</I>. As another example, consider a mail server that stores various messages publicly encrypted for Alice by others. Using our mechanism Alice can send the mail server a key that will enable the server to identify all messages containing some specific keyword, but learn nothing else. We define the concept of public key encryption with keyword search and give several constructions.

In their seminal paper, Miyaji, Nakabayashi and Takano~\cite{miyaji-nakabayashi-takano} describe a simple method for the creation of elliptic curves of prime order with embedding degree 3, 4, or 6. Such curves are important for the realisation of pairing-based cryptosystems on ordinary (non-supersingular) elliptic curves. We provide an alternative derivation of their results, and extend them to allow for the generation of many more suitable curves.

We propose an index calculus algorithm for the discrete logarithm problem on general abelian varieties. The main difference with the previous approaches is that we do not make use of any embedding into the Jacobian of a well-suited curve. We apply this algorithm to the Weil restriction of elliptic curves and hyperelliptic curves over small degree extension fields. In particular, our attack can solve all elliptic curve discrete logarithm problems defined over $GF(q^3)$ in time $O(q^{10/7})$, with a reasonably small constant; and an elliptic problem over $GF(q^4)$ or a genus 2 problem over $GF(p^2)$ in time $O(q^{14/9})$ with a larger constant.

We present a variant of the Boneh \& Franklin Identiy-based Encryption {\sc ibe} scheme to derive an authenticated symmetric key-exchange protocol, when combined with a signature scheme. Our protocol uses {\sc ibe} as a secure channel to establish a symmetric key between two users and, after that, further communication can be done by symmetric cryptography, much faster than pairing-based cryptography.

A combined Identity-Based Signature/Encryption system with multiple security properties is presented. The scheme allows Alice to sign a message and encrypt it for Bob ("confidentiality") in such a way that the ciphertext does not reveal anything about their identities ("anonymity"); upon receipt, Bob is convinced that he is Alice's intended addressee ("authentication") but is unable to prove this to a third party ("unlinkability"); nevertheless, the decrypted message bears a signature by Alice that anyone can verify ("non-repudiation"). The construction is based on the Bilinear Diffie-Hellman assumption, and proved secure in the random oracle model.

We study the problem of root extraction in finite Abelian groups, where the group order is unknown. This is a natural generalization of the problem of decrypting RSA ciphertexts. We study the complexity of this problem for generic algorithms, that is, algorithms that work for any group and do not use any special properties of the group at hand. We prove an exponential lower bound on the generic complexity of root extraction, even if the algorithm can choose the "public exponent" itself. In other words, both the standard and the strong RSA assumption are provably true w.r.t. generic algorithms. The results hold for arbitrary groups, so security w.r.t. generic attacks follows for any cryptographic construction based on root extracting. As an example of this, we revisit Cramer-Shoup signature scheme. We modify the scheme such that it becomes a generic algorithm. This allows us to implement it in RSA groups without the original restriction that the modulus must be a product of safe primes. It can also be implemented in class groups. In all cases, security follows from a well defined complexity assumption (the strong root assumption), without relying on random oracles, and the assumption is shown to be true w.r.t. generic attacks.

Committed Oblivious Transfer (COT) is a useful cryptographic primitive that combines the functionalities of bit commitment and oblivious transfer. In this paper, we introduce an extended version of COT (ECOT) which additionally allows proofs of relations among committed bits, and we construct an efficient protocol that securely realizes an ECOT functionality in the universal-composability (UC) framework in the common reference string (CRS) model. Our construction is more efficient than previous (non-UC) constructions of COT, involving only a constant number of exponentiations and communication rounds. Using the ECOT functionality as a building block, we construct efficient UC protocols for general two-party and multi-party functionalities (in the CRS model), each gate requiring a constant number of ECOT's.

Chameleon signatures are based on well established hash-and-sign paradigm, where a \emph{chameleon hash function} is used to compute the cryptographic message digest. Chameleon signatures simultaneously provide the properties of non-repudiation and non-transferability for the signed message, $i.e.,$ the designated recipient is capable of verifying the validity of the signature, but cannot disclose the contents of the signed information to convince any third party without the signer's consent. One disadvantage of the initial chameleon signature scheme is that signature forgery results in the signer recovering the recipient's trapdoor information, $i.e.,$ private key. Therefore, the signer can use this information to deny \emph{other} signatures given to the recipient. This creates a strong disincentive for the recipient to forge signatures, partially undermining the concept of non-transferability. In this paper, we firstly propose a chameleon hashing scheme in the gap Diffie-Hellman group to solve the problem of key exposure. We can prove that the recipient's trapdoor information will never be compromised under the assumption of Computation Diffie-Hellman Problem (CDHP) is intractable. Moreover, we use the proposed chameleon hashing scheme to design a chameleon signature scheme.

The aim of the paper is the construction of the index calculus algorithm for the discrete logarithm problem on elliptic curves. The construction presented here is based on the problem of finding bounded solutions to some explicit modular multivariate polynomial equations. These equations arise from the elliptic curve summation polynomials introduced here and may be computed easily. Roughly speaking, we show that given the algorithm for solving such equations, which works in polynomial or low exponential time in the size of the input, one finds discrete logarithms faster than by means of Pollard's methods.

Hyperelliptic curve cryptography recently received a lot of attention, especially for constrained environments. Since there space is critical, compression techniques are interesting. In this note we propose a new method which avoids factoring the first representing polynomial. In the case of genus two the cost for decompression is, essentially, computing two square roots in $\F_q$, the cost for compression is much less.

We build several highly-practical and optimized signcryption constructions directly from trapdoor permutations, in the random oracle model. All our constructions share features such as simplicity, efficiency, generality, near-optimal exact security, flexible and ad-hoc key management, key reuse for sending/receiving data, optimally-low message expansion, "backward" use for plain signature/encryption, long message and associated data support, the strongest-known qualitative security (so-called IND-CCA and sUF-CMA) and, finally, complete compatibility with the PKCS#1 infrastructure. While some of these features are present in previous works to various extents, we believe that our schemes improve on earlier proposals in at least several dimensions, making the overall difference quite noticeable in practice. Concretely, we present three methods generally based on what we call Parallel, Sequential, and eXtended sequential Padding schemes (P-Pad, S-Pad, X-Pad). P-Pad offers parallel "signing" and "encrypting", optimal exact security, and minimum ciphertext length twice as long as the length of a TDP , while still maintaining optimal bandwidth. S-Pad loses parallelism and some exact security, but has minimal ciphertext length equal to that of a TDP. Any S-Pad can also be used as a "universal padding" scheme. X-Pad is similar to S-Pad, but regains optimal exact security at the expense of a marginally-longer minimum ciphertext length. Moreover, to unify various padding options, we construct a single versatile padding scheme PSEP (Probabilistic Signature-Encryption Padding) which, by simply adjusting the lengths of the parameters, can work optimally as either a P-Pad, S-Pad or X-Pad.

In this paper, we provide a new approach to study undeniable signatures by translating secure digital signatures to secure undeniable signatures so that the existing algorithms can be used. Our mechanism is that any verifier without trapdoor information cannot distinguish whether a message is encoded from Diffie-Hellamn resource $D$ or random resource $R$ while a signer with trapdoor information can distinguish efficiently a codeword which is computed from $D$ or $R$. We show how our mechanism can be efficiently achieved and provide proofs of security for our schemes in the standard complexity model. We also provide evidences to show that our approach can be applied to construct designated confirmer signatures, designated verifier signatures as well.

Coron et al. proposed the ES-based scheme PSS-ES which realizes an encryption scheme and a signature scheme with a unique padding scheme and key pair. The security of PSS-ES as an encryption scheme is based on the \textit{partial-domain one-wayness} of the encryption permutation. In this paper, we propose new ES schemes OAEP-ES, OAEP++-ES, and REACT-ES, and prove their security under the assumption of \textit{only} the \textit{one-wayness} of encryption permutation. OAEP-ES, OAEP++-ES, and REACT-ES suit practical implementation because they use the same padding technique for encryption and for signature, and their security proof guarantees that we can prepare one key pair to realize encryption and signature in the same way as PSS-ES. Since \textit{one-wayness} is a weaker assumption than \textit{partial-domain one-wayness}, the proposed schemes offer tighter security than PSS-ES. Hence, we conclude that OAEP-ES, OAEP++-ES, and REACT-ES are more effective than PSS-ES. OAEP++-ES is the most practical approach in terms of the tightness of security and communication efficiency.

In 2002 the new genre of digital signature scheme TTS (Tame Transformation Signatures) is introduced along with a sample scheme TTS/2. TTS is from the family of multivariate cryptographic schemes to which the NESSIE primitive {SFLASH} also belongs. It is a realization of Moh's theory for digital signatures, based on Tame Transformations or Tame Maps. Properties of multivariate cryptosystems are determined mainly by their central maps. TTS uses Tame Maps as their central portion for even greater speed than $C^\ast$-related schemes (using monomials in a large field for the central portion), previously usually acknowledged as fastest. We show a small flaw in TTS/2 and present an improved TTS implementation which we call TTS/4. We will examine in some detail how well TTS/4 performs, how it stands up to previously known attacks, and why it represents an advance over TTS/2. Based on this topical assessment, we consider TTS in general and TTS/4 in particular to be competitive or superior in several aspects to other schemes, partly because the theoretical roots of TTS induce many good traits. One specific area in which TTS/4 should excel is in low-cost smartcards. It seems that the genre has great potential for practical deployment and deserves further attention by the cryptological community.

In this paper, we analyze two proxy signatures scheme [1], [2] proposed by Lal and Awasthi and found that both the schemes suffer with the security flaws. The scheme [1] suffers with proxy signer's forgery attacks and misuse of original signer's delegated information. The other scheme [2] suffers with original signer's forgery attack, proxy signer's undeniability and misuse of delegated information.

In resent years, Popescu proposed several group signature schemes based on the Okamoto-Shiraishi assumption in [8-11], and claimed his schemes are secure. However, this paper demonstrates that all these schemes are insecure by identifying some security flaws. Exploiting these flaws, an attacker without any secret can mount universally forging attacks. That is, anybody (not necessarily a group member) can forge valid group signatures on arbitrary messages of his/her choice.

We show how to construct a CCA-secure public-key encryption scheme from any CPA-secure identity-based encryption (IBE) scheme. Our conversion from IBE to a CCA-secure scheme is simple, efficient, and provably secure in the standard model (i.e., security of the resulting scheme does not rely on the random oracle model). In addition, the resulting scheme achieves CCA security even if the underlying IBE scheme satisfies only a ``weak'' notion of security which is known to be achievable in the standard model based on the bilinear Diffie-Hellman assumption. Thus, our results yield a new construction of CCA-secure public-key encryption in the standard model. Interestingly, the resulting scheme avoids any non-interactive proofs of ``well-formedness'' which were shown to underlie all previously-known constructions. We also extend our technique to obtain a simple and reasonably efficient method for securing any BTE scheme against adaptive chosen-ciphertext attacks. This, in turn, yields more efficient constructions of CCA-secure (hierarchical) identity-based and forward-secure encryption schemes in the standard model. Our results --- building on previous black-box separations --- rule out black-box constructions of IBE from CPA-secure public-key encryption.

Cryptographic computations are often carried out on insecure devices for which the threat of key exposure represents a serious and realistic concern. In an effort to mitigate the damage caused by exposure of secret keys stored on such devices, the paradigm of \emph{forward security} was introduced. In a forward-secure scheme, secret keys are updated at regular periods of time; exposure of the secret key corresponding to a given time period does not enable an adversary to ``break'' the scheme (in the appropriate sense) for any \emph{prior} time period. A number of constructions of forward-secure digital signature schemes, key-exchange protocols, and symmetric-key schemes are known. We present the first non-trivial constructions of (non-interactive) forward-secure public-key encryption schemes. Our main construction achieves security against chosen-plaintext attacks under the decisional bilinear Diffie-Hellman assumption in the standard model. This scheme is practical, and all parameters grow at most logarithmically with the total number of time periods. We also give a slightly more efficient scheme in the random oracle model. Both our schemes can be extended to achieve security against chosen-ciphertext attacks and to support an unbounded number of time periods. Toward our goal, we introduce the notion of \emph{binary tree encryption} and show how to construct a binary tree encryption scheme in the standard model. This new primitive may be of independent interest. In particular, we use it to construct the first known example of a (hierarchical) identity-based encryption scheme that is secure in the standard model. (Here, however, the notion of security we achieve is slightly weaker than what is achieved in some previous constructions in the random oracle model.)

Identity-based (ID) cryptosystems avoid the necessity of certificates to authenticate public keys in a digital communications system. This is desirable, specially for these applications which involve a large number of public keys in each execution. For example, any computation and verification of a ring signature scheme, where a user anonymously signs a message on behalf of a set of users including himself, requires to authenticate the public keys of all the members of the set. We use bilinear pairings to design a new ID-based ring signature scheme. We extend to the ID-based scehario some known results about the security of generic ring signature schemes. This allows us to formally prove the security of our scheme, under the assumption that the Computational Diffie-Hellman problem is hard to solve.

We extend the explicit formulae for arithmetic on genus two curves of Takahashi and Miyamoto,Doi,Matsuo,Chao,and Tsuji to fields of even characteristic and to arbitrary equation of the curve and slightly improve them. These formulae can be evaluated faster than the more general Cantor algorithm and allow to obtain faster arithmetic on a hyperelliptic genus 2 curve than on elliptic curves. We give timings for implementations using various libraries for the field arithmetic.

Using the Frobenius endomorphism the operation of computing scalar-mulitples in the Jacobian of a hyperelliptic curve is sped-up considerably. The kind of curves considered are Kobiltz i.e. subfield curves, defined over a small finite field which are then considered over a large extension field. We deal with computation of the group order over various extension fields, algorithms to obtain the mentioned speed-up, and experimental results concerning both issues. Additionally an alternative set-up is treated which uses arihtmetic in the finite field only and allows shorter code for similar security. Furthermore explicit formulae to perform the arithmetic in the ideal class group explicitely are derived and can thus be used for implementation in hardware; in software they are also faster than the generic Cantor algorithm. As a second group suitable for cryptographic applications the trace-zero-variety is considered. Here we investigate the group operation and deal with security issues.

Blind signature is the concept to ensure anonymity of e-cion. Untracebility and unlinkability are two main properties of real coin, which require mimicking electronically. Proxy signature schemes allow a proxy signer to generate a proxy signature on behalf of an original signer.All the previous proxy signature schemes are based on ElGamal-type schemes.In this paper, we propose a new proxy blind signature scheme based on an ID-based signature scheme, which uses bilinear pairings of elliptic curves or hyperelliptic curves.

A public key cryptosystem based on Drinfeld modules has been proposed by Gillard, Leprevost, Panchishkin and Roblot. The paper shows how an adversary can directly recover a private key using only the public key, and so the cryptosystem is insecure.

A practical key substitution attack on SFLASH^{v3} is described: Given a valid (message, signature) pair (m,\sigma) for some public key v_0, one can derive another public key v_1 (along with matching secret data) such that (m,\sigma) is also valid for v_1. The computational effort needed for finding such a `duplicate' key is comparable to the effort needed for ordinary key generation.

We define the notion of adative chosen stegotext security. We then construct \emph{efficient} public key steganographic schemes secure against adaptively chosen stegotext attacks, without resort to any special existence assumption such as unbiased functions. This is the first time such a construction is obtained. Not only our constructions are \emph{secure}, but also are essentially optimal and have \emph{no error} decoding. We achieve this by applying a primitive called $\ch{P}$-codes.

At Crypto'89, Chaum and van Antwerpen first introduced the concept of undeniable signatures, which has a special property such that a signature cannot be verified without the signer's cooperation. In 1996, Jakobsson, Sako, and Impagliazzo proposed a not-interactive undeniable signature scheme by employing a new primitive called designated verifier proofs. However, this paper shows that their scheme is insecure by demonstrating a simple attack that allows a dishonest signer to convince a designated verifier receiving invalid signatures. In addition, two intuitive countermeasures are presented.

In this paper, we study the security notions of verifiably committed signatures by introducing privacy and cut-off time, and then we propose the first scheme which is provably secure in the standard complexity model based on the strong RSA assumption. The idea behind the construction is that given any valid partial signature of messages, if a co-signer with its auxiliary input is able to generate variables called the resolution of messages such that the distribution of the variables is indistinguishable from that generated by the primary signer alone from the views of the verifier/arbitrator, a verifiably committed signature can be constructed.

This paper introduces the concept of 'certificateless public key cryptography' (CL-PKC). In contrast to traditional public key cryptographic systems, CL-PKC does not require the use of certificates to guarantee the authenticity of public keys. It does rely on the use of a trusted third party (TTP) who is in possession of a master key. In these respects, CL-PKC is similar to identity-based public key cryptography (ID-PKC). On the other hand, CL-PKC does not suffer from the key escrow property that seems to be inherent in ID-PKC. Thus CL-PKC can be seen as a model for the use of public key cryptography that is intermediate between traditional certificated PKC and ID-PKC. We make concrete the concept of CL-PKC by introducing certificateless public key encryption (CL-PKE), signature and key exchange schemes. We also demonstrate how hierarchical CL-PKC can be supported. The schemes are all derived from pairings on elliptic curves. The lack of certificates and the desire to prove the schemes secure in the presence of an adversary who has access to the master key requires the careful development of new security models. For reasons of brevity, the focus in this paper is on the security of CL-PKE. We prove that our CL-PKE scheme is secure in a fully adaptive adversarial model, provided that an underlying problem closely related to the Bilinear Diffie-Hellman Problem is hard.

In this paper, we give a first example of identity based undeniable signature using pairings over elliptic curves. We extend to the identity based setting the security model for the notions of invisibility and anonymity given by Galbraith and Mao in 2003 and we prove that our scheme is existentially unforgeable under the Bilinear Diffie-Hellman assumption in the random oracle model. We also prove that it has the invisibility property under the Decisional Bilinear Diffie-Hellman assumption and we discuss about the efficiency of the scheme.

At Eurocrypt 2003, Augot and Finiasz proposed a new public-key encryption scheme based on the polynomial reconstruction problem. The scheme was subsequently broken by Coron, who showed that given the public-key and a ciphertext, one could recover the corresponding plaintext in polynomial time. Recently, Augot, Finiasz and Loidreau published on the IACR eprint archive a reparation of the cryptosystem. The reparation is based on the trace operator, and is resistant against the previous attack. However, we describe a new cryptanalysis of the repaired scheme. Given the public-key and a ciphertext, we can still recover the corresponding plaintext in polynomial time. Our technique is a variant of the Berlekamp-Welsh algorithm, and works very well in practice, as for the proposed parameters, we recover the plaintext in less than 8 minutes on a single PC.

In [http://eprint.iacr.org/2003/211/] SFLASH^{v3} is presented, which supersedes SFLASH^{v2}, one of the digital signature schemes in the NESSIE Portfolio of recommended cryptographic primitives. We show that a known attack against the affine parts of SFLASH^{v1} and SFLASH^{v2} carries over immediately to the new version SFLASH^{v3}: The 861 bit representing the affine parts of the secret key can easily be derived from the public key alone.

In this paper, we present a modification of the Augot-Finiasz cryptosystem presented at EUROCRYPT 2003. Coron managed to design an attack against the original cryptosystem enabling an attacker to decrypt any intercepted ciphertext efficiently. We introduce here a modification of the scheme which appears to resist to this attack. We furthermore propose parameters thwarting the state of the art attacks.

A compact mesh architecture for supporting the relation collection step of the number field sieve is described. Differing from TWIRL, only isolated chips without inter-chip communication are used. According to a preliminary analysis for 768-bit numbers, with a 130 nm process one mesh-based device fits on a single chip of ca. (4.9 cm)^2 - the largest proposed chips in the TWIRL cluster for 768-bit occupy ca. (6.7 cm)^2. A 300 mm silicon wafer filled with the mesh-based devices is about 6.3 times slower than a wafer with TWIRL clusters, but due to the moderate chip size, lack of inter-chip communication, and the comparatively regular structure, from a practical point of view the mesh-based approach might be as attractive as TWIRL.

In this letter, we show that structured ElGamal-type multisignature scheme due to Burmester et al. is not secure if the adversary attacks key generation.

In a proxy signature scheme, a potential signer delegates his capabilities to a proxy signer, who can sign documents on behalf of him. The recipient of the signature verifies both identities: that of the delegator and that of the proxy signer. There are many proposals of proxy signature schemes, but security of them has not been considered in a formal way until the appearance of the work by Boldyreva et al. If the entities which take part in a proxy signature scheme are formed by sets of participants, then we refer to it as a fully distributed proxy signature scheme. In this work, we extend the security definitions introduced by Boldyreva et al. to the scenario of fully distributed proxy signature schemes, and we propose a specific scheme which is secure in this new model.

Ma and Chen proposed a new authenticated encryption scheme with public verifiability. This scheme requires less computational costs and communication overheads than the conventional signature-then-encryption approaches. In this letter, we show that the Ma-Chen scheme does not satisfy three security properties: unforgeability, confidentiality and non-repudiation.

Forward-secure signatures are used to defeat signature forgeries in cases of key exposure. In this model, the signature key evolves with time and it is computationally infeasible for an adversary to forge a signature for some time-period prior to the key’s exposure. In this paper a new forward-secure digital signature scheme is presented, which is based on the use of bilinear maps recently advocated by Boneh and Franklin [9]. This scheme is efficiently constructed and can be used with a large number of time periods with a log magnitude complexity. The signing and key-update operations are very efficient when compared with other previously available schemes. A formal definition, as well as a detailed analysis of the security performance or this scheme, is presented. The security proof for this scheme is based on the Computational Diffie-Hellman assumption, which leads to a unique approach to proving security in the random oracle model. Furthermore, within the proof both the hash oracle and the signing oracle are constructed in an innovative manner.

We introduce the notion of certificate-based encryption. In this model, a certificate -- or, more generally, a signature -- acts not only as a certificate but also as a decryption key. To decrypt a message, a keyholder needs both its secret key and an up-to-date certificate from its CA (or a signature from an authorizer). Certificate-based encryption combines the best aspects of identity-based encryption (implicit certification) and public key encryption (no escrow). We demonstrate how certificate-based encryption can be used to construct an efficient PKI requiring less infrastructure than previous proposals, including Micali's Novomodo, Naor-Nissim and Aiello-Lodha-Ostrovsky.

We present a new binary tree based parallel algorithm for extending the domain of a UOWHF. The key length expansion is m(t+O(log*(t))) bits. In particular, the key length expansion is 2m bits for t=2; m(t+1) bits for 3\leq t\leq 6 and m(t+2) bits for 7\leq t\leq 134, where m is the length of the message digest and t\geq 2 is the height of the binary tree. The previously best known binary tree algorithm required a key length expansion of m(t+[log_2 (t-1)]) bits. We also give a sufficient condition for valid domain extension in sequental domain extension.

In this paper we present a fast addition algorithm in the Jacobian of a Picard curve over a finite field $\mathbb F _q$ of characteristic different from $3$. This algorithm has a nice geometric interpretation, comparable to the classic "chord and tangent" law for the elliptic curves. Computational cost for addition is $144M + 12SQ + 2I$ and $158M + 16SQ + 2I$ for doubling.

Security against adaptive chosen ciphertext attacks (or, CCA security) has been accepted as the standard requirement from encryption schemes that need to withstand active attacks. In particular, it is regarded as the appropriate security notion for encryption schemes used as components within general protocols and applications. Indeed, CCA security was shown to suffice in a large variety of contexts. However, CCA security often appears to be somewhat {\em too strong:} there exist encryption schemes (some of which come up naturally in practice) that are not CCA secure, but seem sufficiently secure ``for most practical purposes.'' We propose a relaxed variant of CCA security, called {\sf Replayable CCA (RCCA)} security. RCCA security accepts as secure the non-CCA (yet arguably secure) schemes mentioned above; furthermore, it suffices for most existing applications of CCA security. We provide three formulations of RCCA security. The first one follows the spirit of semantic security and is formulated via an ideal functionality in the universally composable security framework. The other two are formulated following the indistinguishability and non-malleability approaches, respectively. We show that the three formulations are equivalent in most interesting cases.

We consider the impact of the possibility of decryption failures in proofs of security for padding schemes, where these failures are both message and key dependent. We explain that an average case failure analysis is not necessarily sufficient to achieve provable security with existing CCA2-secure schemes. On a positive note, we introduce NAEP, an efficient padding scheme similar to PSS-E designed especially for the NTRU one-way function. We show that with this padding scheme we can prove security in the presence of decryption failures, under certain explicitly stated assumptions. We also discuss the applicability of proofs of security to instantiated cryptosystems in general, introducing a more practical notion of cost to describe the power of an adversary.

Let $E$ be an elliptic curve defined over a prime finite field $F_p$ by a Weierstrass equation. In this paper we introduce a new partition of $E(F_p)$ into classes which are generally larger than $\{\pm R\}$. We give an effective procedure to compute representatives of such classes. So one can iterate the pseudorandom function, related to a discrete logarithm problem in $E(F_p)$, on the set of representatives of classes and get probably some speed up in computing discrete logarithms. The underlying idea how to enlarge known classes on anomalous binary elliptic curves is given.

We describe an efficient combination of two variants of RSA cryptosystem (MPrime and Rebalanced RSA) analysed by Boneh and Schacham. The decryption process resultant is (for 2048-bits moduli) about 8 times faster than that presented by Quisquater and Couvreur and about 27 times faster than original cryptosystem.

In this paper, we study some RSA-based semantically secure encryption schemes (IND-CPA) in the standard model. We first derive the exactly tight one-wayness of Rabin-Paillier encryption scheme which assumes that factoring Blum integers is hard. We next propose the first IND-CPA scheme whose one-wayness is equivalent to factoring {\it general} $n=pq$ (not factoring Blum integers). Our reductions of one-wayness are very tight because they require only one decryption-oracle query.

We give a method for constructing ordinary elliptic curves over finite prime field $\mathbb{F}_p$ with small security parameter $k$ with respect to a prime $\ell$ dividing the group order $\#E(\mathbb{F}_p)$ such that $p<<\ell^2$.

We propose a simple algorithm to select group generators suitable for pairing-based cryptosystems. The selected parameters are shown to favor implementations of the Tate pairing that are at once conceptually simple and efficient, with an observed performance about 2 to 10 times better than previously reported implementations, depending on the embedding degree. Our algorithm has beneficial side effects: various non-pairing operations become faster, and bandwidth may be saved.

We demonstrate that some finite fields, including GF(2^210) are weak for elliptic curve cryptography in the sense that any instance of the elliptic curve discrete logarithm problem for any elliptic curve over these fields can be solved in significantly less time than it takes Pollard's rho method to solve the hardest instances. We discuss the implications of our observations to elliptic curve cryptography, and list some open problems.