Signature introduction

At a glance: By convention, Message Authentication Codes (MACs), generated and verified with the same symmetric key, are not considered as signatures. They do not provide the property of non-repudiation.

Further info at a.o.

Signature scheme

A signature scheme is usually defined as a triplet of algorithms (K; S; V ), where K generates pairs (s; v) of keys for the Signing/Verification algorithm. Only the party knowing s is able to generate a valid signature on m, sig(m), but using V and the corresponding key v (assumed to be public information), anybody can efficiently decide if a given (m; sig(m)) pair is valid.

Note that some schemes, e.g. Identity based schemes, also specify a fourth function, P, that generates parameters.


The Fiat–Shamir heuristic is a technique for taking an interactive proof of knowledge and creating a digital signature based on it. It is described in "How To Prove Yourself: Practical Solutions to Identification and Signature Problems", Fiat, Amos; Shamir, Adi, CRYPTO' 86.

This is used a.o. to define Schnorr signatures.

Signature suite

To meet security requirements and to allow signing of more or less arbitrary long messages, a signature scheme requires a hash function, so that the signing/verification algorithms operate on a fixed-size hash of the message. The combination of signature algorithm and hash function is called a signature suite.

With or without message recovery

Some signature schemes enable the whole message, or part of it, to be recovered from the signature. These schemes can be useful in constrained environments because only the non-recoverable part of the message need be stored or transmitted with the signature. As for asymmetric encryption, main choices are whether to use factoring or DLOG based schemes (in the latter case also which group) and what security model/proof (if any) one finds attractive.


Today the most widely used security notion for signatures is called resistance against existential forgery under adaptive chosen message attack. It is similar to that for MACs. Informally, this means that the attacker is allowed to have messages of his own choosing signed by a 'signing oracle', after which the attacker is to provide a single valid (m; sig(m))-pair that he has not seen before.

For more info refer to the NESSIE Security report, available at

Signature transformations


RSA (1977)

RSA is a set of algorithms that can be used for encryption and for signature. For signatures it can be used either as a scheme with appendix or as a scheme with message recovery. It can be observed that:

Rabin (1979)

DLP-based (discrete logarithm problem)

In any group G, powers bk can be defined for all integers k, and the discrete logarithm logb a is an integer k such that bk = a.

Used in DSA and ECDSA


Based on the difficulty of computing discrete logarithms. It was described by Taher Elgamal in 1985.

The ElGamal signature algorithm is rarely used in practice. A variant developed at the NSA and known as the Digital Signature Algorithm (DSA) is more widely used. There are several other variants.


Undeniable signatures

In this scheme, a signer possessing a private key can publish a signature of a message. However, the signature reveals nothing to a recipient/verifier of the message and signature without taking part in either of two interactive protocols: Refer to Chaum, David; van Antwerpen, Hans (1990) "Undeniable Signatures" and Chaum, David (1991) "Zero-Knowledge Undeniable Signatures" EUROCRYPT '90.


DH-based (Diffie-Hellman) key exchange

DH problems

There's the DH computational and the decision problem.

The Diffie–Hellman problem is stated informally as follows: Given an element g and the values of gx and gy, what is the value of gxy? (remember 32 = 9, 33 = 27, 32 * 33 = 243 = 32+3, not 32*3)

External and gap DH

Boneh–Lynn–Shacham (BLS) signatures

Hash based

One-time signatures (OTS)

Other hash based signatures

Few time signatures

Few-times signatures schemes (FTS) include:

Structure Preserving Signatures

In most signature schemes, the message space consists of integers in Zord(G) for some group G, or of arbitrary strings mapped to either integers in Zord(G) or elements of a group G via a cryptographic hash function. In the latter case, the hash function is often modeled as a random oracle (thus, one effectively signs random group elements).

In contrast, structure-preserving signature (SPS) schemes sign group elements without requiring any prior encoding. SPS are defined over two groups G1 and G2 , equipped with a bilinear map (pairing), and messages are vectors of group elements (from either G1 or G2 or both). Moreover, public keys and signatures also consist of group elements only and signatures are verified by deciding group membership of their elements and evaluating the pairing on elements from the public key, the message and the signature.

Fully SPS schemes also require the secret key to consist of group elements. The main reason for the introduction of SPS was their interoperability with the non-interactive zero-knowledge proof (NIZK) system by Groth and Sahai.

Structure-preserving signatures (SPS) are pairing-based signatures where all the messages, signatures and public keys are group elements, verified by testing equality of products of pairings of group elements.

They are useful building blocks in modular design of cryptographic protocols, in particular in combination with non-interactive zero-knowledge (NIZK) proofs for algebraic relations in a group. SPS have found numerous applications in public-key cryptography, such as blind signatures, group signatures, homomorphic signatures, delegatable anonymous credentials, compact verifiable shuffles, network encoding, oblivious transfer and e-cash.

Lattice based (relevant for PQ)

PQ signatures

Signature types

CL signatures

Signatures with efficient protocols are a form of digital signature invented by Jan Camenisch and Anna Lysyanskaya in 2001. They highlighted how certain digital signature schemes with suitable algebraic structures are amenable to applications such as anonymous credentials, direct anonymous attestation (DAA), and group signatures. These schemes easily enable the signing of a commitment, typically by being algebraically compatible with a Pedersen commitment, and support very efficient zero-knowledge proofs of knowledge of a valid message-signature pair.

In addition to being secure digital signatures, they need to allow for the efficient implementation of two protocols: The combination of these two protocols allows for the implementation of digital credential and ecash protocols.

CL anonymous credentials

And then there's also

Blind signatures

Electronic cash

Anonymous (group) signatures

Group signatures, introduced by Chaum and van Heyst, provide anonymity for signers. Any member of the group can sign messages, but the resulting signature keeps the identity of the signer secret. In some systems there is a third party that can trace the signature, or undo its anonymity, using a special trapdoor. Some systems support revocation where group membershipcan be selectively disabled without affecting the signing ability of unrevoked members.

The relevance of group signatures is indicated by e.g.

Baric and Pfitzman

First solutions were introduced by Baric and Pfitzman, based on the Strong-RSA assumption, see N. Baric and B. Pfitzman. Collision-free accumulators and fail-stop signature schemes without trees. In Proceedings of Eurocrypt 1997, pages 480–494. Springer-Verlag, May 1997.


Boneh, Boyen, and Shacham defined a short group signature scheme, i.e. signer anonymity is provided, and with a standard security level, signatures can be represented in only 250 bytes. It is based on the Decision Linear assumption (DLIN).

Their protocol first uses linear encryption in order to define a special type of zero-knowledge proof. Then the Fiat–Shamir heuristic is applied to transform the proof system into a digital signature. They prove this signature fulfills the additional requirements of unforgeability, anonymity, and traceability required of a group signature.

Their proof relies on not only the DLIN assumption but also another assumption called the q-strong Diffie-Hellman assumption. It is proven in the random oracle model.

Apparently BBS signatures were covered by CL signatures (but not under that name and without security proof).

Summary: the Decision Linear Problem in G1 is stated as follows. Given u, v, h, ua, vb, hc ∈ G1 as input, output yes if a + b = c and no otherwise. One can easily show that an algorithm for solving Decision Linear in G1 gives an algorithm for solving DDH in G1. The converse is believed to be false. That is, it is believed that Decision Linear is a hard problem even in bilinear groups where DDH is easy (e.g., when G1 = G2).

The Decision Linear problem gives rise to the Linear encryption (LE) scheme, a natural extension of ElGamal encryption. Unlike ElGamal encryption, Linear encryption can be secure even in groups where a DDH-deciding algorithm exists. The underlying building block for the group signature scheme is a protocol for proving possession of a solution to an SDH problem.

MATTR reference implementation (New Zealand) Microsoft reference implementation Further: Most applications, and the RFC draft, consider the provably-secure version of BBS referred to as BBS+, whose signatures consist of one group element in G1 and two scalars in Zp, where p is the group order.


BBS+ signatures are derived from BBS, which was improved on in Constant-Size Dynamic k-TAA as BBS+

The scheme was proposed by Au, Susilo, and Mu, and proved secure under the q-SDH assumption.

BBS+ signatures require a pairing-friendly curve, e.g. BLS12-381.

BBS+ Signatures allow for multi-message signing whilst producing a single output signature. With a BBS signature, a proof of knowledge based proof can be produced where only some of the originally signed messages are revealed at the discretion of the prover.

Threshold signatures

Signature formats



The Cryptographic Message Syntax (CMS) is the IETF's standard for cryptographically protected messages. It can be used by cryptographic schemes and protocols to sign, digest, authenticate or encrypt data. It is based on the syntax of PKCS #7, which in turn is based on the Privacy-Enhanced Mail standard. CMS is used as the key cryptographic component of a.o. S/MIME, PKCS #12 and the RFC 3161 Digital timestamping protocol. OpenSSL is open source software that can encrypt, decrypt, sign and verify, compress and uncompress CMS documents.

W3C Linked Data Proofs

A mechanism for ensuring the authenticity and integrity of Linked Data documents using mathematical proofs. Not a W3C Standard nor on the W3C Standards Track. Experimental.

Signature standards





For more signature standards refer to

Signature verification


See also ISO and ETSI.