量子コンピュータは、公開鍵暗号（PKC）を破ることができるのか
現存する量子コンピュータは、あくまでもプロトタイプであり、汎用的な計算はもちろん、単純な算術計算も満足にできません。
では、将来的に量子コンピュータにより暗号署名がハックされるというのは空想の産物なのでしょうか？
一方で、量子コンピューターは話題にされているほどには進化していないかもしれませんが、現在BTCで使われているSHA-256をクラックできる可能性についてはどうでしょうか？
BTCコミュニティでは、もしこれが起こった場合を想定して、他のハッシュ関数にハードフォークするという対抗策をとるという議論がなされました。
「JiuZhang」量子コンピューターは、Bosonサンプリング問題のみを処理することができます。 Galton Board(Bean Machine)の量子版であると言えるでしょう。Bosonサンプリングでは、ボールが光子に、ペグがミラーやプリズムなどの光学デバイスに置き換えられます。
これは、汎用コンピュータ（チューリング完全）ではありません。 厳密にはコンピュータではなく機械であり、アルゴリズムの代替物ではなく物理学のゲームです。
Bosonサンプリングは、一般的なコンピューターでは解決が困難な問題を、専用マシンで簡単に解決するというアプローチです。 ECDSAやSHAは異なります。 量子コンピュータでSHA256をクラックするのは、火星に着陸するよりも難しく、コストもかかると私は確信しています。
結論：
無理（現時点の想定では）
では、Viteのセキュリティアルゴリズムはどうでしょうか？
非対称暗号化、ハッシュといったセキュリティアルゴリズムは、ブロックチェーンの基礎となるものです。多くのセキュリティアルゴリズムの実装の中で、Viteはどのように選択しているのでしょうか？
A. デジタル署名アルゴリズム — Ed25519
背景
デジタル・シグネチャ（デジタル署名）の目的は、ウェット・シグネチャ（紙の契約書に署名）における否認防止の解決策を実現することです。効果的なデジタル署名の主な特徴は、署名されたメッセージに基づいて署名者が明確に識別されるという部分です。署名メッセージは関連する秘密鍵の保有者によってのみ生成されるというメカニズムによりこれが達成されます。デジタル署名は、米国やドイツの署名法など、一部の国で既に法的な強制力を持っています。
公開鍵と秘密鍵は、秘密鍵による署名及び公開鍵の公開、メッセージの検証と署名の送信といった一連のプロセスにおいて重要な役割を果たします。公開鍵と秘密鍵は、特殊な一方向性関数と乱数を用いて生成されるのが一般的です。一方向性関数f(x)=yを解く複雑さは多項式を解く複雑さと同等ですが、逆関数f-1(y)=xを解くのは指数関数的な難しさになります。公開鍵から秘密鍵を計算するコストは、現代のあらゆるコンピューティングシステムの能力を超えるものであり、この署名モデルは今でも十分安全です。しかし、将来、量子コンピュータが実用化された場合には、RSAやDLP（離散対数問題）、ECC（DLPを発展させた楕円曲線暗号）など、現在の非対称暗号の仕組みは安全とは言えなくなります。これは言い換えれば、量子セキュリティの実現には、量子コンピュータの実現と同じ時間がかかるという事です。
ブロックチェーンシステムには、アカウントアドレスやトランザクションの生成がベースとなる署名アルゴリズムが不可欠です。署名アルゴリズムの選択には、そのアルゴリズムのセキュリティとパフォーマンス評価が必須となり、ここではセキュリティ面がより重要となります。サトシ・ナカモトは「ECDSA over secp256k1」を選択しました。secp256k1は、SECGが定義したコブリッツ曲線であり、ナカモト論文が発表されるまでは、誰も使っていなかったアルゴリズムです。ECDSA over secp256k1は透過的に設計されていますが、NISTが使用している「secp256r1」カーブ（より主流のP256アルゴリズム）は独自のパラメータを持っており、これはNSAが仕組んだバックドアであることが広く認識されています。その後の一連の事件により、ナカモトの選択ビジョンが明確に証明され、イーサリアムやEOSにも取り上げられました。
その後、Ed25519の特許がきれた事によりビットコインのコア開発者もVitalik ButerinもEd25519への移行を口にしていましたが、移行コストが高すぎて実現できませんでした。一方、リップルは2014年に何のためらいもなくこのような移行を行いました。
セキュリティへの配慮
Ed25519は、多くの独立系企業や著名なセキュリティの専門家によるテストとレビューを経て 安全性を証明され、一方のsecp256k1は 「安全ではない 」と判断されました。
性能への配慮
高スループットで低レイテンシー、優れたスケーラビリティといった産業用アプリケーション要件を満たすために、Viteはトランザクションを リクエストとレスポンスに分解することを意味する 「transaction decomposition」のコンセプトを導入するなどの最適化スキームを設計しました。検証や確認は非常に頻繁に行われる作業であるため、システム全体のパフォーマンスは、署名アルゴリズムと署名検証プロセスの両方の速度に特に敏感になります。Viteの高いTPS目標を考慮した場合、この速度の問題は特に重要となります。データによると、Ed25519の性能はsecp256k1を超えるECDSAよりも数倍速いとされています。この高速化により、Viteのシステムの性能も大きく向上すると考えられます。また、Ed25519の署名はECDSAの署名よりも若干短いことから、ネットワーク伝送やストレージシステムの負担を軽減することができます。
修正点
Ed25519でSHA2を使用する代わりに、ViteはBlake2bを使用しています。
欠点
キースペースが非線形であることからBIPのHierarchical Deterministic Key Derivationとの互換性を持ちません。
B. ハッシュ・アルゴリズム — Blake2b
背景
ハッシュアルゴリズムの目的は、任意の長いメッセージから短い固定サイズの要約を生成することであり、ハッシュ関数は一方通行なものです。しかし、ハッシュ関数と非対称暗号システムの一方向性関数との違いは、後者の関数は理論的には可能でありながら実際には不可能な逆解を求めることです。つまり、公開鍵には、秘密鍵を生成するために必要な情報が全て含まれています。しかし、ハッシュ関数は理論的に可逆ではなく、実質的に可逆であるといえます。ハッシュにはそれに対応する無限のソースメッセージがあり、その例を紹介します。
ハッシュ関数の出力がnビットであれば、全ての出力の量は2nになりますが、可能な入力量は無限にあります。pigeonhole principleによれば、入力された前置イメージがm * 2nビットで、ハッシュ関数の出力が均等に分布している場合、Hash(X)=targetを許すXが前置イメージである確率は1/m(均等でない場合はさらに確率が低くなる)となります。しかし、実際には、ストレージや計算機の能力に限りがあるため、原文はあまり長くなりません。一般的には、入力があまり長くなければmの範囲も広がりません。ですから、Hash(X) = TargetとなるXは、おそらく本当のソースメッセージとなるでしょう。
Viteシステムでは、ハッシュ関数はマイニング、データの改ざん防止、データ保護などの役割を担っています。ハッシュ関数は署名アルゴリズムと同様に基本的なものであり、私たちはハッシュアルゴリズムのセキュリティとパフォーマンスについて真剣に検討しています。
セキュリティに関する考察 Blake2はBlakeから進化したものです。Blakeは、SHA3規格でkeccakと競合して敗れましたが、その理由は、BlakeとSHA2が似ているのに対し、NISTはSHA2規格とは全く異なるハッシュアルゴリズムを目指していたからだということです。
既存のSHA-2アルゴリズムを補完するためのSHA-3への要望としてBlakeはSHA-2に類似しています。また、BlakeとKeccakは非常に大きなセキュリティマージンを持っており、Blake2とkeccakのセキュリティレベルは同程度であると考えられます。
性能に関する考察
膨大なデータによると、一般的なCPU（X86 ARMなど）では、Blake2は他のどのHashアルゴリズムと比較して優れています。また、Blake2の特徴として、ASICで設計されたBlake2アルゴリズムのピーク値はあまり高くないため、マイニングのピークスピードが比較的低いことが挙げられます。
C. Key Derivation Function — scrypt
背景
簡単に言うと、Key Derivation Functionはマスター・プライベート・キーからサブ・プライベート・キーを導き出すために使用されます。例えば、KDFアルゴリズムを使用して、短い文字列を必要な形式に拡張することができます。KDFはハッシュと似ていますが、テーブルルックアップ攻撃（レインボーテーブルなど）でハッキングされないようランダム変数を追加する点が異なります。今回使用したscryptはメモリ依存のKDFなので、計算のたびにかなりのメモリと時間を消費するため、ブルートフォースアタックはほぼ不可能となります。
Viteのシステムでは、KDFは非基本的なものであり、ユーザーが入力した短い可変長のキーワードをKDFで変換し、256ビットの鍵を受け取り後、その鍵をAES-256-GCMアルゴリズムを用いてEd25519の秘密鍵を暗号化し、個人のコンピュータに安全に保存します。
理由
技術的には、2015年パスワードハッシュ化コンペティションで優勝したscryptとargon2に大きな変化はありません。実用面ではscryptの方が先に誕生し、広く使われているためより成熟しています。今後2～3年の間にargon2に致命的な問題が発生しなければ、引き続き使用することを検討しています。
D. 用語
- ECDSA(Elliptic Curve Digital Signature Algorithm)：楕円曲線を用いたデジタル署名アルゴリズム
- secp256k1：ECDSAアルゴリズムのパラメータ
- sec：SECG（Standards for Efficient Cryptography Group）が導入したStandards for Efficient Cryptogrpahyの略称
- p：楕円曲線が素数場を使用していることを意味する
- 256 ：素数の長さが256ビットであることを意味する
- k：コブリッツ曲線の略称
- 1 ：最初の（唯一の）標準曲線タイプであることを意味する
- Ed25519：SHA512/256とCurve25519を用いたEdDSAの署名アルゴリズム
- NIST(National Institute of Standards and Technology)：SHA3やP256などのセキュリティ規格を策定
- NSA：National Security Agencyの略称
- AES-256-GCM：256ビットの鍵を持つガロア/カウンタモードの高度な暗号化規格
