論文の概要: Distributed Non-Interactive Zero-Knowledge Proofs

• arxiv url: http://arxiv.org/abs/2502.07594v1
• Date: Tue, 11 Feb 2025 14:44:51 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-02-12 14:05:31.645125
• Title: Distributed Non-Interactive Zero-Knowledge Proofs
• Title（参考訳）: 分散非インタラクティブゼロ知識証明
• Authors: Alex B. Grilo, Ami Paz, Mor Perry,
• Abstract要約: 分散非相互作用ゼロ知識証明(dNIZK)について検討する。 証明器からのO(log n)ビットメッセージと近隣のO(log n)サイズメッセージで3色化するためのdNIZKプロトコルが存在する。 三角形自由度のためのdNIZKプロトコルのファミリがあり、証明者からのメッセージのサイズと隣人の間でのメッセージサイズの間のトレードオフを示す。
• 参考スコア（独自算出の注目度）: 1.360022695699485
• License:
• Abstract: Distributed certification is a set of mechanisms that allows an all-knowing prover to convince the units of a communication network that the network's state has some desired property, such as being 3-colorable or triangle-free. Classical mechanisms, such as proof labeling schemes (PLS), consist of a message from the prover to each unit, followed by one round of communication between each unit and its neighbors. Later works consider extensions, called distributed interactive proofs, where the prover and the units can have multiple rounds of communication before the communication among the units. Recently, Bick, Kol, and Oshman (SODA '22) defined a zero-knowledge version of distributed interactive proofs, where the prover convinces the units of the network's state without revealing any other information about the network's state or structure. In their work, they propose different variants of this model and show that many graph properties of interest can be certified with them. In this work, we define and study distributed non-interactive zero-knowledge proofs (dNIZK); these can be seen as a non-interactive version of the aforementioned model, and also as a zero-knowledge version of PLS. We prove the following: - There exists a dNIZK protocol for 3-coloring with O(log n)-bit messages from the prover and O(log n)-size messages among neighbors. - There exists a family of dNIZK protocols for triangle-freeness, that presents a trade-off between the size of the messages from the prover and the size of the messages among neighbors. - There exists a dNIZK protocol for any graph property in NP in the random oracle models, which is secure against an arbitrary number of malicious parties.
• Abstract（参考訳）: 分散認証は、全ての知識を持つ証明者が、ネットワークの状態が3色や三角形のないような望ましい性質を持っていることを、通信ネットワークのユニットを納得させるメカニズムである。 証明ラベリングスキーム(PLS)のような古典的なメカニズムは、証明者から各ユニットへのメッセージで構成され、続いて各ユニットとその隣人の間で1ラウンドの通信が行われる。 その後の研究では、分散対話的証明と呼ばれる拡張を考慮し、証明者とユニットは、ユニット間の通信の前に複数のラウンドの通信を行うことができる。 近年、Bick, Kol, and Oshman (SODA '22) は分散対話型証明のゼロ知識バージョンを定義している。 彼らの研究で、彼らはこのモデルの異なる変種を提案し、興味のあるグラフの性質の多くを証明できることを示す。 本研究では,分散非対話型ゼロ知識証明 (dNIZK) の定義と研究を行い,上記のモデルの非対話型版,PLSのゼロ知識版とみなすことができる。 証明する: - 証明者からのO(log n)ビットメッセージと隣人の間でO(log n)サイズのメッセージで3色化するためのdNIZKプロトコルが存在する。 -三角形自由度のためのdNIZKプロトコルのファミリが存在し、証明者からのメッセージのサイズと隣人の間でのメッセージサイズの間のトレードオフを提示する。 -無作為なオラクルモデルにおいて、NP内のグラフプロパティに対してdNIZKプロトコルが存在し、これは任意の数の悪意のあるパーティに対して安全である。

関連論文リスト

• Networks of Networks: Complexity Class Principles Applied to Compound AI Systems Design [63.24275274981911]
  多くの言語モデル推論コールからなる複合AIシステムは、ますます採用されている。 本研究では,提案した回答の生成と正当性検証の区別を中心に,ネットワークネットワーク(NoN)と呼ばれるシステムを構築した。 我々は,Kジェネレータを備えた検証器ベースの判定器NoNを導入し,"Best-of-K"あるいは"judge-based"複合AIシステムのインスタンス化を行う。
  論文  参考訳（メタデータ） (2024-07-23T20:40:37Z)
• Entropy Accumulation under Post-Quantum Cryptographic Assumptions [4.416484585765028]
  デバイス非依存(DI)量子プロトコルでは、セキュリティステートメントは量子装置の特性を損なう。 本稿では,量子情報理論のツールの組み合わせを利用して,そのようなプロトコルの安全性を証明するフレキシブルなフレームワークを提案する。
  論文  参考訳（メタデータ） (2023-07-02T12:52:54Z)
• A non-sequential hierarchy of message-passing models [0.0]
  本稿では,大規模モデルと局所モデルの両方を含む通信モデルの統一階層について述べる。 私たちが考慮しているすべての通信モデルは、モナディック二階述語論理において公理化することができる。
  論文  参考訳（メタデータ） (2022-10-24T09:31:25Z)
• QuTE: decentralized multiple testing on sensor networks with false discovery rate control [130.7122910646076]
  本稿では、偽発見率(FDR)の証明可能な保証を備えたグラフ上での分散多重仮説検定法を設計する。 異なるエージェントが無向グラフのノードに存在し、各エージェントはそのノードに局所的な1つ以上の仮説に対応するp値を持つ。 各エージェントは、グラフ全体の大域的FDRが予め定義されたレベルで制御されなければならないという共同目的のもと、隣人とのみ通信することで、それぞれのローカル仮説の1つ以上の拒絶を個別に決めなければならない。
  論文  参考訳（メタデータ） (2022-10-09T19:48:39Z)
• Distributed Quantum Interactive Proofs [0.5156484100374058]
  分散対話型証明では、$n$ノードネットワーク$G$のノードは、短いメッセージ(証明書と呼ばれる)を強力な証明器で交換することができる。 目標は、入力($G$自身を含む)が何らかの言語に属しているかどうかを判断し、対話のターンがほとんどなく、ノードと証明者の間でできる限りビットを交換することである。 証明は量子ビットとなり、ネットワークのノードは量子計算を行うことができる。
  論文  参考訳（メタデータ） (2022-10-04T05:38:31Z)
• Towards Semantic Communication Protocols: A Probabilistic Logic Perspective [69.68769942563812]
  我々は,NPMを確率論理型言語ProbLogで記述された解釈可能なシンボルグラフに変換することによって構築された意味プロトコルモデル(SPM)を提案する。 その解釈性とメモリ効率を利用して、衝突回避のためのSPM再構成などのいくつかの応用を実演する。
  論文  参考訳（メタデータ） (2022-07-08T14:19:36Z)
• Vehicle: Interfacing Neural Network Verifiers with Interactive Theorem Provers [1.5749416770494706]
  車両には、ニューラルネットワーク仕様を記述するための表現力のあるドメイン固有言語が備わっている。 同様のITPの形式化において、保守性とスケーラビリティに関する過去の問題を克服しています。 ニューラルネットワーク検証器であるMarabouをAgdaに接続し、ニューラルネットワークで操縦された車が道路を離れないことを正式に検証することで、その実用性を実証する。
  論文  参考訳（メタデータ） (2022-02-10T18:09:23Z)
• A Correspondence Variational Autoencoder for Unsupervised Acoustic Word Embeddings [50.524054820564395]
  そこで本稿では,変数分割音声セグメントを固定次元表現にマッピングするための教師なしモデルを提案する。 結果として得られる音響単語の埋め込みは、低リソース言語とゼロリソース言語のための検索、発見、インデックスシステムの基礎を形成することができる。
  論文  参考訳（メタデータ） (2020-12-03T19:24:42Z)
• Tractable Inference in Credal Sentential Decision Diagrams [116.6516175350871]
  確率感性決定図は、解離ゲートの入力が確率値によってアノテートされる論理回路である。 我々は、局所確率を質量関数のクレーダル集合に置き換えることができる確率の一般化である、クレーダル感性決定図を開発する。 まず,ノイズの多い7セグメント表示画像に基づく簡単なアプリケーションについて検討する。
  論文  参考訳（メタデータ） (2020-08-19T16:04:34Z)
• CSNE: Conditional Signed Network Embedding [77.54225346953069]
  署名されたネットワークは、友人/フォアや信頼/不信のようなエンティティ間の正と負の関係を符号化する。 サイン予測のための既存の埋め込み手法は、一般に最適化関数におけるステータスやバランス理論の異なる概念を強制する。 条件付き符号付きネットワーク埋め込み(CSNE)を導入する。 我々の確率論的アプローチは、きめ細かな詳細とは別途、ネットワーク内の記号に関する構造情報をモデル化する。
  論文  参考訳（メタデータ） (2020-05-19T19:14:52Z)

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

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