1990 | OriginalPaper | Chapter
Batch RSA
Author : Amos Fiat
Published in: Advances in Cryptology — CRYPTO’ 89 Proceedings
Publisher: Springer New York
Included in: Professional Book Archive
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
Number theoretic cryptographic algorithms are all based upon modular mul- tiplication modulo some composite or prime. Some security parameter n is set (the length of the composite or prime). Cryptographic functions such as digi- tal signature or key exchange require O(n) or O(√n) modular multiplications ([DH, RSA, R, E, GMR, FS], etc.).This paper proposes a variant of the RSA scheme which requires only polylog(n) (O(log2n)) modular multiplications per RSA operation. Inherent to the scheme is the idea of batching, i.e., performing several encryption or signature operations simultaneously. In practice, the new variant effectively performs several modular exponentiations at the cost of a single modular ex- ponentiation. This leads to a very fast RSA-like scheme whenever RSA is to be performed at some central site or when pure-RSA encryption (vs. hybrid encryption) is to be performed.An important feature of the new scheme is a practical scheme 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 be performed.