論文の概要: AC4: Algebraic Computation Checker for Circuit Constraints in ZKPs
- arxiv url: http://arxiv.org/abs/2403.15676v3
- Date: Tue, 7 May 2024 04:29:29 GMT
- ステータス: 処理完了
- システム内更新日: 2024-05-08 19:13:23.598537
- Title: AC4: Algebraic Computation Checker for Circuit Constraints in ZKPs
- Title(参考訳): AC4:ZKPの回路制約に対する代数計算チェッカ
- Authors: Hao Chen, Minyu Chen, Ruibang Liu, Guoqiang Li, Sinka Gao,
- Abstract要約: 本稿では,ZKP回路の2種類のバグをピンポイントする手法を提案する。
本稿では,この手法の実装を表現するためのツールAC4を提案する。
可溶範囲内では、AC4のチェック時間も顕著に改善されている。
- 参考スコア(独自算出の注目度): 4.810904298160318
- License: http://creativecommons.org/publicdomain/zero/1.0/
- Abstract: ZKP systems have surged attention and held a fundamental role in contemporary cryptography. Zk-SNARK protocols dominate the ZKP usage, often implemented through arithmetic circuit programming paradigm. However, underconstrained or overconstrained circuits may lead to bugs. Underconstrained circuits refer to circuits that lack the necessary constraints, resulting in unexpected solutions in the circuit and causing the verifier to accept a bogus witness. Overconstrained circuits refer to circuits that are constrained excessively, resulting in the circuit lacking necessary solutions and causing the verifier to accept no witness, rendering the circuit meaningless. 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 polynomial equation systems over a finite field by algebraic computation. The classification of verification results is refined, greatly enhancing the expressive power of the system. We proposed a tool, AC4, to represent the implementation of this method. Experiments demonstrate that AC4 represents a substantial 29% increase in the checked ratio compared to prior work. Within a solvable range, the checking time of AC4 has also exhibited noticeable improvement, demonstrating a magnitude increase compared to previous efforts.
- Abstract(参考訳): ZKPシステムは注目され、現代の暗号において基本的な役割を担っている。
Zk-SNARKプロトコルはZKPの利用を支配し、しばしば演算回路プログラミングのパラダイムによって実装される。
しかし、過度に制約された回路や過度に制約された回路はバグを引き起こす可能性がある。
制約の少ない回路は、必要な制約を欠いた回路を指し、結果として回路の予期せぬ解が生まれ、検証者が悪質な証人を受け入れる。
過制約回路は過度に制約された回路を指し、結果として回路は必要な解決策が欠如し、検証者が証人を受け入れることなく回路を無意味にする。
本稿では,ZKP回路の2種類のバグをピンポイントする手法を提案する。
この方法では、算術回路の制約を多項式方程式系に符号化し、代数計算により有限体上の多項式方程式系を解く。
検証結果の分類が洗練され、システムの表現力が大幅に向上する。
我々は,この手法の実装を表現するためのツールAC4を提案した。
実験の結果、AC4は前回の作業に比べてチェック比が29%大きく向上していることがわかった。
可溶範囲内では、AC4のチェックタイムも顕著に改善され、以前の取り組みに比べて大幅に向上した。
関連論文リスト
- 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。