How Provably Secure are Cryptographic Primitives used in Practice?

For the second time this year, many of the group have made the short trip to Cambridge for the Newton Institute workshop titled Formal and Computational Cryptographic Proofs. In the spirit of the workshop the focus of Eike Kiltz's talk was provable security of RSA-FDH (Full Domain Hash) signatures.

When looking at provable security it is of course vital to consider the following process:

1. Define the security model required: Unforgeability under Chosen Message Attack (UF-CMA)

2. Describe the scheme: [RSA-FDH]

3. Define and analyse a 'hard problem': the RSA assumption

4. Create a security reduction from the scheme to the hard problem.

So in this case one needs to show that breaking the UF-CMA property means that one can break the RSA assumption, to draw the conclusion that the scheme is secure. First off, the signature scheme is (t_F, ε_F, q_s, q_h)-secure in the random oracle model is for all forgers F running in time t_F making at most q_s signature queries and q_h random oracle queries, Pr[F wins] < ε_F where the event F wins is F creating a forgery on a message not previously asked.

In RSA-FDH the public key is (N, e, H:{0.1}^k → Z*_N ), the secret key is d = ¹⁄_e mod φ (N). Unique signature s = H(m)^1⁄_e mod N. Verification holds if s^e = H(m) mod N.

A variation of this scheme is used in practice, and it gives unique signatures from a deterministic algorithm. In 2000, Coron [pdf] showed that if we assume that RSA is (t_A, ε_A)-hard to invert, then RSA-FDH is (t_F, ε_F, q_s, q_h)-secure in the random oracle model where ε_F = q_s ⋅ ε_A and t_F ≈ t_A. The reduction is not tight, as it has 'security loss' of q_s. Thus for 80-bit security RSA-FDH, the "work factor(F)" = ^t_F⁄_εF ≥ 2⁸⁰ for q_s = 2³⁰, requiring hardness of RSA against an adversary A with "work factor(A)" = t_A / ε_A = ^{(q_s ˙ t_F)}⁄_εF = 2¹¹⁰. Thus the size of N is required to be approximately 2000 bits, rather than 1000 if the reduction was tight.

In 2002 Coron [pdf] showed that if there exists a reduction R from security of RSA-FSH to the hardness of RSA losing a factor < q_s then this reduction R can be used to break RSA. So given the reduction R, we have to simulate a forger F_sim that has some universe of hash queries M = {1,...,q_s} and signing queries Q = {1,...,q_s}. The forger gives M and receives back the hashes of the elements of M. Forger then selects an m* in M but not in Q, and gets back σ* = sign(m*). Then it gives Q and receives signatures on the elements of Q, then it rewinds to before m* was queried, so that after the rewind the reduction doesn't know what happened so m* is not in Q, and so it still counts as a valid forgery. This simulates the view of a forger used to break a hard problem.

Let F_real be a real forger making the same queries Q and outputs a forgery σ*_real on m*. Then by definition:

Pr[R^F_real (N,e,x^e) = x] = ε_R

Pr[R^F_sim (N,e,x^e) = x] = ε_I

|Pr[R^F_real (N,e,x^e) = x] - Pr[R^F_sim (N,e,x^e)=x]| ≤ Pr[σ* incorrect AND S correct AND ¬Fail ] ≤ ^ε_F⁄_qs

so we have ε_I ≥ ε_R - ^ε_F⁄_qs .

RSA is referred to as 'certified' if given (N,e) one can verify in polynomial time that f_(N,e)(x) : = x^e mod N defines a permutation over Z^∗_N.

A folklore result states that for e > N and e prime, is certified. In a paper of Kiltz and Kakvi appearing next week at Eurocrypt it is showed that RSA is certified if N^1⁄₄ < e < N and e prime. Small exponent RSA, where e < N^1⁄₄, is not certified as it is 'lossy.' This work shows that it is possible to create a tight reduction of RSA-FDH usign the Phi-Hiding assumption, which is simply a factor of 2 loss in the reduction. Thus if Phi-Hiding and RSA are equally difficult assumptions (assumed to be the case) then we have a tight reduction.

In the standard model, Dodis et al. [pdf] gave the following theorem: If f is a homomorphic trapdoor permutation, there does not exist any blackbox reduction R from the security of f-FDH to any non-interactive hard problem of F. There is however a positive result due to programmable hash functions (Hofheinz, Kiltz 2008 [pdf]). A brief discussion of programmable hash functions included how if we assume H is a (m,1)-programmable hash function, then RSA is hard to invert. Then RSA-FDH is a secure m-time signature scheme, no doubt a weaker model.

In randomized RSA-FDH, the public key includes two hash functions H and P, and signatures are defnined as H(m)^1⁄_P(r) where r is a random t-bit string. The security is discussed in the paper of Hofheinz, Jager and Kiltz [pdf].