# Probabilistic verification of signature schemes like RSA?

I was wondering if there were any verification algorithm in the literature that enables a "probabilistic" verification of well-known signature schemes?

For RSA signature verification for example, is there any way to verify $$s^e = H(m) \mod N$$ in a fast way but with a certain "error" probability ?

If not for RSA, for any other schemes ?

Every signature scheme has some nonzero forgery probability: if there are $$n$$ distinct possible signatures, this forgery probability is always at least $$1/n$$, because a forger could just try signatures uniformly at random. But sometimes $$n$$ is so large that $$1/n$$ is smaller than it needs to be for confidence, say $$1/2^{2048}$$ when all you really need is $$1/2^{100}$$, and we can exploit this to trade off forgery probability for performance. Here's an example of how, with RSA.

Suppose a signature is not an integer $$s$$ such that $$s^e \equiv H(m) \pmod N$$, but rather a pair of integers $$(s, k)$$ with $$s < N$$ and $$k < N^{e - 1}$$ such that $$s^e = H(m) + kN.$$ Then the verifier can verify this equation modulo a secret uniform random $$v$$-bit prime $$r$$, $$s^e \equiv H(m) + kN \pmod r.$$ There are $$\pi(2^v) - \pi(2^{v-1})$$ such primes, and $$s^e - h - kN$$ has at most $$\lceil(\log_2 N^e)/v\rceil$$ $$v$$-bit prime factors, so the probability that $$r \mid s^e - h - kN$$ is at most $$\frac{\lceil(\log_2 N^e)/v\rceil}{\pi(2^v) - \pi(2^{v-1})}$$ for any fixed $$(s, k)$$, $$h$$, and $$N$$ unless $$s^e = h + kN$$. Of course, while the forger can try about $$t$$ messages to find one whose hash $$h$$ has a desired property occurring with probability $$1/t$$, only about $$1/2^{2048}$$ of them satisfy $$s^e = h + kN$$ if $$N \approx 2^{2048}$$, so the forger has no hope of finding those.

For $$v = 128$$, we have $$\pi(2^v) - \pi(2^{v - 1}) \approx \frac{2^{128}}{\log 2^{128}} - \frac{2^{127}}{\log 2^{127}} \approx 2^{120},$$ and for $$e = 3$$ and $$N \approx 2^{2048}$$, we have $$\lceil(\log_2 N^e)/v\rceil = 48$$, so the forgery probability is at most about $$1/2^{114}$$.

Obviously, the verifier can choose independent primes $$r_1, r_2, r_3, \dots$$ to lower the forgery probability further; the verifier can also reuse the primes for multiple verifications to save effort, as long as they remain secret.

This scheme is not particularly attractive unless $$e$$ is very small: even for $$e = 3$$, it triples the size of the signature. It is most attractive for Rabin-type signatures with $$e = 2$$, which are, of course, qualitatively different from RSA-type signatures (and largely better all around except in being deployed anywhere!).

To my knowledge, this idea was first published by Bernstein in 1997, and is mentioned in his summary paper on modular root signature schemes discussing many variations on the themes of RSA and Rabin–Williams signatures.

• Squeamish, does the scheme in your answer have some probability of error in the verification? Anyway, could you please point some (others) signature schemes where the probability of verification of a well well-known signature isn't zero? – McFly Oct 16 at 19:31
• This will sometimes accept a forgery, but with probability small enough not to matter as long as the prime $r$ is large enough or you use enough independent primes. This will never reject a valid signature. – Squeamish Ossifrage Oct 16 at 19:40
• I'm just wondering: if schemes with a small probability of forgery are acceptable, why not with some small probability of reject valid signed? – McFly Oct 16 at 19:46
• Of course, every signature scheme accepts a forgery with some probability—if there are $n$ possible signatures then the forgery probability is always at least $1/n$. There are some signature schemes that may fail when making a signature, but if randomized you can just start over with independent randomization when this happens. However, it would be rather curious for a signature scheme to sometimes reject a valid signature, and I've never heard of such a scheme. If you had one, you could just try verifying the signature and start over if verification fails. – Squeamish Ossifrage Oct 16 at 19:50