Catálogo de publicaciones - libros

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.

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.

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.

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.

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.

Let C be a curve of genus g , defined over a finite field ${\mathbb F}_q$ , where q  =  p ^ m 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 q ^ k  − 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.

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 2 d  ≤  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 − log_ p d ), log p ). 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.

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.

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.

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.