International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Ben Lynn

Publications

Year
Venue
Title
2004
EUROCRYPT
2004
JOFC
2004
JOFC
2003
EUROCRYPT
2003
EPRINT
On the Selection of Pairing-Friendly Groups
We propose a simple algorithm to select group generators suitable for pairing-based cryptosystems. The selected parameters are shown to favor implementations of the Tate pairing that are at once conceptually simple and efficient, with an observed performance about 2 to 10 times better than previously reported implementations, depending on the embedding degree. Our algorithm has beneficial side effects: various non-pairing operations become faster, and bandwidth may be saved.
2002
CRYPTO
2002
EUROCRYPT
2002
EPRINT
Efficient Algorithms for Pairing-Based Cryptosystems
We describe fast new algorithms to implement recent cryptosystems based on the Tate pairing. In particular, our techniques improve pairing evaluation speed by a factor of about 55 compared to previously known methods in characteristic 3, and attain performance comparable to that of RSA in larger characteristics. We also propose faster algorithms for scalar multiplication in characteristic 3 and square root extraction over $\GF{p^m}$, the latter technique being also useful in contexts other than that of pairing-based cryptography.
2002
EPRINT
Authenticated Identity-Based Encryption
Ben Lynn
Suppose Alice wishes to send a message to Bob using an identity-based encryption scheme (recall such a scheme is a public key cryptosystem where any string is a valid public key), but desires integrity as well as security. In other words, Alice wants Bob to know that only she could have sent the message. Furthermore, suppose she does not want the non-repudiation property that would necessarily be present if she simply used an identity-based signature scheme i.e. she does not want Bob to be able to prove to a third party that she is the sender. We augment the system of Boneh and Franklin to allow communication with integrity without nonrepudiation. We formalize notions of security and integrity for our scheme, and show that new encryption and decryption algorithms are more efficient, despite being equally secure and authenticated.
2002
EPRINT
Constructing Elliptic Curves with Prescribed Embedding Degrees
Pairing-based cryptosystems depend on the existence of groups where the Decision Diffie-Hellman problem is easy to solve, but the Computational Diffie-Hellman problem is hard. Such is the case of elliptic curve groups whose embedding degree is large enough to maintain a good security level, but small enough for arithmetic operations to be feasible. However, the embedding degree is usually enormous, and the scarce previously known suitable elliptic groups had embedding degree $k \leqslant 6$. In this note, we examine criteria for curves with larger $k$ that generalize prior work by Miyaji et al. based on the properties of cyclotomic polynomials, and propose efficient representations for the underlying algebraic structures.
2002
EPRINT
Aggregate and Verifiably Encrypted Signatures from Bilinear Maps
An aggregate signature scheme is a digital signature that supports aggregation: Given $n$ signatures on $n$ distinct messages from $n$ distinct users, it is possible to aggregate all these signatures into a single short signature. This single signature (and the $n$ original messages) will convince the verifier that the $n$ users did indeed sign the $n$ original messages (i.e., user $i$ signed message $M_i$ for $i=1,\ldots,n$). In this paper we introduce the concept of an aggregate signature scheme, present security models for such signatures, and give several applications for aggregate signatures. We construct an efficient aggregate signature from a recent short signature scheme based on bilinear maps due to Boneh, Lynn, and Shacham. Aggregate signatures are useful for reducing the size of certificate chains (by aggregating all signatures in the chain) and for reducing message size in secure routing protocols such as SBGP. We also show that aggregate signatures give rise to verifiably encrypted signatures. Such signatures enable the verifier to test that a given ciphertext $C$ is the encryption of a signature on a given message $M$. Verifiably encrypted signatures are used in contract-signing protocols. Finally, we show that similar ideas can be used to extend the short signature scheme to give simple ring signatures.
2001
ASIACRYPT