暗号半導体チップにおける『ナオキの法則』

背景

半導体業界ではムーアの法則が有名ですが、ムーアの法則は集積回路上のトランジスタ数は「2年ごとに倍になる」という指標のような経験則です。似たような法則として平山 直紀(Naoki Hirayama)が2018年に発明したSnakeCubeから、後世の人に役立つ指標になるナオキの法則(Naoki's law)を提案します。発明直後に、この法則が言えることを確信していたのですがSnakeCubeの実装に奔走していたため、後回しにしてきました。この法則が学会、産業界で、大いに活用してもらえるように、ここで発表します。

概略

SnakeCubeはRSAなどの公開鍵暗号の演算で良く使われるモンゴメリ乗算器とプロセッサの構成法のことです。デバイスに依存しない数学のアルゴリズムに近いものです。ざっくり言うと演算器、単体で３倍以上、性能を４倍にできる中国人剰余定理も併用可能なため、従来研究の３×４＝１２倍の高速化を達成しました。演算器単体でも１０倍あるかもしれないデータもあるため革命的な発明ではないかと思われます。モンゴメリ乗算を使わないアルゴリズムにはSnakeCubeよりも高速なサバンジュ大学の論文があります。ただ量子コンピュータによる解読問題を緩和するためには、鍵長を長くする必要があるのですが、その方法は鍵長を大きくすることが実装上非常に困難であるため、僕はSnakeCubeが世界最高の暗号プロセッサであると考えています。移植の容易性や、鍵長を長くするのが、とても容易なこと。鍵長を長くしても効率が落ちない。マルチチップに実装することが容易であること、IPにしやすいなど、SnakeCubeは良い点が多いのです。

トルコにあるサバンジュ大学の論文

次の論文は「鍵長２倍で計算時間２倍」を理論的に説明した論文。米アマゾンとイーサリアム財団ら、賞金10万ドルのFPGAデザインコンテストを優勝した論文です。

理論的に美しい論文ですが、鍵長が長くなるにしたがって、効率が下がり、実装が急激に(経済的にも)困難になっていくため、量子コンピュータの暗号解読が懸念される、現在では、論文の成果が薄れています。

暗号プロセッサSnakeCube

SnakeCubeは、平山 直紀(Naoki Hirayama)が2018年に発明した暗号プロセッサ。
次のURLにある説明を読むとわかるかも。

暗号プロセッサSnakeCube

巨大整数用四則演算プロセッサSnakeCubeが高速である秘密

[大きなモンゴメリ乗算器は実装できるのか？

ナオキの法則 (Naoki's law)

RSA暗号は鍵長が２倍になると計算量が８倍になるのです。
サバンジュ大学の論文は、わかりやすく説明すると、理論的にRSA暗号性能が「鍵長２倍で計算時間２倍」を説明した論文ですが、ナオキの法則は「鍵長２倍で計算時間４倍」です。
サバンジュ大学の論文のほうが勝っていますが、これは鍵長を２倍にした場合、トランジスタ数を４倍にして計算時間２倍を成り立たせています。ただし前述のように実際の製品にしていくには鍵長が大きくなるしたがって、劇的に困難になります。一方、ナオキの法則はSnakeCubeによって、だいたい保証されそうだということが、わかってきています。つまり、あるプロセスのデバイスでデータを取るとナオキの法則を使って、そのデバイスで鍵長を大きくした場合の精密な性能が予測できるのです。

SnakeCubeは世界最高の暗号プロセッサ

SnakeCubeよりもレイテンシ性能の高いプロセッサを開発することは可能だと思います。しかしデバイス毎に大きな設計コストが要求されると予想されるため、SnakeCubeが世界最高の暗号プロセッサであり続けると考えています。これは、これまで設計にお金をかけるよりデバイスにお金をかけて性能を向上することを優先する場合が多かったこと。概略で書いたとおりSnakeCubeの良い点が、多数あるため。

まとめ

今後、世界でSnakeCubeよりも高速な暗号プロセッサの開発を考えることはあると思います。ナオキの法則は、それを評価する上で便利な指標となるため、広く利用されるように考えます。量子コンピュータの進歩によりRSA暗号の安全性が危ぶまれている状況ですが、2048bitの鍵長を、いっきに大きくして、量子ビットを同時に多数安定化する技術が限界に達するところまで、もっていけば、RSAも、まだしばらくは安全だと楽観的に考えることもできるように思います。またSnakeCubeはRSA暗号専用のプロセッサではなくて、巨大な整数の四則演算器なので、今後、新しい公開暗号を高速化するためにも役に立ちます。

ナオキの法則は、人類史に残る法則となるかもしれない。