2025-11-16T14:22:13.039505

MPCitH-based Signatures from Restricted Decoding Problems

Battagliola, Bitzer, Wachter-Zeh et al.
Threshold-Computation-in-the-Head (TCitH) and VOLE-in-the-Head (VOLEitH), two recent developments of the MPC-in-the-Head (MPCitH) paradigm, have significantly improved the performance of digital signature schemes in this framework. In this note, we embed the restricted decoding problem within these frameworks. We propose a structurally simple modeling that achieves competitive signature sizes. Specifically, by instantiating the restricted decoding problem with the same hardness assumption underlying CROSS, we reduce sizes by more than a factor of two compared to the NIST submission. Moreover, we observe that ternary full-weight decoding, closely related to the hardness assumption underlying WAVE, is a restricted decoding problem. Using ternary full-weight decoding, we obtain signature sizes comparable to the smallest MPCitH-based candidates in the NIST competition.
academic

制限付き復号問題に基づくMPCitH署名

基本情報

  • 論文ID: 2510.11224
  • タイトル: MPCitH-based Signatures from Restricted Decoding Problems
  • 著者: Michele Battagliola (マルケ工科大学)、Sebastian Bitzer、Antonia Wachter-Zeh、Violetta Weger (ミュンヘン工科大学)
  • 分類: cs.CR (暗号とセキュリティ)、cs.IT (情報理論)、math.IT (情報理論)
  • 発表日: 2025年10月13日 (arXiv プレプリント)
  • 論文リンク: https://arxiv.org/abs/2510.11224

要旨

本論文は、制限付き復号問題(E-SDP)をThreshold-Computation-in-the-Head (TCitH)およびVOLE-in-the-Head (VOLEitH)フレームワークに組み込んでいます。これらは MPC-in-the-Head (MPCitH)パラダイムの最新の発展であり、デジタル署名方式の性能を大幅に改善しています。著者らは構造が単純なモデリング手法を提案し、競争力のある署名サイズを実現しました。CROSSと同じ困難性仮定を用いてE-SDPをインスタンス化することで、NIST提出版と比較して署名サイズを2倍以上削減しました。さらに、三元全重み復号がWAVEの基礎となる困難性仮定と密接に関連していることを発見し、この手法により得られた署名サイズはNIST競技における最小のMPCitH候補方式と同等です。

研究背景と動機

問題背景

  1. 耐量子暗号標準化の必要性: NISTはCRYSTALS-Dilithium、FALCON、SPHINCS+の標準化後、2022年9月に追加のデジタル署名方式の募集を開始し、耐量子署名標準の多様化を目指しています。
  2. MPCitHパラダイムの発展: 2007年のIshai等による提案以来、MPCitH技術は耐量子デジタル署名の状況を一変させました。TCitHおよびVOLEitHはMPCitHの最新の特殊化であり、従来の構成と比較して顕著な性能改善を提供しています。
  3. 暗号学における符号理論の応用: 符号理論に基づく困難問題(ハミング距離計量および秩計量復号問題など)は、効率的な耐量子署名の構築のための理論的基礎を提供しています。

研究動機

  1. 性能最適化の必要性: 既存のCROSS署名方式は制限付き復号問題に基づいていますが、比較的単純なCVEプロトコルを使用しており、署名サイズの最適化の余地があります。
  2. フレームワークの統一: 制限付き復号問題を先進的なTCitH/VOLEitHフレームワークに統一し、これらのフレームワークの性能上の利点を最大限に活用します。
  3. 競争力の向上: セキュリティを維持しながら署名サイズを大幅に削減し、NIST競技における競争力を高めます。

核心的貢献

  1. E-SDPの多項式モデリング手法の提案: 制限付き症候群復号問題をTCitHおよびVOLEitHフレームワークに組み込むための、構造が単純で効果的な多項式関係を設計しました。
  2. CROSS型署名サイズの大幅削減: 同じ復号問題に対して、NIST提出のCROSS方式と比較して署名サイズを50%以上削減しました(12.4kBから5.5kBへ)。
  3. 三元全重み復号の応用可能性の発見: WAVE関連の三元全重み復号が制限付き復号問題であることを証明し、最小のMPCitH候補方式と同等の署名サイズ(3.1kB)を実現しました。
  4. 完全なパラメータ化方式の提供: NIST安全レベル1、3、5に対する具体的なパラメータ選択と性能分析を提供しました。

方法の詳細

タスク定義

研究目標は、制限付き症候群復号問題(E-SDP)を多項式関係として表現し、TCitHおよびVOLEitHフレームワークでデジタル署名方式を構築できるようにすることです。

E-SDP定義: 制限集合 E ⊂ F、検査行列 H ∈ F^(r×n)、症候群 s ∈ F^r が与えられたとき、eH^T = s を満たす e ∈ E^n を見つけます。

コア・モデリング手法

1. 多項式制約の構成

システム形式の検査行列 H = (A, I_r) に対して、ここで A ∈ F^(r×k)、I_r は単位行列です:

  • 証人ベクトル: w ∈ F^k (部分誤り ベクトル)
  • 拡張誤りベクトル: e = (w, s - wA^T)
  • 制限多項式: f_E(x) = ∏_{e∈E}(x - e)

多項式関係システム:

F(x) = (f_1, ..., f_n) ∈ F[x_1, ..., x_k]^n

ここで:

  • f_i(x) = f_E(x_i) for i ∈ k
  • f_{k+i}(x) = f_E(s_i - ⟨a_i, x⟩) for i ∈ r

2. 次数分析

命題1: この多項式関係は z = |E| の次数でE-SDPのモデリングを提供します。w ∈ F^k が F(w) = 0 を満たす場合、誤りベクトル e = (w, s - wA^T) はE-SDPインスタンス(H, s)を解きます。

具体的なインスタンス化

CROSS-SDP

  • 制限集合: E = {2^i | i ∈ 7} ⊆ F_{127}
  • パラメータ: |E| = 7, p = 127
  • セキュリティ: 7,15の詳細分析に基づく

Ternary-SDP

  • 制限集合: E = {1, 2} ⊆ F_3
  • パラメータ: |E| = 2, p = 3
  • 複雑性: O(2^{0.247·n}) 操作(多項式因子内)

実験設定

パラメータ選択戦略

セキュリティ要件と性能最適化目標に基づいて、以下の主要パラメータを選択します:

  1. TCitHフレームワークパラメータ:
    • τ: 並列繰り返し回数
    • N: 評価域サイズ
    • μ: 拡大体の次数 K : F
    • η: バッチ処理パラメータ
  2. VOLEitHフレームワークパラメータ:
    • ρ: 拡大体パラメータ
    • B: 一貫性チェックパラメータ
    • T_open: VC方式パラメータ

セキュリティ制約

以下のセキュリティ要件を満たします:

  • TCitH: N ≤ p^μ, p^{μ·η} ≥ 2^λ, (N/d)^τ ≥ 2^{λ-w}
  • VOLEitH: N^τ/d ≥ 2^{λ-w}, p^ρ ≥ 2^λ

評価指標

主に署名サイズを評価し、3つの構成要素を含みます:

  • |σ_sym|: VC方式関連
  • |σ_w|: 証人関連
  • |σ_F|: OWF関連

実験結果

主要な結果

TCitHフレームワークの性能

セキュリティレベルE-SDP型|F||E|nkτNμη署名サイズ(B)
NIST 1CROSS-SDP1277127761520482105,533
NIST 1Ternary-SDP325792131220487123,095
NIST 3CROSS-SDP127718711123204821412,354
NIST 3Ternary-SDP328393091820487186,860

VOLEitHフレームワークの性能

セキュリティレベルE-SDP型署名サイズ(B)TCitH比改善
NIST 1CROSS-SDP4,372~21%
NIST 1Ternary-SDP2,974~4%
NIST 3CROSS-SDP9,361~24%
NIST 3Ternary-SDP6,463~6%

NIST候補方式との比較

方式困難性仮定設計原理署名サイズ(kB)
本研究(CROSS-SDP)制限付き復号VOLEitH4.4
本研究(Ternary-SDP)制限付き復号TCitH3.1
CROSSCROSS-E-SDPCVE12.4
SDitH症候群復号VOLEitH3.7
MQOM多変数二次TCitH2.8
PERK置換核問題VOLEitH3.5

主要な発見

  1. 顕著なサイズ削減: CROSS-SDPは元のCROSSと比較して署名サイズを64.5%削減
  2. フレームワーク選択の影響: 高次数問題に対して、VOLEitHはTCitHより有利
  3. 競争力: Ternary-SDPは最良のMPCitH候補方式と同等の性能を達成

関連研究

MPCitHパラダイムの発展

  1. オリジナルMPCitH 23: 2007年提案、安全多者計算とFiat-Shamir変換の結合
  2. TCitHフレームワーク 21: ℓ-out-of-n閾値秘密分散を使用したインスタンス化
  3. VOLEitHフレームワーク 13: VOLE基盤ゼロ知識プロトコルの公開検証可能プロトコルへのコンパイル

符号理論の応用

  1. ハミング距離計量復号: SDitH等方式の基礎
  2. 秩計量復号: RYDE、Mirath等方式
  3. 置換核問題: PERK方式の困難性仮定

制限付き復号問題

  1. CROSS方式 6: 単純なCVEプロトコルを使用した制限付き復号
  2. WAVE方式 10,19: 三元高重み症候群復号に基づく
  3. 理論分析 8,9: E-SDPのNP完全性と具体的困難性

結論と考察

主要な結論

  1. フレームワーク統合の成功: 制限付き復号問題を先進的なMPCitHフレームワークに効果的に統合できることを証明
  2. 顕著な性能向上: 単純なCVEプロトコルをTCitH/VOLEitHに置き換えることで、署名サイズを大幅削減
  3. 広範な適用性: この手法は異なるタイプの制限付き復号問題に適用可能

制限事項

  1. 複雑性の増加: 元のCROSSの単純なCVEプロトコルと比較して、TCitH/VOLEitH構成は著しく複雑
  2. 計算オーバーヘッド: 署名サイズは削減されますが、署名生成と検証の計算複雑性が増加する可能性
  3. パラメータ依存性: 性能は具体的なパラメータ選択と最適化戦略に大きく依存

今後の方向性

  1. さらなる最適化: より効率的な多項式モデリング手法の探索
  2. 他の制限付き問題: この手法を他のタイプの制限付き復号問題に拡張
  3. 実装最適化: 計算オーバーヘッドを削減するための効率的な実装の開発

深度評価

利点

  1. 技術的革新: 制限付き復号問題の簡潔で効果的な多項式モデリング手法を提案
  2. 顕著な改善: 同じセキュリティを維持しながら署名サイズを大幅削減
  3. 理論的貢献: 制限付き復号問題と先進的なMPCitHフレームワーク間の橋渡しを確立
  4. 実用的価値: 耐量子署名方式の新しい設計思想を提供

不足点

  1. 複雑性のトレードオフ: 構成の複雑性と引き換えに署名サイズを削減
  2. 限定的な新規性: 主に既存技術の巧妙な組み合わせであり、理論的革新は相対的に限定的
  3. 実装詳細の欠落: 詳細な性能分析と実装の比較が不足

影響力

  1. 学術的価値: MPCitHフレームワークの応用に新しいケーススタディを提供
  2. 実用的意義: 将来のNIST標準化プロセスにおける方式選択に影響を与える可能性
  3. 方法論的貢献: 他の困難問題の類似モデリングの参考となる

適用シーン

  1. リソース制約環境: 署名サイズに敏感なアプリケーション
  2. 耐量子暗号展開: 多様なセキュリティ仮定が必要なシステム
  3. 研究プロトタイプ: さらなる最適化と改善の基礎

参考文献

論文は24篇の重要な参考文献を引用しており、MPCitHフレームワークの発展、符号理論の応用、および関連するNIST候補方式をカバーしており、研究に堅実な理論的基礎を提供しています。