
Previous Article
Constructing publickey cryptographic schemes based on class group action on a set of isogenous elliptic curves
 AMC Home
 This Issue

Next Article
Efficient implementation of elliptic curve cryptography in wireless sensors
A filtering method for the hyperelliptic curve index calculus and its analysis
1.  Fakultät für Mathematik, RuhrUniversität Bochum and Horst Gösrtz Institut für ITSicherheit, Universitätsstraße 150, D44780 Bochum 
2.  Instituto de Matemática y Física, Universidad de Talca, Casilla 747, Talca 
This technique, which we call harvesting, is in fact a new strategy that subtly alters the whole index calculus algorithm. In particular, it changes the relation search to find many times more relations than variables, after which a selection process is applied to the set of the relations  the harvesting process. The aim of this new process is to extract a (slightly) overdetermined submatrix which is as small as possible. Furthermore, the size of the factor base also has to be readjusted, in order to keep the (extended) relation search faster than it would have been in an index calculus algorithm without harvesting. The size of the factor base must also be chosen to guarantee that the final matrix will be indeed smaller than it would be in an optimised index calculus without harvesting, thus also speeding up the linear algebra step.
The version of harvesting presented here is an improvement over an earlier version by the same authors. By means of a new selection algorithm, timecomplexity can be reduced from quadratic to linear (in the size of the input), thus making its running time effectively negligible with respect to the rest of the index calculus algorithm. At the same time we make the process of harvesting more effective  in the sense that the final matrix should (on average) be smaller than with the earlier approach.
We present an analysis of the impact of harvesting (for instance, we show that its usage can improve index calculus performance by more than 30% in some cases), we show that the impact on matrix size is essentially independent on the genus of the curve considered, and provide an heuristic argument in support of the effectiveness of harvesting as one parameter (which defines how far the relation search is pushed) increases.
[1] 
GuoNiu Han, Huan Xiong. Skew doubled shifted plane partitions: Calculus and asymptotics. Electronic Research Archive, 2021, 29 (1) : 18411857. doi: 10.3934/era.2020094 
[2] 
Knut Hüper, Irina Markina, Fátima Silva Leite. A Lagrangian approach to extremal curves on Stiefel manifolds. Journal of Geometric Mechanics, 2020 doi: 10.3934/jgm.2020031 
[3] 
Baoli Yin, Yang Liu, Hong Li, Zhimin Zhang. Approximation methods for the distributed order calculus using the convolution quadrature. Discrete & Continuous Dynamical Systems  B, 2021, 26 (3) : 14471468. doi: 10.3934/dcdsb.2020168 
[4] 
Kerioui Nadjah, Abdelouahab Mohammed Salah. Stability and Hopf bifurcation of the coexistence equilibrium for a differentialalgebraic biological economic system with predator harvesting. Electronic Research Archive, 2021, 29 (1) : 16411660. doi: 10.3934/era.2020084 
[5] 
Petr Pauš, Shigetoshi Yazaki. Segmentation of color images using mean curvature flow and parametric curves. Discrete & Continuous Dynamical Systems  S, 2021, 14 (3) : 11231132. doi: 10.3934/dcdss.2020389 
[6] 
Dominique Chapelle, Philippe Moireau, Patrick Le Tallec. Robust filtering for joint stateparameter estimation in distributed mechanical systems. Discrete & Continuous Dynamical Systems  A, 2009, 23 (1&2) : 6584. doi: 10.3934/dcds.2009.23.65 
[7] 
Kalikinkar Mandal, Guang Gong. On ideal $ t $tuple distribution of orthogonal functions in filtering de bruijn generators. Advances in Mathematics of Communications, 2020 doi: 10.3934/amc.2020125 
[8] 
Håkon Hoel, Gaukhar Shaimerdenova, Raúl Tempone. Multilevel Ensemble Kalman Filtering based on a sample average of independent EnKF estimators. Foundations of Data Science, 2020, 2 (4) : 351390. doi: 10.3934/fods.2020017 
[9] 
JeanPaul Chehab. Damping, stabilization, and numerical filtering for the modeling and the simulation of time dependent PDEs. Discrete & Continuous Dynamical Systems  S, 2021 doi: 10.3934/dcdss.2021002 
[10] 
Fengwei Li, Qin Yue, Xiaoming Sun. The values of two classes of Gaussian periods in index 2 case and weight distributions of linear codes. Advances in Mathematics of Communications, 2021, 15 (1) : 131153. doi: 10.3934/amc.2020049 
[11] 
Thabet Abdeljawad, Mohammad Esmael Samei. Applying quantum calculus for the existence of solution of $ q $integrodifferential equations with three criteria. Discrete & Continuous Dynamical Systems  S, 2020 doi: 10.3934/dcdss.2020440 
[12] 
KuoChih Hung, ShinHwa Wang. Classification and evolution of bifurcation curves for a porousmedium combustion problem with large activation energy. Communications on Pure & Applied Analysis, , () : . doi: 10.3934/cpaa.2020281 
[13] 
Karol Mikula, Jozef Urbán, Michal Kollár, Martin Ambroz, Ivan Jarolímek, Jozef Šibík, Mária Šibíková. Semiautomatic segmentation of NATURA 2000 habitats in Sentinel2 satellite images by evolving open curves. Discrete & Continuous Dynamical Systems  S, 2021, 14 (3) : 10331046. doi: 10.3934/dcdss.2020231 
2019 Impact Factor: 0.734
Tools
Metrics
Other articles
by authors
[Back to Top]