KDDI、世界で初めて1409次元の暗号を解読 18
ストーリー by nagazou
桁が違う 部門より
桁が違う 部門より
KDDI総合研究所は26日、暗号解読コンテスト「Challenges for code-based problems」で、Classic McElieceと呼ばれる次世代暗号の1409次元の暗号を解読し、これまでの世界記録を更新したそうだ。この1409次元の暗号は10の56乗（=100兆×100兆×100兆×100兆）通りの解の候補が存在する。このため、総当たりでは解読に1兆年以上かかるとされてきたが、KDDIは独自の解読アルゴリズムを用いて、2700万の解読処理を同時に実行できる並列コンピューティング環境を構築・活用することにより、29.6時間で解読に成功したとしている（KDDI、ASCII.jp）。
これにより、1409次元の暗号を解読するために必要な計算量が2の63乗であることを実証し、この次元を上回れば暗号の解読が困難という目安である暗号の強度を突き止めたとしている。この成果は、将来の量子コンピューターの台頭に備えた暗号の開発や標準化に向けた貴重な情報になるとしている。
DJB御大の掌の上 (スコア:3, 参考になる)
１つ前の世界記録見たらDJB先生だった
15年前から解読アルゴリズムはぜんぜん進歩してない。その証拠に、この記録は2008年のソフトウェアを実行しただけ。
記録更新とかいっても、単にハードウェアが進化しただけじゃないか。同じハードウェアなら、2022年のソフトウェアより2008年の自作ソフトウェアのほうが速い。
的なことが書いてある
https://isd.mceliece.org/1347.html [mceliece.org]
KDDIには、DJB先生のコメントを踏まえた上での、解読の意義についても解説が欲しいところ
Re: (スコア:0)
実証することは意義があります
必要なコンピュータリソース量と解読時間は貴重な情報ですよ
Re: (スコア:0)
最後の方に格子暗号はまだダメダメとか書かれててびっくり
標準化進んでると聞いていたのに
Re: (スコア:0)
記録のページと成定氏のスライド
https://decodingchallenge.org/goppa/record/27 [decodingchallenge.org]
https://joint.imi.kyushu-u.ac.jp/wp-content/uploads/2022/08/220803_03n... [kyushu-u.ac.jp]
を見るに、MMTの並列化アルゴリズムの話だと思うから、アルゴリズムはアルゴリズムでも別のレベルの話で噛み合わないんじゃないかな。
話が2つあるわけか (スコア:1)
①1409次元のClassic McElieceの解の候補は10^56あるが、10^20に絞り込むことが可能だと示した
②並列コンピューティング環境（とはいえPC10台らしいが）で30時間で解読できたというデモンストレーションを行い、実際に必要な計算量を示した
標準候補として提案されているのは3488次元以上らしい。鍵のサイズがクソでかくなるな。
Re: (スコア:0)
公開鍵3.5MとかになるとTLSには向かないな
Re: (スコア:0)
3.5Kでは
Re: (スコア:0)
wikipedia を参考にしつつ
n=3488, k=0.8n=~2791 とすると
k * (n - k) = 1945327 bit
だいたい 243k って事になるのかな。詳しくは判らんが
Re: (スコア:0)
古典コンピューターだけを考えるとちょっと鍵が大きすぎるな
Re: (スコア:0)
それを考慮すると、計算量とは一対一が理想なのかな。
よし次は (スコア:0)
世界で初めての1408次元での解読を目指そう。
2022-blake3-chacha20-poly1305 (スコア:0)
これをクラックできるならNSAから雇用通知来るな
https://github.com/Shadowsocks-NET/shadowsocks-specs/blob/main/2022-1-... [github.com]
数学的暗号はダメ (スコア:0)
一瞬で解く方法があるかもしれないから、
だから量子暗号みたいな物理的な方法を使わないといけないとか暗号の専門家が言ってた気がする
（ただし本物の量子コンピューターがあれば量子の状態も計算して求めることが可能だと思うが）
よく混同される量子暗号と耐量子暗号 (スコア:3, 参考になる)
「耐量子」暗号（このスレの主題）：古典コンピュータでも量子コンピュータでも計算が困難そうな暗号。応用数学。
「量子暗号」（このスレと無関係）：量子力学に基づいた秘密鍵が盗聴不能な暗号。物理学。
Re:よく混同される量子暗号と耐量子暗号 (スコア:1)
量子暗号は暗号って言うか鍵共有よな。
Re: (スコア:0)
よな！よな！
Re: (スコア:0)
数学者が証明されていないという理由でP≠BQPを信じていないのに経験則に過ぎない物理法則を信じるというのはちょっと理解しかねるな
どういう事？ (スコア:0)
この宇宙は51次元じゃなかったっけ？