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

Henry  Cohn; Nadia  Heninger

doi:10.3934/amc.2015.9.311

Article Contents

2015, Volume 9, Issue 3: 311-339. Doi: 10.3934/amc.2015.9.311

This issue Previous Article On weighted minihypers in finite projective spaces of square order Next Article Weight distributions of a class of cyclic codes from $\Bbb F_l$-conjugates

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

Henry Cohn^1, and
Nadia Heninger^2,

1.
Microsoft Research New England, One Memorial Drive, Cambridge, MA 02142
2.
Department of Computer and Information Science, University of Pennsylvania, Philadelphia, PA 19104

Received: January 31, 2014

Published: October 2015

Abstract Related Papers Cited by

Abstract

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.

Keywords:

Mathematics Subject Classification: Primary: 58F15, 58F17; Secondary: 53C35.

Citation:

Related Papers

Cited by

References

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