CRYPTOGRAPHY - Signatures

Contents

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.

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.

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.

Security

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 https://www.cosic.esat.kuleuven.ac.be/nessie/deliverables/D20-v2.pdf

Signature transformation types

Factorisation

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

DH-based (Diffie-Hellman)

Based on the DH computational 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?

Hash based (relevant for PQ)

One-time signatures (OTS)

Other hash based signatures

Few-time signatures

Few-times signatures schemes (FTS) include:

Lattice based (relevant for PQ)

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.

Other signature types

Blind signatures

Group signatures

Anonymous signatures

Threshold signatures

Signature formats

RSA PKCS

IETF CMS

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