MPCitH-based Signatures from Restricted Decoding Problems

Basic Information

• Paper ID: 2510.11224
• Title: MPCitH-based Signatures from Restricted Decoding Problems
• Authors: Michele Battagliola (University Polytechnic of Marche), Sebastian Bitzer, Antonia Wachter-Zeh, Violetta Weger (Technical University of Munich)
• Classification: cs.CR (Cryptography and Security), cs.IT (Information Theory), math.IT (Information Theory)
• Publication Date: October 13, 2025 (arXiv preprint)
• Paper Link: https://arxiv.org/abs/2510.11224

Abstract

This paper embeds the Restricted Syndrome Decoding Problem (E-SDP) into the Threshold-Computation-in-the-Head (TCitH) and VOLE-in-the-Head (VOLEitH) frameworks, which represent the latest developments in the MPC-in-the-Head (MPCitH) paradigm, significantly improving the performance of digital signature schemes. The authors propose a structurally simple modeling approach that achieves competitive signature sizes. By instantiating the restricted decoding problem using the same hardness assumptions as CROSS, signature sizes are reduced by more than two-fold compared to the NIST submission version. Furthermore, the authors discover that ternary full-weight decoding is closely related to the underlying hardness assumptions of WAVE, and using this approach yields signature sizes comparable to the smallest MPCitH candidate schemes in the NIST competition.

Research Background and Motivation

Problem Background

1. Post-Quantum Cryptography Standardization Needs: Following the standardization of CRYSTALS-Dilithium, FALCON, and SPHINCS+, NIST launched a call for additional digital signature schemes in September 2022, aiming to diversify the post-quantum signature standards portfolio.
2. Development of the MPCitH Paradigm: Since its introduction by Ishai et al. in 2007, MPCitH technology has reshaped the landscape of post-quantum digital signatures. TCitH and VOLEitH, as the latest specializations of MPCitH, offer significant performance improvements over previous constructions.
3. Application of Coding Theory in Cryptography: Hardness problems based on coding theory (such as decoding problems in Hamming and rank metrics) provide a theoretical foundation for constructing efficient post-quantum signatures.

Research Motivation

1. Performance Optimization Needs: While existing CROSS signature schemes are based on restricted decoding problems, they employ relatively simple CVE protocols with room for optimization in signature size.
2. Framework Unification: Unifying restricted decoding problems into advanced TCitH/VOLEitH frameworks to fully leverage the performance advantages of these frameworks.
3. Enhanced Competitiveness: Significantly reducing signature sizes while maintaining security to improve competitiveness in the NIST competition.

Core Contributions

1. Proposed a Polynomial Modeling Approach for E-SDP: Designed a structurally simple yet effective polynomial relationship to embed the restricted syndrome decoding problem into the TCitH and VOLEitH frameworks.
2. Significantly Reduced Signature Sizes for CROSS-type Schemes: For the same decoding problem, signature sizes are reduced by more than 50% compared to the NIST-submitted CROSS scheme (from 12.4 kB to 5.5 kB).
3. Discovered the Application Potential of Ternary Full-Weight Decoding: Demonstrated that ternary full-weight decoding related to WAVE is a restricted decoding problem and achieved signature sizes comparable to the smallest MPCitH candidate schemes (3.1 kB).
4. Provided Complete Parameterization Schemes: Delivered specific parameter choices and performance analyses for NIST security categories 1, 3, and 5.

Methodology Details

Task Definition

The research objective is to represent the Restricted Syndrome Decoding Problem (E-SDP) as a polynomial relationship suitable for constructing digital signature schemes within the TCitH and VOLEitH frameworks.

E-SDP Definition: Given a restriction set E ⊂ F, a parity-check matrix H ∈ F^(r×n), and a syndrome s ∈ F^r, find e ∈ E^n such that eH^T = s.

Core Modeling Approach

1. Polynomial Constraint Construction

For a parity-check matrix H in systematic form H = (A, I_r), where A ∈ F^(r×k) and I_r is the identity matrix:

• Witness Vector: w ∈ F^k (partial error vector)
• Extended Error Vector: e = (w, s - wA^T)
• Restriction Polynomial: f_E(x) = ∏_{e∈E}(x - e)

Polynomial Relation System:

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

where:

• 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. Degree Analysis

Proposition 1: This polynomial relationship provides a degree z = |E| modeling of E-SDP. If w ∈ F^k satisfies F(w) = 0, then the error vector e = (w, s - wA^T) solves the E-SDP instance (H, s).

Concrete Instantiations

CROSS-SDP

• Restriction Set: E = {2^i | i ∈ 7} ⊆ F_{127}
• Parameters: |E| = 7, p = 127
• Security: Based on detailed analysis in 7,15

Ternary-SDP

• Restriction Set: E = {1, 2} ⊆ F_3
• Parameters: |E| = 2, p = 3
• Complexity: O(2^{0.247·n}) operations (within polynomial factors)

Experimental Setup

Parameter Selection Strategy

Based on security requirements and performance optimization objectives, the following key parameters are selected:

1. TCitH Framework Parameters:
   • τ: Number of parallel repetitions
   • N: Evaluation field size
   • μ: Extension field degree K : F
   • η: Batching parameter
2. VOLEitH Framework Parameters:
   • ρ: Extension field parameter
   • B: Consistency check parameter
   • T_open: VC scheme parameter

Security Constraints

The following security requirements are satisfied:

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

Evaluation Metrics

Primary evaluation focuses on signature size, comprising three components:

• |σ_sym|: VC scheme-related
• |σ_w|: Witness-related
• |σ_F|: OWF-related

Experimental Results

Main Results

TCitH Framework Performance

| Security Level | E-SDP Type | |F| | |E| | n | k | τ | N | μ | η | Signature Size (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 Framework Performance

Comparison with NIST Candidate Schemes

Key Findings

1. Significant Size Reduction: CROSS-SDP achieves 64.5% reduction in signature size compared to the original CROSS
2. Framework Selection Impact: VOLEitH outperforms TCitH for high-degree problems
3. Competitiveness: Ternary-SDP achieves performance comparable to the best MPCitH candidate schemes

Related Work

Development of the MPCitH Paradigm

1. Original MPCitH 23: Introduced in 2007, combining secure multi-party computation with Fiat-Shamir transformation
2. TCitH Framework 21: Instantiation using ℓ-out-of-n threshold secret sharing
3. VOLEitH Framework 13: Compilation of VOLE-based zero-knowledge protocols into publicly verifiable protocols

Application of Coding Theory

1. Hamming Metric Decoding: Foundation of schemes like SDitH
2. Rank Metric Decoding: Basis of schemes like RYDE and Mirath
3. Permutation Kernel Problem: Hardness assumption of the PERK scheme

Restricted Decoding Problems

1. CROSS Scheme 6: Restricted decoding using simple CVE protocol
2. WAVE Scheme 10,19: Based on ternary high-weight syndrome decoding
3. Theoretical Analysis 8,9: NP-completeness and concrete hardness of E-SDP

Conclusions and Discussion

Main Conclusions

1. Successful Framework Integration: Demonstrated that restricted decoding problems can be effectively integrated into advanced MPCitH frameworks
2. Significant Performance Improvements: By replacing the simple CVE protocol with TCitH/VOLEitH, signature sizes are substantially reduced
3. Broad Applicability: The approach is applicable to different types of restricted decoding problems

Limitations

1. Increased Complexity: Compared to the simple CVE protocol of the original CROSS, TCitH/VOLEitH constructions are significantly more complex
2. Computational Overhead: While signature sizes are reduced, computational complexity of signature generation and verification may increase
3. Parameter Dependence: Performance is highly dependent on specific parameter choices and optimization strategies

Future Directions

1. Further Optimization: Explore more efficient polynomial modeling methods
2. Other Restricted Problems: Extend the approach to other types of restricted decoding problems
3. Implementation Optimization: Develop efficient implementations to reduce computational overhead

In-Depth Evaluation

Strengths

1. Technical Innovation: Proposes a concise and effective polynomial modeling approach for restricted decoding problems
2. Significant Improvements: Substantially reduces signature sizes while maintaining the same security level
3. Theoretical Contribution: Establishes a bridge between restricted decoding problems and advanced MPCitH frameworks
4. Practical Value: Provides new design insights for post-quantum signature schemes

Weaknesses

1. Complexity Trade-off: Exchanges construction complexity for reduction in signature size
2. Limited Novelty: Primarily a clever combination of existing techniques with relatively limited theoretical innovation
3. Missing Implementation Details: Lacks detailed performance analysis and comparison with practical implementations

Impact

1. Academic Value: Provides new case studies for the application of MPCitH frameworks
2. Practical Significance: May influence scheme selection in future NIST standardization processes
3. Methodological Contribution: Provides reference for similar modeling of other hardness problems

Applicable Scenarios

1. Resource-Constrained Environments: Applications sensitive to signature size
2. Post-Quantum Cryptography Deployment: Systems requiring diverse security assumptions
3. Research Prototypes: Foundation for further optimization and improvement

References

The paper cites 24 important references covering the development of MPCitH frameworks, applications of coding theory, and related NIST candidate schemes, providing a solid theoretical foundation for the research.