Signatures with Tight Multi-User Security from Search Assumptions

Jiaxin Pan; Magnus Ringerud

Paper 2021/382

Signatures with Tight Multi-User Security from Search Assumptions

Jiaxin Pan and Magnus Ringerud

Abstract

We construct two tightly secure signature schemes based on the computational Diffie-Hellman (CDH) and factoring assumptions in the random oracle model. Our schemes are proven secure in the multi-user setting, and their security loss is constant and does not depend on the number of users or signing queries. They are the first schemes that achieve this based on standard search assumptions, as all existing schemes we are aware of are either based on stronger decisional assumptions, or proven tightly secure in the less realistic single-user setting. Under a concrete estimation, in a truly large scale, the cost of our CDH-based scheme is about half of Schnorr and DSA (in terms of signature size and running time for signing).

Metadata

Available format(s): PDF
Category: Public-key cryptography
Publication info: Published elsewhere. ESORICS 2020
DOI: 10.1007/978-3-030-59013-0_24
Keywords: Digital signatures Tight reduction Multi-user security Search assumption
Contact author(s): magnus ringerud @ ntnu no
History: 2021-03-22: revised; 2021-03-22: received; See all versions
Short URL: https://ia.cr/2021/382
License: CC BY

BibTeX

@misc{cryptoeprint:2021/382,
      author = {Jiaxin Pan and Magnus Ringerud},
      title = {Signatures with Tight Multi-User Security from Search Assumptions},
      howpublished = {Cryptology {ePrint} Archive, Paper 2021/382},
      year = {2021},
      doi = {10.1007/978-3-030-59013-0_24},
      url = {https://eprint.iacr.org/2021/382}
}