Paper 2026/827

A Post-Quantum Accountable Sanitizable Signature Scheme Based on Unbalanced Oil and Vinegar

Abstract

Sanitizable signature schemes~(SSS) allow a designated sanitizer to modify admissible portions of a signed message while preserving the validity of the original signer's authorisation. All existing SSS constructions satisfying the Brzuska et~al.\ security framework rely on classical number-theoretic assumptions broken by Shor's algorithm. We present \textsf{UOV-San}, a sanitizable signature scheme based entirely on multivariate cryptography. The construction employs a dual-signature architecture with strict key separation enforced by a two-message interactive signing protocol: the signer holds only $\sk_S$ and the public trapdoor-hash key $\ck$, whereas the sanitizer holds $\sk_{\mathsf{San}}$ and the trapdoor key $\tk$. We introduce a target second-preimage resistance assumption, \textsf{tSPR}, for UOV public maps. It captures the hardness of finding a distinct input $r'\neq r$ that collides with a given random target input $r$ under the public map $P$, namely $P(r')=P(r)$. Based on this assumption we construct MV-CH, a dedicated multivariate target-collision trapdoor hash. MV-CH is not a standard message-dependent chameleon hash of the form $CH(m,r)$; instead, it hashes only the randomness $r$, while message binding is provided by the upper-layer dual-signature construction. The sanitizer can use the UOV trapdoor to generate target collisions, whereas outsiders face the \textsf{tSPR} problem, except for random-oracle target-collision events. \textsf{UOV-San} provably achieves unforgeability, immutability, and accountability---including against a malicious signer---under UOV EUF-CMA security and \textsf{tSPR} in the random-oracle model. We forgo transparency and privacy: these properties are structurally incompatible with the dual-signature architecture and key-separation requirement, and are operationally unnecessary for our target application domains such as supply-chain audit, government document redaction, and blockchain audit trails. Experimental evaluation confirms practical signing times under $5$ ms and verification times under $2$ ms on commodity hardware.