Advanced Search
Article Contents
Article Contents

Ideal forms of Coppersmith's theorem and Guruswami-Sudan list decoding

Abstract Related Papers Cited by
  • We develop a framework for solving polynomial equations with size constraints on solutions. We obtain our results by showing how to apply a technique of Coppersmith for finding small solutions of polynomial equations modulo integers to analogous problems over polynomial rings, number fields, and function fields. This gives us a unified view of several problems arising naturally in cryptography, coding theory, and the study of lattices. We give (1) a polynomial-time algorithm for finding small solutions of polynomial equations modulo ideals over algebraic number fields, (2) a faster variant of the Guruswami-Sudan algorithm for list decoding of Reed-Solomon codes, and (3) an algorithm for list decoding of algebraic-geometric codes that handles both single-point and multi-point codes. Coppersmith's algorithm uses lattice basis reduction to find a short vector in a carefully constructed lattice; powerful analogies from algebraic number theory allow us to identify the appropriate analogue of a lattice in each application and provide efficient algorithms to find a suitably short vector, thus allowing us to give completely parallel proofs of the above theorems.
    Mathematics Subject Classification: Primary: 58F15, 58F17; Secondary: 53C35.


    \begin{equation} \\ \end{equation}
  • [1]

    M. Ajtai, The shortest vector problem in $L_2$ is NP-hard for randomized reductions, in Proc. 30th Ann. ACM Symp. Theory Comput., Assoc. Comput. Mach., New York, 1998, 10-19.doi: 10.1145/276698.276705.


    M. Ajtai, R. Kumar and D. Sivakumar, A sieve algorithm for the shortest lattice vector problem, in Proc. 33rd Ann. ACM Symp. Theory Comput., Assoc. Comput. Mach., New York, 2001, 601-610.doi: 10.1145/380752.380857.


    M. Alekhnovich, Linear Diophantine equations over polynomials and soft decoding of Reed-Solomon codes, IEEE Trans. Inf. Theory, 51 (2005), 2257-2265.doi: 10.1109/TIT.2005.850097.


    P. Beelen and K. Brander, Efficient list decoding of a class of algebraic-geometry codes, Adv. Math. Commun., 4 (2010), 485-518.doi: 10.3934/amc.2010.4.485.


    P. Beelen and K. Brander, Key equations for list decoding of Reed-Solomon codes and how to solve them, J. Symb. Comput., 45 (2010), 773-786.doi: 10.1016/j.jsc.2010.03.010.


    D. J. Bernstein, Reducing lattice bases to find small-height values of univariate polynomials, in Algorithmic Number Theory: Lattices, Number Fields, Curves and Cryptography, Cambridge Univ. Press, Cambridge, 2008, 421-446.


    D. J. Bernstein, List decoding for binary Goppa codes, in Coding and Cryptology, Springer-Verlag, Berlin, 2011, 62-80.doi: 10.1007/978-3-642-20901-7_4.


    J.-F. Biasse and G. Quintin, An algorithm for list decoding number field codes, in 2012 IEEE Int. Symp. Inf. Theory Proc., IEEE, 2012, 91-95.doi: 10.1109/ISIT.2012.6284696.


    D. Bleichenbacher and P. Q. Nguyen, Noisy polynomial interpolation and noisy Chinese remaindering, in Adv. Crypt. - EUROCRYPT 2000, Springer-Verlag, Berlin, 2000, 53-69.doi: 10.1007/3-540-45539-6_4.


    J. Blömer and A. May, New partial key exposure attacks on RSA, in Adv. Crypt. - CRYPTO 2003, Springer-Verlag, Berlin, 2003, 27-43.doi: 10.1007/978-3-540-45146-4_2.


    D. Boneh, Finding smooth integers in short intervals using CRT decoding, in Proc. 32nd Ann. ACM Symp. Theory Comput., Assoc. Comput. Mach., New York, 2000, 265-272.doi: 10.1145/335305.335337.


    D. Boneh, G. Durfee and Y. Frankel, An attack on RSA given a small fraction of the private key bits, in Adv. Crypt. - ASIACRYPT '98, Springer-Verlag, Berlin, 1998, 25-34.doi: 10.1007/3-540-49649-1_3.


    J. Buchmann, T. Takagi and U. Vollmer, Number field cryptography, in High Primes and Misdemeanours, Amer. Math. Soc., Providence, 2004, 111-121.


    M. F. I. Chowdhury, C.-P. Jeannerod, V. Neiger, É. Schost and G. Villard, Faster algorithms for multivariate interpolation with multiplicities and simultaneous polynomial approxima-tions, IEEE Trans. Inf. Theory, 61 (2015), 2370-2387.doi: 10.1109/TIT.2015.2416068.


    H. Cohen, A Course in Computational Algebraic Number Theory, Springer-Verlag, Berlin, 1993.doi: 10.1007/978-3-662-02945-9.


    H. Cohn and N. Heninger, Approximate common divisors via lattices, in Proc. 10th Algor. Number Theory Symp., Math. Sci. Publ., Berkeley, 2013, 271-293.doi: 10.2140/obs.2013.1.271.


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


    D. Coppersmith, Finding small solutions to small degree polynomials, in Cryptography and Lattices, Springer-Verlag, Berlin, 2001, 20-31.doi: 10.1007/3-540-44670-2_3.


    D. Coppersmith, N. Howgrave-Graham and S. V. Nagaraj, Divisors in residue classes, constructively, Math. Comp., 77 (2008), 531-545.doi: 10.1090/S0025-5718-07-02007-8.


    N. Coxon, List decoding of number field codes, Des. Codes Cryptogr., 72 (2014), 687-711.doi: 10.1007/s10623-013-9803-x.


    C. Fieker and M. E. Pohst, On lattices over number fields, in Algorithmic Number Theory, Springer-Verlag, Berlin, 1996, 133-139.doi: 10.1007/3-540-61581-4_48.


    C. Fieker and D. Stehlé, Short bases of lattices over number fields, in Algorithmic Number Theory, Springer-Verlag, Berlin, 2010, 157-173.doi: 10.1007/978-3-642-14518-6_15.


    J. von zur Gathen, Hensel and Newton methods in valuation rings, Math. Comp., 42 (1984), 637-661.doi: 10.2307/2007608.


    J. von zur Gathen and J. Gerhard, Modern Computer Algebra, 2nd edition, Cambridge Univ. Press, Cambridge, 2003.


    J. von zur Gathen and E. Kaltofen, Factorization of multivariate polynomials over finite fields, Math. Comp., 45 (1985), 251-261.doi: 10.2307/2008063.


    P. Giorgi, C.-P. Jeannerod and G. Villard, On the complexity of polynomial matrix computations, in Proc. 2003 Int. Symp. Symb. Algebr. Comput., Assoc. Comput. Mach., New York, 2003, 135-142.doi: 10.1145/860854.860889.


    E. Grigorescu and C. Peikert, List decoding Barnes-Wall lattices, in Proc. 27th IEEE Conf. Comput. Compl., IEEE Comp. Soc., Los Alamitos, 2012, 316-325.doi: 10.1109/CCC.2012.33.


    V. Guruswami and A. Rudra, Explicit codes achieving list decoding capacity: error correction with optimal redundancy, IEEE Trans. Inf. Theory, 54 (2008), 135-150.doi: 10.1109/TIT.2007.911222.


    V. Guruswami, A. Sahai and M. Sudan, "Soft-decision'' decoding of Chinese remainder codes, in Proc. 41st Ann. Symp. Found. Comp. Sci., IEEE Comp. Soc., Los Alamitos, 2000, 159-168.doi: 10.1109/SFCS.2000.892076.


    V. Guruswami and M. Sudan, Improved decoding of Reed-Solomon and algebraic-geometry codes, IEEE Trans. Inf. Theory, 45 (1999), 1757-1767.doi: 10.1109/18.782097.


    N. Howgrave-Graham, Approximate integer common divisors, in Cryptography and Lattices, Springer-Verlag, Berlin, 2001, 51-66.doi: 10.1007/3-540-44670-2_6.


    M.-D. Huang and D. Ierardi, Efficient algorithms for the Riemann-Roch problem and for addition in the Jacobian of a curve, J. Symb. Comput., 18 (1994), 519-539.doi: 10.1006/jsco.1994.1063.


    T. Kailath, Linear Systems, Prentice-Hall, Inc., Upper Saddle River, 1980.


    S. V. Konyagin and T. Steger, On polynomial congruences, Math. Notes, 55 (1994), 596-600.doi: 10.1007/BF02110354.


    A. K. Lenstra, Factoring polynomials over algebraic number fields, in Computer Algebra, Springer-Verlag, Berlin, 1983, 245-254.doi: 10.1007/3-540-12868-9_108.


    A. K. Lenstra, Factoring multivariate polynomials over algebraic number fields, SIAM J. Comput., 16 (1987), 591-598.doi: 10.1137/0216040.


    H. W. Lenstra, Algorithms in algebraic number theory, Bull. Amer. Math. Soc., 26 (1992), 211-244.doi: 10.1090/S0273-0979-1992-00284-7.


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


    D. Lorenzini, An Invitation to Arithmetic Geometry, Amer. Math. Soc., Providence, 1996.doi: 10.1090/gsm/009.


    V. Lyubashevsky, C. Peikert and O. Regev, On ideal lattices and learning with errors over rings, in Adv. Crypt. - EUROCRYPT 2010, Springer-Verlag, Berlin, 2010, 1-23.doi: 10.1007/978-3-642-13190-5_1.


    K. Manders and L. Adleman, NP-complete decision problems for quadratic polynomials, in Proc. 8th Ann. ACM Symp. Theory Comp., Assoc. Comp. Mach., New York, 1976, 23-29.doi: 10.1145/800113.803627.


    R. C. Mason, Diophantine Equations over Function Fields, Cambridge Univ. Press, Cambridge, 1984.doi: 10.1017/CBO9780511752490.


    A. May, New RSA Vulnerabilities Using Lattice Reduction Methods, Ph.D. thesis, Univ. Paderborn, 2003.


    A. May, Using LLL-reduction for solving RSA and factorization problems, in The LLL Algorithm, Springer-Verlag, Berlin, 2010, 315-348.doi: 10.1007/978-3-642-02295-1_10.


    M. Naor and B. Pinkas, Oblivious transfer and polynomial evaluation, in Proc. 31st Ann. ACM Symp. Theory Comp., Assoc. Comp. Mach., New York, 1999, 245-254.doi: 10.1145/301250.301312.


    F. Parvaresh and A. Vardy, Correcting errors beyond the Guruswami-Sudan radius in polynomial time, in Proc. 46th IEEE Symp. Found. Comp. Sci., IEEE Comp. Soc., Los Alamitos, 2005, 285-294.doi: 10.1109/SFCS.2005.29.


    C. Peikert and A. Rosen, Lattices that admit logarithmic worst-case to average-case connection factors, in Proc. 39th Ann. ACM Symp. Theory Comp., Assoc. Comp. Mach., New York, 2007, 478-487.doi: 10.1145/1250790.1250860.


    M. Rosen, Number Theory in Function Fields, Springer-Verlag, New York, 2002.doi: 10.1007/978-1-4757-6046-0.


    M. A. Shokrollahi and H. Wasserman, List decoding of algebraic-geometric codes, IEEE Trans. Inf. Theory, 45 (1999), 432-437.doi: 10.1109/18.748993.


    V. Shoup, OAEP reconsidered, in Adv. Crypt. - CRYPTO 2001, Springer-Verlag, Berlin, 2001, 239-259.doi: 10.1007/3-540-44647-8_15.


    H. Stichtenoth, Algebraic Function Fields and Codes, 2nd edition, Springer-Verlag, Berlin, 2010.doi: 10.1007/978-3-540-76878-4.


    M. Sudan, Ideal error-correcting codes: Unifying algebraic and number-theoretic algorithms in Applied Algebra, Algebraic Algorithms and Error-Correcting Codes, Springer-Verlag, Berlin, 2001, 36-45.doi: 10.1007/3-540-45624-4_4.


    V. Vassilevska Williams, Multiplying matrices faster than Coppersmith-Winograd, in Proc. 44th ACM Symp. Theory Comp., Assoc. Comp. Mach., New York, 2012, 887-898.doi: 10.1145/2213977.2214056.

  • 加载中

Article Metrics

HTML views() PDF downloads(211) Cited by(0)

Access History

Other Articles By Authors



    DownLoad:  Full-Size Img  PowerPoint