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-based Signatures from Restricted Decoding Problems

基本信息

  • 论文ID: 2510.11224
  • 标题: MPCitH-based Signatures from Restricted Decoding Problems
  • 作者: Michele Battagliola (University Polytechnic of Marche), Sebastian Bitzer, Antonia Wachter-Zeh, Violetta Weger (Technical University of Munich)
  • 分类: cs.CR (Cryptography and Security), cs.IT (Information Theory), math.IT (Information Theory)
  • 发表时间: 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相同的困难性假设实例化受限解码问题，签名大小相比NIST提交版本减少了两倍以上。此外，作者发现三元全权重解码与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，找到e ∈ E^n使得eH^T = s。

核心建模方法

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: 该多项式关系提供了E-SDP的度数为z = |E|的建模，如果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^λ

评价指标

主要评估签名大小，包括三个组成部分：

  • |σ_sym|: VC方案相关
  • |σ_w|: 见证相关
  • |σ_F|: OWF相关

实验结果

主要结果

TCitH框架性能

| 安全级别 | E-SDP类型 | |F| | |E| | n | k | τ | N | μ | η | 签名大小(B) | |---------|-----------|-----|-----|---|---|---|---|---|---|-----------| | NIST 1 | CROSS-SDP | 127 | 7 |127| 76| 15|2048| 2| 10| 5,533 | | NIST 1 | Ternary-SDP| 3 | 2 |579|213| 12|2048| 7| 12| 3,095 | | NIST 3 | CROSS-SDP | 127 | 7 |187|111| 23|2048| 2| 14| 12,354 | | NIST 3 | Ternary-SDP| 3 | 2 |839|309| 18|2048| 7| 18| 6,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候选方案，为研究提供了坚实的理论基础。