Sparse polynomial approximation in finite fields

ABSTRACT

We consider a polynomial analogue of the hidden number problem which has recently been introduced by Boneh and Venkatesan. Namely we consider the sparse polynomial approximation problem of recovering an unknown polynomial f(X) \in \F_p[X] with at most $m$ non-zero terms from approximate values of f(t) at polynomially many points t \in \F_p selected uniformly at random. The case of a polynomial f(X) = &agr; X corresponds to the hidden number problem. The above problem is related to the noisy polynomial interpolation problem and to the sparse polynomial interpolation problem which have recently been considered in the literature. Our results are based on a combination of some number theory tools such as bounds of exponential sums and the number of solutions of congruences with the lattice reduction technique.

REFERENCES

• 1: Miklós Ajtai , Ravi Kumar , D. Sivakumar, A sieve algorithm for the shortest lattice vector problem, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.601-610, July 2001, Hersonissos, Greece [doi>10.1145/380752.380857]
• 2: Sigal Ar , Richard J. Lipton , Ronitt Rubinfeld , Madhu Sudan, Reconstructing Algebraic Functions from Mixed Data, SIAM Journal on Computing, v.28 n.2, p.487-510, April 1999 [doi>10.1137/S0097539796297577]
• 3: Sanjeev Arora , Madhu Sudan, Improved low-degree testing and its applications, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.485-495, May 04-06, 1997, El Paso, Texas, United States [doi>10.1145/258533.258642]
• 4: D.Bleichenbacher and P.Q.Nguyen,Noisy polynomial interpolation and noisy Chinese remaindering,Lect.Notes in Comp.Sci., Springer-Verlag,Berlin,1807 (2000),53 -69.
• 5: Dan Boneh , Ramarathnam Venkatesan, Hardness of Computing the Most Significant Bits of Secret Keys in Diffie-Hellman and Related Schemes, Proceedings of the 16th Annual International Cryptology Conference on Advances in Cryptology, p.129-142, August 18-22, 1996
• 6: Dan Boneh , Ramarathnam Venkatesan, Rounding in lattices and its cryptographic applications, Proceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms, p.675-682, January 05-07, 1997, New Orleans, Louisiana, United States
• 7: R.Canetti,J.B.Friedlander,S.Konyagin, M.Larsen,D.Lieman and I.E.Shparlinski,On the statistical properties of Di .e -Hellman distributions, Israel J.Math.,120 (2000),23 -46.
• 8: Michael Clausen , Andreas Dress , Johannes Grabmeier , Marek Karpinski, On zero-testing and interpolation of k -sparse multivariate polynomials over finite fields, Theoretical Computer Science, v.84 n.2, p.151-164, July 29, 1991 [doi>10.1016/0304-3975(91)90157-W]
• 9: Edwin El Mahassni , Phong Q. Nguyen , Igor Shparlinski, The Insecurity of Nyberg-Rueppel and Other DSA-Like Signature Schemes with Partially Known Nonces, Revised Papers from the International Conference on Cryptography and Lattices, p.97-109, March 29-30, 2001
• 10: John Friedlander , Michael Larsen , Daniel Lieman , Igor Shparlinski, On The Correlation Of Binary $M$-sequences, Designs, Codes and Cryptography, v.16 n.3, p.249-256, May 1999 [doi>10.1023/A:1008383811226]
• 11: O.Goldreich,R.Rubinfeld and M.Sudan,Learning polynomials with queries:the highly noisy case, Electronic Colloq.on Comp.Compl.,Univ.of Trier, TR1998-060 (1998),1 -34.
• 12: M.I.Gonzalez Vasco and I.E.Shparlinski,On the security of Di .e -Hellman bits,Proc.Workshop on Cryptography and Computational Number Theory, Singapore 1999,Birkhauser,2001,257 -268.
• 13: Maria Isabel González Vasco , Igor E. Shparlinski, Security of the most significant bits of the Shamir message passing scheme, Mathematics of Computation, v.71 n.237, p.333-342, January 2002 [doi>10.1090/S0025-5718-01-01358-8]
• 14: M.I.Gonzalez Vasco and I.E.Shparlinski,'Trace interpolation problem for polynomials over .nite .elds',Preprint, 2001,1 -11.
• 15: Dima Grigoriev , Marek Karpinski , Michael F. Singer, Computational Complexity of Sparse Rational Interpolation, SIAM Journal on Computing, v.23 n.1, p.1-12, Feb. 1994 [doi>10.1137/S0097539791194069]
• 16: V.Guruswami and M.Sudan,Improved decoding of Reed -Solomon and algebraic geometric codes,IEEE Trans.Inform.Theory,45 (1999),1757 -1767.
• 17: N. A. Howgrave-Graham , N. P. Smart, Lattice Attacks on Digital Signature Schemes, Designs, Codes and Cryptography, v.23 n.3, p.283-290, August 2001 [doi>10.1023/A:1011214926272]
• 18: R.Kannan,Algorithmic geometry of numbers, Annual Review of Comp.Sci.,2 (1987),231 -267.
• 19: Ravi Kannan, Minkowski's convex body theorem and integer programming, Mathematics of Operations Research, v.12 n.3, p.415-440, August 1, 1987 [doi>10.1287/moor.12.3.415]
• 20: M.Kiwi,F.Magniez and M.Santha,Exact and approximate testing/coorecting of algebraic functions:A survey,Electronic Colloq.on Comp. Compl.,Univ.of Trier,TR2001-014 (2001),1
• 21: Y. N. Lakshman , B. David Saunders, Sparse Polynomial Interpolation in Nonstandard Bases, SIAM Journal on Computing, v.24 n.2, p.387-397, April 1995 [doi>10.1137/S0097539792237784]
• 22: A.K.Lenstra,H.W.Lenstra and L.Lovasz, Factoring polynomials with rational coe .cients, Mathematische Annalen,261 (1982),515 -534.
• 23: Arjen K. Lenstra , Eric R. Verheul, The XTR Public Key System, Proceedings of the 20th Annual International Cryptology Conference on Advances in Cryptology, p.1-19, August 20-24, 2000
• 24: Arjen K. Lenstra , Eric R. Verheul, Key Improvements to XTR, Proceedings of the 6th International Conference on the Theory and Application of Cryptology and Information Security: Advances in Cryptology, p.220-233, December 03-07, 2000
• 25: Rudolf Lide , Harald Niederreiter, Finite fields, Cambridge University Press, New York, NY, 1996
• 26: S.Micali and C.P.Schnorr,E .cient,perfect polynomial random number generators,J. Cryptology,3 (1991),157 -172.
• 27: Daniele Micciancio , Shafi Goldwasser, On the hardness of the shortest vector problem, 1998
• 28: P.Q.Nguyen,The dark side of the Hidden Number Problem:Lattice attacks on DSA,Proc.Workshop on Cryptography and Computational Number Theory,Singapore 1999,Birkhauser,2001,321 -330.
• 29: P.Q.Nguyen and I.E.Shparlinski,The insecurity of the Digital Signature Algorithm with partially known nonces,Preprint,2000,1 -26.
• 30: P.Q.Nguyen and I.E.Shparlinski,The insecurity of the elliptic curve Digital Signature Algorithm with partially known nonces,Preprint,2000,1 -20.
• 31: Phong Q. Nguyen , Jacques Stern, Lattice Reduction in Cryptology: An Update, Proceedings of the 4th International Symposium on Algorithmic Number Theory, p.85-112, July 02-07, 2000
• 32: Harald Niederreiter, Random number generation and quasi-Monte Carlo methods, Society for Industrial and Applied Mathematics, Philadelphia, PA, 1992
• 33: H. Niederreiter , C. P. Schnorr, Local randomness in polynomial random number and random function generators, SIAM Journal on Computing, v.22 n.4, p.684-694, Aug. 1993 [doi>10.1137/0222045]
• 34: C. P. Schnorr, A hierarchy of polynomial time lattice basis reduction algorithms, Theoretical Computer Science, v.53 n.2-3, p.201-224, Aug. 1987 [doi>10.1016/0304-3975(87)90064-8]
• 35: M.A.Shokrollahi and H.Wasserman,List decoding of algebraic-geometric codes,IEEE Trans.Inform. Theory,45 (1999),432 -437.
• 36: I.E.Shparlinski,Security of most signi .cant bits g x 2,Preprint,2000,1 -7.
• 37: Igor Shparlinski, On the Generalised Hidden Number Problem and Bit Security of XTR, Proceedings of the 14th International Symposium on Applied Algebra, Algebraic Algorithms and Error-Correcting Codes, p.268-277, November 26-30, 2001
• 38: I.E.Shparlinski,Security of polynomial transformations of the Di .e -Hellman key,Preprint, 2000,1 -8.
• 39: Hal Wasserman, Reconstructing randomly sampled multivariate polynomials from highly noisy data, Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, p.59-67, January 25-27, 1998, San Francisco, California, United States
• 40: A.Weil,Basic number theory,Springer-Verlag,New York,1974.
• 41: K.Werther,The complexity of sparse polynomial interpolation over .nite .elds,Appl.Algebra in Engin.,Commun.and Comp.,5 (1994),91 -103.
• 42: R.Zippel,E .ective polynomial computation,Kluwer Acad.Publ.,Dordrecht,1993.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.2 Approximation
          Subjects: Spline and piecewise polynomial approximation

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems
          Subjects: Computations on polynomials

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.5 Roots of Nonlinear Equations
          Subjects: Polynomials, methods for
  G.2 DISCRETE MATHEMATICS

General Terms:
Performance, Theory, Verification

Keywords:
exponential sums, finite fields, sparse polynomials