Solving Generalized Small Inverse Problems
スポンサーリンク
概要
- 論文の詳細を見る
We introduce a “generalized small inverse problem (GSIP)” and present an algorithm for solving this problem. GSIP is formulated as finding small solutions of f(x0,x1,...,xn)=x0h(x1,...,xn)+C=0(mod M) for an n-variate polynomial h, non-zero integers C and M. Our algorithm is based on lattice-based Coppersmith technique. We provide a strategy for construction of a lattice basis for solving f=0, which is systematically transformed from a lattice basis for solving h=0. Then, we derive an upper bound such that the target problem can be solved in polynomial time in log M in an explicit form. Since GSIPs include some RSA-related problems, our algorithm is applicable to them. For example, the small key attacks by Boneh and Durfee are re-found automatically.
- 2011-06-01
著者
関連論文
- Extended Password Recovery Attacks against APOP, SIP, and Digest Authentication
- Extension of Secret Handshake Protocols with Multiple Groups in Monotone Condition
- Cryptanalysis of Two MD5-Based Authentication Protocols : APOP and NMAC
- Extended Password Recovery Attacks against APOP, SIP, and Digest Authentication
- New Message Differences for Collision Attacks on MD4 and MD5
- Improved Collision Attacks on MD4 and MD5(Hash Functions,Cryptography and Information Security)
- Deterministic Polynomial Time Equivalence between Factoring and Key-Recovery Attack on Takagi's RSA
- Improved Collision Search for Hash Functions : New Advanced Message Modification
- Small Secret CRT-Exponent Attacks on Takagi's RSA
- Near-Collision Attacks on MD4 : Applied to MD4-Based Protocols
- Exact Analyses of Computational Time for Factoring in Quantum Computers(Public Key Cryptography)(Cryptography and Information Security)
- Solving Generalized Small Inverse Problems