Вестник БФУ им. И. Канта

Текущий выпуск

Назад к списку Скачать статью

Эффективная реализация экспоненциальной части алгоритма подсчета точек в якобианах гиперэллиптических кривых рода 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 cryptog­raphy. Namely, Jacobians are applicable to constructions of DLP-based cryp­tosystems, 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 pre­sent an overview of approaches to accelerate Gaudry-Schost point counting algorithm that is the fastest known algorithm for computing the order of Jaco­bians of hyperelliptic curves of genus 2. This algorithm consists of two stages: 1) computing the number of points (equivalently, the characteristic polynomi­al 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. How­ever, 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 expo­nential part of Gaudry-Schost’s point counting algorithm. We evaluate the ef­ficiency 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 Tsu­jii’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 Appli­cations 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.