論文の概要: AC4: Algebraic Computation Checker for Circuit Constraints in ZKPs
- arxiv url: http://arxiv.org/abs/2403.15676v4
- Date: Thu, 26 Sep 2024 12:18:21 GMT
- ステータス: 処理完了
- システム内更新日: 2024-11-09 03:48:22.293618
- Title: AC4: Algebraic Computation Checker for Circuit Constraints in ZKPs
- Title（参考訳）: AC4:ZKPの回路制約に対する代数計算チェッカ
- Authors: Hao Chen, Guoqiang Li, Minyu Chen, Ruibang Liu, Sinka Gao,
- Abstract要約: 過度に制約された回路や過度に制約された回路はバグを引き起こす可能性がある。
提案手法の実装を表すためにAC4というツールが提案されている。
解決可能な範囲内では、チェック時間も顕著に改善されている。
- 参考スコア（独自算出の注目度）: 4.810904298160317
- License: http://creativecommons.org/publicdomain/zero/1.0/
- Abstract: Zero-knowledge proof (ZKP) systems have surged attention and held a fundamental role in contemporary cryptography. Zero-knowledge succinct non-interactive argument of knowledge (zk-SNARK) protocols dominate the ZKP usage, implemented through arithmetic circuit programming paradigm. However, underconstrained or overconstrained circuits may lead to bugs. The former refers to circuits that lack the necessary constraints, resulting in unexpected solutions and causing the verifier to accept a bogus witness, and the latter refers to circuits that are constrained excessively, resulting in lacking necessary solutions and causing the verifier to accept no witness. This paper introduces a novel approach for pinpointing two distinct types of bugs in ZKP circuits. The method involves encoding the arithmetic circuit constraints to polynomial equation systems and solving them over finite fields by the computer algebra system. The classification of verification results is refined, greatly enhancing the expressive power of the system. A tool, AC4, is proposed to represent the implementation of the method. Experiments show that AC4 demonstrates a increase in the checked ratio, showing a 29% improvement over Picus, a checker for Circom circuits, and a 10% improvement over halo2-analyzer, a checker for halo2 circuits. Within a solvable range, the checking time has also exhibited noticeable improvement, demonstrating a magnitude increase compared to previous efforts.
- Abstract（参考訳）: ゼロ知識証明(ZKP)システムは注目され、現代暗号において基本的な役割を担っている。
Zero-knowledge succinct non-interactive argument of knowledge (zk-SNARK)プロトコルは、算術回路プログラミングパラダイムによって実装されたZKPの使用を支配している。
しかし、過度に制約された回路や過度に制約された回路はバグを引き起こす可能性がある。
前者は、必要な制約を欠いた回路を指し、予期せぬ解を生じさせ、検証者が悪質な証人を受け入れ、後者は過度に制約された回路を指し、その結果、必要な解が欠如し、検証者が証人を受け入れない。
本稿では,ZKP回路の2種類のバグをピンポイントする手法を提案する。
この方法では、算術回路の制約を多項式方程式系に符号化し、計算機代数系によって有限体上で解く。
検証結果の分類が洗練され、システムの表現力が大幅に向上する。
提案手法の実装を表すためにAC4というツールが提案されている。
実験の結果、AC4はチェック比の増加を示し、Picusよりも29%改善し、Circom回路はチェッカー、Halo2回路は10%改善した。
解決可能な範囲内では、チェックタイムも顕著に改善され、以前の取り組みに比べて大幅に向上した。
関連論文リスト
- Quantum Error Mitigation via Linear-Depth Verifier Circuits [0.044998333629984864]
低次元行列積演算子(MPO)によって正確に表現される量子回路の検証回路を構築する方法を提案する。
回路を2次元の量子ビット配列にトランスパイルすることにより、検証回路が回路自体よりも浅いクロスオーバー点を推定し、量子エラー軽減(QEM)に有用である。
提案手法は、コヒーレントノイズに対処するために量子サブ回路の校正に有用であるが、現在のデバイスに存在する非コヒーレントノイズを補正することができない。
論文 参考訳（メタデータ） (2024-11-05T16:44:18Z) - Enhancing Quantum Memory Lifetime with Measurement-Free Local Error Correction and Reinforcement Learning [1.0446041735532203]
本稿では,$textitlocal$エラー情報に基づく,計測不要な回路レベルのエラー訂正プロトコルについて検討する。
これらの回路は,2次元トーリック符号メモリを保存するために,中間回路の読み出し速度を低減できることを示す。
論文 参考訳（メタデータ） (2024-08-18T16:18:21Z) - On the Constant Depth Implementation of Pauli Exponentials [49.48516314472825]
任意の指数を$mathcalO(n)$ ancillae と 2体 XX と ZZ の相互作用を用いて一定深さの回路に分解する。
クビットリサイクルの恩恵を受ける回路の書き直し規則を導入し,本手法の正しさを実証する。
論文 参考訳（メタデータ） (2024-08-15T17:09:08Z) - Quantum Circuit Tensors and Enumerators with Applications to Quantum Fault Tolerance [0.0]
本稿では,安定化符号に対するポアソン公式の類似式を導入し,誤り経路の数を正確に計算する手法を提案する。
回路列挙器は, チャネルのプロセス行列と関連していることを示す。
論文 参考訳（メタデータ） (2024-05-30T02:53:11Z) - Bit-flipping Decoder Failure Rate Estimation for (v,w)-regular Codes [84.0257274213152]
並列ビットフリップデコーダのDFRを高精度に推定する手法を提案する。
本研究は,本症候群のモデル化およびシミュレーションによる重み比較,第1イテレーション終了時の誤りビット分布の誤検出,復号化復号化率(DFR)について検証した。
論文 参考訳（メタデータ） (2024-01-30T11:40:24Z) - Fault-tolerant quantum architectures based on erasure qubits [49.227671756557946]
我々は、支配的なノイズを既知の場所での消去に効率よく変換することで、消去量子ビットの考え方を利用する。
消去量子ビットと最近導入されたFloquet符号に基づくQECスキームの提案と最適化を行う。
以上の結果から, 消去量子ビットに基づくQECスキームは, より複雑であるにもかかわらず, 標準手法よりも著しく優れていることが示された。
論文 参考訳（メタデータ） (2023-12-21T17:40:18Z) - Formal Verification of Zero-Knowledge Circuits [44.99833362998488]
ゼロ知識回路は素体で解釈された算術式に対する等式制約の集合である。
我々は、回路が正しく計算を符号化することを確実にする問題に貢献する。
論文 参考訳（メタデータ） (2023-11-15T10:47:28Z) - Adaptive Planning Search Algorithm for Analog Circuit Verification [53.97809573610992]
シミュレーションの少ない機械学習(ML)アプローチを提案する。
提案手法により,OCCを全回路の仕様に近づけることができることを示す。
論文 参考訳（メタデータ） (2023-06-23T12:57:46Z) - Quantum Error Mitigation by Pauli Check Sandwiching [4.419800664096479]
複数対のパリティチェックを用いて誤りの有無を検知する誤差軽減手法を記述・解析する。
私たちは、拡張フラグガジェットの成果の上に構築し、しっかりとした理論的基礎の上に置きます。
論文 参考訳（メタデータ） (2022-06-01T03:48:50Z) - Software mitigation of coherent two-qubit gate errors [55.878249096379804]
2量子ゲートは量子コンピューティングの重要な構成要素である。
しかし、量子ビット間の不要な相互作用(いわゆる寄生ゲート)は、量子アプリケーションの性能を低下させる。
寄生性2ビットゲート誤差を軽減するための2つのソフトウェア手法を提案する。
論文 参考訳（メタデータ） (2021-11-08T17:37:27Z) - Efficient and robust certification of genuine multipartite entanglement
in noisy quantum error correction circuits [58.720142291102135]
実効多部絡み(GME)認証のための条件付き目撃手法を導入する。
線形な二分割数における絡み合いの検出は, 多数の測定値によって線形にスケールし, GMEの認証に十分であることを示す。
本手法は, 距離3の位相的カラーコードとフラグベースの耐故障バージョンにおける安定化作用素の雑音可読化に適用する。
論文 参考訳（メタデータ） (2020-10-06T18:00:07Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。