Advances in Mathematics of Communications (AMC)

Ideal forms of Coppersmith's theorem and Guruswami-Sudan list decoding
Pages: 311 - 339, Issue 3, August 2015

doi:10.3934/amc.2015.9.311      Abstract        References        Full text (489.4K)           Related Articles

Henry Cohn - Microsoft Research New England, One Memorial Drive, Cambridge, MA 02142, United States (email)
Nadia Heninger - Department of Computer and Information Science, University of Pennsylvania, Philadelphia, PA 19104, United States (email)

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.
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.       
3 M. Alekhnovich, Linear Diophantine equations over polynomials and soft decoding of Reed-Solomon codes, IEEE Trans. Inf. Theory, 51 (2005), 2257-2265.       
4 P. Beelen and K. Brander, Efficient list decoding of a class of algebraic-geometry codes, Adv. Math. Commun., 4 (2010), 485-518.       
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.       
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.       
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.
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.       
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.       
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.       
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.       
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.       
15 H. Cohen, A Course in Computational Algebraic Number Theory, Springer-Verlag, Berlin, 1993.       
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.       
17 D. Coppersmith, Small solutions to polynomial equations, and low exponent RSA vulnerabilities, J. Cryptology, 10 (1997), 233-260.       
18 D. Coppersmith, Finding small solutions to small degree polynomials, in Cryptography and Lattices, Springer-Verlag, Berlin, 2001, 20-31.       
19 D. Coppersmith, N. Howgrave-Graham and S. V. Nagaraj, Divisors in residue classes, constructively, Math. Comp., 77 (2008), 531-545.       
20 N. Coxon, List decoding of number field codes, Des. Codes Cryptogr., 72 (2014), 687-711.       
21 C. Fieker and M. E. Pohst, On lattices over number fields, in Algorithmic Number Theory, Springer-Verlag, Berlin, 1996, 133-139.       
22 C. Fieker and D. Stehlé, Short bases of lattices over number fields, in Algorithmic Number Theory, Springer-Verlag, Berlin, 2010, 157-173.       
23 J. von zur Gathen, Hensel and Newton methods in valuation rings, Math. Comp., 42 (1984), 637-661.       
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.       
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.       
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.       
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.       
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.       
30 V. Guruswami and M. Sudan, Improved decoding of Reed-Solomon and algebraic-geometry codes, IEEE Trans. Inf. Theory, 45 (1999), 1757-1767.       
31 N. Howgrave-Graham, Approximate integer common divisors, in Cryptography and Lattices, Springer-Verlag, Berlin, 2001, 51-66.       
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.       
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.       
35 A. K. Lenstra, Factoring polynomials over algebraic number fields, in Computer Algebra, Springer-Verlag, Berlin, 1983, 245-254.       
36 A. K. Lenstra, Factoring multivariate polynomials over algebraic number fields, SIAM J. Comput., 16 (1987), 591-598.       
37 H. W. Lenstra, Algorithms in algebraic number theory, Bull. Amer. Math. Soc., 26 (1992), 211-244.       
38 A. K. Lenstra, H. W. Lenstra and L. Lovász, Factoring polynomials with rational coefficients, Math. Ann., 261 (1982), 515-534.       
39 D. Lorenzini, An Invitation to Arithmetic Geometry, Amer. Math. Soc., Providence, 1996.       
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.       
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.       
42 R. C. Mason, Diophantine Equations over Function Fields, Cambridge Univ. Press, Cambridge, 1984.       
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.
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.       
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.
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.       
48 M. Rosen, Number Theory in Function Fields, Springer-Verlag, New York, 2002.       
49 M. A. Shokrollahi and H. Wasserman, List decoding of algebraic-geometric codes, IEEE Trans. Inf. Theory, 45 (1999), 432-437.       
50 V. Shoup, OAEP reconsidered, in Adv. Crypt. - CRYPTO 2001, Springer-Verlag, Berlin, 2001, 239-259.       
51 H. Stichtenoth, Algebraic Function Fields and Codes, 2nd edition, Springer-Verlag, Berlin, 2010.       
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.       
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.       

Go to top