“Textbook RSA” and Patches

Here is the most straightforward signature scheme based on the RSA problem:

gen generates \(n=pq\), \(e\) and \(d\) as in the RSA problem, and lets \((sk,pk) := (d,n \Vert e)\).
sgn returns \(\sigma := m^d \pmod{n}\).
vrf checks if \(\sigma^e = m \pmod{n}\).

Exercise. Try to prove security of the scheme. Get a feeling how the proof gets stuck.

In your attempted security proof, you should find it impossible to answer signature requests from the virtual adversary. In fact any attempt is hopeless: the scheme is fragile under even \(\ECM^1\) attacks! For example, an adversary can request an arbitrary signature \((m,\sigma)\) and forge say \((m^{34},\sigma^{34})\). Clearly the forgery is valid as the scheme is multiplicative.

There is a canonical “pad-then-sign” approach to break multiplicativity: sgn pads the message with a fixed string, say 00000000, before raising it to power \(d\); vrf is modified accordingly. This effectively prevents the aforementioned attack (and many others) and forms the basis of the RSA PKCS standard. But security proof of this patched version is still out of current reach – perhaps it isn’t secure after all, yet in the meantime people haven’t found proper attacks.

Another approach, known as “hash-then-sign”, turns out to be more systematic in breaking multiplicativity. This time, sgn hashes the message \(m\) to \(H(m)\) and then raise it to power \(d\); vrf is modified accordingly. The good news is that the patch does admit a formal security proof; the bad news is that the known proof relies on a restricted “random oracle model”. In this model, the function \(H\) is managed by a central agency and could not be evaluated by individuals; moreover \(H\) is assumed perfectly random. Every time a player (signer or adversary) intends to hash a message, he must request it to the agency. If the message has not been answered before, then a fresh random value is returned; otherwise the old answer is returned.

Exercise. Prove that the hash-then-sign RSA scheme, as specified above, is \(\ECM^+\) secure under random oracle model.

A centralized setting as in random oracle model is usually impractical. So, at implementation, people often replace the \(H\) by a locally computable hash scheme. The discrepancy between theory (i.e. security only under random oracle model) and practice (i.e. using hash scheme as substitute) is controversial and should be viewed with scepticism.

Gennaro-Halevi-Rabin Scheme

Without surrender to random oracle model, is it actually possible to build provably secure schemes directly on the RSA problem? An influential scheme by Gennaro, Halevi and Rabin answered the question affirmatively. The only requirement is a strengthened version of RSA assumption, which we state below.

People believe that the following problem is hard to solve (i.e. any polynomial time algorithm could succeed with negligible probability only):

With \(n=pq\) generated as in the RSA problem and \(y \in \Int_n\) sampled uniformly, find \(x \in \Int_n\) and \(e \geq 2\) such that \(x^e = y\).

So the adversary is allowed to pick a non-trivial exponent freely, leading to a higher winning chance. The game itself is easier, so its hardness assumption is stronger. We call the problem/assumption the “strong RSA problem/assumption”.

Assume a collision-resistant hash scheme \((\texttt{spl}, H)\) such that any instantiation of \(H\) injectively maps from \(\set{0,1}^*\) to prime numbers. (Such hash scheme can be constructed via discrete logarithm.) The GHR signature scheme is specified as:

gen generates \(n=pq\) as in the RSA problem, along with a uniform random number \(r \in \Int_n\). It calls spl to instantiate a hash function \(H\). Finally, it takes \((sk,pk) := (\phi(n), n \Vert r \Vert H)\).
sgn returns \(\sigma := r^{(H(m))^{-1} \bmod \phi(n)} \pmod {n}\).
vrf checks if \(\sigma^{H(m)} = r \pmod {n}\).

Unlike previously seen contructions, the GHR scheme uses a flexible exponent \((H(m))^{-1}\) that leverages the strong RSA problem; nonetheless the ability of inverting \(H(m)\) somewhat displays the ownership of secret. We next show that the scheme is \(\ECM\) secure.

Security proof. Let us take an arbitrary \(\ECM\) adversary \(A\) and construct a solver for the strong RSA problem.

The judge generates \(n=pq\) and \(y \in \Int_n\), and transmits us \(n\) and \(y\).
The virtual adversary \(A\) requests us the signatures of messages \(m_1, \dots, m_{\ell}\).
We emulate gen by:
- choose \(r := y^{\prod_{j} H(m_j)}\), which is uniformly random since \(y\) was sampled uniformly by the judge.
- publish \(pk := n \Vert r\) to the virtual adversary.
We emulate sgn on message \(m_i\) by:
- return the valid signature \(\sigma_i := y^{\prod_{j \neq i} H(m_j)}\).
On receipt of a valid forgery \((m, \sigma)\) from the virtual adversary,
- note \(\sigma^{H(m)} = r = y^{\prod_{j} H(m_j)}\);
- without loss of generality assume \(H(m) \not\in \set{H(m_1), \dots, H(m_{\ell})}\), for otherwise we can attack collision resistance of the hash scheme;
- hence \(\operatorname{gcd}(H(m), \prod_{j} H(m_j)) = 1\) as the hash values are distinct primes;
- so we can find \(u,v \in \Int\) such that \(u \cdot H(m) + v \cdot \prod_{j} H(m_j) = 1\);
- then \((y^u \sigma^v)^{H(m)} = y\) (this is by Shamir’s trick that we cited in one-time RSA scheme);
- submit the solution \((y^u \sigma^v, H(m))\) to the judge. ∎

Compared to schemes from previous chapters, GHR scheme is much more compact and efficient since it bypasses the trust-propagation construction. Elaborating on the idea of GHR, a milestone scheme due to Hohenberger and Waters successfully drops the strong RSA assumption down to normal RSA assumption while keeping the signatures compact. In practice, however, these schemes are still too slow as they require generating a large amount of prime numbers. It remains an open problem to improve the efficiency of these provably secure RSA-based schemes.

Return↩︎