跳转至

参考文献

  • [1] Akavia, A. (2009) “Solving Hidden Number Problem with One Bit Oracle and Advice,” in Halevi, S. (ed.) Advances in Cryptology – CRYPTO 2009. LNCS, vol. 5677,pp. 337–354. Springer, Heidelberg.

  • [2] Akavia, A., Goldwasser, S., and Safra, S. (2003) “Proving Hard-Core Predicates Using List Decoding,” in FOCS 2003, pp. 146–157. IEEE Computer Society, Washington, DC.

  • [3] Alexi, W., Chor, B., Goldreich, O., and Schnorr, C.P. (1988) “RSA and Rabin Functions: Certain Parts are as Hard as the Whole,” in SIAM Journal on Computing, 17(2), 194–209.

  • [4] Aranha, D.F., Fouque, P.-A., G ́erard B., Kammerer, J.-G., Tibouchi., M., and Zapalowicz, J.-C. (2014) “GLV/GLS Decomposition, Power Analysis, and Attacks on ECDSA Signatures with Single-Bit Nonce Bias,” in Sarkar, P., Iwata, T. (eds.) Advances in Cryptology – ASIACRYPT 2014. LNCS, vol. 8873, pp. 262–281. Springer, Heidelberg.
  • [5] Babai, L. (1986) “On Lov ́asz’ Lattice Reduction and the Nearest Lattice Point Problem,” in Combinatorica, 6(1), 1–13.
  • [6] Ben-Or, M., Chor, B., and Shamir, A. (1983) “On the Cryptographic Security of Single RSA Bits,” Johnson, D.S., Fagin, R., Fredman, M.L., Harel, D., Karp, R.M., Lynch, N.A., Papadimitriou, C.H., Rivest, R.L., Ruzzo, W.L., Seiferas, J.I. (eds.)STOC 1983, pp. 421–430. ACM, New York.
  • [7] Blake, I.F., and Garefalakis, T. (2004) “On the Complexity of the Discrete Logarithm and Diffie–Hellman Problems,” in Journal of Complexity, 20(2-3), 148–170.
  • [8] Blake, I.F., Garefalakis, T., and Shparlinski, I.E. (2006) “On the Bit Security of the Diffie–Hellman Key,” in Applicable Algebra in Engineering, Communication and Computing, 16(6), 397–404.
  • [9] Blake, I.F., Seroussi, G., and Smart, N.P. (1999) Elliptic Curves in Cryptography. Cambridge University Press.
  • [10] Bleichenbacher, D. (2000) “On the Generation of One-time Keys in DL Signature Schemes,” Presentation at IEEE P1363 Working Group meeting.
  • [11] Blackburn, S.R., Gomez-Perez, D., Gutierrez, J, and Shparlinski, I.E. (2003) “Predicting the Inversive Generator,” in Paterson, K.G. (ed.) Cryptography and Coding.LNCS, vol. 2898, pp. 264–275. Springer, Heidelberg.
  • [12] Blackburn, S.R., Gomez-Perez, D., Gutierrez, J, and Shparlinski, I.E. (2005) “Predicting Nonlinear Pseudorandom Number Generators,” in Mathematics of Computation, 74(251), 1471–1494.
  • [13] Brouwer, A.E., Pellikaan, R., and Verheul, E.R. (1999) “Doing More with Fewer Bits,” in Advances in Cryptology – ASIACRYPT ’99, 321–332.
  • [14] Boneh, D. (1998) “The Decision Diffie–Hellman problem,” in Buhler, J.P. (ed.) Algorithmic Number Theory – ANTS-III. LNCS, vol. 1423, pp. 48–63. Springer, Heidelberg.
  • [15] Boneh, D., Halevi, S., and Howgrave-Graham, N. (2001) “The Modular Inversion Hidden Number Problem,” in Boyd, C. (ed.) Advances in Cryptology – ASIACRYPT 2001. LNCS, vol. 2248, pp. 36–51. Springer, Heidelberg.
  • [16] Boneh, D., and Shparlinski, I.E. (2001) “On the Unpredictability of Bits of the Elliptic Curve Diffie–Hellman Scheme,” in Kilian, J. (ed.) Advances in Cryptology – CRYPTO 2001. LNCS, vol. 2139, pp. 201–212. Springer, Heidelberg.
  • [17] Boneh, D., and Venkatesan, R. (1996) “Hardness of Computing the Most Significant Bits of Secret Keys in Diffie–Hellman and Related Schemes,” in Koblitz, N. (ed.) Advances in Cryptology – CRYPTO ’96. LNCS, vol. 1109, pp. 129–142. Springer, Heidelberg.
  • [18] Boneh, D., and Venkatesan, R. (1997) “Rounding in Lattices and its Cryptographic Applications,” in Saks, M.E. (ed.) SODA 1997, pp. 675–681. ACM/SIAM, Philadelphia.
  • [19] Bourgain, J., and Konyagin, S.V. (2003) “Estimates for the Number of Sums and Products and for Exponential Sums over Subgroups in Fields of Prime Order,” in Comptes Rendus Mathematique, Acad. Sci. Paris, Ser. I 337(2), 75–80.
  • [20] Bourgain, J., Glibichuk, A.A., and Konyagin, S.V. (2006) “Estimates for the Number of Sums and Products and for Exponential Sums in Fields of Prime Order,” in Journal of the London Mathematical Society, 73(2), 380–398.
  • [21] Brakerski, Z., Langlois, A., Peikert, C., Regev, R., and Stehl ́e, D. (2013) “Classical Hardness of Learning with Errors,” in Proc. 45th ACM Symposium on Theory of Computing – STOC 2013, pp. 575–584. ACM, New York.
  • [22] Childs, A.M., Jao, D., and Soukharev, V. (2014) “Constructing Elliptic Curve Isogenies in Quantum Subexponential Time,” in Journal Mathematical Cryptology, 8(1), 1–29.
  • [23] Coppersmith, D. (1997) “Small Solutions to Polynomial Equations, and Low Exponent RSA Vulnerabilities,” in Journal of Cryptology, 10(4), 233–260.
  • [24] Couveignes, J.-M. (2006) “Hard Homogeneous Spaces,” in Cryptology ePrint Archive, Report 2006/291. http://eprint.iacr.org/2006/291.
  • [25] Cox, D.A. (1989) Primes of the Form x2 + ny2. John Wiley & Sons, Inc. New York.
  • [26] Cox, D.A., Little, J., and O’Shea, D. (2007) Ideals, Varieties, and Algorithms: An Introduction to Computational Algebraic Geometry and Commutative Algebra. Undergraduate Texts in Mathematics (3nd edition). Springer-Verlag, New York.
  • [27] De Mulder, E., Hutter, M., Marson, M.E., and Pearson, P. (2013) “Using Bleichenbacher’s Solution to the Hidden Number Problem to Attack Nonce Leaks in 384-Bit ECDSA,” in Bertoni, G., Coron, J.-S. (eds.), CHES 2013, Springer LNCS 8086, 435–452.
  • [28] Diffie, W., and Hellman, M.E. (1976) “New directions in cryptography,” IEEE Transactions on Information Theory, 12(6), 644–654.
  • [29] Duc, A., and Jetchev, D. (2012) “Hardness of Computing Individual Bits for One-Way Functions on Elliptic Curves,” in Safavi-Naini, R., Canetti, R. (eds.) Advances in Cryptology – CRYPTO 2012. LNCS, vol. 7417, pp. 832–849. Springer, Heidelberg.
  • [30] Fazio, N., Gennaro, R., Perera I.M., and Skeith, W.E. III (2013) “Hard-Core Predicates for a Diffie–Hellman Problem over Finite Fields,” in Canetti, R., Garay, J.A.(eds.) Advances in Cryptology – CRYPTO 2013. LNCS, vol. 8043, pp. 148–165. Springer, Heidelberg.
  • [31] Galbraith, S.D. (2012) Mathematics of Public Key Cryptography. Cambridge University Press.
  • [32] Galbraith, S.D., Hopkins, H.J., and Shparlinski, I.E. (2004) “Secure Bilinear Diffie–Hellman Bits,” in Wang, H., Pieprzyk, J., Varadharajan, V. (eds.) Information Security and Privacy – ACISP 2004, Proc. 9th Australasian Conference. LNCS, vol. 3108, pp. 370–378. Springer, Heidelberg.
  • [33] Galbraith, S.D., Laity, J., and Shani, B. (2016) “Finding Significant Fourier Coefficients: Clarifications, Simplifications, Applications and Limitations,” under review. arXiv:1607.01842 [cs.CR]. https://arxiv.org/abs/1607.01842.
  • [34] Galbraith, S.D., and Shani, B. (2015) “The Multivariate Hidden Number Problem,” in Lehmann, A., Wolf, S. (eds.) Information Theoretic Security – ICITS 2015, Proc. 8th International Conference on Information-Theoretic Security. LNCS, vol. 9063, pp. 250–268. Springer, Heidelberg.
  • [35] Galbraith, S.D., Petit, C., Shani, B., and Ti, Y.B. (2016) “On the Security of Supersingular Isogeny Cryptosystems,” in Cheon, J.H., Takagi, T. (eds.) Advances in Cryptology – ASIACRYPT 2016. LNCS, vol. 10031, pp. 63–91. Springer, Heidelberg.
  • [36] Gama, N., Izabach`ene, M., Nguyen, P.Q., and Xie, X. (2016) “Structural Lattice Reduction: Generalized Worst-Case to Average-Case Reductions and Homomorphic Cryptosystems,” in Coron, J.-S., Fischlin, M. (eds.) Advances in Cryptology – EUROCRYPT 2016. LNCS, vol. 9666, pp. 528–558. Springer, Heidelberg.
  • [37] Gilbert, A.C., Indyk, P., Iwen, M., and Schmidt, L. (2014) “Recent Developments in the Sparse Fourier Transform,” in IEEE Signal Processing Magazine, 31(5), 91–100.
  • [38] Gong, M.I., and Harn, L. (1999) “Public-Key Cryptosystems Based on Cubic Finite Field Extensions,” in IEEE Transactions on Information Theory, 45(7), 2601–2605.
  • [39] Gonz ́alez Vasco, M.I., and N ̈aslund, M. (2001) “A Survey of Hard Core Functions,” in Lam, K.-Y., Shparlinski, I., Wang, H., Xing, C. (eds.) Proc. Workshop on Cryptography and Computational Number Theory 1999. Progress in Computer Science and Applied Logic, vol. 20, pp. 227–255. Birkh ̈auser, Basel.
  • [40] Gonz ́alez Vasco, M.I., N ̈aslund, M., and Shparlinski, I.E. (2004) “New Results on the Hardness of Diffie–Hellman Bits,” in Bao, F., Deng, R., Zhou, J. (eds.) Public Key Cryptography – PKC 2004. LNCS, vol. 2947, pp. 159–172. Springer, Heidelberg.
  • [41] Gonz ́alez Vasco, M.I., and Shparlinski, I.E. (2001) “On the Security of Diffie-Hellman Bits,” in Lam, K.-Y., Shparlinski, I., Wang, H., Xing, C. (eds.) Proc. Workshop on Cryptography and Computational Number Theory 1999. Progress in Computer Science and Applied Logic, vol. 20, pp. 257–268. Birkh ̈auser, Base.
  • [42] Granger, R., Page, D., and Stam, M. (2004) “A Comparison of CEILIDH and XTR,” in Buell, D. (ed.) Algorithmic Number Theory – ANTS-VI. LNCS, Vol. 3076, pp. 235–249. Springer-Verlag.
  • [43] Granger, R., and Vercauteren, F. (2005) “On the Discrete Logarithm Problem on Algebraic Tori,” in Shoup, V. (ed.) Advances in Cryptology – CRYPTO 2005. LNCS, Vol. 3621, pp. 66–85. Springer-Verlag.
  • [44] Gross, B.H. (1987) “Heegner Points and the Modular Curve of Prime Level,” in Journal of the Mathematical Society of Japan, 39(2), 345–362.
  • [45] Howgrave-Graham, N., and Smart, N.P. (2001) “Lattice Attacks on Digital Signature Schemes,” in Designs, Codes and Cryptography, 23(3), 283–290.
  • [46] H ̊astad, J., and N ̈aslund, M. (2003) “The Security of all RSA and Discrete Log Bits,” in Journal of the ACM, 51(2), 187–230.
  • [47] Jao, D., and De Feo, L. (2011) “Towards Quantum-Resistant Cryptosystems from Supersingular Elliptic Curve Isogenies,” in Yang, B.-Y. (ed.) Post-Quantum Cryptography – PQCrypto 2011. LNCS, vol. 7071, pp. 19–34. Springer, Heidelberg.
  • [48] Jao, D., Jetchev, D., and Venkatesan, R. (2007) “On the Bits of Elliptic Curve Diffie–Hellman Keys,” in Srinathan, K., Pandu Rangan, C., Yung, M. (eds.) Progress in Cryptology – INDOCRYPT 2007. LNCS, vol. 4859, pp. 33–47. Springer, Heidelberg.
  • [49] Jetchev, D., and Venkatesan, R. (2008) “Bits Security of the Elliptic Curve Diffie–Hellman Secret Keys,” in Wagner, D. (ed.) Advances in Cryptology – CRYPTO 2008. LNCS, vol. 5157, pp. 75–92. Springer, Heidelberg.
  • [50] Joux, A. (2000) “A One Round Protocol for Tripartite Diffie-Hellman,” in Bosma, W. (ed.) Algorithmic Number Theory – ANTS-IV. LNCS, Vol. 1838, pp. 385–393. Springer-Verlag.
  • [51] Kiltz, E. (2001) “A Primitive for Proving the Security of Every Bit and About Universal Hash Functions & Hard Core Predicates,” in Freivalds, R. (ed.) Fundamentals of Computation Theory, Proc. 13th International Symposium, FCT 2001, pp. 388–391. Springer-Verlag. Full paper available at http://homepage.ruhr-uni-bochum.de/Eike.Kiltz/papers/hash_full.pdf.
  • [52] Koblitz, N. (1987) “Elliptic Curve Cryptosystems,” in Mathematics of Computation, 48(177), 203–209.
  • [53] Konyagin, S.V., and Shparlinski, I.E. (1999) Character Sums with Exponential Functions and Their Applications. Cambridge University Press.
  • [54] Kushilevitz, E., and Mansour, Y. (1991) “Learning Decision Trees Using the Fourier Sprectrum,” in Koutsougeras, C., Vitter, J.S. (eds.) STOC 1991, ACM, 455–464.
  • [55] Laity, J., and Shani, B. (2016) “On Sets of Large Fourier Transform Under Changes in Domain,” under review. arXiv:1610.04330 [math.CA]. https://arxiv.org/abs/1610.04330.
  • [56] Lenstra, A.K., Lenstra, H.W. Jr., and Lov ́asz, L. (1982) “Factoring Polynomials with Rational Coefficients,” in Mathematische Annalen, 261(4), 515–534.
  • [57] Lenstra, A.K., and Verheul, E.R. (1999) “The XTR Public Key System,” in Bellare, M. (ed.) Advances in Cryptology – CRYPTO 2000. LNCS, vol. 1880, pp. 1–19. Springer, Heidelberg.
  • [58] Lenstra, A.K., and Verheul, E.R. (2001) “An Overview of the XTR Public Key System,” in Alster, K., Urbanowicz, J., Williams H.C. (eds.) Proc. of the Public-Key Cryptography and Computational Number Theory Conference, pp. 151–180. Walter de Gruyter, Berlin.
  • [59] Li, W.-C.W., N ̈aslund, M., and Shparlinski, I.E. (2002) “Hidden Number Problem with the Trace and Bit Security of XTR and LUC,” in Yung, M. (ed.) Advances in Cryptology – CRYPTO 2002. LNCS, vol. 2442, pp. 433–448. Springer, Heidelberg.
  • [60] Lidl, R., and Niederreiter, H. (1997) Finite Fields. Cambridge University Press.
  • [61] Ling, S., Shparlinski, I.E., Steinfeld, R., and Wang, H. (2012) “On the Modular Inversion Hidden Number Problem,” in Journal of Symbolic Computation, 47(4), 358–367.
  • [62] Mansour, Y. (1992) “Randomized Interpolation and Approximation of Sparse Polynomials,” in Proceedings of the 19th International Colloquium on Automata, Languages and Programming, 261–272.
  • [63] Maurer, U.M. (1994) “Towards the Equivalence of Breaking the Diffie-Hellman Protocol and Computing Discrete Logarithms,” in Desmedt, Y.G. (ed.) Advances in Cryptology – CRYPTO ’94. LNCS, vol. 839, pp. 271–281. Springer, Heidelberg.
  • [64] Micciancio, D., and Voulgaris, P. (2013) “A Deterministic Single Exponential Time Algorithm for Most Lattice Problems Based on Voronoi Cell Computations,” in SIAM Journal on Computing, 42(3), 1364–1391.
  • [65] Miller, V.S. (1986) “Use of Elliptic Curves in Cryptography,” in Williams, H.C. (ed.) Advances in Cryptology – CRYPTO ’85. LNCS, vol. 218, pp. 417–426. Springer, Heidelberg.
  • [66] Moreno, C.J., and Moreno, O. (1991) “Exponential Sums and Goppa Codes: I,” in Proc. Amer. Math. Soc., 111, 523–531.
  • [67] Morillo, P., and R`afols, C. (2009) “The Security of All Bits Using List Decoding,” in Jarecki, S., Tsudik, G. (eds.) Public Key Cryptography – PKC 2009: Proceedings of the 12th International Conference on Practice and Theory in Public Key Cryptography. LNCS, vol. 5443, pp. 15–33. Springer, Heidelberg.
  • [68] Nguyen, P.Q., and Shparlinski, I.E. (2002) “The Insecurity of the Digital Signature Algorithm with Partially Known Nonces,” in Journal of Cryptology, 15(3), 151–176.
  • [69] Nguyen, P.Q., and Shparlinski, I.E. (2003) “The Insecurity of the Elliptic Curve Digital Signature Algorithm with Partially Known Nonces,” in Journal of Cryptology, 30(2), 201–217.
  • [70] Nguyen, P.Q., and Stern, J. (2001) “The Two Faces of Lattices in Cryptology,” in Silverman, J.H. (ed.) Cryptography and Lattices 2001. LNCS, vol. 2146, pp. 146–180. Springer, Heidelberg.
  • [71] Nguyen, P.Q., and Tibouchi, M. (2012) “Lattice-Based Fault Attacks on Signatures,” in Fault Analysis in Cryptography. Information Security and Cryptography, pp. 201–220. Springer, Heidelberg.
  • [72] Rostovtsev, A., and Stolbunov, A. (2006) “Public-Key Cryptosystem Based on Isogenies,” in Cryptology ePrint Archive, Report 2006/145. http://eprint.iacr.org/2006/145.
  • [73] Rubin, R., and Silverberg, A. (2003) “Torus-Based Cryptography,” in Boneh, D. (ed.) Advances in Cryptology – CRYPTO 2003. LNCS, vol. 2729, pp. 349–365. Springer, Heidelberg.
  • [74] Rubin, R., and Silverberg, A. (2004) “Using Primitive Subgroups to Do More with Fewer Bits,” in Buell, D. (ed.) Algorithmic Number Theory – ANTS-VI. LNCS, Vol. 3076, pp. 18–41. Springer-Verlag.
  • [75] Rubin, R., and Silverberg, A. (2008) “Compression in Finite Fields and Torus-Based Cryptography,” in SIAM Journal on Computing, 37(5), 1401–1428.
  • [76] Schnorr, C.P. (1987) “A Hierarchy of Polynomial Time Lattice Basis Reduction Algorithms,” in Theoretical Computer Science, 53(2-3), 201–224.
  • [77] Shani, B. (2017) “On the Bit Security of Elliptic Curve Diffie–Hellman,” in Fehr, S. (ed.) Public Key Cryptography – PKC 2017. LNCS, vol. 10174, pp. 361–387. Springer, Heidelberg. Full paper appears in Cryptology ePrint Archive, Report 2016/1189. http://eprint.iacr.org/2016/1189.
  • [78] Shoup, V. (1997) “Lower Bounds for Discrete Logarithms and Related Problems,” in Fumy, W. (ed.) Advances in Cryptology – EUROCRYPT ’97. LNCS, vol. 1233, pp. 256–266. Springer, Heidelberg.
  • [79] Shparlinski, I.E. (2001) “On the Generalised Hidden Number Problem and Bit Security of XTR,” in Boztas, S., Shparlinski, I.E. (eds.) Applied Algebra, Algebraic Algorithms and Error-Correcting Codes. LNCS, vol. 2227, pp. 268–277. Springer, Heidelberg.
  • [80] Shparlinski, I.E. (2001) “Sparse Polynomial Approximation in Finite Fields,” in Proc. 33rd ACM Symposium on Theory of Computing – STOC 2001, pp. 209–215. ACM, New York.
  • [81] Shparlinski, I.E. (2004) “Security of Polynomial Transformations of the Diffie–Hellman Key,” in Finite Fields and Their Applications, 10(1), pp. 123–131.
  • [82] Shparlinski, I.E. (2005) “Playing “Hide-and-Seek” with Numbers: The Hidden Number Problem, Lattices and Exponential Sums,” in Garrett, P., Lieman, D. (eds.) Public-Key Cryptography; Proceedings of Symposia in Applied Mathematics, vol. 62, AMS, pp. 153–177.
  • [83] Shparlinski, I.E., and Winterhof, A. (2003) “A Hidden Number Problem in Small Subgroups,” in Mathematics of Computation 2005, vol. 74, pp. 2073–2080.
  • [84] Shparlinski, I.E., and Winterhof, A. (2004) “A Nonuniform Algorithm for the Hidden Number Problem in Subgroups,” in Bao, F., Deng, R.H., Zhou, J. (eds.) Public Key Cryptography – PKC 2004. LNCS, vol. 2947, pp. 416–424. Springer, Heidelberg.
  • [85] Silverman, J.H. (2009) The Arithmetic of Elliptic Curves. Graduate Texts in Mathematics, vol. 106 (2nd edition). Springer-Verlag, New York.
  • [86] Smith, P., and Skinner, C. (1995) “A Public-Key Cryptosystem and a Digital Signature System Based on the Lucas Function Analogue to Discrete Logarithms,” in Pieprzyk, J., Safavi-Naini, R. (eds.) Advances in Cryptology – ASIACRYPT ’94. LNCS, vol. 917, pp. 355–364. Springer, Heidelberg.
  • [87] Stam, M. (2003) “Speeding up Subgroup Cryptosystems.” Ph.D. Thesis, Technische Universiteit Eindhoven.
  • [88] Stinson, D.R. (2005) Cryptography: Theory and Practice. Discrete Mathematics and Its Applications (3rd edition). CRC Press.
  • [89] Stolbunov, A. (2010) “Constructing Public-key Cryptographic Schemes Based on Class Group Action on a Set of Isogenous Elliptic Curves,” in Advances in Mathematics of Communications, 4(2), 215–235.
  • [90] Terras, A. (1999) Fourier Analysis on Finite Groups and Applications. London Mathematical Society Student Texts (No. 43), Cambridge University Press. Cambridge.
  • [91] Verheul, E.R. (2000) “Certificates of Recoverability with Scalable Recovery Agent Security,” in Imai, H., Zheng, Y. (eds.) Public Key Cryptography – PKC 2000. LNCS, vol. 1751, pp. 258–275. Springer, Heidelberg.
  • [92] Vinogradov, J.M. (1927) “On a General Theorem Concerning the Distribution of the Residues and Non-Residues of Powers,” in Transactions of the American Mathematical Society, 29(1), 209–217.
  • [93] Wang, Y., and Lv, K. (2016) “The Security of Polynomial Information of Diffie–Hellman Key,” in Information and Communications Security ICICS 2016, pp. 71–81.
  • [94] Wang, M., Zhan, T., and Zhang, H. (2016) “Bit Security of the CDH Problems over Finite Fields,” in Selected Areas in Cryptography – SAC 2015, pp. 441–461.
  • [95] Xu, J., Hu, L., Huang, Z., and Peng, L. (2014) “Finding Small Solutions of a Class of Simultaneous Modular Equations and Applications to Modular Inversion Hidden Number Problem and Inversive Congruential Generators,” in Cryptology ePrint Archive, Report 2014/843. http://eprint.iacr.org/2014/843.
  • [96] Zhang, Fangguo (2015) “Bit Security of the Hyperelliptic Curves Diffie–Hellman Problem,” in Cryptology ePrint Archive, Report 2015/614. http://eprint.iacr.org/2015/614