# 「Cryptography-MIT6875」: Lecture 12

**Topics Covered: **

Construction of CRHF from Discrete Log

Digital Signatures only from OWF

Direct Constructions:Trapdoor Permutation and the Hash-and-Sign Paradigm.

Random Oracles.

# Digital Signature from CRHF

We showed the theorem about digital signature in Lecture 10.

**Theorem:**

Assuming the existence of **one-way functions** and **collision-resistant hash function families**, there are digital signature schemes.

## CRHF Definition

Recall the definition of **Collision-Resistant Hash Functions.**

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

The function $h$ is __given to the adversary__. And the advantage of finding a collision is negligible.

How can we construct the CRHF ?

## Construction of CRHF from Discrete Log

**Construction: **

- Let $p=2q+1$ be a “safe” prime.
- Let $\mathcal{H}=\{h:(\mathbb{Z}_q)^2\rightarrow QR_p\}$
- $\mathcal{H}$ maps two element in $\mathbb{Z}_q$ to one element in $QR_p$, the
**subgroup of quadratic residues**in $\mathbb{Z}_p^*$ with order $q$. - Each function $h_{g_1,g_2}\in \mathcal{H}$ is
**parameterized**by two generators $g_1$ and $g_2$ of $QR_p$.

- $\mathcal{H}$ maps two element in $\mathbb{Z}_q$ to one element in $QR_p$, the
- Define $h_{g_1,g_2}(x_1,x_2)=g_1^{x_1}g_2^{x_2} \mod p$.
- This
**compresses**$2\log q$ bits into $\log q\approx \log {q+1}$ bits.

Prove $h_{g_1,g_2}$ is collision-resistant.

**Proof: **

- Suppose for
**contradiction**that there is an adversary that**finds a collision**$(x_1,x_2)$ and $(y_1,y_2)$. - $g_1^{x_1}g_2^{x_2}= g_1^{y_1}g_2^{y_2}\mod p$
- $g_1^{x_1-y_1}= g_2^{y_2-x_2}\mod p$
- $g_1=g_2^{(y_2-x_2)(x_1-y_1)^{-1}}\mod p$ (assuming $x_1-y_1\ne 0$)
- This turns to
**a discrete log problem**of $DLOG_{g_2}(g_1)$.

Turns out to another theorem of digital signature scheme.

**Theorem: **

Assuming the **hardness of the discrete logarithm problem**, there are digital signature schemes.

## Other Constructions of CRHF

Similarly, we can construct CRHF from the hardness of factoring, lattice problems etc.

It’s **not known** to follow from the __existence of one-way functions__ or even __one-way permutations.__ It’s still a big open problem.

“Black-box separations”: Certain ways of constructing CRHF from OWF/OWP cannot work.

”Finding collisions on a one-way street”, Daniel Simon, Eurocrypt 1998.

# Digital Signature from OWF

But it turns out that **collision-resistant hashing is not necessary**; something weaker called **universal one-way hashing (UOWHF) suffices.**

Furthermore, **UOWHFs** can be __constructed from one-way functions alone.__

The challenge is different between CRHF and UOWHF.

**CRHF**- Give $\mathcal{A}$ the
**function**$h$ - It’s computationally hard for $\mathcal{A}$ to gives $(x,y)$ such that $h(x)=h(y)$ s.t. $x\ne y$.

- Give $\mathcal{A}$ the
**UOWHF**- $\mathcal{A}$ requests for the hash of $x$.
- Give $\mathcal{A}$ the
**hash**$h(x)$ - It’s computationally hard for $\mathcal{A}$ to give $y$ such that $h(x)=h(y)$ s.t. $x\ne y$.

So we can construct Digital Signature only from OWF.

**Theorem: **

Digital Signature schemes exist **if and only if** __one-way functions exist.__

We can construct Digital Signatures from two routes.

- OWF → UOWHF → Digital Signatures
- CRHF(+OWF) → Digital Signatures

Now we catch the sight of words in crypto.

# Direct Constructions

We will show that “Hash-and-Sign” is secure **in random oracle model.**

## “Vanilla” RSA Signatures

We can construct Digital Signature scheme directly __from any trapdoor permutation__, e.g. RSA.

**Vanilla RSA Signatures: **

- $Gen(1^\lambda)$
- Pick primes $(P,Q)$ and let $N=PQ$.
- Pick $e$ relatively prime to $\phi(N)$ and let $d=e^{-1} \pmod {\phi(N)}$.
- $SK=(N,d)$ and $VK=(N,e)$

- $Sign(SK,m)$
- Output signature $\sigma=m^d \pmod N$

- $Verify(VK,m,\sigma)$
- Check if $\sigma^e=m\pmod N$

But it is existentially forgeable and malleable.

*Problems: *

**Existentially forgeable**- Attack1: Pick a random $\sigma$ and output $(m=\sigma^e,\sigma)$ as the forgery.

**Malleable**- Attack2: Given a signature of $m$, you can produce a signature of $2m,3m,\dots$

__Fundamental issues __ under the problems:

- Can
__“reverse-engineer” the message__starting from the signature. (Attack 1) __Algebraic structure__allows malleability. (Attack 2)

How to fix Vanilla RSA ?

**Fixed Vanilla RSA Signature: **

- $Gen(1^\lambda)$
- Pick primes $(P,Q)$ and let $N=PQ$.
- Pick $e$ relatively prime to $\phi(N)$ and let $d=e^{-1} \pmod {\phi(N)}$.
- $SK=(N,d)$ and $VK=(N,e,\color{blue}{H})$

- $Sign(SK,m)$
- Output signature: $\sigma= \color{blue}{H(m)}^d \pmod N$

- $Verify(VK,m,\sigma)$
- Check if $\sigma^e=\color{blue}{H(m)}\pmod N$

**What is $H$ ?**

$H$ is some very complicated “hash” function.

$H$ should be __at least one-way .__ ( to prevent Attack 1)

$H$ should be __hard to “algebraically manipulate”__ $H(m)$ into $H(\text{related } m’)$.(to prevent Attack 2)

**Collision-resistance** dose **not** seem to be enough.

Given a CRHF $H(m)$, you may be able to produce $H(m’)$ for related $m’$.

## The Random Oracle Heuristic

We want a **public** $H$ that is “**non-malleable”.**

Given $H(m)$, it is __hard to produce $H(m’)$ for any non-trivially related $m’$.__

The **goal** of adversary is to **come up with the relation** $R$ such that __you can somehow manipulate $H(m)$ into $H(m’)$.__

How about the **relation** $R$ where $R(x,y)=1$ if and only if $y=H(x)$ ?

A **public** $H$ that **“behaves like a random function”.**

We can consider it as a **proxy** to __a random function.__

(A PRF also behaves like a random function, but $PRF_K$ is **not publicly computable. )**

The adversary $\mathcal{A}$ can __get the public function__ $H$ in **reality**.

But in the **Random Oracle Heuristic world**, the __only way to compute $H$,__ virtually a black box, is __by calling the oracle.__

**Claim:**

The hashed RSA is EUF-CMA secure **in the random oracle model.**

**Proof:**

**Assume**there is a PPT adversary $\mathcal{A}$ that breaks the EUF-CMA security of hashed RSA**in the random oracle model.**- Given $\mathcal{A}$ the verification key.
- $\mathcal{A}$ asks the
**Hash Query**for poly. times.

(We can model it to split the hash queries and sign queries.) - $\mathcal{A}$ asks the
**Sign Query**for poly. times. - $\mathcal{A}$ gives a forgery $(m^*, \sigma^*)$.

Recall the

**RSA assumption:**

given $N,e$ and $y=x^e\mod N$, hard to compute $x$.Then, there is an algorithm $\mathcal{B}$ that solves the RSA problem.

- The task of $\mathcal{B}$ is to compute $x$ given the $(N,e,y)$.
- $\mathcal{B}$ needs to interact with the adversary $\mathcal{A}$

$\mathcal{B}$ gives the verification key $VK=(N,e)$ to $\mathcal{A}$.

$\mathcal{A}$ asks polynomially many

**Hash Queries.**- For all hash queries, $\mathcal{B}$
__picks a random__$\tilde{m}$ as the**trap**. - For the
**trap**$\tilde{m}$, $\mathcal{B}$ sets the hash $H(\tilde{m})=y$. - For other
**normal**$m$, $\mathcal{B}$ picks a random $x$ and sets the hash $H(m)=x^e$.

- For all hash queries, $\mathcal{B}$
$\mathcal{A}$ asks polynomially many

**Sign Queries.**For each Sign Query for $m$:

- If $m=\tilde{m}$, i.e. hits the trap, $\mathcal{B}$ aborts.

Because $\mathcal{B}$__cannot produce the signature.__ - Otherwise, $\mathcal{B}$ is
__able to produce the signature__$\sigma=x$.

- If $m=\tilde{m}$, i.e. hits the trap, $\mathcal{B}$ aborts.
$\mathcal{A}$ promises to produce the

**forgery**$(m^*,\sigma^*)$.- The thing to
**notice**is that the message $m^*$ is__new to all the messages in Sign Query__, not in Hash Query. - If $m^*=\tilde{m}$,
**hits the trap**, then the signature $\sigma^*=x$ is what she wants. **Claim:**

To produce**a successful forgery**, $\mathcal{A}$ must__have queried the hash oracle__on $m^*$. With probability $1/q$, $m^*$ is the trap.

(where $q$ is the number of hash queries)

- The thing to

## Bottomline: Hashed RSA (SHA-3)

In **practice**, we let $H$ be the **SHA-3 hash function.**

And we believe that SHA-3 __acts like a random function.__

That’s the heuristic.

On the one hand, it doesn’t make any sense, but one the other hand, it has served us well so far.

There are __no attacks against RSA+SHA-3__, for example.

「Cryptography-MIT6875」: Lecture 12