論文の概要: Zero-Knowledge Proofs in Sublinear Space

• arxiv url: http://arxiv.org/abs/2509.05326v1
• Date: Sat, 30 Aug 2025 23:22:54 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-09-09 16:12:15.236036
• Title: Zero-Knowledge Proofs in Sublinear Space
• Title（参考訳）: 地下空間におけるゼロ知識証明
• Authors: Logan Nye,
• Abstract要約: 本稿では,最初のサブ線形空間ZKP証明器を構築する。 私たちのコアコントリビューションは、古典的なツリー評価問題の例として、証明生成を再構成する等価性です。 このアプローチは、証明のサイズ、検証時間、基礎システムのトランスクリプト/セキュリティ保証を保ちながら、証明メモリを線形の T から O(sqrt(T)) (O(log T) の下位項まで) に還元する。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Modern zero-knowledge proof (ZKP) systems, essential for privacy and verifiable computation, suffer from a fundamental limitation: the prover typically uses memory that scales linearly with the computation's trace length T, making them impractical for resource-constrained devices and prohibitively expensive for large-scale tasks. This paper overcomes this barrier by constructing, to our knowledge, the first sublinear-space ZKP prover. Our core contribution is an equivalence that reframes proof generation as an instance of the classic Tree Evaluation problem. Leveraging a recent space-efficient tree-evaluation algorithm, we design a streaming prover that assembles the proof without ever materializing the full execution trace. The approach reduces prover memory from linear in T to O(sqrt(T)) (up to O(log T) lower-order terms) while preserving proof size, verifier time, and the transcript/security guarantees of the underlying system. This enables a shift from specialized, server-bound proving to on-device proving, opening applications in decentralized systems, on-device machine learning, and privacy-preserving technologies.
• Abstract（参考訳）: 現代のゼロ知識証明(ZKP)システムは、プライバシと検証可能な計算に必須であり、基本的な制限に悩まされている。 本稿では、この障壁を、私たちの知る限り、最初のサブ線形空間ZKP証明器を構築することで克服する。 私たちのコアコントリビューションは、古典的なツリー評価問題の例として、証明生成を再構成する等価性です。 近年, 空間効率のよい木評価アルゴリズムを応用して, 完全実行トレースを実現することなく, 証明を組み立てるストリーミング証明器を設計する。 このアプローチは、証明のサイズ、検証時間、基礎システムのトランスクリプト/セキュリティ保証を保ちながら、証明メモリを線形の T から O(sqrt(T)) (O(log T) の下位項まで) に還元する。 これにより、特殊なサーババウンド証明からオンデバイス証明への移行が可能になり、分散システム、オンデバイス機械学習、プライバシ保護テクノロジへのアプリケーションを開放する。

関連論文リスト

• On Immutable Memory Systems for Artificial Agents: A Blockchain-Indexed Automata-Theoretic Framework Using ECDH-Keyed Merkle Chains [0.0]
  本稿では,暗号的に固定された決定論的計算フレームワークであるMerkle Automatonの概念を紹介する。 各エージェントのトランジション、メモリフラグメント、推論ステップは、オンチェーンでルートされたMerkle構造内で実行される。 このアーキテクチャはメモリをキャッシュではなく台帳として再設定する - 内容がプロトコルによって強制され、暗号によって拘束され、形式論理によって制約される。
  論文  参考訳（メタデータ） (2025-06-16T08:43:56Z)
• Log-Augmented Generation: Scaling Test-Time Reasoning with Reusable Computation [80.69067017594709]
  大規模言語モデル(LLM)とそのエージェントモデルは、以前のタスクからの推論を維持するのに苦労する。 本稿では,従来の計算を直接再利用し,テスト時に過去のログから推論する新しいフレームワークであるLAGを提案する。 本手法は,ログを使用しない標準的なエージェントシステムよりも優れている。
  論文  参考訳（メタデータ） (2025-05-20T14:14:38Z)
• Quantifying Memory Utilization with Effective State-Size [73.52115209375343]
  「我々は、テキスト・メモリ利用の尺度を策定する。」 この計量は、textitinput-invariant および textitinput-variant linear operator を持つシステムの基本的なクラスに適合する。
  論文  参考訳（メタデータ） (2025-04-28T08:12:30Z)
• Periodic Online Testing for Sparse Systolic Tensor Arrays [0.0]
  モダン機械学習(ML)アプリケーションは、しばしば構造化されたスパーシティの恩恵を受ける。これは、モデルの複雑さを効率的に低減し、ハードウェア内のスパースデータの処理を単純化するテクニックである。 本稿では,ベクトルの開始前にスパルス・シストリック・テンソルアレイ内の永久断層を検出し,検出するオンラインエラーチェック手法を提案する。
  論文  参考訳（メタデータ） (2025-04-25T18:10:45Z)
• Determinant Estimation under Memory Constraints and Neural Scaling Laws [48.68885778257016]
  メモリ制約設定における大規模対数決定式計算のための新しい階層的アルゴリズムを導出する。 擬似決定詞の比率が法則関係を満たすことを示し、対応するスケーリング法則を導出できるようにする。 これにより、完全なデータセットのごく一部からNTKログ行列式を正確に推定できる。
  論文  参考訳（メタデータ） (2025-03-06T13:32:13Z)
• Cryptanalysis via Machine Learning Based Information Theoretic Metrics [58.96805474751668]
  本稿では,機械学習アルゴリズムの新たな2つの応用法を提案する。 これらのアルゴリズムは、監査設定で容易に適用でき、暗号システムの堅牢性を評価することができる。 本稿では,DES,RSA,AES ECBなど,IND-CPAの安全でない暗号化スキームを高精度に識別する。
  論文  参考訳（メタデータ） (2025-01-25T04:53:36Z)
• Nemesis: Noise-randomized Encryption with Modular Efficiency and Secure Integration in Machine Learning Systems [1.3824176915623292]
  Nemesisは、正確さやセキュリティを損なうことなく、FHEベースの機械学習システムを高速化するフレームワークである。 我々は、標準的な暗号的仮定の下で、Nemesisのセキュリティを証明する。 その結果、NemesisはFHEベースのMLシステムの計算オーバーヘッドを大幅に削減することがわかった。
  論文  参考訳（メタデータ） (2024-12-18T22:52:12Z)
• At Least Factor-of-Two Optimization for RWLE-Based Homomorphic Encryption [0.0]
  ホモモルフィック暗号化(HE)は、復号化を必要とせずに、暗号化データの特定の操作をサポートする。 HEスキームには、データ集約的なワークロードを妨げるような、非自明な計算オーバーヘッドが伴います。 我々は、Zincと呼ぶ暗号化方式を提案し、複数のキャッシュ処理を禁止し、単一のスカラー加算で置き換える。
  論文  参考訳（メタデータ） (2024-08-14T05:42:35Z)
• SZKP: A Scalable Accelerator Architecture for Zero-Knowledge Proofs [10.603449308259496]
  ZKPは検証可能なコンピューティングにおける創発的なパラダイムである。 証明生成における2つの重要なプリミティブは、Number Theoretic Transform(NTT)とMulti-scalar multiplication(MSM)である。 我々は,チップ上での証明全体を高速化する最初のASICであるスケーラブルなアクセラレータフレームワークであるSZKPを提案する。
  論文  参考訳（メタデータ） (2024-08-12T01:53:58Z)
• Topology-aware Embedding Memory for Continual Learning on Expanding Networks [63.35819388164267]
  本稿では,メモリリプレイ技術を用いて,メモリ爆発問題に対処する枠組みを提案する。 Topology-aware Embedding Memory (TEM) を用いたPDGNNは最先端技術よりも優れている。
  論文  参考訳（メタデータ） (2024-01-24T03:03:17Z)
• Large-Scale OD Matrix Estimation with A Deep Learning Method [70.78575952309023]
  提案手法は,ディープラーニングと数値最適化アルゴリズムを統合し,行列構造を推論し,数値最適化を導出する。 大規模合成データセットを用いて,提案手法の優れた一般化性能を実証するために実験を行った。
  論文  参考訳（メタデータ） (2023-10-09T14:30:06Z)
• ReLU and Addition-based Gated RNN [1.484528358552186]
  従来のリカレントゲートの乗算とシグモイド関数を加算とReLUアクティベーションで置き換える。 このメカニズムは、シーケンス処理のための長期メモリを維持するために設計されているが、計算コストは削減されている。
  論文  参考訳（メタデータ） (2023-08-10T15:18:16Z)
• Constant Memory Attention Block [74.38724530521277]
  Constant Memory Attention Block (CMAB) は、新しい汎用アテンションブロックであり、その出力を一定メモリで計算し、一定計算で更新を実行する。 提案手法は,メモリ効率を著しく向上しつつ,最先端技術と競合する結果が得られることを示す。
  論文  参考訳（メタデータ） (2023-06-21T22:41:58Z)
• Improved Branch and Bound for Neural Network Verification via Lagrangian Decomposition [161.09660864941603]
  ニューラルネットワークの入出力特性を公式に証明するためのブランチとバウンド(BaB)アルゴリズムのスケーラビリティを改善します。 活性化に基づく新しい分岐戦略とBaBフレームワークであるブランチとデュアルネットワーク境界(BaDNB)を提案する。 BaDNBは、従来の完全検証システムを大きなマージンで上回り、対数特性で平均検証時間を最大50倍に削減した。
  論文  参考訳（メタデータ） (2021-04-14T09:22:42Z)
• Online Limited Memory Neural-Linear Bandits with Likelihood Matching [53.18698496031658]
  本研究では,探索学習と表現学習の両方が重要な役割を果たす課題を解決するために,ニューラルネットワークの帯域について検討する。 破滅的な忘れ込みに対して耐性があり、完全にオンラインである可能性の高いマッチングアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-02-07T14:19:07Z)
• Dimension reduction in recurrent networks by canonicalization [8.071506311915396]
  本稿では、半無限入力に対応するために、古典的な正準状態空間実現の概念を適用する。 いわゆる入力忘れ特性は、正準実現の存在と一意性(系同型まで)を保証する鍵仮説として同定される。 再生カーネルヒルベルト空間(RKHS)を用いた暗黙還元の概念を導入し、線形リードアウトを持つシステムでは、縮小された空間を計算せずに次元縮小を実現する。
  論文  参考訳（メタデータ） (2020-07-23T17:12:37Z)
• Faster Secure Data Mining via Distributed Homomorphic Encryption [108.77460689459247]
  ホモモルフィック暗号化(HE)は、最近、暗号化されたフィールド上で計算を行う能力により、ますます注目を集めている。 本稿では,スケーリング問題の解決に向けて,新しい分散HEベースのデータマイニングフレームワークを提案する。 各種データマイニングアルゴリズムとベンチマークデータセットを用いて,新しいフレームワークの有効性と有効性を検証する。
  論文  参考訳（メタデータ） (2020-06-17T18:14:30Z)
• Fast Estimation of Information Theoretic Learning Descriptors using Explicit Inner Product Spaces [4.5497405861975935]
  カーネル法は、信号処理や機械学習における非線形問題を解くため、理論的に座屈し、強力で汎用的な枠組みを形成する。 近年, NTカーネル適応フィルタ (KAF) を提案する。 我々は,内部積空間カーネルを用いたIPLの高速,スケーラブル,高精度な推定器群に着目した。
  論文  参考訳（メタデータ） (2020-01-01T20:21:12Z)

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

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