Signatures with Tight Multi-user Security from Search Assumptions
Peer reviewed, Journal article
Accepted version
Åpne
Permanent lenke
https://hdl.handle.net/11250/2726753Utgivelsesdato
2020Metadata
Vis full innførselSamlinger
- Institutt for matematiske fag [2531]
- Publikasjoner fra CRIStin - NTNU [38689]
Originalversjon
https://doi.org/10.1007/978-3-030-59013-0_24Sammendrag
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).