Bitslog

When I posted about RSAL in my last post I was also thinking of a variant scheme that allows some pre-computation. I spent some time (minutes) evaluating its security and now I’m convinced that it’s secure :).

Here it is:

The RSALX Digital signature Scheme

PrecomputeSign() →< A, a, t¹, … , t^{2^d} >

1. Chose a random message A of d bits each, where d is the size of the hash function digest.

2. Compute a :=Hash(A )

3. Compute t :=Integer(a).

4. Compute d powers: t¹, t², t⁴ , t⁸ ,… , t^{2^d} (mod n)

5. Return < A, a, t¹, … , t^{2^d} >

OnlineSign(M, < A, a, t¹, … , t^{2^d} >) → (s,A)

6. Let M be the message to sign.

7. Compute z :=Hash(M).

8. Compute m :=ConvertToInteger(z).

9. Compute g := m^-1 ( mod φ(n) ).

10. Compute s := t^g (mod n) by the exponentiation by squaring method but using the precomputed squarings.

11. The signature is (s,A)

Verify(M, (s,A), n)

1. Compute z :=Hash(M).

2. Compute a := Hash(A)

3. Compute t := Integer(a).

4. Compute m :=ConvertToInteger(z)

5. Compute y := s^m (mod n).

6. Accept the signature if y=t

Correctness

If the signature is authentic then we have: y = s^m = t^g*m = t

The scheme security relies on the RSA assumption, and not the strong RSA assumption as one may think. This is because t must be chosen before s as a hash of some random message, so both s and y cannot be chosen together.

“A” values  (and consequently t values) should not be reused. If reused then the scheme becomes insecure.

For a 2048 bit modulus, precomputation requires 2048 multiplications and signing on average requires 1024 multiplications and a fast modular inversion (because the value to be inverted is only d-bits long). This implies that this method is almost as fast as RSA for signing, with the benefit of allowing precomputation of two thirds of the work. The drawback is that it produces signatures d bits longer, which is probably not very relevant since d will be much smaller than n.