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

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.