International Association
for Cryptologic Research

Being required in many applications, modular exponentiations form the most expensive part of modern cryptographic primitives. It is a significant challenge for resource-constrained mobile devices to perform these heavy computations (e.g., mobile devices that require secure cryptographic computations or RFID tags). Cloud services can significantly enhance the computational capability of these devices. In this way, expensive computations at client side can significantly be reduced by means of secure outsourcing modular exponentiations to a potentially untrusted server S. In this paper, we study this problem which is an active research area of mobile and cloud computing, and mostly known as secure outsourced computation. We propose new efficient outsourcing algorithms for modular exponentiations using only one untrusted cloud service provider solving an open problem highlighted in [11]. These algorithms cover each possible case ranging from public-base & private-exponent, private-base & public-exponent, private-base & private-exponent to the most general private-basis & private-exponents simultaneous modular exponentiations. Our algorithms are the most efficient outsourced computation algorithms to date which use single untrusted server and have the best checkability (verifiability) property. Finally, we give two different real-life applications for outsourcing within the realm of Oblivious Transfer protocols and Blind Signatures.