論文の概要: 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-09-28 01:51:33.554937
- 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:
- 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 Circuit Tensors and Enumerators with Applications to Quantum Fault Tolerance [0.0]
本稿では,安定化符号に対するポアソン公式の類似式を導入し,誤り経路の数を正確に計算する手法を提案する。
回路列挙器は, チャネルのプロセス行列と関連していることを示す。
論文 参考訳(メタデータ) (2024-05-30T02:53:11Z) - Multi-qubit Lattice Surgery Scheduling [3.7126786554865774]
量子回路は、唯一の非クリフォード多ビットゲートの列に変換できる。
本研究では, トランスパイレーションにより, テストした回路の回路長が大幅に減少することを示す。
結果として生じるマルチキュービットゲート回路は、シリアル実行よりも期待される回路実行時間を短縮する。
論文 参考訳(メタデータ) (2024-05-27T22:41:41Z) - 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) - On the realistic worst case analysis of quantum arithmetic circuits [69.43216268165402]
量子回路の設計における直観は誤解を招く可能性があることを示す。
また,T数を減らすことで,全深度を増大させることができることを示した。
リップルキャリーを用いた加算回路と乗算回路について述べる。
論文 参考訳(メタデータ) (2021-01-12T21:36:16Z) - Machine Learning Optimization of Quantum Circuit Layouts [63.55764634492974]
本稿では量子回路マッピングQXXとその機械学習バージョンQXX-MLPを紹介する。
後者は、レイアウトされた回路の深さが小さくなるように最適なQXXパラメータ値を自動的に推論する。
近似を用いてレイアウト法を学習可能な経験的証拠を提示する。
論文 参考訳(メタデータ) (2020-07-29T05:26:19Z) - Hardware-Encoding Grid States in a Non-Reciprocal Superconducting
Circuit [62.997667081978825]
本稿では、非相互デバイスと、基底空間が2倍縮退し、基底状態がGottesman-Kitaev-Preskill(GKP)符号の近似符号であるジョセフソン接合からなる回路設計について述べる。
この回路は、電荷やフラックスノイズなどの超伝導回路の一般的なノイズチャネルに対して自然に保護されており、受動的量子誤差補正に使用できることを示唆している。
論文 参考訳(メタデータ) (2020-02-18T16:45:09Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。