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 signaturesTight reductionMulti-user securitySearch 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}
}
