💻 computer science

GPU Acceleration of Learning With Errors KEMs Using OpenACC for Post-Quantum Cryptography

本論文は、OpenACCを用いたLearning with Errors (LWE) ベースの鍵カプセル化メカニズムのGPU加速実装を提示し、従来のCPUおよびH100ベースのシステムと比較して、特にNVIDIA Grace Hopper Superchipにおいて、最大208倍の大幅な高速化とエネルギー効率の向上を実証している。

原著者： Tiziana Liberati, Nitin Shukla, Matteo Barbieri, Gabriella Bettonte, Elisabetta Boella, Simone Rizzo, Daniele Gregori, Marco Pedicini

公開日 2026-06-02

📖 1 分で読めます☕ さくっと読める

CC BY 4.0

原著者： Tiziana Liberati, Nitin Shukla, Matteo Barbieri, Gabriella Bettonte, Elisabetta Boella, Simone Rizzo, Daniele Gregori, Marco Pedicini

原論文は CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) でライセンスされています。 ✨ これは以下の論文のAI生成解説です。著者が執筆または承認したものではありません。技術的な正確性については原論文を参照してください。免責事項の全文を読む

あなたは、未来の超高性能ロボット（量子コンピュータ）でさえ解けないほど複雑な鍵を使って、宝箱に鍵をかけようとしているところだと想像してください。これが**耐量子計算機暗号（Post-Quantum Cryptography）**の目的です。この論文が焦点を当てている特定の「鍵」は、**LWE（Learning With Errors）**と呼ばれるものです。

LWEを、誰かが意図的に「静電気」や「ノイズ」を信号に加えた、巨大な数学パズルを解こうとしている状態だと考えてください。ノイズを作るのは簡単ですが、秘密鍵なしで元のメッセージをフィルタリングして見つけ出すのは、非常に困難です。問題は、標準的なコンピュータでこのパズルを解こうとすると、山を砂粒一つずつ動かしていくようなもので、永遠に時間がかかるということです。

研究者たちが、これを高速化するために行ったことを、分かりやすく説明します：

1. 問題点：CPUは遅いトラックである

著者たちは、標準的なコンピュータのプロセッサ（CPU）で動作するバージョンのこの暗号からスタートしました。彼らは、CPUが苦戦していることを見つけました。それは、まるで一台の配送トラックが数千もの箱を運ぼうとしているようなものでした。箱（データの一片）を倉庫（メモリ）からトラックの荷台に移すたびに、トラックは停止し、積み込み、そして走行しなければなりませんでした。トラックは、作業をしている時間よりも、待っている時間に多くの時間を費やしていました。

2. 解決策：GPUはドローンの艦隊である

これを修正するために、彼らは重い作業を**GPU（グラフィックス・プロセッシング・ユニット）**へと移しました。もしCPUが一台の配送トラックなら、GPUは数千機の小型で超高速なドローンの艦隊です。

比喩： 一度に一つの箱を運ぶ一台のトラックの代わりに、GPUは数千の箱を同時に運ぶことができます。
ツール： 彼らはOpenACCと呼ばれるプログラミング言語を使用しました。これは「ユニバーサル・リモコン」のようなものです。ドローンのための指示書全体を書き直す（それは難しく、間違いも起きやすい）代わりに、既存のトラックへの指示に対してリモコンを向け、「おい、君もこれをやってくれ、ただしもっと速く！」と指示したのです。これにより、ソフトウェアを壊すことなく簡単にアップグレードすることができました。

3. ボトルネック：「ノイズ」生成器

この暗号では、パズルを難しくするために大量のランダムな「ノイズ」が必要です。

従来の方法： CPUがノイズを生成し、それを書き留め、その後GPUへと運びました。これは、トラックの運転手が買い物リストを書き、店へ車を走らせ、品物を買い、そして戻ってくるようなものでした。多くの時間を無駄にしていました。
修正策： 彼らはGPUの倉庫の中に直接「ノイズ生成器」を設置しました。これにより、ドローンは現場で独自のランダムなノイズを生成できるようになりました。彼らはトラックがノイズを持ってくるのを待つ必要はありません。これにより、待ち時間が劇的に減少しました。

4. 「バッチ処理」のトリック

暗号化プロセスには、一度に256個の小さなパズルを解く工程が含まれます（メッセージの各ビットに対して一つ）。

従来の方法： GPUが一つのパズルを解き、停止し、指示を待ち、次のパズルを解き、停止し、また待つ……というものでした。これは、シェフが一度に一つの卵を調理し、卵を焼くたびにコンロが冷めるのを待っているようなものです。
修正策： 彼らは**イントラ・オペレーション・バッチ処理（Intra-Operation Batching）**と呼ばれる戦略を用いました。これは、シェフが256個の卵をすべて一度に大きなフライパンに入れ、まとめて調理するようなものです。GPUは、256個のパズルを同時に解くために、一度の大きな「ローンチ（起動）」を行います。これにより、膨大な時間が節約されます。

5. 結果：速度とエネルギー

研究者たちは、さまざまな種類の超高速コンピュータ（GPU）でこのテストを行い、従来のCPU方式と比較しました。

速度： 彼らがテストした中で最も新しく強力なコンピュータ（Grace Hopper Superchip）において、彼らの新しい手法は、従来のCPU方式よりも208倍高速でした。
- 比喩： もし古いトラックが荷物の配達に3時間かかるとしたら、新しいドローン艦隊は1分足らずで完了します。
- 彼らは、従来のCPUではメモリ不足でクラッシュしてしまうほど巨大なパズルのサイズさえも解くことができました。
エネルギー： 新しい手法は、より少ないエネルギーも使用しました。Grace Hopperコンピュータは、別の種類の高速GPUを備えた標準的なコンピュータと比較して、同じ作業を行うのに約半分のエネルギーしか使いませんでした。
- 比喩： これは、同じ配達を、ガソリンを大量に消費するトラックではなく、ハイブリッド車で行うようなものです。

6. なぜこれが重要なのか

この論文は、これらの「ドローン」（GPU）とスマートな管理術（OpenACC、バッチ処理、およびデバイス内でのノイズ生成）を使用することで、これらの量子耐性を持つ実用的なロックを現実的なものにできることを示しています。これらのスピードアップがなければ、数学的な計算があまりに遅すぎて、実用性に欠けてしまいます。これらがあれば、私たちは、たった一つの鍵がカチッと鳴るのを何日も待つことなく、将来の量子コンピュータに対してデータを保護することができます。

要約すると： 彼らは、遅くて重い作業を伴う暗号化手法を、数千の小さな作業員（GPU）が協力し、自ら物資を生成し、指示を待つこともなく働くことで、大幅に高速化しました。その結果、数百倍速く、かつ非常にエネルギー効率の高いシステムを実現したのです。

技術要約：OpenACCを用いたLearning With Errors KEMのGPU加速

問題提起
大規模な量子コンピュータの出現は、ショアのアルゴリズムを通じて、現在の非対称暗号プロトコル（例：RSA、ECC）を脅かしています。耐量子計算機暗号（PQC）は解決策として浮上しており、特に格子ベースのスキーム、中でもLearning With Errors（LWE）問題に依存する鍵カプセル化メカニズム（KEM）がその中心となっています。しかし、LWEベースのスキームは、大規模な行列演算や乱数生成による多大な計算オーバーヘッドを伴い、標準的なCPUアーキテクチャ上の高スループットなサーバサイドアプリケーションにおいては実用性を欠くことが多々あります。GPU加速の研究も行われていますが、既存の実装の多くはCUDA固有の最適化に依存しており、移植性や開発者の生産性を制限しています。さらに、単純な移植では、ホスト・デバイス間のメモリ転送レイテンシや乱数生成の直列化といったボトルネックに対処できないことがよくあります。

手法
著者らは、「プレーン」LWE（Ring-LWEのような追加の代数的構造を避けたもの）に基づく鍵カセル化メカニズム（KEM）を提案し、OpenACCディレクティブベースのプログラミングモデルを用いたGPU指向の実装を開発しました。本研究は、以下の手法的なステップに従って進行します。

ベースライン実装: LWE-KEMのC++実装を、マルチコアCPU向けにOpenMPを用いて並列化しました。このスキームは、KeyGen、Encaps、Decapsのフェーズを含む、IND-CCA2セキュリティを実現するためのFujisaki-Okamoto（FO）変換を利用しています。
OpenACCへの移植と最適化: CPUコードをOpenACCを用いてGPUへ移植しました。性能のボトルネックを克服するため、著者らは主に3つの戦略を実装しました。
- 演算内バッチ処理（Intra-Operation Batching）: 256個の独立したメッセージビットを逐次的に処理する（これにより個別のカーネル起動やメモリ転送が発生する）代わりに、これら256個の暗号化を単一のGPUカーネル起動に融合させました。これにより、微細な並列性（ $256 \times n$ のワークアイテム）を露出し、呼び出しオーバーヘッドを軽減しました。
- デバイス常駐型乱数生成（Device-Resident Random Number Generation）: ランダムなノイズベクトルをPCIe経由で転送することが深刻なボトルネックになることを認識し、著者らはRNGonGPUライブラリを統合しました。このライブラリは、AES-256決定論的乱数生成器（DRBG）をGPU上で直接実装しています。ホストからデバイスへは64ビットのシードのみが転送されるため、事前に生成されたノイズベクトルを転送する場合と比較して、データ転送量を約6桁削減できました。
- 明示的なデータ管理: CUDAのUnified Memoryを避け、enter dataおよびexit dataディレクティブを明示的に使用することで、ホスト・デバイス間の転送を決定論的に制御し、不要な通信を最小限に抑え、特定の同期ポイント（例：ハッシュ計算の前）でのみデータの整合性を確保しました。
カーネルの並列化: 主な計算コストである行列・ベクトル乗算を階層的に並列化しました。暗号化/復号においては、独立したメッセージ暗号化をOpenACCのギャング（gangs）に割り当て、一方で、暗ケットの構成要素をベクトルレーン間で並行に計算しました。

主な貢献

オープンソース実装: 著者らは、CPU（OpenMP）およびGPU（OpenACC）の両方に対して、プレーンLWEベースのKEMのオープンソース実装を提供し、再現可能なベンチマークを可能にしました。
ディレクティブベースの最適化: 幅広いクラスのLWEスキームに適用可能なGPU指向の最適化セットを提供し、深いCUDAの専門知識なしに高いパフォーマンスを達成できることを示しました。
包括的な評価: 複数のNVIDIA GPU世代（Volta, Ampere, Hopper）およびアーキテクチャ（x86 + Hopper vs. ARMベースのGrace Hopper Superchip）にわたる、性能、エネルギー効率、およびスケーラビリティの詳細な研究。

結果
評価は、NVIDIA GH200 Grace Hopper Superchip、A100、およびV100Sを含む様々なプラットフォームで実施されました。

スピードアップ: 最適化されたOpenACC実装は、マルチスレッドCPUベースラインに対して大幅なスピードアップを達成しました。GH200プラットフォームでは、大きな問題サイズ（ $n=4096$ ）において最大208倍のスピードアップに達しました。GPU実装は、 $n \ge 256$ においてCPUベースラインを上回り始めました。
スケーラビリティ: GPU実装は、問題サイズが増加するにつれてCPUバージョンよりも優れたスケーラビリティを示し、メモリ競合や同期オーバーヘッドのためにCPUでは処理が困難であったパラメータセット（例： $n=32768$ ）を効果的に処理しました。
エネルギー効率: GH200 Superchipにおいて、実装はx86 + H100システムと比較して、1.78倍のエネルギー・トゥ・ソリューション（解へのエネルギー消費）の削減を達成しました。これは主にARMベースのGrace CPUによる低消費電力に起因します。GH200対x86+HopperのTime-to-solutionの改善は、1.19倍とより緩やかなものでした。
アーキテクチャのスケーリング: 世代を超えた分析（V100S $\to$ A100 $\to$ GH200）により、性能のスケーリングは主に高帯域幅メモリ（HBM）の帯域幅によって駆動されていることが明らかになりました。しかし、帯域幅が増加するにつれ、オンデマンドの行列要素生成（演算コスト）および固定されたCPU側のFO変換コストの相対的なオーバーヘッドがスケーリングを制限し始め、ボトルネックが純粋なメモリ境界から、計算と同期の制約が混在した状態へと移行することが示されました。
最適化の影響: プロファイリングの結果、ナイーブな実装はホスト側の計算とPCIe転送によって支配されていました（GPUの飢餓状態）。最適化された実装は、ボトルネックを同期へと移行させ、GPUの活動時間はイテレーション時間の約98%に維持されました。

意義
本論文は、その結果が、計算負荷の高いLWEベースの暗号ワークロードに対するGPU加速の有効性を強調していると主張しています。OpenACCを活用することで、著者らは、低レベルのCUDAコーディングを必要とせずに、プログラマビリティとパフォーマンスのバランスが取れた高パフォーマンスなPQCへの道筋を示しました。本研究は、適切な最適化（特に、演算内バッチ処理とデバイス常駐型RNG）を行うことで、「プレーン」LWEスキーム（保守的なセキュリティ仮定を提供する一方で、高い計算コストを伴うもの）が、現代のヘテロジニアスなプラットフォーム上で実用的になり得ることを示唆しています。また、次世代のアーキテクチャにおいては、CPU側の操作とインターコネクトがスケーラビリティをますます制約することから、ヘテロジニアスなパイプライン全体を協調最適化することの重要性も強調しています。今後の課題として、このアプローチをマルチGPU環境や他のアクセラレータ・アーキテクチャ（AMD, Intel）へ拡張することが提案されています。