American Institute of Mathematical Sciences

Advanced
August  2015, 9(3): 311-339. doi: 10.3934/amc.2015.9.311

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, United States
2. 

Department of Computer and Information Science, University of Pennsylvania, Philadelphia, PA 19104, United States

Received  February 2014 Published  July 2015

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: Coppersmith's theorem, Lattice basis reduction, list decoding..
Mathematics Subject Classification: Primary: 58F15, 58F17; Secondary: 53C3.
Citation: Henry Cohn, Nadia Heninger. Ideal forms of Coppersmith's theorem and Guruswami-Sudan list decoding. Advances in Mathematics of Communications, 2015, 9 (3) : 311-339. doi: 10.3934/amc.2015.9.311
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.  Google Scholar

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

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

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

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

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

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

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

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

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

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

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

[13]

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

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

[15]

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

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

[17]

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

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

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

[20]

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

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

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

[23]

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

[24]

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

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

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

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

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

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

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

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

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

[33]

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

[34]

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

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

[36]

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

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

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

[39]

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

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

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

[42]

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

[43]

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

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

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

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

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

[48]

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

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

[50]

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

[51]

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

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

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

show all references

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.  Google Scholar

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

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

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

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

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

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

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

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

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

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

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

[13]

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

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

[15]

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

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

[17]

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

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

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

[20]

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

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

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

[23]

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

[24]

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

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

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

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

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

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

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

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

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

[33]

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

[34]

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

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

[36]

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

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

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

[39]

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

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

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

[42]

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

[43]

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

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

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

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

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

[48]

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

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

[50]

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

[51]

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

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

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

[1]

Ahmed S. Mansour, Holger Boche, Rafael F. Schaefer. The secrecy capacity of the arbitrarily varying wiretap channel under list decoding. Advances in Mathematics of Communications, 2019, 13 (1) : 11-39. doi: 10.3934/amc.2019002
[2]

Peter Beelen, Kristian Brander. Efficient list decoding of a class of algebraic-geometry codes. Advances in Mathematics of Communications, 2010, 4 (4) : 485-518. doi: 10.3934/amc.2010.4.485
[3]

Thomas Espitau, Antoine Joux. Certified lattice reduction. Advances in Mathematics of Communications, 2020, 14 (1) : 137-159. doi: 10.3934/amc.2020011
[4]

Holger Boche, Rafael F. Schaefer. Arbitrarily varying multiple access channels with conferencing encoders: List decoding and finite coordination resources. Advances in Mathematics of Communications, 2016, 10 (2) : 333-354. doi: 10.3934/amc.2016009
[5]

Jonas Eriksson. A weight-based characterization of the set of correctable error patterns under list-of-2 decoding. Advances in Mathematics of Communications, 2007, 1 (3) : 331-356. doi: 10.3934/amc.2007.1.331
[6]

Fernando Hernando, Tom Høholdt, Diego Ruano. List decoding of matrix-product codes from nested codes: An application to quasi-cyclic codes. Advances in Mathematics of Communications, 2012, 6 (3) : 259-272. doi: 10.3934/amc.2012.6.259
[7]

John Hubbard, Yulij Ilyashenko. A proof of Kolmogorov's theorem. Discrete & Continuous Dynamical Systems, 2004, 10 (1&2) : 367-385. doi: 10.3934/dcds.2004.10.367
[8]

Rabah Amir, Igor V. Evstigneev. On Zermelo's theorem. Journal of Dynamics & Games, 2017, 4 (3) : 191-194. doi: 10.3934/jdg.2017011
[9]

Hahng-Yun Chu, Se-Hyun Ku, Jong-Suh Park. Conley's theorem for dispersive systems. Discrete & Continuous Dynamical Systems - S, 2015, 8 (2) : 313-321. doi: 10.3934/dcdss.2015.8.313
[10]

Sergei Ivanov. On Helly's theorem in geodesic spaces. Electronic Research Announcements, 2014, 21: 109-112. doi: 10.3934/era.2014.21.109
[11]

Rentsen Enkhbat, Evgeniya A. Finkelstein, Anton S. Anikin, Alexandr Yu. Gornov. Global optimization reduction of generalized Malfatti's problem. Numerical Algebra, Control & Optimization, 2017, 7 (2) : 211-221. doi: 10.3934/naco.2017015
[12]

Daniele Mundici. The Haar theorem for lattice-ordered abelian groups with order-unit. Discrete & Continuous Dynamical Systems, 2008, 21 (2) : 537-549. doi: 10.3934/dcds.2008.21.537
[13]

Nikolai Dokuchaev. Dimension reduction and Mutual Fund Theorem in maximin setting for bond market. Discrete & Continuous Dynamical Systems - B, 2011, 16 (4) : 1039-1053. doi: 10.3934/dcdsb.2011.16.1039
[14]

C. D. Ahlbrandt, A. C. Peterson. A general reduction of order theorem for discrete linear symplectic systems. Conference Publications, 1998, 1998 (Special) : 7-18. doi: 10.3934/proc.1998.1998.7
[15]

Anne-Sophie de Suzzoni. Consequences of the choice of a particular basis of $L^2(S^3)$ for the cubic wave equation on the sphere and the Euclidean space. Communications on Pure & Applied Analysis, 2014, 13 (3) : 991-1015. doi: 10.3934/cpaa.2014.13.991
[16]

Pengyan Wang, Pengcheng Niu. Liouville's theorem for a fractional elliptic system. Discrete & Continuous Dynamical Systems, 2019, 39 (3) : 1545-1558. doi: 10.3934/dcds.2019067
[17]

V. Niţicâ. Journé's theorem for $C^{n,\omega}$ regularity. Discrete & Continuous Dynamical Systems, 2008, 22 (1&2) : 413-425. doi: 10.3934/dcds.2008.22.413
[18]

Jacques Féjoz. On "Arnold's theorem" on the stability of the solar system. Discrete & Continuous Dynamical Systems, 2013, 33 (8) : 3555-3565. doi: 10.3934/dcds.2013.33.3555
[19]

Lena Noethen, Sebastian Walcher. Tikhonov's theorem and quasi-steady state. Discrete & Continuous Dynamical Systems - B, 2011, 16 (3) : 945-961. doi: 10.3934/dcdsb.2011.16.945
[20]

Dmitry Kleinbock, Barak Weiss. Dirichlet's theorem on diophantine approximation and homogeneous flows. Journal of Modern Dynamics, 2008, 2 (1) : 43-62. doi: 10.3934/jmd.2008.2.43

2020 Impact Factor: 0.935

Tools

Metrics

  • PDF downloads (145)
  • HTML views (0)
  • Cited by (4)

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences | Privacy Policy