## Friday, April 13, 2012

### 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 (tF, εF, qs, qh)-secure in the random oracle model is for all forgers F running in time tF making at most qs signature queries and qh 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 = 1e mod φ (N). Unique signature s = H(m)1e mod N. Verification holds if se = 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 (tA, εA)-hard to invert, then RSA-FDH is (tF, εF, qs, qh)-secure in the random oracle model where εF = qs ⋅ εA and tF tA. The reduction is not tight, as it has 'security loss' of qs. Thus for 80-bit security RSA-FDH, the "work factor(F)" = tFεF ≥ 280 for qs = 230, requiring hardness of RSA against an adversary A with "work factor(A)" = tA / εA = (qs ˙ tF)εF = 2110. 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 < qs then this reduction R can be used to break RSA. So given the reduction R, we have to simulate a forger Fsim that has some universe of hash queries M = {1,...,qs} and signing queries Q = {1,...,qs}. 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 Freal be a real forger making the same queries Q and outputs a forgery σ*real on m*. Then by definition:
Pr[RFreal (N,e,x^e) = x] = εR
Pr[RFsim (N,e,x^e) = x] = εI
|Pr[RFreal (N,e,x^e) = x] - Pr[RFsim (N,e,x^e)=x]| ≤ Pr[σ* incorrect AND S correct AND ¬Fail ] ≤ εFqs
so we have εI ≥ εR - εFqs .

RSA is referred to as 'certified' if given (N,e) one can verify in polynomial time that f(N,e)(x) : = xe mod N defines a permutation over ZN.

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 N14 < e < N and e prime. Small exponent RSA, where e < N14, 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)1P(r) where r is a random t-bit string. The security is discussed in the paper of Hofheinz, Jager and Kiltz [pdf].