# 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 ?

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!).