Abstract
We present a variant of the RSA algorithm called Batch RSA with two important properties:
-
• The cost per private operation is exponentially smaller than other number-theoretic schemes [9], [23], [22], [11], [13], [12]. In practice, the new variant effectively performs several modular exponentiations at the cost of a single modular exponentiation. This leads to a very fast RSA-like scheme whenever RSA is to be performed at some central site or when pure-RSA encryption (versus hybrid encryption) is to be performed.
-
• An additional important feature of Batch RSA is the possibility of using a distributed Batch RSA process that isolates the private key from the system, irrespective of the size of the system, the number of sites, or the number of private operations that need to be performed.
Article PDF
Similar content being viewed by others
References
Abadi, M., Feigenbaum, J., and Kilian, J., On hiding information from an oracle,Proceedings of the 19th Annual ACM Symposium on Theory of Computing, pp. 195–203. New York City, May 25–27, 1987.
Aho, A. V., Hopcroft J. E., and Ullman, J. D.,The Design and Analysis of Computer Algorithms, Addison-Wesley, Reading, MA, 1974.
Blum, M., Personal communication.
Blum, M., Floyd, R. W., Pratt, V., Lewis, R. L., and Tarjan, R. E., Time bounds for selection,J. Comput. System Sci. vol. 7 pp. 448–461, 1973.
Yacobi, Y., and Beller, M. J., Batch Diffie-Hellman key agreement systems,Proceedings of Eurocrypt '92, pp. 208–217.
Coppersmith, D., Fast evaluation of logarithms in fields of characteristic two.IEEE Trans. Inform. Theory, vol. IT-30, no. 4, pp. 587–592, July 1984.
Coppersmith, D., Modifications to the number field sieve, IBM Research Report #RC 16264.
Chaum, D., Fiat, A., and Naor, M., Untraceable electronic cash,Proceedings of Crypto '88, pp. 319–227, 1976.
Diffie, W. and Hellman, M. E., New Directions in Cryptography, IEEE Trans. Inform. Theory, vol. IT-22, 1976.
Dwork, C. and Naor, M., An efficient existentially unforgeable signature scheme and its applications,Advances in Cryptology—Proceedings of Crypto'94, Lecture Notes in Computer Science, Vol. 839, Springer-Verlag, Berlin, 1994, pp. 234–346.
El Gamal, T., A public key cryptosystem and a signature scheme based on discrete logarithms,IEEE Trans. Inform. Theory, vol. IT-31, no. 4, pp. 459–472, July 1985.
Fiat, A. and Shamir, A., How to prove yourself: Practical solutions to identification and signature problems,Advances in Cryptography—Proceedings of Crypto'86, pp. 186–194, Spinger-Verlag, Berlin, 1987.
Goldwasser, S., Micali, S., and Rivest, R. L., A digital signature scheme secure against adaptive chosen message attacks,SIAM J. Comput., vol. 17, no. 2, pp. 281–308, April 1988.
Guillou, L. C. and Quisquater, J. J., A practical zero-knowledge protocol fitted to security microprocessor minimizing both transmission and memory, In:Advances in Cryptology: Proceedings of Eurocrpyt '88 (C.G. Gunther, ed.), Davos, Switzerland, May 25–27, pp. 123–128, 1988.
Håstad, J., On using RSA with low exponent in a public key network,Proceedings of Crypto '85, pp. 403–408.
Koblitz, N., Elliptic curve cryptosystems,Math. Comput., vol. 48, pp. 203–209, 1987.
Knuth, D.,The Art of Computer Programming, vol. 2:Seminumerical Algorithms, 2nd edn., Addison-Wesley, Reading, MA, 1981.
Lenstra, A. K., Lenstra, Jr., H. W., Manasse, M. S., and Pollard, J. M., The number field sieve,Proceedings of the 22nd ACM Symposium on the Theory of Computing, pp. 464–572, 1990.
Menezes, A. and Vanstone, S., The implementation of elliptic curve cryptosystems, In:Advances in Cryptology—Auscrypt '90 (J. Seberry, and J. Pieprzyk, eds.), Sydney, Jan. 1990, pp. 2–13.
Menezes, A., Okamoto, T., and Vanstone, S., Reducing elliptic curve logarithms to logarithms in a finite field,Proceedings of the 22nd Annual ACM Symposium on the Theory of Computing, pp. 80–89, 1991.
Quisquater, J. J. and Couvreur, C., Fast decipherment algorithm for RSA public-key cryptosystem,Electronic Letters, vol. 18, no. 21, 1982, pp. 905–907.
Rabin, M. O., Digitalized signatures, In:Foundations of Secure Computation, Academic Press, New York, 1978.
Rivest, R. L., Shamir, A., and Adleman, L., A method for obtaining digital signatures and public key cryptosystems.Comm. ACM, vol. 21, no. 2, 1978.
Shamir, A., On the generation of cryptographically strong pseudorandom sequences,ACM Trans. Comput. Systems, vol. 1, no. 1, 1983.
Tarjan, R. E., Amortized computational complexity.SIAM J. Algebraic Discrete Methods, vol. 2, no. 6, pp. 306–318, 1985.
Wiener, M. J., Cryptoanalysis of Short RSA exponents.IEEE Trans. Inform. Theory, vol. 36, no. 3, May 1990, pp. 553–558.
Author information
Authors and Affiliations
Additional information
Communicated by Gilles Brassard
A preliminary version of this paper appeared inAdvances in Cryptology: Proceedings of Crypto '89, pp. 175–185. This work was performed at U.C., Berkeley, and ARL, Israel.
Rights and permissions
About this article
Cite this article
Fiat, A. Batch RSA. J. Cryptology 10, 75–88 (1997). https://doi.org/10.1007/s001459900021
Received:
Revised:
Issue date:
DOI: https://doi.org/10.1007/s001459900021