Paper 2021/1659

XTR and Tori

Martijn Stam

Abstract

At the turn of the century, 80-bit security was the standard. When considering discrete-log based cryptosystems, it could be achieved using either subgroups of 1024-bit finite fields or using (hyper)elliptic curves. The latter would allow more compact and efficient arithmetic, until Lenstra and Verheul invented XTR. Here XTR stands for 'ECSTR', itself an abbreviation for Efficient and Compact Subgroup Trace Representation. XTR exploits algebraic properties of the cyclotomic subgroup of sixth degree extension fields, allowing representation only a third of their regular size, making finite field DLP-based systems competitive with elliptic curve ones. Subsequent developments, such as the move to 128-bit security and improvements in finite field DLP, rendered the original XTR and closely related torus-based cryptosystems no longer competitive with elliptic curves. Yet, some of the techniques related to XTR are still relevant for certain pairing-based cryptosystems. This chapter describes the past and the present of XTR and other methods for efficient and compact subgroup arithmetic.

Note: This material will be published in revised form in Computational Cryptography edited by Joppe W. Bos and Martijn Stam and published by Cambridge University Press. See www.cambridge.org/9781108795937.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Published elsewhere. Computational Cryptography
DOI
10.1017/9781108854207.013
Keywords
implementationnumber theorypublic key cryptography
Contact author(s)
martijn @ simula no
History
2021-12-17: received
Short URL
https://ia.cr/2021/1659
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2021/1659,
      author = {Martijn Stam},
      title = {XTR and Tori},
      howpublished = {Cryptology ePrint Archive, Paper 2021/1659},
      year = {2021},
      doi = {10.1017/9781108854207.013},
      note = {\url{https://eprint.iacr.org/2021/1659}},
      url = {https://eprint.iacr.org/2021/1659}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.