Article Contents
Article Contents

# Reconstructing points of superelliptic curves over a prime finite field

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.

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

 Citation:

•  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$ then6 | return$(w_0+\varepsilon_0, w_1+\varepsilon_1)$7 else8 | return$(0,0)$9 end
•  [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.

Tables(1)