# 「Cryptography-MIT6875」: Lecture 10

Today’s topic is Digital Signatures.

**Topics Covered: **

- Motivation for Digital Signatures.
- Definition: EUF-CMA Security
- One-time signatures: Lamport’s Scheme.
- how to sign a single bit, once
- how to sign $n$ bits, once

- Collision-resistant hashing
- how to sign polynomially many bits, once.

# Digital Signatures

## Digital Signatures vs. MACs

### MACs

In Lecture 5, we mentioned the applications of PRF and one of them is authentication.

**Message Authentication Codes**(MAC) can __be evaluated by PRF, the message taken as input.__

MAC gives the **Authenticity** that __Bob is able to ensure the messages came from Alice.__

Yet it needs Alice and Bob to **share a secret key beforehand.**

Then Alice uses the $sk$ to produce the MAC.

### Digital Signatures

Digital Signatures is the **Public-key analog** of MACs.

The goal:

**Only Alice**can produce signatures.- Bob (or
**anyone**else) can verify them.

There is a pair of keys, **secret key** $sk$ and the corresponding **(public) verification key** $vk$.

(Public) verification keys are stored in a “dictionary”.

### Comparison

Signatures | MACs | |
---|---|---|

1 | n uses require n key-pairs | $n$ user require $n^2$ keys |

2 | Publicly Verifiable | Privately Verifiable |

3 | Transferable | Not transferable |

4 | Provides Non-Repudiation | Dose not provide Non-Repudiation |

- Signatures have public verification keys and private secret keys, so $n$ uses require $n$ key-pairs.

But MAC have (private) shared keys beforehand, so $n$ users require $n^2$ keys. - Anyone can verify the signatures using the
**public**$vk$.

But only Bob who has the**secret**key $sk$ can verify the MACs. - Signatures are
**Transferable**. That is, you__can take signatures and show it to others.__ - Signatures provides
**Non-Repudiation**. That is, you__cannot claim that you didn’t sign it__.[*不可抵赖]

Transferability and Non-Repudiation whether they are good properties or bad properties depends on the scenario. It is double edged sword.

## Applications

There are abundant applications of signatures.

**Certificates**, or a public-key directory in practice.- Trusted Certificate Authority(CA), e.g. Verisign, Let’s Encrypt.

- When
**Alice**(=www.google.com) wants to*register*her public (encryption and signing) keys $pk$ and $vk$,**CA**first checks that she is Alice. **CA***issues*a “certificate” $\sigma\leftarrow Sign(SK_{Verisign},Alice||pk||vk)$.

The certificate is essentially the signature.

The**certificate**indicates that $pk$ and $sk$ are indeed Alice’s.

**CA**produces the signature using its sign key $SK_{Verisign}$.**Alice**can later*stores*this certificate to prove she “owns” $pk$ and $sk$.**Browsers***store*$VK_{Verisign}$ and check the certificate.

$VK_{Verisign}$ is the public verification key of CA.

- Bitcoin and other cryptocurrencies.
- I am
**identified**by__my verification key $vk$.__ - When I pay you (your verification key = $vk’$), I sign “$x$ paid to $vk’$” with my $sk$.

- I am

## Definition

The definition of Digital Signatures consists of **a triple of PPT algorithms** $(Gen,Sign,Verify)$.

- $Gen(1^n)\rightarrow (vk,sk)$ running by Alice(signer)
**PPT**Key Generation algorithm__generates a public-private key pair.__ - $Sign(sk,m)\rightarrow \sigma$ running by Alice (signer)
**(possible probabilistic**) Signing algorithm__uses the secret signing key to produce a signature__$\sigma$.

Whether deterministic or probabilistic Signing algorithm makes sense. - $Verify(vk,m,\sigma)\rightarrow Acc(1)/Rej(0)$ running by Bob (any verifier)

Verification algorithm__uses the public verification key to check__the signature $\sigma$**against**a message $m$.

*Correctness: *

For all $vk,sk,m$: $Verify(vk,m,Sign(sk,m))=accept$.

## EUF-CMA Security

Define the adversary first.

The adversary __after seeing signatures of many messages__, should **not be able** to produce a signature of any **new message**.

**Adversary: **

- Power of adversary:
**Chosen-message attack**

The adversary can request for, and obtain, signatures__of (poly. many) messages__$m_1,m_2,\dots$ - Goal of adversary:
**Existential Forgery**

The adversary wins if she__produces a signature__of any**new**message $m^*\notin \{m_1,m_2,\dots \}$.

Then we give **Existentially Unforgeable against a Chosen Message Attack (EUF-CMA) security** by a game.

**Game :**

- The
**Challenger**generates a public-private key pair $(vk,sk)$ and sends the public verification key $vk$ to Eve. **Eve**can__request for poly. many messages__$\{m_1,m_2,\dots\}$ and__obtain the corresponding signatures__$\{\sigma_1,\sigma_2,\dots\}$.**Eve**produce a signature $\sigma^*$__against a new message__$m^*\notin \{m_1,m_2,\dots\}$.

The challenger gives Eve a lot of signatures.

Now Eve wants to forge a signature of other message right.

We say that she wins if she **produces a signature right** of __even one message that was not signed already.__

We call this an **existential forgery** because there __exists a $m^*$ not in the set__ for which she produces a signature.

It’s a very strong definition.

But the definition **dose not prevent** the adversary from producing **a new signature** for the **same message.**

Yet she dose not win.

In other words, it’s consistent with the definition to __allow the adversary to produce a new signature for the same message.__

We can make the job easier for adversary. She **wins as well** if she __produces a new signature for the same message.__

Then we can get **strong EUF-CMA definition.**

So the stronger adversary, the stronger security by definition.

# Lamport (One-time) Signatures

In this section, we introduce a beautiful signature, **Lamport Signature.**

It’s **One-time signature** sort of like One-time Pads.

The **one-time signatures** means that the __adversary gets a signature of some message__ **once**, a single message, and she __should not be able to produce a signature of any other different message.__

## How to sign a bit

We only use the signing key to **sign once** and we are __really signing a bit.__

- $Gen(1^n)\rightarrow (SK,VK)$
- Signing Key $SK:[x_0,x_1]$

where $x_0,x_1$**are both $n$-bit string.** - Verification Key $VK:[y_0=f(x_0),y_1=f(x_1)]$

where $f$ is a**OWF**.

- Signing Key $SK:[x_0,x_1]$
- $Sign(SK,b)\rightarrow \sigma$ where $b$ is a
**bit**- The signature is $\sigma=x_b$.

- $Verify(VK,b,\sigma)$
- Check if $f(\sigma)\overset ? = y_b$

The **signing keys $SK$** are __two random $n$-bit string__ and the **verification keys** $VK$ are the __corresponding values of OWF__, i.e. the signing keys are **images** of verification keys.

The game in Lamport (One-time) Signatures **differs** from that __Eve only gets a signature of a single message.__

If $b=0$, the challenger gives Eve $x_0$, the signature of $0$, and Eve wants to **forge the signature of** $1$.

So the task of adversary is producing a signature of $1$.

That’s $x_1$. She **cannot** do it __because $x_1$ is random.__

**Claim :**

Assuming $f$ is a **OWF**, no PPT adversary can produce a signature of $\bar{b}$ **given** a signature of $b$.

The intuition of proof is easy.

There’s no way Eve can produce $x_1$ unless she can invert the $y_1$ she have.

## How to sign n bits

We can use the signing keys to **sign $n$ bits, once.**

Just repeat it.

- $Gen(1^n)\rightarrow (SK,VK)$
- Signing Key $ SK:\left[\begin{array}{c}x_{1,0},x_{2,0},\dots, x_{n,0}\\ x_{1,1},x_{2,1} ,\dots, x_{n,1}\end{array} \right]$

where $x_{\cdot,\cdot}$ is $n$-bit random string and**each column**is__a pair-key for one bit.__ - Verification Key $VK:\left[\begin{array}{c}y_{1,0},y_{2,0},\dots, y_{n,0}\\ y_{1,1},y_{2,1} ,\dots, y_{n,1}\end{array} \right]$

where $f$ is a OWF and $y_{i,c}=f(x_{i,c})$.

- Signing Key $ SK:\left[\begin{array}{c}x_{1,0},x_{2,0},\dots, x_{n,0}\\ x_{1,1},x_{2,1} ,\dots, x_{n,1}\end{array} \right]$
- $Sign(SK,\vec m)\rightarrow \vec\sigma$ where
__$m$ is a $n$-bit message__$(m_1,\dots, m_n)$.- The signature is $\vec \sigma=(x_{1,m_1},\dots, x_{n,m_n})$.

- $Verify(VK,\vec m,\vec\sigma)$
- Check if $\forall i:f(\sigma_i)\overset ? = y_{i,m_i}$.

In the game, Eve can **request for a signature once** of any $n$-bit message $m$ and she **wants to forge the signature** of a different message $m’\ne m$.

There are two claims.

**Claim 1:**

Assuming $f$ is a **OWF**, no PPT adversary can produce a signature of $m’$ **given a signature of a single** message $m\ne m’$.

**Claim 2:**

The adversary can forge signature on any message **given the signatures on (some) two messages.**

We only give the proof of Claim 1.

Claim 2 can be comprehended easily after proving Claim1.

**Proof for Claim 1: **

Suppose for the **contradiction** that __there is a adversary forging a signature__ of $m’$ __given a signature of a single message__ $m$ s.t. $m’\ne m$.

We want to construct a **OWF Inverter for $y$** so we need to interact with the forger.

*Interaction with the forger: *

**Inverter**gives the*verification keys*$VK$ to the forgery.- The
**forger**request for a signature of a single message $m$. **Inverter**produces the signature $\sigma$ she wants.- Then the
**forger**promises to give a signature $\sigma’$ against a new message $m’$

The **key idea** is we can take $y$ into $VK$ and plop it into one of the two slots in one column.

The **thing to notice** is that __there is at least one different bit between $m$ and $m’$.__

__Note:__

- The message $m$ is what the
**forger**wants to__obtain its signature__ - The message $m’$ is what the
**forger**wants to__forge its signature.__

For simplicity, we **suppose** there is __only one different bit__ between $m$ and $m’$.

*messages $m$ and $m’$ are known in advance: *

Suppose the Inverter knows $m$ and $m’$in advance.

For simplicity, suppose $m=00\dots 0$ and $m’=10\dots 0$.The Inverter wants to get the inverse of $y$ against the OWF $f$.

So the Inverter

**interacts with the forger.**The Inverter samples $SK$ and

$$ VK=\left[\begin{array}{c}f(x_{1,0}) &,f(x_{2,0}),\dots, f(x_{n,0})\\ y &,f(x_{2,1}) ,\dots, f(x_{n,1})\end{array} \right] $$__generates the verification keys__(put $y$ into one slot as follows)where $x_{\cdot,\cdot}$ is

**known to the Inverter.**The

**forger**requests for the signature of $m=00\dots 0$.The

**Inverter**produces the signature $\sigma=(x_{1,0},\dots,x_{n,0})$.The

**forger**promises to produce the signature on $m’=10\dots0$ from the contradiction**which has the inverse**of $y$.

Done.

However, the Inverter **dosen’t know the two messages in advance.**

The Invert only knows there is one different bit between $m$ and $m’$.

So the Inverter could **guess it.**

*messages $m$ and $m’$ are unknown in advance: *

The Inverter

**guesses**the__different bit locates in $i$-th bit__right**w.p.**$1/n$.Suppose the Inverter

$$ VK=\left[\begin{array}{c}f(x_{1,0}) ,\dots ,&y&,\dots, f(x_{n,0})\\ f(x_{1,1}) ,\dots ,&f(x_{i,1})& ,\dots, f(x_{n,1})\end{array} \right] $$**plants the trap**$y$ into the slot $(i,0)$, $i$-th column and $0$-th row.

Then the generated**verification keys**is as follows.where $x_{\cdot,\cdot}$ is

**known to the Inverter.**In the forger’s point of view, when she looks at the verification keys $VK$, she

**has no information about where the trap is.**There are

**two events**that could happen__even if $m$ differs from $m’$ in $i$-th bit.__- The message $m$
__hits the trap__while the $m’$ dose not hit the trap. - The message $m$
__dosen’t hit the trap__while the $m’$ hits the trap.

- The message $m$
The Inverter can

**only handle**with the second event.

The message $m$ hits the opposite location to the trap while the $m’$ hits the trap.- The
**Inverter**is__able to give the signature of__$m$, i.e. $(\dots,x_{i,1},\dots)$ - The
**forger**promises to__produce the signature of $m’$from the contradiction__, which**have the inverse of**$y$. - Otherwise, the forger gives something that the Inverter already has known.

- The
So the

**probability of inverting right**is $\varepsilon/2n$ if the advantage of forging is non-negligibly $\varepsilon$.

The $1/n$ is the probability of__guessing the location of different bit__and the $1/2$ is the probability of__guessing whether $m$ hits the trap.__Done.

Besides, **Claim 2** says that __once I give you the two signatures__, I am actually __giving you all the inverses__ and you can produce signatures of any message you want.

This violates one-wayness.

So far, the length of message is limited by the size of verification keys.

Before proceeding to the next question that how to sign poly. many bits, we **take a detour** in __collision-resistant hash function.__

## Detour: Collision-Resistant Hash Functions

A **compressing function** $h:\{0,1\}^m\rightarrow \{0,1\}^n$ (where $m>n$ ) for which it is __computationally hard to find collisions.__

It compresses the bits sort of the opposite of PRG.

*Definition: *

$h$ is **collision-resistant** if for every PPT algorithm $A$, there is a negligible function $\mu$ s.t.

**In theory**, we like to talk about __families of functions__ to handle non-uniform adversaries (who could have hardcoded collision for the fixed function $h$).

A **compressing family of functions** $\mathcal{H}=\{\{0,1\}^m\rightarrow \{0,1\}^n\}$ (where $m>n$) for which it is computationally hard to find collisions.

*Collision-Resistant Definition: *

$\mathcal{H}$ is collision-resistant if for every PPT algorithm $A$, there is a negligible function $\mu$ s.t.

$$ \operatorname{Pr}_{h\gets \mathcal{H}}[A(1^n)=(x,y):x\ne y, h(x,y)]=\mu(n) $$## How to sign poly. many bits

Back to the question that how to **sign poly. many bits** with __a fixed verification key.__

The **key idea** is hashing the message into $n$ bits and __sign the hash.__

- $Gen(1^n)\rightarrow (SK,VK)$
- Signing Key $SK:\left[\begin{array}{c}x_{1,0},x_{2,0},\dots, x_{n,0}\\ x_{1,1},x_{2,1} ,\dots, x_{n,1}\end{array} \right]$

where $x_{\cdot,\cdot}$ is $n$-bit random string and each column is a pair-key for one bit. - Verification Key $VK:\left[\begin{array}{c}y_{1,0},y_{2,0},\dots, y_{n,0}\\ y_{1,1},y_{2,1} ,\dots, y_{n,1}\end{array} \right]$

where $f$ is a OWF and $y_{i,c}=f(x_{i,c})$. **Sample**$h\gets \mathcal{H}$.

- Signing Key $SK:\left[\begin{array}{c}x_{1,0},x_{2,0},\dots, x_{n,0}\\ x_{1,1},x_{2,1} ,\dots, x_{n,1}\end{array} \right]$
- $Sign(SK,\vec m)\rightarrow \vec\sigma$ where $m$ is a $n$-bit message $(m_1,\dots, m_n)$.
**Compute the hash**$z=h(m)$.- The signature is $\vec \sigma=(x_{1,z1},\dots, x_{n,z_n})$.

- $Verify(VK,\vec m,\vec\sigma)$
**Recompute the hash**$z=h(m)$- Check if $\forall i:f(\sigma_i)\overset ? = y_{i,z_i}$.

**Claim :**

Assuming $f$ is a **OWF** and $\mathcal{H}$ s a **collision-resistant family**, no PPT adversary can produce a signature of $m’$ given a signature of a single $m\ne m’$.

We only give the idea of proof.

*Intuition of Proof: *

Suppose for the contradiction.

There are two possibilities.

- Either the adversary picked $m’$ s.t. $h(m’)=h(m)$, in which case she
**violated collision-resistance**of $\mathcal{H}$. - Or she produced a Lamport signature on a “message” $z’\ne z$, in which case she
**violated one-time security**of Lamport, and therefore the one-wayness of $f$.

「Cryptography-MIT6875」: Lecture 10