## CryptoDB

### Alice Silverberg

#### Affiliation: University of California, Irvine

#### Publications

**Year**

**Venue**

**Title**

2007

EPRINT

Choosing the correct elliptic curve in the CM method
Abstract

We give easy ways to distinguish between the twists of an ordinary elliptic curve $E$ over $\mathbb{F}_p$ in order to identify one with $p+1-2U$ points, when $p=U^2+dV^2$ with $2U, 2V \in \mathbb{Z}$ and $E$ is constructed using the CM method. This is useful for finding elliptic curves with a prescribed number of points, and is a new, faster, and easier way to implement the last step of the CM method. Our algorithms are completely elementary, in most cases consisting of merely reading off simple congruence conditions on $U$ and $V$ modulo $4$, whereas current algorithms rely on elliptic curve arithmetic and computing square roots.

2004

EPRINT

Using primitive subgroups to do more with fewer bits
Abstract

This paper gives a survey of some ways to improve the efficiency of discrete log-based cryptography by using the restriction of scalars and the geometry and arithmetic of algebraic tori and abelian varieties.

2004

EPRINT

Practical Cryptography in High Dimensional Tori
Abstract

At Crypto 2004, van Dijk and Woodruff introduced a new way of using the algebraic tori T_n in cryptography, and obtained an asymptotically optimal n/phi(n) savings in bandwidth and storage for a number of cryptographic applications. However, the computational requirements of compression and decompression in their scheme were impractical, and it was left open to reduce them to a practical level. We give a new method that compresses orders of magnitude faster than the original, while also speeding up the decompression and improving on the compression factor (by a constant term). Further, we give the first efficient implementation that uses T_30, compare its performance to XTR, CEILIDH, and ECC, and present new applications. Our methods achieve better compression than XTR and CEILIDH for the compression of as few as two group elements. This allows us to apply our results to ElGamal encryption with a small message domain to obtain ciphertexts that are 10% smaller than in previous schemes.

2003

EPRINT

Torus-based cryptography
Abstract

We introduce cryptography based on algebraic tori, give a new public key system called CEILIDH, and compare it to other discrete log based systems including LUC and XTR. Like those systems, we obtain small key sizes. While LUC and XTR are essentially restricted to exponentiation,
we are able to perform multiplication as well. We also disprove the open conjectures from the paper "Looking beyond XTR", and give a new algebro-geometric interpretation of the approach in that paper and of LUC and XTR.

2002

EPRINT

Hierarchical ID-Based Cryptography
Abstract

We present hierarchical identity-based encryption schemes and signature schemes that have total collusion resistance on an arbitrary number of levels and that have chosen ciphertext security in the random oracle model assuming the difficulty of the Bilinear Diffie-Hellman problem.

2002

EPRINT

Applications of Multilinear Forms to Cryptography
Abstract

We study the problem of finding efficiently computable non-degenerate multilinear maps from (G_1)^n to G_2, where G_1 and G_2 are groups of the same prime order, and where computing discrete logarithms in G_1 is hard. We present several applications to cryptography, explore directions for building such maps, and give some reasons to believe that finding examples with n > 2 may be difficult.

2001

EPRINT

Efficient Traitor Tracing Algorithms using List Decoding
Abstract

We apply powerful, recently discovered techniques for the list decoding of error-correcting codes to the problem of efficiently tracing traitors. Traitor tracing schemes have been extensively studied for use as a piracy deterrent. In a widely studied model for protecting digital content, each user in the system is associated with a unique set of symbols. For example, the sets may be used to install a software CD or decrypt pay-TV content. The assignment of sets is done in such a way that if a bounded collection of sets is used to form a new set to enable piracy, at least one of the traitor sets can be identified by applying a traitor tracing algorithm to the newly formed set. Much work has focused on methods for constructing such traceability schemes, but the complexity of the traitor tracing algorithms has received little attention. A widely used traitor tracing algorithm, the TA algorithm, has a running time of $O(\n)$ in general, where $\n$ is number of sets in the system (e.g., the number of copies of the CD), and therefore is inefficient for large populations. In this paper we use a coding theoretic approach to produce traceability schemes for which the TA algorithm is very fast. We show that when suitable error-correcting codes are used to construct traceability schemes, and fast list decoding algorithms are used to trace, the run time of the TA algorithm is polynomial in the codeword length. We also use the strength of the error-correcting code approach to construct traceability schemes with more efficient algorithms for finding all possible traitor coalitions. Finally, we provide evidence that amongst traceability schemes in general, TA traceability schemes are the most likely to be amenable to efficient tracing methods.

#### Program Committees

- Crypto 2014
- PKC 2006
- Crypto 2005
- Crypto 2004

#### Coauthors

- Dan Boneh (1)
- Craig Gentry (2)
- Robert Granger (2)
- Hendrik W. Lenstra Jr. (1)
- Dan Page (2)
- Karl Rubin (8)
- Jessica Staddon (2)
- Martijn Stam (2)
- Marten van Dijk (2)
- Judy L. Walker (2)
- David P. Woodruff (2)