A New Code-Based Blind Signature Scheme

Abstract Blind signature is an important cryptographic primitive with widespread applications in secure e-commerce, for example to guarantee participants’ anonymity. Existing blind signature schemes are mostly based on number-theoretic hard problems, which have been shown to be solvable with quantum computers. The National Institute of Standards and Technology (NIST) began in 2017 to specify a new standard for digital signatures by selecting one or more additional signature algorithms, designed to be secure against attacks carried out using quantum computers. However, none of the third-round candidate algorithms are code-based, despite the potential of code-based signature algorithms in resisting quantum computing attacks. In this paper, we construct a new code-based blind signature (CBBS) scheme as an alternative to traditional number-theoretic based schemes. Specifically, we first extend Santoso and Yamaguchi’s three pass identification scheme to a concatenated version (abbreviated as the CSY scheme). Then, we construct our CBBS scheme from the CSY scheme. The security of our CBBS scheme relies on hardness of the syndrome decoding problem in coding theory, which has been shown to be NP-complete and secure against quantum attacks. Unlike Blazy et al.’s CBBS scheme which is based on a zero-knowledge protocol with cheating probability $2/3$, our CBBS scheme is based on a zero-knowledge protocol with cheating probability $1/2$. The lower cheating probability would reduce the interaction rounds under the same security level and thus leads to a higher efficiency. For example, to achieve security level $2^{-82}$, the signature size in our CBBS scheme is $1.63$ MB compared to $3.1$ MB in Blazy et al.’s scheme.