Batch RSA

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.