ExpSOS: Secure and Verifiable Outsourcing of Exponentiation Operations for Mobile Cloud Computing

Kai Zhou, M. H. Afifi, Jian Ren

This paper presents ExpSOS, a novel framework for securely offloading heavy cryptographic computations—specifically exponentiation—from mobile devices to the cloud. By leveraging ring homomorphism, the authors allow a resource-constrained device to disguise its sensitive data, let an untrusted server do the heavy lifting, and verify the result with nearly 100% certainty.

TL;DR

ExpSOS allows mobile devices to outsource expensive cryptographic operations (like modular exponentiation and elliptic curve scalar multiplication) to a single untrusted cloud server. It achieves massive speedups (up to 116x) while ensuring the cloud learns nothing about the private keys and can't cheat without being caught.

What Problem Does This Paper Address?

Modern security relies on public-key cryptosystems (like RSA or Elliptic Curve Cryptography), which require "exponentiation" operations ($u^a \pmod N$ or $sP$). These operations are computationally "expensive," draining the battery and CPU of mobile and IoT devices.

While "cloud outsourcing" seems like an obvious fix, it introduces two massive risks:

  1. Privacy: The cloud is "curious" and might try to steal the private exponent or the base data.
  2. Verifiability: The cloud might be "malicious" or "lazy," returning a fake or incorrect result to save its own computing resources.

Previous solutions often required two different cloud providers that promised not to talk to each other (non-collusion), which is a risky and impractical assumption. Others required the mobile device to do so much "pre-computation" that the benefit of outsourcing was lost.

Methods

The core innovation of ExpSOS is the use of Ring Homomorphism.

  1. Problem Transformation: The user maps their data from a standard ring ($\mathbb{R}_N$) to a much larger, "disguised" ring ($\mathbb{R}_L$) using a secret large prime.
  2. Blinding the Base: The base $u$ is transformed into $U = (u + rN) \pmod L$.
  3. Blinding the Exponent: The exponent $a$ is transformed into $A = a + k\phi(N)$.
  4. Cloud Computation: The cloud receives these blinded values and performs the exponentiation. Because of the homomorphic property, the cloud is essentially calculating the correct answer hidden inside a "noise" shell.
  5. Result Recovery: The user receives the result and simply applies a modulo operation ($Result \pmod N$) to strip away the noise and recover the true answer.
  6. Verification (The "Anti-Cheating" Mechanism): To handle malicious servers, the user sends two related queries. These queries are linked by a secret affine function ($A_2 = t_1 a + t_2 + k_2\phi(N)$). If the cloud tries to guess the relationship or return garbage, the mathematical check on the user's side will fail with a probability of nearly 1.

Datasets

As a theoretical cryptography paper, it does not use a "dataset" in the machine-learning sense. Instead, the authors evaluated the algorithm's performance through:

  • Simulation Environment: A real-world mobile device (Samsung GT-I9100, Dual-core 1.2 GHz CPU, 1 GB RAM) running Android 4.1.2.
  • Parameters: They tested varying bit-lengths for the modulus ($l_N$) from 128 to 1024 bits and security parameters ($l_b$) from 4 to 16 bits to measure the trade-off between security and speed.

Key Insights and Ideas

  • Single-Server Security: Unlike many predecessors, ExpSOS is secure even when using just one untrusted server. It eliminates the "non-collusion" headache.
  • Zero Pre-computation: Most existing schemes require the device to pre-calculate a table of values. ExpSOS requires no pre-processing, making it "instant" for the end-user.
  • Universal Applicability: The math works for both standard modular exponentiation (used in RSA/DSA) and scalar multiplication on elliptic curves (used in modern ECC), making it a "black box" tool for many protocols.
  • The Verifiability Probability: By adjusting a security parameter $b$, the user can reach a verifiability of $1 - 1/2b^2$. Even with a small $b$, the chance of the cloud successfully cheating is infinitesimally small.

Key Results

  • Computational Gain ($\tau$): The authors measured the ratio of local processing time vs. outsourcing time. For a 1024-bit operation, the mobile device saw a 116.2x speedup.
  • Local Efficiency: The mobile device only needs to perform about 3 to 5 modular multiplications locally.
  • Comparison: Compared to the best existing schemes (like those by Hohenberger or Chen), ExpSOS required fewer queries to the server and provided higher verifiability (approaching 1 vs. 1/2 or 2/3 in older models).
  • Real-world Apps: The paper successfully demonstrated ExpSOS being used for the Digital Signature Algorithm (DSA) and Identity-Based Encryption (IBE).

Limitations and Future Work

  • Security Parameter Trade-off: There is a linear trade-off; as you increase the security parameter $b$ to make cheating harder for the cloud, the local computational overhead on the mobile device increases slightly (logarithmically).
  • Communication Overhead: While the computation is offloaded, the device still has to send and receive data. In extremely low-bandwidth environments, the cost of data transfer might compete with the savings in CPU time.
  • Future Directions: The authors suggest applying this homomorphic approach to even more complex cryptographic primitives beyond simple exponentiation.

Summary updated

Abstract

Discrete exponential operation, such as modular exponentiation and scalar multiplication on elliptic curves, is a basic operation of many public-key cryptosystems. However, the exponential operations are considered prohibitively expensive for resource-constrained mobile devices. In this paper, we address the problem of secure outsourcing of exponentiation operations to one single untrusted server. Our proposed secure outsourcing scheme for general exponential (ExpSOS) only requires a very limited number of modular multiplications at local mobile environment, and thus it can achieve significant computational performance gain. ExpSOS also provides a secure verification scheme with probability approximately 1 to ensure that the mobile end users can always receive valid results. The comprehensive analysis as well as the simulation results in real mobile device demonstrates that our proposed ExpSOS can significantly improve the existing schemes in efficiency, security, and result verifiability. We apply ExpSOS to securely outsource several cryptographic protocols to show that ExpSOS can be widely applied to many computation-intensive applications and achieve significant performance improvement.
BibTeX
@article{zhou2017expsos,
  author = {Kai Zhou and M. H. Afifi and Jian Ren},
  title = {{ExpSOS: Secure and Verifiable Outsourcing of Exponentiation Operations for Mobile Cloud Computing}},
  journal = {IEEE Trans. Inf. Forensics Secur.},
  year = {2017},
  url = {https://openreview.net/forum?id=ZkLRFfPRFh},
}
Figure