論文の概要: Enhancing TreePIR for a Single-Server Setting via Resampling
- arxiv url: http://arxiv.org/abs/2510.04882v1
- Date: Mon, 06 Oct 2025 15:03:05 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-10-07 16:52:59.923653
- Title: Enhancing TreePIR for a Single-Server Setting via Resampling
- Title（参考訳）: 再サンプリングによる単一サーバ設定のためのTreePIRの強化
- Authors: Elian Morel,
- Abstract要約: Private Information Retrievalは、クライアントがクエリされたインデックスを公開せずに、パブリックデータベースからエントリを検索することを可能にする。
従来のPIRスキームは、強い仮定の下でのみ、サブ線形サーバ計算を実現する。
本稿では,複数テーブルのヒント構造を導入し,単一サーバ設定へのTreePIRの適用を提案する。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Private Information Retrieval (PIR) allows a client to retrieve an entry $\text{DB}[i]$ from a public database $\text{DB}$ held by one or more servers, without revealing the queried index $i$. Traditional PIR schemes achieve sublinear server computation only under strong assumptions, such as the presence of multiple non-colluding servers or the use of public-key cryptography. To overcome these limitations, \textit{preprocessing PIR} schemes introduce a query-independent offline phase where the client collects \textit{hints} that enable efficient private queries during the online phase. In this work, we focus on preprocessing PIR schemes relying solely on \textit{One-Way Functions} (OWFs), which provide minimal cryptographic assumptions and practical implementability. We study three main constructions -- TreePIR, PIANO, and PPPS -- that explore different trade-offs between communication, storage, and server trust assumptions. Building upon the mechanisms introduced in PIANO and PPPS, we propose an adaptation of TreePIR to the single-server setting by introducing a dual-table hint structure (primary and backup tables) and a \textit{resampling} technique to refresh hints efficiently. Our proposed scheme achieves logarithmic upload bandwidth and $O(\sqrt{n}\log n)$ download complexity while requiring $O(\sqrt{n}\log n)$ client storage. This represents a significant improvement over prior single-server preprocessing PIR schemes such as PIANO ($O(\sqrt{n})$ bandwidth) and PPPS ($O(n^{1/4})$ bandwidth), while maintaining the simplicity and minimal assumptions of the OWF-based setting.
- Abstract（参考訳）: Private Information Retrieval (PIR)により、クライアントは1つ以上のサーバが保持する公開データベースから$\text{DB}[i]$のエントリを取得できる。
従来のPIRスキームは、複数の非凝固サーバの存在や公開鍵暗号の使用など、強い前提の下でのみ、サブ線形サーバ計算を実現する。
これらの制限を克服するために、 \textit{preprocessing PIR} スキームは、クライアントがオンラインフェーズ中に効率的なプライベートクエリを可能にする \textit{hints} を収集するクエリ非依存のオフラインフェーズを導入している。
本研究は,最小限の暗号仮定と実用的な実装性を提供する,‘textit{One-Way Functions} (OWFs) のみに依存するPIRスキームの事前処理に焦点をあてる。
TreePIR、PIANO、PPPSの3つの主要な構成について検討し、通信、ストレージ、およびサーバ信頼の前提間の異なるトレードオフを探索する。
PIANO と PPPS で導入された機構を基盤として,Double-table hint 構造 (プライマリテーブルとバックアップテーブル) と \textit{resampling} 技術を導入して,単一サーバ環境における TreePIR の適応性を提案する。
提案手法は,$O(\sqrt{n}\log n)$クライアントストレージを必要としながら,対数アップロード帯域と$O(\sqrt{n}\log n)$ダウンロード複雑性を実現する。
これは、PIANO(O(\sqrt{n})$バンド幅)やPPPS(O(n^{1/4})$バンド幅)のようなPIRスキームよりも大幅に改善され、OWFベースの設定の単純さと最小限の仮定を維持している。
関連論文リスト
- Symmetric Private Information Retrieval (SPIR) on Graph-Based Replicated Systems [43.914623898157856]
単純なグラフでモデル化された複製されたデータベース上の対称プライベート情報検索。
本研究では,SPIRを実現するのに必要なサーバ側の共通乱数性も,そのグラフに従ってサーバに複製されるような設定について考察する。
論文 参考訳（メタデータ） (2025-07-23T17:51:08Z) - 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) - Private Information Retrieval on Multigraph-Based Replicated Storage [39.51026717015587]
多重グラフを用いた複製システムにおけるプライベート情報検索問題について考察する。
我々の目標は、$r$-multigraphのPIR容量の上下境界を確立することです。
論文 参考訳（メタデータ） (2025-01-29T18:48:22Z) - Federated Combinatorial Multi-Agent Multi-Armed Bandits [79.1700188160944]
本稿では,Banditを用いたオンライン最適化に適したフェデレーション学習フレームワークを提案する。
この設定では、エージェントのアームサブセットは、個々のアーム情報にアクセスせずにこれらのサブセットに対するノイズの多い報酬を観察し、特定の間隔で協力して情報を共有することができる。
論文 参考訳（メタデータ） (2024-05-09T17:40:09Z) - Private Aggregate Queries to Untrusted Databases [3.6209090009720155]
プライベート情報検索(Private Information Search, PIR)は、プライバシ保護のための暗号ツールである。
ほとんどのPIRプロトコルは、クライアントが意図したデータベースアイテムの正確な行インデックスを知る必要がある。
我々は、ユーザが集約された結果を取得することができる新しい情報理論PIRフレームワークを構築した。
論文 参考訳（メタデータ） (2024-03-20T04:35:21Z) - RAMP: A Flat Nanosecond Optical Network and MPI Operations for
Distributed Deep Learning Systems [68.8204255655161]
我々は、RAMPと呼ばれるナノ秒再構成による、ほぼスケール、全2分割帯域、オールツーオール、シングルホップ、オール光学ネットワークアーキテクチャを導入する。
RAMPは、最大65,536ノードで1ノードあたり12.8Tbpsの大規模分散並列コンピューティングシステムをサポートしている。
論文 参考訳（メタデータ） (2022-11-28T11:24:51Z) - Quantum Private Information Retrieval for Quantum Messages [71.78056556634196]
量子メッセージのための量子プライベート情報検索(QPIR)は、1つまたは複数のサーバから複数の量子状態のうちの1つを、どの状態が検索されたかを明らかにすることなく取得するプロトコルである。
我々はQPIRを,サーバがメッセージ状態の1つのコピーを含むブラインド設定と,サーバがメッセージ状態の記述を含む可視設定の2つの異なる設定で検討する。
論文 参考訳（メタデータ） (2021-01-22T10:28:32Z) - Towards Differentially Private Text Representations [52.64048365919954]
信頼できないサーバ環境下で新しいディープラーニングフレームワークを開発する。
乱数化モジュールに対して、プライバシーパラメータ$epsilon$の精度への影響を低減するために、新しいローカル微分プライベート(LDP)プロトコルを提案する。
分析と実験により、我々のフレームワークは、非プライベートなフレームワークや既存のLDPプロトコルと同等またはそれ以上のパフォーマンスを提供することが示された。
論文 参考訳（メタデータ） (2020-06-25T04:42:18Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。