Abstract
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.
Work supported in part by NSF CAREER Award CCR-9624439 and a 1996 Packard Foundation Fellowship in Science and Engineering.
Preview
Unable to display preview. Download preview PDF.
References
L. Adleman and K. Kompella. Fast Checkers for Cryptography. In A. J. Menezes and S. Vanstone, editors, Advances in Cryptology — Crypto '90, pages 515–529, Berlin, 1990. Springer-Verlag. Lecture Notes in Computer Science No. 537.
S. Arora, C. Lund, R. Motwani, M. Sudan, and M. Szegedy. Proof verification and hardness of approximation problems. In Proc. 33rd Annual Symposium on Foundations of Computer Science, pages 14–23. IEEE, 1992.
M. Bellare, J. Garay, and T. Rabin. Distributed Pseudo-Random Bit Generators—A New Way to Speed-Up Shared Coin Tossing. In Proceedings Fifteenth Annual Symposium on Principles of Distributed Computing, pages 191–200. ACM, 1996.
M. Beller and Y. Yacobi. Batch Diffie-Hellman Key Agreement Systems and their Application to Portable Communications. In R. Rueppel, editor, Advances in Cryptology — Eurocrypt '92, pages 208–220, Berlin, 1992. Springer-Verlag. Lecture Notes in Computer Science No. 658.
E. Berlekamp and L. Welch. Error correction of algebraic block codes. US Patent 4,633,470.
M. Blum, W. Evans, P. Gemmell, S. Kannan, and M. Naor. Checking the Correctness of Memories. In Proceeding 32nd Annual Symposium on the Foundations of Computer Science, pages 90–99. IEEE, 1991.
M. Blum and S. Kannan. Designing Programs that Check their Work. In Proceedings 21st Annual Symposium on the Theory of Computing, pages 86–97. ACM, 1989.
M. Blum, M. Luby, and R. Rubinfeld. Self-Testing/Correcting with Applications to Numerical Problems. Journal of Computer and System Sciences, 47:549–595, 1993.
J. Bos and M. Coster. Addition Chain Heuristics. In Advances in Cryptology-Proceedings of Crypto 89, Lecture Notes in Computer Science Vol. 658, pages 400–407. Springer-Verlag, 1989.
E. Brickell, D. Gordon, K. McCurley, and D. Wilson. Fast Exponentiation with Precomputation. In R. Rueppel, editor, Advances in Cryptology — Eurocrypt '92, pages 200–207, Berlin, 1992. Springer-Verlag. Lecture Notes in Computer Science No. 658.
E. Brickell, P. Lee, and Y. Yacobi. Secure Audio Teleconference. In Advances in Cryptology-Proceedings of Crypto 87, Lecture Notes in Computer Science Vol. 293, C. Pomerance editor, pages 418–426. Springer-Verlag, 1987.
B. Chor, S. Goldwasser, S. Micali, and B. Awerbuch. Verifiable Secret Sharing and Achieving Simultaneity in the Presence of Faults. In Proceeding 26th Annual Symposium on the Foundations of Computer Science, pages 383–395. IEEE, 1985.
F. Ergun, S. Ravi Kumar, and R. Rubinfeld. Approximate Checking of Polynomials and Functional Equations. In Proc. 37th Annual Symposium on Foundations of Computer Science, pages 592–601. IEEE, 1996.
A. Fiat. Batch RSA. Journal of Cryptology, 10(2):75–88, 1997.
National Institute for Standards and Technology. Digital Signature Standard (DSS). Technical Report 169, August 30 1991.
P. Gemmell, R. Lipton, R. Rubinfeld, M. Sudan, and A. Wigderson. Self-testing/correcting for polynomials and for approximate functions. In Proc. Twenty Third Annual ACM Symposium on Theory of Computing, pages 32–42. ACM, 1991.
C.H. Lim and P.J. Lee. More Flexible Exponentiation with Precomputation. In Y. Desmedt, editor, Advances in Cryptology — Crypto '94, pages 95–107, Berlin, 1994. Springer-Verlag. Lecture Notes in Computer Science No. 839.
D. Naccache, D. M'Rahi, S. Vaudenay, and D. Raphaeli. Can D.S.A be improved? Complexity trade-offs with the digital signature standard. In A. De Santis, editor, Advances in Cryptology — Eurocrypt '94, pages 77–85, Berlin, 1994. Springer-Verlag. Lecture Notes in Computer Science No. 950.
R. Rivest, A. Shamir, and L. Adleman. A Method for Obtaining Digital Signatures and Public-Key Cryptosystems. Communications of the ACM, 21:120–126, 1978.
R. Rubinfeld. Batch Checking with Applications to Linear Functions. Information Processing Letters, 42:77–80, 1992.
R. Rubinfeld. On the Robustness of Functional Equations. In Proc. 35th Annual Symposium on Foundations of Computer Science, pages 2–13. IEEE, 1994.
R. Rubinfeld. Designing Checkers for Programs that Run in Parallel. Algorithmica, 15(4):287–301, 1996.
R. Rubinfeld and M. Sudan. Robust Characterizations of Polynomials with Applications to Program Testing. SIAM Journal on Computing, 25(2):252–271, 1996.
J. Sauerbrey and A. Dietel. Resource requirements for the application of addition chains modulo exponentiation. In Advances in Cryptology-Eurorypt '92, Lecture Notes in Computer Science Vol. 658. Springer-Verlag, 1992.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1998 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Bellare, M., Garay, J.A., Rabin, T. (1998). Batch verification with applications to cryptography and checking. In: Lucchesi, C.L., Moura, A.V. (eds) LATIN'98: Theoretical Informatics. LATIN 1998. Lecture Notes in Computer Science, vol 1380. Springer, Berlin, Heidelberg. https://doi.org/10.1007/BFb0054320
Download citation
DOI: https://doi.org/10.1007/BFb0054320
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-64275-6
Online ISBN: 978-3-540-69715-2
eBook Packages: Springer Book Archive