International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

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

Authors:
Shuichi Katsumata , AIST
Ryo Nishimaki , NTT Secure Platform Laboratories
Shota Yamada , AIST
Takashi Yamakawa , NTT Secure Platform Laboratories
Download:
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.
BibTeX
@inproceedings{eurocrypt-2021-30842,
  title={Round-Optimal Blind Signatures in the Plain Model from Classical and Quantum Standard Assumptions},
  publisher={Springer-Verlag},
  author={Shuichi Katsumata and Ryo Nishimaki and Shota Yamada and Takashi Yamakawa},
  year=2021
}