Эффективная реализация экспоненциальной части алгоритма подсчета точек в якобианах гиперэллиптических кривых рода 2
- Страницы / Pages
- 42-48
Аннотация
Задача вычисления порядка якобиана гиперэллиптической кривой является классической задачей теории чисел с приложениями в современной криптографии. Якобиан кривой используется для построения криптосистем, основанных на дискретном логарифме; как группа большого «неизвестного» порядка в конструкциях верифицируемых функций задержки (VDF) и других приложениях. В статье приводится обзор подходов к ускорению наиболее быстрого алгоритма подсчета точек в якобианах гиперэллиптических кривых — алгоритма Годри — Шоста. Данный алгоритм состоит из двух этапов: 1) нахождение числа точек (характеристического многочлена) по модулю малых простых чисел с объединением результата в один большой модуль по китайской теореме об остатках (полиномиальная часть алгоритма); 2) восстановление полного числа точек из информации по модулю с помощью алгоритмов, основанных на парадоксе дней рождения (экспоненциальная часть алгоритма). В теории алгоритм терминируется в первой части и имеет полиномиальную сложность , где — размер конечного поля. Однако на практике полиномиальная часть алгоритма останавливается на некотором простом числе из-за ограничений по использованию памяти, которая растет как , и полное число точек находят уже по экспоненциальному алгоритму. В данной работе выполнена многопоточная реализация экспоненциальной части алгоритма Годри — Шоста на языке программирования C++, дается оценка ее эффективности по затратам времени и памяти.
Abstract
Computing the order of Jacobian of a hyperelliptic curve is a common number-theoretical problem that has lots of applications in modern cryptography. Namely, Jacobians are applicable to constructions of DLP-based cryptosystems, as well as constructions of verifiable delay functions (VDF’s), since they can be viewed as large groups of unknown order. In this article, we present an overview of approaches to accelerate Gaudry-Schost point counting algorithm that is the fastest known algorithm for computing the order of Jacobians of hyperelliptic curves of genus 2. This algorithm consists of two stages: 1) computing the number of points (equivalently, the characteristic polynomial of the curve) modulo some small primes and combining the result into a large module using CRT (polynomial-time part); 2) restoring the number of points utilizing modular data using algorithms based on birthday paradox (exponential-time part). Theoretically, the algorithm terminates after the first stage with time-complexity, where is a finite field modulus. However, in practice we terminate the polynomial-time part (due to high memory consumption), and we proceed to the second, memory-efficient, exponential-time part. This article presents a multithreaded C++ implementation of exponential part of Gaudry-Schost’s point counting algorithm. We evaluate the efficiency of our multithreaded implementation.
Список литературы
1. Gaudry P. NTLJac2, Tools for genus 2 Jacobians in NTL. URL: http:// www.lix.polytechnique.fr/Labo/Pierrick.Gaudry/NTLJac2/ (дата обращения: 13.10.2020).
2. Gaudry P., Schost É. Genus 2 point counting over prime fields // J. of Symbolic Computation. 2012. Vol. 47, № 4. Р. 368—400.
3. Dobson S., Galbraith S. D., Smith B. Trustless Groups of Unknown Order with Hyperelliptic Curves // Cryptology ePrint Archive, Report 2020/196. URL: https:// eprint.iacr.org/2020/196 (дата обращения: 10.09.2020).
4. Gaudry P., Schost É.A low-memory parallel version of Matsuo, Chao, and Tsujii’s algorithm // International Algorithmic Number Theory Symposium. Springer, 2004. Р. 208—222.
5. Matsuo K., Chao J., Tsujii S. An improved baby step giant step algorithm for point counting of hyperelliptic curves over finite fields // International Algorithmic Number Theory Symposium. Springer, 2002. Р. 461—474.
6. Boneh D., Bunz B., Fisch B. Batching Techniques for Accumulators with Applications to IOPs and Stateless Blockchains // Cryptology ePrint Archive, Report 2018/1188. URL: https://eprint.iacr.org/2018/1188.pdf (дата обращения: 10.09.2020).
7. Bünz B., Fisch B., Szepieniec A. Transparent SNARKs from DARK Compilers // Cryptology ePrint Archive, Report 2019/1229. URL: https://eprint.iacr.org/2019/ 1229.pdf (дата обращения: 10.09.2020).
8. Galbraith S., Ruprai R. S. Using Equivalence Classes to Accelerate Solving the Discrete Logarithm Problem in a Short Interval // International Workshop on Public Key Cryptography. Springer, 2010. Р. 368—383.
9. Smith B. Isogenies and the discrete logarithm problem in Jacobians of genus 3 hyperelliptic curves // Advances in Cryptology — Eurocrypt. Springer, 2008. Р. 163—180.
10. Kedlaya K. S., Sutherland A. V. Computing L-series of hyperelliptic curves // International Algorithmic Number Theory Symposium. Springer, 2008. Р. 312—326.
11. Fité F., Kedlaya K. S., Rotger, V., Sutherland, A. V. Sato-Tate distributions and Galois endomorphism modules in genus 2 // Compositio Mathematica. 2012. Т. 148, № 5. Р. 1390—1442.