International Association for Cryptologic Research

International Association
for Cryptologic Research


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

Shuichi Katsumata , AIST
Ryo Nishimaki , NTT Secure Platform Laboratories
Shota Yamada , AIST
Takashi Yamakawa , NTT Secure Platform Laboratories
DOI: 10.1007/978-3-030-77870-5_15 (login may be required)
Search ePrint
Search Google
Conference: EUROCRYPT 2021
Abstract: 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 \emph{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.
Video from EUROCRYPT 2021
  title={Round-Optimal Blind Signatures in the Plain Model from Classical and Quantum Standard Assumptions},
  author={Shuichi Katsumata and Ryo Nishimaki and Shota Yamada and Takashi Yamakawa},