\`x^2+y_1+z_12^34\`
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.

    Citation:

    \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.

    [2]

    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.

    [3]

    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.

    [4]

    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.

    [5]

    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.

    [6]

    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.

    [7]

    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.

    [8]

    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.

    [9]

    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.

    [10]

    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.

    [11]

    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.

    [12]

    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.

    [13]

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

    [14]

    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.

    [15]

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

    [16]

    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.

    [17]

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

    [18]

    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.

    [19]

    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.

    [20]

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

    [21]

    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.

    [22]

    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.

    [23]

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

    [24]

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

    [25]

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

    [26]

    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.

    [27]

    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.

    [28]

    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.

    [29]

    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.

    [30]

    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.

    [31]

    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.

    [32]

    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.

    [33]

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

    [34]

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

    [35]

    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.

    [36]

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

    [37]

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

    [38]

    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.

    [39]

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

    [40]

    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.

    [41]

    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.

    [42]

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

    [43]

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

    [44]

    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.

    [45]

    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.

    [46]

    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.

    [47]

    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.

    [48]

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

    [49]

    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.

    [50]

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

    [51]

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

    [52]

    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.

    [53]

    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.

  • 加载中
SHARE

Article Metrics

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

Access History

Other Articles By Authors

Catalog

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return