Biblio

In cloud computing application scenarios involving computationally weak clients, the natural need for applied cryptography solutions requires the delegation of the most expensive cryptography algorithms to a computationally stronger cloud server. Group exponentiation is an important operation used in many public-key cryptosystems and, more generally, cryptographic protocols. Solving the problem of delegating group exponentiation in the case of a single, possibly malicious, server, was left open since early papers in the area. Only recently, we have solved this problem for a large class of cyclic groups, including those commonly used in cryptosystems proved secure under the intractability of the discrete logarithm problem. In this paper we solve this problem for an important class of non-cyclic groups, which includes RSA groups when the modulus is the product of two safe primes, a common setting in applications using RSA-based cryptosystems. We show a delegation protocol for fixed-exponent exponentiation in such groups, satisfying natural correctness, security, privacy and efficiency requirements, where security holds with exponentially small probability. In our protocol, with very limited offline computation and server computation, a client can delegate an exponentiation to an exponent of the same length as a group element by only performing two exponentiations to an exponent of much shorter length (i.e., the length of a statistical parameter). We obtain our protocol by a non-trivial adaptation to the RSA group of our previous protocol for cyclic groups.

Group exponentiation is an important operation used in many public-key cryptosystems and, more generally, cryptographic protocols. To expand the applicability of these solutions to computationally weaker devices, it has been advocated that this operation is outsourced from a computationally weaker client to a computationally stronger server, possibly implemented in a cloud-based architecture. While preliminary solutions to this problem considered mostly honest servers, or multiple separated servers, some of which honest, solving this problem in the case of a single (logical), possibly malicious, server, has remained open since a formal cryptographic model was introduced in [20]. Several later attempts either failed to achieve privacy or only bounded by a constant the (security) probability that a cheating server convinces a client of an incorrect result. In this paper we solve this problem for a large class of cyclic groups, thus making our solutions applicable to many cryptosystems in the literature that are based on the hardness of the discrete logarithm problem or on related assumptions. Our main protocol satisfies natural correctness, security, privacy and efficiency requirements, where the security probability is exponentially small. In our main protocol, with very limited offline computation and server computation, the client can delegate an exponentiation to an exponent of the same length as a group element by performing an exponentiation to an exponent of short length (i.e., the length of a statistical parameter). We also show an extension protocol that further reduces client computation by a constant factor, while increasing offline computation and server computation by about the same factor.