Cryptology ePrint Archive: Report 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).

Category / Keywords: public-key cryptography / Digital signatures, Tight reduction, Multi-user security, Search assumption

Original Publication (in the same form): ESORICS 2020

Date: received 22 Mar 2021, last revised 22 Mar 2021

Contact author: magnus ringerud at ntnu no

Available format(s): PDF | BibTeX Citation

Version: 20210322:203808 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]