@kenmaroです。
普段は主に秘密計算、準同型暗号などの記事について投稿しています。
秘密計算に関連するまとめの記事に関しては以下をご覧ください。
概要
最近のいくつかの記事で、OpenFHEを用いて、CKKS形式の
- ブートストラップと演算の組み合わせ
- 非線形演算チェビシェフ近似
- プロキシ再暗号化
- Threshold 暗号構成
- 線形回帰モデルの学習チュートリアル
などを行ってきました。
また、前回の記事
でOpenFHEがサポートしている、
Intel Homomorphic Encryption Acceleration Library (Intel HEXL)
を用いてビルドを行い、
ハードウェアによってどのくらいの高速化が実現可能なのか、という検証を行いました。
今回は、Intel HEXLが一体何者なのか、どうやって格子暗号に必要な演算を高速化しているのか、
ということについて理解を深めたいと考えています。
細かいところは論文に任せて、全体として何を高速化しているのか、
というところに言及します。
Intel HEXL は何に使われているのか
IntelHEXLは、Microsoft SEAL や、 Palisade (そしてそれを継承したOpenFHE)といった、
準同型暗号の中でも格子暗号を実装したライブラリのデファクトスタンダードとなっているもの、
に応用されています。
この背景として、IntelはNASDAQと共同で準同型暗号の研究開発をおこなっているということ、
また、Microsoftと、米国の軍に関連した研究期間DARPAのプログラムで協業しており、
格子暗号の実用化に向けてハードウェアによる高速化を研究開発していることが挙げられます。
AVX-512 命令セットとHEXL
AVX-512命令セットは、Intelが開発した命令セットであり、Advanced Vector Extensions 512の略です。
AVX-512 は、５１２ビットを使って、６４ビットのuint64 を８つ同時に足し算したり、掛け算したりすることができる命令セットです。
HEXLは、格子暗号のランタイムのボトルネックとなっている演算である、環状の多項式乗算のオペレーションを高速化するために、AVX-512命令セットを使用して組み上げられた、ソフトウェアライブラリであり、OSSとして公開されています。
2021年の４月にHEXLは誕生してから、Microsoftとの共同開発に際し、Microsoft SEALへHEXLを実装するために研究開発をしてきました。
また、DualityTechnologies とも共同開発を行い、彼らの開発する Palisade についてもHEXLを低レイヤで実装するために研究開発をおこなってきました。
HEXLが高速化する多項式乗算
格子暗号は多項式環と呼ばれる代数の上で構築されています。
どういうことかというと、普通の整数の演算が最小構成要素となっているのではなく、
基本的にはとても大きな数を係数に持つ、非常に巨大な多項式同士の足し算や、掛け算を最小構成要素として持ちます。
格子暗号を用いて暗号同士を掛け算したり、ブートストラップと呼ばれる非常に重い演算を実行する際、
この最小構成要素がたくさん実行されるので、この最小構成要素が高速に動作すればするほど、
暗号ライブラリの実行時間も改善されるということです。
この時、多項式と多項式の乗算は、普通に（ナイーブに）実行すると非常に遅い演算であるため、
いろいろな高速化手法が用いられます。
HEXLは、簡単にいうと、AVX-512という特殊な命令セットを駆使し、この巨大な多項式同士の乗算を、 NTT（数論変換手法）と呼ばれるアルゴリズムを使って高速化するライブラリです。
詳しいことは論文の内容に委ねようと思いますので、後述の参考文献をご覧ください。
キーワードとしては、NTT、FFT、RNS、CRT などが理解できていれば分かる内容となっています。
ベンチマーキング
実際に論文のベンチマークをみると、以下のような比較が結論づけられています。
Nという数字は、多項式の大きさ（つまり x のN乗まで含む多項式）を表しています。
シングルスレッドでの実測において、Intel HEXL を使用すると、NTLなどの従来最速であったライブラリよりもさらに２０％程度早い実装となっていることがわかります。
さらに、HEXLを低レイヤに採用し実装された Microsoft SEAL、及びPalisade は、従来のものに比べて、
ライブラリのAPIが数倍高速化しているという結果が出ています。
SEAL + HEXL による高速化
Palisade + HEXL による高速化
前回の記事で、私も Palisade の後継である、OpenFHEのHEXLによる高速化は実測を行いました。
是非ご覧いただければと思います。
まとめ
今回は、Intel HEXL が実現する、現在一般的に使用可能な、
格子暗号のハードウェア構成について記事を書いてみました。
実測を行ってみると、確かにベンチマーキングされた程度の高速化は確認できましたし、
並列化も大きく作用しているため、マシンパワーを大きくすることによりかなり秘密計算のサーバサイドのランタイムは向上できるという印象です。
また、これらIntelが取り組んでいるハードウェアによる格子暗号の演算の高速化ですが、
以前の記事でもいろいろ取り上げている通り、ASICやFPGAによる特化型ハードウェアも開発されてきています。
汎用的に使えるようになるには時間がかかると考えられますが、それらの特化型ハードウェアはこれらの汎用型のハードウェアとは違い、さらに桁違いの高速化が得られると考えられていますので、
彼らの研究開発のニュースについてもキャッチアップしていくと大変面白いと思います。
それらの高速化について理解する上でも、AVX-512をしようするIntel HEXLの理解は非常に重要となりますので、このレイヤを勉強することは非常におすすめです。
頑張ろう。
今回はこの辺で。
参考文献