High-speed high-security signatures

By Daniel J. Bernstein, Niels Duif, Tanja Lange, Peter Schwabe, Bo-Yin Yang. Journal of Cryptographic Engineering, 2011

831 citations recorded by the source corpus.

This paper shows that a $390 mass-market quad-core 2.4GHz Intel Westmere (Xeon E5620) CPU can create 109000 signatures per second and verify 71000 signatures per second on an elliptic curve at a 2128 security level. Public keys are 32 bytes, and signatures are 64 bytes. These performance figures include strong defenses against software side-channel attacks: there is no data flow from secret keys to array indices, and there is no data flow from secret keys to branch conditions.

Subfields: Artificial Intelligence, Information Systems

View Paper: https://www.semanticscholar.org/paper/218b4099a98a7c015ff5d9ad15af61de53be8fd6

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

1. Dan Boneh
2. Eli Ben-Sasson
3. Eran Tromer
4. Madars Virza
5. Peter Schwabe
6. Alessandro Chiesa
7. Emiliano De Cristofaro
8. George Danezis

In Information Systems

1. Eran Tromer
2. Eli Ben-Sasson
3. Peter Schwabe
4. George Danezis
5. Madars Virza
6. Tanja Lange
7. Bryan Ford
8. Alessandro Chiesa

Citations in the corpus

• Leaky Cauldron on the Dark Land: Understanding Memory Side-Channel Hazards in SGX (2017, background): “Edwards-curve Digital Signature Algorithm (EdDSA) [13] is a high-speed high-security digital signature scheme over twisted Edwards curves.”
• ADSNARK: Nearly Practical and Privacy-Preserving Proofs on Authenticated Data (2015, methodology): “9 For the signature scheme, we have used the ed2551910 implementation described in [30], which offers extremely fast batch verification that we incorporated in the ADSNARK public verification algorithm (recall that one signature per input must be verified).”
• Efficient Private Statistics with Succinct Sketches (2015, methodology): “The cryptographic layer of the protocol is also written in JavaScript, using the Ed25519 curve [8] implementation available from Elliptic.js , 6 which supports 256-bit points and provides security comparable to a 128-bit security parameter.”
• Simple Schnorr multi-signatures with applications to Bitcoin (2019, background): “Note that what we just described is the so-called “key-prefixed” variant of the scheme where the public key is hashed together with R and m [BDL + 11].”
• A Formal Security Analysis of the Signal Messaging Protocol (2017, background): “Sign is a signature scheme based on Ed25519 [13, 62].”
• Identity inference of genomic data using long-range familial searches (2018, methodology): “To facilitate consideration of our approach by the community, we provide a demo source code on GitHub that can sign and verify the raw genotype files using previously-published digital signature scheme (24).”
• Preventing Page Faults from Telling Your Secrets (2016, background): “In EdDSA signing algorithm [11], the main ingredient is a randomly chosen scalar value r which forms the session key.”
• CONIKS: Bringing Key Transparency to End Users (2015, background): “10There are deterministic variants of Schnorr or DSA [5, 50] but these are not verifiably deterministic as they generate nonces pseudorandomly as a symmetric-key MAC of the data to be signed.”
• The Security Impact of a New Cryptographic Library (2012, background): “See [7], [11], and [12] for detailed surveys of previous speeds.”
• Software Speed Records for Lattice-Based Signatures (2013, methodology): “First, the Ed25519 elliptic-curve signature scheme [3] and second, RSA-2048 signatures based on the OpenSSL implementation (ronald2048).”
• Enhancing Bitcoin Security and Performance with Strong Consistency via Collective Signing (2016, methodology): “However, the cost for public-key operations has decreased due to well-optimized asymmetric cryptosystems [6], making those costs less of an issue.”
• Telling Your Secrets without Page Faults: Stealthy Page Table-Based Attacks on Enclaved Execution (2017, methodology): “The Edwards-curve Digital Signature Algorithm (EdDSA) [4] is an efficient, highsecurity signature scheme over a twisted Edwards elliptic curve with public reference point G.”
• Succinct Non-Interactive Zero Knowledge for a von Neumann Architecture (2014, methodology): “We follow [19]’s suggestions and achieve an assembly-optimized heap to implement the Bos–Coster algorithm.”