- Signature introduction
- Signature transformation types
- RSA signatures - factorisation
- DLP-based signatures
- DH-based signatures
- Hash signatures
- Lattice signatures
- Other signature types
- Blind signatures
- Group signatures
- Anonymous signatures
- Threshold signatures
- One time signatures
- Undeniable signatures
- Other signatures
- Signature formats
- Signature standards

- 1976 Idea published by Whit Diffie and Martin Hellman
- 1978 RSA crypto system invented by Rivest, Shamir and Adleman, can be used for encryption and signature
- 1985 ElGamal Signature Scheme invented, later improved by Schnorr
- Today any computationally hard problem can be turned into a signature scheme
- Variants of RSA (RSA-PKCS#1, RSA-PSS) and ElGamal-Schnorr (DSA, ECDSA) dominate applications

- K is the Key generation algorithm,
- S is the Signing algorithm and
- V is the Verification algorithm.

- Signature scheme with appendix:
- Message + Alice’s private key = Signature (signature does not contain message, use of hash, more efficient for long messages)
- Message + Signature + Alice’s public key = YES/NO
- Signature scheme with message recovery:
- Message + Alice’s private key = Signature (signature contains message)
- Signature + Alice’s public key = YES/NO+Message

- RSA is not suited to some applications since signature generation is a costly operation.
- RSA signatures are large, some applications require smaller signature footprints.
- DSA is an algorithm that tries to address this.

- RSA cryptosystem - Wikipedia
*- Clifford Cocks, GCHQ, had developed an equivalent system in 1973, which was not declassified until 1997.* - Ron Rivest's homepage -
*with further crypto links ...* - Ron Rivest - Wikipedia
- RSA PKCS

- Taher ElGamal - Wikipedia
- ElGamal signature scheme (1985) - Wikipedia - based on the difficulty of computing discrete logarithm
- DSA - Wikipedia
- a Federal Information Processing Standard for digital signatures, based on the mathematical concept of modular exponentiation and the discrete logarithm problem.
- a variant of the Schnorr and ElGamal signature schemes
- DSA is a signature with appendix algorithm and the signature produced consists of two 160-bit integers r and s
- The integer r is a function of a 160-bit random number k called the ephemeral key which changes with every message
- The integer s is a function of the message, the signer’s private key x, the integer r, the ephemeral key k
- Schnorr signature scheme (1989) - Wikipedia
- Schnorr signatures have been suggested to be used for challenge response mechanisms in smart cards since the response part of the signature (the value of s) is particularly easy to evaluate since it only requires the computation of a single modular multiplication and a single modular addition.
- Edwards DSA (2011) - Wikipedia
- The Edwards-Curve Digital Signature Algorithm (EdDSA) is a deterministic Schnorr signature variant using twisted Edwards curves rather than Weier-strass curves, at a significant performance gain.
- Ed25519 is a popular if not the most popular instance of EdDSA and is based on the Edwards Curve25519 providing 128-bits of security. Due to its superior efficiency among Elliptic Curve schemes and better security guarantees against side-channel attacks under weak randomness sources,Ed25519 is widely adopted by such protocols as TLS 1.3, SSH, Tor, GnuPGP,Signal and more. It is also the preferred signature scheme of several blockchain systems, such as Corda, Tezos, Stellar, and Libra. For an analysis see Konstantinos Chalkias (SSR2020).
- ed25519 paper and public reference implementation
- Pointcheval Stern signature scheme - Wikipedia
- changes the ElGamal scheme slightly to produce an algorithm which has been proven secure in a strong sense against adaptive chosen-message attacks
- Nyberg–Rueppel Signatures
- based on discrete logarithms in some public finite abelian group G
- provides message recoverable (which many other DL-based algorithms do not)

- Decisional DH - Wikipedia
- The DDH assumption states that, given g
^{a}and g^{b}for uniformly and independently chosen a, b in Zq, the value g^{ab}"looks like" a random element in G. - The DDH assumption is related to the discrete log assumption. If it were possible to efficiently compute discrete logs in G, then the DDH assumption would not hold in G.
- Computational DH - Wikipedia
- The CDH assumption states that, given g
^{a}and g^{b}for a randomly chosen generator g and random a, b in { 0 , … , q − 1 } it is computationally intractable to compute the value g^{xy}. - BLS - Boneh–Lynn–Shacham - Wikipedia
- The signature scheme is provably secure (the scheme is existentially unforgeable under adaptive chosen-message attacks) assuming both the existence of random oracles and the intractability of the computational Diffie–Hellman problem in a gap Diffie–Hellman group.
- Boneh and Franklin describe a generic method for converting any Identity-Based Encryption scheme into a signature scheme in 'Dan Boneh and Matthew K. Franklin. Identity-based encryption from the Weil pairing. SIAM J. Comput., 32(3):586–615, 2003.'
- Brent Waters in 'Efficient Identity-Based Encryption Without Random Oracles' presented the first efficient Identity-Based Encryption (IBE) scheme that is fully secure without random oracles. Security is based on the decisional Bilinear Diffie-Hellman (BDH) problem. This can be used to build a new signature scheme that is secure under the computational Diffie-Hellman assumption without random oracles.

- Lamport one-time signatures - 1979
- Both x and y are integers, private key is (x, y), public key is (h(x) | h(y)).
- To sign a single bit:
- if it’s 0, publish (x)
- if it’s 1, publish (y)
- Simple, but don’t use it to sign twice obviously (since you publish x 'half of the time'). Hence it's referred to as OTS.
- To sign multiple bits, hash what you want to sign (so that it has a predictible output length),
for example with SHA-256. Then use 256 key pairs, each consisting of (x
_{n}, y_{n}): - Concatenate all x
_{n}, y_{n}to create the private key, - Concatenate all h(x
_{n}) | h(y_{n}) to create the public key, - If you want to sign (100110
_{2}...), - Then publish (y
_{0}, x_{1}, x_{2}, y_{3}, y_{4}, x_{5}, ...)

- Ralph Merkle
- Merkle signature scheme - Wikipedia
- A Merkle signature scheme (MSS) consists of the combination of a one-time signature scheme (OTS) to sign the data and Merkle’s tree authentication scheme which reduces the authenticity of many one-time verification keys to the authenticity of a single public key.
- Merkle's paper
*'A certified digital signature'*- 1979 - This paper describes a digital signature system which is "pre-certified," generates signatures of about 1 to 3 kilobytes (depending on the exact security requirements), requires a few thousand applications of the underlying encryption function per signature, and only a few kilobytes of memory. If the underlying encryption function takes 10 microseconds to encrypt a block, generating a signature might take 20 milliseconds. The new signature method is called a "tree signature."
- Contents:
- A discussion of one way functions.
- A description of the Lamport-Diffie one time signature.
- An improvement to the Lamport-Diffie one time signature.
- The Winternitz one time signature.
- The W-OTS scheme was proposed by Ralph Merkle in his 1979 paper as an improved version of the Lamport-Diffie OTS to reduce the size of signatures. Instead of a 'per-bit-signature', he proposed to sign multiple bits at once. He was inspired by Robert Winternitz, hence the name.
- Some months after Lamport’s publication, Winternitz of the Stanford Mathematics Department proposed to
publish h
^{w}(x) instead of publishing (h(x) | h(y)). - For example choose w=16 and publish h
^{16}(x) as public key, still using x as secret key. - To sign the binary 1001
_{2}(equal to 9_{10}), publish h^{9}(x). - A problem now is that a malicious person could see this signature and hash it to create h
^{10}(x) and thus forge a valid signature for 1010_{2}(equal to 10_{10}). However this can be circumvented by adding a short checksum after the message (which you would have to sign as well). - A description of tree signatures.
- Winternitz security
- Huelsing's W-OTS+ signatures
- Huelsing's W-OTS+ signatures explained
- XMSS signature - Buchmann, Dahmen and Huelsing
- The eXtended Merkle Signature Scheme (XMSS) allows assembling a set of one time public keys W-OTS+ into one public key. This means that XMSS enables the public key to be used multiple times.
- XMSS signature as IETF RFC 8391
- XMSS reference implementation matching RFC 8391

- Leighton-Micali Hash-Based Signatures ('LMS') - RFC 8554 - describes the Leighton and Micali adaptation of the original Lamport-Diffie-Winternitz-Merkle one-time signature system
- Sphincs.cr.yp.to
- SPHINCS-256 is a PQ stateless hash-based signature scheme that signs hundreds of messages per second on a modern 4-core 3.5GHz Intel CPU.
- Signatures are 41 KB, public keys are 1 KB, and private keys are 1 KB.
- SPHINCS-256 is designed to provide long-term 2
^{128}security even against attackers equipped with quantum computers. - Unlike most hash-based signature schemes, SPHINCS-256 is stateless, allowing it to be a drop-in replacement for current signature schemes.

- 1994, The Bleichenbacher-Maurer OTS
- 2001, The BiBa OTS
- 2002, HORS
- 2014, HORST (HORS with Trees)

- Confirmation protocol, which confirms that a candidate is a valid signature of the message issued by the signer, identified by the public key.
- Disavowal protocol, which confirms that a candidate is not a valid signature of the message issued by the signer.

- Blind signature - Wikipedia - e.g. RSA

- Group - x

- Anonymous - x

- Victor Shoup - Practical Threshold Signatures
- Threshold signatures - implementation

- RSA PKCS#1 (IETF RFC 8017) - RSA Cryptography Specifications Version 2.2
- cryptographic primitives
- encryption schemes
- signature schemes with appendix
- ASN.1 syntax for representing keys and for identifying the schemes

- CMS - Wikipedia
- RFC 5652 Cryptographic Message Syntax (CMS)
- RFC 6268 New ASN.1 Modules for Cryptographic Message Syntax (CMS) and S/MIME
- RFC 5753 Using Elliptic Curve Cryptography with CMS
- RFC 5084 Using AES-CCM and AES-GCM Authenticated Encryption in the Cryptographic Message Syntax (CMS)

- W3C XMLDSIG - the basis for XAdES
- Wikipedia on XMLDSIG
- XML signatures can be used to sign data–a resource–of any type, typically XML documents, but anything that is accessible via a URL can be signed.
- An XML signature used to sign a resource outside its containing XML document is called a detached signature;
- if it is used to sign some part of its containing document, it is called an enveloped signature;
- if it contains the signed data within itself it is called an enveloping signature.
- XAdES (short for XML Advanced Electronic Signatures) is a set of extensions to XML-DSig recommendation making it suitable for advanced electronic signatures. W3C and ETSI maintain and update XAdES together.
- XMLDSIG interop report 2001
- OpenSignature.org - widely supported
- Cloud Signature Consortium (CSC) - remote signatures

- ISO signature standards
- ETSI signature standards
- OASIS, Cloud, etc