CISPA
Browse
cispa_all_3238.pdf (484.69 kB)

The Provable Security of Ed25519: Theory and Practice

Download (484.69 kB)
conference contribution
posted on 2023-11-29, 18:15 authored by Jacqueline Brendel, Cas CremersCas Cremers, Dennis Jackson, Mang Zhao
A standard requirement for a signature scheme is that it is existentially unforgeable under chosen message attacks (EUF-CMA), alongside other properties of interest such as strong unforgeability (SUF-CMA), and resilience against key substitution attacks. Remarkably, no detailed proofs have ever been given for these security properties for EdDSA, and in particular its Ed25519 instantiations. Ed25519 is one of the most efficient and widely used signature schemes, and different instantiations of Ed25519 are used in protocols such as TLS 1.3, SSH, Tor, ZCash, and WhatsApp/Signal. The differences between these instantiations are subtle, and only supported by informal arguments, with many works assuming results can be directly transferred from Schnorr signatures. Similarly, several proofs of protocol security simply assume that Ed25519 satisfies properties such as EUF-CMA or SUF-CMA. In this work we provide the first detailed analysis and security proofs of Ed25519 signature schemes. While the design of the schemes follows the well-established Fiat-Shamir paradigm, which should guarantee existential unforgeability, there are many side cases and encoding details that complicate the proofs, and all other security properties needed to be proven independently. Our work provides scientific rationale for choosing among several Ed25519 variants and understanding their properties, fills a much needed proof gap in modern protocol proofs that use these signatures, and supports further standardisation efforts.

History

Preferred Citation

Jacqueline Brendel, Cas Cremers, Dennis Jackson and Mang Zhao. The Provable Security of Ed25519: Theory and Practice. In: IEEE Symposium on Security and Privacy (S&P). 2021.

Primary Research Area

  • Reliable Security Guarantees

Name of Conference

IEEE Symposium on Security and Privacy (S&P)

Legacy Posted Date

2020-10-08

Open Access Type

  • Unknown

BibTeX

@inproceedings{cispa_all_3238, title = "The Provable Security of Ed25519: Theory and Practice", author = "Brendel, Jacqueline and Cremers, Cas and Jackson, Dennis and Zhao, Mang", booktitle="{IEEE Symposium on Security and Privacy (S&P)}", year="2021", }

Usage metrics

    Categories

    No categories selected

    Exports

    RefWorks
    BibTeX
    Ref. manager
    Endnote
    DataCite
    NLM
    DC