はじめに
前回のブログ「わかりやすいICF3-Fのモンゴメリ乗算器の説明」で途方もなく大きなモンゴメリ乗算器を実装できるということ書きました。ここではICF3-Fは複数チップを接続したものでも実装できるのか？という話をしてみたいと思います。そして、そこから何が言えるのか？を考えてみたいと思います。
巨大なモンゴメリ乗算器は実装できる
当たり前のような気もしますが、演算器の周波数を落とさず、演算器の大きさに比例した性能を出すことができる実装ができるという意味です。 RSA暗号をCPUで計算した場合、おおよそ鍵長が２倍になると計算時間は8倍になります。僕が書いた次の記事が参考になると思います。
RSA 8192bitの性能を測定するソースコード - Qiita
ICF3-Fは鍵を大きくしていっても鍵長２倍で計算時間４倍のまま、ほとんど効率は低下しません。
複数チップ上に実装しても効率は下がらないのか
現在の設計では、複数チップ間の遅延時間にもよりますが、演算器の周波数が全く下がらないような設計をしています。現時点(2019年11月6日)では設計までで検証はできていませんけれども。隣接するDSP間の通信が３サイクルあっても、周波数を下げずに動作することができます。もちろんチップ間の遅延時間が大きければ周波数は下がりますが、チップ間の遅延時間が1サイクルに入る限りは大丈夫です。DSPからチップのI/Oピン、チップ間、チップのI/OピンからDSPというぐあいに3サイクルで転送させます。
言えることは
電子投票などの準同型暗号システムや、SSLを使ったシステムを設計する上で、量子コンピュータの解読脅威のため、可能な限り大きな鍵の公開鍵暗号(RSA暗号など)を使いたい。システムに必要な要求性能は、わかっている。ICF3-Fの、あるFPGAの実装から「鍵長２倍で計算時間４倍」法則を使って、システムの鍵長を考えることができる。またICF3-Fは演算器の最下位ビットから最上位ビットまで、一筆書きのように、並べるだけの実装なので開発コストが小さく、見積もりが容易。 サバンチ大学の剰余乗算のFPGA実装は米アマゾンのFPGAコンテストの結果からも言えるように美しい理論はあるものの実際には実装してみないと性能が、わからないところがある。そして鍵長が大きくなるにしたがって効率が、どんどん下がっていく。ICF3-Fの「鍵長２倍で計算時間４倍」が理論のように見えてくるのかも。
