Batch verification with applications to cryptography and checking

Let R(.) be a polynomial time-computable boolean relation. Suppose we are given a sequence inst(1),...,inst(n) of instances and asked whether it is the case that R(inst(i)) = 1 for all i = 1,..., n. The naive way to figure out the answer is to compute R(inst(i)) for each i and check that we get 1 each time. But this takes n computations of R. Can one do any better? The above is the "batch verification" problem. We initiate a broad investigation of it. We look at the possibility of designing probabilistic batch verifiers, or tests, for basic mathematical relations R. Our main results are for modular exponentiation, an expensive operation in terms of number of multiplications: here g is some fixed element of a group G and R(x, y) = 1 iff g(x) = y. We find surprisingly fast batch verifiers for this relation. We also find efficient batch verifiers for the degrees of polynomials. The first application is to cryptography, where modular exponentiation is a common component of a large number of protocols, including digital signatures, bit commitment, and zero knowledge. Similarly, the problem of verifying the degrees of polynomials underlies (verifiable) secret sharing, which in turn underlies many secure distributed protocols. The second application is to program checking. We can use batch verification to provide faster batch checkers, in the sense of [20], for modular exponentiation. These checkers also have stronger properties than standard ones, and illustrate how batch verification can not only speed up how we do old things, but also enable us to do new things.