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