Post-Quantum Sanitizable Signatures from McEliece-Based Chameleon Hashing

1. Problem Statement

Sanitizable signatures allow a signer to delegate the right to modify specific parts of a signed document to a designated "sanitizer" without invalidating the signature, while keeping the rest of the document immutable. This is crucial for applications like redacting patient identifiers in medical records or updating expiration dates in certificates.

However, existing sanitizable signature schemes rely on classical cryptographic primitives (RSA, Discrete Logarithms, Pairings) which are vulnerable to Shor's algorithm on quantum computers. While recent lattice-based post-quantum (PQ) solutions exist, they suffer from:

• Reliance on the Random Oracle Model (ROM) for collision resistance.
• Lack of perfect transparency (the ability to make sanitized signatures statistically indistinguishable from fresh ones).
• Reliance on newer, less mature hardness assumptions (Module-LWE).

The paper addresses the gap in code-based post-quantum sanitizable signatures, specifically aiming to construct a scheme that is transparent, immutable, and based on the long-standing McEliece cryptosystem.

2. Methodology

The authors propose a novel construction based on the McEliece cryptosystem and Goppa codes. The core innovation is a chameleon hash function derived from syndrome decoding.

A. The Chameleon Hash Construction

The hash function is defined as:
$$H_{pk}(m, r) = (G(m) \oplus r) \cdot H_{pub}^T$$
Where:

• $m$: The message block.
• $r$: A randomizer vector with Hamming weight $t$.
• $G(m)$: A hash function modeled as a Random Oracle (e.g., SHA-3).
• $H_{pub}$: The public parity-check matrix of a binary Goppa code.

Key Design Choices:

1. Random Oracle Preprocessing: Without $G(m)$, the hash is linear ($H(x,r) = (x \oplus r)H^T$), making it trivially vulnerable to collision attacks. By hashing the message first, finding a collision requires inverting the random oracle, which is infeasible.
2. Trapdoor Mechanism: The sanitizer holds the secret key (Goppa code parameters, scrambling matrix $S'$, and permutation $P$). To find a collision for a new message $m'$, the sanitizer computes a target syndrome and uses Patterson decoding to find a valid randomizer $r'$ such that $H(m, r) = H(m', r')$. This operation is efficient ($O(n \cdot t)$).

B. The Sanitizable Signature Scheme

The scheme chains the chameleon hash across message blocks:

1. Key Generation: Generates two independent McEliece key pairs: one for immutable blocks ($H_{non}$) and one for admissible blocks ($H_{san}$).
2. Signing: The signer creates a hash chain. For immutable blocks, they use $H_{non}$; for admissible blocks, they use $H_{san}$. The final digest is signed using a standard PQ signature (e.g., Dilithium2).
3. Sanitization: The sanitizer modifies admissible blocks. Using the trapdoor of $H_{san}$, they find new randomizers $r'$ to maintain the hash chain integrity. The final signature remains valid because the final digest ($h_L$) and the admissibility mask are preserved.

3. Key Contributions

1. First Code-Based PQ Sanitizable Signature: This is the first construction of a transparent, post-quantum sanitizable signature scheme based on code-based assumptions (Syndrome Decoding).
2. Perfect Transparency via Weight Constraints:
   • The authors prove that if the signer samples randomizers with exactly weight $t$, the distribution of fresh signatures is identical to sanitized signatures (Patterson decoding naturally outputs weight-$t$ vectors).
   • This achieves perfect transparency ($\delta = 0$), meaning no statistical or computational advantage exists for an observer to distinguish between a signer and a sanitizer.
   • Without this constraint, the statistical distance is negligible but non-zero ($\delta \approx 0.0187$ for standard parameters).
3. Rigorous Security Proofs:
   • Existential Unforgeability (EUF-CMA): Proven in the ROM, reducing to the hardness of the Syndrome Decoding (SD) problem.
   • Immutability: Proven that even the sanitizer cannot alter immutable blocks without the corresponding trapdoor (which they do not possess).
4. Implementation and Benchmarks: A Python prototype was implemented using NIST Category 1 parameters (Classic-McEliece: $n=3488, k=2720, t=64$).

4. Results and Performance

The paper provides empirical data and theoretical analysis for the scheme:

• Security Level: Achieves ~128-bit post-quantum security (NIST Category 1).
• Key Sizes:
  • Public Key: ~655.3 KB (dominated by two parity-check matrices). This is smaller than the lattice-based alternative (~850 KB).
  • Signature Size: ~6.75 KB for 10 blocks (scales linearly with the number of blocks due to randomizer vectors).
• Performance:
  • Sanitization: Theoretical Patterson decoding time is ~8 ms per modified block. (Note: The Python prototype used a randomized search which was slower/less reliable; the theoretical estimate assumes a real Patterson decoder).
  • Signing/Verification: Linear scaling with the number of blocks.
• Comparison:
  • vs. Lattice-based (Clermont et al.): Smaller public keys, stronger transparency (Perfect vs. Weak), and relies on a 45-year-old hardness assumption (Syndrome Decoding) vs. a 15-year-old one (Module-LWE).
  • vs. Classical (RSA): Larger keys/signatures but offers quantum resistance.

5. Significance and Limitations

Significance:

• Long-Term Security: Provides a robust solution for data that must remain secure for decades (e.g., medical records, legal contracts) against future quantum attacks.
• Privacy: The achievement of perfect transparency is a major theoretical breakthrough, ensuring that sanitized documents are cryptographically indistinguishable from original ones, protecting the privacy of the sanitization process.
• Diversity: Adds code-based cryptography to the post-quantum toolkit, reducing reliance on lattice-based schemes.

Limitations:

• Random Oracle Model (ROM): The collision resistance of the chameleon hash relies on the ROM. No known code-based chameleon hash achieves this in the standard model.
• Key Size: While smaller than lattice alternatives, 655 KB is still large compared to classical RSA/ECC keys, potentially limiting use in bandwidth-constrained IoT devices.
• Exposure-Freeness: The scheme is not "exposure-free." Repeated sanitization of the same block could theoretically leak information about the trapdoor.
• Policy Hiding: The admissibility mask (which blocks are mutable) is public.

Conclusion:
This work establishes a foundational, transparent, and secure post-quantum sanitizable signature scheme. It successfully adapts the McEliece cryptosystem for controlled collision finding, offering a practical path for long-term secure data management in a quantum era, with a strong emphasis on privacy through perfect transparency. Future work suggests exploring MDPC/LDPC codes to reduce key sizes and developing constant-time implementations to prevent side-channel attacks.