47.06.04 · theoretical-cs / 06-cryptographic-foundations

Digital Signatures and Collision-Resistant Hash Functions

shipped3 tiersLean: none

Anchor (Master): Arora and Barak 2009 Computational Complexity: A Modern Approach (Cambridge) Ch. 9-10; Naor and Yung 1989 Universal One-Way Hash Functions and Their Cryptographic Applications (STOC); Rompel 1990 One-Way Functions are Necessary and Sufficient for Secure Signatures (STOC)

Intuition Beginner

A handwritten signature on a document proves you approved it. Anyone can see the signature and compare it to a known sample. A digital signature does the same thing for electronic messages: you sign with a private key, and anyone verifies with your public key.

The key difference from a physical signature is that a digital signature cannot be forged. If you sign message $m$ with your private key $s k$ , producing signature $σ$ , then no one can produce a valid signature on a different message $m^{'}$ without knowing $s k$ . This is guaranteed not by the difficulty of imitating handwriting but by the computational hardness of inverting a one-way function.

Hash functions are the compression workhorse of cryptography. A hash function takes an input of any length and produces a fixed-length output, like a fingerprint. A collision-resistant hash function has the property that no one can find two different inputs with the same output. This seems simple, but it is remarkably useful: you can sign the hash of a message instead of the message itself, compressing arbitrarily long messages to a fixed size before signing.

Together, signatures and hash functions form the backbone of digital trust. Every time you visit a secure website, your browser verifies a digital signature on the site's certificate. Every time you install a software update, the operating system verifies a signature on the update. And every one of those signatures involves a hash function.

Visual Beginner

Digital signature workflow:

  Signer (Alice):                    Verifier (Bob):
  Private key sk                     Public key vk
    
  Message m                          Message m
  Hash: h = H(m)                     
  Sign: s = Sign(sk, h)              
                                     Receive (m, s)
                                     Hash: h' = H(m)
                                     Verify: Verify(vk, h', s)?
                                     Yes -> authentic
                                     No  -> forged

Hash function collision resistance:

  Input space: 2^256 possible inputs (or more)
  Output space: 2^256 possible hashes
  
  Finding x, y with H(x) = H(y) by brute force:
    Birthday attack: ~2^128 trials needed
    (This is infeasible -- 2^128 ~ 10^38)

Primitive	Input	Output	Security property
Hash function $H$	Any-length message	Fixed-length digest	Collision resistance
Signature $Sign (s k, m)$	Message + private key	Signature $σ$	Unforgeability
Verification $Verify (v k, m, σ)$	Message + public key + sig	Accept/Reject	Completeness

Worked example Beginner

We illustrate RSA-based digital signatures with toy parameters. Alice uses RSA with $p = 7, q = 13$ , so $N = 91$ and $ϕ (N) = 72$ . She picks $e = 5$ (coprime to 72) and computes $d = 5^{- 1} mod 72$ . Since $5 \times 29 = 145 = 2 \times 72 + 1$ , $d = 29$ .

Public key: $(N, e) = (91, 5)$ . Private key: $d = 29$ .

Signing. Alice wants to sign the message $m = 42$ . She computes the signature $σ = m^{d} mod N = 4 2^{29} mod 91$ .

Using repeated squaring: $4 2^{2} \equiv 35 (mod 91)$ . $4 2^{4} \equiv 42$ . $4 2^{8} \equiv 35$ . $4 2^{16} \equiv 42$ .

Now $4 2^{29} = 4 2^{16} \times 4 2^{8} \times 4 2^{4} \times 42$ . Stepwise: $42 \times 35 \equiv 14$ . $14 \times 42 \equiv 42$ . $42 \times 42 \equiv 35$ . So $σ = 35$ .

Verification. Bob computes $3 5^{5} mod 91$ . $3 5^{2} \equiv 42$ . $3 5^{4} \equiv 35$ . $3 5^{5} \equiv 35 \times 35 = 1225 \equiv 42 = m$ . Verified.

Check your understanding Beginner

Formal definition Intermediate+

Definition (digital signature scheme). A digital signature scheme is a triple of PPT algorithms $(K ey G e n, S i g n, V er i f y)$ :

$K ey G e n (1^{n}) \to (v k, s k)$ : outputs a verification key and signing key.
$S i g n (s k, m) \to σ$ : outputs a signature on message $m$ .
$V er i f y (v k, m, σ) \to {0, 1}$ : outputs accept or reject.

Correctness: $V er i f y (v k, m, S i g n (s k, m)) = 1$ for all $m$ .

Definition (EUF-CMA security). A signature scheme is existentially unforgeable under chosen-message attack if for every PPT adversary $A$ :

Pr [Verify (v k, m^{*}, σ^{*}) = 1 \land m^{*} \in / Q] \leq negl (n)

where $(v k, s k) \leftarrow K ey G e n (1^{n})$ , $A$ has oracle access to $S i g n (s k, \cdot)$ with query set $Q$ , and $(m^{*}, σ^{*})$ is $A$ 's output.

Definition (collision-resistant hash function). A family of functions $H = {h_{k} : {0, 1}^{*} \to {0, 1}^{n}}_{k \in {0, 1}^{n}}$ is collision-resistant if for every PPT algorithm $A$ :

k Pr [A (k) = (x, y) : x \neq = y \land h_{k} (x) = h_{k} (y)] \leq negl (n) .

Definition (Merkle-Damgard construction). Given a compression function $f : {0, 1}^{2 n} \to {0, 1}^{n}$ , the Merkle-Damgard hash of a message $m = m_{1} ∥ m_{2} ∥ \dots ∥ m_{l}$ (with appropriate padding) is:

h_{0} = I V, h_{i} = f (h_{i - 1}, m_{i}), H (m) = h_{l} .

Counterexamples to common slips

"Collision resistance means no two inputs have the same hash." By the pigeonhole principle, collisions always exist (the input space is larger than the output space). Collision resistance means finding a collision is computationally infeasible, not that collisions do not exist.
"A signature proves who sent the message." A signature proves that someone with the private key signed it. The connection to identity (who holds the private key) is established by a public-key infrastructure (PKI), not by the signature scheme itself.
"MD5 and SHA-1 are collision-resistant." Both have been broken: Wang et al. (2004) found collisions in MD5, and Stevens et al. (2017) found collisions in SHA-1. SHA-256 and SHA-3 are the current recommendations.

Key theorem with proof Intermediate+

Theorem (RSA-FDH is EUF-CMA in the random oracle model). The RSA Full-Domain Hash signature scheme—where $S i g n (s k, m) = H (m)^{d} mod N$ and $V er i f y (v k, m, σ)$ checks $σ^{e} mod N = H (m)$ —is EUF-CMA secure in the random oracle model assuming the RSA problem is hard.

Proof sketch. Let $A$ be an EUF-CMA adversary that makes $q_{H}$ hash queries, $q_{S}$ signing queries, and forges with probability $ε$ . We build an algorithm $B$ that solves the RSA problem: given $(N, e, y)$ , find $x$ with $x^{e} \equiv y (mod N)$ .

$B$ sets $v k = (N, e)$ and simulates the random oracle and signing oracle for $A$ :

Random oracle simulation. $B$ maintains a table $H$ of query-response pairs. For each new query $m$ : with probability $1 - q_{S} / q_{H}$ , set $H (m) = y \cdot r^{e} mod N$ for random $r$ (an RSA challenge embedded in the hash). With probability $q_{S} / q_{H}$ , set $H (m) = r^{e} mod N$ for random $r$ (a "signable" value). Record $(m, r, type)$ .

Signing oracle simulation. When $A$ asks for a signature on $m$ : if $m$ was a hash query of "signable" type, return $r$ (since $r^{e} = H (m)$ , so $S i g n = H (m)^{d} = (r^{e})^{d} = r$ ). If $m$ was not queried, handle it fresh as signable.

Forgery extraction. $A$ outputs $(m^{*}, σ^{*})$ with $σ^{\aste} = H (m^{*}) mod N$ . If $m^{*}$ was a hash query where $B$ embedded the RSA challenge: $H (m^{*}) = y \cdot r^{e}$ , so $σ^{*} = (y \cdot r^{e})^{d} = y^{d} \cdot r$ . Then $y^{d} = σ^{*} / r mod N$ , and $B$ outputs $(σ^{*} \cdot r^{- 1})^{1} = y^{d}$ as the RSA solution.

The probability $m^{*}$ is the challenge-embedded query is at least $(1/ q_{H}) (1 - q_{S} / q_{H}) \approx ε / q_{H}$ , giving a non-negligible RSA solver. $□$

Bridge. The RSA-FDH construction is the foundational reason hash-then-sign works: the hash function randomises the message before the RSA operation, preventing algebraic attacks on structured messages, and this builds toward the Merkle-Damgard construction that extends fixed-size compression to arbitrary-length hashing. The central insight is that the hash function serves dual purposes—compressing the message to the RSA domain and randomising it to prevent exploitation of RSA's multiplicative structure—and this is exactly the pattern that appears again in 47.06.02 where hashing randomises the plaintext before RSA encryption (OAEP padding). Putting these together with the one-way function theory of 47.06.01 shows that collision-resistant hash functions can be built from one-way functions (via Naor-Yung UOWHFs), and this is the bridge between the abstract OWF and the concrete hash-then-sign paradigm.

Exercises Intermediate+

Exercise 4 (medium, symbolic).

Prove that the Merkle-Damgard construction preserves collision resistance. Specifically, show that a collision in $H$ yields a collision in the compression function $f$ .

Answer

Suppose $H (m) = H (m^{'})$ with $m \neq = m^{'}$ . Let $m = m_{1} ∥ \dots ∥ m_{l}$ and $m^{'} = m_{1}^{'} ∥ \dots ∥ m_{l^{'}}^{'}$ . After length padding, both have lengths encoded in their final blocks.

Working backwards: $H (m) = f (h_{l - 1}, m_{l}) = H (m^{'}) = f (h_{l^{'} - 1}^{'}, m_{l^{'}}^{'})$ . If $(h_{l - 1}, m_{l}) \neq = (h_{l^{'} - 1}^{'}, m_{l^{'}}^{'})$ , this is a collision in $f$ . If they are equal, then $h_{l - 1} = h_{l^{'} - 1}^{'}$ and $m_{l} = m_{l^{'}}^{'}$ . Since $m_{l} = m_{l^{'}}^{'}$ and the length padding ensures the final blocks encode the same length, we must have $l = l^{'}$ . Continue backwards: $f (h_{l - 2}, m_{l - 1}) = f (h_{l - 2}^{'}, m_{l - 1}^{'})$ . Again, if inputs differ, this is an $f$ -collision. If equal, continue. This process must eventually find an $f$ -collision because $m \neq = m^{'}$ means at least one message block differs. At the first position where blocks differ (from the front), the chaining values going in are equal (by the forward propagation from $I V$ ), so $f$ is evaluated on different inputs giving the same output—a collision. Rubric: full credit for the backwards-chaining argument.

Exercise 6 (hard, symbolic).

The Naor-Yung construction builds a universal one-way hash function (UOWHF) from any one-way permutation. A UOWHF is weaker than a collision-resistant hash: the adversary must specify their target input $x$ before seeing the hash key. Construct a UOWHF from a one-way permutation $f$ .

Answer

Given a one-way permutation $f : {0, 1}^{n} \to {0, 1}^{n}$ and the Goldreich-Levin hard-core predicate $h (x, r) = ⟨ x, r ⟩$ :

Define $G_{k} : {0, 1}^{2 n} \to {0, 1}^{n}$ by $G_{k} (x, r) = (f^{(1)} (x), h (x, r), h (f (x), r), \dots, h (f^{(k - 1)} (x), r))$ compressed to $n$ bits using pairwise-independent hashing.

For UOWHF security: the adversary commits to $x$ before seeing the key $k$ . The key determines which bits of the PRG output to reveal. By the hard-core property, finding $y \neq = x$ with $G_{k} (y) = G_{k} (x)$ requires inverting $f$ (since the hard-core bits for $y$ and $x$ would need to agree on all revealed positions, which happens with negligible probability unless $y$ is related to $x$ in a way that allows inversion).

More precisely: Naor and Yung's construction uses a pairwise-independent hash family to compress. The key selects a hash function $g$ from the family, and the UOWHF is $g \circ P R G$ . The adversary, having committed to $x$ , must find $y$ with $g (P R G (y)) = g (P R G (x))$ . By pairwise independence, this requires $P R G (y) = P R G (x)$ (with high probability over $g$ ), which requires finding a collision in the PRG. But the PRG's pseudorandomness property implies collision resistance against adversaries who commit to one input first. Rubric: full credit for the PRG-based construction and the target-preimage security argument.

Exercise 7 (hard, symbolic).

Prove that EUF-CMA security of a signature scheme implies that the scheme is also secure against random-message attacks (where the adversary sees signatures on random messages, not chosen ones).

Answer

Let $(K ey G e n, S i g n, V er i f y)$ be EUF-CMA secure. Suppose for contradiction it is not secure against random-message attacks: there exists a PPT adversary $A^{'}$ that, given signatures on random messages $m_{1}, \dots, m_{q}$ (each chosen uniformly), forges a signature on a new message $m^{*}$ with non-negligible probability $ε$ .

We build an EUF-CMA adversary $A$ : receive $v k$ , submit random messages $m_{1}, \dots, m_{q}$ to the signing oracle (these are uniformly random, matching the random-message attack model), receive signatures $σ_{1}, \dots, σ_{q}$ , and feed them to $A^{'}$ . If $A^{'}$ outputs a valid forgery $(m^{*}, σ^{*})$ , $A$ outputs it.

The distribution of messages seen by $A^{'}$ is identical to the random-message attack setting (both are uniform). $A$ 's queries are all to the signing oracle, which is allowed in EUF-CMA. So $A$ forges with the same probability $ε$ as $A^{'}$ , contradicting EUF-CMA security.

This is a direct reduction: the random-message attack is a restricted version of the chosen-message attack (fewer adversarial capabilities), so EUF-CMA security is strictly stronger. Rubric: full credit for the reduction argument.

Exercise 8 (hard, short answer).

Explain why length-extension attacks are possible on the basic Merkle-Damgard construction and how SHA-3 (Keccak) prevents them.

Answer

In the basic Merkle-Damgard construction, $H (m ∥ m^{'})$ can be computed from $H (m)$ and the length of $m$ , without knowing $m$ : simply initialise the chaining value to $H (m)$ and continue hashing $m^{'}$ . This is a length-extension attack: given $H (m)$ and $∣ m ∣$ , one can compute $H (m ∥ padding ∥ m^{'})$ for any $m^{'}$ .

This is problematic for MAC constructions like $M A C_{k} (m) = H (k ∥ m)$ : an attacker who sees $M A C_{k} (m)$ can compute $M A C_{k} (m ∥ padding ∥ m^{'})$ without knowing $k$ .

SHA-3 (Keccak) uses the sponge construction instead of Merkle-Damgard. The sponge absorbs the message in blocks and then squeezes output. The internal state after absorbing the message is not exposed as the hash output; instead, additional permutation rounds are applied before squeezing. This breaks the length-extension property because the output does not directly reveal the internal state that would be needed to continue hashing.

Lean formalization Intermediate+

Mathlib has no formalization of digital signature schemes, EUF-CMA security, or the Merkle-Damgard construction. The hash function framework in Mathlib is limited to basic function composition. A natural formalization target would be the Merkle-Damgard collision-resistance preservation proof, using Mathlib's List, Finset, and function composition structures. The EUF-CMA security proof would require modelling adversaries and oracles, which is beyond Mathlib's current scope. This unit ships without a lean_module.

Advanced results Master

Three results extend the signature and hash function framework.

Result 1 (Rompel's theorem: OWF implies signatures). Rompel (1990) proved that one-way functions are necessary and sufficient for the existence of EUF-CMA secure signature schemes. The sufficiency direction constructs a UOWHF from any OWF (via the Naor-Yung technique), then builds a tree-based signature scheme where each node in a Merkle tree authenticates its children. The construction is polynomial-time but impractical due to large constants. Practical signature schemes (RSA, DSA, EdDSA) use specific number-theoretic assumptions for efficiency ^{[Rompel 1990]}.

Result 2 (sponge construction and SHA-3). The Keccak sponge construction (Bertoni, Daemen, Peeters and Van Assche, 2011), selected as SHA-3, uses a fixed-length permutation $f : {0, 1}^{b} \to {0, 1}^{b}$ (where $b = 1600$ for SHA-3). The message is absorbed into the state in $r$ -bit blocks (rate $r$ ), with $c = b - r$ bits of capacity untouched. The output is squeezed from the state. The security proof shows that distinguishing the sponge output from random requires either inverting the permutation or finding a collision in the capacity part, both of which are assumed to be hard ^{[Arora-Barak Ch. 9]}.

Result 3 (aggregate and multi-signatures). Boneh, Gentry, Lynn and Shacham (2003) introduced aggregate signatures, where $n$ signatures on $n$ different messages from $n$ different signers can be combined into a single short signature. This is achieved using bilinear pairings on elliptic curves: the pairing equation $e (g^{a}, g^{b}) = e (g, g)^{ab}$ allows verification of multiple signatures simultaneously. Aggregate signatures are used in blockchain systems (certificates, block headers) to compress authentication data ^{[Arora-Barak Ch. 9-10]}.

Synthesis. Digital signatures and collision-resistant hash functions form the authentication layer of cryptography: signatures provide unforgeable attestation, and hash functions provide the compression and randomisation that make signatures efficient and secure. The central insight is that the hash-then-sign paradigm reduces the security of the signature scheme to two independent assumptions (collision resistance of the hash and security of the underlying primitive), and this builds toward Rompel's theorem showing that the entire construction chain rests on one-way functions. This is exactly the pattern that appears again in 47.06.01 where OWFs provide the foundation, and it generalises to the full cryptographic stack: OWFs yield hash functions, hash functions yield signatures, and signatures yield authentication and non-repudiation. Putting these together with the zero-knowledge proofs of 47.06.03 shows that the Fiat-Shamir heuristic converts ZK identification protocols into signatures, bridging the privacy and authentication layers of cryptography.

Full proof set Master

Proposition 1 (Merkle-Damgard preserves collision resistance). If $f : {0, 1}^{2 n} \to {0, 1}^{n}$ is a collision-resistant compression function, then the Merkle-Damgard hash $H_{f}$ built from $f$ with proper length padding is collision-resistant.

Proof. Suppose an adversary finds $m \neq = m^{'}$ with $H_{f} (m) = H_{f} (m^{'})$ . Let $m = m_{1} ∥ \dots ∥ m_{l}$ and $m^{'} = m_{1}^{'} ∥ \dots ∥ m_{l^{'}}^{'}$ after padding (which encodes the original message length in the final block).

Since $m \neq = m^{'}$ and the length padding ensures different-length messages have different final blocks, there exists an index where the padded messages differ. Let $j$ be the largest index such that $(h_{j - 1}, m_{j}) \neq = (h_{j - 1}^{'}, m_{j}^{'})$ .

We have $h_{j} = f (h_{j - 1}, m_{j})$ and $h_{j}^{'} = f (h_{j - 1}^{'}, m_{j}^{'})$ . Since $j$ is the largest index where inputs differ, for all $i > j$ : $(h_{i - 1}, m_{i}) = (h_{i - 1}^{'}, m_{i}^{'})$ . So $h_{j} = h_{j}^{'}$ (they propagate to the same final hash). Therefore $f (h_{j - 1}, m_{j}) = f (h_{j - 1}^{'}, m_{j}^{'})$ with $(h_{j - 1}, m_{j}) \neq = (h_{j - 1}^{'}, m_{j}^{'})$ .

This is a collision in $f$ . So any collision in $H_{f}$ yields a collision in $f$ , contradicting $f$ 's collision resistance. $□$

Proposition 2 (RSA-FDH security reduction). If there exists a PPT adversary $A$ that breaks EUF-CMA security of RSA-FDH with probability $ε$ making $q_{H}$ hash queries, then there exists a PPT algorithm $B$ that solves the RSA problem with probability $Ω (ε / q_{H})$ .

Proof. $B$ receives $(N, e, y)$ and must find $x$ with $x^{e} = y mod N$ . $B$ picks a random index $j^{*} \in {1, \dots, q_{H}}$ and simulates the random oracle:

For query $j \neq = j^{*}$ : pick random $r_{j}$ and set $H (m_{j}) = r_{j}^{e} mod N$ .
For query $j^{*}$ : set $H (m_{j^{*}}) = y$ .

When $A$ requests a signature on message $m$ : if $m$ was queried at index $j \neq = j^{*}$ , return $r_{j}$ (since $r_{j}^{e} = H (m)$ , so $r_{j} = H (m)^{d}$ ). If $m$ was queried at $j^{*}$ , abort (cannot sign without knowing $y^{d}$ ). If $m$ was not queried, handle it as a new non- $j^{*}$ query.

$A$ outputs forgery $(m^{*}, σ^{*})$ . If $m^{*} = m_{j^{*}}$ (probability $1/ q_{H}$ ), then $σ^{\aste} = H (m^{*}) = y mod N$ , so $σ^{*} = y^{1/ e} = y^{d}$ is the RSA solution.

The probability $B$ succeeds is $(ε - q_{S} / q_{H}) / q_{H} \approx ε / q_{H}$ (subtracting the probability of aborting on a signing query for $m_{j^{*}}$ ). $□$

Connections Master

47.06.02 — RSA provides the trapdoor one-way function underlying RSA-FDH signatures; the same key generation and modular arithmetic appear in both encryption and signing.
47.06.01 — One-way functions are the foundation: Rompel's theorem shows OWFs are necessary and sufficient for signatures, and collision-resistant hash functions are built from OWFs via the Naor-Yung construction.
47.06.03 — The Fiat-Shamir heuristic converts zero-knowledge identification protocols into signature schemes; ZK protocols provide the interactive core that becomes non-interactive via hashing.
47.05.01 — Universal hashing and pairwise independence are used in the birthday-bound analysis of collision resistance and in the Naor-Yung UOWHF construction.

Historical & philosophical context Master

The concept of digital signatures was introduced by Diffie and Hellman (1976) in the same paper that proposed public-key cryptography. The first practical signature scheme was RSA (1978), where signing is encryption with the private key.

The formal security definition (EUF-CMA) was given by Goldwasser, Micali and Rivest (1988), who also introduced the distinction between existential and universal forgery. The Rompel theorem (1990) showing that OWFs suffice for signatures was a landmark, establishing that the entire authentication infrastructure rests on the same minimal assumption as symmetric cryptography.

The practical importance of hash functions was underscored by the break of MD5 (Wang et al. 2004) and SHA-1 (Stevens et al. 2017), which demonstrated that collision resistance is a property of specific constructions, not an abstract guarantee. The transition to SHA-256 and SHA-3 is ongoing across the software ecosystem.

The philosophical lesson is that authentication, like encryption, reduces to computational hardness: the impossibility of forging a signature is no more absolute than the impossibility of factoring a number, but it is sufficient for practical purposes ^{[Arora-Barak Ch. 9]}.

Bibliography Master

@book{arora2009computational,
  author    = {Arora, Sanjeev and Barak, Boaz},
  title     = {Computational Complexity: A Modern Approach},
  publisher = {Cambridge University Press},
  year      = {2009},
}
@inproceedings{rompel1990one,
  author    = {Rompel, John},
  title     = {One-Way Functions are Necessary and Sufficient for Secure Signatures},
  booktitle = {Proceedings of the 22nd ACM Symposium on Theory of Computing},
  year      = {1990},
  pages     = {387--394},
}
@inproceedings{naor1989universal,
  author    = {Naor, Moni and Yung, Moti},
  title     = {Universal One-Way Hash Functions and Their Cryptographic Applications},
  booktitle = {Proceedings of the 21st ACM Symposium on Theory of Computing},
  year      = {1989},
  pages     = {33--43},
}
@article{goldwasser1988digital,
  author  = {Goldwasser, Shafi and Micali, Silvio and Rivest, Ronald L.},
  title   = {A Digital Signature Scheme Secure Against Adaptive Chosen-Message Attacks},
  journal = {SIAM Journal on Computing},
  volume  = {17},
  number  = {2},
  pages   = {281--308},
  year    = {1988},
}

Prerequisites

47.06.02

Tier anchors

beginner: Arora and Barak 2009 Computational Complexity: A Modern Approach (Cambridge) Ch. 9-10 (signing messages so anyone can verify but no one can forge, and hash functions that compress without collisions)
intermediate: Arora and Barak 2009 Computational Complexity: A Modern Approach (Cambridge) Ch. 9-10 (EUF-CMA security, RSA-FDH signatures, Merkle-Damgard construction, birthday bound)
master: Arora and Barak 2009 Computational Complexity: A Modern Approach (Cambridge) Ch. 9-10; Naor and Yung 1989 Universal One-Way Hash Functions and Their Cryptographic Applications (STOC); Rompel 1990 One-Way Functions are Necessary and Sufficient for Secure Signatures (STOC)

References

Arora, S. and Barak, B. — Computational Complexity: A Modern Approach · Cambridge University Press (2009). Chapter 9-10 develops digital signatures and hash functions, defining a digital signature scheme as a triple $(K ey G e n, S i g n, V er i f y)$ where $K ey G e n$ produces a signing key $s k$ and verification key $v k$ , $S i g n (s k, m)$ produces a signature $σ$ , and $V er i f y (v k, m, σ) \in {0, 1}$ satisfies correctness ( $V er i f y (v k, m, S i g n (s k, m)) = 1$ ) and unforgeability (for every PPT adversary $A$ with access to a signing oracle, $Pr [V er i f y (v k, m^{*}, σ^{*}) = 1 \land m^{*} \in / Q] \leq negl (n)$ where $Q$ is the set of queried messages); a collision-resistant hash function $h : {0, 1}^{*} \to {0, 1}^{n}$ satisfies that no PPT algorithm can find $x \neq = y$ with $h (x) = h (y)$ ; the Merkle-Damgard construction extends a compression function $f : {0, 1}^{2 n} \to {0, 1}^{n}$ to arbitrary-length inputs by iterating $h_{i} = f (h_{i - 1}, x_{i})$ with length padding, and is collision-resistant if $f$ is.
Rompel, J. — One-Way Functions are Necessary and Sufficient for Secure Signatures · Proceedings of the 22nd ACM Symposium on Theory of Computing (1990). Proves that one-way functions are necessary and sufficient for the existence of secure digital signature schemes; the sufficiency construction transforms any OWF into a universal one-way hash function (UOWHF) using the Naor-Yung transformation, then builds a signature scheme from the UOWHF using a tree-based authentication structure (Merkle tree) where each message block is authenticated by a chain of hash evaluations rooted at the verification key.

Estimated time

beginner: 15m
intermediate: 40m
master: 90m