論文の概要: Perfect Zero-Knowledge PCPs for #P
- arxiv url: http://arxiv.org/abs/2403.11941v2
- Date: Tue, 19 Mar 2024 14:17:07 GMT
- ステータス: 処理完了
- システム内更新日: 2024-03-20 19:30:44.377953
- Title: Perfect Zero-Knowledge PCPs for #P
- Title（参考訳）: 完全ゼロ知識PCP for #P
- Authors: Tom Gur, Jack O'Connor, Nicholas Spooner,
- Abstract要約: 完全ゼロ知識確率的証明(PZK-PCP)を#Pのすべての言語に対して構築する。
これは、BPP以外の言語向けのPZK-PCPの最初の構成である。
- 参考スコア（独自算出の注目度）: 5.278573457491116
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We construct perfect zero-knowledge probabilistically checkable proofs (PZK-PCPs) for every language in #P. This is the first construction of a PZK-PCP for any language outside BPP. Furthermore, unlike previous constructions of (statistical) zero-knowledge PCPs, our construction simultaneously achieves non-adaptivity and zero knowledge against arbitrary (adaptive) polynomial-time malicious verifiers. Our construction consists of a novel masked sumcheck PCP, which uses the combinatorial nullstellensatz to obtain antisymmetric structure within the hypercube and randomness outside of it. To prove zero knowledge, we introduce the notion of locally simulatable encodings: randomised encodings in which every local view of the encoding can be efficiently sampled given a local view of the message. We show that the code arising from the sumcheck protocol (the Reed-Muller code augmented with subcube sums) admits a locally simulatable encoding. This reduces the algebraic problem of simulating our masked sumcheck to a combinatorial property of antisymmetric functions.
- Abstract（参考訳）: 完全ゼロ知識確率的証明(PZK-PCP)を#Pのすべての言語に対して構築する。
これは、BPP以外の言語向けのPZK-PCPの最初の構成である。
さらに,従来の(統計的)ゼロ知識PCPとは違って,任意の(適応的な)多項式時間不正な検証に対して,非適応性とゼロ知識を同時に実現している。
我々の構成は、合成ヌルステレンサッツを用いてハイパーキューブ内の非対称構造と、その外側のランダム性を得る新しいマスク付き要約PCPで構成されている。
ゼロ知識を証明するために、メッセージのローカルビューを考慮し、すべてのローカルビューを効率的にサンプリングできるランダム化されたエンコーディングという、局所的なシミュラブルエンコーディングの概念を導入する。
sumcheckプロトコル(subcube sumsを付加したReed-Mullerコード)から生じるコードは、局所的にシミュラブルなエンコーディングが可能であることを示す。
これにより、マスク付き和チェックを非対称関数の組合せ的性質にシミュレートする代数的問題を減らすことができる。
関連論文リスト
- Pseudorandom quantum authentication [0.8204952610951527]
擬似ランダム量子認証方式(PQAS)を導入する。
擬似ランダムユニタリ(PRU)の存在のみに依存する量子状態の効率的な方法である。
論文 参考訳（メタデータ） (2025-01-01T20:46:37Z) - List Decodable Quantum LDPC Codes [49.2205789216734]
我々は、ほぼ最適レート距離のトレードオフを持つ量子低密度パリティチェック(QLDPC)符号の構成を行う。
復号化可能なQLDPCコードとユニークなデコーダを効率よくリストアップする。
論文 参考訳（メタデータ） (2024-11-06T23:08:55Z) - Pseudorandom unitaries with non-adaptive security [43.15464425520681]
本稿では、ランダムなクリフォードユニタリ、擬似乱数二相演算子、擬似乱数置換演算子の結合であるPRU構成を提案する。
このPRU構造は、量子セキュア片方向関数の存在を前提として、非適応微分器に対して安全であることを示す。
論文 参考訳（メタデータ） (2024-02-22T18:56:37Z) - Linear-time Minimum Bayes Risk Decoding with Reference Aggregation [52.1701152610258]
最小ベイズリスク(MBR、Minimum Bayes Risk)は、機械翻訳の品質向上を図ったテキスト生成技術である。
これは2次複雑性を持つ実用計量のペアワイズ計算を必要とする。
本稿では,集約された参照表現に対して計算したスコアを用いて,ペアワイズメトリックスコアを近似する。
論文 参考訳（メタデータ） (2024-02-06T18:59:30Z) - Zero-Shot Detection of Machine-Generated Codes [83.0342513054389]
本研究は,LLMの生成したコードを検出するためのトレーニング不要な手法を提案する。
既存のトレーニングベースまたはゼロショットテキスト検出装置は、コード検出に効果がないことがわかった。
本手法は,リビジョン攻撃に対する堅牢性を示し,Javaコードによく適応する。
論文 参考訳（メタデータ） (2023-10-08T10:08:21Z) - Gaussian conversion protocol for heralded generation of qunaught states [66.81715281131143]
ボソニック符号は、qubit型量子情報をより大きなボソニックヒルベルト空間にマッピングする。
我々は、これらの符号 GKP qunaught 状態の2つのインスタンスと、ゼロ論理エンコードされた量子ビットに対応する4つの対称二項状態とを変換する。
GKPqunaught状態は98%以上、確率は約3.14%である。
論文 参考訳（メタデータ） (2023-01-24T14:17:07Z) - On efficient quantum block encoding of pseudo-differential operators [6.134067544403308]
ブロック符号化は多くの既存の量子アルゴリズムの中核にある。
本稿では, 擬微分演算子 (PDO) を用いた高密度演算子のリッチファミリーのブロック符号化について述べる。
論文 参考訳（メタデータ） (2023-01-21T07:18:57Z) - Neural Belief Propagation Decoding of Quantum LDPC Codes Using
Overcomplete Check Matrices [60.02503434201552]
元のチェック行列における行の線形結合から生成された冗長な行を持つチェック行列に基づいてQLDPC符号を復号する。
このアプローチは、非常に低い復号遅延の利点を付加して、復号性能を著しく向上させる。
論文 参考訳（メタデータ） (2022-12-20T13:41:27Z) - Finding the disjointness of stabilizer codes is NP-complete [77.34726150561087]
我々は、$c-不連続性を計算すること、あるいはそれを定数乗算係数の範囲内で近似することの問題はNP完全であることを示す。
CSSコード、$dコード、ハイパーグラフコードなど、さまざまなコードファミリの相違点に関するバウンダリを提供します。
以上の結果から,一般的な量子誤り訂正符号に対するフォールトトレラント論理ゲートの発見は,計算に難題であることが示唆された。
論文 参考訳（メタデータ） (2021-08-10T15:00:20Z) - Multi-theorem (Malicious) Designated-Verifier NIZK for QMA [4.264192013842096]
マルチセオラムセキュリティを備えたQMAのための非対話型ゼロ知識引数システムを提案する。
我々の技術は古典的だが量子プロトコルに向いており、QMAのための再利用可能なMDV-NIZKの構築を可能にしている。
論文 参考訳（メタデータ） (2020-07-25T13:14:49Z) - Single-Shot Decoding of Linear Rate LDPC Quantum Codes with High
Performance [5.33024001730262]
我々は、線形符号化率、スケーリング距離、効率的な復号方式を用いて、低密度パリティチェック(LDPC)量子コード群を構築し、解析する。
コードファミリーは、Guth と Lubotzky が最初に示唆したように、閉じた4次元の双曲型のテッセルレーションに基づいている。
論文 参考訳（メタデータ） (2020-01-10T17:21:27Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。