We consider non-malleable (NM) and universally composable (UC) commitmentschemes in the common reference string (CRS) model. We show how to construct non-interac\-tive NM commitments that remain non-malleable even if the adversary has access to an arbitrary number of commitments from honest players - rather than one, as in several previous schemes. We show this is a strictly stronger security notion. Our construction is the first non-interactive scheme achieving this that can be based on the minimal assumption of existence of one-way functions. But it can also be instantiated in a very efficient version based on the strong RSA assumption. For UC commitments, we show that existence of a UC commitment scheme in the CRS model (interactive or not) implies key exchange and - for a uniform reference string - even implies oblivious transfer. This indicates that UC commitment is a strictly stronger primitive than NM. Finally, we show that our strong RSA based construction can be used to improve the most efficient known UC commitment scheme so it can work with a CRS of size independent of the number of players, without loss of efficiency.

At Crypto'99, Fujisaki and Okamoto~\cite{FO99} presented a nice generic transformation from weak asymmetric and symmetric schemes into an IND-CCA hybrid encryption scheme in the Random Oracle Model. From this transformation, two specific candidates to standardization were designed: EPOC-2~\cite{EPOC} and PSEC-2~\cite{PSEC}, based on Okamoto-Uchiyama and El Gamal primitives, respectively. Since then, several cryptanalysis of EPOC have been published, one in the Chosen Ciphertext Attack game and others making use of a poor implementation that is vulnerable to reject timing attacks. The aim of this work is to avoid these attacks from the generic transformation, identifying the properties that an asymmetric scheme must hold to obtain a secure hybrid scheme. To achieve this, some ambiguities in the proof of the generic transformation~\cite{FO99} are described, which can lead to false claims. As a result the original conversion is modified and the range of asymmetric primitives that can be used is shortened. In second place, the concept of {\it Easy Verifiable Primitive} is formalized, showing its connection with the Gap problems. Making use of these ideas, a {\it new} security proof for the modified transformation is given. The good news is that the reduction is {\it tight}, improving the concrete security claimed in the original work for the Easy Verifiable Primitives. For the rest of primitives the concrete security is improved at the cost of stronger assumptions. Finally, the resistance of the new conversion against reject timing attacks is addressed.

In this note, we describe a probabilistic attack on public key cryptosystems based on the word/conjugacy problems for finitely presented groups of the type proposed recently by Anshel, Anshel and Goldfeld. In such a scheme, one makes use of the property that in the given group the word problem has a polynomial time solution, while the conjugacy problem has no known polynomial solution. An example is the braid group from topology in which the word problem is solvable in polynomial time while the only known solutions to the conjugacy problem are exponential. The attack in this paper is based on having a canonical representative of each string relative to which a length function may be computed. Hence the term length attack. Such canonical representatives are known to exist for the braid group.

We investigate formulae to double and add in the ideal class group of a hyperelliptic genus 2 curve avoiding inversions. To that aim we introduce a further coordinate in the representation of a class in which we collect the common denominator of the usual 4 coordinates. The analysis shows that this is practical and advantageous whenever inversions are expensive compared to multiplications like for example on smart cards.

This paper is the third in a line considering the arithmetic in the ideal class group of hyperelliptic genus two curves. The previous two papers deal with generalizations of affine and projective coordinates. Now we investigate how one can obtain inversion free formulae that are faster than projective by considering weighted coordinates. To that end we make an extensive case study to deal with different characteristic, equation of the curve, space requirement and situation of appliance.

Braid Groups have recently been considered for use in Public-Key Cryptographic Systems. The most notable of these system has been the Birman-Ko-Lee system presented at Crypto 2000. This article gives a brief introduction into braid groups and the hard problems on which public key systems have been defined. It suggests a canonical form max run form using the Artin generators and supplies some supporting algorithms necessary for cryptographic operations.

Mambo et al [6-7] introduced a proxy signature scheme. Neuman [8] extended the scheme for delegation by warrant, which was further extended by Kim et al [4] to partial delegation with a warrant. In this paper we propose a new type of digital proxy signature scheme in which the warrant message can be recovered from the proxy signature. In this scheme the warrant message is conveyed within the proxy signature and recovered by the verifier, i.e., the warrant need not be hashed or sent along with the proxy signature. It saves both communication bandwidth and storage space.

It is widely believed that genus four hyperelliptic curve cryptosystems (HECC) are not attractive for practical applications because of their complexity compared to systems based on lower genera, especially elliptic curves. Our contribution shows that for low cost security applications genus-4 hyperelliptic curves (HEC) can outperform genus-2 HEC and that we can achieve a performance similar to genus-3 HEC. Furthermore our implementation results show that a genus-4 HECC is an alternative cryptosystem to systems based on elliptic curves. In the work at hand we present for the first time explicit formulae for genus-4 HEC, resulting in a 60% speed-up compared to the best published results. In addition we implemented genus-4 HECC on a Pentium4 and an ARM microprocessor. Our implementations on the ARM show that for genus four HECC are only a factor of 1.66 slower than genus-2 curves considering group order ~2^{190}. For the same group order ECC and genus-3 HECC are about a factor of 2 faster than genus-4 curves on the ARM. The two most surprising results are: 1) for low cost security application, namely considering an underlying group of order 2^{128}, HECC with genus 4 outperform genus-2 curves by a factor of 1.46 and has similar performance to genus-3 curves on the ARM and 2) when compared to genus-2 and genus-3, genus-4 HECC are better suited to embedded microprocessors than to general purpose processors.

A (public key) Trace and Revoke Scheme combines the functionality of broadcast encryption with the capability of traitor tracing. Specifically, (1) a trusted center publishes a single public key and distributes individual secret keys to the users of the system; (2) anybody can encrypt a message so that all but a specified subset of ``revoked'' users can decrypt the resulting ciphertext; and (3) if a (small) group of users combine their secret keys to produce a ``pirate decoder'', the center can trace at least one of the ``traitors'' given access to this decoder. We construct the first chosen ciphertext (CCA2) secure Trace and Revoke Scheme based on the DDH assumption. Our scheme is also the first adaptively secure scheme, allowing the adversary to corrupt players at any point during execution, while prior works (e.g., [NP00,TT01]) only achieves a very weak form of non-adaptive security even against chosen plaintext attacks. In fact, no CCA2 scheme was known even in the symmetric setting. Of independent interest, we present a slightly simpler construction that shows a ``natural separation'' between the classical notion of CCA2 security and the recently proposed [Sho01,ADR02] relaxed notion of gCCA2 security.

In this paper, the authors propose a new structured multisignature scheme that considers the signing order among co-signers. The proposed scheme can resolve signing structures of serial, parallel, and the mix of them. Moreover, the size and the verification of a structured multisignature is the same as those of an individual signature generated by any co-signer. Arithmetically, the proposed scheme makes use of the Gap Diffie-Hellman (GDH) signature scheme recently presented by Boneh, Shacham, and Lynn. Due to the underlying GDH group, our scheme has the merits of simplicity in construction and efficiency in performance.

We study elliptic curve cryptosystems by first investigating the schemes defined over $Z_p$ and show that the scheme is provably secure against adaptive chosen cipher-text attack under the decisional Diffie-Hellman assumption. Then we derive a practical elliptic curve cryptosystem by making use of some nice elliptic curve where the decisional Diffie-Hellman assumption is reserved.

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 data stored on such devices, the paradigm of \emph{forward security} was introduced. In this model, secret keys are updated at regular intervals throughout the lifetime of the system; furthermore, exposure of a secret key corresponding to a given interval does not enable an adversary to ``break'' the system (in the appropriate sense) for any \emph{prior} time period. A number of constructions of forward-secure digital signature schemes and symmetric-key schemes are known. We present the first construction of a forward-secure public-key encryption scheme whose security is based on the bilinear Diffie-Hellman assumption in the random oracle model. Our scheme can be extended to achieve chosen-ciphertext security at minimal additional cost. The construction we give is quite efficient: all parameters of the scheme grow (at most) poly-logarithmically with the total number of time periods.

We show all the existing TTM implementation schemes have a defect that there exist linearization equations $$ \sum_{i=1,j=1}^{n,m} a_{ij}x_iy_j(x_1,\dots,x_{n})+ \sum_{i=1}^{n} b_ix_i+\sum_{j=1}^{m} c_jy_j(x_1,\dots,x_{n}) + d= 0, $$ which are satisfied by the components $y_i(x_1,\dots,x_n)$ of the ciphers of the TTM schemes. We further demonstrate that, for the case of the most recent two implementation schemes in two versions of the paper \cite{CM}, where the inventor of TTM used them to refute a claim in \cite{CG}, if we do a linear substitution with the linear equations derived from the linearization equations for a given ciphertext, we can find the plaintext easily by an iteration of the procedure of first search for linear equations by linear combinations and then linear substitution. The computation complexity of the attack on these two schemes is less than $2^{35}$ over a finite field of size $2^8$.

A Tamed Transformation Method (TTM) cryptosystem was proposed by T.T.Moh in 1999. We describe how the first implementation scheme of the TTM system can be defeated. The computational complexity of our attack is $2^{33}$ computations on the finite field with $2^8$ elements.

An aggregate signature scheme is a digital signature that supports aggregation: Given $n$ signatures on $n$ distinct messages from $n$ distinct users, it is possible to aggregate all these signatures into a single short signature. This single signature (and the $n$ original messages) will convince the verifier that the $n$ users did indeed sign the $n$ original messages (i.e., user $i$ signed message $M_i$ for $i=1,\ldots,n$). In this paper we introduce the concept of an aggregate signature scheme, present security models for such signatures, and give several applications for aggregate signatures. We construct an efficient aggregate signature from a recent short signature scheme based on bilinear maps due to Boneh, Lynn, and Shacham. Aggregate signatures are useful for reducing the size of certificate chains (by aggregating all signatures in the chain) and for reducing message size in secure routing protocols such as SBGP. We also show that aggregate signatures give rise to verifiably encrypted signatures. Such signatures enable the verifier to test that a given ciphertext $C$ is the encryption of a signature on a given message $M$. Verifiably encrypted signatures are used in contract-signing protocols. Finally, we show that similar ideas can be used to extend the short signature scheme to give simple ring signatures.

NTRU is an efficient public-key cryptosystem proposed by Hoffstein, Pipher, and Silverman. Assuming access to a decryption oracle, we show ways to recover the private key of NTRU systems that do not include a ciphertext validating procedure. The strongest of our methods will employ just a single call to the oracle, and in all cases, the number of calls needed will be small enough to be realistic.

Pointcheval and Stern introduced in 1996 some forking lemmas useful to prove the security of a family of digital signature schemes. This family includes, for example, Schnorr's scheme and a modification of ElGamal signature scheme. In this work we generalize these forking lemmas to the ring signatures' scenario. In a ring signature scheme, a signer in a subset (or {\it ring}) of potential signers produces a signature of a message in such a way that the receiver can verify that the signature comes from a member of the ring, but cannot know which member has actually signed. We propose a new ring signature scheme, based on Schnorr signature scheme, which provides unconditional anonymity. We use the generalized forking lemmas to prove that this scheme is existentially unforgeable under adaptive chosen-message attacks, in the random oracle model.

We propose the first polynomial time algorithm for the braid Diffie-Hellman conjugacy problem (DHCP) on which the braid key exchange scheme and the braid encryption scheme are based~\cite{KLCHKP01}. We show the proposed method solves the DHCP for the image of braids under the Lawrence-Krammer representation and the solutions play the equivalent role of the original key for the DHCP of braids. Given a braid index $n$ and a canonical length $\ell$, the complexity is about $2^{-2}\ell^3 n^{4\tau+2}\log n$ bit operations, where $\tau=\log_27\approx 2.8$ (Theoretically, it can be reduced to $O(\ell^3 n^{8.3}\log n)$ using $\tau=2.376$). Further, we show that the generalization into the decomposition problem causes only 8 times of the complexity.

We propose an elliptic curve trapdoor system which is of interest in key escrow applications. In this system, a pair ($E_{\rm s}, E_{\rm pb}$) of elliptic curves over $\F_{2^{161}}$ is constructed with the following properties: (i) the Gaudry-Hess-Smart Weil descent attack reduces the elliptic curve discrete logarithm problem (ECDLP) in $E_{\rm s}(\F_{2^{161}})$ to a hyperelliptic curve DLP in the Jacobian of a curve of genus 7 or 8, which is computationally feasible, but by far not trivial; (ii) $E_{\rm pb}$ is isogenous to $E_{\rm s}$; (iii) the best attack on the ECDLP in $E_{\rm pb}(\F_{2^{161}})$ is the parallelized Pollard rho method.\\ The curve $E_{\rm pb}$ is used just as usual in elliptic curve cryptosystems. The curve $E_{\rm s} is submitted to a trusted authorityfor the purpose of key escrow. The crucial difference from other key escrow scenarios is that the trusted authority has to invest a considerable amount of computation to compromise a user's private key, which makes applications such as widespread wire-tapping impossible.

The pairings on elliptic curves have been applied for realizing the secure ID based cryptosystems that can be invulnerable to the collusion attacks. The computation of the pairing are necessary for the cryptosystems, though the computation of the pairing requires high cost compared with the computation cost for the power operation over the finite fields or on the elliptic curve when the parameters are securely to be provided. In this paper we propose an efficient method for a class of ID based cryptosystems which have been proposed by the present authors. The proposed method is able to reduce the number of the computations for the pairing for verifying the ID based signature and also for decoding of the ID based public key cryptosystems with the authentication, by a factor of 2. Moreover we propose the ID based public key cryptosystems with signature and the ID based public key cryptosystems having the multiple centers.

We give a closed formula for the Tate-pairing on the hyperelliptic curve $y^2 = x^p - x + d$ in characteristic $p$. This improves recent implementations by Barreto et.al. and by Galbraith et.al. for the special case $p=3$. As an application, we propose a $n$-round key agreement protocol for up to $3^n$ participants by extending Joux's pairing-based protocol to $n$ rounds.

Sufficient conditions are obtained on the prime factors of an RSA modulus in order to avoid Wiener and Boneh-Durfee attacks. The public exponent can be chosen arbitrarily.

Boneh and Venkatesan have proposed a polynomial time algorithm for recovering a "hidden" element $\alpha \in \F_p$, where $p$ is prime, from rather short strings of the most significant bits of the residue of $\alpha t$ modulo $p$ for several randomly chosen $t\in \F_p$. Gonzälez Vasco and the first author have recently extended this result to subgroups of $\F_p^*$ of order at least $p^{1/3+\varepsilon}$ for all $p$ and to subgroups of order at least $p^\varepsilon$ for almost all $p$. Here we introduce a new modification in the scheme which amplifies the uniformity of distribution of the `multipliers' $t$ and thus extend this result to subgroups of order at least $(\log p)/(\log \log p)^{1-\varepsilon}$ for all primes $p$. As in the above works, we give applications of our result to the bit security of the Diffie--Hellman secret key starting with subgroups of very small size, thus including all cryptographically interesting subgroups.

Extensive studies have been made of the public-key cryptosystems based on multivariate polynomials . However most of the proposed public-key cryptosystems of rate 1.0 based on multivariate polynomials, are proved not secure. In this paper, we propose several types of new constructions of public-key cryptosystems based on two classes of randomly generated simultaneous equations, namely, a class based on bijective transformation and another class based on random transformation. One of the features of the proposed cryptosystems is that the sets of random simultaneous equations significantly improve the utilization factor of the public-key space. We show an example of the proposed cryptosystem whose size is only 100 bits that seems to be apparently secure in a sense that the utilization factor is significantly large compared with the conventional public-key cryptosystems.

Recently, based on Guillou-Quisquater signature scheme, Saeednia proposed an identity-based society oriented signature scheme. However, in this note, we point out that Saeednia's scheme does not satisfy the claimed properties.

We describe a cryptanalysis of a public-key encryption scheme based on the polynomial reconstruction problem. Given the public-key and a ciphertext, we recover the corresponding plaintext in polynomial time. Therefore, the scheme is not one-way. Our technique is a variant of the Berlekamp-Welsh algorithm.

We introduce cryptography based on algebraic tori, give a new public key system called CEILIDH, and compare it to other discrete log based systems including LUC and XTR. Like those systems, we obtain small key sizes. While LUC and XTR are essentially restricted to exponentiation, we are able to perform multiplication as well. We also disprove the open conjectures from the paper "Looking beyond XTR", and give a new algebro-geometric interpretation of the approach in that paper and of LUC and XTR.

We present a new identity based scheme based on pairings over elliptic curves. It combines the functionalities of signature and encryption and is provably secure in the random oracle model. We compare it with Malone-Lee's one from security and efficiency points of view. We give a formal proof of semantical security under the Decisional Bilinear Diffie-Hellman assumption for this new scheme and we show how to devise other provably secure schemes that produce even shorter ciphertexts.

Homomorphic cryptosystems are designed for the first time over any finite group. Applying Barrington's construction we produce for any boolean circuit of the logarithmic depth its encrypted simulation of a polynomial size over an appropriate finitely generated group.

In this paper, we extend the 2-party key exchange protocol on braid groups to the group key agreement protocol based on the hardness of Ko-Lee problem. We also provide authenticity to the group key agreement protocol.

We proposed the first threshold GQ signature scheme. The scheme is unforgeable and robust against any adaptive adversary if the base GQ signature scheme is unforgeable under the chosen message attack and computing the discrete logarithm modulo a safe prime is hard. Our scheme achieve optimal resilience, that is, the adversary can corrupt up to a half of the players. As an extension of our work, we proposed a threshold forward-secure signature scheme, which is the threshold version of the most efficient forward-secure signature scheme up to now.

In smartcard encryption and signature applications, randomized algorithms can be used to increase tamper resistance against attacks based on averaging data-dependent power or EMR variations. Recently, Oswald and Aigner described such an algorithm suitable for point multiplication in elliptic curve cryptography (ECC). With the assumption that an attacker can identify additions and doublings and distinguish them from each other during a single point multiplication, it is shown that the algorithm is insecure for repeated use of the same secret key without blinding of that key. This scotches hopes that the expense of such blinding might be avoided by using the algorithm unless the differences between point additions and doublings can be obscured successfully.

In this paper we present a simpler construction of an encryption scheme that achieves adaptive chosen ciphertext security (CCA2), assuming the existence of trapdoor permutations. We build on previous works of Sahai and De Santis et al. and construct a scheme that we believe is the easiest to understand to date. In particular, it is only slightly more involved than the Naor-Yung encryption scheme that is secure against passive chosen-ciphertext attacks (CCA1). We stress that the focus of this paper is on simplicity only.

A property of the NTRU public-key cryptosystem is that it does not provide perfect decryption. That is, given an instance of the cryptosystem, there exist ciphertexts which can be validly created using the public key but which can't be decrypted using the private key. The valid ciphertexts which an NTRU secret key will not correctly decipher determine, up to a cyclic shift, the secret key. In this paper we present attacks based on this property against the NTRU primitive and many of the suggested NTRU padding schemes. These attacks use an oracle for determining if valid ciphertexts can be correctly deciphered, and recover the user's secret key. The attacks are quite practical. For example, the attack against the NTRU-REACT padding scheme proposed at CRYPTO 2002 with the $N=503$ parameter set requires on average fewer than 30,000 oracle calls and can be performed on a PC in a few minutes. As the traditional definition of a public-key encryption scheme requires perfect decryption, we also define a new type of encryption scheme which encompasses both NTRU and an attack model for the attacks presented against it.

Artin's braid groups currently provide a promising background for cryptographical applications, since the first cryptosystems using braids were introduced in \cite{SCY,AAF, AAG, KLC}. A variety of key agreement protocols based on braids have been described, but few authentication or signature schemes have been proposed so far. We introduce three authentication schemes based on braids, two of them being zero-knowledge interactive proofs of knowledge. Then we discuss their possible implementations, involving normal forms or an alternative braid algorithm, called handle reduction, which can achieve good efficiency under specific requirements.

We present extremely simple ways of embedding a backdoor in the key generation scheme of RSA. Three of our schemes generate two genuinely random primes $p$ and $q$ of a given size, to obtain their public product $n=pq$. However they generate private/public exponents pairs $(d,e)$ in such a way that appears very random while allowing the author of the scheme to easily factor $n$ given only the public information $(n,e)$. Our last scheme, similar to the PAP method of Young and Yung, but more secure, works for any public exponent $e$ such as $3,17,65537$ by revealing the factorization of $n$ in its own representation. This suggests that nobody should rely on RSA key generation schemes provided by a third party.

We propose an elliptic curve scheme over the ring $\entq$, which is efficient and semantically secure in the standard model. There appears to be no previous elliptic curve cryptosystem based on factoring that enjoys both of these properties. KMOV scheme has been used as an underlying primitive to obtain efficiency and probabilistic encryption. Semantic security of the scheme is based on a new decisional assumption, namely, the Decisional Small-$x$ $e$-Multiples Assumption. Confidence on this assumption is also discussed.

Given a positive integer $n$ and a point $P$ on an elliptic curve $E$, the computation of $nP$, that is, the result of adding $n$ times the point $P$ to itself, called the \emph{scalar multiplication}, is the central operation of elliptic curve cryptosystems. We present an algorithm that, using $p$ processors, can compute $nP$ in time $O(\log n+H(n)/p+\log p)$, where $H(n)$ is the Hamming weight of $n$. Furthermore, if this algorithm is applied to Koblitz curves, the running time can be reduced to $O(H(n)/p+\log p)$.

Mix chains as proposed by Chaum allow sending untraceable electronic e-mail without requiring trust in a single authority: messages are recursively public-key encrypted to multiple intermediates (mixes), each of which forwards the message after removing one layer of encryption. To conceal as much information as possible when using variable (source routed) chains, all messages passed to mixes should be of the same length; thus, message length should not decrease when a mix transforms an input message into the corresponding output message directed at the next mix in the chain. Chaum described an implementation for such length-preserving mixes, but it is not secure against active attacks. We show how to build practical cryptographically secure length-preserving mixes. The conventional definition of security against chosen ciphertext attacks is not applicable to length-preserving mixes; we give an appropriate definition and show that our construction achieves provable security.

Many variants of the ElGamal signature scheme have been proposed. The most famous is the DSA standard. If computing discrete logarithms is hard, then some of these schemes have been proven secure in an idealized model, either the random oracle or the generic group. We propose a generic but simple presentation of signature schemes with security based on the discrete logarithm. We show how they can be proven secure in idealized model, under which conditions. We conclude that none of the previously proposed digital signature schemes has optimal properties and we propose a scheme named PECDSA.

We describe a credential system similar to the electronic cash system described by Chaum, Fiat and Naor. Our system uses bit commitments to create selective disclosure credentials which limit what portions of a credential the holder must reveal. We show how credentials from separate issuers can be linked to the same person in order to prevent users from pooling credentials to obtain services no one user could obtain alone. We also describe how to use a blinding technique described by Laurie which may not violate the patents on blind signatures.

A. Joux presented a one round protocol for tripartitie key agreement and Al-Riyami et.al. developed a number of tripartitie, one round, authenticated protocols related to MTI and MQV protocols. Recently, Boneh and Silverleg studied multilinear forms, which provides a one round multi-party key agreement protocol. In this paper, we propose $(n+1)$ types of one round authenticated multi-party key agreement protocols from multilinear forms based on the application of MTI and MQV protocols.

The Weil and Tate pairings are a popular new gadget in cryptography and have found many applications, including identity-based cryptography. In particular, the pairings have been used for key exchange protocols. This paper studies the bit security of keys obtained using protocols based on pairings (that is, we show that obtaining certain bits of the common key is as hard as computing the entire key). These results are valuable as they give insight into how many ``hard-core'' bits can be obtained from key exchange using pairings.

Undeniable signature is an intriguing concept introduced by Chaum and Antwerpen at Crypto'89. In 1999, Lee and Hwang presented two group-oriented undeniable signature schemes with a trusted center. Their schemes are natural generalizations of Chaum's zero-knowledge undeniable signature scheme proposed in 1990. However, we find that the Lee-Hwang schemes are insecure. In this paper, we demonstrate five attacks on their schemes: four of them are universal forgery, in which one dishonest member (maybe collude with a verifier) can get a valid signature on any chosen massage, and another attack allows a dishonest member to prevent honest members from generating valid signatures but his cheating behavior is undetected. We also suggest heuristic improvements to overcome some of the problems involved in these attacks.

In this paper we present the first lattice attack on an authenticated key agreement protocol, which does not use a digital signature algorithm to produce the authentication. We present a two stage attack on MQV in which one party may recover the other party's static private key from partial knowledge of the nonces from several runs of the protocol. The first stage reduces the attack to a hidden number problem which is partially solved by considering a closest vector problem and using Babai's algorithm. This stage is closely related to the attack of Nguyen and Shparlinski on DSA but is complicated by a non-uniform distribution of multipliers. The second stage recovers the rest of the key using the baby-step/giant-step algorithm or Pollard's Lambda algorithm and runs in time $O(q^{1/4})$. The attack has been proven to work with high probability and validated experimentally. We have thus reduced the security from $O(q^{1/2})$ down to $O(q^{1/4})$ when partial knowledge of the nonces is given.

At EUROCRYPT '96 J. Patarin introduced the "Isomorphisms of Polynomials (IP)" problem as a basis of authentication and signature schemes. We describe an attack on the secret key of "IP with one secret" and demonstrate its efficiency through examples with realistic parameter sizes. To prevent our attack, additional restrictions on the suggested parameters should be imposed.

Quartz is a signature scheme based on an HFEv- trapdoor function published at Eurocrypt 1996. In this paper we study "inversion" attacks for Quartz, i.e. attacks that solve the system of multivariate equations used in Quartz. We do not cover some special attacks that forge signatures without inversion. We are interested in methods to invert the HFEv- trapdoor function or at least to distinguish it from a random system of the same size. There are 4 types of attacks known on HFE: Shamir-Kipnis, Shamir-Kipnis-Courtois, Courtois, and attacks related to Gröbner bases such as the F5/2 attack by Jean Charles Faugère. No attack has been published so far on HFEv- and it was believed to be more secure than HFE. In this paper we show that even modified HFE systems can be successfully attacked. It seems that the complexity of the attack increases by at least a factor of $q^{tot}$ with $tot$ being the total number of perturbations in HFE. From this and all the other known attacks we will estimate what is the complexity of the best "inversion" attack for Quartz.

The ESIGN signature scheme was provided with an inadequate proof of security. We propose two techniques to repair the scheme, which we name ESIGN-D and ESIGN-R. Another improvement of ESIGN is encouraged, where the public key is hashed together with the message. This allows to have a security proof in the multi key setting. Additionally, the lower security of ESIGN compared to RSA-PSS leads to suggest that a common public key is used for ESIGN and RSA-PSS, leaving to the signer the choice between fast signature or better security.

Wagner and Magyarik outlined a general construction for public key cryptosystems based on the hardness of the word problem for finitely presented groups. At the same time, they gave a specific example of such a system. We prove that their approach is vulnerable to so-called reaction attacks, namely, it is possible to retrieve the private key just by watching the performance of a legitimate recipient.

We present an algorithm for computing the zeta function of an arbitrary hyperelliptic curve over a finite field $\FF_q$ of characteristic 2, thereby extending the algorithm of Kedlaya for odd characteristic. For a genus $g$ hyperelliptic curve defined over $\FF_{2^n}$, the average-case time complexity is $O(g^{4 + \varepsilon} n^{3 + \varepsilon})$ and the average-case space complexity is $O(g^{3} n^{3})$, whereas the worst-case time and space complexities are $O(g^{5 + \varepsilon} n^{3 + \varepsilon})$ and $O(g^{4} n^{3})$ respectively.

This paper contains three parts. In the first part we present a new side channel attack on plaintext encrypted by EME-OAEP PKCS#1 v.2.1. In contrast with Manger´s attack, we attack that part of the plaintext, which is shielded by the OAEP method. In the second part we show that Bleichenbacher’s and Manger’s attack on the RSA encryption scheme PKCS#1 v.1.5 and EME-OAEP PKCS#1 v.2.1 can be converted to an attack on the RSA signature scheme with any message encoding (not only PKCS). This is a new threat for those implementations of PKI, in which the roles of signature and encryption keys are not strictly separated. This situation is often encountered in the SSL protocol used to secure access to web servers. In the third part we deploy a general idea of fault-based attacks on the RSA-KEM scheme and present two particular attacks as the examples. The result is the private key instead of the plaintext as with attacks on PKCS#1 v.1.5 and v.2.1. These attacks should highlight the fact that the RSA-KEM scheme is not an entirely universal solution to problems of RSAES-OAEP implementation and that even here the manner of implementation is significant.

In regular digital signatures, once the secret key is compromised, all signatures, even those that were issued by the honest signer before the compromise, will not be trustworthy any more. Forward-secure signatures have been proposed to address this major shortcoming. We present a new forward-secure signature scheme, called KREUS, with several advantages. It has the most efficient Key Update of all known schemes, requiring just a single modular squaring. Our scheme thus enables more frequent Key Update and hence allows shorter time periods, enhancing security: fewer signatures might become invalid as a result of key compromise. In addition, the on-line component of signing is also very efficient, consisting of a single multiplication. We precisely analyze the total signer costs and show that they are lower when the number of signatures per time period is small; the advantage of our scheme increases considerably as the number of time periods grows. Our scheme's security relies on the Strong-RSA assumption and the random-oracle-based Fiat-Shamir transform.

We investigate relations among the discrete logarithm (DL) problem, the Diffie-Hellman (DH) problem and the bilinear Diffie-Hellman (BDH) problem when we have an efficient computable non-degenerate bilinear map $e:G\times G \rightarrow H$. Under a certain assumption on the order of $G$, we show that the DH problem on $H$ implies the DH problem on $G$, and both of them are equivalent to the BDH problem when $e$ is {\it weak-invertible}. Moreover, we show that given the bilinear map $e$ an injective homomorphism $f:H\rightarrow G$ enables us to solve the DH problem on $G$ efficiently, which implies the non-existence a {\it self-bilinear} map $e:G\times G \rightarrow G$ when the DH problem on $G$ is hard. Finally we introduce a sequence of bilinear maps and its applications.

A common practice to encrypt with RSA is to first apply a padding scheme to the message and then to exponentiate the result with the public exponent; an example of this is OAEP. Similarly, the usual way of signing with RSA is to apply some padding scheme and then to exponentiate the result with the private exponent, as for example in PSS. Usually, the RSA modulus used for encrypting is different from the one used for signing. The goal of this paper is to simplify this common setting. First, we show that PSS can also be used for encryption, and gives an encryption scheme semantically secure against adaptive chosen-ciphertext attacks, in the random oracle model. As a result, PSS can be used indifferently for encryption or signature. Moreover, we show that PSS allows to safely use the same RSA key-pairs for both encryption and signature, in a concurrent manner. More generally, we show that using PSS the same set of keys can be used for both encryption and signature for any trapdoor partial-domain one-way permutation. The practical consequences of our result are important: PKIs and public-key implementations can be significantly simplified.

In this paper we investigate the efficiency of cryptosystems based on ordinary elliptic curves over fields of characteristic three. We look at different representations for curves and consider some of the algorithms necessary to perform efficient point multiplication. We give example timings for our operations and compare them with timings for curves in characteristic two of a similar level of security. We show that using the Hessian form in characteristic three produces a point multiplication algorithm under $50$ percent slower than the equivalent system in characteristic two. Thus it is conceivable that curves in characteristic three, could offer greater performance than currently perceived by the community.

In this paper, a new special-purpose factorization algorithm is presented, which finds a prime factor $p$ of an integer $n $ in polynomial time, if $4p-1$ has the form $d b^2$ where $d \in \{3, 11, 19, 43, 67, 163\}$ and $b$ is an integer. Hence such primes should be avoided when we select the RSA secret keys. Some generalizations of the algorithm are discussed in the paper as well.

Using more than two factors in the modulus of the RSA cryptosystem has the arithmetic advantage that the private key computations can be speeded up using Chinese remaindering. At the same time, with a proper choice of parameters, one does not have to work with a larger modulus to achieve the same level of security in terms of the difficulty of the integer factorization problem. However, numerous attacks on specific instances on the RSA cryptosystem are known that apply if, for example, the decryption or encryption exponent are chosen too small, or if partial knowledge of the private key is available. Little work is known on how such attacks perform in the multi-prime case. It turns out that for most of these attacks it is crucial that the modulus contains exactly two primes. They become much less effective, or fail, when the modulus factors into more than two distinct primes.

We investigate the possibility of building elliptic curves over finite prime fields having given small MOV-degrees. Using complex multiplication, we give many examples of such curves.

This paper presents results that show that there exist problems in that are provably hard in the generic group model but easy to solve whenever the random encoding function is replaced with a specific encoding function (or one drawn from a specific set of encoding functions). We also show that there exist cryptographic schemes that are provably hard in the generic group model but easy to break in practice.

We propose an elliptic curve scheme over the ring $\entq$, which is efficient and semantically secure in the standard model, and it has expansion factor 2 (previous schemes with similar features present expansion factors greater or equal than 4). Demytko's RSA type scheme has been used as an underlying primitive to obtain efficiency and probabilistic encryption. Semantic security of the scheme is based on a new decisional assumption, namely, the Decisional Small Root Assumption. Confidence on this assumption is also discussed.

We propose a new notion of intrusion-resilient signature schemes, which generalizes and improves upon both forward-secure [And97,BM99] and key-insulated [DKXY02] signature schemes. Specifically, as in the prior notions, time is divided into predefined time periods (e.g., days); each signature includes the number of the time time period in which it was generated; while the public key remains the same, the secret keys evolve with time. Also, as in key-insulated schemes, the user has two modules, signer and home base: the signer generates signatures on his own, and the base is needed only to help update the signer's key from one period to the next. The main strength of intrusion-resilient schemes, as opposed to prior notions, is that they remain secure even after arbitrarily many compromises of both modules, as long as the compromises are not simultaneous. Moreover, even if the intruder does compromise both modules simultaneously, she will still be unable to generate any signatures for the previous time periods. We provide an efficient intrusion-resilient signature scheme, provably secure in the random oracle model based on the strong RSA assumption. We also discuss how such schemes can eliminate the need for certificate revocation in the case of on-line authentication.

A new framework for protection against key exposure was recently suggested by Dodis et. al.. We take its realization further towards practice by presenting simple new schemes that provide benefits over previous ones in terms of scalability, performance and security. Our first contribution is a simple, practical, scalable scheme called SKIE-OT that achieves the best possible security in their framework. SKIE-OT is based on the Boneh-Franklin identity-based encryption (IBE) scheme and exploits algebraic properties of the latter. We also show that the role of identity-based encryption is not coincidental by proving that IBE is equivalent to (not strongly) key-insulated encryption with optimal threshold and allowing random-access key updates.

The Cramer-Shoup cryptosystem for groups of prime order is a practical public-key cryptosystem, provably secure in the standard model under standard assumptions. This paper extends the cryptosystem for groups of unknown order, namely the group of quadratic residues modulo a composed N. Two security results are: In the standard model, the scheme is provably secure if both the Decisional Diffie-Hellman assumption for QR_N *and* the factorisation assumption for N hold. In the random oracle model, the security of the scheme is provable by a quite efficient reduction.

We formally study the notion of a joint signature and encryption in the public-key setting. We refer to this primitive as {\em signcryption}, adapting the terminology of Zheng [Zhe97]. We present wo definitions for the security of signcryption depending on whether the adversary is an outsider or a legal user of the system. We then examine generic sequential composition methods of building signcryption from a signature and encryption scheme. Contrary to what recent results in the symmetric setting [BN00,Kra01] might lead one to expect, we show that classical ``encrypt-then-sign'' (EtS) and ``sign-then-encrypt'' (StE) methods are both {\em secure} composition methods in the public-key setting. We also present a new composition method which we call ``commit-then-encrypt-and-sign'' (CtE&S). Unlike the generic sequential composition methods, CtE&S applies the expensive signature and encryption operations {\em in parallel}, which could imply a gain in efficiency over the StE and EtS schemes. We also show that the new CtE&S method elegantly combines with the recent ``hash-sign-switch'' technique of Shamir and Tauman [ST01], leading to efficient {\em on-line/off-line} signcryption. Finally and of independent interest, we discuss the {\em definitional} inadequacy of the standard notion of chosen ciphertext (CAA) security. Motivated by our applications to signcryption, we show that the notion of CAA-security is syntactically ill-defined, and leads to artificial examples of ``secure'' encryption schemes which do not meet the formal definition of CCA-security. We suggest a natural and very slight relaxation of CAA-security, which we call generalized CCA-security (gCCA). We show that gCCA-security suffices for all known uses of CCA-secure encryption, while no longer suffering from the definitional shortcomings of the latter.

Cryptographic computations (decryption, signature generation, etc.) are often performed on a relatively insecure device (e.g., a mobile device or an Internet-connected host) which cannot be trusted to maintain secrecy of the private key. We propose and investigate the notion of \emph{key-insulated security} whose goal is to minimize the damage caused by secret-key exposures. In our model, the secret key(s) stored on the insecure device are refreshed at discrete time periods via interaction with a physically-secure --- but computationally-limited --- device which stores a ``master key''. All cryptographic computations are still done on the insecure device, and the public key remains unchanged. In a (t, N)-key-insulated scheme, an adversary who compromises the insecure device and obtains secret keys for up to t periods of his choice is unable to violate the security of the cryptosystem for \emph{any} of the remaining N-t periods. Furthermore, the scheme remains secure (for \emph{all} time periods) against an adversary who compromises \emph{only} the physically-secure device. We notice that key-insulated schemes significantly improve the security guarantee of forward-secure schemes [A97,BM99], in which exposure of the secret key at even a single time period (necessarily) compromises the security of the system for all future time periods. This improvement is achieved with minimal cost: infrequent key updates with a (possibly untrusted) secure device. We focus primarily on key-insulated public-key encryption. We construct a (t,N)-key-insulated encryption scheme based on any (standard) public-key encryption scheme, and give a more efficient construction based on the DDH assumption. The latter construction is then extended to achieve chosen-ciphertext security.

The article describes an attack on OpenPGP format, which leads to disclosure of the private signature keys of the DSA and RSA algorithms. The OpenPGP format is used in a number of applications including PGP, GNU Privacy Guard and other programs specified on the list of products compatible with OpenPGP, which is available at http://www.pgpi.org/products. Therefore all these applications must undergo the same revision as the actual program PGP. The success of the attack was practically verified and demonstrated on the PGP program, version 7.0.3 with a combination of AES and DH/DSS algorithms. As the private signature key is the basic information of the whole system which is kept secret, it is encrypted using the strong cipher. However, it shows that this protection is illusory, as the attacker has neither to attack this cipher nor user´s secret passphrase. A modification of the private key file in a certain manner and subsequent capturing of one signed message is sufficient for successful attack. Insufficient protection of the integrity of the public as well as private parts of signature keys in the OpenPGP format is analyzed in DSA and RSA algorithms and on the basis of this, a procedure of attacks is shown on both private signature keys. The attacks apply to all lengths of parameters (modules, keys) of RSA and DSA. In the end the cryptographic measures for correction of the OpenPGP format as well as PGP format are proposed.

We introduce a new class of computational problems which we call the ``one-more-RSA-inversion'' problems. Our main result is that two problems in this class, which we call the chosen-target and known-target inversion problems respectively, have polynomially-equivalent computational complexity. We show how this leads to a proof of security for Chaum's RSA-based blind signature scheme in the random oracle model based on the assumed hardness of either of these problems. We define and prove analogous results for ``one-more-discrete-logarithm'' problems. Since the appearence of the preliminary version of this paper, the new problems we have introduced have found other uses as well.

Suppose Alice wishes to send a message to Bob using an identity-based encryption scheme (recall such a scheme is a public key cryptosystem where any string is a valid public key), but desires integrity as well as security. In other words, Alice wants Bob to know that only she could have sent the message. Furthermore, suppose she does not want the non-repudiation property that would necessarily be present if she simply used an identity-based signature scheme i.e. she does not want Bob to be able to prove to a third party that she is the sender. We augment the system of Boneh and Franklin to allow communication with integrity without nonrepudiation. We formalize notions of security and integrity for our scheme, and show that new encryption and decryption algorithms are more efficient, despite being equally secure and authenticated.

The public key cryptosystem $MST_1$ has been introduced in~\cite{MaStTr00}. Its security relies on the hardness of factoring with respect to wild logarithmic signatures. To identify `wild-like' logarithmic signatures, the criterion of being totally-non-transversal has been proposed. We give tame totally-non-transversal logarithmic signatures for the alternating and symmetric groups of degree $\ge 5$. Hence, basing a key generation procedure on the assumption that totally-non-transversal logarithmic signatures are `wild like' seems critical. We also discuss the problem of recognizing `weak' totally-non-transversal logarithmic signatures, and demonstrate that another proposed key generation procedure based on permutably transversal logarithmic signatures may produce weak keys.

The public key cryptosystems $MST_1$ and $MST_2$ make use of certain kinds of factorizations of finite groups. We show that generalizing such factorizations to infinite groups allows a uniform description of several proposed cryptographic primitives. In particular, a generalization of $MST_2$ can be regarded as a unifying framework for several suggested cryptosystems including the ElGamal public key system, a public key system based on braid groups and the MOR cryptosystem.

We introduce a new methodology for achieving security against adaptive chosen-ciphertext attack (CCA) for public-key encryption schemes, which we call the {\em oblivious decryptors model}. The oblivious decryptors model generalizes both the two-key model of Naor and Yung, as well the Cramer--Shoup encryption schemes. The key ingredient in our new paradigm is Sahai's notion of Simulation-Sound NIZK proofs. Our methodology is easy to use: First, construct an encryption scheme which satisfies the ``bare'' oblivious-decryptors model: This can be done quite easily, with simple proofs of security. Then, by adding a Simulation-Sound NIZK proof, the scheme becomes provably CCA-secure. Note that this paradigm allows for the use of {\em efficient} special-purpose Simulation-Sound NIZK proofs, such as those recently put forward by Cramer and Shoup. We also show how to present all known efficient (provably secure) CCA-secure public-key encryption schemes as special cases of our model.

A group signature scheme allows any group member to sign on behalf of the group in an anonymous and unlinkable fashion. In the event of a dispute, a designated trusted entity can reveal the identity of the signer. Group signatures are claimed to have many useful applications such as voting and electronic cash. A number of group signature schemes have been proposed to-date. However, in order for the whole group signature concept to become practical and credible, the problem of secure and efficient group member revocation must be addressed. In this paper, we construct a new revocation method for group signatures based on the signature scheme by Ateniese et al. at Crypto 2000. This new method represents an advance in the state-of-the-art since the only revocation schemes proposed thus far are either: 1) based on implicit revocation and the use of fixed time periods, or 2) require the signature size to be linear in the number of revoked members. Our method, in contrast, does not rely on time periods, offers constant-length signatures and constant work for the signer.

We analyze the security of different versions of the adapted RSA-PSS signature scheme, including schemes with variable salt lengths and message recovery. We also examine a variant with Rabin-Williams (RW) as the underlying verification primitive. Our conclusion is that the security of RSA-PSS and RW-PSS in the random oracle model can be tightly related to the hardness of inverting the underlying RSA and RW primitives, at least if the PSS salt length is reasonably large. Our security proofs are based on already existing work by Bellare and Rogaway and by Coron, who examined signature schemes based on the original PSS encoding method.

We introduce the OAEP++ encoding method, which is an adaptation of the OAEP encoding method, replacing the last step of the encoding operation with an application of a block cipher such as AES. We demonstrate that if $f$ is a one-way trapdoor function that is hard to invert, then OAEP++ combined with $f$ is secure against an IND-CCA2 adversary in the random oracle model. Moreover, the security reduction is tight; an adversary against $f$-OAEP++ can be extended to an $f$-inverter with a running time linear in the number of oracle queries.

In this paper we describe an elementary criterion to determine supersingular hyperelliptic curve of genus $2$, using only the given Weierstrass equation. Furthermore, we show that the discrete logarithm problem defined on any supersingular abelian variety of dimension $2$ over ${\mathbb F}_p, p>16,$ can be embedded to that over the extension field ${\mathbb F}_{p^{k}}$, with $k \leq 6.$ This implies that supersingular hyperelliptic curves are cryptographically weaker than the general case due to the Frey-R$\ddot{u}$ck attack. A family of the hyperelliptic curve $H/{\mathbb F}_p$ of the type $v^2=u^5+a$ and $v^2 = u^5 + au$ have been studied and further examples are listed.

In this paper we propose a universal forgery attack of Hess's second ID-based signature scheme against the known-message attack.

Proved here is the sufficiency of certain conditions to ensure the Elliptic Curve Digital Signature Algorithm (ECDSA) existentially unforgeable by adaptive chosen-message attacks. The sufficient conditions include (i) a uniformity property and collision-resistance for the underlying hash function, (ii) pseudo-randomness in the private key space for the ephemeral private key generator, (iii) generic treatment of the underlying group, and (iv) a further condition on how the ephemeral public keys are mapped into the private key space. For completeness, a brief survey of necessary security conditions is also given. Some of the necessary conditions are weaker than the corresponding sufficient conditions used in the security proofs here, but others are identical. Despite the similarity between DSA and ECDSA, the main result is not appropriate for DSA, because the fourth condition above seems to fail for DSA. (The corresponding necessary condition is plausible for DSA, but is not proved here nor is the security of DSA proved assuming this weaker condition.) Brickell et al., Jakobsson et al. and Pointcheval et al. only consider signature schemes that include the ephemeral public key in the hash input, which ECDSA does not do, and moreover, assume a condition on the hash function stronger than the first condition above. This work seems to be the first advance in the provable security of ECDSA.

For certain security applications, including identity based encryption and short signature schemes, it is useful to have abelian varieties with security parameters that are neither too small nor too large. Supersingular abelian varieties are natural candidates for these applications. This paper determines exactly which values can occur as the security parameters of supersingular abelian varieties (in terms of the dimension of the abelian variety and the size of the finite field), and gives constructions of supersingular abelian varieties which are optimal for use in cryptography.

Motivated by emerging needs in online interactions, we define a new type of digital signature called a `Content Extraction Signature' (CES). A CES allows the owner, Bob, of a document signed by Alice, to produce an `extracted signature' on selected extracted portions of the original document, which can be verified to originate from Alice by any third party Cathy, while hiding the unextracted (removed) document portions. The new signature therefore achieves verifiable content extraction with minimal multi-party interaction. We specify desirable functional and security requirements for a CES (including an efficiency requirement: a CES should be more efficient in either computation or communication than the simple multiple signature solution). We propose and analyze four CES constructions which are provably secure with respect to known cryptographic assumptions and compare their performance characteristics.

We describe general exponent group signature schemes and show how these naturally give rise to identity based signature schemes if pairings are used. We prove these schemes to be secure in the random oracle model. Furthermore we describe a particular identity based signature scheme which is quite efficient in terms of bandwidth and computing time, and we develop a further scheme which is not derived from a general exponent group signature scheme. The realization of these schemes uses supersingular elliptic curves and the Tate pairing, which is more efficient than the Weil pairing. Finally we show that these schemes have a more natural solution, than Shamir's original scheme, to the ``escrow'' property that all identity based signature schemes suffer from.

This paper considers arbitrary-length chosen-ciphertext secure asymmetric encryption, thus addressing what is actually needed for a practical usage of strong public-key cryptography in the real world. We put forward two generic constructions, gem-1 and gem-2, which apply to explicit fixed-length weakly secure primitives and provide a strongly secure (IND-CCA2) public-key encryption scheme for messages of unfixed length (typically computer files). Our techniques optimally combine a single call to any one-way trapdoor function with repeated encryptions through some weak block-cipher (a simple xor is fine) and hash functions of fixed-length input so that a minimal number of calls to these functions is needed. Our encryption/decryption throughputs are comparable to the ones of standard methods (asymmetric encryption of a session key + symmetric encryption with multiple modes). In our case, however, we formally prove that our designs are secure in the strongest sense and provide complete security reductions holding in the random oracle model.

We present an efficient identity-based signature scheme which makes use of bilinear pairings on elliptic curves. Our scheme is similar to the generalized ElGamal signature scheme. We consider the security of our scheme.

In the trivial $n$-recipient public-key encryption scheme, a ciphertext is a concatenation of independently encrypted messages for $n$ recipients. In this paper, we say that an $n$-recipient scheme has a ``{\it shortened ciphertext}'' property if the length of the ciphertext is almost a half (or less) of the trivial scheme and the security is still almost the same as the underlying single-recipient scheme. We first present (multi-plaintext, multi-recipient) schemes with the ``{\it shortened ciphertext}'' property for ElGamal scheme and Cramer-Shoup scheme. We next show (single-plaintext, multi-recipient) hybrid encryption schemes with the ``{\it shortened ciphertext}'' property.

An accumulator scheme, introduced be Benaloh and de Mare and further studied by Baric̈ and Pfitzmann, is an algorithm that allows to hash a large set of inputs into one short value, called the \textit{accumulator}, such that there is a short witness that a given input was incorporated into the accumulator. We put forward the notion of \textit{dynamic accumulators}, i.e., a method that allows to dynamically add and delete inputs from the accumulator, such that the cost of an add or delete is independent on the number of accumulated values. We achieve this under the strong RSA assumption. For this construction, we also show an efficient zero-knowledge protocol for proving that a committed value is in the accumulator. In turn, our construction of dynamic accumulator enables efficient membership revocation in the anonymous setting. This method applies to membership revocation in group signature schemes, such as the one due to Ateniese et al., and efficient revocation of credentials in anonymous credential systems, such as the one due to Camenisch and Lysyanskaya. Using our method, allowing revocation does not alter the complexity of any operations of the underlying schemes. In particular, the cost of a group signature verification or credential showing increases by only a small constant factor, less than 2. All previously known methods (such as the ones due to Bresson and Stern and Ateniese and Tsudik incurred an increase in these costs that was linear in the number of members.

This document compares the two published RSA-based hybrid encryption schemes having linear reduction in their security proof: RSA-KEM with DEM1 and RSA-REACT. While the performance of RSA-REACT is worse than the performance of RSA-KEM+DEM1, a complete proof of its security has already been published. This is indeed an advantage, because we show that the security result for RSA-KEM+DEM1 has a small hole. We provide here a complete proof of the security of RSA-KEM+DEM1. We also propose some changes to RSA-REACT to improve its efficiency without changing its security, and conclude that this new RSA-REACT is a generalisation of RSA-KEM+DEM1, with at most the same security, and with possibly worse performance. Therefore we show that RSA-KEM+DEM1 should be preferred to RSA-REACT.

This document is an initial proposal for a draft for a forthcoming ISO standard on public-key encryption. It is hoped that this proposal will serve as a basis for discussion, from which a consensus for a standard may be formed.

A new public key encryption scheme, along with several variants, is proposed and analyzed. The scheme and its variants are quite practical, and are proved secure against adaptive chosen ciphertext attack under standard intractability assumptions. These appear to be the first public-key encryption schemes in the literature that are simultaneously practical and provably secure.

We present several new and fairly practical public-key encryption schemes and prove them secure against adaptive chosen ciphertext attack. One scheme is based on Paillier's Decision Composite Residuosity (DCR) assumption, while another is based in the classical Quadratic Residuosity (QR) assumption. The analysis is in the standard cryptographic model, i.e., the security of our schemes does not rely on the Random Oracle model. We also introduce the notion of a universal hash proof system. Essentially, this is a special kind of non-interactive zero-knowledge proof system for an NP language. We do not show that universal hash proof systems exist for all NP languages, but we do show how to construct very efficient universal hash proof systems for a general class of group-theoretic language membership problems. Given an efficient universal hash proof system for a language with certain natural cryptographic indistinguishability properties, we show how to construct an efficient public-key encryption schemes secure against adaptive chosen ciphertext attack in the standard model. Our construction only uses the universal hash proof systemas a primitive: no other primitives are required, although even more efficient encryption schemes can be obtained by using hash functions with appropriate collision-resistance properties. We show how to construct efficient universal hash proof systems for languages related to the DCR and QR assumptions. From these we get corresponding public-key encryption schemes that are secure under these assumptions. We also show that the Cramer-Shoup encryption scheme (which up until now was the only practical encryption scheme that could be proved secure against adaptive chosen ciphertext attack under a reasonable assumption, namely, the Decision Diffie-Hellman assumption) is also a special case of our general theory.

We present an Extended Quadratic Frobenius Primality Test (EQFT), which is related to the Miller-Rabin test and the Quadratic Frobenius test (QFT) by Grantham. EQFT is well-suited for generating large, random prime numbers since on a random input number, it takes time about equivalent to 2 Miller-Rabin tests, but has much smaller error probability. EQFT extends QFT by verifying additional algebraic properties related to the existence of elements of order 3 and 4. We obtain a simple closed expression that upper bounds the probability of acceptance for any input number. This in turn allows us to give strong bounds on the average-case behaviour of the test: consider the algorithm that repeatedly chooses random odd $k$ bit numbers, subjects them to $t$ iterations of our test and outputs the first one found that passes all tests. We obtain numeric upper bounds for the error probability of this algorithm as well as a general closed expression bounding the error. For instance, it is at most $2^{-143}$ for $k=500, t=2$. Compared to earlier similar results for the Miller-Rabin test, the results indicates that our test in the average case has the effect of 9 Miller-Rabin tests, while only taking time equivalent to about 2 such tests. We also give bounds for the error in case a prime is sought by incremental search from a random starting point. While EQFT is slower than the average case on a small set of inputs, we present a variant that is always fast, i.e.takes time about 2 Miller-Rabin tests. The variant has slightly larger worst case error probability than EQFT, but still improves on previous proposed tests.

In this paper, we first show that three public-key $(k,n)$-traceability schemes can be derived from an $[n,u,d]$-linear code ${\cal C}$ such that $d \geq 2k+1$. The previous schemes are obtained as special cases. This observation gives a more freedom and a new insight to this field. For example, we show that Boneh-Franklin scheme is equivalent to a slight modification of the corrected Kurosawa-Desmedt scheme. This means that BF scheme is redundant or overdesigned because the modified KD scheme is much simpler. It is also shown that the corrected KD scheme is the best among them.

We describe a fast hash algorithm that maps arbitrary messages onto points of an elliptic curve defined over a finite field of characteristic 3. Our new scheme runs in time $O(m^2)$ for curves over $\GF{3^m}$. The best previous algorithm for this task runs in time $O(m^3)$. Experimental data confirms the speedup by a factor $O(m)$, or approximately a hundred times for practical $m$ values. Our results apply for both standard and normal basis representations of $\GF{3^m}$.

In using elliptic curves for cryptography, one often needs to construct elliptic curves with a given or known number of points over a given finite field. In the context of primality proving, Atkin and Morain suggested the use of the theory of complex multiplication to construct such curves. One of the steps in this method is the calculation of the Hilbert class polynomial $H_D(X)$ modulo some integer $p$ for a certain fundamental discriminant $D$. The usual way of doing this is to compute $H_D(X)$ over the integers and then reduce modulo $p$. But this involves computing the roots with very high accuracy and subsequent rounding of the coefficients to the closest integer. (Such accuracy issues also arise for higher genus cases.) We present a modified version of the Chinese remainder theorem (CRT) to compute $H_D(X)$ modulo $p$ directly from the knowledge of $H_D(X)$ modulo enough small primes. Our algorithm is inspired by Couveigne's method for computing square roots in the number field sieve, which is useful in other scenarios as well. It runs in heuristic expected time less than the CRT method in [CNST]. Moreover, our method requires very few digits of precision to succeed, and avoids calculating the exponentially large coefficients of the Hilbert class polynomial over the integers.

We propose a fully functional identity-based encryption scheme (IBE). The scheme has chosen ciphertext security in the random oracle model assuming an elliptic curve variant of the computational Diffie-Hellman problem. Our system is based on bilinear maps between groups. The Weil pairing on elliptic curves is an example of such a map. We give precise definitions for secure identity based encryption schemes and give several applications for such systems.

McEliece is one of the oldest known public key cryptosystems. Though it was less widely studied that RSA, it is remarkable that all known attacks are still exponential. It is widely believed that code-based cryptosystems like McEliece does not allow practical digital signatures. In the present paper we disprove this belief and show a way to build a practical signature scheme based on coding theory. It's security can be reduced in the random oracle model to the well-known {\em syndrome decoding problem} and the distinguishability of permuted binary Goppa codes from a random code. For example we propose a scheme with signatures of $81$-bits and a binary security workfactor of $2^{83}$.

In this paper, we analyze the Gaudry-Hess-Smart (GHS) Weil descent attack on the elliptic curve discrete logarithm problem (ECDLP) for elliptic curves defined over characteristic two finite fields of composite extension degree. For each such field $F_{2^N}$, $N \in [100,600]$, we identify elliptic curve parameters such that (i) there should exist a cryptographically interesting elliptic curve $E$ over $F_{2^N}$ with these parameters; and (ii) the GHS attack is more efficient for solving the ECDLP in $E(F_{2^N})$ than for solving the ECDLP on any other cryptographically interesting elliptic curve over $F_{2^N}$. We examine the feasibility of the GHS attack on the specific elliptic curves over $F_{2^{176}}$, $F_{2^{208}}$, $F_{2^{272}}$, $F_{2^{304}}$, and $F_{2^{368}}$ that are provided as examples inthe ANSI X9.62 standard for the elliptic curve signature scheme ECDSA. Finally, we provide several concrete instances of the ECDLP over $F_{2^N}$, $N$ composite, of increasing difficulty which resist all previously known attacks but which are within reach of the GHS attack.

This paper addresses the security of authenticated encryption schemes in the public key setting. We present two new notions of authenticity that are stronger than the integrity notions given in the symmetric setting \cite{bn00}. We also show that chosen-ciphertext attack security (IND-CCA) in the public key setting is not obtained in general from the combination of chosen-plaintext security (IND-CPA) and integrity of ciphertext (INT-CTXT), which is in contrast to the results shown in the symmetric setting \cite{ky00,bn00}. We provide security analyses of authenticated encryption schemes constructed by combining a given public key encryption scheme and a given digital signature scheme in a ``generic'' manner ---namely, Encrypt-and-Sign, Sign-then-Encrypt, and Encrypt-then-Sign--- and show that none of them, in general, provide security under all notions defined in this paper. We then present a scheme called {\em ESSR} that meets all security notions defined here. We also give security analyses on an efficient Diffie-Hellman based scheme called {\em DHETM}, which can be thought of as a transform of the encryption scheme ``DHIES'' \cite{abr01} into an {\em authenticated} encryption scheme in the public key setting.

In the public key cryptosystem using finite non abelian groups which is suggested in CRYPTO 2001, the discrete logarithm problems in inner automorphism groups are used. In this paper, we generalize the system and give some examples of non abelian groups which is applicable to our system.

The Probabilistic Signature Scheme (PSS) designed by Bellare and Rogaway is a signature scheme provably secure against chosen message attacks in the random oracle model, with a security level equivalent to RSA. In this paper, we derive a new security proof for PSS in which a much shorter random salt is used to achieve the same security level, namely we show that $\log_2 q_{sig}$ bits suffice, where $q_{sig}$ is the number of signature queries made by the attacker. When PSS is used with message recovery, a better bandwidth is obtained because longer messages can now be recovered. Moreover, we show that this size is optimal: if less than $\log_2 q_{sig}$ bits of random salt are used, PSS is still provably secure but no security proof can be tight. This result is based on a new technique which shows that other signature schemes such as the Full Domain Hash scheme and Gennaro-Halevi-Rabin's scheme have optimal security proofs.

In this paper we extend the Weil descent attack due to Gaudry, Hess and Smart (GHS) to a much larger class of elliptic curves. This extended attack still only works for fields of composite degree over $\F_2$. The principle behind the extended attack is to use isogenies to find a new elliptic curve for which the GHS attack is effective. The discrete logarithm problem on the target curve can be transformed into a discrete logarithm problem on the new isogenous curve. One contribution of the paper is to give an improvement to an algorithm of Galbraith for constructing isogenies between elliptic curves, and this is of independent interest in elliptic curve cryptography. We conclude that fields of the form $\F_{q^7}$ should be considered weaker from a cryptographic standpoint than other fields. In addition we show that a larger proportion than previously thought of elliptic curves over $\F_{2^{155}}$ should be considered weak.

This paper is concerned with generalisations of Paillier's probabilistic encryption scheme from the integers modulo a square to elliptic curves over rings. Paillier himself described two public key encryption schemes based on anomalous elliptic curves over rings. It is argued that these schemes are not secure. A more natural generalisation of Paillier's scheme to elliptic curves is given.