doi: 10.3934/amc.2022022
Online First

Online First articles are published articles within a journal that have not yet been assigned to a formal issue. This means they do not yet have a volume number, issue number, or page numbers assigned to them, however, they can still be found and cited using their DOI (Digital Object Identifier). Online First publication benefits the research community by making new scientific discoveries known as quickly as possible.

Readers can access Online First articles via the “Online First” tab for the selected journal.

Reconstructing points of superelliptic curves over a prime finite field

University of Cantabria, Santander, E-39071, Spain

Received  April 2021 Revised  February 2022 Early access March 2022

Fund Project: Author is partially supported by grant PID2019-110633GB-I00 funded by MCIN/AEI/10.13039/ 501100011033

Let $ p $ be a prime and $ \mathbb{F}_p $ the finite field with $ p $ elements. We show how, when given an superelliptic curve $ Y^n+f(X) \in \mathbb{F}_p[X,Y] $ and an approximation to $ (v_0,v_1) \in \mathbb{F}_p^2 $ such that $ v_1^n = -f(v_0) $, one can recover $ (v_0,v_1) $ efficiently, if the approximation is good enough. As consequence we provide an upper bound on the number of roots of such bivariate polynomials where the roots have certain restrictions. The results has been motivated by the predictability problem for non-linear pseudorandom number generators and, other potential applications to cryptography.

Citation: Jaime Gutierrez. Reconstructing points of superelliptic curves over a prime finite field. Advances in Mathematics of Communications, doi: 10.3934/amc.2022022
References:
[1]

L. Babai, On Lovász' lattice reduction and the nearest lattice point problem, Combinatorica, 6 (1986), 1-13.  doi: 10.1007/BF02579403.

[2]

R. C. Baker, M. Munsch and I. E. Shparlinski, Additive energy and a large sieve inequality for sparse sequences, preprint, arXiv: 2103.12659.

[3]

S. R. BlackburnD. Gomez-PerezJ. Gutierrez and I. E. Shparlinski, Predicting nonlinear pseudorandom number generators, Math. Comp., 74 (2005), 1471-1494.  doi: 10.1090/S0025-5718-04-01698-9.

[4]

S. R. BlackburnD. Gomez-PerezJ. Gutierrez and I. E. Shparlinski, Reconstructing noisy polynomial evaluation in residue rings, J. Algorithms, 61 (2006), 47-59.  doi: 10.1016/j.jalgor.2004.07.002.

[5]

J. Blömer and A. May, A tool kit for finding small roots of bivariate polynomials over the integers, in Advances in Cryptology–Eurocrypt 2005, Lecture Notes in Comput. Sci., 3494, Springer, Berlin, 2005,251–267. doi: 10.1007/11426639_15.

[6]

D. Boneh, S. Halevi and N. Howgrave-Graham, The modular inversion hidden number problem, in Advances in Cryptology–ASIACRYPT 2001 (Gold Coast), Lecture Notes in Comput. Sci., 2248, Springer, Berlin, 2001, 36–51. doi: 10.1007/3-540-45682-1_3.

[7]

J. Boyar, Inferring sequences produced by pseudo-random number generators, J. Assoc. Comput. Mach., 36 (1989), 129-141.  doi: 10.1145/58562.59305.

[8]

M.-C. ChangJ. CillerueloM. Z. GaraevJ. HernándezI. E. Shparlinski and A. Zumalacárregui, Points on curves in small boxes and applications, Michigan Math. J, 63 (2014), 503-534.  doi: 10.1307/mmj/1409932631.

[9]

D. Coppersmith, Finding small solutions to small degree polynomials, in Cryptography and Lattices (Providence, RI, 2001), Lecture Notes in Comput. Sci., 2146, Springer, Berlin, 2001, 20–31. doi: 10.1007/3-540-44670-2_3.

[10]

D. Coppersmith, Small solutions to polynomial equations, and low exponent RSA vulnerabilities, J. Cryptology, 10 (1997), 233-260.  doi: 10.1007/s001459900030.

[11]

J.-S. Coron, Finding small roots of bivariate integer polynomial equations: A direct approach, in Advances in Cryptology–CRYPTO 2007, Lecture Notes in Comput. Sci., 4622, Springer, Berlin, 2007,379–394. doi: 10.1007/978-3-540-74143-5_21.

[12]

A. Dunn, B. Kerr, I. E. Shparlinski and A. Zaharescu, Bilinear forms in Weyl sums for modular square roots and applications, Adv. Math., 375 (2020), 58pp. doi: 10.1016/j.aim.2020.107369.

[13]

A. M. FriezeJ. HåstadR. KannanJ. C. Lagarias and A. Shamir, Reconstructing truncated integer variables satisfying linear congruences, SIAM J. Comput., 17 (1988), 262-280.  doi: 10.1137/0217016.

[14]

D. Gómez and J. Gutierrez, Recovering zeros of polynomials modulo a prime, Math. Comp., 83 (2014), 2953-2965.  doi: 10.1090/S0025-5718-2014-02808-1.

[15]

M. Grötschel, L. Lovász and A. Schrijver, Geometric Algorithms and Combinatorial Optimization, Algorithms and Combinatorics: Study and Research Texts, 2, Springer-Verlag, Berlin, 1988. doi: 10.1007/978-3-642-97881-4.

[16]

J. Gutierrez and Á. Ibeas, Inferring sequences produced by a linear congruential generator on elliptic curves missing high-order bits, Des. Codes Cryptogr., 45 (2007), 199-212.  doi: 10.1007/s10623-007-9112-3.

[17]

N. Howgrave-Graham, Finding small roots of univariate modular equations revisited, in Cryptography and Coding (Cirencester, 1997), Lecture Notes in Comput. Sci., 1355, Springer, Berlin, 1997,131–142. doi: 10.1007/BFb0024458.

[18]

E. Jochemsz and A. May, A strategy for finding roots of multivariate polynomials with new applications in attacking RSA variants, in Advances in Cryptology–ASIACRYPT 2006, Lecture Notes in Comput. Sci., 4284, Springer, Berlin, 2006,267–282. doi: 10.1007/11935230_18.

[19]

A. Joux and J. Stern, Lattice reduction: A toolbox for the cryptanalyst, J. Cryptology, 11 (1998), 161-185.  doi: 10.1007/s001459900042.

[20]

R. Kannan, Minkowski's convex body theorem and integer programming, Math. Oper. Res., 12 (1987), 415-440.  doi: 10.1287/moor.12.3.415.

[21]

H. Krawczyk, How to predict congruential generators, J. Algorithms, 13 (1992), 527-545.  doi: 10.1016/0196-6774(92)90054-G.

[22]

A. K. LenstraH. W. Lenstra Jr. and L. Lovász, Factoring polynomials with rational coefficients, Math. Ann., 261 (1982), 515-534.  doi: 10.1007/BF01457454.

[23]

L. Mérai and I. E. Shparlinski, Sparsity of curves and additive and multiplicative expansion of rational maps over finite fields, Acta Arith., 188 (2019), 401-411.  doi: 10.4064/aa180307-20-8.

[24]

D. Micciancio and S. Goldwasser, Complexity of Lattice Problems. A Cryptographic Perspective, The Kluwer International Series in Engineering and Computer Science, 671, Kluwer Academic Publishers, Boston, MA, 2002. doi: 10.1007/978-1-4615-0897-7.

[25]

P. Q. Nguyen and J. Stern, Lattice reduction in cryptology: An update, in Algorithmic Number Theory (Leiden, 2000), Lecture Notes in Comput. Sci., 1838, Springer, Berlin, 2000, 85–112. doi: 10.1007/10722028_4.

show all references

References:
[1]

L. Babai, On Lovász' lattice reduction and the nearest lattice point problem, Combinatorica, 6 (1986), 1-13.  doi: 10.1007/BF02579403.

[2]

R. C. Baker, M. Munsch and I. E. Shparlinski, Additive energy and a large sieve inequality for sparse sequences, preprint, arXiv: 2103.12659.

[3]

S. R. BlackburnD. Gomez-PerezJ. Gutierrez and I. E. Shparlinski, Predicting nonlinear pseudorandom number generators, Math. Comp., 74 (2005), 1471-1494.  doi: 10.1090/S0025-5718-04-01698-9.

[4]

S. R. BlackburnD. Gomez-PerezJ. Gutierrez and I. E. Shparlinski, Reconstructing noisy polynomial evaluation in residue rings, J. Algorithms, 61 (2006), 47-59.  doi: 10.1016/j.jalgor.2004.07.002.

[5]

J. Blömer and A. May, A tool kit for finding small roots of bivariate polynomials over the integers, in Advances in Cryptology–Eurocrypt 2005, Lecture Notes in Comput. Sci., 3494, Springer, Berlin, 2005,251–267. doi: 10.1007/11426639_15.

[6]

D. Boneh, S. Halevi and N. Howgrave-Graham, The modular inversion hidden number problem, in Advances in Cryptology–ASIACRYPT 2001 (Gold Coast), Lecture Notes in Comput. Sci., 2248, Springer, Berlin, 2001, 36–51. doi: 10.1007/3-540-45682-1_3.

[7]

J. Boyar, Inferring sequences produced by pseudo-random number generators, J. Assoc. Comput. Mach., 36 (1989), 129-141.  doi: 10.1145/58562.59305.

[8]

M.-C. ChangJ. CillerueloM. Z. GaraevJ. HernándezI. E. Shparlinski and A. Zumalacárregui, Points on curves in small boxes and applications, Michigan Math. J, 63 (2014), 503-534.  doi: 10.1307/mmj/1409932631.

[9]

D. Coppersmith, Finding small solutions to small degree polynomials, in Cryptography and Lattices (Providence, RI, 2001), Lecture Notes in Comput. Sci., 2146, Springer, Berlin, 2001, 20–31. doi: 10.1007/3-540-44670-2_3.

[10]

D. Coppersmith, Small solutions to polynomial equations, and low exponent RSA vulnerabilities, J. Cryptology, 10 (1997), 233-260.  doi: 10.1007/s001459900030.

[11]

J.-S. Coron, Finding small roots of bivariate integer polynomial equations: A direct approach, in Advances in Cryptology–CRYPTO 2007, Lecture Notes in Comput. Sci., 4622, Springer, Berlin, 2007,379–394. doi: 10.1007/978-3-540-74143-5_21.

[12]

A. Dunn, B. Kerr, I. E. Shparlinski and A. Zaharescu, Bilinear forms in Weyl sums for modular square roots and applications, Adv. Math., 375 (2020), 58pp. doi: 10.1016/j.aim.2020.107369.

[13]

A. M. FriezeJ. HåstadR. KannanJ. C. Lagarias and A. Shamir, Reconstructing truncated integer variables satisfying linear congruences, SIAM J. Comput., 17 (1988), 262-280.  doi: 10.1137/0217016.

[14]

D. Gómez and J. Gutierrez, Recovering zeros of polynomials modulo a prime, Math. Comp., 83 (2014), 2953-2965.  doi: 10.1090/S0025-5718-2014-02808-1.

[15]

M. Grötschel, L. Lovász and A. Schrijver, Geometric Algorithms and Combinatorial Optimization, Algorithms and Combinatorics: Study and Research Texts, 2, Springer-Verlag, Berlin, 1988. doi: 10.1007/978-3-642-97881-4.

[16]

J. Gutierrez and Á. Ibeas, Inferring sequences produced by a linear congruential generator on elliptic curves missing high-order bits, Des. Codes Cryptogr., 45 (2007), 199-212.  doi: 10.1007/s10623-007-9112-3.

[17]

N. Howgrave-Graham, Finding small roots of univariate modular equations revisited, in Cryptography and Coding (Cirencester, 1997), Lecture Notes in Comput. Sci., 1355, Springer, Berlin, 1997,131–142. doi: 10.1007/BFb0024458.

[18]

E. Jochemsz and A. May, A strategy for finding roots of multivariate polynomials with new applications in attacking RSA variants, in Advances in Cryptology–ASIACRYPT 2006, Lecture Notes in Comput. Sci., 4284, Springer, Berlin, 2006,267–282. doi: 10.1007/11935230_18.

[19]

A. Joux and J. Stern, Lattice reduction: A toolbox for the cryptanalyst, J. Cryptology, 11 (1998), 161-185.  doi: 10.1007/s001459900042.

[20]

R. Kannan, Minkowski's convex body theorem and integer programming, Math. Oper. Res., 12 (1987), 415-440.  doi: 10.1287/moor.12.3.415.

[21]

H. Krawczyk, How to predict congruential generators, J. Algorithms, 13 (1992), 527-545.  doi: 10.1016/0196-6774(92)90054-G.

[22]

A. K. LenstraH. W. Lenstra Jr. and L. Lovász, Factoring polynomials with rational coefficients, Math. Ann., 261 (1982), 515-534.  doi: 10.1007/BF01457454.

[23]

L. Mérai and I. E. Shparlinski, Sparsity of curves and additive and multiplicative expansion of rational maps over finite fields, Acta Arith., 188 (2019), 401-411.  doi: 10.4064/aa180307-20-8.

[24]

D. Micciancio and S. Goldwasser, Complexity of Lattice Problems. A Cryptographic Perspective, The Kluwer International Series in Engineering and Computer Science, 671, Kluwer Academic Publishers, Boston, MA, 2002. doi: 10.1007/978-1-4615-0897-7.

[25]

P. Q. Nguyen and J. Stern, Lattice reduction in cryptology: An update, in Algorithmic Number Theory (Leiden, 2000), Lecture Notes in Comput. Sci., 1838, Springer, Berlin, 2000, 85–112. doi: 10.1007/10722028_4.

Table1 
Algorithm 1: Recovering algorithm
  Input: $(f(X), \Delta,w_0,w_1)$ such that $(w_0,w_1)$ is a $ \Delta$-approximation to a root $(v_0,v_1)$ of $Y^n+f(X)$.
  Output: $(v_0,v_1)$ or $ (0,0) $
1 Compute a solution $\vec T$ of the system of congruences (4);
2 Compute $\vec u$ a closest vector to $\vec T$ and lattice (6) using the algorithm in [1];
3 $\vec F \leftarrow \vec T$ - $\vec u$ = $ (f_1, \ldots, f_{m}, \ldots, f_{m+n-1}) $ $\varepsilon_0 ,\varepsilon_1\leftarrow f_{1}/ \Delta^{m},f_{m}/ \Delta^{m}$;
4 ${\varepsilon _0},{\varepsilon _1} \leftarrow {f_1}/{\Delta ^m},{f_m}/{\Delta ^m}$
5 if $ |\varepsilon_0| \le \Delta \quad \& \quad |\varepsilon_1| \le \Delta $ then
6 | return$(w_0+\varepsilon_0, w_1+\varepsilon_1)$
7 else
8 | return$(0,0)$
9 end
Algorithm 1: Recovering algorithm
  Input: $(f(X), \Delta,w_0,w_1)$ such that $(w_0,w_1)$ is a $ \Delta$-approximation to a root $(v_0,v_1)$ of $Y^n+f(X)$.
  Output: $(v_0,v_1)$ or $ (0,0) $
1 Compute a solution $\vec T$ of the system of congruences (4);
2 Compute $\vec u$ a closest vector to $\vec T$ and lattice (6) using the algorithm in [1];
3 $\vec F \leftarrow \vec T$ - $\vec u$ = $ (f_1, \ldots, f_{m}, \ldots, f_{m+n-1}) $ $\varepsilon_0 ,\varepsilon_1\leftarrow f_{1}/ \Delta^{m},f_{m}/ \Delta^{m}$;
4 ${\varepsilon _0},{\varepsilon _1} \leftarrow {f_1}/{\Delta ^m},{f_m}/{\Delta ^m}$
5 if $ |\varepsilon_0| \le \Delta \quad \& \quad |\varepsilon_1| \le \Delta $ then
6 | return$(w_0+\varepsilon_0, w_1+\varepsilon_1)$
7 else
8 | return$(0,0)$
9 end
[1]

Florian Luca, Igor E. Shparlinski. On finite fields for pairing based cryptography. Advances in Mathematics of Communications, 2007, 1 (3) : 281-286. doi: 10.3934/amc.2007.1.281

[2]

Stefania Fanali, Massimo Giulietti, Irene Platoni. On maximal curves over finite fields of small order. Advances in Mathematics of Communications, 2012, 6 (1) : 107-120. doi: 10.3934/amc.2012.6.107

[3]

Joseph H. Silverman. Local-global aspects of (hyper)elliptic curves over (in)finite fields. Advances in Mathematics of Communications, 2010, 4 (2) : 101-114. doi: 10.3934/amc.2010.4.101

[4]

Josep M. Miret, Jordi Pujolàs, Anna Rio. Explicit 2-power torsion of genus 2 curves over finite fields. Advances in Mathematics of Communications, 2010, 4 (2) : 155-168. doi: 10.3934/amc.2010.4.155

[5]

Ryutaroh Matsumoto. Strongly secure quantum ramp secret sharing constructed from algebraic curves over finite fields. Advances in Mathematics of Communications, 2019, 13 (1) : 1-10. doi: 10.3934/amc.2019001

[6]

Ferruh Özbudak, Burcu Gülmez Temür, Oǧuz Yayla. Further results on fibre products of Kummer covers and curves with many points over finite fields. Advances in Mathematics of Communications, 2016, 10 (1) : 151-162. doi: 10.3934/amc.2016.10.151

[7]

Santanu Sarkar, Subhamoy Maitra. Some applications of lattice based root finding techniques. Advances in Mathematics of Communications, 2010, 4 (4) : 519-531. doi: 10.3934/amc.2010.4.519

[8]

Kaushik Nath, Palash Sarkar. Efficient arithmetic in (pseudo-)mersenne prime order fields. Advances in Mathematics of Communications, 2022, 16 (2) : 303-348. doi: 10.3934/amc.2020113

[9]

Nazar Arakelian, Saeed Tafazolian, Fernando Torres. On the spectrum for the genera of maximal curves over small fields. Advances in Mathematics of Communications, 2018, 12 (1) : 143-149. doi: 10.3934/amc.2018009

[10]

Ilias S. Kotsireas, Christos Koukouvinos, Dimitris E. Simos. MDS and near-MDS self-dual codes over large prime fields. Advances in Mathematics of Communications, 2009, 3 (4) : 349-361. doi: 10.3934/amc.2009.3.349

[11]

Isaac A. García, Jaume Giné. Non-algebraic invariant curves for polynomial planar vector fields. Discrete and Continuous Dynamical Systems, 2004, 10 (3) : 755-768. doi: 10.3934/dcds.2004.10.755

[12]

Peter Birkner, Nicolas Thériault. Efficient halving for genus 3 curves over binary fields. Advances in Mathematics of Communications, 2010, 4 (1) : 23-47. doi: 10.3934/amc.2010.4.23

[13]

Igor E. Shparlinski. On some dynamical systems in finite fields and residue rings. Discrete and Continuous Dynamical Systems, 2007, 17 (4) : 901-917. doi: 10.3934/dcds.2007.17.901

[14]

Jean-François Biasse, Michael J. Jacobson, Jr.. Smoothness testing of polynomials over finite fields. Advances in Mathematics of Communications, 2014, 8 (4) : 459-477. doi: 10.3934/amc.2014.8.459

[15]

Shengtian Yang, Thomas Honold. Good random matrices over finite fields. Advances in Mathematics of Communications, 2012, 6 (2) : 203-227. doi: 10.3934/amc.2012.6.203

[16]

Francis N. Castro, Carlos Corrada-Bravo, Natalia Pacheco-Tallaj, Ivelisse Rubio. Explicit formulas for monomial involutions over finite fields. Advances in Mathematics of Communications, 2017, 11 (2) : 301-306. doi: 10.3934/amc.2017022

[17]

Robert Granger, Thorsten Kleinjung, Jens Zumbrägel. Indiscreet logarithms in finite fields of small characteristic. Advances in Mathematics of Communications, 2018, 12 (2) : 263-286. doi: 10.3934/amc.2018017

[18]

Fatma-Zohra Benahmed, Kenza Guenda, Aicha Batoul, Thomas Aaron Gulliver. Some new constructions of isodual and LCD codes over finite fields. Advances in Mathematics of Communications, 2019, 13 (2) : 281-296. doi: 10.3934/amc.2019019

[19]

Shudi Yang, Xiangli Kong, Xueying Shi. Complete weight enumerators of a class of linear codes over finite fields. Advances in Mathematics of Communications, 2021, 15 (1) : 99-112. doi: 10.3934/amc.2020045

[20]

Zilong Wang, Guang Gong. Correlation of binary sequence families derived from the multiplicative characters of finite fields. Advances in Mathematics of Communications, 2013, 7 (4) : 475-484. doi: 10.3934/amc.2013.7.475

2021 Impact Factor: 1.015

Article outline

Figures and Tables

[Back to Top]