Télécharger

Texte intégral

• Ajtai, M.: The shortest vector problem in L2 is NP-hard for randomized reductions (extended abstract). In: STOC 1998, pp. 10-19 (1998)
• Becker, A., Coron, J.-S., Joux, A.: Improved generic algorithms for hard knapsacks. Eprint archive (2011)
• Coster, M.J., Joux, A., LaMacchia, B.A., Odlyzko, A.M., Schnorr, C.-P., Stern, J.: Improved low-density subset sum algorithms. Computational Complexity 2, 111-128 (1992)
• Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman, New York (1979)
• Howgrave-Graham, N., Joux, A.: New generic algorithms for hard knapsacks. In: Gilbert, H. (ed.) EUROCRYPT 2010. LNCS, vol. 6110, pp. 235-256. Springer, Heidelberg (2010)
• Knuth, D.E.: The Art of Computer Programming, 2nd edn. Seminumerical Algorithms, vol. II. Addison-Wesley, Reading (1981)
• Lagarias, J.C., Odlyzko, A.M.: Solving low-density subset sum problems. J. ACM 32(1), 229-246 (1985)
• Lenstra, A.K., Lenstra, H.W., Lovász, L.: Factoring polynomials with rational coefficients. Mathematische Annalen 261, 515-534 (1982)
• May, A., Meurer, A.: Personal communication
• Merkle, R.C., Hellman, M.E.: Hiding information and signatures in trapdoor knapsacks. IEEE Transactions on Information Theory 24, 525-530 (1978)
• Nguyen, P.Q., Shparlinski, I.E., Stern, J.: Distribution of modular sums and the security of the server aided exponentiation. In: Progress in Computer Science and Applied Logic, Final Proceedings of Cryptography and Computational Number Theory Workshop, Singapore, vol. 20, pp. 331-224 (2001)
• Schnorr, C.-P.: A hierarchy of polynomial time lattice basis reduction algorithms. Theor. Comput. Sci. 53, 201-224 (1987)
• Schroeppel, R., Shamir, A.: A T = O(2n/2), S = O(2 n/4) algorithm for certain NP-complete problems. SIAM J. Comput. 10(3), 456-464 (1981)
• Shamir, A.: A polynomial time algorithm for breaking the basic Merkle-Hellman cryptosystem. In: CRYPTO 1982, pp. 279-288 (1982)
• van Oorschot, P.C., Wiener, M.J.: Improving implementable meet-in-the-middle attacks by orders of magnitude. In: Koblitz, N. (ed.) CRYPTO 1996. LNCS, vol. 1109, pp. 229-236. Springer, Heidelberg (1996)
• Wagner, D.: A generalized birthday problem. In: Yung, M. (ed.) CRYPTO 2002. LNCS, vol. 2442, pp. 288-303. Springer, Heidelberg (2002)