論文の概要: Lower Bounds for PIR with Preprocessing from Blackbox Cryptography

• arxiv url: http://arxiv.org/abs/2607.06451v2
• Date: Wed, 08 Jul 2026 18:48:30 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-07-10 14:45:27.265131
• Title: Lower Bounds for PIR with Preprocessing from Blackbox Cryptography
• Title（参考訳）: ブラックボックス暗号による前処理によるPIRの低域化
• Authors: Alexander Hoover, Giuseppe Persiano, Kevin Yeo,
• Abstract要約: プリプロセッシングによるシングルサーバプライベート情報検索(PIR)の限界について検討する。 本研究は,プリプロセッシングを伴うシングルサーバPIRに対して,計算の低いバウンダリを提示する。
• 参考スコア（独自算出の注目度）: 57.20693707878285
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: (shortened for arXiv metadata) We study the limits of single-server private information retrieval (PIR) with preprocessing. Prior work has shown that single-server PIR with sublinear communication requires a linear number of (public-key) server operations per query [DMO00, DH24]. Recent breakthrough works, including [CHK22, ZPZS24, LMW23], circumvent these lower bounds by critically leveraging preprocessing to construct single-server PIR with sublinear query computation. Our work presents computation lower bounds for any single-server PIR with preprocessing that makes blackbox usage of {\em any} cryptography (such as random oracles and virtual blackbox obfuscation). For any client preprocessing scheme where the client stores $s$ bits about an $n$-bit database, we prove the online amortized computation must be $Ω(n/s)$ across $k = Ω(s)$ queries (even if performed in a single batch query). In more detail, we prove that they must have either $Ω(n/s)$ amortized online communication or the server must perform $Ω(n/s)$ cryptographic operations. Our lower bounds are optimal as there exist PIRs with client preprocessing matching exactly one of the above requirements while outperforming the other. Furthermore, our lower bounds also rule out the existence of doubly efficient PIR from blackbox cryptography with sublinear query computation. Our proof framework also supports $Ω(n/s)$ communication lower bounds for three mildly restricted classes of single-server PIR. We also prove lower bounds for symmetric private information retrieval (SPIR) with client preprocessing in the random oracle model and present a matching SPIR construction with client preprocessing using only OWFs during queries.
• Abstract（参考訳）: (arXivメタデータの短縮) プリプロセッシングによるシングルサーバプライベート情報検索(PIR)の限界について検討する。 以前の研究で、サブリニア通信を備えたシングルサーバPIRはクエリ毎の(公開キー)サーバ操作の線形数を必要とすることが示されている。 近年の[CHK22, ZPZS24, LMW23]を含むブレークスルーは, プリプロセッシングを批判的に活用し, サブ線形クエリ計算によるシングルサーバPIRの構築によって, 下位境界を回避している。 我々の研究は、任意のシングルサーバPIRに対して、(ランダムオラクルや仮想ブラックボックス難読化のような)ブラックボックスの暗号を前処理で使用する計算の低いバウンダリを提示する。 クライアントが$n$-bitデータベースに関する$s$ビットを格納している任意のクライアント前処理スキームに対して、オンラインのアモータイズされた計算は$Ω(n/s)$ across $k = Ω(s)$クエリでなければならない(単一のバッチクエリで実行されても)。 より詳しくは、それらが$Ω(n/s)$償却されたオンライン通信を持っているか、サーバが$Ω(n/s)$暗号処理をしなければならないことを証明している。 私たちの下位境界は、クライアント前処理が上記の要件の1つと完全に一致し、他方よりも優れたPIRが存在するため、最適です。 さらに、下位境界では、サブ線形クエリ計算によるブラックボックス暗号からの2倍効率のPIRの存在も除外している。 我々の証明フレームワークは、シングルサーバPIRの3つの軽度に制限されたクラスに対して、$Ω(n/s)$通信の下限もサポートしています。 また、ランダムオラクルモデルにおいて、クライアント前処理を伴う対称プライベート情報検索(SPIR)の下位境界を証明し、クエリ中にOWFのみを使用してクライアント前処理と一致するSPIR構成を示す。

関連論文リスト

• LAPRAS : Learning-Augmented PRivate Answering for linear query Streams [9.706153384025809]
  本稿では,ストリームに現れる可能性のあるクエリの予測セットを出力するオラクルへのアクセスを想定したLAPRASを提案する。 LAPRASはオフライン最適マトリックスメカニズムを使って予測されたクエリに回答し、残りのクエリを残りの予算からオンラインで回答する。 実証的には、2つの実際のデータセットに対して、意図した一貫性-ロバスト性トレードオフを検証する。
  論文  参考訳（メタデータ） (2026-05-03T16:46:53Z)
• On the Gradient Complexity of Private Optimization with Private Oracles [51.044364532408345]
  我々は,リプシッツ損失の個人的経験的/人口的リスクの1次オラクルクエリーの観点から,ランニング時間について検討した。 予測ランニングタイム$(minfracsqrtd2, fracdlog(1/))$は、$dgeq 1/2$のときの次元の問題に対して$$$過剰なリスクを達成するために必要であることを示す。
  論文  参考訳（メタデータ） (2025-11-17T23:58:11Z)
• Enhancing TreePIR for a Single-Server Setting via Resampling [0.0]
  Private Information Retrievalは、クライアントがクエリされたインデックスを公開せずに、パブリックデータベースからエントリを検索することを可能にする。 従来のPIRスキームは、強い仮定の下でのみ、サブ線形サーバ計算を実現する。 本稿では,複数テーブルのヒント構造を導入し,単一サーバ設定へのTreePIRの適用を提案する。
  論文  参考訳（メタデータ） (2025-10-06T15:03:05Z)
• ProofWala: Multilingual Proof Data Synthesis and Theorem-Proving [53.67926215943612]
  $rm P Small ROOFW Small ALA$は、ニューラル定理プローサと2つの確立された対話的証明アシスタント(ITP)間の相互作用を可能にする 私たちは、$rm P Small ROOFWsmall ALA$生成のCoqとLeanのデータの組み合わせでトレーニングされたモデルが、標準のprov-at-k$メトリック上で、Lean-onlyとCoq-onlyのモデルを上回っていることを示します。
  論文  参考訳（メタデータ） (2025-02-07T05:35:46Z)
• $\mathsf{OPA}$: One-shot Private Aggregation with Single Client Interaction and its Applications to Federated Learning [7.713377215066152]
  一発のプライベートアグリゲーション(mathsfOPA$)を導入します。 各クライアントはアグリゲーション毎に1回だけ通信するので、ドロップアウトの管理と動的参加が簡単になる。 $mathsfOPA$は実用的で、最先端のソリューションよりも優れています。
  論文  参考訳（メタデータ） (2024-10-29T17:50:11Z)
• Federated Combinatorial Multi-Agent Multi-Armed Bandits [79.1700188160944]
  本稿では,Banditを用いたオンライン最適化に適したフェデレーション学習フレームワークを提案する。 この設定では、エージェントのアームサブセットは、個々のアーム情報にアクセスせずにこれらのサブセットに対するノイズの多い報酬を観察し、特定の間隔で協力して情報を共有することができる。
  論文  参考訳（メタデータ） (2024-05-09T17:40:09Z)
• Differentially Private Clustering in Data Streams [56.26040303056582]
  私たちは、$k$-meansと$k$-medianクラスタリングのための最初の微分プライベートアルゴリズムを、最大で$T$のストリーム上の$d$-dimensional Euclideanデータポイントに対して提供します。 当社の主な技術的貢献は、オフラインDPコアセットまたはクラスタリングアルゴリズムをブラックボックスとしてのみ必要とする、データストリームのための微分プライベートクラスタリングフレームワークです。
  論文  参考訳（メタデータ） (2023-07-14T16:11:22Z)

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

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