Experimental Analysis of Integer Factorization Methods Using Lattices
>100 Views
February 14, 26
スライド概要
Since 1991, Schnorr has proposed methods using lattices for solving the integer factorization problem whose hardness supports the security of the RSA cryptosystem. In 2022, Yan et al. proposed a modification of Schnorr's lattices and reported numerical experiments by an optimization method using quantum computation. After that, Yamaguchi et al. reported that they succeeded in factoring RSA-type composite numbers of at most 55 bits based on Yan et al.'s modification, using classical annealing calculation. In this paper, we report experimental results of integer factorization methods using lattices in classical computing. Specifically, we analyze the structure of Schnorr's lattices to select suitable parameters and apply existing lattice algorithms for finding smooth relations in the difference-of-squares method. We report the running time of integer factorization using lattices for RSA-type composite numbers of at most 90 bits and the success probability of finding a smooth relation from a lattice. We also discuss the time complexity of integer factorization methods using lattices based on experimental results.
立教大学大学院で，格子基底簡約アルゴリズムに関する研究をしています． 趣味でゲーム開発も行ってます． C++ | Go | Python | SageMath | Asir | Bash NTL | Eigen | DXライブラリ Visual Studio
関連スライド
ZAZA株式会社_会社紹介
ZAZA株式会社
388.1K
各ページのテキスト
Experimental Analysis of Integer Factorization Methods Using Lattices ◎ Arata Sato1 Aurélien Auzemery2 Akira Katayama1 Masaya Yasuda1 1 Rikkyo University 2 University of Limoges September 19th ◎ Sato, Auzemery, Katayama, Yasuda Experimental Analysis of Integer Factorization Methods Using Lattices September 19th 1 / 20
Background Year 1991 2021 2022 2023 Events Schnorr - Factorization methods using lattices [3, 4, 5, 6] • Found relations of difference-of-squares from approximate solutions of CVP on a lattice. • Prime factorization of a 47-bit composite number using a lattice of rank 90.[5] Ducas - Trial experiment [1, 2] • The larger the size of composites, the lower the probability of finding relations. • For RSA numbers, it would be less efficient than the number sieving method. Yan et al. - Quantum optimization method to find relations [8] • Claimed to find relations with O(m/ log m) qubits for m-bit composites. • Found relations for composite numbers up to 48-bits. Yamaguchi et al. - Classical annealing for modified lattices [7] • Reported prime factorizations of RSA-type composite numbers up to 55 bits. ✿✿✿✿✿✿✿✿✿✿✿✿✿✿✿✿✿✿✿✿✿✿✿✿✿✿✿✿✿✿✿✿✿✿✿✿✿✿ ◎ Sato, Auzemery, Katayama, Yasuda Experimental Analysis of Integer Factorization Methods Using Lattices September 19th 2 / 20
Purpose of This Work 1 Report experiment of integer factorization using lattices with classical computing We analyze mathematically appropriate parameters for integer factorization using lattices. ▶ We report sizes of composite numbers the methods can factorize in practice. ▶ 2 Experimental analysis of the complexity of the methods ▶ ▶ We analyze the behavior of run-time of the method. We explore if the methods are faster than other methods such as the number field sieve. ◎ Sato, Auzemery, Katayama, Yasuda Experimental Analysis of Integer Factorization Methods Using Lattices September 19th 3 / 20
Concepts on Difference-of-Squares Method pi : i-th prime number (i ≥ 1) Pℓ = {p0 = −1, p1 , . . . , pℓ }: Factor basis (ℓ ≥ 1) Definition 1 (pℓ -smooth) M ∈ Z is called pℓ -smooth, if none of the prime factors of M exceeds pℓ . Definition 2 (pℓ -smooth relation pair) (u, v) ∈ Z2 is called a pℓ -smooth relation pair (pℓ -sr-pair) def ⇐⇒ ∃ej , e′j ∈ Z≥0 s.t. u = gcd(u, N ) = 1 =⇒ Qℓ e′ −ej j j=0 pj Qℓ e j j=0 pj , u − vN = e′ Qℓ j j=0 pj . = (u − vN )u−1 ≡ 1 (mod N ) ⇝ For simplicity, assume the sr-pair (u, v) satisfies gcd(u, N ) = 1 ◎ Sato, Auzemery, Katayama, Yasuda Experimental Analysis of Integer Factorization Methods Using Lattices September 19th 4 / 20
Flow of the difference-of-squares method 1 Finding smooth relations Fix a factor base Pℓ and find ℓ + 2 different pℓ -sr-pairs (ui , vi ) ui = 2 ei,j j=0 pj , Qℓ u i − vi N = e′i,j j=0 pj . Qℓ Finding non-trivial factors P ′ Then, ∃ (t1 , t2 , . . . , tℓ+2 ) ̸= 0 s.t. ℓ+2 i=1 ti (ei,j − ei,j ) ≡ 0 (mod 2). If we set X := Qℓ m j j=0 pj ∈ Z mj := 12 then 2 X = e′i,j −ei,j p j j=0 Qℓ+2 Qℓ i=1 Pℓ+2 ′ i=1 ti (ei,j − ei,j ) ∈ Z t i ≡ 1 (mod N ). Therefore, gcd(X ± 1, N ) may be a prime factor of N . ◎ Sato, Auzemery, Katayama, Yasuda Experimental Analysis of Integer Factorization Methods Using Lattices September 19th 5 / 20
Schnorr’s Lattices and Finding Smooth Relations (1/2) Schnorr’s Lattices and Construction of the CVP N : the composite number to factorize p1 , . . . , pn : the first n primes ▶ c > 0: precision parameter ▶ ▶ Let L = L(Rn,c ) be the lattice spanned by √ log p1 √ 0 ··· 0 N c log p1 b1 0 log p2 · · · 0 N c log p2 .. Rn,c := .. = . , .. .. .. ... . . . . √ bn c log pn N log pn 0 0 ··· we consider the CVP on L with the target vector t := 0 · · · 0 N c log N ∈ Rn+1 . ◎ Sato, Auzemery, Katayama, Yasuda Experimental Analysis of Integer Factorization Methods Using Lattices September 19th 6 / 20
Schnorr’s Lattices and Composition of CVP (2/2) Properties of Schnorr’s Lattices L = L(Rn,c ) Theorem 3 (Schnorr [6, Section 3]) ▶ b := ▶ u := i=1 ei bi ：A lattice vector on the lattice L(ei ∈ Z) Pn Q Q −ej ej ∈Z ej <0 pj ej >0 pj , v := ∥b − t∥2 ≥ ln (uv) + N 2c ln In particular, u 2 vN N 2c ≫ ln(uv) =⇒ ∥b − t∥2 ≳ N 2c ln u 2 . vN Finding Smooth Relations by Approx-CVP If b ≈ t, then |u − vN | is small ⇝ u − vN may be pℓ -smooth. ◎ Sato, Auzemery, Katayama, Yasuda Experimental Analysis of Integer Factorization Methods Using Lattices September 19th 7 / 20
Yan et al.’s Modification j m (1 ≤ i ≤ n, σ : {1, . . . , n} → {1, . . . , n} is a random permutation) f (i) := σ(i) 2 Let Ln,c := L(Bn,c ) be the lattice spanned by f (1) 0 ··· 0 ⌊10c log p1 ⌉ 0 f (2) · · · 0 ⌊10c log p2 ⌉ Bn,c = .. .. .. .. . . . . . . . c 0 0 · · · f (n) ⌊10 log pn ⌉ and we consider the CVP on Ln,c with the target vector t = 0 · · · 0 ⌊10c log N ⌉ ∈ Zn+1 . P If 102c ≫ ni=1 ei f (i) ∧ b ≈ t, then |u − vN | is small (theorem 3). ⇝ u − vN may be pℓ -smooth ◎ Sato, Auzemery, Katayama, Yasuda Experimental Analysis of Integer Factorization Methods Using Lattices September 19th 8 / 20
Our Analysis for Choosing Parameters (1/2) Lemma 4 c: weight parameter (i.e. Yan et al’s N c =⇒ 10c ) b: closest vector in L to the target t ∥b∥ ≥ ln(uv) + N 2c ln2 uv N c−1 pℓ ∥b − t∥2 = O(mk ) ∧ 1 ≤ v ≤ =⇒ |u − vN | = O(pℓ ) (likely) mk/2 c−1 ⇝ If Nmk/2pℓ ≫ 1, then |u − vN | should be pℓ -smooth. ◎ Sato, Auzemery, Katayama, Yasuda Experimental Analysis of Integer Factorization Methods Using Lattices September 19th 9 / 20
Our Analysis for Choosing Parameters (2/2) linear case (‖b − t‖ = (m)) quadratic case (‖b − t‖ = (e 1/m)) sublinear case (‖b − t‖ = (m 2)) sub-sublinear case(‖b − t‖ = (m ln m)) 300 Proposition 5 N : composite number to factorize m: bit size of N 2 200 150 100 50 b: closest vector in L to a target t 1 rank of lattices 250 n + 1 ≈ 2c ln N = O(m) =⇒ ∥b − t∥2 = O(m). 2c ln N 2 n + 1 ≈ ln(ln N ) = O(m/ ln m) =⇒ ∥b − t∥ = O(m2 ). 0 50 55 60 65 70 75 80 bit length of integers to be factorized 90 plots of linear, quadratic, sublinear, and sub-sublinear curves. ⇝ From this, we estimate parameters for n = O(m) and for n = O(m/ ln m). ◎ Sato, Auzemery, Katayama, Yasuda 85 Experimental Analysis of Integer Factorization Methods Using Lattices September 19th 10 / 20
Our Selection of Suitable Parameters Linear case: n = O(m) √ Take c, ℓ s.t. 10c−1 pℓ ≫ m. ▶ Set c = 5.0, ℓ = 2n to have enough margin. ▶ Choose n = ⌊0.55m⌋ from preliminary experiments with m = 40, 45, 50. ▶ Sublinear case: n = O(m/ ln m) Take c, ℓ s.t. 10c−1 pℓ ≫ m. ▶ Set c = 5.0, ℓ = 2n following Yan et al [8]. (In [8], c ∈ [1.5, 10].) ▶ Choose n = ⌊2.3m/ ln m⌋ from preliminary experiments with m = 45, 50, 55. ▶ ◎ Sato, Auzemery, Katayama, Yasuda Experimental Analysis of Integer Factorization Methods Using Lattices September 19th 11 / 20
Applied Lattice Algorithms and their Implementation We search pℓ -sr-pairs with approx-CVP on Yan et al.’s lattices Ln,c = L(Bn,c ) We solve approx-CVP with Kannan’s Embedding Method： Bn,c 0⊤ . Let L̄n,c := L B̄n,c be a lattice spanned by B̄n,c := t 1 ▶ Lattice vectors u ∈ Ln,c close to t are embedded as shortest vectors on lattices L̄n,c in the form (t, 1) − (u, 0) = (t − u, 1) ∈ L̄n,c . We LLL-reduce the basis with the NTL library. We compute an approx-CVP solution v for (Ln,c , t) with Babai’s algorithm. We set the enumeration radius R = ∥t − v∥. With C++ code, we enumerate lattice vectors b ∈ L̄n,c \ {0} such that ∥b∥ ≤ R. ◎ Sato, Auzemery, Katayama, Yasuda Experimental Analysis of Integer Factorization Methods Using Lattices September 19th 12 / 20
Results (1/3): Run-time and Probability to Search Smooth Relations Every Lattice Ways to experiment We factorized RSA-type numbers N using lattices We searched pℓ -sr-pairs from approx-CVP on Yan et al.’s lattices Ln,c = L(Bn,c ). ▶ We set c = 5.0, ℓ = 2n2 or ℓ = n and chose the best n experimentally. ▶ ▶ Experimental Results Hardware used: 1 core of Intel Xeon Gold 5222 CPU @ 3.80 GHz, 32 GBytes of RAM. Sublinear order for the choice of n =⇒ factorization of 90-bit numbers in ≈ 3.5 days ▶ Size of N increases =⇒ probability of finding p -smooth relations (from a lattice) ℓ rapidly decreases. ▶ ▶ ◎ Sato, Auzemery, Katayama, Yasuda Experimental Analysis of Integer Factorization Methods Using Lattices September 19th 13 / 20
Results (2/3): Run-time and Probability Bit-size m of N (m = ⌈log N ⌉) 50 70 90 Linear case n = ⌊0.55m⌋, c = 5.0, ℓ = 2n n Probability Total Time 27 0.35% 25.2 minutes 38 < 0.001% > 3 days – – – Sublinear case n = ⌊2.3m/ ln m⌋, c = 5.0, ℓ = 2n2 n Probability Total Time 20 17.3% 32.2 seconds 26 2.2% 57.5 minutes 31 0.17% 83.3 hours For sublinear case, we succeeded in factorizing a 90-bit composite number in ≈ 3.5 days, but for linear case on 70-bit numbers, it takes much more than 3 days with a very low success probability to search smooth relations every lattice. For sublinear case, success probability seems to decrease exponentially, and for linear case it might be the same. ⇝ the probability can be approximated by an exponential function. ◎ Sato, Auzemery, Katayama, Yasuda Experimental Analysis of Integer Factorization Methods Using Lattices September 19th 14 / 20
Results (3/3): Probability of Finding Smooth Relations TVDDFTTQSPCBCJMJUZ $BTFPG m ( /ln m) p = 40.5286977 × 0.8977569455m TVDDFTTQSPCBCJMJUZ $BTFPG(m) p = 4078.2008 × 0.756867758m pʢTVDDFTTQSPCBCJMJUZʣ mʢCJUTJ[Fʣ The probability of finding smooth relations exponentially decreases with m. ⇝ Computational complexity of factorization using lattices seems to be in exponential time regarding m (only depending on lattices). ◎ Sato, Auzemery, Katayama, Yasuda Experimental Analysis of Integer Factorization Methods Using Lattices September 19th 15 / 20
Summary 1 Reported experiment of integer factorization using lattices with classical computing Find smooth relations from solutions of approx-CVP on Yan et al.’s lattices. Use Kannan’s embedding method to solve approx-CVP efficiently. ▶ Select the lattice rank as either sublinear or linear cases. ▶ The methods can factorize 90-bit composites in about 3.5 days with sublinear case (n = 31), but only up to 70-bit numbers with linear case. (Cf., Implementations up to only 55 bits had been reported. [7]) ▶ ▶ 2 Experimentally analyzed the complexity of the methods ▶ The probability of finding relations decreases exponentially to the bit-size. ⇝ The complexity of factorization using lattices behaves exponentially. （Independently of the computer’s architecture.） ⇝ not faster than the number field sieve methods. （Their computational complexity is in sub-exponential time.） ◎ Sato, Auzemery, Katayama, Yasuda Experimental Analysis of Integer Factorization Methods Using Lattices September 19th 16 / 20
Reference I [1] Léo Ducas. Testing Schnorr’s factoring claim in SageMath. https://github.com/lducas/SchnorrGate. [2] Léo Ducas. Schnorr’s approach to factoring via lattices. RISC seminar, 2021. https://projects.cwi.nl/crypto/risc_materials/2021_05_20_ducas_ slides.pdf. [3] Claus Peter Schnorr. Factoring integers and computing discrete logarithms via Diophantine approximation. In Advances in Computational Complexity Theory, pages 171–181, 1991. ◎ Sato, Auzemery, Katayama, Yasuda Experimental Analysis of Integer Factorization Methods Using Lattices September 19th 17 / 20
Reference II [4] Claus Peter Schnorr. Average time fast SVP and CVP algorithms: Factoring integers in polynomial time. Rump session at EUROCRYPT 2009, 2009. https://eurocrypt2009rump.cr.yp.to/ e074d37e10ad1ad227200ea7ba36cf73.pdf. [5] Claus Peter Schnorr. Factoring integers by CVP algorithms. Number Theory and Cryptography: Papers in Honor of Johannes Buchmann on the Occasion of His 60th Birthday, pages 73–93, 2013. ◎ Sato, Auzemery, Katayama, Yasuda Experimental Analysis of Integer Factorization Methods Using Lattices September 19th 18 / 20
Reference III [6] Claus Peter Schnorr. Fast factoring integers by SVP algorithms, corrected. Cryptology ePrint Archive, Paper 2021/933, 2021. https://eprint.iacr.org/2021/933. [7] Junpei Yamaguchi, Tetsuya Izu, and Noboru Kunihiro. Experimental report on integer factorization methods using lattice and optimization methods (in Japanese), 2023. IPSJ Technical Report, Vol.2023-IOT-61, No.22, 1–8. ◎ Sato, Auzemery, Katayama, Yasuda Experimental Analysis of Integer Factorization Methods Using Lattices September 19th 19 / 20
Reference IV [8] Bao Yan, Ziqi Tan, Shijie Wei, Haocong Jiang, Weilong Wang, Hong Wang, Lan Luo, Qianheng Duan, Yiting Liu, Wenhao Shi, et al. Factoring integers with sublinear resources on a superconducting quantum processor. arXiv preprint arXiv:2212.12372, 2022. ◎ Sato, Auzemery, Katayama, Yasuda Experimental Analysis of Integer Factorization Methods Using Lattices September 19th 20 / 20