論文の概要: KyberMat: Efficient Accelerator for Matrix-Vector Polynomial Multiplication in CRYSTALS-Kyber Scheme via NTT and Polyphase Decomposition
- arxiv url: http://arxiv.org/abs/2310.04618v1
- Date: Fri, 6 Oct 2023 22:57:25 GMT
- ステータス: 処理完了
- システム内更新日: 2024-03-19 03:02:24.787027
- Title: KyberMat: Efficient Accelerator for Matrix-Vector Polynomial Multiplication in CRYSTALS-Kyber Scheme via NTT and Polyphase Decomposition
- Title（参考訳）: KyberMat:NTTおよびポリフェーズ分解によるCRYSTALS-Kyberスキームの行列ベクトル多項式乗算の効率的な加速器
- Authors: Weihang Tan, Yingjie Lao, Keshab K. Parhi,
- Abstract要約: CRYSTAL-Kyber (Kyber) は、標準化プロセス中に選択された暗号鍵カプセル化機構 (KEM) の1つである。
本稿では,Kyberアーキテクチャのレイテンシとスループットの制約に対する最適化について述べる。
- 参考スコア（独自算出の注目度）: 20.592217626952507
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: CRYSTAL-Kyber (Kyber) is one of the post-quantum cryptography (PQC) key-encapsulation mechanism (KEM) schemes selected during the standardization process. This paper addresses optimization for Kyber architecture with respect to latency and throughput constraints. Specifically, matrix-vector multiplication and number theoretic transform (NTT)-based polynomial multiplication are critical operations and bottlenecks that require optimization. To address this challenge, we propose an algorithm and hardware co-design approach to systematically optimize matrix-vector multiplication and NTT-based polynomial multiplication by employing a novel sub-structure sharing technique in order to reduce computational complexity, i.e., the number of modular multiplications and modular additions/subtractions consumed. The sub-structure sharing approach is inspired by prior fast parallel approaches based on polyphase decomposition. The proposed efficient feed-forward architecture achieves high speed, low latency, and full utilization of all hardware components, which can significantly enhance the overall efficiency of the Kyber scheme. The FPGA implementation results show that our proposed design, using the fast two-parallel structure, leads to an approximate reduction of 90% in execution time, along with a 66 times improvement in throughput performance.
- Abstract（参考訳）: CRYSTAL-Kyber (Kyber) は、標準化プロセス中に選択された暗号鍵カプセル化機構 (KEM) の1つである。
本稿では,Kyberアーキテクチャのレイテンシとスループットの制約に対する最適化について述べる。
具体的には、行列ベクトル乗法と数理論変換(NTT)に基づく多項式乗法は、最適化を必要とする重要な演算とボトルネックである。
この課題に対処するために,計算複雑性を低減するために,新しいサブ構造共有技術を用いて,行列ベクトル乗法とNTTベースの多項式乗法を体系的に最適化するアルゴリズムとハードウェア共同設計手法を提案する。
サブ構造共有アプローチは、多相分解に基づく事前の高速並列アプローチに着想を得たものである。
提案した効率的なフィードフォワードアーキテクチャは,全ハードウェアコンポーネントの高速,低レイテンシ,フル活用を実現し,キーバー方式の全体的な効率を大幅に向上させることができる。
FPGA実装の結果から,高速な2並列構造を用いた設計により,実行時間の約90%が削減され,スループット性能も66倍に向上した。
関連論文リスト
- HF-NTT: Hazard-Free Dataflow Accelerator for Number Theoretic Transform [2.4578723416255754]
多項式乗法は、完全同型暗号(FHE)など、多くのアプリケーションにおける基本的な演算の1つである。
Numberoretic Transform (NTT) は、適応可能な乗算を向上するための有効なツールであるが、NTT加速器を高速に生成する方法が欠如している。
本稿では,新しいNTTアクセラレータであるHF-NTTを導入し,ビット反転操作を不要とするデータ移動戦略を提案する。
論文 参考訳（メタデータ） (2024-10-07T07:31:38Z) - Fast, Scalable, Energy-Efficient Non-element-wise Matrix Multiplication on FPGA [10.630802853096462]
現代のニューラルネットワーク(NN)アーキテクチャは、膨大な数の乗算演算に依存している。
本稿ではFPGA上の高スループット,スケーラブル,エネルギー効率の非要素的行列乗算ユニットを提案する。
AMUを使用すると、FPGAベースの量子ニューラルネットワーク(QNN)アクセラレーターの最先端ソリューションよりも最大9倍高いスループットと112倍高いエネルギー効率が得られる。
論文 参考訳（メタデータ） (2024-07-02T15:28:10Z) - An Efficient Algorithm for Clustered Multi-Task Compressive Sensing [60.70532293880842]
クラスタ化マルチタスク圧縮センシングは、複数の圧縮センシングタスクを解決する階層モデルである。
このモデルに対する既存の推論アルゴリズムは計算コストが高く、高次元ではうまくスケールしない。
本稿では,これらの共分散行列を明示的に計算する必要をなくし,モデル推論を大幅に高速化するアルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-09-30T15:57:14Z) - Accelerating Cutting-Plane Algorithms via Reinforcement Learning
Surrogates [49.84541884653309]
凸離散最適化問題に対する現在の標準的なアプローチは、カットプレーンアルゴリズムを使うことである。
多くの汎用カット生成アルゴリズムが存在するにもかかわらず、大規模な離散最適化問題は、難易度に悩まされ続けている。
そこで本研究では,強化学習による切削平面アルゴリズムの高速化手法を提案する。
論文 参考訳（メタデータ） (2023-07-17T20:11:56Z) - A doubly stochastic matrices-based approach to optimal qubit routing [0.0]
スワップマッピングは、SWAPゲートによって論理量子回路を等価な物理実装可能なものにマッピングする量子コンパイラ最適化である。
本研究では、置換行列の組み合わせとして定義される二重凸行列と呼ばれる構造を用いる。
提案アルゴリズムは,追加時間のコストで,アートアルゴリズムSABREの状態と比較して,大幅な深度低減を実現することができることを示す。
論文 参考訳（メタデータ） (2022-11-14T09:25:35Z) - Decomposition of Matrix Product States into Shallow Quantum Circuits [62.5210028594015]
テンソルネットワーク(TN)アルゴリズムは、パラメタライズド量子回路(PQC)にマッピングできる
本稿では,現実的な量子回路を用いてTN状態を近似する新しいプロトコルを提案する。
その結果、量子回路の逐次的な成長と最適化を含む1つの特定のプロトコルが、他の全ての手法より優れていることが明らかとなった。
論文 参考訳（メタデータ） (2022-09-01T17:08:41Z) - Matrix Reordering for Noisy Disordered Matrices: Optimality and
Computationally Efficient Algorithms [9.245687221460654]
単細胞生物学とメダゲノミクスの応用により,ノイズモノトンToeplitz行列モデルに基づく行列化の問題を考察した。
我々は、決定理論の枠組みでこの問題の基本的な統計的限界を確立し、制約付き最小二乗率を示す。
そこで本研究では,性能向上を保証した新しい時間適応ソートアルゴリズムを提案する。
論文 参考訳（メタデータ） (2022-01-17T14:53:52Z) - Adaptive pruning-based optimization of parameterized quantum circuits [62.997667081978825]
Variisyハイブリッド量子古典アルゴリズムは、ノイズ中間量子デバイスの使用を最大化する強力なツールである。
我々は、変分量子アルゴリズムで使用されるそのようなアンサーゼを「効率的な回路訓練」(PECT)と呼ぶ戦略を提案する。
すべてのアンサッツパラメータを一度に最適化する代わりに、PECTは一連の変分アルゴリズムを起動する。
論文 参考訳（メタデータ） (2020-10-01T18:14:11Z) - Multi-View Spectral Clustering with High-Order Optimal Neighborhood
Laplacian Matrix [57.11971786407279]
マルチビュースペクトルクラスタリングは、データ間の固有のクラスタ構造を効果的に明らかにすることができる。
本稿では,高次最適近傍ラプラシア行列を学習するマルチビュースペクトルクラスタリングアルゴリズムを提案する。
提案アルゴリズムは, 1次ベースと高次ベースの両方の線形結合の近傍を探索し, 最適ラプラシア行列を生成する。
論文 参考訳（メタデータ） (2020-08-31T12:28:40Z) - Iterative Algorithm Induced Deep-Unfolding Neural Networks: Precoding
Design for Multiuser MIMO Systems [59.804810122136345]
本稿では,AIIDNN(ディープ・アンフォールディング・ニューラルネット)を一般化した,ディープ・アンフォールディングのためのフレームワークを提案する。
古典的重み付き最小二乗誤差(WMMSE)反復アルゴリズムの構造に基づく効率的なIAIDNNを提案する。
提案したIAIDNNは,計算複雑性を低減した反復WMMSEアルゴリズムの性能を効率よく向上することを示す。
論文 参考訳（メタデータ） (2020-06-15T02:57:57Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。