Visible to the public On the Provable Security of (EC)DSA Signatures

TitleOn the Provable Security of (EC)DSA Signatures
Publication TypeConference Paper
Year of Publication2016
AuthorsFersch, Manuel, Kiltz, Eike, Poettering, Bertram
Conference NameProceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security
PublisherACM
Conference LocationNew York, NY, USA
ISBN Number978-1-4503-4139-4
Keywordsdigital signatures, DSA, ECDSA, GOST, Human Behavior, Metrics, provable security, pubcrawl, random key generation, Resiliency, Scalability, signature schemes, SM2
Abstract

Among the signature schemes most widely deployed in practice are the DSA (Digital Signature Algorithm) and its elliptic curves variant ECDSA. They are represented in many international standards, including IEEE P1363, ANSI X9.62, and FIPS 186-4. Their popularity stands in stark contrast to the absence of rigorous security analyses: Previous works either study modified versions of (EC)DSA or provide a security analysis of unmodified ECDSA in the generic group model. Unfortunately, works following the latter approach assume abstractions of non-algebraic functions over generic groups for which it remains unclear how they translate to the security of ECDSA in practice. For instance, it has been pointed out that prior results in the generic group model actually establish strong unforgeability of ECDSA, a property that the scheme de facto does not possess. As, further, no formal results are known for DSA, understanding the security of both schemes remains an open problem. In this work we propose GenericDSA, a signature framework that subsumes both DSA and ECDSA in unmodified form. It carefully models the "modulo q" conversion function of (EC)DSA as a composition of three independent functions. The two outer functions mimic algebraic properties in the function's domain and range, the inner one is modeled as a bijective random oracle. We rigorously prove results on the security of GenericDSA that indicate that forging signatures in (EC)DSA is as hard as solving discrete logarithms. Importantly, our proofs do not assume generic group behavior.

URLhttp://doi.acm.org/10.1145/2976749.2978413
DOI10.1145/2976749.2978413
Citation Keyfersch_provable_2016