Search

The beauty of identity-based encryption (IBE) lies in the convenience of public key handling, in the sense that any identification such as an email address, a name, or an IP number can serve as a public key of a party. However, such convenience is not inherited by a system where a party possesses many identities (e.g., many email addresses) and has to use them as his public keys. When this system is handled with a standard IBE, the user must manage all the private keys that are associated with all the public keys (identities). However, keeping these private keys is inconvenient to the user. In this paper, we solve this problem by proposing a novel identity-based encryption where we set a private key that maps multiple public keys (identities); namely, we can use a private key to decrypt multiple ciphertexts; each was encrypted with a different public key (identity). [ABSTRACT FROM AUTHOR]

We derive a new algorithm for computing the Tate pairing on an elliptic curve over a finite field. The algorithm uses a generalisation of elliptic divisibility sequences known as elliptic nets, which are maps from ℤn to a ring that satisfy a certain recurrence relation. We explain how an elliptic net is associated to an elliptic curve and reflects its group structure. Then we give a formula for the Tate pairing in terms of values of the net. Using the recurrence relation we can calculate these values in linear time. Computing the Tate pairing is the bottleneck to efficient pairing-based cryptography. The new algorithm has time complexity comparable to Miller's algorithm, and should yield to further optimisation. [ABSTRACT FROM AUTHOR]

Undeniable signatures, introduced by Chaum and van Antwerpen, is a useful cryptography primitive to limit the publicly verifiable property of ordinary digital signatures. In an undeniable signature scheme, the validity or invalidity of the signature can only be verified via the confirmation/disavowal protocol with the help of the signer. An extended concept, convertible undeniable signatures, was introduced by Boyar, Chaum, Damgård and Pedersen. In the new concept, the signer can publish some selective proofs to convert one or more undeniable signatures into publicly verifiable ones, or issue a universal proof to make all his undeniable signatures publicly verifiable. In this paper, we first present a security model for convertible undeniable signature schemes, and then propose a new construction from bilinear pairings. Compared with the other schemes in the literature, the new construction has three advantages: Our scheme is both selectively and universally convertible; the signature length of our scheme is as short as BLS signature; meanwhile, all the security properties are formally proven under some conventional assumptions in the random oracle model. [ABSTRACT FROM AUTHOR]

Recent developments on the Tate or Eta pairing computation over hyperelliptic curves by Duursma-Lee and Barreto et al. have focused on degenerate divisors. We present two efficient methods that work for general divisors to compute the Eta paring over divisor class groups of the hyperelliptic curves $H/{{\mathbb F}}_{7^n}:y^2 = x^7 - x \pm 1$ of genus 3. The first method generalizes the method of Barreto et al. so that it holds for general divisors, and we call it the pointwise method. For the second method, we take a novel approach using resultant. We focus on the case that two divisors of the pairing have supporting points in $H({{\mathbb F}}_{7^{3n}}),$ not in $H({{\mathbb F}}_{7^n})$. Our analysis shows that the resultant method is faster than the pointwise method, and our implementation result supports the theoretical analysis. In addition to the fact that the two methods work for general divisors, they also provide very explicit algorithms. [ABSTRACT FROM AUTHOR]

In many aspects, cryptanalyses of pairing based cryptography consider protocol level security and take difficulties of primitives for granted. In this survey, we consider pairing inversion. At the time this manuscript was written(April 2007), to the best of the author's knowledge, there are neither known feasible algorithms for pairing inversions nor published proofs that the problem is unfeasible. [ABSTRACT FROM AUTHOR]

In EUROCRYPT 2006, Cheon proposed breakthrough algorithms for pairing-related problems such as the q-weak/strong Diffie-Hellman problem. Using that the exponents of an element in an abelian group G of prime order p form the ring Z/pZ structure even if G is a generic group, Cheon's algorithms reduce their complexity by Pohlig-Hellman like method over (Z/pZ)* or its extension. The algorithms are more efficient than solving the relative discrete logarithm problems in certain cases. This paper shows that Cheon's algorithms are faster than the result obtained by the complexity analysis in Cheon's paper, i.e. the algorithms can be done within $O( \sqrt{p/d} + \sqrt{d} )$ group operations, where d is a positive divisor of p − 1 with d ≤ q or a positive divisor of p + 1 with 2d ≤ q, instead of $O( \log p ( \sqrt{p/d} + \sqrt{d} ) )$ group operations shown by Cheon. This paper also shows an improvement of one of the algorithms for q-weak Diffie-Hellman problem. The improvement can be done within $O( \epsilon \sqrt{p/d} )$ group operations, where ε =  min ( 2/(1 − logpd), logp ). Moreover, this paper discusses how to choose the group order so that the algorithms are inefficient and also shows a condition for the group order and the probability that an order satisfies the condition. [ABSTRACT FROM AUTHOR]

Let C be a curve of genus g, defined over a finite field ${\mathbb F}_q$, where q = pm for a prime p. Let N be a large integer coprime to p, dividing the order of the Jacobian variety associated to C. Pairings can transport the discrete logarithm problem (DLP) from the curve to a finite field where there are more efficient methods for solving the discrete logarithm. The embedding degree is defined to be the smallest positive integer k such that N divides qk − 1. We show that the minimal embedding field is not necessarily ${\mathbb F}_{q^k}$, as is traditionally understood, but rather is ${\mathbb F}_{p^{{\mathrm{ord}}_N p}}={\mathbb F}_{q^{{\mathrm{ord}}_Np/m}}$, which can be a field of significantly smaller size. This fact reveals that attacks on the DLP can be dramatically faster than otherwise expected, so a parameter separate from the embedding degree k needs to be used to indicate security. [ABSTRACT FROM AUTHOR]

This paper presents a formal model for fair blind signature schemes and a provably secure scheme based on bilinear maps. A blind signature scheme is a protocol for obtaining a signature on a message which is unknown from the signer. Furthermore, the signer cannot link his transcript of a protocol to the resulting message-signature pair. Fair blind signatures were introduced by Stadler et al. at Eurocrypt'95 in [37]. A fair blind signature scheme is a blind signature scheme allowing two types of blindness revocation: link a signature to the session which conducted this signature (Session Tracing) or, conversely, identify a signature knowing a signing session (Signature Tracing). Various fair blind signature schemes have been proposed in the past years, but none of them presents a secure fair blind signature scheme that allows polynomially many signatures to be securely issued, even if Abe et al.'s claimed it in [3]. In this paper, we first show a flaw in the blindness of most (fair) blind signature schemes where the signer is able to link signatures if he chooses his keys in an appropriate way. Then, we show a flaw in the proof of unforgeability of Abe et al.' scheme and propose a stronger security model than theirs. It possesses all the needed properties for fair blind signature schemes: blindness, traceability and non frameability for both revocations (the one-more unforgeability is implied by these properties). Finally, we describe a new fair blind signature scheme based on bilinear maps. This scheme thwarts the flaw against previous blind signatures and is proved secure in the random oracle model with respect to our model. [ABSTRACT FROM AUTHOR]

A proxy re-encryption system allows the proxy to transform ciphertexts encrypted under Alice's public key into the different ciphertexts that can be decrypted by Bob's secret key. In this paper, we propose new proxy re-encryption systems; one for the transformation from ciphertexts encrypted under a traditional PKI-based public key into the ciphertexts that can be decrypted by an secret key for Identity-Based Encryption, and the other one for the transformation from ciphertexts encrypted in IBE manner into the different ciphertexts that can be decrypted by the other secret key for the IBE. [ABSTRACT FROM AUTHOR]

We investigate the possibilities for injecting faults on pairings and assess their consequences. We assess the effect of faults that seek to corrupt the data being operated on and show that pairings with either no or a straightforward final exponentiation are less secure than pairings with a more complex final exponentiation when considering such fault attacks. As evidence, we describe two types of fault attacks on the Weil and η pairing that recover the secret point, which cannot be applied to the Tate pairing. This can be accredited to its more complex final exponentiation. [ABSTRACT FROM AUTHOR]

A series of recent algorithmic advances has delivered highly effective methods for pairing evaluation and parameter generation. However, the resulting multitude of options means many different variations of base field must ideally be supported on the target platform. Typical hardware accelerators in the form of co-processors possess neither the flexibility nor the scalability to support fields of different characteristic and order. On the other hand, extending the instruction set of a general-purpose processor by custom instructions for field arithmetic allows to combine the performance of hardware with the flexibility of software. To this end, we investigate the integration of a tri-field multiply-accumulate (MAC) unit into a SPARC V8 processor core to support arithmetic in ${\mathbb{F}}_{p}$, ${\mathbb{F}}_{2^n}$ and ${\mathbb{F}}_{3^n}$. Besides integer multiplication, the MAC unit can also execute dedicated multiply and MAC instructions for binary and ternary polynomials. Our results show that the tri-field MAC unit adds only a small size overhead while significantly accelerating arithmetic in ${\mathbb{F}}_{2^n}$ and ${\mathbb{F}}_{3^n}$, which sheds new light on the relative performance of ${\mathbb{F}}_{p}$, ${\mathbb{F}}_{2^n}$ and ${\mathbb{F}}_{3^n}$ in the context of pairing-based cryptography. [ABSTRACT FROM AUTHOR]

In this paper we describe an efficient implementation of the Tate and Ate pairings using Barreto-Naehrig pairing-friendly curves, on both a standard PC and on a 32-bit smartcard. First we introduce a sub-family of such curves with a particularly simple representation. Next we consider the issues that arise in the efficient implemention of field arithmetic in ${{\mathbb{F}}_{p^{12}}}$, which is crucial to good performance. Various optimisations are suggested, including a novel approach to the ‘final exponentiation', which is faster and requires less memory than the methods previously recommended. [ABSTRACT FROM AUTHOR]

We provide the first explicit construction of genus 2 curves over finite fields whose Jacobians are ordinary, have large prime-order subgroups, and have small embedding degree. Our algorithm is modeled on the Cocks-Pinch method for constructing pairing-friendly elliptic curves [5], and works for arbitrary embedding degrees k and prime subgroup orders r. The resulting abelian surfaces are defined over prime fields ${{\mathbb F}}_q$ with q ≈ r4. We also provide an algorithm for constructing genus 2 curves over prime fields ${{\mathbb F}}_q$ with ordinary Jacobians J having the property that $J[r] \subset J({{\mathbb F}}_{q})$ or $J[r] \subset J({{\mathbb F}}_{q^k})$ for any even k. [ABSTRACT FROM AUTHOR]

We compute in a direct (not algorithmic) way the zeta function of all supersingular curves of genus 2 over a finite field k, with many geometric automorphisms. We display these computations in an appendix where we select a family of representatives of all these curves up to ${\overline{k}}$-isomorphism and we exhibit equations and the zeta function of all their ${\overline{k}}/k$-twists. As an application we obtain a direct computation of the cryptographic exponent of the Jacobians of these curves. [ABSTRACT FROM AUTHOR]

We survey recent research on pairings on hyperelliptic curves and present a comparison of the performance characteristics of pairings on elliptic curves and hyperelliptic curves. Our analysis indicates that hyperelliptic curves are not more efficient than elliptic curves for general pairing applications. [ABSTRACT FROM AUTHOR]

In 2003, Al-Riyami and Paterson introduced a new public key encryption paradigm called Certificateless Public Key Encryption (CL-PKE), which like Identity-Based Encryption (IBE) is certificatefree, and meanwhile which unlike IBE but similar to certificate-based encryption is key-escrow-free. In this paper, based on a heuristic observation on some existing IBE schemes and PKE schemes, we propose a general approach to build a CL-PKE solution, which makes use of a simple combination of an IBE scheme, a Diffie-Hellman type key establishment algorithm and a secure hash-function. Following this approach we construct two efficient concrete CL-PKE schemes and formally analyse their security in the random oracle model. [ABSTRACT FROM AUTHOR]

The concept of Certificateless Public Key Encryption (CLPKE) eliminates the use of certificates in certified Public Key Encryption (PKE) scheme and the key-escrow problem in Identity Based Encryption (IBE) scheme. Al-Riyami and Paterson first proposed a CL-PKE scheme and proved its security in their security model (AP-model) using idealized random oracles. Several generic constructions were also proposed to construct a CL-PKE scheme by composing the standard PKE and IBE schemes. Recently, it was proved that some generic constructions are not secure against chosen ciphertext attacks in light of the security goals in the AP-model. In this paper, we show that all the known generic constructions are not secure against chosen ciphertext attacks, in the AP-model or a weaker security model than the AP-model. We also propose a CL-PKE scheme which is provably secure against chosen ciphertext attacks without random oracles. Our construction is proven secure in the selective-ID security model, reflecting the feature of CL-PKE scheme. [ABSTRACT FROM AUTHOR]

This paper puts forward new efficient constructions for public-key broadcast encryption that simultaneously enjoy the following properties: receivers are stateless; encryption is collusion-secure for arbitrarily large collusions of users and security is tight in the standard model; new users can join dynamically i.e. without modification of user decryption keys nor ciphertext size and little or no alteration of the encryption key.We also show how to permanently revoke any subgroup of users. Most importantly, our constructions achieve the optimal bound of O(1)-size either for ciphertexts or decryption keys, where the hidden constant relates to a couple of elements of a pairing-friendly group. Our broadcast-KEM trapdoor technique, which has independent interest, also provides a dynamic broadcast encryption system improving all previous efficiency measures (for both execution time and sizes) in the private-key setting. [ABSTRACT FROM AUTHOR]

At FC'05, Dodis and Yum introduced a new cryptographic tool called time capsule signature(TCS) which allows signers to generate "future signatures" that only become valid from a specific future time t (chosen at signature generation) when a trusted entity (called Time Server) discloses some trapdoor information for period t. In addition, time capsule signatures endow signers with the ability to make their signatures valid before the pre-determined time t. Full signatures that were completed by their original issuer should be indistinguishable from those that automatically became valid after the release of the timespecific trapdoor. Time capsule signatures were showed to be generically constructible from another primitive called identity-based trapdoor hardto- invert relation(ID-THIR). The only known instantiations of the latter either rely on the idealized random oracle model or are too inefficient for real-world applications. In this paper, we devise the first efficient IDTHIR (and thus TCS) construction which is secure in the standard model (i.e. without the random oracle heuristic). [ABSTRACT FROM AUTHOR]

We study the problem of a public key encryption with conjunctive keyword search (PECK). The keyword searchable encryption enables a user to outsource his data to the storage of an untrusted server and to have the ability to selectively search his data without leaking information. The PECK scheme provides the document search containing each of several keywords over a public key setting. First, we construct an efficient PECK scheme whose security is proven over a decisional linear Diffie-Hellman assumption in the random oracle model. In comparison with previous schemes, our scheme has the shortest ciphertext size and private key size, and requires a comparable computation overhead. Second, we discuss problems related to the security proof of previous schemes and show they cannot guarantee complete security. Finally, we introduce a new concept called a multi-user PECK scheme, which can achieve an efficient computation and communication overhead and effectively manage the storage in a server for a number of users. [ABSTRACT FROM AUTHOR]

In this paper, we introduce the definition of insiderimpersonation -MIM attack for tripartite key agreement schemes and show that almost all of the proposed schemes are not secure under this attack. We present a new protocol which is much more efficient than the existential secure protocol [13] in terms of computational efficiency and transmitted data size. Moreover, our protocol is the first scheme for multiple keys which means that not only a large number of keys but also various kinds of keys can be generated by applying our scheme. [ABSTRACT FROM AUTHOR]

We notice that a strong designated verifier signature (SDVS) scheme can easily be realized by any secure one-way and two-party authenticated key agreement scheme. So any SDVS scheme without lower communication/computation cost or enhanced security comparing to these one-way and two-party authenticated key agreement schemes may have less advantage in practical use. In this paper, we introduce an SDVS scheme which realizes low communication/computation cost and is more efficient than current one-way key agreement schemes and SDVS schemes. In addition, we show how to remove a hash function used in this scheme where in this modified scheme, an enhanced security will be provided such that the consistency of a signature cannot be ascertained by any third party even if the signer's private key is revealed. We will prove the security of our schemes using random oracle models. Keywords: CDH assumption, DDH assumption, double discrete logarithm, designated verifier signature, one-way two-party authenticated key agreement, privacy. [ABSTRACT FROM AUTHOR]

In this paper, we propose a fast signature scheme which realizes short transmissions and minimal on-line computation. Our scheme would require a modular exponentiation as preprocessing (i.e., off-line computation). However, there exist the following remarkable properties: neither multiplication and modular reduction is used in the actual signature generation (i.e., on-line computation). This means that in the on-line phase, our scheme requires only two operations: hashing and addition. So far, some fast signature schemes with small on-line computation are proposed. However, those schemes require multiplication or modular reduction in the on-line phase. This leads to a large amount of work compared to that of addition. As far as we know, this is the first approach to obtain the fast signature without those two calculus methods. [ABSTRACT FROM AUTHOR]

I will survey the checkered history of supersingular elliptic curves in cryptography, from their first consideration in the seminal papers of Koblitz and Miller, to their rejection after the discovery of the Weil and Tate pairing attacks on the discrete logarithm problem for these curves, and concluding with their resurrection alongside the discovery of pairing-based cryptography. [ABSTRACT FROM AUTHOR]

Bilinear groups of composite order are groups with an efficient bilinear map where the group order is a product of two large primes. Such groups are constructed from pairing friendly curves over a finite field. Composite order bilinear groups were recently used in a number of interesting cryptographic constructions. This talk will survey three applications: 1Private Information Retrieval1Anonymous Identity Based Encryption1Non-Interactive Zero Knowledge. [ABSTRACT FROM AUTHOR]