Lecture 18

Chapter 5: Authentication

5.1 Introduction

Signatures

private key

Alice and Bob share a secret key $k$.

Message Authentication Codes (MACs)

public key

Any one can verify the signature.

Digital Signatures

Definitions 134.1

A message authentication codes (MACs) is a triple $(Gen, Tag, Ver)$ where

• $k\gets Gen(1^k)$ is a p.p.t. algorithm that takes as input a security parameter $k$ and outputs a key $k$.
• $\sigma\gets Tag_k(m)$ is a p.p.t. algorithm that takes as input a key $k$ and a message $m$ and outputs a tag $\sigma$.
• $Ver_k(m, \sigma)$ is a deterministic algorithm that takes as input a key $k$, a message $m$, and a tag $\sigma$ and outputs "Accept" if $\sigma$ is a valid tag for $m$ under $k$ and "Reject" otherwise.

For all $n\in\mathbb{N}$, all $m\in\mathcal{M}_n$.

Definition 134.2 (Security of MACs)

Security: Prevent an adversary from producing any accepted $(m, \sigma)$ pair that they haven't seen before.

• Assume they have seen some history of signed messages. $(m_1, \sigma_1), (m_2, \sigma_2), \ldots, (m_q, \sigma_q)$.
• Adversary $\mathcal{A}$ has oracle access to $Tag_k$. Goal is to produce a new $(m, \sigma)$ pair that is accepted but none of $(m_1, \sigma_1), (m_2, \sigma_2), \ldots, (m_q, \sigma_q)$.

$\forall$ n.u.p.p.t. adversary $\mathcal{A}$ with oracle access to $Tag_k(\cdot)$,

MACs scheme

$F=\{f_s\}$ is a PRF family.

$f_s:\{0,1\}^{|S|}\to\{0,1\}^{|S|}$

$Gen(1^k): s\gets \{0,1\}^n$

$Tag_k(m)$ outputs $f_s(m)$.

$Ver_s(m, \sigma)$ outputs "Accept" if $f_s(m)=\sigma$ and "Reject" otherwise.

Proof of security (Outline):

Suppose we used $F\gets RF_n$ (true random function).

If $\mathcal{A}$ wants $F(m)$ for $m\in \{m_1, \ldots, m_q\}$. $F(m)\gets U_n$.

Suppose an adversary $\mathcal{A}$ has $\frac{1}{p(n)}$ chance of success with our PRF-based scheme...

This could be used to distinguish PRF $f_s$ from a random function.

The distinguisher runs as follows:

• Runs $\mathcal{A}(1^n)$
• Whenever $\mathcal{A}$ asks for $Tag_k(m)$, we ask our oracle for $f(m)$
• $(m, \sigma)\gets\mathcal{A}^{F(\cdot)}(1^n)$
• Query oracle for $f(m)$
• If $\sigma=f(m)$, output 1
• Otherwise, output 0

$D$ will output 1 for PRF with probability $\frac{1}{p(n)}$ and for RF with probability $\frac{1}{2^n}$.

Definition 135.1(Digital Signature D.S. over $\{M_n\}_n$)

A digital signature scheme is a triple $(Gen, Sign, Ver)$ where

• $(pk,sk)\gets Gen(1^k)$ is a p.p.t. algorithm that takes as input a security parameter $k$ and outputs a public key $pk$ and a secret key $sk$.
• $\sigma\gets Sign_{sk}(m)$ is a p.p.t. algorithm that takes as input a secret key $sk$ and a message $m$ and outputs a signature $\sigma$.
• $Ver_{pk}(m, \sigma)$ is a deterministic algorithm that takes as input a public key $pk$, a message $m$, and a signature $\sigma$ and outputs "Accept" if $\sigma$ is a valid signature for $m$ under $pk$ and "Reject" otherwise.

For all $n\in\mathbb{N}$, all $m\in\mathcal{M}_n$.

Security of Digital Signature

For all n.u.p.p.t. adversary $\mathcal{A}$ with oracle access to $Sign_{sk}(\cdot)$.

5.4 One time security: $\mathcal{A}$ can only use oracle once.

Output $(m, \sigma)$ if $m\neq m$

Security parameter $n$

One time security on $\{0,1\}^n$

One time security on $\{0,1\}^*$

Regular security on $\{0,1\}^*$

Note: the adversary automatically has access to $Ver_{pk}(\cdot)$

One time security scheme (Lamport Scheme on $\{0,1\}^n$)

$Gen(1^k)$: $\mathbb{Z}_n$ random n-bit string

$sk$: List 0: $\bar{x_1}^0, \bar{x_2}^0, \ldots, \bar{x_n}^0$

List 1: $\bar{x_1}^1, \bar{x_2}^1, \ldots, \bar{x_n}^1$

All $\bar{x_i}^j\in\{0,1\}^n$

$pk$: For a strong one-way function $f$

List 0: $f(\bar{x_1}^0), f(\bar{x_2}^0), \ldots, f(\bar{x_n}^0)$

List 1: $f(\bar{x_1}^1), f(\bar{x_2}^1), \ldots, f(\bar{x_n}^1)$

$Sign_{sk}(m):(m_1, m_2, \ldots, m_n)\mapsto(\bar{x_1}^{m_1}, \bar{x_2}^{m_2}, \ldots, \bar{x_n}^{m_n})$

$Ver_{pk}(m, \sigma)$: output "Accept" if $\sigma$ is a prefix of $f(m)$ and "Reject" otherwise.

Example: When we sign a message $01100$, $Sign_{sk}(01100)=(\bar{x_1}^0, \bar{x_2}^1, \bar{x_3}^1, \bar{x_4}^0, \bar{x_5}^0)$ We only reveal the $x_1^0, x_2^1, x_3^1, x_4^0, x_5^0$ For the second signature, we need to reveal exactly different bits.
The adversary can query the oracle for $f(0^n)$ (reveals list0) and $f(1^n)$ (reveals list1) to produce any valid signature they want.