論文の概要: Sublinear-Overhead Secure Linear Algebra on a Dishonest Server
- arxiv url: http://arxiv.org/abs/2502.13060v1
- Date: Tue, 18 Feb 2025 17:05:17 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-02-19 14:05:13.067823
- Title: Sublinear-Overhead Secure Linear Algebra on a Dishonest Server
- Title(参考訳): ディホントサーバ上のサブリニア・オーバーヘッドセキュア線形代数
- Authors: Mark Braverman, Stephen Newman,
- Abstract要約: 我々は、高速、遠隔、およびデータ公開線形代数に対する自然効率性とセキュリティデシラタを述べる。
我々は、満足なアルゴリズムを暗示する行列とベクトル族の存在を予想し、共通暗号仮定に基づくそのようなアルゴリズムを提供する。
- 参考スコア(独自算出の注目度): 3.8105803634609483
- License:
- Abstract: Most heavy computation occurs on servers owned by a second party. This reduces data privacy, resulting in interest in data-oblivious computation, which typically severely degrades performance. Secure and fast remote computation is particularly important for linear algebra, which comprises a large fraction of total computation and is best run on highly specialized hardware often only accessible through the cloud. We state the natural efficiency and security desiderata for fast, remote, and data-oblivious linear algebra, conjecture the existence of matrix and vector families implying satisfactory algorithms, and provide such an algorithm contingent on common cryptographic assumptions. We achieve sublinear overhead for the server, dramatically reduced computation cost for the client, and various other practical advantages over previous algorithms. Keywords: Data Privacy, Data-Oblivious Computation, Delegation, Homomorphic Encryption, Cloud Computing, Algorithm Efficiency, Sublinear Overhead, LPN, Matrix Multiplication.
- Abstract(参考訳): 最も重い計算は、第2のパーティが所有するサーバで行われる。
これによりデータのプライバシが低下し、データ公開計算への関心が高まり、パフォーマンスが著しく低下する。
セキュアで高速なリモート計算は、線形代数において特に重要であり、これは総計算量のごく一部を含み、しばしばクラウドを通してのみアクセス可能な、高度に専門化されたハードウェア上で最もよく実行される。
本稿では, 高速, 遠隔, およびデータ公開線形代数に対する自然効率とセキュリティデシラタを述べるとともに, 満足なアルゴリズムを暗示する行列やベクトル族の存在を予想し, 共通暗号的仮定に基づくアルゴリズムを提案する。
サーバのサブ線形オーバーヘッド、クライアントの計算コストを劇的に削減し、以前のアルゴリズムよりも多くの実用的な利点を実現した。
キーワード:データプライバシ、データ公開計算、デリゲーション、同型暗号化、クラウドコンピューティング、アルゴリズム効率、サブリニアオーバーヘッド、LPN、マトリックス乗算。
関連論文リスト
- Optimal Oblivious Algorithms for Multi-way Joins [2.8151472703172398]
我々は,ORAMシミュレーションや他のセキュリティ仮定に頼らずに動作するマルチウェイ結合処理のためのソートに基づく新しいアルゴリズムを提案する。
我々のアルゴリズムは、安全でない最悪ケースの最適結合アルゴリズムと対数係数を一致させる時間的複雑さを持つ、基本的なプリミティブの非自明で明白な構成である。
論文 参考訳(メタデータ) (2025-01-08T01:23:29Z) - Online Nonparametric Supervised Learning for Massive Data [0.0]
本研究では,非パラメトリック分類器を大規模にリアルタイムに計算する高速アルゴリズムと,ストリーミングデータフレームワークを開発した。
提案手法は、リアルタイムな胎児の健康モニタリングによく使用される機械学習アルゴリズムと比較して評価・比較する。
論文 参考訳(メタデータ) (2024-05-29T20:04:23Z) - Secure and Efficient General Matrix Multiplication On Cloud Using Homomorphic Encryption [21.253885519048016]
ホモモルフィック暗号化(HE)は、機密性の高いアプリケーションのプライバシーとセキュリティを確保する効果的なツールとして登場した。
HEベースの計算を採用する上での大きな障害のひとつは、計算コストの過大さである。
論文 参考訳(メタデータ) (2024-05-03T16:50:02Z) - CoLA: Exploiting Compositional Structure for Automatic and Efficient
Numerical Linear Algebra [62.37017125812101]
機械学習における大規模線形代数問題に対して, CoLA という, 単純だが汎用的なフレームワークを提案する。
線形演算子抽象と合成ディスパッチルールを組み合わせることで、CoLAはメモリと実行時の効率的な数値アルゴリズムを自動的に構築する。
偏微分方程式,ガウス過程,同変モデル構築,教師なし学習など,幅広い応用で有効性を示す。
論文 参考訳(メタデータ) (2023-09-06T14:59:38Z) - Randomized Polar Codes for Anytime Distributed Machine Learning [66.46612460837147]
本稿では,低速な計算ノードに対して堅牢で,線形演算の近似計算と精度の両立が可能な分散コンピューティングフレームワークを提案する。
本稿では,復号化のための計算複雑性を低く保ちながら,実数値データを扱うための逐次復号アルゴリズムを提案する。
大規模行列乗算やブラックボックス最適化など,様々な文脈において,このフレームワークの潜在的な応用を実証する。
論文 参考訳(メタデータ) (2023-09-01T18:02:04Z) - Hyperdimensional Computing as a Rescue for Efficient Privacy-Preserving
Machine Learning-as-a-Service [9.773163665697057]
ホモモルフィック暗号化(HE)はこの逆問題に対処するための有望な手法である。
HEを使用すると、サービスプロバイダは、暗号化されたデータをクエリとして取り、それを復号することなくモデルを実行することができる。
我々は、超次元コンピューティングが、暗号化データによるプライバシー保護機械学習の救いになることを示した。
論文 参考訳(メタデータ) (2023-08-17T00:25:17Z) - RSC: Accelerating Graph Neural Networks Training via Randomized Sparse
Computations [56.59168541623729]
トレーニンググラフニューラルネットワーク(GNN)は、疎グラフベースの操作がハードウェアによって加速することが難しいため、時間を要する。
我々は,サンプリングに基づく近似による時間的複雑性を低減するために,計算精度のトレードオフを検討する。
本稿では,GNNを近似演算でトレーニングする可能性を初めて示すランダム化スパース計算を提案する。
論文 参考訳(メタデータ) (2022-10-19T17:25:33Z) - Photonic co-processors in HPC: using LightOn OPUs for Randomized
Numerical Linear Algebra [53.13961454500934]
従来のハードウェアでは,次元削減のためのランダム化ステップ自体が計算ボトルネックとなる可能性がある。
ランダム化は,様々な重要なrandnlaアルゴリズムにおいて,精度損失が無視できないほど大幅に高速化できることを示す。
論文 参考訳(メタデータ) (2021-04-29T15:48:52Z) - Berrut Approximated Coded Computing: Straggler Resistance Beyond
Polynomial Computing [34.69732430310801]
本稿では,ストラグラー効果に対処する代替手法として,Berrut Approximated Coded Computing (BACC)を提案する。
BACCは計算複雑性が低い数値的に安定であることが証明されている。
特に、BACCは、サーバのクラスタ上でディープニューラルネットワークをトレーニングするために使用される。
論文 参考訳(メタデータ) (2020-09-17T14:23:38Z) - New Oracle-Efficient Algorithms for Private Synthetic Data Release [52.33506193761153]
微分プライベートな合成データを構築するための3つの新しいアルゴリズムを提案する。
アルゴリズムは最悪の場合でも差分プライバシーを満たす。
現状の手法である高次元行列機構 citeMcKennaMHM18 と比較すると,我々のアルゴリズムは大規模作業負荷の精度が向上する。
論文 参考訳(メタデータ) (2020-07-10T15:46:05Z) - Faster Secure Data Mining via Distributed Homomorphic Encryption [108.77460689459247]
ホモモルフィック暗号化(HE)は、最近、暗号化されたフィールド上で計算を行う能力により、ますます注目を集めている。
本稿では,スケーリング問題の解決に向けて,新しい分散HEベースのデータマイニングフレームワークを提案する。
各種データマイニングアルゴリズムとベンチマークデータセットを用いて,新しいフレームワークの有効性と有効性を検証する。
論文 参考訳(メタデータ) (2020-06-17T18:14:30Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。