Batch RSA

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.