## CryptoDB

### Karl Rubin

#### Publications

Year
Venue
Title
2009
JOFC
2007
EPRINT
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.
2005
EUROCRYPT
2004
EPRINT
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
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
CRYPTO
2003
EPRINT
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
CRYPTO

#### Coauthors

Robert Granger (2)
Dan Page (2)
Alice Silverberg (8)
Martijn Stam (2)
Marten van Dijk (2)
David P. Woodruff (2)