Computing Multiple Exponentiations in Discrete Log and RSA Groups: From Batch Verification to Batch Delegation

Speaker:   Matluba Khodjaeva, Ph. D. Program in Computer Science, CUNY Graduate Center

We consider the problem of a client efficiently, privately and securely delegating the computation of multiple group exponentiations to a computationally more powerful server (e.g. a cloud server). We provide the first practical and provable solutions to this batch delegation problem for groups commonly used in cryptography, based on discrete logarithm and RSA hardness assumptions. Previous results either solved delegation of a single group exponentiation with limited security properties or verification of multiple group exponentiations in prime-order groups (not applicable to RSA) where solutions depended on certain simplifying assumptions on the exponentiation values (not applicable to some discrete logarithm groups). Our results directly solve batch delegation of various algorithms in cryptosystems, including RSA encryption and Diffie-Hellman key agreement protocol.