論文の概要: A Complexity-Theoretic Approach to Proofs of Space

• arxiv url: http://arxiv.org/abs/2608.08993v1
• Date: Mon, 10 Aug 2026 01:28:01 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-08-11 19:16:37.030229
• Title: A Complexity-Theoretic Approach to Proofs of Space
• Title（参考訳）: 宇宙の証明に対する複雑性-理論的アプローチ
• Abstract要約: 我々は、デランドマイズ仮定と暗号仮定の組み合わせからPoSを構築するための基本的な暗号フレームワークを提供する。 ほぼ最適なパラメータと相互作用パターンを持つPoSは、(a)上の仮定と(c)$mathsfP$に対するSNARGから従う。
• 参考スコア（独自算出の注目度）: 5.160781170457704
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: A Proof of Space, PoS, as introduced by Dziembowski et al. [CRYPTO'15], is a two-phase protocol that enables a Prover to convince an efficient Verifier that it has allocated a large amount of persistent memory to storing some information. To our knowledge, all existing PoS protocols are only known to be secure in the random oracle model (or under ad hoc assumptions about cryptographic assumptions). We provide an elementary framework for constructing PoS from a combination of derandomization assumptions and cryptographic assumptions. We provide a few simple instantiations of the framework. We show that non-trivial PoS follow from (a) $\mathsf{E}=\mathsf{DTIME[2^{O(n)}]}$ is hard for exponential-size nondeterministic circuits (an assumption introduced to show $\mathsf{AM}=\mathsf{NP}$), and (b) collision-resistant hash functions. We also show that PoS with nearly optimal parameters and interaction pattern follows from assumption (a) above and (c) SNARGs for $\mathsf{P}$.
• Abstract（参考訳）: Proof of Space, PoS は、Dziembowski et al [CRYPTO'15] によって導入された2段階のプロトコルで、Prover が効率の良い検証者に対して、いくつかの情報を格納するために大量の永続メモリを割り当てていることを納得させることができる。 我々の知る限り、既存のPoSプロトコルはすべて、ランダムなオラクルモデル(または暗号的仮定に関するアドホックな仮定)でのみセキュアであることが知られている。 我々は、デランドマイズ仮定と暗号仮定の組み合わせからPoSを構築するための基本的なフレームワークを提供する。 フレームワークの簡単なインスタンス化をいくつか提供します。 非自明なPoSが続くことを示す。 a) $\mathsf{E}=\mathsf{DTIME[2^{O(n)}]}$は指数サイズの非決定性回路($\mathsf{AM}=\mathsf{NP}$を示すために導入された仮定)と(b)衝突耐性ハッシュ関数に対して難しい。 また、ほぼ最適なパラメータと相互作用パターンを持つPoSが仮定から従うことを示す。 (a) 上の SNARG は$\mathsf{P}$ である。

関連論文リスト

• Verified Pythagorean Composition for Adaptive Cryptographic Games: Noise Flooding in Homomorphic Encryption [45.00791460144501]
  ノイズフラッディングは、近似同型暗号に対する復号攻撃に対する標準的な防御である。 本稿では,SSProveのセマンティクス上に新たなリレーショナル・プログラム・ロジックを構築した。
  論文  参考訳（メタデータ） (2026-08-14T00:40:29Z)
• Multi-Prover Interactive Proof Systems with Leakage [1.0960289997471082]
  本稿では,プロデューサ間の通信が許されるが境界づけられた設定にアプローチする2つの手法を提案する。 任意の$p$に対して、$mathsfNEXP$と$mathsfRE$に対して$mathsfMIPast$と$mathsfMIPast$プロトコルを構築することができる。
  論文  参考訳（メタデータ） (2026-05-11T01:58:44Z)
• Cloning Games, Black Holes and Cryptography [50.022147589030304]
  クローンゲーム解析のための新しいツールキットを提案する。 このフレームワークにより、バイナリフェーズ状態に基づいて新しいクローンゲームを分析することができる。 連成位相の変分最適境界は、ブラックホールの理想化されたモデルで衝突する情報について定量的な洞察を与えることを示す。
  論文  参考訳（メタデータ） (2024-11-07T14:09:32Z)
• Projection by Convolution: Optimal Sample Complexity for Reinforcement Learning in Continuous-Space MDPs [56.237917407785545]
  本稿では,円滑なベルマン作用素を持つ連続空間マルコフ決定過程(MDP)の一般クラスにおいて,$varepsilon$-optimal Policyを学習する問題を考察する。 我々のソリューションの鍵となるのは、調和解析のアイデアに基づく新しい射影技術である。 我々の結果は、連続空間 MDP における2つの人気と矛盾する視点のギャップを埋めるものである。
  論文  参考訳（メタデータ） (2024-05-10T09:58:47Z)
• Lossy Cryptography from Code-Based Assumptions [7.880958076366762]
  高度な暗号プリミティブの拡散は、複雑性クラス$SZK$の難しい問題を暗示している。 これは、コードベースの仮定から高度なプリミティブを構築するための障壁となる。 我々は、Dense-Sparseという、複雑性クラス$BPPSZK$に該当する新しいコードベースの仮定を提案する。
  論文  参考訳（メタデータ） (2024-02-06T02:17:08Z)
• A Fast Algorithm for the Real-Valued Combinatorial Pure Exploration of Multi-Armed Bandit [55.2480439325792]
  多武装バンディット(R-CPE-MAB)の真価純探査問題について検討する。 本稿では,差分に基づく探索法 (CombGapE) アルゴリズムを提案する。 我々は,CombGapEアルゴリズムが,合成データセットと実世界のデータセットの両方において,既存の手法を大幅に上回っていることを数値的に示す。
  論文  参考訳（メタデータ） (2023-06-15T15:37:31Z)
• Fast Rates for Maximum Entropy Exploration [52.946307632704645]
  エージェントが未知の環境下で活動し、報酬が得られない場合、強化学習(RL)における探索の課題に対処する。 本研究では,最大エントロピー探索問題を2つの異なるタイプで検討する。 訪問エントロピーには、$widetildemathcalO(H3S2A/varepsilon2)$ sample complexity を持つゲーム理論アルゴリズムを提案する。 軌道エントロピーに対しては,次数$widetildemathcalO(mathrmpoly(S,)の複雑さのサンプルを持つ単純なアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-03-14T16:51:14Z)
• Quantum Cryptography in Algorithmica [0.7524721345903025]
  ブラックボックス設定では、一方の関数が存在しなくても擬似ランダム状態に基づく量子暗号が可能であることを示す。 また、我々の結果をマルチコピー安全な擬似ランダム状態に一般化する予想も導入する。
  論文  参考訳（メタデータ） (2022-12-01T21:33:38Z)
• Reward-Mixing MDPs with a Few Latent Contexts are Learnable [75.17357040707347]
  報酬混合マルコフ決定過程(RMMDP)におけるエピソード強化学習の検討 我々のゴールは、そのようなモデルにおける時間段階の累積報酬をほぼ最大化する、ほぼ最適に近いポリシーを学ぶことである。
  論文  参考訳（メタデータ） (2022-10-05T22:52:00Z)
• Learning a Single Neuron with Adversarial Label Noise via Gradient Descent [50.659479930171585]
  モノトン活性化に対する $mathbfxmapstosigma(mathbfwcdotmathbfx)$ の関数について検討する。 学習者の目標は仮説ベクトル $mathbfw$ that $F(mathbbw)=C, epsilon$ を高い確率で出力することである。
  論文  参考訳（メタデータ） (2022-06-17T17:55:43Z)
• Quantum Resources Required to Block-Encode a Matrix of Classical Data [56.508135743727934]
  回路レベルの実装とリソース推定を行い、古典データの高密度な$Ntimes N$行列をブロックエンコードして$epsilon$を精度良くすることができる。 異なるアプローチ間のリソーストレードオフを調査し、量子ランダムアクセスメモリ(QRAM)の2つの異なるモデルの実装を検討する。 我々の結果は、単純なクエリの複雑さを超えて、大量の古典的データが量子アルゴリズムにアクセスできると仮定された場合のリソースコストの明確な図を提供する。
  論文  参考訳（メタデータ） (2022-06-07T18:00:01Z)
• A Ihara-Bass Formula for Non-Boolean Matrices and Strong Refutations of Random CSPs [4.023424709659175]
  制約あたり$k$変数(k-CSP)によるランダム制約満足度問題の強い反響を証明する。 割当数$p$の制約で満たされたランダムk-CSPインスタンスの場合、最適値が最大値$p+O_k(epsilon)$の制約で満足する証明書を効率的に計算できる。
  論文  参考訳（メタデータ） (2022-04-20T16:21:21Z)
• DASHA: Distributed Nonconvex Optimization with Communication Compression, Optimal Oracle Complexity, and No Client Synchronization [77.34726150561087]
  我々は,分散最適化問題に対する新しい手法であるDASHAを開発し,解析する。 MARINAとは異なり、新しいDASHAとDASHA-MVRは圧縮ベクターのみを送信し、ノードを同期しないため、学習をより実用的なものにしている。
  論文  参考訳（メタデータ） (2022-02-02T20:10:40Z)
• The Curse of Passive Data Collection in Batch Reinforcement Learning [82.6026077420886]
  高い利害関係のアプリケーションでは、アクティブな実験は危険すぎると考えられ、データはしばしば受動的に収集される。 バンディットやパッシブ、アクティブなデータ収集などの単純な場合も同様に効果的であるが、制御された状態のシステムからデータを集める場合、パッシブサンプリングの価格ははるかに高い。
  論文  参考訳（メタデータ） (2021-06-18T07:54:23Z)

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

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