Date of Degree


Document Type


Degree Name



Computer Science


Delaram Kahrobaei

Committee Members

Vladimir Shpilrain

Xiaowen Zhang

Giovanni Di Crescenzo

Subject Categories

Information Security | Other Computer Sciences


Single Exponentiation, Multiple Exponentiations, Security, Efficiency, Delegation, Outsourcing


Group exponentiation is an important operation used in many cryptographic protocols, specifically public-key cryptosystems such as RSA, Diffie Hellman, ElGamal, etc. To expand the applicability of group exponentiation to computationally weaker devices, procedures were established by which to delegate this operation from a computationally weaker client to a computationally stronger server. However, solving this problem with a single, possibly malicious, server, has remained open since a formal cryptographic model was introduced by Hohenberger and Lysyanskaya in 2005. Several later attempts either failed to achieve privacy or only achieved constant security probability.

In this dissertation, we study and solve this problem for discrete log type groups and RSA type groups for both single and multiple (batch) exponentiations and apply our solution in several protocols. Each of our protocols satisfies natural correctness, security, privacy, and efficiency requirements, where security holds with exponentially small probability.