Paper 2014/346

Time-Memory Trade-offs for Index Calculus in Genus 3

Kim Laine and Kristin Lauter

Abstract

In this paper, we present a variant of Diem's $\widetilde{O}(q)$ index calculus algorithm to attack the discrete logarithm problem (DLP) in Jacobians of genus $3$ non-hyperelliptic curves over a finite field $\mathbb{F}_q$. We implement this new variant in C++ and study the complexity in both theory and practice, making the logarithmic factors and constants hidden in the $\widetilde{O}$-notation precise. Our variant improves the computational complexity at the cost of a moderate increase in memory consumption, but we also improve the computational complexity even when we limit the memory usage to that of Diem's original algorithm. Finally, we examine how parallelization can help to reduce both the memory cost per computer and the running time for our algorithms.

Note: Minor typos fixed.

Metadata
Available format(s)
PDF
Publication info
Preprint. MINOR revision.
Keywords
discrete logarithm problemindex calculusdouble large primehigher genusgenus 3non-hyperelliptic curvequartic curveplane curvetime-memory trade-off
Contact author(s)
kim laine @ gmail com
History
2014-09-12: last of 2 revisions
2014-05-19: received
See all versions
Short URL
https://ia.cr/2014/346
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2014/346,
      author = {Kim Laine and Kristin Lauter},
      title = {Time-Memory Trade-offs for Index Calculus in Genus 3},
      howpublished = {Cryptology ePrint Archive, Paper 2014/346},
      year = {2014},
      note = {\url{https://eprint.iacr.org/2014/346}},
      url = {https://eprint.iacr.org/2014/346}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.