Digital signature algorithms: present and future

21 Oct 2022

Introduction and general structure

In many ways, digital signatures are the digital equivalent of the handwritten signatures we all use every day. However, the main difference between the two is that, while the authenticity of a handwritten signature is linked to the handwriting of the person who writes it, the authenticity of a digital signature is guaranteed by the signer’s possession of a cryptographic tool (cryptographic keys). Similar to a handwritten signature, the main purpose of a digital signature is non-repudiation (the signer cannot deny having signed a document), as well as ensuring the authenticity and integrity of the signed document.

Digital signatures are developed in the field of asymmetric cryptography. In fact, a signature scheme requires a pair of cryptographic keys $(sk,pk)$ :

The private (or signing) key $sk$ , which only the signer knows, is used to create the signature;
The public (or verification) key $pk$ , which is known to everyone, is used to verify the signature itself.

In order to create the signature, it is therefore necessary to use an algorithm which, given the document $D$ and the private key $sk$ as input, returns the signature $S$ as output. Fig. 1 below shows a schematic representation of this process.

Fig. 1 General structure of a signature algorithm

Any user in possession of the signer’s public key $pk$ can verify this signature using an algorithm which, given the signed document, the signature, and the public key $pk$ as input, returns:

TRUE if the signature $S$ was actually created by the user corresponding to the public key $pk$ in question and if the document $D$ has not been modified;
FALSE if the document $D$ has been modified after the signature was affixed or if the private key used to sign does not match the public key used in the verification, i.e., if the signature was made by someone other than the person believed to be the signer.

Fig. 2 shows the digital signature verification process.

Fig. 2 General structure of a verification algorithmWe can now consider a first example of a digital signature based on the RSA asymmetric encryption scheme. In this signature algorithm, as in the RSA cryptosystem, we start with a parameter $N=pq$ with $p$ and $q$ prime numbers. The signer, named Samantha here, generates a pair of RSA keys $(d,e)$ with $d\cdot e = 1 \mod (p-1)(q-1)$ , where $d$ is the private key and $e$ is the public key.

To sign a document $D$ , seen as a positive integer less than $N$ , Samantha calculates the signature $S$ as

$S = D^d \mod N.$

To verify the signature, any user in possession of Samantha’s public key $e$ can check whether

$S^e = D \mod N.$

If so, the signature is deemed valid; otherwise, it is rejected.

Most common algorithms and main paradigms

The digital signature scheme presented in the previous section, although a good example to illustrate how such algorithms work, is not usable in practice because it is insecure. However, the underlying structure of the RSA scheme is used in the RSA PKCS #1 v1.5 signature scheme (now deprecated) or in its more recent version RSA-PSS, which are among the most widely used algorithms today.

Other widely used schemes are certainly ECDSA and EdDSA: both of these algorithms base their security on the discrete logarithm problem on elliptic curves. Depending on the requirements related to the context of use of these algorithms, it is then possible to select a different elliptic curve from those listed in the NIST standards or which have become de facto industry standards: an example of this is the instance of ECDSA that uses the Secp256k1 curve, adopted by Bitcoin.

We can identify two main paradigms underlying the digital signature schemes used today:

Hash-then-sign , in which the hash (or digest) of the message we want to sign is calculated and the signature of that digest is calculated;
Fiat-Shamir , in which the signature is constructed by applying the Fiat-Shamir transform which, starting from an identification protocol that requires interaction between the parties, derives a non-interactive signature scheme.

The Hash-then-sign paradigm is adopted by schemes such as the aforementioned RSA PCKS #1 v1.5 and RSA-PSS. The use of this paradigm aims to solve some of the problems that plague signature schemes that do not use hash functions.

Firstly, by considering the digest of the document as the object to be signed rather than the document itself, the size of the signed object is guaranteed to be limited: this allows for a much more efficient algorithm and ensures that it is not necessary to “break” the document into several pieces. By not having to fragment the document to be signed, the possibility of “deletion attacks” is reduced. These are attacks in which a malicious actor deletes a piece of the message with the corresponding signature, and the recipient has no way of knowing that what they are receiving is a “cut” version of the document originally signed by the sender.

Another reason for calculating the document digest before applying the digital signature is that the use of hash functions reduces the risk of an attacker being able to construct a valid signature even without possessing the private key: this type of attack would be extremely simple if the “naive” version of the RSA-based signature introduced above were used.

These security considerations also justify the use of a hash function in the context of signature schemes built using the Fiat-Shamir transform. Among these, it is worth mentioning EdDSA, which was developed in 2011 by a group of researchers led by Daniel J. Bernstein and is currently the state of the art in the field of digital signatures. EdDSA is built on a protocol (Schnorr identification) that is made non-interactive thanks to the Fiat-Shamir transform. EdDSA is defined using Edwards elliptic curves, hence the acronym EdDSA, which stands for Edwards-curve Digital Signature Algorithm. There are two versions of EdDSA in particular:

Ed25519, which uses the Curve25519 elliptic curve and the SHA512 hash function;
Ed448, which uses the Curve448 curve and the SHAKE256 hash function.

Although ECDSA does not use the Fiat-Shamir transform, it is also based on a protocol that would require interaction between the parties and is made non-interactive so that it can be used as a digital signature scheme.

From a technical point of view, EdDSA is considered better than ECDSA because it offers better performance, greater resistance to side-channel attacks, and a higher level of security. In EdDSA, the signature is constructed deterministically and does not require a random nonce, thus avoiding the risks arising from the repetition of the nonce following implementation errors with devastating consequences for the security of the signature scheme.

Applications of digital signatures

Digital signature schemes are used whenever it is necessary to guarantee the properties of authentication, integrity, and non-repudiation. There are numerous purposes for which the above schemes are used, for example, to authorize bank payments, to electronically sign documents, and to authorize cryptocurrency transactions within the blockchain.

However, digital signature schemes are mainly used within the so-called Public Key Infrastructure (PKI). PKI can be defined as the set of structures designed to use cryptography to guarantee authentication between parties during a key exchange; one example is web PKI, which allows an authenticated key exchange to be established between a user’s browser and a website.

In web PKI, website authentication is performed using a certificate (often defined according to the X.509 standard) that contains the public key of the website itself along with other information. The authenticity of this certificate is guaranteed by a Certification Authority (CA), i.e., a trusted third party that verifies the information and affixes its digital signature as validation. The user’s browser, using the CA’s public key (present in the browser code itself), verifies the certificate, thus authenticating the website with which it is communicating.

The NIST post-quantum competition

All the signature schemes mentioned so far base their security on the difficulty of integer factorization (RSA) or discrete logarithms (ECDSA, EdDSA). While these problems guarantee high levels of security against a classical attacker, they are not sufficient to withstand attacks from a quantum computer. Given the great advances made in recent years in the development of increasingly powerful quantum computers by national agencies and industry, it is therefore necessary to develop new digital signature schemes that continue to guarantee non-repudiation, authenticity, and integrity even in the face of quantum attacks.

To this end, in 2017, the US National Institute of Standards and Technology (NIST) launched a standardization process that includes among its objectives the identification and standardization of quantum-resistant digital signature schemes.

The third round of this competition concluded in July 2022, at the end of which three signature schemes were identified that will now be standardized: Dilithium, Falcon, and SPHINCS+. These schemes base their security on mathematical problems considered “difficult” even for a quantum computer: in particular, Dilithium and Falcon are based on problems from lattice theory, while SPHINCS+ is based on symmetric primitives.

Unlike key negotiation, the signature schemes selected by NIST share the same high-level structure as the schemes currently in use, which should ease the transition to quantum-resistant solutions. However, it should be noted that the post-quantum schemes currently being standardized are characterized by large key and signature sizes, which will need to be taken into account during implementation.

The next articles in this series will take a closer look at each primitive and describe how these schemes work.

This article is part of a series of contributions by the Telsy Cryptography Research Group dedicated to quantum computing and its implications for cryptography. For other articles, please refer to the index of the section.

For other articles related to quantum and cryptography, please refer to the relevant categories in the blog.

The authors

Edoardo Signorini, graduated in Mathematics with a curriculum in cryptography at the University of Trento, in 2020 carried out the Master’s thesis in the field of Post-Quantum Cryptography (PQC) at Telsy. He currently holds the role of cryptographer within the Telsy research group and carries out an industrial research doctorate in Pure and Applied Mathematics at the Politecnico di Torino. His activity focuses on PQC research and on the analysis and development of cryptographic protocols.

Marco Rinaudo, a bachelor’s degree in Mathematics at the University of Turin and a student of the master’s degree course in Mathematics with a specialization in Cryptography at the University of Trento, currently an intern in the Telsy research group.