論文の概要: Batch, Pack, and Prove: More Efficient Verifiable Computation for CKKS
- arxiv url: http://arxiv.org/abs/2611.16922v1
- Date: Thu, 12 Nov 2026 15:09:44 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-11-14 01:36:33.497023
- Title: Batch, Pack, and Prove: More Efficient Verifiable Computation for CKKS
- Title(参考訳): Batch, Pack, Prove: CKKSのより効率的な検証可能な計算方法
- Abstract要約: ホモモルフィック暗号化(HE)における重要な課題は、計算の計算の整合性を保証することである。
[Cascudo et al. CRYPTO 2025] は、CKKSスキームのこの問題に対する解決策を最近提案した。
重要な進歩にもかかわらず、彼らの仕事は、コミットメント証明のサイズ、レンジ証明における大きなO(N)$オーバーヘッド、効率的なサブ線形暗号文に対する明示的な方法の欠如といった課題に直面している。
- 参考スコア(独自算出の注目度): 6.136858211135927
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: An important challenge in homomorphic encryption (HE) is ensuring the integrity of the encrypted computations. Although verifiable computation can address this in theory, making it practical is far from trivial. [Cascudo et al. CRYPTO 2025] recently proposed a solution to this problem for the CKKS scheme. In particular, they propose new succinct arguments that efficiently prove arithmetic circuits and range checks over the ring $R_q = \mathbb{Z}_q[Y]/(Y^N+1)$, and combine them to prove computations on CKKS ciphertexts. Despite the important progress, their work faces scalability challenges: the size of the polynomial commitment proofs, a large $O(N)$ overhead in range proofs, and the lack of an explicit method for efficient -- sublinear in circuit size -- verification. In this paper we present new techniques that remove all these bottlenecks. First, we provide a more efficient arithmetization of CKKS computations. Second, we introduce BatchFold, a new polynomial commitment for $R_q$ that supports batched evaluations and achieves shorter proofs. Third, we design packing, a novel algebraic technique that eliminates the need to commit to massive polynomials and removes the $O(N)$ overhead in range proofs. Finally, we introduce SparsePack, an efficient protocol for proving the evaluations of sparse, circuit-dependent polynomials, leveraging both packing and batched evaluations. We evaluate the efficiency of our solution on a generic neural network architecture, achieving proofs several orders of magnitude smaller and faster than prior approaches.
- Abstract(参考訳): ホモモルフィック暗号化(HE)における重要な課題は、暗号化された計算の完全性を保証することである。
検証可能な計算は理論上はこの問題に対処できるが、現実的なものにはほど遠い。
[Cascudo et al CRYPTO 2025] は、CKKSスキームのこの問題に対する解決策を最近提案した。
特に、彼らは算術回路とレンジチェックを環$R_q = \mathbb{Z}_q[Y]/(Y^N+1)$上で効率的に証明する新しい簡潔な引数を提案し、それらを組み合わせてCKKS暗号文上での計算を証明した。
重要な進歩にもかかわらず、それらの作業はスケーラビリティの課題に直面している。多項式のコミットメント証明のサイズ、レンジ証明における大きなO(N)$オーバーヘッド、そして回路サイズがサブリニアで効率的な明示的な方法が欠如している。
本稿では,これらのボトルネックを取り除く新しい手法を提案する。
まず、CKKS計算のより効率的なアリスメトリゼーションを提案する。
次にBatchFoldを紹介します。これは、バッチ評価をサポートし、より短い証明を実現する、$R_q$に対する新しい多項式コミットメントです。
第3に、我々は、巨大な多項式にコミットする必要をなくし、レンジ証明の$O(N)$オーバーヘッドを取り除く新しい代数的テクニックであるパッキングを設計する。
最後に、スパース・回路依存多項式の評価を効率よく証明するためのプロトコルであるSparsePackを紹介し、パッキングとバッチ評価の両方を活用する。
我々は、汎用ニューラルネットワークアーキテクチャ上でのソリューションの効率を評価し、従来のアプローチよりも数桁小さく高速な証明を達成した。
関連論文リスト
- Differential Privacy Meets Fixed Parameter Tractability: Algorithms and Lower Bounds [40.593115580783156]
我々は、$$-differential privacy($-DP)の制約の下で最適化問題を研究する。
Gupta et al の暗黙表現フレームワークを一般化する。
我々は、$-DPエンコーダとデコーダのペアが、デコーダがサブ指数時間で動作する場合、一定の近似保証を達成できないことを証明した。
論文 参考訳(メタデータ) (2026-09-11T07:13:24Z) - Pseudo-MDPs: A Novel Framework for Efficiently Optimizing Last Revealer Seed Manipulations in Blockchains [0.0]
本研究では,マルコフ決定過程(MDP)を限定クラスで解く際の計算課題に取り組む。
これはLast Revealer Attack (LRA)によって動機付けられ、資本化(B Market)のようなPoS(Proof-of-Stake)ブロックチェーンの公平性を損なう。
疑似MDP(pMDP)は,このような問題を自然にモデル化し,標準的なMDPに2つの異なる問題を還元するフレームワークである。
論文 参考訳(メタデータ) (2025-10-08T14:39:20Z) - Bootstrapping as a Morphism: An Arithmetic Geometry Approach to Asymptotically Faster Homomorphic Encryption [0.9179857807576733]
本稿では,従来の回路評価モデルを完全にバイパスするブートストラップ手法を提案する。
直射射影としてブートストラップ操作を再構成するために,現代の算術幾何学のツールを適用した。
我々の研究は、$O(d cdot textpoly(log q))$、$d$が環次元、$q$が暗号文である完全かつ確実に正しいブートストラップアルゴリズムである。
論文 参考訳(メタデータ) (2025-09-29T03:39:01Z) - Arbitrary-Threshold Fully Homomorphic Encryption with Lower Complexity [8.228450733641122]
我々はtextitapproximate secret sharing (ApproxSS) と呼ばれる新しいプリミティブを開発する。
任意閾値(ATh)-ApproxSS特性上におけるAThFHEの正当性と安全性を実証する。
ATASSESは3.83タイム= -- 15.4タイム=ベースライン以上のスピードアップを実現している。
論文 参考訳(メタデータ) (2025-01-20T02:46:08Z) - DCC: Differentiable Cardinality Constraints for Partial Index Tracking [3.429982727480958]
インデックス追跡はポートフォリオの最適化を目的とした受動的投資戦略として人気があるが、インデックスの複製は高い取引コストにつながる可能性がある。
本稿では,索引追跡のための可変濃度制約を提案し,浮動小数点精度認識手法を提案する。
論文 参考訳(メタデータ) (2024-12-22T22:05:56Z) - Perturb-and-Project: Differentially Private Similarities and Marginals [73.98880839337873]
差分プライバシーのための入力摂動フレームワークを再検討し、入力にノイズを付加する。
まず、ペアワイズ・コサイン類似性をプライベートにリリースするための新しい効率的なアルゴリズムを設計する。
我々は,$k$の辺縁クエリを$n$の機能に対して計算する新しいアルゴリズムを導出する。
論文 参考訳(メタデータ) (2024-06-07T12:07:16Z) - Efficiently Learning One-Hidden-Layer ReLU Networks via Schur
Polynomials [50.90125395570797]
正方形損失に関して、標準的なガウス分布の下での$k$ReLU活性化の線形結合をPAC学習する問題をmathbbRd$で検討する。
本研究の主な成果は,この学習課題に対して,サンプルおよび計算複雑性が$(dk/epsilon)O(k)$で,epsilon>0$が目標精度である。
論文 参考訳(メタデータ) (2023-07-24T14:37:22Z) - Nonconvex Zeroth-Order Stochastic ADMM Methods with Lower Function Query
Complexity [109.54166127479093]
ゼロ次法(ゼロ次法、英: Zeroth-order method)は、機械学習問題を解決するための効果的な最適化手法のクラスである。
本稿では,非有限項問題を解くために,より高速なゼロ階交互勾配法乗算器 (MMADMM) を提案する。
我々は、ZOMMAD法が、$epsilon$-stationary pointを見つけるために、より低い関数$O(frac13nfrac1)$を達成することができることを示す。
同時に、より高速なゼロオーダーオンラインADM手法(M)を提案する。
論文 参考訳(メタデータ) (2019-07-30T02:21:43Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。