Reconstructing points of superelliptic curves over a prime finite field

Jaime Gutierrez

doi:10.3934/amc.2022022

Article Contents

2024, Volume 18, Issue 1: 222-232. Doi: 10.3934/amc.2022022

This issue Previous Article Infinite families of 2-designs from a class of affine-invariant codes Next Article On the hardness of the Lee syndrome decoding problem

Reconstructing points of superelliptic curves over a prime finite field

Jaime Gutierrez

University of Cantabria, Santander, E-39071, Spain

Received: April 2021

Revised: February 2022

Early access: March 2022

Published: February 2024

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

Abstract / Introduction Full Text(HTML) Figure(0) / Table(1) Related Papers Cited by

Abstract

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.

Keywords:

Mathematics Subject Classification: Primary: 11H06, 11Y16, 12Y05; Secondary: 11K16.

Citation:

Full Text(HTML)

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

| Show Table

DownLoad: CSV

Related Papers

Cited by

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. Blackburn, D. Gomez-Perez, J. 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. Blackburn, D. Gomez-Perez, J. 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. Chang, J. Cilleruelo, M. Z. Garaev, J. Hernández, I. 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. Frieze, J. Håstad, R. Kannan, J. 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. Lenstra, H. 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.