§18 Digital Signatures, Hash-and-Sign Paradigm, and RSA-based Digital Signatures

Digital Signatures

Digital Signature scheme

• A digital signature scheme $\Pi$ is defined by three PPT algorithms $(Gen, Sign, Vrfy)$:
  • $Gen$: Key generation algorithm that on input $1^n$, outputs public-private key pair $(pk, sk)$. Each key has length at least $n$, and $n$ can be determined from $pk, sk$.
  • $Sign$: Signing algorithm that on input private key $sk$ and message $m \in \{0,1\}^*$, outputs a signature $\sigma$. We write this as $\sigma \leftarrow Sign_{sk}(m)$. Note that the message space may depend on $pk$.
  • $Vrfy$: Verification algorithm that on input public key $pk$, message $m$, and signature $\sigma$, outputs a bit $b$ with $b = 1$ indicating validity, and $b = 0$ meaning signature is invalid. We write $b := Vrfy_{pk}(m, \sigma)$.

Digital Signature Experiment $\operatorname{Sig-Forge}_{\mathscr{A}, \Pi}(n)$

• Fix a signature scheme $\Pi = (Gen, Sign, Vrfy)$, an adversary $\mathscr A$, and security parameter $n$. Define the randomized experiment $\operatorname{Sig-Forge}_{\mathscr{A}, \Pi}(n)$ as:

  1. Run $Gen(1^n)$ to obtain keys $(pk, sk)$.
  2. Adversary $\mathscr A$ is given $1^n$, $pk$ and oracle access to $Sign_{sk}( \cdot )$. Let $Q = \{m_1,\ldots, m_q\}$ denote the set of message queries submitted by $\mathscr A$ to the signing oracle.
  3. $\mathscr A$ outputs $(m, \sigma)$.
  4. The adversary $\mathscr A$ succeeds, and the experiment $\operatorname{Sig-Forge}_{\mathscr{A}, \Pi}(n)$ evaluates to $1$, if and only if
     1. $Vrfy_{pk}(m, \sigma) = 1$, and
     2. $m \notin Q$.

• Definition: A Digital Signature scheme $\Pi = (Gen, Sign, Vrfy)$ is existentially unforgeable under an adaptive chosen-message attack, or just secure, if for all PPT adversaries $\mathscr A$, there is a negligible function $\epsilon$ such that

  $$\Pr[\operatorname{Sig-Forge}_{\mathscr{A}, \Pi}(n) = 1] \le \epsilon(n)$$

Hash-and-Sign Paradigm

Hash-and-Sign Digital Signature Scheme

• Let $\Pi = (Gen, Sign, Vrfy)$ be a signature scheme for messages of length $l(n)$, and let $\Pi_H = (Gen_H, H)$ be a hash function with output length $l(n)$.

  Construct a signature scheme $\Pi' = (Gen' , Sign' , Vrfy')$ as follows:

  • $Gen'$: On input $1^n$, run $Gen(1^n)$ to obtain $(pk, sk)$ and run $Gen_H(1^n)$ to obtain $s$. The public key is $\langle pk, s \rangle$, and the private key is $\langle sk, s \rangle$.
  • $Sign'$: On input a private key $\langle sk, s \rangle$ and a message $m \in \{0,1\}^*$, output $\sigma \leftarrow Sign_{sk} (H^s(m))$.
  • $Vrfy'$: On input a public key $\langle pk, s \rangle$, a message $m \in \{0,1\}^*$, and a signature $\sigma$, output $1$ if and only if $Vrfy_{pk} (H^s(m), \sigma) = 1$.

Hash-and-Sign Digital Signature: Security

• Theorem. If $\Pi$ is a secure signature scheme for messages of length $l$ and $\Pi_H$ is collision resistant, then the constructed scheme $Π'$ is a secure signature scheme for arbitrary-length messages.

RSA-based Digital Signatures

Textbook RSA Digital Signature Scheme

• Let $GenRSA$ be a PPT algorithm that on input $1^n$ outputs a modulus $N$ that is the product of two $n$-bit primes (except with negligible probability), along with integers $e, d$, satisfying $ed = 1 \bmod \phi(N)$.

  Define the plain RSA signature scheme $\Pi$ as follows.

  • $Gen$: On input $1^n$, run $GenRSA(1^n)$ to obtain $(N, e, d)$.

    The public key is $\langle N, e\rangle$, and private key is $\langle N, d\rangle$.

  • $Sign$: On input a private key $sk = \langle N, d \rangle$ and a message $m \in \mathbb{Z}^*_N$,

    Output the signature as $\sigma := [m^d \bmod N]$.

  • $Vrfy$: On input a public key $pk = \langle N, e \rangle$, a message $m \in \mathbb{Z}^*_N$, and a signature $\sigma \in \mathbb{Z}^*_N$,

    Output $1$ if and only if $m = [\sigma^e \bmod N]$.

The RSA-FDH Digital Signature Scheme

• Let $GenRSA$ be a PPT algorithm that on input $1^n$ outputs a modulus $N$ that is the product of two $n$-bit primes (except with negligible probability), along with integers $e, d$, satisfying $ed = 1 \bmod \phi(N)$.

  Construct the RSA-FDH signature scheme as follows.

  • $Gen$: On input $1^n$, run $GenRSA(1^n)$ to compute $(N, e, d)$.

    The public key is $\langle N, e\rangle$ and the private key is $\langle N, d\rangle$.

  • $Sign$: On input a private key $\langle N, d \rangle$ and a message $m \in \{0,1\}^*$,

    Output $\sigma := [H(m)^d \bmod N]$.

  • $Vrfy$: On input a public key $\langle N, e\rangle$, a message $m \in \{0,1\}^*$, and a signature $\sigma$,

    Output $1$ if and only if $\sigma^e = H(m) \bmod N$.

Security of the RSA-FDH Signature Scheme

• Theorem. If the RSA problem is hard relative to $GenRSA$ and $H$ is modeled as a random oracle, then the RSA-FDH signature scheme is secure.

— Apr 11, 2023

§18 Digital Signatures, Hash-and-Sign Paradigm, and RSA-based Digital Signatures by Lu Meng is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License. Permissions beyond the scope of this license may be available at About.