Interpolation and Approximation of Polynomials in Finite Fields over a Short Interval from Noisy Values

REFERENCES

• [Akavia 09] A. Akavia. “Solving Hidden Number Problem with One Bit Oracle and Advice.” In Advances in Cryptology – CRYPTO 2009, Lect. Notes in Comp. Sci. 5677, pp. 337–354. Springer, 2009.
   Google Scholar
• [Boneh and Venkatesan 96] D. Boneh, and R. Venkatesan. “Hardness of Computing the Most Significant Bits of Secret Keys in Diffie–Hellman and Related Schemes.” In Advances in Cryptology - CRYPTO ’96, Lect. Notes in Comp. Sci. 1109, pp. 129–143. Springer, 1996.
   Google Scholar
• [Boneh and Venkatesan 97] D. Boneh, and R. Venkatesan. “Rounding in Lattices and Its Cryptographic Applications.” In Proc. 8th Annual ACM-SIAM Symp. on Discr. Algorithms, pp. 675–681. SIAM, 1997.
   Google Scholar
• [Chang et al.  11 M.-C. Chang, J. Cilleruelo, M. Z. Garaev, J. Hernández, I. E. Shparlinski, A. Zumalacárregui.. “Points on Curves in Small Boxes and Applications.” To appear in Michigan J. Math. Preprint at arxiv.org/abs/1111.1543, to appear.
   Google Scholar
• [Cilleruelo et al. 12] J. Cilleruelo, M. Z. Garaev, A. Ostafe, I. E. Shparlinski. “On the Concentration of Points of Polynomial Maps and Applications.” Math. Zeit. 272 (2012), 825–837.
   Web of Science ®Google Scholar
• [Cochrane et al. 03] T. Cochrane, C. Pinner, and J. Rosenhouse. “Bounds on Exponential Sums and the Polynomial Waring’s Problem .” Proc. Lond. Math. Soc. 67 (2003), 319–336.
   Web of Science ®Google Scholar
• [Conway and Sloane 99] J.H. Conway, N.J.A. Sloane, A. SchrijverSphere Packings, Lattices and Groups, 3rdedition , Grundlehren der Mathematischen Wissenschaften 290. Springer, 1999.
   Google Scholar
• [Garcia-Morchon et al. 12] O. Garcia-Morchon, R. Rietman, L. Tolhuizen, D. Gómez-Pérez, J. Gutierrez, and S. Merino del Pozo. “An Ultra-lightweight ID-Based Pairwise Key Establishment Scheme Aiming at Full Collusion Resistance.” , Report618, available online (http://eprint.iacr.org/2012/618), 2012.
   Google Scholar
• [Grötsche et al. 93] M. Grötschel, L. Lovász, A. Schrijver, Geometric Algorithms and Combinatorial Optimization, Algorithms and Combinatorics: Study and Research Texts 2. Springer, 1993.
   Google Scholar
• [Gruber and Lekkerkerker 87] P. M. Gruber, C. G. Lekkerkerker, Geometry of Numbers, 2ndedition , North-Holland Mathematical Library 37. North-Holland, 1987.
   Google Scholar
• [Hilbert 94] D. Hilbert. “Ein Beitrag zur Theorie des Legendre’schen Polynoms.” Acta Mathematica 18 (1894), 155–159.
   Google Scholar
• [Ivić 05] A. Ivić. “On a Problem of Erdős Involving the Largest Prime Factor of n.” Monatsh. Math. 145 (2005), 35–46.
   Web of Science ®Google Scholar
• [Iwaniec and Kowalski 04] H. Iwaniec, E. Kowalski, Analytic number theory. Amer. Math. Soc., 2004.
   Google Scholar
• [Kerr 13] B. Kerr. “Solutions to Polynomial Congruences in Well Shaped Sets.” Bull. Aust. Math. Soc. 88 (2013), 435–447.
   Web of Science ®Google Scholar
• [Lenstra et al. 82] A. K. Lenstra, H. W. Lenstra, and L. Lovász. “Factoring Polynomials with Rational Coefficients.” Mathem. Ann. 261 (1982), 515–534.
   Web of Science ®Google Scholar
• [Lidl and Niederreiter 97] R. Lidl, H. Niederreiter, Finite fields. Cambridge Univ. Press, 1997.
   Google Scholar
• [Micciancio 98] D. Micciancio. “On the Hardness of the Shortest Vector Problem.” PhD thesis, MIT, 1998.
   Google Scholar
• [Micciancio and Voulgaris 13] D. Micciancio, and P. Voulgaris. “A Deterministic Single Exponential Time Algorithm for Most Lattice Problems Based on Voronoi Cell Computations.” SIAM J. Comp. 42 (2013), 1364–1391.
   Web of Science ®Google Scholar
• [Montgomery 94] H. L. Montgomery, Ten Lectures on the Interface between Analytic Number Theory and Harmonic Analysis. Amer. Math. Soc., 1994.
   Google Scholar
• [Nguyen 09] P. Q. Nguyen. “Public-Key Cryptanalysis.” In Recent Trends in Cryptography, Contemp. Math. 477, pp. 67–119. Amer. Math. Soc., 2009.
   Google Scholar
• [Nguyen and Stern 00] P. Q. Nguyen and J. Stern. “Lattice Reduction in Cryptology: An Update.” In Algorithmic Number Theory, ANTS-IV, Lect. Notes in Comp. Sci. 1838, pp. 85–112. Springer, 2000.
   Google Scholar
• [Nguyen and Stern 01] P. Q.Nguyen, and J. Stern. “The Two Faces of Lattices in Cryptology.” , 2001.
   Google Scholar
• [Regev 10] O. Regev. “On the Complexity of Lattice Problems with Polynomial Approximation Factors.” In The LLL Algorithm: Surveys and Applications, pp. 475–496. Springer, 2010.
   Google Scholar
• [Shparlinski 01]] I.E. Shparlinski. “Sparse Polynomial Approximation In Finite Fields.” In STOC’01, July 6–8, 2001, Hersonissos, Crete, Greece., pp. 209–215. ACM, 2001.
   Google Scholar
• [Shparlinski 05] I.E. Shparlinski. “Playing ‘Hide-and-Seek’ with Numbers: The Hidden Number Problem, Lattices and Exponential Sums.” In Public-Key Cryptography, Proc. Symp. in Appl. Math. 62, pp. 153–177. Amer. Math. Soc., 2005.
   Google Scholar
• [Shparlinski and Winterhof 05] I.E.Shparlinski, and A. Winterhof. “Noisy Interpolation of Sparse Polynomials in Finite Fields.” Appl. Algebra in Engin., Commun. and Computing, 16 (2005), 307–317.
   Web of Science ®Google Scholar
• [Von zur Gathen and Shparlinski 04] J.vonzur Gathen, and I. E. Shparlinski. “Polynomial Interpolation from Multiples.” In Proc. 15th ACM-SIAM Symposium on Discrete Algorithms, pp. 1125–1130. SIAM, 2004.
   Google Scholar
• [Wooley 11] T.D. Wooley. “Multigrade Efficient Congruencing and Vinogradov’s Mean Value Theorem.” arxiv.org/abs/1310.8447, 2011.
   Google Scholar
• [Wooley 12] T.D. Wooley[Wooley 12] T.D. Wooley. “Vinogradov’s Mean Value Theorem via Efficient Congruencing.” Ann. Math. 175 (2012), 1575–1627.
   Web of Science ®Google Scholar
• [Wooley 13] T.D. Wooley. “Vinogradov’s Mean Value Theorem via Efficient Congruencing, II.” Duke Math. J. 162 (2013), 673–730.
   Web of Science ®Google Scholar