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

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

##### 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 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)
Category
Foundations
Publication info
A major revision of an IACR publication in EUROCRYPT 2021
Keywords
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
History
Short URL
https://ia.cr/2021/306

CC BY

BibTeX

@misc{cryptoeprint:2021/306,
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{https://eprint.iacr.org/2021/306}},
url = {https://eprint.iacr.org/2021/306}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.