BATCH RSA

We present a variant of the RSA algorithm called Batch RSA with two im portant properties: The cost per private operation is exponentially sm aller than other number-theoretic schemes [9], [23], [22], [11], [13], [12]. In practice, the new variant effectively performs several modul ar exponentiations at the cost of a single modular exponentiation. Thi s 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 encry ption) is to be performed. An additional important feature of Batch RS A is the possibility of using a distributed Batch RSA process that iso lates 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.