Homomorphic Encryption as a Solution of Trust Issues in Cloud

Khalid El Makkaoui, Abdellah Ezzati, Abderrahim Beni HssaneBdca 2015

Introduction

Cloud computing has revolutionized data storage and accessibility, yet a persistent "trust gap" prevents many sensitive sectors from fully embracing it. While encryption at rest is standard, the necessity of decrypting data for processing creates a significant security vulnerability. This paper explores Homomorphic Encryption (HE) as a solution to this problem, enabling computations on encrypted data without ever revealing the underlying plaintext.

The Problem: Level Two Trust in the Cloud

The primary obstacle to cloud adoption in fields like healthcare and finance is the requirement for cloud providers to access raw data during computation. The authors define a hierarchy of trust: Level One covers basic privacy and availability, while Level Two Trust demands confidentiality even during active processing.

Cloud computing architecture and trust model between client and provider.

As shown in the figure above, the client sends encrypted data and public keys to the cloud provider. The provider performs evaluation and storage. To achieve Level Two Trust, the processing server must be able to execute requests without decrypting the data, ensuring that even a compromised provider cannot access sensitive information.

Taxonomy of Homomorphic Encryption

The paper categorizes HE systems based on their functional capabilities. These are generally divided into three classes:

  • Partially Homomorphic Encryption (PHE): Supports a single type of operation (either addition or multiplication) for an unlimited number of times. Examples include RSA and ElGamal.
  • Somewhat Homomorphic Encryption (SWHE): Supports both addition and multiplication but is limited to a finite number of operations before the "noise" in the ciphertext makes decryption impossible.
  • Fully Homomorphic Encryption (FHE): Supports arbitrary computations (unlimited additions and multiplications).
Classification of various Homomorphic Encryption schemes into PHE, SWHE, and FHE.

The table above illustrates how common cryptographic schemes like Paillier and BGN fit into this taxonomy. The authors specifically focus on refining the Enhanced Homomorphic Encryption Scheme (EHES) to improve its security profile.

Identifying and Fixing the EHES Vulnerability

A core contribution of this research is the identification of a critical security flaw in the standard EHES algorithm. In certain edge cases—specifically when the random factor $r$ is a multiple of the prime $q$—the encryption function $Enc(x)$ can inadvertently return the original plaintext $x$. This "encryption to self" leaves data completely exposed.

To resolve this, the authors propose a mathematical refinement: $$Enc(x) = x + p^{rq} \pmod n$$ By utilizing the prime $p$ as a base for the exponent, the formula ensures that the ciphertext is always distinct from the plaintext, effectively closing the loophole.

Results and Operational Limits

The proposed "Enhanced EHES" successfully prevents the $Enc(x) = x$ failure state. However, the paper also notes operational boundaries for these systems. For instance, in multiplicative schemes like ElGamal, the product of messages must remain below the prime modulus $p$ to ensure successful decryption. Similar constraints apply to the sums and products in EHES.

Conclusion and Future Directions

While HE offers a robust theoretical framework for Level Two Trust, practical implementation remains challenging due to significant computational overhead, particularly for FHE. Future work will focus on empirical testing of the Enhanced EHES against standard benchmarks and exploring performance optimizations to make these secure processing methods viable for high-speed cloud environments.

Summary updated

BibTeX
@inproceedings{makkaoui2015homomorphic,
  author = {Khalid El Makkaoui and Abdellah Ezzati and Abderrahim Beni Hssane},
  title = {{Homomorphic Encryption as a Solution of Trust Issues in Cloud}},
  booktitle = {Bdca},
  year = {2015},
}
Figure