Skip to content

Digital Signatures

links: AC2 TOC Digital Signatures - Index

Basics

Digital signatures solve the problem of authenticated communication between Alice and Bob

  • For signing a message, Alice uses her private key
  • For verifying a signed message, Bob uses Alice’s public key

If the verification succeeds, and provided that

  • only Alice knows her private key
  • Bob uses Alice’s public key

then Bob knows that the message originates from Alice and has not been modified during transmission. In other words, digital signatures provide sender authenticity, message integrity, and non-repudiation.

Note that digital signatures are publicly verifiable, i.e., anyone (not only Bob) can verify that s is a valid signature for \(m\).

Scheme

A digital signature scheme consists of a message space \(M\) and three (randomised) polynomial-time algorithms:

  • Key generation: \((pk, sk) ← keyGen()\)
  • Signature generation: \(s ← sign_{sk}(m)\)
  • Verification: \(v := verify_{pk}(m, s)\), where \(v ∈ {0, 1}\)

The set of all valid signatures generated by \(sign_{sk}(m)\) is called signature space \(S\)

Applications

  • Web server authentication
  • Secure e-mail
  • Signed documents
  • Digital contracts
  • Code signing (software updates, drivers, etc.)
  • Digital certificates
  • Time-stamping service
  • Identification schemes

Authenticated Private Communication?

As we can sign our messages and encrypt data using the counterparts public key we achieved authenticated private communication. But there are two things we need to be aware of in order to not compromise security:

Alice wants to send an encrypted message to Bob:

First there is a public key exchange in both directions.

Man in the Middle Attack

A man in the middle attacker can intersect the public key of Bob and send their own public key to Alice. Alice will then encrypt the message with the public key of the attacker and the attacker can decrypt the message with their private key. The attacker can then send the message to Bob.

Combination of encrypt and sign

If Alice does the following:

  • \(c \leftarrow enc_{pkB}(m)\)
  • \(s \leftarrow sign_{skA}(m)\)

The message \(m\) can be leaked as a signature has different security requirement than a ciphertext. It could be possible to learn \(m\) from \(s\).

See here: Authenticated Encryption Schemes

Security and Adversary Models

  • We consider probabilistic polynomial-time (PPT) adversaries
  • Existentially Unforgeability (EUF)
    • It should not be possible for an attacker, even if they have seen a number of valid message-signature pairs, to forge a valid signature for even a single additional message.
  • Chosen-Message Attack (CMA)
    • The adversary can ask a signing oracle to produce valid signatures \(s′ ← sign_{sk}(m′)\) for arbitrary messages \(m′ \neq m\).

EUF-CMA

  • EUF-CMA = Existentially unforgeability under chosen-message attack (standard security model for digital signatures)

links: AC2 TOC Digital Signatures - Index