- Signature introduction
- Signature transformations
- Factorisation
- DLP-based signatures
- Diffie-Hellman key exchange/BLS
- Hash-based signatures
- One Time Signatures (OTS) Lamport, Merkle, ...
- Other hash-based signatures
- Few Time Signatures (FTS)
- Pairing-based signatures Structure Preserving Signatures
- Lattice-based signatures NTRU
- PQ signatures ETSI and NIST
- Signature types
- CL signatures
- CL anonymous credentials
- Blind signatures
- Electronic cash
- Anonymous (group) signatures - BBS, BBS+ (DLIN + SDH)
- Threshold signatures
- Signature formats
- Signature verification

- 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 - involves four operations: key generation, key distribution, signing and verification
- Key generation
- Choice of algorithm parameters which may be shared between different users of the system.
- Choose a key length N
- Choose a N-bit prime number p
- Choose a cryptographic hash function H with output length L bits
- Choose a generator g < p of the multiplicative group of integers modulo p, Z_p^*
- The algorithm parameters are (p, g) which may be shared between users of the system
- Computation of a key pair for a user
- Choose an integer x randomly from {1 … p−2}, x is the private key
- Compute y:=g^x mod p, y is the public key
- Key distribution
- The signer should send the public key y to the receiver via a reliable, but not necessarily secret, mechanism.
- The signer should keep the private key x secret.
- Signing of a message m
- Choose an integer as ephemeral key k randomly from {2 … p−2} with k relatively prime to p−1
- Compute r:=g^k mod p
- Compute s:=(H(m)-xr)k^{-1} mod p-1
- In the unlikely event that s=0 start again with a different random k
- The signature is (r,s)
- Verification
- Verify that 0 < r < p, and 0 < s < p-1
- The signature is valid if and only if g^H(m) = y^r r^s mod p

- 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.
- Key generation
- Choice of algorithm parameters which may be shared between different users of the system.
- Agreement on a group G of prime order q, with generator g in which the DLP is assumed to be hard. Typically a Schnorr group is used.
- Agreement on a hash function H: {0, 1} → Z_q
- Computation of a key pair for a user
- Choose a private signing key, x from the allowed set
- The public verification key is y=g^x
- Key distribution
- The signer should send the public key y to the receiver via a reliable, but not necessarily secret, mechanism.
- The signer should keep the private key x secret.
- Signing of a message m
- Choose a random k from the allowed set
- Let r=g^k
- Let e = H (r ∥ M) where ∥ denotes concatenation and r is represented as a bit string
- Let s=k-xe
- The signature is the pair (s, e)
- Verification
- Let r_v=g^s y^e
- Let e_v = H(r_v ∥ M)
- If e_v = e then the signature is verified.

- 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.

- 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* - ECDSA - Wikipedia
- By Don Johnson and Alfred Menezes, 1999
- A variant of DSA that uses elliptic curves
- Given a message and its signature, the public key can be recovered. An invalid signature, or a signature from a different message, will result in the recovery of an incorrect public key. The recovery algorithm can only be used to check validity of a signature if the signer's public key (or its hash) is known beforehand.
- EdDSA - 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)

- External and gap DH - Wikipedia
- The external Diffie–Hellman (XDH) assumption is used in ECC.
- XDH implies the existence of two distinct groups ⟨G1, G2⟩ with the following properties:
- The discrete logarithm problem (DLP), the computational Diffie–Hellman problem (CDH), and the computational co-Diffie–Hellman problem are all intractable in G1 and G2.
- There exists an efficiently computable bilinear map (pairing) e ( ⋅ , ⋅ ) : G1 × G2 → GT
- The decisional Diffie–Hellman problem (DDH) is intractable in G1.
- In certain EC subgroups, the existence of an efficiently-computable bilinear map (pairing) can allow for practical solutions to the DDH problem. These groups, referred to as
**gap Diffie–Hellman**(GDH) groups, facilitate a variety of cryptographic protocols, including tri-partite key exchange, identity based encryption, and secret handshakes.

- BLS - Boneh–Lynn–Shacham - Wikipedia
*'Short signatures from the Weil pairing'*- uses gap DH - Works in a 'gap group', a group in which CDH problem is intractable but DDH problem can be efficiently solved. Non-degenerate, efficiently computable, bilinear pairings permit such groups.
- Let e : G × G → G
_{T}be a non-degenerate, efficiently computable, bilinear pairing where G, G_{T}are groups of prime order, r. Let g be a generator of G. - Consider an instance of the CDH problem, g, g
^{x}, g^{y}. Intuitively, the pairing function e does not help us compute g^{xy}, the solution to the CDH problem. It is conjectured that this instance of the CDH problem is intractable. **Given g**^{z}, we may check if g^{z}= g^{xy}without knowledge of x, y, and z, by testing whether e(g^{x}, g^{y}) = e(g, g^{z}) holds.- By using the bilinear property x+y+z times, we see that if e(g
^{x}, g^{y}) = e(g, g)^{xy}= e (g, g)^{z}= e(g , g^{z}), then, since G_{T}is a prime order group, xy = z. - 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
*'Identity-based encryption from the Weil pairing'*SIAM J. Comput., 32(3):586–615, 2003.' - Pointcheval and Sanders describe a randomizable signature scheme based on pairings in
*'Short Randomizable Signatures'*- Proceedings of the Cryptographers Track at the RSA Conference (CT-RSA ’16)

- 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)

- ETSI TR 103 616 V1.1.1 (2021-09) "Quantum-Safe Signatures"
- ETSI TR 103 823 V1.1.1 (2021-09) "Quantum-Safe Public Key Encryption and Key Encapsulation"

- A protocol for computing a digital signature in a secure two-party computation protocol
- In applications, the first protocol allows a signer to possess the signing key to issue a signature to a user (the signature owner) without learning all the messages being signed or the complete signature
- A protocol for proving knowledge of a digital signature in a zero-knowledge protocol
- The second protocol allows the signature owner to prove that he has a signature on many messages without revealing the signature and only a (possibly) empty subset of the messages

- Signature with efficient protocols- Wikipedia - Camenisch-Lysyanskaya
- Signature with efficient protocols - Camenisch-Lysyanskaya - a basis for anonymous credentials
- a signature scheme for issuing a signature on a committed value (so the signer has no information on the signed value)
- and for providing knowledge of a signature on a committed value
- can be used as a building block for anonymous credential schemes

- An Efficient System for Non-transferable Anonymous Credentials with Optional Anonymity Revocation - Camenisch-Lysyanskaya
- (1) We give the first practical solution that allows a user to unlinkably demonstrate possession of a credential as many times as necessary without involving the issuing organization.
- (2) To prevent misuse of anonymity, our scheme is the first to offer optional anonymity revocation for particular transactions.
- (3) Our scheme offers separability: all organizations can choose their cryptographic keys independently of each other.
- plus a new primitive, called circular encryption, which is of independent interest

- Blind signature - Wikipedia - e.g. blind RSA (Chaum)

- GNU Taler (LU) - RSA, DSA, blind signatures, no blockchain or snarks

- The Trusted Computing effort [29] that, among other things, enables a desktop PC to prove to a remote party what software it is running via a process called attestation. Group signatures are needed for privacy-preserving attestation.
- The Vehicle Safety Communications (VSC) system from the Department of Transportation in the U.S. embeds short-range transmitters in cars; these transmit status information to other cars in close proximity. For example, if a car executes an emergency brake, all cars in its vicinity are alerted. To prevent message spoofing, all messages in the system are signed by a tamper-resistant chip in each car. (MACs were ruled out for this many-to-many broadcast environment.) Since VSC messages reveal the speed and location of the car, there is a strong desire to provide user privacy so that the full identity of the car sending each message is kept private. Using group signatures, where the group is the set of all cars, we can maintain privacy while still being able to revoke a signing key in case the tamper resistant chip in a car is compromised. Due to the number of cars transmitting concurrently there is a hard requirement that the length of each signature be under 250 bytes

- BBS group signatures - Boneh, Boyen, Shacham, based on the Strong Diffie-Hellman (SDH) assumption in groups with a bilinear map

- In the LE scheme, a user’s public key is a triple of generators u, v, h ∈ G1
- The private key is the exponents x, y ∈ Zp such that u
^{x}= v^{y}= h. - To encrypt a message M ∈ G1, choose random values a, b ∈ Zp, and output the triple (u
^{a}, v^{b}, m · h^{a+b}). - To recover the message from an encryption (T1, T2, T3), the user computes T3/(T1
^{x}· T2^{y}).

- BBS standardization effort by the W3C Verifiable Credentials Working group
- RFC draft: draft-irtf-cfrg-bbs-signatures-01, Internet Engineering Task Force, October 2022
- BBS is also a building block for DAA
- BBS is used by Intel SGX’s EPID protocol

- 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 - Wikipedia

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

- 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

- S/MIME - Wikipedia
- S/MIME (Secure/Multipurpose Internet Mail Extensions) is a standard for public-key encryption and signing of MIME data. S/MIME is on an IETF standards track and defined in a number of documents, most importantly RFC 8551.
- It was originally developed by RSA Data Security, and the original specification used the IETF MIME specification with the de facto industry standard PKCS #7 secure message format.
- Change control to S/MIME has since been vested in the IETF, and the specification is now layered on Cryptographic Message Syntax (CMS), an IETF specification that is identical in most respects with PKCS #7.
- S/MIME functionality is built into the majority of modern email software and interoperates between them. Since it is built on CMS, MIME can also hold an advanced digital signature.
- IETF RFC 8551 S/MIME
- IETF draft pairing-friendly curves
- IETF RFC 5091- Identity-Based Cryptography Standard (IBCS) #1: Supersingular Curve Implementations of the BF and BB1 Cryptosystems
- IETF RFC 6090- Fundamental Elliptic Curve Cryptography Algorithms
- IETF RFC 6507- Elliptic Curve-Based Certificateless Signatures for Identity-Based Encryption (ECCSI)
- IETF RFC 6508- Sakai-Kasahara Key Encryption (SAKKE) - IBE
- IETF RFC 6509- MIKEY-SAKKE: Sakai-Kasahara Key Encryption in Multimedia Internet KEYing (MIKEY)
- IETF RFC 9052- COSE: CBOR Object Signing and Encryption (COSE): Structures and Process - for IOT

- OpenSignature.org - widely supported
- Cloud Signature Consortium (CSC) - remote signatures

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

- IETF RFC 3280 - certificate, CRL, extensions, validation path