This paper proposes new explicit formulas for the doubling and addition steps in Miller's algorithm to compute the Tate pairing on elliptic curves in Weierstrass and in Edwards form. For Edwards curves the formulas come from a new way of seeing the arithmetic. We state the first geometric interpretation of the group law on Edwards curves by presenting the functions which arise in addition and doubling. The Tate pairing on Edwards curves can be computed by using these functions in Miller's algorithm. Computing the sum of two points or the double of a point and the coefficients of the corresponding functions is faster with our formulas than with all previ ously proposed formulas for pairings on Edwards curves. They are even competitive with all published formulas for pairing computation on Weierstrass curves. We also improve the formulas for Tate pairing computation on Weierstrass curve s in Jacobian coordinates. Finally, we present several examples of pairing-friendly Edwards curves.

Drawback of code-based public-key cryptosystems is that their public-key size is lage. It takes some hundreds KB to some MB for typical parameters. While several attempts have been conducted to reduce it, most of them have failed except one, which is Quasi-Dyadic (QD) public-key (for large extention degrees). While an attack has been proposed on QD public-key (for small extension degrees), it can be prevented by making the extension degree $m$ larger, specifically by making $q^(m (m-1))$ large enough where $q$ is the base filed and for a binary code, $q=2$. The drawback of QD is, however, it must hold $n << 2^m - t$ (at least $n \leq 2^{m-1}$) where $n$ and $t$ are the code lenght and the error correction capability of the underlying code. If it is not satisfied, its key generation fails since it is performed by trial and error. This condition also prevents QD from generating parameters for code-based digital signatures since without making $n$ close to $2^m - t$, $2^{mt}/{n \choose t}$ cannot be small. To overcome these problems, we propose ``Flexible'' Quasi-Dyadic (FQD) public-key that can even achieve $n=2^m - t$ with one shot. Advantages of FQD include 1) it can reduce the publi-key size further, 2) it can be applied to code-based digital signatures, too.

We give a new method for generating genus 2 curves over a finite field with a given number of points on the Jacobian of the curve. We define two new invariants for genus 2 curves as values of modular functions on the Hilbert moduli space and show how to compute them. We relate them to the usual three Igusa invariants on the Siegel moduli space and give an algorithm to construct curves using these new invariants. Our approach simplifies the complex analytic method for computing genus 2 curves for cryptography and reduces the amount of computation required.

In this paper, we present an \emph{online/offline identity-based signature} scheme for the wireless sensor network (WSN). We argue that due to significant reduction in computational and storage costs, our scheme is particularly suitable for the WSN environment with severely constrained resources. One of the interesting features of our scheme is that it provides \textit{multi-time} usage of the offline storage, which allows the signer to re-use the offline pre-computed information in polynomial time, in contrast to \textit{one-time} usage in all previous online/offline signature schemes. As evidence of the practicality and feasibility of our scheme to be used in the WSN environment, we provide an actual implementation result of our scheme on the MicaZ platform.

Many authenticated multiple key exchange protocols were published in recent years. In 2008, Lee et al. presented an authenticated multiple key exchange protocol based on bilinear pairings. However, Vo et al. demonstrated an impersonation attack on the protocol , and it failed to provide authenticity and perfect forward secrecy as they had claimed. Later, Vo et al. proposed their enhancement protocol conforming which conforms to all desirable security properties. But, Vo's protocol required any party had held the public key each other, which required a large amount of storage. In this paper, we propose two new authenticated multiple key exchange protocols based on Lee's protocol, and makes them immune against Vo et al.'s attacks.

Proxy re-encryption (PRE), introduced by Blaze, Bleumer and Strauss in Eurocrypt'98, allows a semi-trusted proxy to convert a ciphertext originally intended for Alice into an encryption of the same message intended for Bob. PRE has recently drawn great interest, and many interesting PRE schemes have been proposed. However, up to now, it is still an important question to come up with a chosen-ciphertext secure unidirectional PRE in the adaptive corruption model. To address this problem, we propose a new unidirectional PRE scheme, and prove its chosen-ciphertext security in the adaptive corruption model without random oracles. Compared with the best known unidirectional PRE scheme proposed by Libert and Vergnaud in PKC'08, our schemes enjoys the advantages of both higher efficiency and stronger security.

In this paper, we analyse how to calculate the GCD of $k$ $(\geq 2)$ many large integers, given their approximations. Two versions of the approximate common divisor problem, presented by Howgrave-Graham in CaLC 2001, are special cases of our analysis when $k = 2$. We then relate the approximate common divisor problem to the implicit factorization problem. This has been introduced by May and Ritzenhofen in PKC 2009 and studied under the assumption that some of Least Significant Bits (LSBs) of certain primes are same. Our strategy can be applied to the implicit factorization problem in a general framework considering the equality of (i) Most Significant Bits (MSBs), (ii) Least Significant Bits (LSBs) and (iii) MSBs and LSBs together. We present new and improved theoretical as well as experimental results in comparison with the state of the art works in this area.

Edwards curves have attracted great interest for their efficient addition and doubling formulas. Furthermore, the addition formulas are strongly unified or even complete, i.e., work without change for all inputs. In this paper, we propose the first halving algorithm on binary Edwards curves, which can be used for scalar multiplication. We present a point halving algorithm on binary Edwards curves in case of $d_1\neq d_2$. The halving algorithm costs about $3I+5M+4S$, which is slower than the doubling one. We also give a theorem to prove that the binary Edwards curves have no minimal two-torsion in case of $d_1= d_2$, and we briefly explain how to achieve the point halving algorithm using an improved algorithm in this case. Finally, we apply our halving algorithm in scalar multiplication with $\omega$-coordinate using Montgomery ladder.

Recently, Liu et al. proposed the first certificateless signcryption scheme without random oracles and proved it was semantically secure in the standard model. However, Selvi et al. launched a fatal attack to its confidentiality by replacing users' public keys, thus pointed out this scheme actually doesn't reach the semantic security as claimed. In this paper, we come up with a rescue scheme based on Liu et al.'s original proposal. A Schnorr-based one-time signature is added to each user's public key, which is used to resist Selvi et al.'s attack. In addition, according to the mistake made in Liu et al.'s security proof, we also show that our improvement is really secure in the standard model under the intractability of the decisional bilinear Diffie-Hellman assumption.

We apply the Cocks-Pinch method to obtain pairing-friendly composite order groups with prescribed embedding degree associated to ordinary elliptic curves, and we show that new security issues arise in the composite order setting.

We propose a new encryption scheme that supports joint fingerprinting and decryption. The scheme is remarkably resistant to known-plaintext attack and collusion attack (e.g. average attack or other linear combination attack) on keys. Interestingly, the security of our scheme is relied on a lattice problem: Given a collection of random lattice points generated from a short basis of a lattice, find the short basis. The scheme can be used as a traitor-tracing scheme or a buyer-seller watermarking scheme.

Verifiable encryption allows to encrypt a signature and prove that the plaintext is valid. We introduce a new primitive called commuting signature that extends verifiable encryption in multiple ways: a signer can encrypt both signature and message and prove validity; more importantly, given a ciphertext, a signer can create a verifiably encrypted signature on the encrypted message; thus signing and encrypting commute. We instantiate commuting signatures using the proof system by Groth and Sahai (EUROCRYPT '08) and the automorphic signatures by Fuchsbauer (ePrint report 2009/320). As an application, we give an instantiation of delegatable anonymous credentials, a powerful primitive introduced by Belenkiy et al. (CRYPTO '09). Our instantiation is arguably simpler than theirs and it is the first to provide non-interactive issuing and delegation, which is a standard requirement for non-anonymous credentials. Moreover, the size of our credentials and the cost of verification are less than half of those of the only previous construction, and efficiency of issuing and delegation is increased even more significantly. All our constructions are proved secure in the standard model.

In this note we describe a security weakness in pairing-based protocols when the group order is composite and the imbedding degree $k$ is greater than $2$.

We introduce a ``generalized small inverse problem (GSIP)'' and present an algorithm for solving this problem. GSIP is formulated as finding small solutions of $f(x_0, x_1, \ldots , x_n)=x_0 h(x_1, \ldots , x_n)+C=0 (\bmod \; M)$ for an $n$-variate polynomial $h$, non-zero integers $C$ and $M$. Our algorithm is based on lattice-based Coppersmith technique. We provide a strategy for construction of a lattice basis for solving $f=0$, which are systematically transformed from a lattice basis for solving $h=0$. Then, we derive an upper bound such that the target problem can be solved in polynomial time in $\log M$ in an explicit form. Since GSIPs include some RSA related problems, our algorithm is applicable to them. For example, the small key attacks by Boneh and Durfee are re-found automatically.

The paper provides a cryptanalysis the $AA_\beta$-cryptosystem recently proposed by Ariffin and Abu. The scheme is in essence a key agreement scheme whose security is based on a discrete logarithm problem in the infinite (additive) group $\mathbb{R}/\mathbb{Z}$ (the reals modulo $1$). The paper breaks the $AA_\beta$-cryptosystem (in a passive adversary model) by showing that this discrete logarithm problem can be efficiently solved in practice.

In identity-based public-key cryptography, an entity's public key can be easily derived from its identity. The direct derivation of public keys in identity-based public-key cryptography eliminates the need for certificates and solves certain public key management problems in traditional public-key cryptosystems. Recently, the notion of asymmetric group key agreement was introduced, in which the group members merely negotiate a common encryption key which is accessible to any entity, but they hold respective secret decryption keys. In this paper, we first propose a security model for identity-based authenticated asymmetric group key agreement (IB-AAGKA) protocols. We then propose an IB-AAGKA protocol which is proven secure under the Bilinear Di±e-Hellman Exponent assumption. Our protocol is also efficient, and readily adaptable to provide broadcast encryption.

This paper presents a deterministic algorithm for converting points on an ordinary elliptic curve (defined over a field of characteristic 2) to points on a complete binary Edwards curve. This avoids the problem of choosing curve parameters at random. When implemented on a large (512 bit) hardware multiplier, computation of point multiplication using this algorithm performs significantly better, in terms of code complexity, code coverage and timing, than the standard implementation. In addition, we propose a simple modification to the birational equivalence detailed in the paper by Bernstein et al. which both reduces the number of inversions required in the affine mapping and has fewer exceptional points. Finally, we compare software implementations using this efficient point multiplication for binary Edwards curves with computations on elliptic curves in Weierstrass form.

Generalized Signcryption is a fresh cryptographic primitive that not only can obtain encryption and signature in a single operation, but also provives encryption or signature alone when needed. This paper gives a formal definition of certificateless generalized signcryption and its security model is present. A concrete certificateless generalized signcryption scheme is also proposed in this paper.

Verifiably encrypted signature schemes (VES) allow a signer to encrypt his or her signature under the public key of a trusted third party, while maintaining public signature verifiability. With our work, we propose two generic constructions based on Merkle authentication trees that do not require non-interactive zero-knowledge proofs (NIZKs) for maintaining verifiability. Both are stateful and secure in the standard model. Furthermore, we extend the specification for VES, bringing it closer to real-world needs. We also argue that statefulness can be a feature in common business scenarios. Our constructions rely on the assumption that CPA (even slightly weaker) secure encryption, ``maskable'' CMA secure signatures, and collision resistant hash functions exist. ``Maskable'' means that a signature can be hidden in a verifiable way using a secret masking value. Unmasking the signature is hard without knowing the secret masking value. We show that our constructions can be instantiated with a broad range of efficient signature and encryption schemes, including two lattice-based primitives. Thus, VES schemes can be based on the hardness of worst-case lattice problems, making them secure against subexponential and quantum-computer attacks. Among others, we provide the first efficient pairing-free instantiation in the standard model.

This paper describes new attacks on PKCS \#1 v1.5, a deprecated but still widely used RSA encryption standard. The first cryptanalysis is a broadcast attack, allowing the opponent to reveal an identical plaintext sent to different recipients. This is nontrivial because different randomizers are used for different encryptions (in other words, plaintexts coincide only partially). The second attack predicts, using a single query to a validity checking oracle, which of two chosen plaintexts corresponds to a challenge ciphertext. The attack's success odds are very high. The two new attacks rely on different mathematical tools and underline the need to accelerate the phase out of PKCS \#1 v1.5.

The classical McEliece cryptosystem is built upon the class of Goppa codes, which remains secure to this date in contrast to many other families of codes but leads to very large public keys. Previous proposals to obtain short McEliece keys have primarily centered around replacing that class by other families of codes, most of which were shown to contain weaknesses, and at the cost of reducing in half the capability of error correction. In this paper we describe a simple way to reduce significantly the key size in McEliece and related cryptosystems using a subclass of Goppa codes, while also improving the efficiency of cryptographic operations to $\tilde{O}(n)$ time, and keeping the capability of correcting the full designed number of errors in the binary case.

An identity-based online/offline encryption (IBOOE) scheme splits the encryption process into two phases. The first phase performs most of the heavy computations, such as modular exponentiation or pairing over points on elliptic curve. The knowledge of the plaintext or the receiver's identity is not required until the second phase, where the ciphertext is produced by only light computations, such as integer addition/multiplication or hashing. This division of computations makes encryption affordable by devices with limited computation power since the preparation works can be executed ``offline'' or possibly by some powerful devices. Since efficiency is the main concern, smaller ciphertext size and less burden in the computation requirements of all phases (i.e., both phases of encryption and the decryption phase) are desirable. In this paper, we proposed new schemes with improved efficiency over previous schemes by assuming random oracles. Our first construction is a very efficient scheme which is secure against chosen-plaintext attack (CPA), This scheme is slightly modified from an existing scheme. In particular, the setup and the user private key remain the same. We then proceed to propose the notion of ID-based Online/Offline KEM (IBOOKEM) that allows the key encapsulation process to be split into offline and online stages, in the same way as IBOOE does. We also present a generic transformation to get security against chosen-ciphertext attack (CCA) for IBOOE from any IBOOKEM scheme with one-wayness only. Our schemes (both CPA and CCA) are the most efficient one in the state-of-the-art, in terms of online computation and ciphertext size, which are the two main focuses of online/offline schemes. Our schemes are very suitable to be deployed on embedded devices such as smartcard or wireless sensor which have very limited computation powers and the communication bandwidth is very expensive.

We construct a simple public-key encryption scheme that supports polynomially many additions and one multiplication, similar to the cryptosystem of Boneh, Goh, and Nissim (BGN). Security is based on the hardness of the learning with errors (LWE) problem, which is known to be as hard as certain worst-case lattice problems. Some features of our cryptosystem include support for large message space, an easy way of achieving formula-privacy, a better message-to-ciphertext expansion ratio than BGN, and an easy way of multiplying two encrypted polynomials. Also, the scheme can be made identity-based and leakage-resilient (at the cost of a higher message-to-ciphertext expansion ratio).

Recent emergence of RFID tags capable of performing public key operations motivates new RFID applications, including electronic travel documents, identification cards and payment instruments. In such settings, public key certificates form the cornerstone of the overall system security. In this paper, we argue that one of the prominent -and still woefully unaddressed- challenges is how to handle revocation checking of RFID reader certificates. This is an important issue considering that these high-end RFID tags are geared for applications such as e-documents and contactless payment instruments. Furthermore, the problem is unique to public key-based RFID systems, since tags (even those capable of complex cryptographic operations) have no clock and thus cannot use traditional (time-based) off-line revocation checking methods. Whereas, on-line methods require unrealistic connectivity assumptions. In this paper, we address the problem of reader revocation in PKI-Based RFID systems. We begin by observing an important distinguishing feature of personal RFID tags used in authentication, access control or payment applications -the involvement of a human user. We then take advantage of the user's awareness and presence to construct a simple, efficient, secure and (most importantly) feasible solution for reader revocation checking. And finally, we evaluate the usability and practical security our solution via usability studies and discuss its feasibility in a case study of e-Passports. In our approach, the main extra feature is the requirement for a small passive on-tag display. However, as discussed in the paper, modern low-power display technology (e.g., e-paper) is low-cost and appealing for other (e.g., authentication and verification) purposes.

In this paper we present some problems and their solutions exploiting lattice based root finding techniques. In CaLC 2001, Howgrave-Graham proposed a method to find the Greatest Common Divisor (GCD) of two large integers when one of the integers is exactly known and the other one is known approximately. In this paper, we present three applications of the technique. The first one is to show deterministic polynomial time equivalence between factoring $N$ ($N = pq$, where $p > q$ or $p, q$ are of same bit size) and knowledge of $q^{-1} \bmod p$. Next, we consider the problem of finding smooth integers in a short interval. The third one is to factorize $N$ given a multiple of the decryption exponent in RSA. In Asiacrypt 2006, Jochemsz and May presented a general strategy for finding roots of a polynomial. We apply that technique for solving the following two problems. The first one is to factorize $N$ given an approximation of a multiple of the decryption exponent in RSA. The second one is to solve the implicit factorization problem given three RSA moduli considering certain portions of LSBs as well as MSBs of one set of three secret primes are same.

Sanitizable signatures provide several security features which are useful in many scenarios including military and medical applications. Sanitizable signatures allow a semi-trusted party to update some part of the digitally signed document without interacting with the original signer. Such schemes, where the verifer cannot identify whether the message has been sanitized, are said to possess strong transparency. In this paper, we have described the first efficient and provably secure sanitizable signature scheme having strong transparency under the standard model.

In this paper we propose two public key encryption schemes over the semi-smooth subgroup introduced by Groth05. Both the schemes are proved secure against chosen ciphertext attacks under the factoring assumption. Since the domain of exponents is much smaller, both our schemes are significantly more efficient than Hofheiz-Kiltz 2009 encryption.

In Informatica 32 (2008), Ren and Gu proposed an anonymous hierarchical identity based encryption scheme based on the q-ABDHE problem with full security in the standard model. Later in Indocrypt'08, they proposed another secure hierarchical identity based encryption scheme based on the q-TBDHE problem with full security in the standard model. They claimed that their schemes have short parameters, high efficiency and tight reduction. However, in this paper we give attacks to show their schemes are insecure at all. Concretely, from any first level private key, the adversary can easily derive a proper ``private key'' which can decrypt any ciphertexts for the target identity. That is to say, one key generation query on any first level identity excluding the target's first level identity, is enough to break their schemes.

We present a variant of Regev's cryptosystem, but with a new choice of parameters. By a recent classical reduction by Peikert we prove the scheme semantically secure based on the worst-case lattice problem GapSVP. From this we construct a threshold cryptosystem which has a very efficient and non-interactive decryption protocol. We prove the threshold cryptosystem secure against passive adversaries corrupting all but one of the players, and againts active adversaries corrupting less than one third of the players. We also describe how one can build a distributed key generation protocol. In the final part of the paper, we show how one can, in zero-knowledge - prove knowledge of the plaintext contained in a given ciphertext from Regev's original cryptosystem or our variant. The proof is of size only a constant times the size of a ciphertext.

Genus 2 curves are useful in cryptography for both discrete-log based and pairing-based systems, but a method is required to compute genus 2 curves with Jacobian with a given number of points. Currently, all known methods involve constructing genus 2 curves with complex multiplication via computing their 3 Igusa class polynomials. These polynomials have rational coefficients and require extensive computation and precision to compute. Both the computation and the complexity analysis of these algorithms can be improved by a more precise understanding of the denominators of the coefficients of the polynomials. The main goal of this paper is to give a bound on the denominators of Igusa class polynomials of genus 2 curves with CM by a primitive quartic CM field $K$. We give an overview of Igusa's results on the moduli space of genus two curves and the method to construct genus 2 curves via their Igusa invariants. We also give a complete characterization of the reduction type of a CM abelian surface, for biquadratic, cyclic, and non-Galois quartic CM fields, and for any type of prime decomposition of the prime, including ramified primes.

We introduce the notion of automorphic signatures, which satisfy the following properties: the verification keys lie in the message space, messages and signatures consist of elements of a bilinear group, and verification is done by evaluating a set of pairing-product equations. These signatures make a perfect counterpart to the powerful proof system by Groth and Sahai (Eurocrypt 2008). We provide practical instantiations of automorphic signatures under appropriate assumptions and use them to construct the first efficient round-optimal blind signatures. By combining them with Groth-Sahai proofs, we moreover give practical instantiations of various other cryptographic primitives, such as fully-secure group signatures, non-interactive anonymous credentials and anonymous proxy signatures. To do so, we show how to transform signature schemes whose message space is a group to a scheme that signs arbitrarily many messages at once.

In this paper, we propose a new method for constructing the public-key cryptosystems based on a class of perfect error-correcting codes. The constructed PKC is referred to as K(IV)SE(1)PKC. In K(IV)SE(1)PKC, members of the class of perfect error correcting codes such as (7,4,3) cyclic Hamming code and (3,1,3) code {000,111} is used, yielding a simple process of encryption and decryption. The K(IV)SE(1)PKC has a remarkable feature that the coding rate can take on exactly 1.0 due to the use of perfect codes. Besides the size of the public key for K(IV)SE(1)PKC can be made smaller than that of the McEliece PKC.

This paper proposes practical chosen-ciphertext secure public-key encryption systems that are provably secure under the computational Diffie-Hellman assumption, in the standard model. Our schemes are conceptually simpler and more efficient than previous constructions. We also show that in bilinear groups the size of the public-key can be shrunk from n to 2\sqrt{n} group elements, where n is the security parameter.

We present the first signature scheme which is ''short'', stateless and secure under the RSA assumption in the standard model. Prior short, standard model signatures in the RSA setting required either a strong complexity assumption such as Strong RSA or (recently) that the signer maintain state. A signature in our scheme is comprised of one element in ZN* and one integer. The public key is also short, requiring only the modulus N, one element of ZN*, one integer, one PRF seed and some short chameleon hash parameters. To design our signature, we employ the known generic construction of fully-secure signatures from weakly-secure signatures and a chameleon hash. We then introduce a new proof technique for reasoning about weakly-secure signatures. This technique enables the simulator to predict a prefix of the message on which the adversary will forge and to use knowledge of this prefix to embed the challenge. This technique has wider applications beyond RSA. We also use it to provide an entirely new analysis of the security of the Waters signatures: the only short, stateless signatures known to be secure under the Computational Diffie-Hellman assumption in the standard model.

In this paper, we give an overview of cryptographic applications using real hyperelliptic curves. We review previously proposed cryptographic protocols, and discuss the infrastructure of a real hyperelliptic curve, the mathematical structure underlying all these protocols. We then describe recent improvements to infrastructure arithmetic, including explicit formulas for divisor arithmetic in genus 2; and advances in solving the infrastructure discrete logarithm problem, whose presumed intractability is the basis of security for the related cryptographic protocols.

Proxy re-encryption (PRE) allows a semi-trusted proxy to convert a ciphertext originally intended for Alice into one encrypting the same plaintext for Bob. The proxy only needs a re-encryption key given by Alice, and cannot learn anything about the plaintext encrypted. This adds flexibility in various applications, such as confidential email, digital right management and distributed storage. In this paper, we study unidirectional PRE, which the re-encryption key only enables delegation in one direction but not the opposite. In PKC 2009, Shao and Cao proposed a unidirectional PRE assuming the random oracle. However, we show that it is vulnerable to chosen-ciphertext attack (CCA). We then propose an efficient unidirectional PRE scheme (without resorting to pairings). We gain high efficiency and CCA-security using the ``token-controlled encryption'' technique, under the computational Diffie-Hellman assumption, in the random oracle model and a relaxed but reasonable definition.

Liskov proposed several weakened versions of the random oracle model, called {\em weakened random oracle models} (WROMs), to capture the vulnerability of ideal compression functions, which are expected to have the standard security of hash functions, i.e., collision resistance, second-preimage resistance, and one-wayness properties. The WROMs offer additional oracles to break such properties of the random oracle. In this paper, we investigate whether public-key encryption schemes in the random oracle model essentially require the standard security of hash functions by the WROMs. In particular, we deal with four WROMs associated with the standard security of hash functions; the standard, collision tractable, second-preimage tractable, first-preimage tractable ones (ROM, CT-ROM, SPT-ROM, and FPT-ROM, respectively), done by Numayama et al. for digital signature schemes in the WROMs. We obtain the following results: (1) The OAEP is secure in all the four models. (2) The encryption schemes obtained by the Fujisaki-Okamoto conversion (FO) are secure in the SPT-ROM. However, some encryption schemes with FO are insecure in the FPT-ROM. (3) We consider two artificial variants wFO and dFO of FO for separation of the WROMs in the context of encryption schemes. The encryption schemes with wFO (dFO, respectively) are secure in the CT-ROM (ROM, respectively). However, some encryption schemes obtained by wFO (dFO, respectively) are insecure in the SPT-ROM (CT-ROM, respectively). These results imply that standard encryption schemes such as the OAEP and FO-based one do not always require the standard security of hash functions. Moreover, in order to make our security proofs complete, we construct an efficient sampling algorithm for the binomial distribution with exponentially large parameters, which was left open in Numayama et al.'s paper.

A New digital signature scheme based on Stepwise Triangular Scheme (STS) is proposed. The proposed trapdoor has resolved the vulnerability of STS and secure against both Gröbner Bases and Rank Attacks. In addition, as a basic trapdoor, it is more efficient than the existing systems. With the efficient implementation, the Multivariate Public Key Cryptosystems (MPKC) signature public key has the signature longer than the message by less than 25 %, for example.

In a proxy re-encryption scheme, a semi-trusted proxy can transform a ciphertext under Alice's public key into another ciphertext that Bob can decrypt. However, the proxy cannot access the plaintext. Due to its transformation property, proxy re-encryption can be used in many applications, such as encrypted email forwarding. In this paper, by using the techniques of Canetti-Hohenberger and Kurosawa-Desmedt, we propose a new single-use unidirectional proxy re-encryption scheme. Our proposal is secure against chosen ciphertext attack (CCA) and collusion attack in the standard model.

Machine Readable travel documents have been rapidly put in place since 2004. The initial standard was made by the ICAO and it has been quickly followed by the Extended Access Control (EAC). In this paper we discuss about the evolution of these standards and more precisely on the evolution of EAC. We intend to give a realistic survey on these standards. We discuss about their problems, such as the inexistence of a clock in the biometric passports and the absence of a switch preventing the lecture of a closed passport. We also look at the issue with retrocompatibility that could be easily solved and the issue with terminal revocation that is harder.

A fair blind signature is a blind signature with revocable anonymity and unlinkability, i.e., an authority can link an issuing session to the resulting signature and trace a signature to the user who requested it. In this paper we first revisit the security model for fair blind signatures given by Hufschmitt and Traoré in 2007. We then give the first practical fair blind signature scheme with a security proof in the standard model. Our scheme satisfies a stronger variant of the Hufschmitt-Traoré model.

We propose a variant of Peikert's lattice-based existentially unforgeable signature scheme in the standard model. Our construction offers the same efficiency as Peikert's but supports the stronger notion of strong unforgeability. Strong unforgeability demands that the adversary is unable to produce a new message-signature pair (m, s), even if he or she is allowed to see a different signature sig' for m. In particular, we provide the first treeless signature scheme that supports strong unforgeability for the post-quantum era in the standard model. Moreover, we show how to directly implement identity-based, and even hierarchical identity-based, signatures (IBS) in the same strong security model without random oracles. An additional advantage of this direct approach over the usual generic conversion of hierarchical identity-based encryption to IBS is that we can exploit the efficiency of ideal lattices without significantly harming security. We equip all constructions with strong security proofs based on mild worst-case assumptions on lattices and we also propose concrete security parameters.

A code-based cryptosystem is considered secure if the best known attack against it is information-set decoding. Stern's algorithm and its improvements are well optimized and the complexity is reasonably well understood. However, these algorithms only handle codes over F2. This paper presents a generalization of Stern's information-set-decoding algorithm for decoding linear codes over arbitrary finite fields Fq and analyzes the complexity. This result makes it possible to compute the security of recently proposed code-based systems over non-binary fields. As an illustration, ranges of parameters for generalized McEliece cryptosystems using classical Goppa codes over F31 are suggested for which the new information-set-decoding algorithm needs 2^128 bit operations.

We show that an RSA private key with small public exponent can be efficiently recovered given a 0.27 fraction of its bits at random. An important application of this work is to the "cold boot" attacks of Halderman et al. We make new observations about the structure of RSA keys that allow our algorithm to make use of the redundant information in the typical storage format of an RSA private key. Our algorithm itself is elementary and does not make use of the lattice techniques used in other RSA key reconstruction problems. We give an analysis of the running time behavior of our algorithm that matches the threshold phenomenon observed in our experiments.

A random number generator based on the operation of isogenies between elliptic curves over finite fields Fp is proposed. By using the proposed generator together with the isogeny cryptography algorithm, which is against the attack of quantum computer, we can save hardware and software components. Theoretical analyses show that periods of the proposed random number generator are sufficiently long. Moreover, the generated sequences have passed the U.S. NIST statistical test.

Recently, a certificateless signcryption scheme in the standard model was proposed by Liu et al. in \cite{LiuHZM10}. Another certificateless signcryption scheme in the standard model was proposed by Xie et al. in \cite{WZ09}. Here, we show that the scheme in \cite{LiuHZM10} and \cite{WZ09} are not secure against Type-I adversary.

Pairings on elliptic curves over finite fields are crucial for constructing various cryptographic schemes. The \eta_T pairing on supersingular curves over GF(3^n) is particularly popular since it is efficiently implementable. Taking into account the Menezes-Okamoto-Vanstone (MOV) attack, the discrete logarithm problem (DLP) in GF(3^{6n}) becomes a concern for the security of cryptosystems using \eta_T pairings in this case. In 2006, Joux and Lercier proposed a new variant of the function field sieve in the medium prime case, named JL06-FFS. We have, however, not yet found any practical implementations on JL06-FFS over GF(3^{6n}). Therefore, we first fulfilled such an implementation and we successfully set a new record for solving the DLP in GF(3^{6n}), the DLP in GF(3^{6 \cdot 71}) of 676-bit size. In addition, we also compared JL06-FFS and an earlier version, named JL02-FFS, with practical experiments. Our results confirm that the former is several times faster than the latter under certain conditions.

In this article, we propose an identification scheme which is based on the two combinatorial problems Multivariate Quadratic equations (MQ) and Isomorphism of Polynomials (IP). We show that this scheme is statistical zero-knowledge. Using a trapdoor for the MQ-problem, it is possible to make it also identity-based, i.e., there is no need for distributing public keys or for certificates within this scheme. The size of the public keys and the communication complexity\ are within the range of other non-number-theoretic identification schemes. In contrast to MQ^*-IP, these schemes do usually no permit identity-based public keys.

In this paper, we investigate the difficulty of the Isomorphism of Polynomials (IP) Problem as well as one of its variant IP1S. The Isomorphism of Polynomials is a well-known problem studied more particularly in multivariate cryptography as it is related to the hardness of the key recovery of such cryptosystems. The problem is the following: given two families of multivariate polynomials~$\A$ and~$\B$, find two invertible linear (or affine) mappings $S$ and $T$ such that $\B=T\circ \A \circ S$. For IP1S, we suppose that $T$ is the identity. It is known that the difficulty of such problems depends on the structure of the polynomials (\ie homogeneous, or not) and the nature of the transformations (affine, or linear). Here, we analyze the different cases and propose improved algorithms. We precisely describe the situation in terms of complexity and sufficient conditions to make the algorithms work. The algorithms presented here combine linear algebra techniques, including the use of differentials, together with Gröbner bases and statistical tools such as the birthday paradox and a totally new object in the IP-context, the so-called \emph{Galton-Watson trees}. We show that random instances of IP1S with quadratic polynomials can be broken in time $\bigO{n^6}$, where $n$ is the number of variables, independently of the number of polynomials. For IP1S with cubic polynomials, as well as for IP, we propose new algorithms of complexity $\bigO{n^6}$ if the polynomials of $\A$ are inhomogeneous and $S, T$ linear. In all the other cases, we propose an algorithm that requires $\bigO{n^6 \cdot q^{n/2}}$ computation. Finally, we propose several algorithms for different subcases of the full IP problem, the best of which has complexity $\bigO{q^{n/2}}$. These new tools allow to break the challenges proposed by Patarin in practice, and also raise some fundamental questions about the general security of multivariate public-key schemes.

We need to perform arithmetic in $\Fpt$ to use Ate pairing on a Barreto-Naehrig (BN) curve, where $p(z)$ is a prime given by $p(z)=36z^4+36z^3+24z^2+6z+1$ with an integer $z$. In many implementations of Ate pairing, $\Fpt$ has been regarded as the 6-th extension of $\Fpp$, and it has been constructed as $\Fpt=\Fpp[v]/(v^6-\xi)$ for an element $\xi\in \Fpp$ such that $v^6-\xi$ is irreducible in $\Fpp[v]$. Such $\xi$ depends on the value of $p(z)$, and we may use mathematic software to find $\xi$. This paper shows that when $z \equiv 7,11 \pmod{12}$ we can universally construct $\Fpp$ as $\Fpt=\Fpp[v]/(v^6-u-1)$, where $\Fpp=\Fp[u]/(u^2+1)$.

This paper reports on the factorization of the 768-bit number RSA-768 by the number field sieve factoring method and discusses some implications for RSA.

This paper introduces a new intractable security problem whose intractability is due to the NP completeness of multivariate quadratic problem. This novel problem uses quaternion algebra in conjunction with MQ. Starting with the simultaneous multivariate equations, we transform these equations into simultaneous quaternion based multivariate quadratic equations. A new scheme for computational zero knowledge proof based on this problem is proposed. It is proved that according to black box definition of zero knowledge proof (ZKP) system, the proposed scheme is ZKP. Our proof has two lemmas. The proof is done through two lemmas. In the first lemma it is shown that expected polynomial time machine V * M halts in a polynomial time. In the second lemma, it is showed that the probability ensembles V x L M x * and x L P x , V * x are polynomially indistinguishable. The scheme has low computational overhead and is particularly useful in cryptographic applications such as digital signature and key agreement.

Undeniable signatures, introduced by Chaum and van Antwerpen, require a verifier to interact with the signer to verify a signature, and hence allow the signer to control the verifiability of his signatures. Convertible undeniable signatures, introduced by Boyar, Chaum, Damg\aa{}rd, and Pedersen, furthermore allow the signer to convert signatures to publicly verifiable ones by publicizing a verification token, either for individual signatures or for all signatures universally. In addition, the signer is able to delegate the ability to prove validity and convert signatures to a semi-trusted third party by providing a verification key. While the latter functionality is implemented by the early convertible undeniable signature schemes, most recent schemes do not consider this despite its practical appeal. In this paper we present an updated definition and security model for schemes allowing delegation, and highlight a new essential security property, token soundness, which is not formally treated in the previous security models for convertible undeniable signatures. We then propose a new convertible undeniable signature scheme. The scheme allows delegation of verification and is provably secure in the standard model assuming the computational co-Diffie-Hellman problem, a closely related problem, and the decisional linear problem are hard. Our scheme is, to the best of our knowledge, the currently most efficient convertible undeniable signature scheme which provably fulfills all security requirements in the standard model.

Let $N = pq$ be the product of two large primes. Consider CRT-RSA with the public encryption exponent $e$ and private decryption exponents $d_p, d_q$. It is well known that given any one of $d_p$ or $d_q$ (or both) one can factorize $N$ in probabilistic poly$(\log N)$ time with success probability almost equal to 1. Though this serves all the practical purposes, from theoretical point of view, this is not a deterministic polynomial time algorithm. In this paper, we present a lattice based deterministic poly$(\log N)$ time algorithm that uses both $d_p, d_q$ (in addition to the public information $e, N$) to factorize $N$ for certain ranges of $d_p, d_q$. We like to stress that proving the equivalence for all the values of $d_p, d_q$ may be a nontrivial task.

We give a list of the Solinas prime numbers of the form $f(2^k)=2^m - 2^n \pm 1$, $m \leq 2000$, with small modular reduction weight $wt < 15$, and $k=8,16,32,64$, i.e., $k$ is a multiple of the computer integer arithmetic word size. These can be useful in the construction of cryptographic protocols.

In this paper, we introduce the intermediate hashed Diffie-Hellman (IHDH) assumption which is weaker than the hashed DH (HDH) assumption (and thus the decisional DH assumption), and is stronger than the computational DH assumption. We then present two public key encryption schemes with short ciphertexts which are both chosen-ciphertext secure under this assumption. The short-message scheme has smaller size of ciphertexts than Kurosawa-Desmedt (KD) scheme, and the long-message scheme is a KD-size scheme with arbitrary plaintext length which is based on a weaker assumption than the HDH assumption.

We adapt the CRT approach to computing Hilbert class polynomials to handle a wide range of class invariants. For suitable discriminants D, this improves its performance by a large constant factor, more than 200 in the most favourable circumstances. This has enabled record-breaking constructions of elliptic curves via the CM method, including examples with |D| > 10^{15}.

We describe a one-time signature scheme based on the hardness of the syndrome decoding problem, and prove it secure in the random oracle model. Our proposal can be instantiated on general linear error correcting codes, rather than restricted families like alternant codes for which a decoding trapdoor is known to exist.

Since their introduction in 2008, the non interactive zero-knowledge (NIZK) and non interactive witness indistinguishable (NIWI) proofs designed by Groth and Sahai have been used in numerous applications. In this paper we offer two contributions to the study of these proof systems. First we identify and correct some errors, present in the oringal online manuscript, that occur in two of the three instantiations of the Groth-Sahai NIWI proofs for which the equation checked by the verifier is not valid for honest executions of the protocol. (In particular, implementations of these proofs would not work correctly.) We explain why, perhaps surprisingly, the NIZK proofs that are built from these NIWI proofs do not suffer from a similar problem. Secondly, we study the efficiency of existing instantiations and note that only one of the three instantiations has the potential of being practical. We therefore propose a natural extension of an existing assumption from symmetric pairings to asymmetric ones which in turn enables Groth-Sahai proofs based on new classes of efficient pairings.

We propose a couple of general ways of constructing authentication schemes from actions of a semigroup on a set, without exploiting any specific algebraic properties of the set acted upon. Then we give several concrete realizations of this general idea, and in particular, we describe several authentication schemes with long-term private keys where forgery (a.k.a. impersonation) is NP-hard. Computationally hard problems that can be employed in these realizations include Graph Colorability, Diophantine Problem, and many others.

In this paper, we consider the problem of predicate encryption and focus on the predicate for testing whether the hamming distance between the attribute $X$ of a data item and a target $V$ is equal to (or less than) a threshold $t$ where $X$ and $V$ are of length $m$. Existing solutions either do not provide attribute protection or produce a big ciphertext of size $O(m2^m)$. For the equality version of the problem, we provide a scheme which is match-concealing (MC) secure and the sizes of the ciphertext and token are both $O(m)$. For the inequality version of the problem, we give two practical schemes. The first one, also achieving MC security, produces ciphertext with size $O(m^{t_{max}})$ if the maximum value of $t$, $t_{max}$, is known in advance and is a constant. We also show how to update the ciphertext if the user wants to increase $t_{max}$ without constructing the ciphertext from scratch. On the other hand,in many real applications, the security requirement can be lowered from MC to MR (match-revealing). Our second scheme, which is MR secure, produces ciphertext of size $O(m)$ and token of size $O((t+1)m)$ only.

In this paper, we propose a new practical identity-based encryption scheme which is suitable for wireless sensor network (WSN). We call it \textit{Receiver-Bounded Online/Offline Identity-based Encryption} (RB-OOIBE). It splits the encryption process into two parts -- the offline and the online part. In the offline part, all heavy computations are done without the knowledge of the receiver's identity and the plaintext message. In the online stage, only light computations such as modular operation and symmetric key encryption are required, together with the receiver's identity and the plaintext message. Moreover, since each offline ciphertext can be re-used for the same receiver, the number of offline ciphertexts the encrypter holds only confines the number of receivers instead of the number of messages to be encrypted. In this way, a sensor node (with limited computation power and limited storage) in WSN can send encrypted data easily: A few offline ciphertexts can be computed in the manufacturing stage while the online part is light enough for the sensor to process. We propose an efficient construction for this new notion. The scheme can be proven selective-ID CCA secure in the standard model. Compared to previous online/offline identity-based encryption schemes, our scheme is exempt from a high storage requirement, which is proportional to the number of messages to be sent. The improvement is very significant if many messages are sent to few receivers.

We present a fully homomorphic encryption scheme which has both relatively small key and ciphertext size. Our construction follows that of Gentry by producing a fully homomorphic scheme from a “somewhat” homomorphic scheme. For the somewhat homomorphic scheme the public and private keys consist of two large integers (one of which is shared by both the public and private key) and the ciphertext consists of one large integer. As such, our scheme has smaller message expansion and key size than Gentry’s original scheme. In addition, our proposal allows efficient fully homomorphic encryption over any field of characteristic two.

The HFE (Hidden Field Equations) cryptosystem is one of the most interesting public-key multivariate scheme. It has been proposed more than 10 years ago by Patarin and seems to withstand the attacks that break many other multivariate schemes, since only subexponential ones have been proposed. The public key is a system of quadratic equations in many variables. These equations are generated from the composition of the secret elements: two linear mappings and a polynomial of small degree over an extension field. In this paper we show that there exist weak keys in HFE when the coefficients of the internal polynomial are defined in the ground field. In this case, we reduce the secret key recovery problem to an instance of the Isomorphism of Polynomials (IP) problem between the equations of the public key and themselves. Even though for schemes such as SFLASH or $C^*$ the hardness of key-recovery relies on the hardness of the IP problem, this is normally not the case for HFE, since the internal polynomial is kept secret. However, when a weak key is used, we show how to recover all the components of the secret key in practical time, given a solution to an instance of the IP problem. This breaks in particular a variant of HFE proposed by Patarin to reduce the size of the public key and called the ``subfield variant''.

A directed signature scheme allows a designated verifier to directly verify a signature issued to him, and a third party to check the signature validity with the help of the signer or the designated verifier as well. Directed signatures are applicable where the signed message is sensitive to the signature receiver. Due to its merits, directed signature schemes are suitable for applications such as bill of tax and bill of health. In this paper, we proposed an efficient identity based directed signature scheme from bilinear pairings. Our scheme is efficient than the existing directed signature schemes. In the random oracle model, our scheme is unforgeable under the Computational Diffie-Hellman (CDH) assumption, and invisible under the Decisional Bilinear Diffie-Hellman (DBDH).

Encrypt-and-sign, where one encrypts and signs a message in parallel, is usually not recommended for confidential message transmission. The reason is that the signature typically leaks information about the message. This motivates our investigation of confidential signature schemes, which hide all information about (high-entropy) input messages. In this work we provide a formal treatment of confidentiality for such schemes and a comprehensive discussion of the relationship of different notions we propose. We give constructions meeting our notions, both in the random oracle model and the standard model. As part of this we show that full domain hash signatures achieve a weaker level of confidentiality than Fiat-Shamir signatures. We then revisit the connection of confidential signatures to signcryption schemes. We give formal security models for deterministic signcryption schemes for high-entropy and low-entropy messages, and prove encrypt-and-sign to be secure for confidential signature schemes and high-entropy messages. Finally, we show that one can derandomize any signcryption scheme in our model and obtain a secure deterministic scheme.

In this paper we propose an efficient multivariate public key cryptosystem. Public key of our cryptosystem contains polynomials of total degree three in plaintext and ciphertext variables, two in plaintext variables and one in ciphertext variables. However, it is possible to reduce the public key size by writing it as two sets of quadratic multivariate polynomials. The complexity of encryption in our public key cryptosystem is $O(n^{3})$, where $n$ is bit size, which is equivalent to other multivariate public key cryptosystems. For decryption we need only four exponentiations in the binary field. Our Public key algorithm is bijective and can be used for encryption as well as for signatures.

We propose a semantically-secure public-key encryption scheme whose security is polynomial-time equivalent to the hardness of solving random instances of the subset sum problem. The subset sum assumption required for the security of our scheme is weaker than that of existing subset-sum based encryption schemes, namely the lattice-based schemes of Ajtai and Dwork (STOC '97), Regev (STOC '03, STOC '05), and Peikert (STOC '09). Additionally, our proof of security is simple and direct. We also present a natural variant of our scheme that is secure against key-leakage attacks, as well as an oblivious transfer protocol that is secure against semi-honest adversaries.

A pairing-friendly curve is a curve over a finite field whose Jacobian has small embedding degree with respect to a large prime-order subgroup. In this paper we construct pairing-friendly genus 2 curves over finite fields $\mathbb{F}_q$ whose Jacobians are ordinary and simple, but not absolutely simple. We show that constructing such curves is equivalent to constructing elliptic curves over $\mathbb{F}_q$ that become pairing-friendly over a finite extension of $\mathbb{F}_q$. Our main proof technique is Weil restriction of elliptic curves. We describe adaptations of the Cocks-Pinch and Brezing-Weng methods that produce genus 2 curves with the desired properties. Our examples include a parametric family of genus 2 curves whose Jacobians have the smallest recorded $\rho$-value for simple, non-supersingular abelian surfaces.

In this note we first characterize the class of Montgomery curves with B=1 by the simplicity of their transformation into short Weierstrass form and explicitly determine their torsion points of order 2 and 4. We then consider two ``verifiably random'' elliptic curves in the SECG standards and show that they are B=1 Montgomery curves that can also be simply transformed into Edwards form over their ground fields.

Network coding has received significant attention in the networking community for its potential to increase throughput and improve robustness without any centralized control. Unfortunately, network coding is highly susceptible to ``pollution attacks" in which malicious nodes modify packets in a way that prevents the reconstruction of information at recipients; such attacks cannot be prevented using standard end-to-end cryptographic authentication because network coding requires that intermediate nodes modify data packets in transit. Specialized solutions to the problem have been developed in recent years based on homomorphic hashing and homomorphic signatures. The latter are more bandwidth-efficient but require more computation; in particular, the only known construction uses bilinear maps. We contribute to this area in several ways. We present the first homomorphic signature scheme based solely on the RSA assumption (in the random oracle model), and present a homomorphic hashing scheme based on composite moduli that is computationally more efficient than existing schemes (and which leads to secure network coding signatures based solely on the hardness of factoring in the standard model). Both schemes use shorter public keys than previous schemes. In addition, we show variants of existing schemes that reduce the communication overhead significantly for moderate-size networks, and which improve computational efficiency in some cases quite dramatically (e.g., we achieve a 20-fold speedup in the computation of intermediate nodes). At the core of our techniques is a modified approach to network coding where instead of working in a vector space over a field, we work directly over the integers (with small coefficients).

Recently, the $C^{*-}$ signature scheme has been completely broken by Dubois et al. (Dubois et al., CRYPTO and EUROCRYPT 2007). As a consequence, the security of SFLASH and other multivariate public key systems have been impaired. The attacks presented in (Dubois et al., CRYPTO and EUROCRYPT 2007) rely on a symmetry of the differential of the encryption mapping. In (Ding et al., 2007), Ding et al. experimentally justify the use projection as a method of avoiding the new attack. In this paper, we derive some properties of the discrete differential, give a theoretical justification for the reparation in (Ding et al., 2007), and establish the exact context in which this attack is applicable.

Elliptic curves with small embedding degree and large prime-order subgroup are key ingredients for implementing pairing-based cryptographic systems. Such "pairing-friendly" curves are rare and thus require specific constructions. In this paper we give a single coherent framework that encompasses all of the constructions of pairing-friendly elliptic curves currently existing in the literature. We also include new constructions of pairing-friendly curves that improve on the previously known constructions for certain embedding degrees. Finally, for all embedding degrees up to 50, we provide recommendations as to which pairing-friendly curves to choose to best satisfy a variety of performance and security requirements.

In this paper we describe a cryptanalysis of a key exchange scheme recently proposed by Alvarez, Tortosa, Vicent and Zamora. The scheme is based on exponentiation of block matrices over a finite field of prime order. We present an efficient reduction of the problem of disclosing the shared key to the discrete logarithm problem (DLP) in an extension of the base field.

In this paper, we present a new class of linear multivariate PKC referred to as K(I)SE(1)PKC. We shall show that K(I)SE(1)PKC, a linear multivariate PKC, can be sufficiently secure against any linear transformation attack due to the probabilistic structure. We show that the probabilistic structure can be successfully introduced by the use of the Chinese Remainder Theorem.

We study a new generic trapdoor for public key multivariate cryptosystems, called IFS for Intermediate Field Systems, which can be seen as dual to HFE. This new trapdoor relies on the possibility to invert a system of quadratic multivariate equations with few (logarithmic with respect to the security parameter) unknowns on an intermediate field thanks to Groebner bases algorithms. We provide a comprehensive study of the security of this trapdoor and show that it is equivalent to the security provided by HFE. Therefore, while insecure in its basic form, this trapdoor may reveal quite attractive when used with, e.g., the minus modifier.

We develop an abstract framework that encompasses the key properties of bilinear groups of composite order that are required to construct secure pairing-based cryptosystems, and we show how to use prime-order elliptic curve groups to construct bilinear groups with the same properties. In particular, we define a generalized version of the subgroup decision problem and give explicit constructions of bilinear groups in which the generalized subgroup decision assumption follows from the decision Diffie-Hellman assumption, the decision linear assumption, and/or related assumptions in prime-order groups. We apply our framework and our prime-order group constructions to create more efficient versions of cryptosystems that originally required composite-order groups. Specifically, we consider the Boneh-Goh-Nissim encryption scheme, the Boneh-Sahai-Waters traitor tracing system, and the Katz-Sahai-Waters attribute-based encryption scheme. We give a security theorem for the prime-order group instantiation of each system, using assumptions of comparable complexity to those used in the composite-order setting. Our conversion of the last two systems to prime-order groups answers a problem posed by Groth and Sahai.

In this paper, we cryptanalyze two knapsack cryptosystems. The first one is proposed by Hwang et al [4], which is based on a new permutation algorithm named Permutation Combination Algorithm. We show that this permutation algorithm is useless to the security of the cryptosystem. Because of the special super increasing structure, we can break this cryptosystem use the method provided by Shamir at Crypto'82. The second one is provided by Su et al [16], which is based on the elliptic curve discrete logarithm and knapsack problem. We show that one can recover the plaintext as long as he solve a knapsack problem.Unfounately, this knapsack problem can be solved by Shamir's method or the low density attack. Finally, we give a improved version of Su's cryptosystem to avoid these attacks.

In this paper, we define an underlying computational problem and its decisional problem. As an application of their problems, we propose an efficient designated verifier signature (DVS) scheme without random oracles (related to symmetric pairings). We formally redefine the (Strong) Privacy of Signature's Identity, and prove our DVS scheme satisfying security based on the difficulty of the problems. Also we prove that the difficulty of the computational problem is tightly equivalent to the Strong Unforgeability of our proposed conventional signature scheme (without random oracles) related to asymmetric pairings. We believe that our underlying problems are profitable to propose many efficient cryptographic schemes.

Efficiently computable homomorphisms allow elliptic curve point multiplication to be accelerated using the Gallant-Lambert-Vanstone (GLV) method. We extend results of Iijima, Matsuo, Chao and Tsujii which give such homomorphisms for a large class of elliptic curves by working over quadratic extensions and demonstrate that these results can be applied to the GLV method. Our implementation runs in between 0.70 and 0.84 the time of the previous best methods for elliptic curve point multiplication on curves without small class number complex multiplication. Further speedups are possible when using more special curves.

We construct the first public-key encryption scheme in the Bounded-Retrieval Model (BRM), providing security against various forms of adversarial "key leakage" attacks. In this model, the adversary is allowed to learn arbitrary information about the decryption key, subject only to the constraint that the overall amount of "leakage" is bounded by at most L bits. The goal of the BRM is to design cryptographic schemes that can flexibly tolerate arbitrarily leakage bounds L (few bits or many Gigabytes), by only increasing the size of secret key proportionally, but keeping all the other parameters -- including the size of the public key, ciphertext, encryption/decryption time, and the number of secret-key bits accessed during decryption -— small and independent of L. As our main technical tool, we introduce the concept of an Identity-Based Hash Proof System (IB-HPS), which generalizes the notion of hash proof systems of Cramer and Shoup [CS02] to the identity-based setting. We give three different constructions of this primitive based on: (1) bilinear groups, (2) lattices, and (3) quadratic residuosity. As a result of independent interest, we show that an IB-HPS almost immediately yields an Identity-Based Encryption (IBE) scheme which is secure against (small) partial leakage of the target identity’s decryption key. As our main result, we use IB-HPS to construct public-key encryption (and IBE) schemes in the Bounded-Retrieval Model.

Designated verifier signature (DVS) is a cryptographic primitive that allows a signer to convince a verifier the validity of a statement in a way that the verifier is unable to transfer the conviction to a third party. In DVS, signatures are publicly verifiable. The validity of a signature ensures that it is from either the signer or the verifier. Strong DVS (SDVS) enhances the privacy of the signer so that anyone except the designated verifier cannot verify the signer's signatures. In this paper we propose a highly efficient SDVS scheme based on pseudorandom functions, which is proved to be secure in the standard model. Compared with the most efficient SDVS scheme secure in the random oracle model, our scheme has almost the same complexity in terms of both the computational cost of generating a signature and signature size. A signature of our scheme is simply the output of a pseudorandom function. The security of the scheme is tightly reduced to the hardness of DDH problem and the security of the pseudorandom function. Since our scheme is vulnerable to delegatability attacks, the study of which was initiated by Lipmaa, Wang and Bao in ICALP 2005, we then propose another construction of SDVS, which is the \emph{first} one immune to delegatability attacks. The scheme is also very efficient, and has the same signature size with that of Lipmaa-Wang-Bao non-delegatable DVS scheme. We show that it is secure based on discrete logarithm assumption and gap Diffie-Hellman assumption in the random oracle model.

In Undeniable Signature, a signature's validity can only be confirmed or disavowed with the help of an alleged signer via a confirmation or disavowal protocol. A Convertible undeniable signature further allows the signer to release some additional information which can make an undeniable signature become publicly verifiable. In this work we introduce a new kind of attacks, called \emph{claimability attacks}, in which a dishonest/malicious signer both disavows a signature via the disavowal protocol and confirms it via selective conversion. Conventional security requirement does not capture the claimability attacks. We show that some convertible undeniable signature schemes are vulnerable to this kind of attacks. We then propose a new efficient construction of fully functional convertible undeniable signature, which supports both selective conversion and universal conversion, and is immune to the claimability attacks. To the best of our knowledge, it is the most efficient convertible undeniable signature scheme with provable security in the standard model. A signature is comprised of three elements of a bilinear group. Both the selective converter of a signature and the universal converter consist of one group element only. Besides, the confirmation and disavowal protocols are also very simple and efficient. Furthermore, the scheme can be extended to support additional features which include the delegation of conversion and confirmation/disavowal, threshold conversion and etc. We also propose an alternative generic construction of convertible undeniable signature schemes. Unlike the conventional sign-then-encrypt paradigm, the signer encrypts its (standard) signature with an identity-based encryption instead of a public key encryption. It enjoys the advantage of short selective converter, which is simply an identity-based user private key, and security against claimability attacks.

We construct the first public-key encryption scheme that is proven secure (in the standard model, under standard assumptions) even when the attacker gets access to encryptions of arbitrary efficient functions of the secret key. Specifically, under either the DDH or LWE assumption, for every polynomials L and N we obtain a public-key encryption scheme that resists key-dependent message (KDM) attacks for up to N(k) public keys and functions of *circuit size* up to L(k), where k denotes the size of the secret key. We call such a scheme *bounded KDM secure*. Moreover, we show that our scheme suffices for one of the important applications of KDM security: ability to securely instantiate symbolic protocols with axiomatic proofs of security. We also observe that any fully homomorphic encryption scheme which additionally enjoys circular security and circuit privacy is *fully KDM secure* in the sense that the encryption and decryption algorithms can be independent of the polynomials L and N as above. Thus, the recent fully homomorphic encryption scheme of Gentry (STOC 2009) is fully KDM secure under certain non-standard hardness assumptions. Previous works obtained either full KDM security in the random oracle model Black et al (SAC 2002), or security with respect to a very restricted class of functions (e.g., clique/circular security and affine functions, Boneh et al, CRYPTO 2008, and Applebaum et al, CRYPTO 2009). Our main result is based on a combination of the circular-secure encryption scheme of either Boneh et al or Applebaum et al with Yao's garbled circuit construction. Finally, we extend the impossibility result of Haitner and Holenstein (TCC 2009), showing that it is impossible to prove KDM security against a family of query functions that contains exponentially hard pseudorandom functions, using only *black-box* access to the query function and the adversary attacking the scheme. This proves that the non-black-box usage of the query function in our proof of security makes to the KDM query function is *inherent*.

The McEliece cryptosystem is a promising alternative to conventional public key encryption systems like RSA and ECC. In particular, it is supposed to resist even attackers equipped with quantum computers. Moreover, the encryption process requires only simple binary operations making it a good candidate for low cost devices like RFID tags. However, McEliece's original scheme has the drawback that the keys are very large. Two promising variants have been proposed to overcome this disadvantage. The rst one is due to Berger et al. presented at AFRICACRYPT 2009 and the second is due to Barreto and Misoczki presented at SAC 2009. In this paper we rst present a general attack framework and apply it to both schemes subsequently. Our framework allows us to recover the private key for most parameters proposed by the authors of both schemes within at most a few days on a single PC

Network coding allows the routers to mix the received information before forwarding them to the next nodes. Though this information mixing has been proven to maximize network throughput, it also introduces security challenges such as pollution attacks. A malicious node could insert a malicious packet into the system and this corrupted packet will propagate more quickly than in traditional copy-and-forward networks. Several authors have studied secure network coding from both information theoretic and probabilistic viewpoints. In this paper, we show that there are serious flaws in several of these schemes (the security ``proofs'' for these schemes were presented in these publications).

At CHES 2009, Coron, Joux, Kizhvatov, Naccache and Paillier (CJKNP) exhibited a fault attack against RSA signatures with partially known messages. This attack allows factoring the public modulus N. While the size of the unknown message part (UMP) increases with the number of faulty signatures available, the complexity of CJKNP's attack increases exponentially with the number of faulty signatures. This paper describes a simpler attack, whose complexity is polynomial in the number of faults; consequently, the new attack can handle much larger UMPs. The new technique can factor N in a fraction of a second using ten faulty EMV signatures -- a target beyond CJKNP's reach. We show how to apply the attack even when N is unknown, a frequent situation in real-life attacks.

In a proxy re-encryption scheme, a semi-trusted proxy can transform a ciphertext under Alice's public key into another ciphertext that Bob can decrypt. However, the proxy cannot access the plaintext. Due to its transformation property, proxy re-encryption can be used in many applications, such as encrypted email forwarding. In this paper, by using signature of knowledge and Fijisaki-Okamoto conversion, we propose a proxy re-encryption scheme \emph{without} pairings, in which the proxy can only transform the ciphertext in one direction. The proposal is secure against chosen ciphertext attack (CCA) and collusion attack in the \emph{random oracle model} based on Decisional Diffie-Hellman (DDH) assumption over $\mathbb{Z}_{N^2}^*$ and integer factorization assumption, respectively. To the best of our knowledge, it is the \emph{first} unidirectional PRE scheme with CCA security and collusion-resistance.

In order to prevent illegal tracking and stealing personal or cargo information, the authentication services should be provided for the tags to identify a Reader. A NTRU based signature scheme is proposed in this paper, which meets the demand for a group of tags to quickly and securely identify a Reader in RFID system. In our scheme, only the tag in specified group can verify the reader’s message. Because of fast operation, easy key generation and limited source occupied, our signature is very suit for the RFID systems.

We revisit the notion of the anonymous signature, first formalized by Yang, Wong, Deng and Wang, and then further developed by Fischlin, and Zhang and Imai. We present a new formalism of anonymous signature, where instead of the message, a part of the signature is withheld to maintain anonymity. We introduce the notion unpretendability to guarantee infeasibility for someone other than the correct signer to pretend authorship of the message and signature. Our definition retains applicability for all previous applications of the anonymous signature, provides stronger security, and is conceptually simpler. We give a generic construction from any ordinary signature scheme, and also show that the short signature scheme by Boneh and Boyen can be naturally regarded as such a secure anonymous signature scheme according to our formalism.

We investigate the relationships between identity-based non-interactive key distribution and identity-based encryption. We provide constructions for these schemes that make use of general trapdoor discrete log groups. We then investigate the schemes that result in two concrete settings, obtaining new, provably secure, near-practical identity-based encryption schemes.

In a seminal paper of identity based encryption (IBE), Boneh and Franklin [BF01] mentioned an interesting transform from an IBE scheme to a signature scheme, which was observed by Moni Naor. In this paper, we give formal security treatments for this transform and discover several implications and separations among security notions of IBE and transformed signature. For example, we show for such a successful transform, one-wayness of IBE is an essential condition. Additionally, we give a sufficient and necessary condition for converting a semantically secure IBE scheme into an existentially unforgeable signature scheme. Our results help establish strategies on design and automatic security proof of signature schemes from (possibly weak) IBE schemes. We also show some separation results which strongly support that one-wayness, rather than semantic security, of IBE captures an essential condition to achieve secure signature.

In 1998 [8], Patarin proposed an efficient cryptosystem called Little Dragon which was a variant of Matsumoto Imai cryptosystem C¤. However Patarin later found that Little Dragon cryptosystem is not secure [8], [3]. In this paper we propose a public key cryp- tosystem Little Dragon Two which is as e±cient as Little Dragon cryptosystem but secure against all the known attacks. Like little Dragon cryptosystem the public key of Little Dragon Two is of mixed type that is quadratic in plaintext and ciphertext variables. So the public key size of Little Dragon Two is equal to Little Dragon Cryptosystem. Our Public key algorithm is bijective and can be used for both encryption and signatures.

In this short note, we investigate the security of the Unbalanced Oil and Vinegar Scheme \cite{uov}. To do so, we use a hybrid approach for solving the algebraic systems naturally arising when mounting a signature-forgery attack. The basic idea is to compute Gröbner bases of several modified systems rather than a Gröbner basis of the initial system. It turns out that our approach is efficient in practice. We have obtained a complexity bounded from above by $2^{40.3}$ (or $9$ hours of computation) to forge a signature on a set of parameters proposed by the designers of UOV.

In previous work we showed how to compress certain prime-order subgroups of certain cyclotomic subgroups by a factor of 4. We also showed that single-exponentiation can be efficiently performed using compressed representations. In this paper we show that double-exponentiation can be efficiently performed using factor-4 compressed representation of elements. In addition to giving a considerable speed up to the previously known fastest single-exponentiation algorithm for general bases, double-exponentiation can be used to adapt our compression technique to ElGamal type signature schemes.

To encourage research on the hardness of the elliptic-curve discrete-logarithm problem (ECDLP) Certicom has published a series of challenge curves and DLPs. This paper analyzes the costs of breaking the Certicom challenges over the binary fields $\F_{2^{131}}$ and $\F_{2^{163}}$ on a variety of platforms. We describe details of the choice of step function and distinguished points for the Koblitz and non-Koblitz curves. In contrast to the implementations for the previous Certicom challenges we do not restrict ourselves to software and conventional PCs, but branch out to cover the majority of available platforms such as various ASICs, FPGAs, CPUs and the Cell Broadband Engine. For the field arithmetic we investigate polynomial and normal basis arithmetic for these specific fields; in particular for the challenges on Koblitz curves normal bases become more attractive on ASICs and FPGAs.

The inherent key escrow problem is one of the main reasons for the slow adoption of identity-based cryptography. The existing solution for mitigating the key escrow problem is by adopting multiple Private Key Generators (PKGs). Recently, there was a proposal that attempted to reduce the trust of the PKG by allowing a malicious PKG to be caught if he reveals the user's identity-based secret key illegally. Nonetheless, the proposal does not consider that the PKG can simply decrypt the ciphertext instead of revealing the secret key itself (in the case of identity-based encryption schemes). The aim of this paper is to present an escrow-free identity-based signature (IBS) scheme, in which the malicious PKG will be caught if it releases a signature on behalf of the user but signed by itself. We present a formal model to capture such a scheme and provide a concrete construction.

We propose a convertible undeniable signature scheme without random oracles. Our construction is based on Waters' and Kurosawa and Heng's schemes that were proposed in Eurocrypt 2005. The security of our scheme is based on the CDH and the decision linear assumption. Comparing only the part of undeniable signatures, our scheme uses more standard assumptions than the existing undeniable signatures without random oracles due to Laguillamie and Vergnaud.

In 2003, Boneh, Gentry, Lynn and Shacham (BGLS) devised the first provably-secure aggregate signature scheme. Their scheme uses bilinear pairings and their security proof is in the random oracle model. The first pairing-based aggregate signature scheme which has a security proof that does not make the random oracle assumption was proposed in 2006 by Lu, Ostrovsky, Sahai, Shacham and Waters (LOSSW). In this paper, we compare the security and efficiency of the BGLS and LOSSW schemes when asymmetric pairings derived from Barreto-Naehrig (BN) elliptic curves are employed.

Signcryption is a cryptographic primitive that fulfills both the functions of digital signature and public key encryption simultaneously, at a cost significantly lower than that required by the traditional signature-then-encryption approach. In this paper, we address a question whether it is possible to construct a hybrid signcryption scheme in identity-based setting. This question seems to have never been addressed in the literature. We answer the question positively in this paper. In particular, we extend the concept of signcryption key encapsulation mechanism to the identity-based setting. We show that an identity-based signcryption scheme can be constructed by combining an identity-based signcryption key encapsulation mechanism with a data encapsulation mechanism. We also give an example of identity-based signcryption key encapsulation mechanism.