論文の概要: Fast Plaintext-Ciphertext Matrix Multiplication from Additively Homomorphic Encryption
- arxiv url: http://arxiv.org/abs/2504.14497v1
- Date: Sun, 20 Apr 2025 05:28:46 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-04-30 00:13:36.469845
- Title: Fast Plaintext-Ciphertext Matrix Multiplication from Additively Homomorphic Encryption
- Title（参考訳）: 付加同型暗号を用いた高速平文-球面行列乗算
- Authors: Krishna Sai Tarun Ramapragada, Utsav Banerjee,
- Abstract要約: 平文-暗号行列乗法は、プライバシ保存計算において必須のツールである。
未パッケージ加法的同型暗号方式から効率的なPC-MMを提案する。
提案手法は, 比較的小さなビット幅を持つ大行列に対して, 最先端技術と比較して, 最大で1桁の高速化を実現する。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Plaintext-ciphertext matrix multiplication (PC-MM) is an indispensable tool in privacy-preserving computations such as secure machine learning and encrypted signal processing. While there are many established algorithms for plaintext-plaintext matrix multiplication, efficiently computing plaintext-ciphertext (and ciphertext-ciphertext) matrix multiplication is an active area of research which has received a lot of attention. Recent literature have explored various techniques for privacy-preserving matrix multiplication using fully homomorphic encryption (FHE) schemes with ciphertext packing and Single Instruction Multiple Data (SIMD) processing. On the other hand, there hasn't been any attempt to speed up PC-MM using unpacked additively homomorphic encryption (AHE) schemes beyond the schoolbook method and Strassen's algorithm for matrix multiplication. In this work, we propose an efficient PC-MM from unpacked AHE, which applies Cussen's compression-reconstruction algorithm for plaintext-plaintext matrix multiplication in the encrypted setting. We experimentally validate our proposed technique using a concrete instantiation with the additively homomorphic elliptic curve ElGamal encryption scheme and its software implementation on a Raspberry Pi 5 edge computing platform. Our proposed approach achieves up to an order of magnitude speedup compared to state-of-the-art for large matrices with relatively small element bit-widths. Extensive measurement results demonstrate that our fast PC-MM is an excellent candidate for efficient privacy-preserving computation even in resource-constrained environments.
- Abstract（参考訳）: 平文-暗号行列乗算(英: Plaintext-ciphertext matrix multiplication, PC-MM)は、セキュア機械学習や暗号化信号処理などのプライバシー保護計算において必要不可欠なツールである。
平文-平文行列乗算には多くの確立されたアルゴリズムがあるが、平文-暗号文(および暗号文-暗号文)行列乗算を効率的に計算することは、多くの注目を集めている研究の活発な領域である。
最近の文献では、完全同型暗号(FHE)方式と単一命令多重データ(SIMD)処理を用いて、プライバシー保護行列乗算の様々な手法を探求している。
一方,PC-MM を高速化する試みは,教科書法やストラッセンの行列乗算アルゴリズム以外にも,未パッケージ加法準同型暗号(AHE)方式を用いて行われていない。
本研究では, プレインテキスト・プレーンテキスト・マトリックス乗算にカスセンの圧縮再構成アルゴリズムを適用し, アンパックAHEの効率的なPC-MMを提案する。
本手法は,加法的に同相な楕円曲線ElGamal暗号を用いた具体的なインスタンス化と,Raspberry Pi 5エッジコンピューティングプラットフォーム上でのソフトウェア実装を用いて実験的に検証する。
提案手法は, 比較的小さなビット幅を持つ大行列に対して, 最先端技術と比較して, 最大で1桁の高速化を実現する。
その結果,我々の高速PC-MMは,資源制約環境においても,効率的なプライバシ保存計算の候補として優れていることがわかった。
関連論文リスト
- CIPHERMATCH: Accelerating Homomorphic Encryption-Based String Matching via Memory-Efficient Data Packing and In-Flash Processing [8.114331115730021]
ホモモルフィック暗号化(HE)は、元のデータを公開せずに暗号化されたデータのセキュアな計算を可能にする。
多くのクラウドコンピューティングアプリケーション(例えば、DNA読み取りマッピング、バイオメトリックマッチング、Web検索)は、正確な文字列マッチングをキー操作として使っている。
ホモモルフィック暗号を用いた従来の文字列マッチングアルゴリズムは、高い計算遅延によって制限される。
論文 参考訳（メタデータ） (2025-03-12T00:25:58Z) - A Note on Efficient Privacy-Preserving Similarity Search for Encrypted Vectors [1.3824176915623292]
従来のベクトル類似性探索手法では、完全同型暗号(FHE)を用いて復号化せずに計算が可能であった。
この研究は、より効率的な代替手段を探究する: プライバシー保護類似性検索に加法的同型暗号(AHE)を使用する。
本稿では,AHE で暗号化された類似性探索のアルゴリズムを提案し,そのエラーの増大とセキュリティへの影響を解析する。
論文 参考訳（メタデータ） (2025-02-20T06:07:04Z) - Improving Algorithmic Efficiency using Cryptography [11.496343300483904]
計算問題を解く際の時間的複雑さを改善するために暗号を用いる方法を示す。
標準的な暗号仮定では、既存のアルゴリズムよりも高速なアルゴリズムを設計できることを示す。
論文 参考訳（メタデータ） (2025-02-18T17:08:59Z) - Cryptanalysis via Machine Learning Based Information Theoretic Metrics [58.96805474751668]
本稿では,機械学習アルゴリズムの新たな2つの応用法を提案する。
これらのアルゴリズムは、監査設定で容易に適用でき、暗号システムの堅牢性を評価することができる。
本稿では,DES,RSA,AES ECBなど,IND-CPAの安全でない暗号化スキームを高精度に識別する。
論文 参考訳（メタデータ） (2025-01-25T04:53:36Z) - Three-Input Ciphertext Multiplication for Homomorphic Encryption [6.390468088226496]
ホモモルフィック暗号化(HE)は、暗号文上で直接計算することができる。
HEは、ニューラルネットワーク推論、診断、財務データ分析など、プライバシ保護コンピューティングに不可欠である。
本稿では,計算の複雑さを低減するために,3入力暗号文の乗算を提案する。
論文 参考訳（メタデータ） (2024-10-17T13:40:49Z) - High-Performance Privacy-Preserving Matrix Completion for Trajectory Recovery [0.897780713904412]
本稿では,プライバシ保護行列補完のための高性能な手法を提案する。
数値実験の結果,提案手法は他のアルゴリズムよりも高速であることがわかった。
論文 参考訳（メタデータ） (2024-05-09T14:12:41Z) - SOCI^+: An Enhanced Toolkit for Secure OutsourcedComputation on Integers [50.608828039206365]
本稿では,SOCIの性能を大幅に向上させるSOCI+を提案する。
SOCI+は、暗号プリミティブとして、高速な暗号化と復号化を備えた(2, 2)ホールドのPaillier暗号システムを採用している。
実験の結果,SOCI+は計算効率が最大5.4倍,通信オーバヘッドが40%少ないことがわかった。
論文 参考訳（メタデータ） (2023-09-27T05:19:32Z) - Encrypted Dynamic Control exploiting Limited Number of Multiplications and a Method using RLWE-based Cryptosystem [0.3749861135832073]
本稿では,ほとんどの同型暗号方式で実装可能な動的コントローラを暗号化する手法を提案する。
結果として、暗号化されたコントローラは、暗号化されたデータごとに、限られた数の同型乗算しか必要としない。
本稿では,Ring Learning With Errors(RLWE)ベースの暗号システムにおいて,メッセージのベクトルを1つの暗号文に暗号化する手法のカスタマイズを提案する。
論文 参考訳（メタデータ） (2023-07-07T08:24:48Z) - Machine Learning-Aided Efficient Decoding of Reed-Muller Subcodes [59.55193427277134]
Reed-Muller (RM) 符号は、一般的なバイナリインプットメモリレス対称チャネルの容量を達成する。
RM符号は制限されたレートのみを許容する。
効率的なデコーダは、RM符号に対して有限長で利用可能である。
論文 参考訳（メタデータ） (2023-01-16T04:11:14Z) - Batch-efficient EigenDecomposition for Small and Medium Matrices [65.67315418971688]
EigenDecomposition (ED)は多くのコンピュータビジョンアルゴリズムとアプリケーションの中心にある。
本稿では,コンピュータビジョンの応用シナリオに特化したQRベースのED手法を提案する。
論文 参考訳（メタデータ） (2022-07-09T09:14:12Z) - High-Dimensional Sparse Bayesian Learning without Covariance Matrices [66.60078365202867]
共分散行列の明示的な構成を避ける新しい推論手法を提案する。
本手法では, 数値線形代数と共役勾配アルゴリズムの対角線推定結果とを結合する。
いくつかのシミュレーションにおいて,本手法は計算時間とメモリにおける既存手法よりも拡張性が高い。
論文 参考訳（メタデータ） (2022-02-25T16:35:26Z) - Sparsifying Parity-Check Matrices [60.28601275219819]
パリティチェック行列における1項目数を最小化する問題を考える。
最大型(ML)復号法では、PCMの復号に要する時間と直接関連している。
コード自体ではなく,PCMを変更する単純な行列行操作を提案する。
論文 参考訳（メタデータ） (2020-05-08T05:51:40Z) - Fast Generalized Matrix Regression with Applications in Machine Learning [46.79740387890322]
スケッチ技術を用いてGMR問題を効率的に解く高速一般化行列回帰アルゴリズム(Fast GMR)を提案する。
我々は,Fast GMRアルゴリズムを対称正定値行列近似と単一パス特異値分解に適用する。
論文 参考訳（メタデータ） (2019-12-27T07:03:37Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。