Paper 2018/644

Hide The Modulus: A Secure Non-Interactive Fully Verifiable Delegation Scheme for Modular Exponentiations via CRT

Osmanbey Uzunkol, Jothi Rangasamy, and Lakshmi Kuppusamy


Security protocols using public-key cryptography often requires large number of costly modular exponentiations (MEs). With the proliferation of resource-constrained (mobile) devices and advancements in cloud computing, delegation of such expensive computations to powerful server providers has gained lots of attention. In this paper, we address the problem of verifiably secure delegation of MEs using two servers, where at most one of which is assumed to be malicious (the OMTUP-model). We first show verifiability issues of two recent schemes: We show that a scheme from IndoCrypt 2016 does not offer full verifiability, and that a scheme for $n$ simultaneous MEs from AsiaCCS 2016 is verifiable only with a probability $0.5909$ instead of the author's claim with a probability $0.9955$ for $n=10$. Then, we propose the first non-interactive fully verifiable secure delegation scheme by hiding the modulus via Chinese Remainder Theorem (CRT). Our scheme improves also the computational efficiency of the previous schemes considerably. Hence, we provide a lightweight delegation enabling weak clients to securely and verifiably delegate MEs without any expensive local computation (neither online nor offline). The proposed scheme is highly useful for devices having (a) only ultra-lightweight memory, and (b) limited computational power (e.g. sensor nodes, RFID tags).

Available format(s)
Publication info
Published elsewhere. MAJOR revision.21st Information Security Conference (ISC 2018)
Verifiable and secure delegationmodular exponentiationscloud securitylightweight cryptography
Contact author(s)
osmanbey uzunkol @ gmail com
2018-07-06: received
Short URL
Creative Commons Attribution


      author = {Osmanbey Uzunkol and Jothi Rangasamy and Lakshmi Kuppusamy},
      title = {Hide The Modulus: A Secure Non-Interactive Fully Verifiable Delegation Scheme for Modular Exponentiations via CRT},
      howpublished = {Cryptology ePrint Archive, Paper 2018/644},
      year = {2018},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.