Paper 2021/306

Round-Optimal Blind Signatures in the Plain Model from Classical and Quantum Standard Assumptions

Shuichi Katsumata, Ryo Nishimaki, Shota Yamada, and Takashi Yamakawa


Blind signatures, introduced by Chaum (Crypto’82), allows a user to obtain a signature on a message without revealing the message itself to the signer. Thus far, all existing constructions of round-optimal blind signatures are known to require one of the following: a trusted setup, an interactive assumption, or complexity leveraging. This state-of-the-affair is somewhat justified by the few known impossibility results on constructions of round-optimal blind signatures in the plain model (i.e., without trusted setup) from standard assumptions. However, since all of these impossibility results only hold under some conditions, fully (dis)proving the existence of such round-optimal blind signatures has remained open. In this work, we provide an affirmative answer to this problem and construct the first round-optimal blind signature scheme in the plain model from standard polynomial-time assumptions. Our construction is based on various standard cryptographic primitives and also on new primitives that we introduce in this work, all of which are instantiable from classical and post-quantum standard polynomial-time assumptions. The main building block of our scheme is a new primitive called a blind-signature-conforming zero-knowledge (ZK) argument system. The distinguishing feature is that the ZK property holds by using a quantum polynomial-time simulator against non-uniform classical polynomial-time adversaries. Syntactically one can view this as a delayed-input three-move ZK argument with a reusable first message, and we believe it would be of independent interest.

Available format(s)
Publication info
A major revision of an IACR publication in EUROCRYPT 2021
blind signaturezero knowledge
Contact author(s)
ryo nishimaki zk @ hco ntt co jp
shuichi katsumata @ aist go jp
takashi yamakawa ga @ hco ntt co jp
yamada-shota @ aist go jp
2021-03-09: received
Short URL
Creative Commons Attribution


      author = {Shuichi Katsumata and Ryo Nishimaki and Shota Yamada and Takashi Yamakawa},
      title = {Round-Optimal Blind Signatures in the Plain Model from Classical and Quantum Standard Assumptions},
      howpublished = {Cryptology ePrint Archive, Paper 2021/306},
      year = {2021},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.