論文の概要: Fast Bounded-Independence Functions and Their Duals

• arxiv url: http://arxiv.org/abs/2606.07009v1
• Date: Fri, 05 Jun 2026 07:53:04 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-06-08 14:33:29.625628
• Title: Fast Bounded-Independence Functions and Their Duals
• Title（参考訳）: 高速境界独立関数とその双対
• Authors: Martijn Brehm, Yuval Ishai, Nicolas Resch,
• Abstract要約: 暗号アプリケーションによって動機付けされ、この領域で過去の結果を一般化し、改善する。 上記の結果が暗号に有用であることを示す。 これには、完全にセキュアなマルチパーティ計算のための最初の非自明なプロトコルが含まれる。
• 参考スコア（独自算出の注目度）: 21.031497777539332
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We continue the study of {\em fast} functions, computable by linear-size circuits, that share useful properties of random functions. Motivated by cryptographic applications, we generalize and improve on previous results in this area, obtaining the following results: - For any constant $t$, we construct a fast $t$-wise independent hash function with algebraic degree $\log_2 t$ (over $\mathbb F_2$), simultaneously optimizing both asymptotic circuit size and degree. - We simplify and improve a recent construction (ITCS 2026) of a family of fast codes with fast duals, both meeting the Gilbert-Varshamov bound. Unlike the previous construction, our construction has negligible failure probability, can accommodate general fields and rates, supports a systematic encoding, and admits fast universal encoders. - We strengthen the above to support stronger random-like properties, such as optimal combinatorial list-decoding. This is achieved by constructing, for any constant $t$, a family of fast linear functions that map any $t$ linearly independent inputs to uniform and statistically independent outputs. Prior to our work, this was only known for $t=1$. We demonstrate the usefulness of the above results to cryptography. This includes the first nontrivial protocols for perfectly secure multiparty computation whose circuit complexity scales linearly with the number of parties, as well as protocols for computing encrypted matrix-vector products with optimal asymptotic circuit complexity.
• Abstract（参考訳）: 我々は、ランダム関数の有用な性質を共有する線形サイズ回路で計算可能な関数の研究を継続する。 任意の定数 $t$ に対して、代数次数 $\log_2 t$ (over $\mathbb F_2$) の高速 $t$-wise 独立ハッシュ関数を構築し、同時に漸近回路サイズと次数の両方を最適化する。 -高速双対を持つ高速符号群(ITCS 2026)の最近の構成を簡略化し、改善し、どちらもギルバート=バルシャモフ境界を満たす。 従来の構成とは異なり、我々の構成は無視可能な失敗確率を持ち、一般的なフィールドとレートに対応でき、体系的な符号化をサポートし、高速なユニバーサルエンコーダを許容する。 -最適な組合せリスト復号化など、より強いランダムな特性をサポートするため、上記を強化します。 これは任意の定数$t$に対して、任意の$t$独立な入力を一様かつ統計的に独立な出力にマッピングする高速線型関数の族を構成することによって達成される。 私たちの研究以前には、これは$t=1$でしか知られていなかった。 以上の結果が暗号に有用であることを示す。 これには、回路複雑性がパーティ数と線形にスケールする完全セキュアなマルチパーティ計算のための最初の非自明なプロトコルと、最適な漸近回路複雑性を持つ暗号化行列ベクトル製品を計算するためのプロトコルが含まれる。

関連論文リスト

• Computational aspects of the Volterra Signature [0.0]
  本稿では,Volterraシグネチャカーネルの効率的なアルゴリズムを提案する。 すべてのアルゴリズムは JAX ベースのパッケージ "tensordev" で実装されている。 K(t,s)=sum_p k_p(t-s)A_p$は、$J$と$N$の複雑さを増さないことを示す。
  論文  参考訳（メタデータ） (2026-05-18T13:46:47Z)
• Block encoding of sparse matrices with a periodic diagonal structure [67.45502291821956]
  周期的な対角構造を持つスパース行列を符号化するための明示的な量子回路を提供する。 本手法の様々な応用は, 微分問題を解く文脈で論じる。
  論文  参考訳（メタデータ） (2026-02-11T07:24:33Z)
• Block Encoding Linear Combinations of Pauli Strings Using the Stabilizer Formalism [0.0]
  パウリ弦の線形結合を符号化する量子回路を構築するための新しい手法を提案する。 本手法の回路複雑性をLCU(Linear Combination of Unitary)手法と比較するために,具体的な例を4つ提示し,数値シミュレーションを用いた。
  論文  参考訳（メタデータ） (2026-01-09T11:41:46Z)
• Asymptotic yet practical optimization of quantum circuits implementing GF($2^m$) multiplication and division operations [1.1694898979785655]
  乗算演算と除算演算に最適化された量子回路を提案する。 我々のアシラフリーGF乗算回路はゲートカウントの複雑さが$O(mlog3)$である。 我々は,CNOTとToffoliゲート数の両方の削減を含む,$m$の暗号関連値に対して,実用的な利点を示す。
  論文  参考訳（メタデータ） (2025-11-25T18:43:08Z)
• On the Constant Depth Implementation of Pauli Exponentials [49.48516314472825]
  任意の長さの $Zotimes n$指数を$mathcalO(n)$ ancillae と 2体 XX と ZZ の相互作用を用いて一定深さの回路に分解する。 クビットリサイクルの恩恵を受ける回路の書き直し規則を導入し,本手法の正しさを実証する。
  論文  参考訳（メタデータ） (2024-08-15T17:09:08Z)
• Perturb-and-Project: Differentially Private Similarities and Marginals [73.98880839337873]
  差分プライバシーのための入力摂動フレームワークを再検討し、入力にノイズを付加する。 まず、ペアワイズ・コサイン類似性をプライベートにリリースするための新しい効率的なアルゴリズムを設計する。 我々は,$k$の辺縁クエリを$n$の機能に対して計算する新しいアルゴリズムを導出する。
  論文  参考訳（メタデータ） (2024-06-07T12:07:16Z)
• Fine-grained Analysis and Faster Algorithms for Iteratively Solving Linear Systems [9.30306458153248]
  多くの機械学習タスクにおいて重要なボトルネックとなっているが、大規模な線形システムの解決コストは定量化が難しいことが証明されている。 低次元構造を示すアプリケーションによって動機づけられた線形システムの解法における複雑性の微妙な概念を考察する。 線形システム $Ax = b$, すなわち $|Abarx - b| le epsilon |b|$ であるような $barx$ を求める。
  論文  参考訳（メタデータ） (2024-05-09T14:56:49Z)
• On Function Approximation in Reinforcement Learning: Optimism in the Face of Large State Spaces [208.67848059021915]
  強化学習のコアにおける探索・探索トレードオフについて検討する。 特に、関数クラス $mathcalF$ の複雑さが関数の複雑さを特徴づけていることを証明する。 私たちの後悔の限界はエピソードの数とは無関係です。
  論文  参考訳（メタデータ） (2020-11-09T18:32:22Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。