The revolutionary impact offered by identity based cryptography is phenomenal. This novel mechanism was first coined by Adi Shamir in 1984. Since then, several identity based signature schemes were reported. But surprisingly, none of the identity based signature scheme is having the property of determinism and does rely on bilinear pairing. We think positively in answering this long standing question of realizing deterministic identity based signature in composite order groups and we succeed in developing a signature scheme based on RSA assumption and is deterministic. It is indeed helpful in devising variants of signature primitive. Fully aggregateable identity based signature schemes without prior communication between the signing parties is an interesting issue in identity based cryptography. It is easy to see that deterministic identity based signature schemes lead to full aggregation of signatures without the aforementioned overhead. The major contribution of this paper is a novel deterministic identity based signature scheme whose security relies on the strong RSA assumption and random oracles. Based on this newly proposed deterministic identity based signature scheme, we design an identity based aggregate signature scheme which achieves full aggregation in one round. We formally prove the schemes to be existentially unforgeable under adaptive chosen message and identity attack.

Deniable authentication protocols enable a sender to authenticate a message to a receiver such that the receiver is unable to prove the identity of the sender to a third party. In contrast to interactive schemes, non-interactive deniable authentication schemes improve communication efficiency. Currently, several non-interactive deniable authentication schemes have been proposed with provable security in the random oracle model. In this paper, we study the problem of constructing non-interactive deniable authentication scheme secure in the standard model without bilinear groups. An efficient non-interactive deniable authentication scheme is presented by combining the Diffie-Hellman key exchange protocol with authenticated encryption schemes. We prove the security of our scheme by sequences of games and show that the computational cost of our construction can be dramatically reduced by applying pre-computation technique.

Spatial encryption was first proposed by Boneh and Hamburg in 2008. It is one implementation of the generalized identity-based encryption schemes and many systems with a variety of properties can be derived from it. Recently, Hamburg improved the notion by presenting a variant called doubly-spatial encryption. The doubly spatial encryption is more powerful and expressive. More useful cryptography systems can be builded from it, such as attribute-based encryption, etc. However, most presented spatial encryption schemes are proven to be selectively secure. Only a few spatial encryption schemes achieve adaptive security, but not under standard assumptions. And no fully secure doubly-spatial encryption scheme has been presented before. In this paper, we primarily focus on the adaptive security of (doubly-)spatial encryption. A spatial encryption scheme and a doubly-spatial encryption scheme have been proposed. Then we apply the dual system methodology proposed by Waters in the security proof. Both of the schemes can be proven adaptively secure under standard assumptions, the decisional linear (DLIN) assumption and the decisional bilinear Diffie-Hellman (DBDH) assumption, over prime order groups in the standard model. To the best of our knowledge, our second scheme is the first fully secure construction of doubly-spatial encryption.

In this paper, a new class of Public-Key Cryptosystem(PKC) based on Random Simultaneous Equation of degree g(RSE(g)PKC) is presented. The proposed scheme uses a new class of trap-doors based on two classes of transformation, i.e. random transformation and message-dependent random transformation. For constructing the proposed scheme,random transformations X and Ψ are used. The transformation Ψ would yield a breakthrough to a field of multivaliate cryptosystem in a sense that the transformation is dependent on a message. Namely it is a message-dependent transformation on the basis of random coding. We show that the proposed PKC’s, can be secure against the various excellent attacks such as the attack based on the Gr¨obner bases calculation(Gröbner bases attack, GB attack), Patarin’s attack and Braeken-Wolf-Preneel attack, due to the random transformations using new trap-doors.

In this article we show how we can integrate the RSA (RSA-OAEP) into the IBE. Our prove can be make with either Standard Model or Random Oracle. We firstly develop the basic ideas made in this direction, so that to create a novel scheme with which we can signs and crypt at the same time. Then we give our new approach which conserves properly the syntax of the RSA classic. Additionally we compare our authentication with the signature of Shamir. More than that, in the RSA-IBE there is the problem of relating the exponent with an identity. Even if, there was some proposals in this direction, but they operate only with the Random Oracle. And in this article we will response to question of Xuhua Ding and Gene Tsudik, in order to propose an efficient exponent for an RSA-IBE. In the end of the article we give a useful appendix.

This paper presents a fully secure functional encryption scheme for a wide class of relations, that are specified by non-monotone access structures combined with inner-product relations. The security is proven under a standard assumption, the decisional linear (DLIN) assumption, in the standard model. The proposed functional encryption scheme covers, as special cases, (1) key-policy and ciphertext-policy attribute-based encryption with non-monotone access structures, and (2) (hierarchical) predicate encryption with inner-product relations and functional encryption with non-zero inner-product relations.

Gentry's bootstrapping technique is currently the only known method of obtaining a "pure" fully homomorphic encryption (FHE) schemes, and it may offers performance advantages even in cases that do not require pure FHE (such as when using the new noise-control technique of Brakerski-Gentry-Vaikuntanathan). The main bottleneck in bootstrapping is the need to evaluate homomorphically the reduction of one integer modulo another. This is typically done by emulating a binary modular reduction circuit, using bit operations on binary representation of integers. We present a simpler approach that bypasses the homomorphic modular-reduction bottleneck to some extent, by working with a modulus very close to a power of two. Our method is easier to describe and implement than the generic binary circuit approach, and is likely to be faster in practice. In some cases it also allows us to store the encryption of the secret key as a single ciphertext, thus reducing the size of the public key. We also show how to combine our new method with the SIMD homomorphic computation techniques of Smart-Vercauteren and Gentry-Halevi-Smart, to get a bootstrapping method that works in time quasi-linear in the security parameter. This last part requires extending the techniques from prior work to handle arithmetic not only over fields, but also over some rings. (Specifically, our method uses arithmetic modulo a power of two, rather than over characteristic-two fields.)

We prove a higher dimensional generalization of Gross and Zagier's theorem on the factorization of differences of singular moduli. Their result is proved by giving a counting formula for the number of isomorphisms between elliptic curves with complex multiplication by two different imaginary quadratic fields $K$ and $K^\prime$, when the curves are reduced modulo a supersingular prime and its powers. Equivalently, the Gross-Zagier formula counts optimal embeddings of the ring of integers of an imaginary quadratic field into particular maximal orders in $B_{p, \infty}$, the definite quaternion algebra over $\mathbb{Q}$ ramified only at $p$ and infinity. Our work gives an analogous counting formula for the number of simultaneous embeddings of the rings of integers of primitive CM fields into superspecial orders in definite quaternion algebras over totally real fields of strict class number $1$. Our results can also be viewed as a counting formula for the number of isomorphisms modulo $\frak{p} \vert p$ between abelian varieties with CM by different fields. Our counting formula can also be used to determine which superspecial primes appear in the factorizations of differences of values of Siegel modular functions at CM points associated to two different CM fields, and to give a bound on those supersingular primes which can appear. In the special case of Jacobians of genus $2$ curves, this provides information about the factorizations of numerators of Igusa invariants, and so is also relevant to the problem of constructing genus $2$ curves for use in cryptography.

In this paper, we propose two new spatial encryption (SE) schemes based on existing inner product encryption (IPE) schemes. Both of our SE schemes are fully secure under simple assumptions and in prime order bilinear groups. Moreover, one of our SE schemes has constant-size ciphertexts. Since SE implies hierarchical identity-based encryption (HIBE), we also obtain a fully secure HIBE scheme with constant-size ciphertexts under simple assumptions. Our second SE scheme is attribute-hiding (or anonymous). It has sizes of public parameters, secret keys and ciphertexts that are quadratically smaller than the currently known SE scheme with similar properties. As a side result, we show that negated SE is equivalent to non-zero IPE. This is somewhat interesting since the latter is known to be a special case of the former.

The McEliece cryptosystem is one of the few systems to be considered secure against Quantum attacks. The original scheme is built upon Goppa codes and produces very large keys, hence latest research has focused mainly on trying to reduce the public key size. Previous proposals tried to replace the class of Goppa codes with other families of codes, but this revealed to be an insecure choice. In this paper we introduce a construction based on Generalized Srivastava codes, a large class which include Goppa codes as a special case, that allows relatively short public keys without being vulnerable to known structural attacks.

We present the hash-based signature scheme XMSS. It is the first provably (forward) secure and practical signature scheme with minimal security requirements: a pseudorandom and a second preimage resistant (hash) function family. Its signature size is reduced to less than 25% compared to the best provably secure hash based signature scheme.

This article presents a novel pairing algorithm over supersingular genus-$2$ binary hyperelliptic curves. Starting from Vercauteren's work on optimal pairings, we describe how to exploit the action of the $2^{3m}$-th power Verschiebung in order to reduce the loop length of Miller's algorithm even further than the genus-$2$ $\eta_T$ approach. As a proof of concept, we detail an optimized software implementation and an FPGA accelerator for computing the proposed optimal Eta pairing on a genus-$2$ hyperelliptic curve over $\mathbb{F}_{2^{367}}$, which satisfies the recommended security level of $128$ bits. These designs achieve favourable performance in comparison with the best known implementations of $128$-bit-security Type-1 pairings from the literature.

We propose a new homomorphic encryption scheme based on the hardness of decoding under independent random noise from certain affine families of codes. Unlike in previous lattice-based homomorphic encryption schemes, where the message is hidden in the noisy part of the ciphertext, our scheme carries the message in the affine part of the transformation and applies noise only to achieve security. Our scheme can tolerate noise of arbitrary magnitude, as long as the noise vector has sufficiently small hamming weight (and its entries are independent). Our design achieves "proto-homomorphic" properties in an elementary manner: message addition and multiplication are emulated by pointwise addition and multiplication of the ciphertext vectors. Moreover, the extremely simple nature of our decryption makes the scheme easily amenable to bootstrapping. However, some complications are caused by the inherent presence of noticeable encryption error. Our main technical contribution is the development of two new techniques for handling this error in the homomorphic evaluation process. We also provide a definitional framework for homomorphic encryption that may be useful elsewhere.

Cayley hash functions are a particular kind of cryptographic hash functions with very appealing properties. Unfortunately, their security is related to a mathematical problem whose hardness is not very well understood, the {factorization problem in finite groups}. Given a group $G$, a set of generators $\gen$ for this group and an element $g\in G$, the factorization problem asks for a ``short'' representation of $g$ as a product of the generators. In this paper, we provide a new algorithm for solving this problem for the group $G:=\G$. We first reduce the problem to the resolution of a particular kind of multivariate equation over $\fq$. Then, we introduce a dedicated approach to solve this equation with Gröbner bases. We provide a complexity analysis of our approach that is of independent interest from the point of view of Gröbner basis algorithms. Finally, we give the first subexponential time algorithm computing polynomial-length factorizations of any element $g$ with respect to any generator set $\gen$ of $\G$. Previous algorithms only worked for specific generator sets, ran in exponential time or produced factorizations that had at least a subexponential length. In practice, our algorithm beats the birthday-bound complexity of previous attacks for medium and large values of $n$.

Generalized signcryption(GSC) can adaptively work as an encryption scheme, a signature scheme or a signcryption scheme with only one algorithm. In this paper, the formal definition and security notions of multi-receiver identity-based generalized signcryption (MID-GSC) are defined. A concrete scheme is also proposed and proved to be confidential under the Bilinear Diffie-Hellman (BDH) assumption and existential unforgeable under the Computational Diffie-Hellman(CDH) assumption in the random oracle model, which only needs one pairing computation to generalized signcrypt a single message for n receivers using the randomness re-use technique. Compared with other multi-receiver ID-based signcryption schemes, the new scheme is also of high efficiency.

We address a lattice based method on small secret exponent attack on RSA scheme. Boneh and Durfee reduced the attack into finding small roots of a bivariate modular equation: $x(N+1+y)+1 ¥equiv 0 mod e)$, where $N$ is an RSA moduli and $e$ is the RSA public key. Boneh and Durfee proposed a lattice based algorithm for solving the problem. When the secret exponent $d$ is less than $N^{0.292}$, their method breaks RSA scheme. Since the lattice used in the analysis is not full-rank, the analysis is not easy. Bl¥"omer and May gave an alternative algorithm. Although their bound $d ¥leq N^{0.290}$ is worse than Boneh--Durfee result, their method used a full rank lattice. However, the proof for their bound is still complicated. Herrmann and May gave an elementary proof for the Boneh--Durfee's bound: $d ¥leq N^{0.292}$. In this paper, we first give an elementary proof for achieving the bound of Bl¥"omer--May: $d ¥leq N^{0.290}$. Our proof employs unravelled linearization technique introduced by Herrmann and May and is rather simpler than Bl¥"omer--May's proof. Then, we provide a unified framework to construct a lattice that are used for solving the problem, which includes two previous method: Herrmann--May and Bl¥"omer--May methods as a special case. Furthermore, we prove that the bound of Boneh--Durfee: $d ¥leq N^{0.292}$ is still optimal in our unified framework.

Recently two kinds of Huff curves were introduced as elliptic curves models and their arithmetic was studied. It was also shown that they are suitable for cryptographic use such as Montgomery curves or Koblitz curves (in Weierstrass form) and Edwards curves. In this work, we introduce the new generalized Huff curves $ax(y^{2} -c) = by(x^{2}-d)$ with $abcd(a^{2}c-b^{2}d)\neq 0$, which contains the generalized Huff's model $ax(y^{2}- d) = by(x^{2}-d)$ with $abd(a^{2}-b^{2})\neq 0$ of Joye-Tibouchi-Vergnaud and the generalized Huff curves $x(ay^{2} -1) =y(bx^{2}-1)$ with $ab(a-b)\neq 0$ of Wu-Feng as a special case. The addition law in projective coordinates is as fast as in the previous particular cases. More generally all good properties of the previous particular Huff curves, including completeness and independence of two of the four curve parameters, extend to the new generalized Huff curves. We verified that the method of Joye-Tibouchi-Vergnaud for computing of pairings can be generalized over the new curve.

Elliptic Curve Cryptography (ECC) was independently introduced by Koblitz and Miller in the eighties. ECC requires shorter sizes of underlying finite fields in com- parison to other public key cryptosystems such as RSA, introduced by Rivest, Shamir and Adleman. Hyperelliptic curves, a generalization of elliptic curves, require decreas- ing field size as genus increases. Hyperelliptic curves of genus g achieve equivalent security of ECC with field size 1/g times the size of field of ECC for g <= 4. Recently, a lot of research is being focused on increasing the efficiency of hyperelliptic curve cryptosystems (HECC). The most time consuming operation in HECC is the scalar multiplication. At present, scalar multiplication on HECC over prime fields under performs in terms of computational time compared to ECC of equivalent security. This thesis focuses on optimizing HECC scalar multiplication at the point arithmetic level. At the point arithmetic level we obtain more efficient doubling and mixed addi- tion operations to decrease the computational time in the scalar multiplication using binary expansions of scalars. In addition, we introduce tripling operations for the Jacobians of hyperelliptic curves to make use of multibase representations of scalars that are being used effectively in ECC. We also develop double-add operations for semi-affine coordinates and Lange’s new coordinates. We use these double-add opera- tions to improve the computational cost of precomputation for semi-affine coordinates and that of more important main phase of scalar multiplication for semi-affine coor- dinates and Lange’s new coordinates. We derive special addition to improve the cost of precomputation for Lange’s new coordinates and projective coordinates.

In this paper, we present a new class of multivariate public-key cryptosystems, K(XIII)SE(2)PKC realizing the coding rate of exactly 1.0, based on random pseudo cyclic codes. The K(XIII)SE(2)PKC is constructed on the basis of K(IX)SE(1)PKC, formerly presented by the author. We show that K(XIII)SE(2)PKC is secure against the various attacks including the attack based on the Gröbner bases calculaion(GB attack) and the rank attack.

Can one use the discrete logarithm problem in matrix groups, to build a better and secure cryptosystem? We argue, it is indeed the case. This makes the group of circulant matrices suitable and attractive for lightweight cryptography.

In this paper, we prove a closed formula for the degree of regularity of the family of HFE- (HFE Minus) multivariate public key cryptosystems over a finite field of size $q$. The degree of regularity of the polynomial system derived from an HFE- system is less than or equal to \begin{eqnarray*} \frac{(q-1)(\lfloor \log_q(D-1)\rfloor +a)}2 +2 & & \text{if $q$ is even and $r+a$ is odd,} \\ \frac{(q-1)(\lfloor \log_q(D-1)\rfloor+a+1)}2 +2 & & \text{otherwise.} \end{eqnarray*} Here $q$ is the base field size, $D$ the degree of the HFE polynomial, $r=\lfloor \log_q(D-1)\rfloor +1$ and $a$ is the number of removed equations (Minus number). This allows us to present an estimate of the complexity of breaking the HFE Challenge 2: \vskip .1in \begin{itemize} \item the complexity to break the HFE Challenge 2 directly using algebraic solvers is about $2^{96}$. \end{itemize}

Scalar multiplication is an important operation in elliptic curve cryptosystems(ECC). The algorithms for computing scalar multiplication are mostly based on the binary expansions of scalars, such as the non-adjacent form (NAF) and wNAF(sliding window method). Representing scalars using more bases can speed up the scalar multiplication, such as mbNAF, wmbNAF and extended wmbNAF, which was proposed by Longa and Miri in 2008. In this paper, we give a formal analysis of the Hamming weight of the extended wmbNAF method for scalar multiplication on general elliptic curves over large prime fields. Then the cost of this method is compared with NAF and other double-base methods. The analysis shows that we obtain the most efficient algorithm when using (2; 3; 5)NAF_{1;1;0}, which is 9:0% faster than the NAF method without extra storage requirement. Moreover, the recoding algorithm of the extended wmbNAF method is just as simple and fast as that of the NAF method.

In Gentry's fully homoomrphic cryptosystem, a sparse subset sum problem is used and a big set is included in the public key. In the implementation of a variant of Gentry's scheme, to reduce the size of the public key, Gentry and Halevi used a specific form of a sparse subset sum problem with geometric progressions. In this note, we show that their sparse subset sum challenges are rather easy given the aggressive choice of parameters. Our experiment shows that even their large instance of a sparse subset sum problem could be solved within two days with probability of about $44\%$. A more conservative parameter choice can easily avoid our attack.

The Gallant-Lambert-Vanstone (GLV) method is a very efficient technique for accelerating point multiplication on elliptic curves with efficiently computable endomorphisms. Galbraith, Lin and Scott (J. Cryptol. 24(3), 446-469 (2011)) showed that point multiplication exploiting the 2-dimensional GLV method on a large class of curves over GF(p^2) was faster than the standard method on general elliptic curves over GF(p), and left as an open problem to study the case of 4-dimensional GLV on special curves (e.g., j(E) = 0) over GF(p^2). We study the above problem in this paper. We show how to get the 4-dimensional GLV decomposition with proper decomposed coefficients, and thus reduce the number of doublings for point multiplication on these curves to only a quarter. The resulting implementation shows that the 4-dimensional GLV method on a GLS curve runs in about 0.78 the time of the 2-dimensional GLV method on the same curve and in between 0.78-0.87 the time of the 2-dimensional GLV method using the standard method over GF(p). In particular, our implementation reduces by up to 27% the time of the previously fastest implementation of point multiplication on x86-64 processors due to Longa and Gebotys (CHES2010).

The previous I-cache timing attacks on RSA which exploit the instruction path of a cipher were mostly proof-of-concept, and it is harder to put them into practice than D-cache timing attacks. We propose a new trace driven timing attack model based on spying on the whole I-cache. An improved analysis algorithm of the exponent using the characteristic of the size of the window is advanced, which could further reduce the search space of the bits of the key than the former and provide an error detection mechanism to detect some erroneous decisions of the operation sequence. We implemented an attack on RSA of OpenSSL under a practical environment, proving that the feasibility and effectiveness of I-Cache timing attack could be improved.

Public key cryptography has found many applications in our modern society. To guarantee the authenticity of public keys, we need a trusted third party (TTP). In 1991, Girault defined three trust levels for a TTP. The higher the trusted level of the TTP is, the higher the security level of the cryptographic scheme is. In 2007, Hu et al. proposed a generic construction of a certificateless signature scheme, together with a security model, achieving Girault’s level 3 security. In 2011, Fan et al. presented a certificateless short signature scheme based on pairings. In this paper, we consider in depth the security requirements of certificateless signature schemes and show that previous models are inappropriate for achieving the desired level of security. We also present a new security model for a certificateless signature scheme to achieve level 3 security.

Predicate encryption is an important cryptographic primitive (see \cite{BDOP04,BoWa07,Goyal06,KaSaWa08}) that enables fine-grained control on the decryption keys. Roughly speaking, in a predicate encryption scheme the owner of the master secret key $\MSK$ can derive secret key $\SK_P$, for any predicate $P$ from a specified class of predicates $\mathbb{P}$. In encrypting a message $M$, the sender can specify an {\em attribute} vector $\x$ and the resulting ciphertext $\tilde X$ can be decrypted only by using keys $\SK_P$ such that $P(\x)=1$. Our main contribution is the {\em first} construction of a predicate encryption scheme that can be proved {\em fully} secure against {\em unrestricted} queries by probabilistic polynomial-time adversaries under non-interactive constant sized (that is, independent of the length $\ell$ of the attribute vectors) hardness assumptions on bilinear groups of composite order. Specifically, we consider {\em hidden vector encryption} (HVE in short), a notable case of predicate encryption introduced by Boneh and Waters \cite{BoWa07} and further developed in \cite{ShWa08, IoPe08, SLNHJ10}. In a HVE scheme, the ciphertext attributes are vectors $\x=\langle x_1,\ldots,x_\ell\rangle$ of length $\ell$ over alphabet $\Sigma$, keys are associated with vectors $\y=\langle y_1,\ldots,y_\ell\rangle$ of length $\ell$ over alphabet $\Sigma\cup\{\star\}$ and we consider the $\Match(\x,\y)$ predicate which is true if and only if, for all $i$, $y_i\ne\star$ implies $x_i=y_i$. Previous constructions restricted the proof of security to adversaries that could ask only {\em non-matching} queries; that is, for challenge attribute vectors $\x_0$ and $\x_1$, the adversary could ask only for keys of vectors $\y$ for which$\Match(\x_0,\y)=\Match(\x_1,\y)=$ false. Our proof employs the dual system methodology of Waters \cite{Waters09}, that gave one of the first fully secure construction in this area, blended with a careful design of intermediate security games that keep into account the relationship between challenge ciphertexts and key queries.

In this paper, we present a new class of public-key cryptosystems, K(IX)SE(1)PKC realizing the coding rate of exactly 1.0, based on random pseudo cyclic codes. We show that K(IX)SE(1)PKC is secure against the various attacks including the attack based on the Gröbner bases calculaion (GB attack).

The main contributions of this paper are twofold. On the one hand, the twin Diffie-Hellman (twin DH) problem proposed by Cash, Kiltz and Shoup is extended to the $n$-Diffie-Hellman ($n$-DH) problem for an arbitrary integer $n$, and this new problem is shown to be at least as hard as the ordinary DH problem. Like the twin DH problem, the $n$-DH problem remains hard even in the presence of a decision oracle that recognizes solution to the problem. On the other hand, observe that the double-size key in the Cash et al. twin DH based encryption scheme can be replaced by two separated keys each for one entity, that results in a 2-party encryption scheme which holds the same security feature as the original scheme but removes the key redundancy. This idea is further extended to an $n$-party case, which is also known as $n$-out-of-$n$ encryption. As examples, a variant of ElGamal encryption and a variant of Boneh-Franklin IBE have been presented; both of them have proved to be CCA secure under the computational DH assumption and the computational bilinear Diffie-Hellman (BDH) assumption respectively, in the random oracle model. The two schemes are efficient, due partially to the size of their ciphertext, which is independent to the value $n$.

We provide constructions of (m,1)-programmable hash functions (PHFs) for m >= 2. Mimicking certain programmability properties of random oracles, PHFs can, e.g., be plugged into the generic constructions by Hofheinz and Kiltz (J. Cryptol. 2011) to yield digital signature schemes from the strong RSA and strong q-Diffie-Hellman assumptions. As another application of PHFs, we propose new and efficient constructions of digital signature schemes from weaker assumptions, i.e., from the (standard, non-strong) RSA and the (standard, non-strong) q-Diffie-Hellman assumptions. The resulting signature schemes offer interesting trade-offs between efficiency/signature length and the size of the public-keys. For example, our q-Diffie-Hellman signatures can be as short as 200 bits; the signing algorithm of our Strong RSA signature scheme can be as efficient as the one in RSA full domain hash; compared to previous constructions, our RSA signatures are shorter (by a factor of roughly 2) and we obtain a considerable efficiency improvement (by an even larger factor). All our constructions are in the standard model, i.e., without random oracles.

Signcryption is an important cryptographic primitive that simultaneously achieves confidentiality and authentication in an efficient manner. In 2008, Luo et al. introduced the notion of certificate-based signcryption and proposed the first construction of certificate-based signcryption. However, their scheme is insecure under the key replacement attack and also does not provide insider security. To overcome these disadvantages, we introduce a strengthened security model of certificate-based signcryption in this paper. The new security model accurately models insider security and the key replacement attacks that might be attempted by an adversary in a real certificate-based signcryption system. We also propose a new certificate-based signcryption scheme that reaches insider security and resists key replacement attacks. We show that this scheme is both chosen-ciphertext secure and existentially unforgeable in the random oracle model. Furthermore, performance analysis shows that the proposed scheme is efficient and practical.

This paper shows that a $390 mass-market quad-core 2.4GHz Intel Westmere (Xeon E5620) CPU can create 109000 signatures per second and verify 71000 signatures per second on an elliptic curve at a 2^128 security level. Public keys are 32 bytes, and signatures are 64 bytes. These performance figures include strong defenses against software side-channel attacks: there is no data flow from secret keys to array indices, and there is no data flow from secret keys to branch conditions.

The wild McEliece cryptosystem uses wild Goppa codes over finite fields to achieve smaller public key sizes compared to the original McEliece cryptosystem at the same level of security against all attacks known. However, the cryptosystem drops one of the confidence-inspiring shields built into the original McEliece cryptosystem, namely a large pool of Goppa polynomials to choose from. This paper shows how to achieve almost all of the same reduction in key size while preserving this shield. Even if support splitting could be (1) generalized to handle an unknown support set and (2) sped up by a square-root factor, polynomial-searching attacks in the new system will still be at least as hard as information-set decoding. Furthermore, this paper presents a set of concrete cryptanalytic challenges to encourage the cryptographic community to study the security of code-based cryptography. The challenges range through codes over F_2, F_3,..., F_32, and cover two different levels of how much the wildness is hidden.

We give new methods for generating and using ``strong trapdoors'' in cryptographic lattices, which are simultaneously simple, efficient, easy to implement (even in parallel), and asymptotically optimal with very small hidden constants. Our methods involve a new kind of trapdoor, and include specialized algorithms for inverting $\lwe$, randomly sampling $\sis$ preimages, and securely delegating trapdoors. These tasks were previously the main bottleneck for a wide range of cryptographic schemes, and our techniques substantially improve upon the prior ones, both in terms of practical performance and quality of the produced outputs. Moreover, the simple structure of the new trapdoor and associated algorithms can be exposed in applications, leading to further simplifications and efficiency improvements. We exemplify the applicability of our methods with new digital signature schemes and CCA-secure encryption schemes, which have better efficiency and security than the previously known lattice-based constructions.

Proxy signature schemes can be used in many business applications such as when the original signer is not present to sign important documents. Any proxy signature scheme has to meet the identifiability, undeniability, verifiability and unforgeability security requirements. In some conditions, it may be necessary to protect the proxy signer’s privacy from outsiders or third parties. Recently, several studies about proxy signature schemes have been conducted but only Yu et al.’ anonymous proxy signature scheme proposed in 2009 attempting to protect the proxy signer’s privacy from outsiders. They claimed their scheme can make the proxy signer anonymous. However, based on our research, we determined that this was not the case and the proxy signer’s privacy was not anonymous. Hence, in this paper, we propose a new anonymous proxy signature scheme that truly makes the proxy signer anonymous while making it more secure and efficient when compared with Yu et al.’s scheme in 2009. Our proxy signature scheme consists of two constructions. First, we mainly use random numbers and bilinear pairings to attain the anonymous property in our proxy. Secondly, we increase the security, integrity, and efficiency of our proxy through modifications.

In CRYPTO 1997, Canetti \etal put forward the intruiging notion of \emph{deniable encryption}, which (informally) allows a sender and/or receiver, having already performed some encrypted communication, to produce `fake' (but legitimate-looking) random coins that open the ciphertext to another message. Deniability is a powerful notion for both practice and theory: apart from its inherent utility for resisting coercion, a deniable scheme is also noncommitting (a useful property in constructing adaptively secure protocols) and secure under selective-opening attacks on whichever parties can equivocate. To date, however, known constructions have achieved only limited forms of deniability, requiring at least one party to withhold its randomness, and in some cases using an interactive protocol or external parties. In this work we construct \emph{bi-deniable} public-key cryptosystems, in which both the sender and receiver can simultaneously equivocate; we stress that the schemes are noninteractive and involve no third parties. One of our systems is based generically on ``simulatable encryption'' as defined by Damgård and Nielsen (CRYPTO 2000), while the other is lattice-based and builds upon the results of Gentry, Peikert and Vaikuntanathan (STOC 2008) with techniques that may be of independent interest. Both schemes work in the so-called ``multi-distributional'' model, in which the parties run alternative key-generation and encryption algorithms for equivocable communication, but claim under coercion to have run the prescribed algorithms. Although multi-distributional deniability has not attracted much attention, we argue that it is meaningful and useful because it provides credible coercion resistance in certain settings, and suffices for all of the related properties mentioned above.

A deniable cryptosystem allows a sender and a receiver to communicate over an insecure channel in such a way that the communication is still secure even if the adversary can threaten the parties into revealing their internal states after the execution of the protocol. This is done by allowing the parties to change their internal state to make it look like a given ciphertext decrypts to a message different from what it really decrypts to. Deniable encryption was in this way introduced to allow to deny a message exchange and hence combat coercion. Depending on which parties can be coerced, the security level, the flavor and the number of rounds of the cryptosystem, it is possible to define a number of notions of deniable encryption. In this paper we prove that there does not exist any non-interactive receiver-deniable cryptosystem with better than polynomial security. This also shows that it is impossible to construct a non-interactive bi-deniable public-key encryption scheme with better than polynomial security. Specifically, we give an explicit bound relating the security of the scheme to how efficient the scheme is in terms of key size. Our impossibility result establishes a lower bound on the security. As a final contribution we give constructions of deniable public-key encryption schemes which establishes upper bounds on the security in terms of key length. There is a gap between our lower and upper bounds, which leaves the interesting open problem of finding the tight bounds.

We revisit the topic of joint security for combined public key schemes, wherein a single keypair is used for both encryption and signature primitives in a secure manner. While breaking the principle of key separation, such schemes have attractive properties and are sometimes used in practice. We give a general construction for a combined public key scheme having joint security that uses IBE as a component and that works in the standard model. We provide a more efficient direct construction, also in the standard model. We then consider the problem of how to build signcryption schemes from jointly secure combined public key schemes. We provide a construction that uses any such scheme to produce a triple of schemes -- signature, encryption, and signcryption -- that are jointly secure in an appropriate and strong security model.

I continue the discussion initiated in part I of whether or not computer-assisted proofs are a promising approach to preventing errors in reductionist security arguments. I examine some recent papers that describe automated security proofs for hashed ElGamal encryption, Boneh-Franklin identity-based encryption, and OAEP.

In this paper, we propose a forward secure ring signature scheme without random oracles. With forward security, if a secret key of a corresponding ring member is exposed, all previously signed signatures containing this member remain valid. Yet the one who has stolen the secret key cannot produce any valid signature belonged to the past time period. This is especially useful in the case of ring signature, as the exposure of a single secret key may result in the invalidity of thousands or even millions ring signatures which contain that particular user. The only one with this feature relies on random oracles to prove the security. We are the first to construct a forward secure ring signature scheme that can be proven secure without random oracles. Our scheme can be deployed in many applications, such as wireless sensor networks and smart grid system.

NTRU is a fast public key cryptosystem presented in 1996 by Hoffstein, Pipher and Silverman. It operates in the ring of truncated polynomials. In NTRU, a public key is a polynomial defined by the combination of two private polynomials. In this paper, we consider NTRU with two different public keys defined by different private keys. We present a lattice-based attack to recover the private keys assuming that the public keys share polynomials with a suitable number of common coefficients.

At Eurocrypt 2010, Howgrave-Graham and Joux described an algorithm for solving hard knapsacks of density close to 1 in time O(2^0.337n) and memory O(2^0.256n), thereby improving a 30-year old algorithm by Shamir and Schroeppel. In this paper we extend the Howgrave-Graham Joux technique to get an algorithm with running time down to O(2^0.291n). An implementation shows the practicability of the technique. Another challenge is to reduce the memory requirement. We describe a constant memory algorithm based on cycle finding with running time O(2^0.72n); we also show a time-memory tradeoff.

We show how the study of the geometry of the nine flex tangents to a cubic produces many pseudo-parameterizations, including the ones given by Icart, Kammerer, Lercier, Renault and Farashahi.

The prospect of outsourcing an increasing amount of data storage and management to cloud services raises many new privacy concerns for individuals and businesses alike. The privacy concerns can be satisfactorily addressed if users encrypt the data they send to the cloud. If the encryption scheme is homomorphic, the cloud can still perform meaningful computations on the data, even though it is encrypted. In fact, we now know a number of constructions of fully homomorphic encryption schemes that allow arbitrary computation on encrypted data. In the last two years, solutions for fully homomorphic encryption have been proposed and improved upon, but it is hard to ignore the elephant in the room, namely efficiency -- can homomorphic encryption ever be efficient enough to be practical? Certainly, it seems that all known fully homomorphic encryption schemes have a long way to go before they can be used in practice. Given this state of affairs, our contribution is two-fold. First, we exhibit a number of real-world applications, in the medical, financial, and the advertising domains, which require only that the encryption scheme is "somewhat" homomorphic. Somewhat homomorphic encryption schemes, which support a limited number of homomorphic operations, can be much faster, and more compact than fully homomorphic encryption schemes. Secondly, we show a proof-of-concept implementation of the recent somewhat homomorphic encryption scheme of Brakerski and Vaikuntanathan, whose security relies on the "ring learning with errors" (Ring LWE) problem. The system is very efficient, and has reasonably short ciphertexts. Our unoptimized implementation in magma enjoys comparable efficiency to even optimized pairing-based schemes with the same level of security and homomorphic capacity. We also show a number of application-specific optimizations to the encryption scheme, most notably the ability to convert between different message encodings in a ciphertext.

We present collusion attacks against a recently proposed IBE scheme of Chen et al. from ASIACCS 2010. The attacks recover the master secret key of the scheme and thereby invalidate the existing security analysis of this scheme. The attacks are flexible, allowing, for example, the amount of computation needed to be traded-off against the size of the collusion.

Identity-based encryption (IBE) has shown to be a useful cryptographic scheme enabling secure yet flexible role-based access control. We propose a new variant of IBE named as exclusion-intersection encryption: during encryption, the sender can specify the targeted groups that are legitimate and interested in reading the documents; there exists a trusted key generation centre generating the intersection private decryption keys on request. This special private key can only be used to decrypt the ciphertext which is of all the specified groups' interests, its holders are excluded from decrypting when the documents are not targeted to all these groups (e.g., the ciphertext of only a single group's interest). While recent advances in cryptographic techniques (e.g., attribute-based encryption or wicked IBE) can support a more general access control policy, the private key size may be as long as the number of attributes or identifiers that can be specified in a ciphertext, which is undesirable, especially when each user may receive a number of such keys for different decryption power. One of the applications of our notion is to support an ad-hoc joint project of two or more groups which needs extra helpers that are not from any particular group. We also present an online/offline variant such that encryption can be computed quickly after offline pre-computation.

We propose a lattice-based functional encryption scheme for inner product predicates whose security follows from the difficulty of the "learning with errors" (LWE) problem. This construction allows us to achieve applications such as range and subset queries, polynomial evaluation, and CNF/DNF formulas on encrypted data. Our scheme supports inner products over small fields, in contrast to earlier works based on bilinear maps. Our construction is the first functional encryption scheme based on lattice techniques that goes beyond basic identity-based encryption. The main technique in our scheme is a novel twist to the identity-based encryption scheme of Agrawal, Boneh and Boyen (Eurocrypt 2010).

We give an informal analysis and critique of several typical ``provable security'' results. In some cases there are intuitive but convincing arguments for rejecting the conclusions suggested by the formal terminology and ``proofs,'' whereas in other cases the formalism seems to be consistent with common sense. We discuss the reasons why the search for mathematically convincing theoretical evidence to support the security of public-key systems has been an important theme of researchers. But we argue that the theorem-proof paradigm of theoretical mathematics is of limited relevance here and often leads to papers that are confusing and misleading. Because our paper is aimed at the general mathematical public, it is self-contained and as jargon-free as possible.

We examine several versions of the one-more-discrete-log and one-more-Diffie-Hellman problems. In attempting to evaluate their intractability, we find conflicting evidence of the relative hardness of the different problems. Much of this evidence comes from natural families of groups associated with curves of genus 2, 3, 4, 5, and 6. This leads to questions about how to interpret reductionist security arguments that rely on these non-standard problems.

Over a period of sixteen years elliptic curve cryptography went from being an approach that many people mistrusted or misunderstood to being a public key technology that enjoys almost unquestioned acceptance. We describe the sometimes surprising twists and turns in this paradigm shift, and compare this story with the commonly accepted Ideal Model of how research and development function in cryptography. We also discuss to what extent the ideas in the literature on "social construction of technology" can contribute to a better understanding of this history.

We consider the One-Prime-Not-p and All-Primes-But-p variants of the Discrete Logarithm (DL) problem in a group of prime order p. We give reductions to the Diffie-Hellman (DH) problem that do not depend on any unproved conjectures about smooth or prime numbers in short intervals. We show that the One-Prime-Not-p-DL problem reduces to DH in time roughly L_p(1/2); the All-Primes-But-p-DL problem reduces to DH in time roughly L_p(2/5); and the All-Primes-But-p-DL problem reduces to the DH plus Integer Factorization problems in polynomial time. We also prove that under the Riemann Hypothesis, with e*log p queries to a yes-or-no oracle one can reduce DL to DH in time roughly L_p(1/2); and under a conjecture about smooth numbers, with e*log p queries to a yes-or-no oracle one can reduce DL to DH in polynomial time.

At Eurocrypt 2010 van Dijk {\sl et al.} described a fully homomorphic encryption scheme over the integers. The main appeal of this scheme (compared to Gentry's) is its conceptual simplicity. This simplicity comes at the expense of a public key size in ${\cal \tilde O}(\lambda^{10})$ which is too large for any practical system. In this paper we reduce the public key size to ${\cal \tilde O}(\lambda^{7})$ by encrypting with a quadratic form in the public key elements, instead of a linear form. We prove that the scheme remains semantically secure, based on a stronger variant of the approximate-GCD problem, already considered by van Dijk {\sl et al}. We also describe the first implementation of the resulting fully homomorphic scheme. Borrowing some optimizations from the recent Gentry-Halevi implementation of Gentry's scheme, we obtain roughly the same level of efficiency. This shows that fully homomorphic encryption can be implemented using simple arithmetic operations.

In this paper, we analyze the security of the KMOV public key cryptosystem. KMOV is based on elliptic curves over the ring $\mathbb{Z}_n$ where $n=pq$ is the product of two large unknown primes of equal bit-size. We consider KMOV with a public key $(n,e)$ where the exponent $e$ satisfies an equation $ex-(p+1)(q+1)y=z$, with unknown parameters $x$, $y$, $z$. Using Diophantine approximations and lattice reduction techniques, we show that KMOV is insecure when $x$, $y$, $z$ are suitably small.

Cryptosystems based on the hardness of lattice problems have recently acquired much importance due to their average-case to worst-case equivalence, their conjectured resistance to quantum cryptanalysis, their ease of implementation and increasing practicality, and, lately, their promising potential as a platform for constructing advanced functionalities. In this work, we construct “Fuzzy” Identity Based Encryption from the hardness of the standard Learning With Errors (LWE) problem. We give CPA and CCA secure variants of our construction, for small and large universes of attributes. All are secure against selective-identity attacks in the standard model. Our construction is made possible by observing certain special properties that secret sharing schemes need to satisfy in order to be useful for Fuzzy IBE. We discuss why further extensions are not as easy as they may seem. As such, ours is among the first examples of advanced-functionality cryptosystem from lattices that goes “beyond IBE”.

We present a fully homomorphic encryption scheme that is based solely on the (standard) learning with errors (LWE) assumption. Applying known results on LWE, the security of our scheme is based on the worst-case hardness of ``short vector problems'' on arbitrary lattices. Our construction improves on previous works in two aspects: 1. We show that ``somewhat homomorphic'' encryption can be based on LWE, using a new {\em re-linearization} technique. In contrast, all previous schemes relied on complexity assumptions related to ideals in various rings. 2. We deviate from the ``squashing paradigm'' used in all previous works. We introduce a new {\em dimension-modulus reduction} technique, which shortens the ciphertexts and reduces the decryption complexity of our scheme, {\em without introducing additional assumptions}. Our scheme has very short ciphertexts and we therefore use it to construct an asymptotically efficient LWE-based single-server private information retrieval (PIR) protocol. The communication complexity of our protocol (in the public-key model) is $k \cdot \polylog(k)+\log |DB|$ bits per single-bit query (here, $k$ is a security parameter).

We investigate in this paper the security of HFE and Multi-HFE schemes as well as their minus and embedding variants. Multi-HFE is a generalization of the well-known HFE schemes. The idea is to use a multivariate quadratic system -- instead of a univariate polynomial in HFE -- over an extension field as a private key. According to the authors, this should make the classical direct algebraic (message-recovery) attack proposed by Faugère and Joux on HFE no longer efficient against Multi-HFE. We consider here the hardness of the key-recovery in Multi-HFE and its variants, but also in HFE (both for odd and even characteristic). We first improve and generalize the basic key recovery proposed by Kipnis and Shamir on HFE. To do so, we express this attack as matrix/vector operations. In one hand, this permits to improve the basic Kipnis-Shamir (KS) attack on HFE. On the other hand, this allows to generalize the attack on Multi-HFE. Due to its structure, we prove that a Multi-HFE scheme has much more equivalent keys than a basic HFE. This induces a structural weakness which can be exploited to adapt the KS attack against classical modifiers of multivariate schemes such as minus and embedding. Along the way, we discovered that the KS attack as initially described cannot be applied against HFE in characteristic 2. We have then strongly revised KS in characteristic 2 to make it work. In all cases, the cost of our attacks is related to the complexity of solving MinRank. Thanks to recent complexity results on this problem, we prove that our attack is polynomial in the degree of the extension field for all possible practical settings used in HFE and Multi-HFE. This makes then Multi-HFE less secure than basic HFE for equally-sized keys. As a proof of concept, we have been able to practically break the most conservative proposed parameters of multi-HFE in few days (256 bits security broken in 9 days).

In this paper, we give a generalization of Lucas addition chains, where subtraction is allowed. We call them ''Lucas addition-subtraction chain''. We also show that this new method gives minimal addition-subtraction chains for infinitely many integers. This new method will also be used to prove that Lucas addition chains are optimal for many integers. Moreover, we show that Lucas addition chains give minimal addition chains for all integers of Hamming weight $3$, like the \emph{binary method}. Finally, we give a theorem to get short (and many times minimal) Lucas addition-subtraction chains.

In this thesis, we build on Boneh and Hamburg's work on generalized identity-based encryption and spatial encryption. GIBE is a model that covers many of the generalizations of identity-based cryptography that have appeared in the past decade. It is simple and flexible, and can be tuned to different attack models such as selective security. Spatial encryption is an encryption system within the GIBE model. It is designed as a toolbox from which other encryption systems can be built, using linear algebra as an encoding method. It is based on the work of Boneh, Boyen and Goh, and generalizes hierarchical IBE as well as the hierarchical inner-product encryption of Okamoto and Takashima. Here we show several new results related to spatial encryption. We show how to build adaptively secure spatial systems (under a compact but nonstandard assumption) using Lewko and Waters' dual-system encryption. In doing this, we also show how to adapt Lewko and Waters' result to a prime-order setting without sacrificing constant-size ciphertexts. We also show new embeddings of other cryptosystems into spatial encryption. Beyond spatial encryption, we propose a variant called "doubly-spatial encryption", which generalizes both spatial encryption and Attrapadung and Libert's "negated spatial encryption". This generalization adds more flexibility, including more flexible revocation systems and potential improvements in policy language. Unfortunately, we were only able to prove selective security for doubly-spatial encryption, and its ciphertext is no longer constant-size.

It is well known that any encryption scheme which supports any form of homomorphic operation cannot be secure against adaptive chosen ciphertext attacks. The question then arises as to what is the most stringent security definition which is achievable by homomorphic encryption schemes. Prior work has shown that various schemes which support a single homomorphic encryption scheme can be shown to be IND-CCA1, i.e. secure against lunchtime attacks. In this paper we extend this analysis to the recent fully homomorphic encryption scheme proposed by Gentry, as refined by Gentry, Halevi, Smart and Vercauteren. We show that the basic Gentry scheme is not IND-CCA1; indeed a trivial lunchtime attack allows one to recover the secret key. We then show that a minor modification to the variant of the somewhat homomorphic encryption scheme of Smart and Vercauteren will allow one to achieve IND-CCA1, indeed PA-1, in the standard model assuming a lattice based knowledge assumption. We also examine the security of the scheme against another security notion, namely security in the presence of ciphertext validity checking oracles; and show why CCA-like notions are important in applications in which multiple parties submit encrypted data to the ``cloud'' for secure processing.

In this note we remark that the inversion-based selective-ID secure identity-based encryption (IBE) scheme from Boneh and Boyen can be bootstrapped to full-ID security using a technique by Waters.

Signcryption is a cryptographic primitive which performs encryption and signature in a single logical step with the cost lower than signature-then-encryption approach.. In this paper we gave attacks on confidentiality and unforgeability of two identity based signcryption schemes without random oracles. Further we proposed an improved identity based signcryption scheme without random oracles. We also proposed an identity based public verifiable signcryption scheme with third party verification without random oracles.

Generic decoding of linear codes is the best known attack against most code-based cryptosystems. Understanding and measuring the complexity of the best decoding technique is thus necessary to select secure parameters. We consider here the possibility that an attacker has access to many cryptograms and is satisfied by decrypting (i.e.\ decoding) only one of them. We show that, in many cases of interest in cryptology, a variant of Stern's collision decoding can be adapted to gain a factor almost $\sqrt{N}$ when $N$ instances are given. If the attacker has access to an unlimited number of instances, we show that the attack complexity is significantly lower, in fact raised by a power slightly larger than $2/3$. Finally we give indications on how to counter those attacks.

The concept of an aggregate signcryption scheme was first introduced in 2009 by Selvi S.S.D. et. al. in the identity-based setting. The aggregation process of these schemes reduces the amount of exchanged information and is particularly useful in low-bandwidth communication networks and computationally-restricted environments. In this paper, we define a suitable security model for certificateless aggregate signcryption schemes and propose an example which we prove is secure in the random oracle model under the gap Bilinear Diffie-Hellman and computational Diffie-Helman intractability assumptions.

Kabastianskii, Krouk and Smeets proposed in 1997 a digital signature scheme based on a couple of random error-correcting codes. A variation of this scheme was proposed recently and was proved to be EUF-1CMA secure in the random oracle model. In this paper we investigate the security of these schemes and suggest a simple attack based on (essentially) Stern’s algorithm for finding low weight codewords. It efficiently recovers the private key of all schemes of this type existing in the literature. This is basically due to the fact that we can define a code from the available public data with unusual properties: it has many codewords whose support is concentrated in a rather small subset. In such a case, Stern’s algorithm performs much better and we provide a theoretical analysis substantiating this claim. Our analysis actually shows that the insecurity of the proposed parameters is related to the fact that the rates of the couple of random codes used in the scheme were chosen to be too close. This does not compromise the security of the whole KKS scheme. It just points out that the region of weak parameters is really much larger than previously thought.

A new signature system of multivariate public key cryptosys- tem is proposed. The new system, Hidden Pair of Bijection (HPB), is the advanced version of the Complementary STS system. This system real- ized both high security and quick signing. Experiments showed that the cryptanalysis of HPB by Gröbner bases has no less complexity than the random polynomial systems. It is secure against other way of cryptanalysis effective for Complementary STS. On the other hand, since it is based on bijections, signatures exist for any message, unlike other cryptosystems based on non-bijections such as HFE or Unbalanced Oil and Vinegar.

We present a generic transformation that allows us to use a large class of pairing-based signatures to construct schemes for signing group elements in a structure preserving way. As a result of our transformation we obtain a new efficient signature scheme for signing a vector of group elements that is based only on the well established decisional linear assumption (DLIN). Moreover, the public keys and signatures of our scheme consist of group elements only, and a signature is verified by evaluating a set of pairing-product equations. In combination with the Groth-Sahai proof system, such a signature scheme is an ideal building block for many privacy-enhancing protocols. To do this, we start by proposing a new stateful signature scheme for signing vectors of exponents that is F-unforgeable under weak chosen message attacks. This signature scheme is of independent interest as it is compatible with Groth-Sahai proofs and secure under a computational assumption implied by DLIN. Then we give a general transformation for signing group elements based on signatures (for signing exponents) with efficient non-interactive zero-knowledge proofs. This transform also removes any dependence on state in the signature used to sign exponents. Finally, we obtain our result by instantiating this transformation with the above signature scheme and Groth-Sahai proofs.

We revisit the definition of unforgeability of blind signatures as proposed by Pointcheval and Stern (Journal of Cryptology 2000). Surprisingly, we show that this established definition falls short in two ways of what one would intuitively expect from a secure blind signature scheme: It is not excluded that an adversary submits the same message $m$ twice for signing, and then produces a signature for $m'\neq m$. The reason is that the forger only succeeds if \emph{all} messages are distinct. Moreover, it is not excluded that an adversary performs $k$ signing queries and produces signatures on $k+1$ messages as long as \emph{each} of these signatures does not pass verification with probability~$1$. Finally, we proposed a new definition, honest-user unforgeability, that covers these attacks. We give a simple and efficient transformation that transforms any unforgeable blind signature scheme (with deterministic verification) into an honest-user unforgeable one.

We introduce a new \emph{lattice-based} cryptographic structure called a \emph{bonsai tree}, and use it to resolve some important open problems in the area. Applications of bonsai trees include: \begin{itemize} \item An efficient, stateless `hash-and-sign' signature scheme in the \emph{standard model} (i.e., no random oracles), and \item The first \emph{hierarchical} identity-based encryption (HIBE) scheme (also in the standard model) that does not rely on bilinear pairings. \end{itemize} Interestingly, the abstract properties of bonsai trees seem to have no known realization in conventional number-theoretic cryptography.

For over two decades, timing attacks have been an active area of research within applied cryptography. These attacks exploit cryptosystem or protocol implementations that do not run in constant time. When implementing an elliptic curve cryptosystem with a goal to provide side-channel resistance, the scalar multiplication routine is a critical component. In such instances, one attractive method often suggested in the literature is Montgomery's ladder that performs a fixed sequence of curve and field operations. This paper describes a timing attack vulnerability in OpenSSL's ladder implementation for curves over binary fields. We use this vulnerability to steal the private key of a TLS server where the server authenticates with ECDSA signatures. Using the timing of the exchanged messages, the messages themselves, and the signatures, we mount a lattice attack that recovers the private key. Finally, we describe and implement an effective countermeasure.

Identity-based decryption is an alternative to identity-based encryption, in which Alice encrypts a symmetric key for Bob under a trusted authority’s public key. Alice sends Bob the resulting ciphertext, which Bob can send to the trusted authority. The trusted authority provides Bob the symmetric key only upon verifying Bob’s identity.

In this paper we present a new practical key-recovery attack on the SFLASH signature scheme. SFLASH is a derivative of the older $C^*$ encryption and signature scheme that was broken in 1995 by Patarin. In SFLASH, the public key is truncated, and this simple countermeasure prevents Patarin's attack. The scheme is well-known for having been considered secure and selected in 2004 by the NESSIE project of the European Union to be standardized. However, SFLASH was practically broken in 2007 by Dubois, Fouque, Stern and Shamir. Their attack breaks the original (and most relevant) parameters, but does not apply when more than half of the public key is truncated. It is therefore possible to choose parameters such that SFLASH is not broken by the existing attacks, although it is less efficient. We show a key-recovery attack that breaks the full range of parameters in practice, as soon as the information-theoretically required amount of information is available from the public-key. The attack uses new cryptanalytic tools, most notably pencils of matrices and quadratic forms.

We introduce a new combinatorial primitive called *programmable hash functions* (PHFs). PHFs can be used to *program* the output of a hash function such that it contains solved or unsolved discrete logarithm instances with a certain probability. This is a technique originally used for security proofs in the random oracle model. We give a variety of *standard model* realizations of PHFs (with different parameters). The programmability makes PHFs a suitable tool to obtain black-box proofs of cryptographic protocols when considering adaptive attacks. We propose generic digital signature schemes from the strong RSA problem and from some hardness assumption on bilinear maps that can be instantiated with any PHF. Our schemes offer various improvements over known constructions. In particular, for a reasonable choice of parameters, we obtain short standard model digital signatures over bilinear maps.

Deniable encryption, introduced in 1997 by Canetti, Dwork, Naor, and Ostrovsky, guarantees that the sender or the receiver of a secret message is able to "fake" the message encrypted in a specific ciphertext in the presence of a coercing adversary, without the adversary detecting that he was not given the real message. To date, constructions are only known either for weakened variants with separate "honest" and "dishonest" encryption algorithms, or for single-algorithm schemes with non-negligible detection probability. We propose a sender-deniable public key encryption system with a single encryption algorithm. We describe a generic interactive construction based on a public key bit encryption scheme that has certain properties, and we give two examples of encryption schemes with these properties, one based on the quadratic residuosity assumption and the other on trapdoor permutations. Subsequent to the publication of this work in EUROCRYPT 2011, it was shown by Peikert and Waters that, contrary to our initial claim, the proposed scheme does not have negligible detection probability. In this updated version we describe the attack of Peikert and Waters and the error in our original proof. We include the previous version of the paper with the construction and the (incorrect) security theorem.

Recently in Chinese Journal of Computers, Kang et al. [12] proposed an efficient CCA secure public key encryption (PKE) scheme, and claimed that it is more efficient in the public/private keys than the famous CS98 and BMW05 CCA secure public key encryption scheme. However, in this paper we will show that their proposal is not secure at all. Furthermore, we improve their scheme to be a secure one and prove its security.

We propose a linearly homomorphic signature scheme that authenticates vector subspaces of a given ambient space. Our system has several novel properties not found in previous proposals: - It is the first such scheme that authenticates vectors defined over *binary fields*; previous proposals could only authenticate vectors with large or growing coefficients. - It is the first such scheme based on the problem of *finding short vectors in integer lattices*, and thus enjoys the worst-case security guarantees common to lattice-based cryptosystems. Our scheme can be used to authenticate linear transformations of signed data, such as those arising when computing mean and Fourier transform or in networks that use network coding. Our construction gives an example of a cryptographic primitive --- homomorphic signatures over $\mathbb{F}_2$ --- that can be built using lattice methods, but cannot currently be built using bilinear maps or other traditional algebraic methods based on factoring or discrete-log type problems. Security of our scheme (in the random oracle model) is based on a new hard problem on lattices, called k-SIS, that reduces to standard average-case and worst-case lattice problems. Our formulation of the k-SIS problem adds to the ``toolbox'' of lattice-based cryptography and may be useful in constructing other lattice-based cryptosystems. As a second application of the new k-SIS tool, we construct an ordinary signature scheme and prove it k-time unforgeable in the standard model assuming the hardness of the k-SIS problem. Our construction can be viewed as ``removing the random oracle'' from the signatures of Gentry, Peikert, and Vaikuntanathan at the expense of only allowing a small number of signatures.

In this work, we study (the direct constructions of) bidirectional proxy re-encryption (PRE) with alleviated trust in the proxy, specifically the master secret security (MSS) and the non-transitivity (NT) security, in the standard model, and achieve the following: 1. A multi-hop MSS-secure bidirectional PRE scheme with security against chosen plaintext attacks (CPA) in the standard model, where the ciphertext remains constant size regardless of how many times it has been re-encrypted. To the best of our knowledge, there exists previously no MSS-secure multi-hop bidirectional PRE scheme with constant size of ciphertexts (whether in the random oracle model or not). 2. A single-hop MSS-secure and non-transitive bidirectional PRE scheme with security against chosen ciphertext attacks (CCA) in the standard model. The CCA-secure scheme is based on the CPA-secure scheme, and particularly employs a new re-encryption key (REK) generation mechanism to which each user makes equal contributions, where a \emph{single} REK is used in both directions with the same proxy computation. Single-hop non-transitive bidirectional PRE schemes also enjoy better fine-grained delegate right control (against malicious proxy). The security analysis uses Coron's technique [Coron, Crypto 2000], which particularly allows adaptive secret key corruption. Along the way, we also refine and clarify the security models for bidirectional PRE.

In this paper, we present an improved Rivest's ring signature scheme. In our scheme, the size of the signature is only related to the ring members, and the signer needs no to publish amount of random numbers. On this basis, we propose a group-oriented ring signature. In this scheme, only the person who belongs to the designated group can verify the validity of the ring signature. The security of these two schemes can be proved by using Forking Lemmas.

Strong lattice reduction is the key element for most attacks against lattice-based cryptosystems. Between the strongest but impractical HKZ reduction and the weak but fast LLL reduction, there have been several attempts to find efficient trade-offs. Among them, the BKZ algorithm introduced by Schnorr and Euchner [FCT'91] seems to achieve the best time/quality compromise in practice. However, no reasonable complexity upper bound is known for BKZ, and Gama and Nguyen [Eurocrypt'08] observed experimentally that its practical runtime seems to grow exponentially with the lattice dimension. In this work, we show that BKZ can be terminated long before its completion, while still providing bases of excellent quality. More precisely, we show that if given as inputs a basis $(b_i)_{i\leq n} \in Q^{n \times n}$ of a lattice L and a block-size $\beta$, and if terminated after $\Omega\left(\frac{n^3}{\beta^2}(\log n + \log \log \max_i \|\vec{b}_i\|)\right)$ calls to a $\beta$-dimensional HKZ-reduction (or SVP) subroutine, then BKZ returns a basis whose first vector has norm $\leq 2 \gamma_{\beta}^{\frac{n-1}{2(\beta-1)}+\frac{3}{2}} \cdot (\det L)^{\frac{1}{n}}$, where~$\gamma_{\beta} \leq \beta$ is the maximum of Hermite's constants in dimensions $\leq \beta$. To obtain this result, we develop a completely new elementary technique based on discrete-time affine dynamical systems, which could lead to the design of improved lattice reduction algorithms.

We investigate public key encryption that allows the originator of a ciphertext to retrieve a ``forgotten'' plaintext from the ciphertext. This type of public key encryption with ``backward recovery'' contrasts more widely analyzed public key encryption with ``forward secrecy''. We advocate that together they form the two sides of a whole coin, whereby offering complementary roles in data security, especially in cloud computing, 3G/4G communications and other emerging computing and communication platforms. We formalize the notion of public key encryption with backward recovery, and present two construction methods together with formal analyses of their security. The first method embodies a generic public key encryption scheme with backward recovery using the ``encrypt then sign" paradigm, whereas the second method provides a more efficient scheme that is built on Hofheinz and Kiltz's public key encryption in conjunction with target collision resistant hashing. Security of the first method is proved in a two-user setting, whereas the second is in a more general multi-user setting.

In this paper, we propose a short and efficient certificate-based signature (CBS) scheme. Certificate-based cryptography proposed by Gentry \cite{Gentry03} combines the merit of traditional public key cryptography (PKI) and identity based cryptography, without use of the costly certificate chain verification process and the removal of key escrow security concern. Under this paradigm, we propose the shortest certificate-based signature scheme in the literature. We require one group element for the signature size and public key respectively. Thus the public information for each user is reduced to just one group element. It is even shorter than the state-of-the-art PKI based signature scheme, which requires one group element for the public key while another group element for the certificate. Our scheme is also very efficient. It just requires one scalar elliptic curve multiplication for the signing stage. Our CBS is particularly useful in power and bandwidth limited environment such as Wireless Cooperative Networks.

With a significant advance in ciphertext searchability, Public-key encryption with keyword search (PEKS) is the first keyword searchable encryption scheme based on the probabilistic encryption, such that it is more secure than almost all previous schemes. However, there is an open problem in PEKS that its search complexity is linear with the sum of ciphertexts, such that it is inefficient for a mass of ciphertexts. Fortunately, we find an elegant method that by adaptively taking the keyword trapdoor of each query as an index, the search complexity of the queried keywords can be decreased in a huge degree. We call this method dynamic index (DI) technique. Furthermore, for keywords having not been queried before, we employ deterministic encryption to establish indexes to decrease their first search complexity. We call this method static index (SI) technique. Consequently, we propose a secure hybrid search (SHS) system by combing DI and SI techniques in PEKS to decrease the search complexity of PEKS. At last, we demonstrate its semantic security and convergent search complexity, which is considerably lower than that of PEKS.

After the introduction of designated confirmer signatures (DCS) by Chaum in 1994, considerable researches have been done to build generic schemes from standard digital signatures and construct efficient concrete solutions. In DCS schemes, a signature cannot be verified without the help of either the signer or a semi-trusted third party, called the designated confirmer. If necessary, the confirmer can further convert a DCS into an ordinary signature that is publicly verifiable. However, there is one limit in most existing schemes: the signer is not given the ability to disavow invalid DCS signatures. Motivated by this observation, in this paper we first propose a new variant of DCS model, called designated confirmer signatures with unified verification}, in which both the signer and the designated confirmer can run the same protocols to confirm a valid DCS or disavow an invalid signature. Then, we present the first DCS scheme with unified verification and prove its security in the random oracle (RO) model and under a new computational assumption, called Decisional Co-efficient Linear (D-co-L) assumption, whose intractability in pairing settings is shown to be equivalent to the well-known Decisional Bilinear Diffie-Hellman (DBDH) assumption. The proposed scheme is constructed by encrypting Boneh, Lynn and Shacham's pairing based short signatures with signed ElGamal encryption. The resulting solution is efficient in both aspects of computation and communication. In addition, we point out that the proposed concept can be generalized by allowing the signer to run different protocols for confirming and disavowing signatures.

Recently, a lot of progresses have been made in software implementations of pairings at the 128-bit security level in large characteristic. In this work, we obtain analogous progresses for hardware implementations. For this, we use the RNS representation of numbers which is especially well suited for pairing computation in a hardware context. A FPGA implementation is proposed, based on an adaptation of Guillermin's architecture which computes a pairing in 1.07 ms. It is 2 times faster than all previous hardware implementations (including ASIC and small characteristic implementations) and almost as fast as best software implementations.

We construct the first homomorphic signature scheme that is capable of evaluating multivariate polynomials on signed data. Given the public key and a signed data set, there is an efficient algorithm to produce a signature on the mean, standard deviation, and other statistics of the signed data. Previous systems for computing on signed data could only handle linear operations. For polynomials of constant degree, the length of a derived signature only depends logarithmically on the size of the data set. Our system uses ideal lattices in a way that is a ``signature analogue'' of Gentry's fully homomorphic encryption. Security is based on hard problems on ideal lattices similar to those in Gentry's system.

Cloud computing is a style of computing in which dynamically scalable and commonly virtualized resources are provided as a service over the Internet. This paper, first presents a novel Hierarchical Architecture for Cloud Computing (HACC). Then, Identity-Based Encryption (IBE) and Identity-Based Signature (IBS) for HACC are proposed. Finally, an Authentication Protocol for Cloud Computing (APCC) is presented. Performance analysis indicates that APCC is more efficient and lightweight than SSL Authentication Protocol (SAP), especially for the user side. This aligns well with the idea of cloud computing to allow the users with a platform of limited performance to outsource their computational tasks to more powerful servers.

Due to the possibility of key exposure, forward security in encryption and signing has been well studied, especially in the identity-based setting where an entity's public key is that entity's name. From an efficiency point of view, one would like to use the signcryption primitive and have the best of both worlds. However, strong forward security, where the adversary cannot signcrypt in sender's name nor designcrypt in receiver's name for past time periods even if it has the secrets of both, requires periodic updating of the secret keys of the users. This is an improvement over signcryption schemes that only protect against designcrypting in the past. In this paper, we propose the first ever strong forward secure identity-based signcryption scheme which has public ciphertext verifiability and a third-party verification protocol.

Finding the shortest vector of a lattice is one of the most important problems in computational lattice theory. For a random lattice, one can estimate the length of the shortest vector using the Gaussian heuristic. However, no rigorous proof can be provided for some classes of lattices, as the Gaussian heuristic may not hold for them. In the paper we study two types of random lattices in cryptography: the knapsack lattices and the NTRU lattices. For random knapsack lattices, we prove lower bounds of shortest vector lengths, which are very close to lengths predicted by the Gaussian heuristic. For a random NTRU lattice, we prove that with a overwhelming probability, the ratio between the length of the shortest vector and the length of the target vector, which corresponds to the secret key, is at least a constant, independent of the dimension of the lattice. The main technique we use is the incompressibility method from the theory of Kolmogorov complexity.

In this paper, we compute $\ell$-isogenies between abelian varieties over a field of characteristic different from $2$ in polynomial time in $\ell$, when $\ell$ is an odd prime which is coprime to the characteristic. We use level~$n$ symmetric theta structure where $n=2$ or $n=4$. In a second part of this paper we explain how to convert between Mumford coordinates of Jacobians of genus~$2$ hyperelliptic curves to theta coordinates of level~$2$ or $4$. Combined with the preceding algorithm, this gives a method to compute $(\ell,\ell)$-isogenies in polynomial time on Jacobians of genus~$2$ curves.

We count the number of isogeny classes of Edwards curves over finite fields, answering a question recently posed by Rezaeian and Shparlinski. We also show that each isogeny class contains a {\em complete} Edwards curve, and that an Edwards curve is isogenous to an {\em original} Edwards curve over $\F_q$ if and only if its group order is divisible by $8$ if $q \equiv -1 \pmod{4}$, and $16$ if $q \equiv 1 \pmod{4}$. Furthermore, we give formulae for the proportion of $d \in \F_q \setminus \{0,1\}$ for which the Edwards curve $E_d$ is complete or original, relative to the total number of $d$ in each isogeny class.

We provide a formalization of the emergent notion of ``functional encryption,'' as well as introduce various security notions for it, and study relations among the latter. In particular, we show that indistinguishability and semantic security based notions of security are {\em inequivalent} for functional encryption in general; in fact, ``adaptive'' indistinguishability does not even imply ``non-adaptive'' semantic security. This is alarming given the large body of work employing (special cases of) the former. We go on to show, however, that in the ``non-adaptive'' case an equivalence does hold between indistinguishability and semantic security for what we call {\em preimage sampleable} schemes. We take this as evidence that for preimage sampleable schemes an indistinguishability based notion may be acceptable in practice. We show that some common functionalities considered in the literature satisfy this requirement.

In this paper, we present a new class of knapsack type PKC referred to as K(III)$\Sigma$PKC. In a sharp contrast with the conventional knapsack type PKC's, in our proposed scheme, K(III)$\Sigma$PKC, no conventional secret sequence but the natural binary number with noise is used. We show that the coding rate, a more conservative measure for the security on knapsack PKC, can be made approximately 1.0. In Appendix, we present K(II)$\Sigma$PKC.

In this paper, we present a new secret sharing scheme, referred to as KSS(I) on the basis of systematic Reed-Solomon code[2]. We show that KSS(I) can be successfully applied to biometrics.

We show how to achieve public-key encryption schemes that can securely encrypt nonlinear functions of their own secret key. Specifically, we show that for any constant $d\in\mathbb{N}$, there exists a public-key encryption scheme that can securely encrypt any function $f$ of its own secret key, assuming $f$ can be expressed as a polynomial of total degree~$d$. Such a scheme is said to be key-dependent message (KDM) secure w.r.t.\ degree-$d$ polynomials. We also show that for any constants $c,e$, there exists a public-key encryption scheme that is KDM secure w.r.t.\ all Turing machines with description size $c\log \lambda$ and running time $\lambda^e$, where $\lambda$ is the security parameter. The security of such public-key schemes can be based either on the standard decision Diffie-Hellman (DDH) assumption or on the learning with errors (LWE) assumption (with certain parameters settings). In the case of functions that can be expressed as degree-$d$ polynomials, we show that the resulting schemes are also secure with respect to \emph{key cycles} of any length. Specifically, for any polynomial number $n$ of key pairs, our schemes can securely encrypt a degree-$d$ polynomial whose variables are the collection of coordinates of all $n$ secret keys. Prior to this work, it was not known how to achieve this for nonlinear functions. Our key idea is a general transformation that amplifies KDM security. The transformation takes an encryption scheme that is KDM secure w.r.t.\ \emph{some} functions even when the secret keys are weak (i.e.\ chosen from an arbitrary distribution with entropy~$k$), and outputs a scheme that is KDM secure w.r.t.\ a \emph{richer} class of functions. The resulting scheme may no longer be secure with weak keys. Thus, in some sense, this transformation converts security with weak keys into amplified KDM security.

We show that the elliptic curve Qu-Vanstone implicit certificate scheme (ECQV), when composed with the Elliptic Curve Digital Signature Algorithm (ECDSA), is secure against passive adversaries under the combined assumption of the random oracle model and the generic group model,---if the ECQV certificate itself is excluded from the signable message space, because of an attack of Kravitz. In contrast, we detail an attack on the composition of another implicit certificate scheme, proposed by Pintsov and Vanstone for Optimal Mail Certificates (OMC), and ECDSA. This composition attack forges an implicitly certified ECDSA signature, and is passive in the sense of needing no interaction with the signer or the certification authority. (Pintsov and Vanstone did not propose combining OMC with ECDSA.)

Undeniable signatures, introduced by Chaum and van Antwerpen, and designated confirmer signatures, introduced by Chaum, allow a signer to control the verifiability of his signatures by requiring a verifier to interact with the signer to verify a signature. An important security requirement for these types of signature schemes is \emph{non-transferability} which informally guarantees that even though a verifier has confirmed the validity of a signature by interacting with the signer, he cannot prove this knowledge to a third party. Recently Liskov and Micali pointed out that the commonly used notion of non-transferability only guarantees security against an off-line attacker which cannot influence the verifier while he interacts with the signer, and that almost all previous schemes relying on interactive protocols are vulnerable to on-line attacks. To address this, Liskov and Micali formalized on-line non-transferable signatures which are resistant to on-line attacks, and proposed a generic construction based on a standard signature scheme and an encryption scheme. In this paper, we revisit on-line non-transferable signatures. Firstly, we extend the security model of Liskov and Micali to cover not only the sign protocol, but also the confirm and disavow protocols executed by the confirmer. Our security model furthermore considers the use of multiple (potentially corrupted or malicious) confirmers, and guarantees security against attacks related to the use of signer specific confirmer keys. We then present a new approach to the construction of on-line non-transferable signatures, and propose a new concrete construction which is provably secure in the standard model. Unlike the construction by Liskov and Micali, our construction does not require the signer to issue ``fake'' signatures to maintain security, and allows the confirmer to both confirm and disavow signatures. Lastly, our construction provides noticeably shorter signatures than the construction by Liskov and Micali.

In this work we construct public key encryption schemes that admit a protocol for /blindly/ decrypting ciphertexts. In a blind decryption protocol, a user with a ciphertext interacts with a secret keyholder such that the user obtains the decryption of the ciphertext and the keyholder learns nothing about what it decrypted. While we are not the first to consider this problem, previous works provided only weak security guarantees against malicious users. We provide, to our knowledge, the first practical blind decryption schemes that are secure under a strong CCA security definition. We prove our construction secure in the standard model under simple, well-studied assumptions in bilinear groups. To motivate the usefulness of this primitive we discuss several applications including privacy-preserving distributed file systems and Oblivious Transfer schemes that admit /public/ contribution.

Broadcast encryption provides a convenient method to distribute digital content to subscribers over an insecure broadcast channel. Traitor tracing is needed because some users may give out their decryption keys to construct pirate decoders. There are many traitor tracing schemes based on collusion secure codes and identifiable parent property codes. However, these schemes are subject to public collaboration of traitors, which is presented by Billet and Phan in EUROCRYPT 2009 as an attack against code-based traitor tracing schemes. In this paper, we describe a generic collusion secure codes based scheme secure against such collaboration. Our scheme is motivated by the idea of identity-based encryption with wildcards (WIBE). We regard the collusion secure codeword for each user as his/her identity, and issue private key accordingly. When in broadcasting, we use a special pattern of WIBE, namely all bit positions in the codewords of intended receivers are set as wildcards. When in tracing, we use another special pattern of WIBE, namely all positions are set as wildcards except the tracing position. By using WIBE, each user is issued one decryption key which should be used as a whole and any incomplete part of the key is useless, while in previous codes based schemes each user holds a number of keys that can be used separately for different bit positions in the codeword. Thus our scheme is resistant to public collaboration, since if the decryption key is disclosed as a whole, it will immediately lead to the accusation of the very traitor. Our idea fits well for code based traitor tracing schemes, no matter collusion secure codes or identifiable parent property codes. We provide an instance based on Boneh-Boyen-Goh WIBE scheme, achieving constant private key storage cost for each user. We also present another instance achieving shorter ciphertexts, on the expense of increasing public keys and private keys. Our scheme presents an answer to the problem left open by Billet and Phan.

We show that Katz-Wang’s duplicating key and ciphertext technique can be extended to a generic method that can be used in a certain category of Identity-Based Encryption (IBE) schemes for the purposes of improving their security reductions. We further develop two refined approaches by adapting the randomness reuse technique in the Katz-Wang technique: one is public key duplication, and the other is master key duplication. Compared to the Katz-Wang technique, our two refined approaches do not only improve the performances of the resulting IBE schemes but also enable a reduction algorithm to deal with decryption queries correctly and therefore can achieve chosen ciphertext security. As case studies, we apply these two approaches to modify the Boneh- Franklin IBE scheme and the Boneh-Boyen IBE scheme, respectively. Both of the modifications improve the tightness of security reductions, compared to the original schemes, with a reasonably low cost.

Many identity-based digital signature schemes using bilinear pairings have been proposed. But the relative computation cost of the pairing is approximately twenty times higher than that of the scalar multiplication over elliptic curve group. In order to save the running time and the size of the signature, we propose an identity based signature scheme without bilinear pairings. With both the running time and the size of the signature being saved greatly, our scheme is more practical than the previous related schemes for practical application.

We cryptanalyse a matrix-based key transport protocol due to Baumslag, Camps, Fine, Rosenberger and Xu from 2006. We also cryptanalyse two recently proposed matrix-based key agreement protocols, due to Habeeb, Kahrobaei and Shpilrain, and due to Romanczuk and Ustimenko.