論文の概要: Succinct Oblivious Tensor Evaluation and Applications: Adaptively-Secure Laconic Function Evaluation and Trapdoor Hashing for All Circuits
- arxiv url: http://arxiv.org/abs/2508.09673v1
- Date: Wed, 13 Aug 2025 10:03:03 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-08-14 20:42:00.850085
- Title: Succinct Oblivious Tensor Evaluation and Applications: Adaptively-Secure Laconic Function Evaluation and Trapdoor Hashing for All Circuits
- Title（参考訳）: アクシベートなテンソル評価とその応用: 適応型安全ラコニック関数評価と全回路のトラップドアハッシュ
- Authors: Damiano Abram, Giulio Malavolta, Lawrence Roy,
- Abstract要約: 2つのベクトルのテンソル積の加法的秘密共有を$mathbfx otimes mathbfy$で計算する。
本稿では,LWE問題を用いた標準学習におけるOTEの構成について述べる。
我々は、この新しい技術ツールが暗号化プリミティブのホストをいかに可能にし、すべてLWEに再現可能なセキュリティを実現するかを示す。
- 参考スコア（独自算出の注目度）: 17.82458125377762
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We propose the notion of succinct oblivious tensor evaluation (OTE), where two parties compute an additive secret sharing of a tensor product of two vectors $\mathbf{x} \otimes \mathbf{y}$, exchanging two simultaneous messages. Crucially, the size of both messages and of the CRS is independent of the dimension of $\mathbf{x}$. We present a construction of OTE with optimal complexity from the standard learning with errors (LWE) problem. Then we show how this new technical tool enables a host of cryptographic primitives, all with security reducible to LWE, such as: * Adaptively secure laconic function evaluation for depth-$D$ functions $f:\{0, 1\}^m\rightarrow\{0, 1\}^\ell$ with communication $m+\ell+D\cdot \mathrm{poly}(\lambda)$. * A trapdoor hash function for all functions. * An (optimally) succinct homomorphic secret sharing for all functions. * A rate-$1/2$ laconic oblivious transfer for batch messages, which is best possible. In particular, we obtain the first laconic function evaluation scheme that is adaptively secure from the standard LWE assumption, improving upon Quach, Wee, and Wichs (FOCS 2018). As a key technical ingredient, we introduce a new notion of \emph{adaptive lattice encodings}, which may be of independent interest.
- Abstract（参考訳）: 2つのベクトルのテンソル積の加法的秘密共有を計算し、2つの同時メッセージを交換する「succinct oblivious tensor Evaluation (OTE)」の概念を提案する。
重要なことに、メッセージのサイズとCRSのサイズは$\mathbf{x}$とは独立である。
本稿では,LWE問題を用いた標準学習におけるOTEの構成について述べる。
次に、新しい技術ツールによって暗号化プリミティブのホストが利用可能になり、セキュリティがLWEに再現可能であることを示します。 * depth-D$関数の適応的にセキュアなラドン関数の評価。
※すべての関数に対するトラップドアハッシュ関数。
※すべての関数に対する(最適に)簡潔な同型秘密共有。
※ A rate-$1/2$ laconic oblivious transfer for batch message, which is most possible。
特に、標準的なLWE仮定から適応的に安全であり、Quoch, Wee, Wichs(FOCS 2018)を改良した最初のラコニック関数評価スキームを得る。
重要な技術的要素として、独立な関心を持つかもしれない 'emph{adaptive lattice encodings' という新しい概念を導入する。
関連論文リスト
- Optimal Convergence Rates of Deep Neural Network Classifiers [25.56187933090708]
Tsybakovノイズ条件下での2値分類問題を$[0,1]d$で検討する。
分類器の過大な0-1リスクに対する最適収束率は$$ left ( frac1n right)fracbetacdot (1wedgebeta)qfracd_*s+1+ (1+frac1s+1)cdotbetacdot (1wedgebeta)q;
論文 参考訳（メタデータ） (2025-06-17T18:13:09Z) - Sign Operator for Coping with Heavy-Tailed Noise in Non-Convex Optimization: High Probability Bounds Under $(L_0, L_1)$-Smoothness [74.18546828528298]
SignSGD with Majority Votingは,Kappakappakappa-1right,Kappakappakappa-1right,Kappakappakappa-1right,Kappakappakappa-1right,Kappaka ppakappa-1right,Kappakappakappa-1right,Kappakappakappa-1right,Kappakappakappa-1right,Kappakappakappa -1right,Kappakappakappa-1right,Kappakappakappa-1right,Kappakappappapa-1right,Kappaを用いて,複雑性の全範囲で堅牢に動作することを示す。
論文 参考訳（メタデータ） (2025-02-11T19:54:11Z) - Provably Efficient Reinforcement Learning with Multinomial Logit Function Approximation [67.8414514524356]
本稿では,MNL関数近似を用いたMDPの新たなクラスについて検討し,状態空間上の確率分布の正当性を保証する。
その大きな利点にもかかわらず、非線形関数を組み込むことは、統計的および計算効率の両方において重大な課題を提起する。
我々は,$widetildemathcalO(dH2sqrtK + kappa-1d2H2)$を後悔するアルゴリズムを提案する。
論文 参考訳（メタデータ） (2024-05-27T11:31:54Z) - Corruption-Robust Offline Reinforcement Learning with General Function
Approximation [60.91257031278004]
一般関数近似を用いたオフライン強化学習(RL)における劣化問題について検討する。
我々のゴールは、崩壊しないマルコフ決定プロセス(MDP)の最適方針に関して、このような腐敗に対して堅牢で、最適でないギャップを最小限に抑える政策を見つけることである。
論文 参考訳（メタデータ） (2023-10-23T04:07:26Z) - An Oblivious Stochastic Composite Optimization Algorithm for Eigenvalue
Optimization Problems [76.2042837251496]
相補的な合成条件に基づく2つの難解なミラー降下アルゴリズムを導入する。
注目すべきは、どちらのアルゴリズムも、目的関数のリプシッツ定数や滑らかさに関する事前の知識なしで機能する。
本稿では,大規模半確定プログラム上での手法の効率性とロバスト性を示す。
論文 参考訳（メタデータ） (2023-06-30T08:34:29Z) - Scalable Primal-Dual Actor-Critic Method for Safe Multi-Agent RL with
General Utilities [12.104551746465932]
安全マルチエージェント強化学習について検討し、エージェントはそれぞれの安全制約を満たしつつ、局所的な目的の総和をまとめて最大化しようとする。
我々のアルゴリズムは、$mathcalOleft(T-2/3right)$のレートで1次定常点(FOSP)に収束する。
サンプルベースの設定では、高い確率で、我々のアルゴリズムは、$epsilon$-FOSPを達成するために$widetildemathcalOleft(epsilon-3.5right)$サンプルが必要です。
論文 参考訳（メタデータ） (2023-05-27T20:08:35Z) - Randomized Block-Coordinate Optimistic Gradient Algorithms for Root-Finding Problems [11.15373699918747]
大規模設定における非線形方程式の解を近似する2つの新しいアルゴリズムを開発した。
本稿では,機械学習,統計的学習,ネットワーク最適化などにおける顕著な応用を網羅した大規模有限サム包含のクラスに適用する。
論文 参考訳（メタデータ） (2023-01-08T21:46:27Z) - An Efficient Stochastic Algorithm for Decentralized Nonconvex-Strongly-Concave Minimax Optimization [25.00475462213752]
Decentralized Recursive Dec. Method (DREAM)
具体的には、$mathcalO(minminappaappa3eps-3,kappa2N)$ one-order oracle (SFO)コールと$tildemathcalO(kappa2 epsilon-2)通信ラウンドが必要です。
我々の数値実験は,従来の手法の優越性を検証した。
論文 参考訳（メタデータ） (2022-12-05T16:09:39Z) - On the Complexity of Decentralized Smooth Nonconvex Finite-Sum Optimization [21.334985032433778]
分散最適化問題 $min_bf xinmathbb Rd f(bf x)triq frac1msum_i=1m f_i(bf x)triq frac1nsum_j=1n。
論文 参考訳（メタデータ） (2022-10-25T11:37:11Z) - Nearly Optimal Regret for Learning Adversarial MDPs with Linear Function
Approximation [92.3161051419884]
我々は、敵対的な報酬と完全な情報フィードバックで有限正方体エピソディックマルコフ決定プロセスのための強化学習を研究します。
我々は、$tildeO(dHsqrtT)$ regretを達成できることを示し、$H$はエピソードの長さである。
また、対数因子までの$tildeOmega(dHsqrtT)$の値が一致することを証明する。
論文 参考訳（メタデータ） (2021-02-17T18:54:08Z) - Provably Efficient Safe Exploration via Primal-Dual Policy Optimization [105.7510838453122]
制約付きマルコフ決定過程(CMDP)を用いた安全強化学習(SRL)問題について検討する。
本稿では,関数近似設定において,安全な探索を行うCMDPの効率の良いオンラインポリシー最適化アルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-03-01T17:47:03Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。