Nội dung được dịch bởi AI, chỉ mang tính chất tham khảo
Giải quyết một lớp phương trình đa thức mô-đun và mối quan hệ của nó với bài toán số ẩn đảo mô-đun và bộ sinh tường hợp đảo ngược
Tóm tắt
Trong bài báo này, chúng tôi xem xét lại bài toán số ẩn đảo mô-đun (MIHNP) và bộ sinh tường hợp đảo ngược (ICG) và xem xét cách tấn công chúng một cách hiệu quả hơn. Chúng tôi xem xét các hệ phương trình đa thức mô-đun có dạng $$a_{ij}+b_{ij}x_i+c_{ij}x_j+x_ix_j=0~(\mathrm {mod}~p)$$ và chỉ ra mối liên hệ giữa việc giải quyết các phương trình như vậy với việc tấn công MIHNP và ICG. Chúng tôi trình bày ba chiến lược hướng dẫn sử dụng kỹ thuật tìm nghiệm dựa trên lưới của Coppersmith để giải quyết các phương trình mô-đun nói trên. Trong chiến lược đầu tiên, chúng tôi sử dụng một số mẫu đa thức và đạt được cùng một giới hạn tiệm cận trong việc tấn công ICG như đã được đề xuất trong PKC 2012, đây là kết quả tốt nhất cho đến nay. Tuy nhiên, một số mẫu theo cấp số mũ là cần thiết trong công trình của PKC 2012. Trong chiến lược thứ hai, một phần các đa thức được chọn cho lưới liên quan là các tổ hợp tuyến tính của một số đa thức và điều này cho phép chúng tôi đạt được một giới hạn trên lớn hơn cho nghiệm mong muốn. Tương ứng với phân tích MIHNP, chúng tôi đưa ra một cấu trúc lưới rõ ràng của phương pháp tấn công thứ hai do Boneh, Halevi và Howgrave-Graham đề xuất trong Asiacrypt 2001. Chúng tôi cung cấp giới hạn tốt hơn so với công trình PKC 2012 trong việc tấn công ICG. Hơn nữa, chúng tôi đề xuất chiến lược thứ ba nhằm cải thiện hơn nữa trong việc thiết lập lưới liên quan theo nghĩa yêu cầu ít mẫu hơn.
Từ khóa
#MIHNP #ICG #các phương trình đa thức mô-đun #phương pháp tấn công #kỹ thuật tìm nghiệm lướiTài liệu tham khảo
Akavia A.: Solving hidden number problem with one bit oracle and advice. In: Advances in Cryptology—CRYPTO 2009: 29th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 16–20, 2009, pp. 337–354. Springer, Berlin (2009). https://doi.org/10.1007/978-3-642-03356-8_20.
Bauer A., Vergnaud D., Zapalowicz J.C.: Inferring sequences produced by nonlinear pseudorandom number generators using coppersmiths methods. In: Fischlin M., Buchmann J., Manulis M. (eds.) Public Key Cryptography-PKC 2012. Lecture Notes in Computer Science, vol. 7293, pp. 609–626. Springer, Berlin (2012). https://doi.org/10.1007/978-3-642-30057-8_36.
Blackburn S., Gomez-Perez D., Gutierrez J., Shparlinski I.: Predicting the inversive generator. In: Paterson K. (ed.) Cryptography and Coding. Lecture Notes in Computer Science, vol. 2898, pp. 264–275. Springer, Berlin (2003). https://doi.org/10.1007/978-3-540-40974-8_21.
Blackburn S.R., Gomez-perez D., Gutierrez J., Shparlinski I.E.: Predicting nonlinear pseudorandom number generators. Math. Comput. 74, 1471–1494 (2005).
Boneh D., Venkatesan R.: Hardness of computing the most significant bits of secret keys in Diffie-Hellman and related schemes. In: CRYPTO 1996, pp. 129–142. Springer, Berlin (1996).
Boneh D., Halevi S., Howgrave-Graham N.: The modular inversion hidden number problem. In: ASIACRYPT 2001, pp. 36–51. Springer, Berlin (2001).
Boyar J.: Inferring sequences produced by pseudo-random number generators. J. ACM 36(1), 129–141 (1989). https://doi.org/10.1145/58562.59305.
Comtet L.: Advanced Combinatorics. D. Reidel Publishing Company, Boston (1974).
Cox D.A.: Ideals, Varieties, and Algorithms: An Introduction to Computational Algebraic Geometry and Commutative Algebra. Springer, New York (2007).
Eichenauer J., Lehn J.: A non-linear congruential pseudo random number generator. Stat. Hefte 27(1), 315–326 (1986). https://doi.org/10.1007/BF02932576.
Eichenauer-Herrmann J., Herrmann E., Wegenkittl S.: A survey of quadratic and inversive congruential pseudorandom numbers, pp. 66–97. Springer, New York (1998). https://doi.org/10.1007/978-1-4612-1690-2_4.
Howgrave-Graham N.: Finding small roots of univariate modular equations revisited. In: Crytography and Coding, pp. 131–142. Springer, New York (1997).
Howgrave-Graham N.A., Smart N.P.: Lattice attacks on digital signature schemes. Des. Codes Crypt. 23(3), 283–290 (2001). https://doi.org/10.1023/A:1011214926272.
Lenstra A.K., Lenstra H.W., Lovász L.: Factoring polynomials with rational coefficients. Math. Ann. 261(4), 515–534 (1982).
Ling S., Shparlinski I.E., Steinfeld R., Wang H.: On the modular inversion hidden number problem. J. Symb. Comput. 47(4), 358–367 (2012).
Niederreiter H.: Random Number Generation and Quasi-Monte Carlo Methods. Society for Industrial and Applied Mathematics, Philadelphia, RI (1992). https://doi.org/10.1137/1.9781611970081.
Niederreiter H.: New developments in uniform pseudorandom number and vector generation. In: Niederreiter H., Shiue P.S. (eds.) Monte Carlo and Quasi-Monte Carlo Methods in Scientific Computing. Lecture Notes in Statistics, vol. 106, pp. 87–120. Springer, New York (1995). https://doi.org/10.1007/978-1-4612-2552-2_5.
Niederreiter H., Rivat J.: On the correlation of pseudorandom numbers generated by inversive methods. Monatshefte Math. 153(3), 251–264 (2008). https://doi.org/10.1007/s00605-007-0503-3.
Niederreiter H., Shparlinski I.: Recent advances in the theory of nonlinear pseudorandom number generators. In: Fang K.T., Niederreiter H., Hickernell F. (eds.) Monte Carlo and Quasi-Monte Carlo Methods, pp. 86–102. Springer, Berlin (2000). https://doi.org/10.1007/978-3-642-56046-0_6.
Niederreiter H., Winterhof A.: On the Structure of Inversive Pseudorandom Number Generators, pp. 208–216. Springer, Berlin (2007). https://doi.org/10.1007/978-3-540-77224-8_25.
Pirsic G., Winterhof A.: On the structure of digital explicit nonlinear and inversive pseudorandom number generators. J. Complex. 26(1), 43–50 (2010). https://doi.org/10.1016/j.jco.2009.07.001.
Shparlinski I.E.: Playing hide-and-seek with numbers: the hidden number problem, lattices, and exponential sums. In: Proceeding of Symposia in Applied Mathematics, vol. 62, pp. 153–177 (2005).
Stern J.: Secret linear congruential generators are not cryptographically secure. In: 28th Annual Symposium on Foundations of Computer Science, 1987, pp. 421–426 (1987). https://doi.org/10.1109/SFCS.1987.51.
Topuzoğlu A., Winterhof A.: On the linear complexity profile of nonlinear congruential pseudorandom number generators of higher orders. Appl. Algebr. Eng. Commun. Comput. 16(4), 219–228 (2005). https://doi.org/10.1007/s00200-005-0181-0.
Winterhof A.: Recent Results on Recursive Nonlinear Pseudorandom Number Generators, pp. 113–124. Springer, Berlin (2010). https://doi.org/10.1007/978-3-642-15874-2_9.
Xu J., Hu L., Huang Z., Peng L.: Modular inversion hidden number problem revisited. In: Information Security Practice and Experience, pp. 537–551. Springer, New York (2014).