Secure delegation of group exponentiations: Efficient and fully verifiable schemes with two servers

Abstract Recent interactions between cloud service providers and mobile resource-constrained devices have increased the interest on the delegation of expensive computations to powerful external server providers. At the same time, security and verifiability of the delegated computation are challenging though highly demanded requirements for various application scenarios. Many security solutions using advanced cryptographic technologies require a large number of highly expensive group exponentiations (GEs). In this paper, we address the problems regarding secure and verifiable delegation of GEs. We first analyze two delegation schemes for GEs both introduced recently in Cluster Computing by Fu et al with the claim that they both provide full verifiability. Particularly, we show that the first scheme is only verifiable with a probability at most 2/3, and the second scheme is totally unverifiable. Then, we propose a secure, efficient and fully verifiable delegation scheme InvDel for a GE using two servers, where one of which is malicious. With InvDel the delegator does not require computations of any group inversions (GIs) while providing full verifiability. Then, we extend InvDel to SimInvDel which is the first, efficient and secure delegation scheme for n-simultaneous GEs achieving full verifiability for n > 1. Secondly, we give implementation results of InvDel and SimInvDel using an Android application together with a comprehensive efficiency analysis of computation and communication with the previous schemes. For instance, when the required CPU costs for a single GE are compared with a 4092-bit modulus, InvDel is more than 220-times (resp. more than two times) more efficient than the local computation (resp. using a previous fully verifiable scheme proposed in the literature). Finally, we also utilize InvDel and SimInvDel to speed-up the verification of Schnorr s signature and Cramer-Shoup encryption schemes.