In [3] we introduced a new way of using the algebraic tori T_n in cryptography, and obtained an asymptotically optimal savings in bandwidth and storage for a number of cryptographic applications. This partially answered the conjecture in [1]. In [2] we build upon techniques from our earlier paper [3], yet our new construction is much more practical, answering an open question of that paper.

In [2] we give a new method that is orders of magnitude faster than the original, while retaining the same level of compression. Further, we give the first efficient implementation that uses T_30, compare its performance to XTR [4], CEILIDH [5], 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 and obtain ciphertexts that are 10% smaller than in previous schemes.

References:

[1] A.E. Brouwer, R. Pellikaan and E.R. Verheul. Doing More with Fewer Bits. In Advances of Cryptology (ASIACRYPT), Springer-Verlag LNCS 1716, 321-332, 1999.

[2] M. van Dijk, R. Granger, D. Page, K. Rubin, A. Silverberg, M. Stam and D. Woodruff. Practical Cryptography in High Dimensional Tori. Accepted for publication in Advances in Cryptology (EUROCRYPT), 2005.

[3] M. van Dijk and D. Woodruff. Asymptotically Optimal Communication for Torus-Based Cryptography. In Advances in Cryptology (CRYPTO), Springer-Verlag LNCS 3152, 157--178, 2004.

[4] A.K. Lenstra and E.R. Verheul. The XTR Public Key System. In Advances in Cryptology (CRYPTO), Springer-Verlag LNCS 1880, 1--19, 2000.

[5] K. Rubin and A. Silverberg. Torus-Based Cryptography. In Advances in Cryptology (CRYPTO), Springer-Verlag LNCS 2729, 349--365, 2003.