D3.2: A study on PKI and biometrics

Title: DIGITAL SIGNATURE SCHEMES: TECHNICAL ASPECTS

Digital signature schemes are cryptographic processes which provide similar functions for digital messages as handwritten signatures do for messages on paper: They guarantee the authenticity of a message to its recipients (data origin authentication), and the recipient can prove this authenticity to third parties, such as courts, at a later date (non-repudiation). Hence, digital signatures are necessary wherever legal certainty is required in digital message exchange. 

An essential requirement for a useful deployment of digital signatures is the availability of a Public Key Infrastructure (PKI). Validating a digital signature requires an authenticated public key from the issuer. Certificates (which roughly speaking are signed public keys) organised within a PKI allow the construction of relationships of trust without authenticating each key manually. 

Usually, a digital signature consists of three algorithms: The (probabilistic) key generation algorithm generates a public/secret key pair. The signing algorithm gets the secret key and the message to be signed and outputs the signature. The verification algorithm gets the signature (and sometimes the original message) and outputs whether the verification succeeded or not. Digital signature schemes can be categorised in two general classes: digital signature schemes with appendix require the original message as input to the verification algorithm and digital signature schemes with message recovery do not. 

Security of Digital Signature Schemes

Digital signature schemes are usually based on trapdoor one-way functions like RSA or ElGamal. However, the RSA scheme and the ElGamal scheme are not ‘provably secure’ since they are subject to existential forgery, e.g., it is easy to create new valid message-signature pairs. Since the appearance of public key cryptography, a significant line of research has tried to provide provable security for cryptographic protocols and schemes. In the area of computational security, proofs have been given in the asymptotic framework of complexity theory. However, these are not absolute proofs since cryptography ultimately relies on the existence of one-way functions and the P vs. NP question. Instead, there are computational reductions to and from well known (but not proven) problems from number theory such as factoring, the discrete logarithm problem or the root extraction problem.

The first signature scheme proven to be secure against a very general attack, the so-called adaptive chosen-message attack, was been proposed by Goldwasser, Micali and Rivest in [GMR88]. Since then many provable and efficiently employable schemes have been proposed. 

Forward-Secure Signature Schemes

The goal of forward security is to protect some aspects of signature security against exposure of the secret signing key, but in a simple way. In particular, it requires no distribution of protected storage devices, nor does it increase key management costs. 

However, obviously we cannot expect total security. Once a signing key is exposed, the attacker can forge signatures. The idea of forward security is simply that a distinction can be made between the security of documents pertaining to (meaning dated in) the time prior to key exposure and those pertaining to the period after key exposure.
A forward secure signature scheme is given in [BEL99].