論文の概要: A Characterization of Optimal-Rate Linear Homomorphic Secret Sharing Schemes, and Applications
- arxiv url: http://arxiv.org/abs/2311.14842v1
- Date: Fri, 24 Nov 2023 20:40:50 GMT
- ステータス: 処理完了
- システム内更新日: 2024-03-25 13:06:53.860569
- Title: A Characterization of Optimal-Rate Linear Homomorphic Secret Sharing Schemes, and Applications
- Title（参考訳）: 最適レート線形同型秘密共有スキームのキャラクタリゼーションとその応用
- Authors: Keller Blackwell, Mary Wootters,
- Abstract要約: Homomorphic Secret Sharing (HSS) は秘密共有方式で、$s$サーバ間で秘密の$x$を共有する。
HSSスキームにおける重要なパラメータはダウンロード率であり、各サーバから出力クライアントがダウンロードする必要がある情報の量を測定する。
おそらく驚くべきことに、その建設作業がほぼ最適であるような$ell$sのセットが示されています。
- 参考スコア（独自算出の注目度）: 13.566464121222225
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: A Homomorphic Secret Sharing (HSS) scheme is a secret-sharing scheme that shares a secret $x$ among $s$ servers, and additionally allows an output client to reconstruct some function $f(x)$, using information that can be locally computed by each server. A key parameter in HSS schemes is download rate, which quantifies how much information the output client needs to download from each server. Recent work (Fosli, Ishai, Kolobov, and Wootters, ITCS 2022) established a fundamental limitation on the download rate of linear HSS schemes for computing low-degree polynomials, and gave an example of HSS schemes that meet this limit. In this paper, we further explore optimal-rate linear HSS schemes for polynomials. Our main result is a complete characterization of such schemes, in terms of a coding-theoretic notion that we introduce, termed optimal labelweight codes. We use this characterization to answer open questions about the amortization required by HSS schemes that achieve optimal download rate. In more detail, the construction of Fosli et al. required amortization over $\ell$ instances of the problem, and only worked for particular values of $\ell$. We show that -- perhaps surprisingly -- the set of $\ell$'s for which their construction works is in fact nearly optimal, possibly leaving out only one additional value of $\ell$. We show this by using our coding-theoretic characterization to prove a necessary condition on the $\ell$'s admitting optimal-rate linear HSS schemes. We then provide a slightly improved construction of optimal-rate linear HSS schemes, where the set of allowable $\ell$'s is optimal in even more parameter settings. Moreover, based on a connection to the MDS conjecture, we conjecture that our construction is optimal for all parameter regimes.
- Abstract（参考訳）: HSS(Hymomorphic Secret Sharing)スキームは、秘密共有スキームで、$s$サーバ間で秘密の$x$を共有し、出力クライアントが各サーバでローカルに計算できる情報を使用して、ある関数$f(x)$を再構築することを可能にする。
HSSスキームにおける重要なパラメータはダウンロード率であり、各サーバから出力クライアントがダウンロードする必要がある情報の量を測定する。
最近の研究 (Fosli, Ishai, Kolobov, Wootters, ITCS 2022) は、低次多項式を計算するための線形 HSS スキームのダウンロード率に関する基本的な制限を確立し、この制限を満たす HSS スキームの例を示した。
本稿では,多項式に対する最適レート線形 HSS スキームについて検討する。
我々の主な成果は、最適ラベル重み付き符号を導入した符号化理論の概念の観点から、そのようなスキームの完全な特徴付けである。
最適なダウンロード率を実現するHSSスキームで要求される償却に関するオープンな疑問に答えるために,この特徴を用いる。
より詳しくは、Fosli et al の構成は、問題の$\ell$インスタンスに対する償却を必要とし、$\ell$の特定の値に対してのみ機能する。
おそらく驚くべきことに、その建設作業がほぼ最適である$\ell$のセットが、おそらく1つの追加の$\ell$だけを残していることを示している。
符号化理論を用いて、最適レート線形 HSS スキームを許容する$\ell$ の条件を証明する。
次に、最適レート線形 HSS スキームをわずかに改善し、許容可能な$\ell$'s の集合がさらにパラメータ設定で最適となるようにします。
さらに、MDS予想の関連性に基づき、我々の構成は全てのパラメーターレジームに対して最適であると予想する。
関連論文リスト
- Transfer Q Star: Principled Decoding for LLM Alignment [105.89114186982972]
Transfer $Q*$は、ベースラインモデルを通してターゲット報酬$r$の最適値関数を推定する。
提案手法は, 従来のSoTA法で観測された準最適差を著しく低減する。
論文 参考訳（メタデータ） (2024-05-30T21:36:12Z) - Distributed Optimization with Feasible Set Privacy [35.16231062731263]
2つのエージェントは、実行可能なセットを$mathcalP1$と$mathcalP1$を互いにプライベートに保ちながら、最適なソリューションセットを学ぶ。
エージェントの1つが$mathcalP$をプライベートにチェックする、シーケンシャルなプライベート情報検索(SPIR)フレームワークを採用しています。
SPIR-based private set intersection (PSI) プロトコルで実現可能な$mathcalP1$をプライベートに取得するのに対し、最適な方法を見つけるには、情報漏洩が少なく、ダウンロードも少ないため、我々の手法の方が優れていることを示す。
論文 参考訳（メタデータ） (2023-12-04T18:45:04Z) - Learning to Relax: Setting Solver Parameters Across a Sequence of Linear System Instances [42.16343861129583]
オンライン学習アルゴリズムでは、シーケンス長が増加するにつれて、全体のコストが最高の$omega$に近づくように、一連のインスタンスに対してパラメータを選択できることが示される。
我々の研究は、高精度線形システム解法の最初の学習理論処理と、データ駆動型科学計算のエンドツーエンド保証を提供する。
論文 参考訳（メタデータ） (2023-10-03T17:51:42Z) - Nearly Minimax Optimal Reinforcement Learning for Linear Markov Decision
Processes [80.89852729380425]
そこで本研究では,最小限の最小残差である$tilde O(dsqrtH3K)$を計算効率よく実現したアルゴリズムを提案する。
我々の研究は線形 MDP を用いた最適 RL に対する完全な答えを提供する。
論文 参考訳（メタデータ） (2022-12-12T18:58:59Z) - Shapley-NAS: Discovering Operation Contribution for Neural Architecture
Search [96.20505710087392]
ニューラルアーキテクチャ探索のための演算寄与度(Shapley-NAS)を評価するためのShapley値に基づく手法を提案する。
提案手法は,光探索コストに比例して最先端の手法よりも優れていることを示す。
論文 参考訳（メタデータ） (2022-06-20T14:41:49Z) - Matching Pursuit Based Scheduling for Over-the-Air Federated Learning [67.59503935237676]
本稿では,フェデレートラーニング手法を用いて,オーバー・ザ・エアラーニングのための低複雑さデバイススケジューリングアルゴリズムのクラスを開発する。
最先端の提案方式と比較すると,提案方式は極めて低効率なシステムである。
提案手法の有効性は,CIFARデータセットを用いた実験により確認した。
論文 参考訳（メタデータ） (2022-06-14T08:14:14Z) - Provably Efficient Generative Adversarial Imitation Learning for Online
and Offline Setting with Linear Function Approximation [81.0955457177017]
GAIL(Generative Adversarial mimicion Learning)では、特定の報酬セットにおいて、専門家の政策からそのパフォーマンスを区別できないように、専門家のデモンストレーションからポリシーを学習することを目的としている。
GAILをオンラインとオフラインの両方で線形関数近似を用いて検討し、その変換関数と報酬関数は特徴写像において線形である。
論文 参考訳（メタデータ） (2021-08-19T16:16:00Z) - Single-Server Private Linear Transformation: The Joint Privacy Case [10.072633952908456]
本稿では,プライベート情報検索とプライベート線形計算の問題を一般化するPLT(Private Linear Transformation)の問題を紹介する。
この問題には、1つ以上のリモートサーバが$K$メッセージを格納する(IDコピー)ことと、$D$サブセットの独立線形結合を$L$で計算したいユーザが含まれている。
論文 参考訳（メタデータ） (2021-06-09T17:09:22Z) - On Query-efficient Planning in MDPs under Linear Realizability of the
Optimal State-value Function [14.205660708980988]
固定水平マルコフ決定過程(MDP)における局所的計画の問題点を生成モデルを用いて考察する。
最近の下界は、最適ポリシーの作用値関数が線形に実現可能である場合の関連する問題は指数的なクエリ数を必要とすることを証明している。
本研究では,アクションセットが小さい場合,ポリ$(H, d)$学習が(状態値関数の実現可能性を持つ)可能であることを確かめる。
論文 参考訳（メタデータ） (2021-02-03T13:23:15Z) - Provably Efficient Safe Exploration via Primal-Dual Policy Optimization [105.7510838453122]
制約付きマルコフ決定過程(CMDP)を用いた安全強化学習(SRL)問題について検討する。
本稿では,関数近似設定において,安全な探索を行うCMDPの効率の良いオンラインポリシー最適化アルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-03-01T17:47:03Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。