Post-quantum (partially) blind signatures from matrix code equivalence

Abstract We construct a novel code-based blind signature scheme, using the MEDS group action. The scheme is built using similar ideas to the Schnorr blind signature scheme and CSI-Otter, but uses additional public key and commitment information to overcome the difficulties that the MEDS group action faces: lack of module structure (present in Schnorr) and lack of a quadratic twist (present in CSI-Otter). We address security concerns related to public key validation, and prove the security of our protocol in the random oracle model, using the security framework of Kastner, Loss, and Xu, under a variant of the Inverse Matrix Code Equivalence problem and a mild heuristic assumption. We also discuss alternative techniques for constructing a code-based blind signature, explain how to modify our protocol to yield a partially blind signature, and consider possible parameter sets and corresponding performance metrics.