Paper 2004/352

Practical Cryptography in High Dimensional Tori

Marten van Dijk, Robert Granger, Dan Page, Karl Rubin, Alice Silverberg, Martijn Stam, and David Woodruff


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.

Available format(s)
Public-key cryptography
Publication info
Published elsewhere. Proceedings of Eurocrypt '05
torus-based cryptographydiscrete logarithm problem
Contact author(s)
dpwood @ mit edu
2005-03-13: revised
2004-12-13: received
See all versions
Short URL
Creative Commons Attribution


      author = {Marten van Dijk and Robert Granger and Dan Page and Karl Rubin and Alice Silverberg and Martijn Stam and David Woodruff},
      title = {Practical Cryptography in High Dimensional Tori},
      howpublished = {Cryptology ePrint Archive, Paper 2004/352},
      year = {2004},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.