「素因数分解を劇的に高速化するアルゴリズムの開発」の主張
-
wholescape
- 144
- 0
- 0
- 0
-
- いいね！0
RSA暗号をはじめとする現代の暗号は、大きな素数2つを掛け合わせた合成数を素因数分解することは(ノイマン型コンピュータでは)非常に困難であり、という基礎概念に寄って立っている。
総当たりに試すのでは暗号が保護する情報が意味を持つ時間のうちに解が求められることは非常に困難である、ということでもある。
このため、もし大きな素数の合成数素因数分解を高速に行うことが実現できてしまうと、現在の暗号の応用、すなわちコンピュータやインターネットにおける情報セキュリティ(秘密情報の保護)が一気に崩れてしまう事が考えられる。
おことわり
当未査読論文の手法については再現性がないという検証が挙げられている。(2021年3月4日時点で失敗報告あり。再現成功の報告無し)
Tsukasa #01
@a4lg
Tsukasa OI (大居 司); アマチュア研究者 (情報セキュリティ、人文情報学、文献学) //// 共同研究者、所属先等の公式見解とは無関係。
Tsukasa #01
@a4lg
真偽はともかく、ちょっととんでもない論文が出てきたんだが。国際暗号学会の未査読論文だが、素因数分解を (RSA を破壊するレベルで) 劇的に高速化するアルゴリズムを開発したと主張している。 eprint.iacr.org/2021/232
2021-03-04 19:52:49
Tsukasa #01
@a4lg
このアルゴリズムの背景にある数学理論は完全に私の専門外だが、2^800 前後の数を因数分解するのに必要な算術演算数が事実だとすると、確かに RSA 破壊レベルだ ([G]NFS: 2.8126*10^23 → SVPベースの新アルゴリズム: 8.4*10^10)。
2021-03-04 19:55:25
Tsukasa #01
@a4lg
必要な算術演算の計算時間の細かなところを考えず、両アルゴリズムにおける 1 演算が同じ時間で完了するとした場合、2^800 前後の数で因数分解がおよそ 3 兆倍高速化ということに。実際には並列性の問題とかあるだろうし文字通り 3 兆倍速くなるわけではないだろうが、それでも半端ない。
2021-03-04 19:58:54
Tsukasa #01
@a4lg
というか、この論文の著者、シュノア (Schnorr) 署名で知られるシュノア氏じゃないか。明らかにぽっと出の数学者/暗号学者ではない。
2021-03-04 20:00:49
Tsukasa #01
@a4lg
「多分」再現実験できるレベルでアルゴリズムが書かれてるのでめっちゃ再現実験したいんだが、格子理論に全く詳しくないせいでしたくともできない……。歯痒い。
2021-03-04 20:21:11
Tsukasa #01
@a4lg
どうやら再現性に問題がある様子。 twitter.com/a4lg/status/13…
2021-03-04 22:42:39
Tsukasa #01 (5x vaccinated)
@a4lg
【重要】RSA 破壊を主張する未査読論文ですが、現状再現成功の報告なし (失敗報告あり github.com/lducas/Schnorr…)。また証明内の誤りを指摘する意見 (crypto.stackexchange.com/questions/8858…) もあり。どう少なく見積もっても、未査読論文を不適切なまでにセンセーショナルに扱ってしまいました。申し訳ありません。
2021-03-04 21:49:41
Tsukasa #01
@a4lg
真偽については全く検証できそうにないが、少なくともシュノア署名で知られるシュノア氏自身による (彼を騙る馬の骨ではない)、イタズラでも何でもない論文投稿であることは海外の暗号学者が複数ルートで確かめたようだ。
2021-03-04 20:41:35
Tsukasa #01
@a4lg
【2021-03-04 21:08 追記】論文に示された手法の再現に失敗したという報告もあります。さらなる続報に期待。 twitter.com/DucasLeo/statu…
2021-03-04 21:09:10
Léo Ducas MASTODON: @ducasleo@mathstodon.xyz
@DucasLeo
@chelseakomlo @asanso @_henrycase @FredericJacobs @CryptoBits_eu #SchnorrGate update: the new version of March 3rd is much easier to test, requiring SVP in dimension as low as 47 (down from 1800 !). Out of 1000 trials, no factoring relations was found. github.com/lducas/Schnorr…
2021-03-04 15:51:25
Léo Ducas @ducasleo@mathstodon.xyz
@DucasLeo
Mastodon exodus attempt: @ducasleo@mathstodon.xyz Dad of one. Cryptographer & Cryptanalyst. Tenured researcher at Centrum Wiskunde & Informatica.
Léo Ducas @ducasleo@mathstodon.xyz
@DucasLeo
@chelseakomlo @asanso @_henrycase @FredericJacobs @CryptoBits_eu #SchnorrGate update: the new version of March 3rd is much easier to test, requiring SVP in dimension as low as 47 (down from 1800 !). Out of 1000 trials, no factoring relations was found. github.com/lducas/Schnorr…
2021-03-04 15:51:25
Léo Ducas @ducasleo@mathstodon.xyz
@DucasLeo
This seems like the perfect set-up to advertise this open PHD position... If you enjoy lattices, number theory, algorithms, and for example, would like to explore this approach to factoring and figure out its true complexity, this may be for you ! universiteitleiden.nl/en/vacancies/2…
2021-03-04 16:47:17
Léo Ducas @ducasleo@mathstodon.xyz
@DucasLeo
Added some references on the git README. I am unable to find the manuscript of Adleman online. Would be very grateful if someone has an electronic version of it.
2021-03-04 17:22:28
Tsukasa #01
@a4lg
未査読論文の紹介としては軽率に過ぎたと反省するが、ツイ消しするとそれはそれで問題が起こりそうなので、ひとまず関連情報や続報などを元ツイートにぶら下げることにする。
2021-03-04 21:27:04
Tsukasa #01
@a4lg
【重要】RSA 破壊を主張する未査読論文ですが、現状再現成功の報告なし (失敗報告あり github.com/lducas/Schnorr…)。また証明内の誤りを指摘する意見 (crypto.stackexchange.com/questions/8858…) もあり。どう少なく見積もっても、未査読論文を不適切なまでにセンセーショナルに扱ってしまいました。申し訳ありません。
2021-03-04 21:49:41