The Future of Cryptography: Performing Computations on Encrypted Data

Third-party cloud services reduce complexity and offer flexibility for enterprises. However, organizations need to be able to entrust their data—and their customers’ data—to cloud service providers (CSPs) that are often incentivized to monetize these data. Meanwhile, regulations such as the US state of California’s California Consumer Privacy Act (CCPA),¹ the US Consumer Online Privacy Rights Act (COPRA) bill² and the EU General Data Protection Regulation (GDPR)³ aim to protect consumers’ privacy, and noncompliant organizations are subjected to severe fines and suffer damaged reputations. This results in a tradeoff between data privacy and utility for organizations.⁴ However, fully homomorphic encryption (FHE) allows organizations to ensure their customers’ privacy without undermining their ability to gain insights from their data.

Homomorphic encryption allows for computations of encrypted data without the need to decrypt them. Instead, the resulting computations are preserved in an encrypted domain (consider plaintext to be the unencrypted domain and ciphertexts to be the encrypted domain), which, when decrypted, results in an output the same as if the operations were performed on an unencrypted domain. FHE can be used for privacypreserving storage and computation. This allows data to be encrypted and outsourced to commercial cloud environments for processing while encrypted.⁵

Although there are many applications of FHE, consider two use cases: private contact discovery and log anomaly detection. For example, to add friends to a messaging service, users must upload their contact numbers or emails to the application’s servers. Although the user’s contacts may be encrypted for protection against eavesdropping during transmission to the application servers, the contacts must be decrypted on the servers to calculate hashes and detect any matches for others already using the service. The unencrypted data can be used in any manner, and users are forced to trust the application with their data. Another use case is detecting incidents of compromise (IoC) from log data. Third-party security tools such as security information and event management (SIEM) systems and extended detection and response (XDR) tools need access to unencrypted logs to detect anomalies. With FHE, these operations can be performed on encrypted data without compromising the privacy of the user’s data.

Fully Homomorphic Encryption

The FHE scheme was first envisioned in 1978, within a year of the RSA scheme’s publication.⁶ Partially homomorphic encryption schemes supporting either addition or multiplication already existed, including:

• RSA, an asymmetric encryption used in online data transfers, which is based on the practical difficulty of factoring the product of two large prime numbers
• ElGamal (multiplicative homomorphism), an asymmetric key encryption algorithm based on the Diffie-Hellman key exchange for public-key cryptography, which provides a method of sharing a secret key, but does not allow secure communication
• Paillier (additive homomorphism), a probabilistic asymmetric algorithm for public key cryptography based on the problem that computing n^th residue classes are computationally intensive

US computer scientist Craig Gentry first proposed an FHE scheme based on lattices in 2009.⁷ A lattice L(B) is the set of all integer combinations of the basis B={b₁,…, b_n} of n linearly independent vectors. That is, a lattice is defined as:

L(B)={ B ‧ z : z ϵ Zⁿ}

An FHE scheme supports both addition and multiplication (unlimited) operations, as illustrated by:

HE(a+b)=HE(a)+HE(b) and HE(a*b)=HE(a)*HE(b)

There are three types of homomorphic encryption schemes:⁸

1. Partially homomorphic encryption (PHE)—Allows only a limited set of operations to be performed on encrypted data
2. Somewhat homomorphic encryption (SHE)—Allows a limited number of operations up to a certain complexity to be performed
3. FHE—Allows any mathematical operation to be performed an unlimited number of times

Use Cases

FHE can achieve privacy-preserving computation in many scenarios, including the application of private information retrieval (PIR) protocol, private search, private contact discovery, secure multiparty computation (MPC) and log anomaly detection in SIEM or XDR.⁹ For example, the PIR protocol allows item retrieval from a server without revealing what was retrieved. MPC creates secure algorithms for involved users to jointly compute a function (process data) for their inputs while keeping those inputs private. In practice, Microsoft Edge applies FHE for password monitoring.¹⁰

With FHE, customer data privacy is ensured through cryptography, leveraging rigorous mathematical proofs.

As shown in figure 1, traditional (prevalent) cloud computation and storage solutions require customer data (by symmetric or asymmetric encryption schemes) to be decrypted before performing an operation (such as discovering how many of a user’s contacts are using a messaging service) or detecting any anomalies from system logs. This exposes potentially sensitive customer data to cloud vendors. Customers must trust their provider’s access control policies for data privacy.

With FHE, customer data privacy is ensured through cryptography, leveraging rigorous mathematical proofs. As a result, CSPs will not have access to unencrypted customer data for storage or computation. 

Homomorphic Computations

Some FHE (both additive and multiplicative) include Brakerski-Gentry-Vaikuntanathan (BGV), Fan-Vercauteren (FV) or Brakerski-Fan-Vercauteren (BFV), and Cheon-Kim-Kim-Song (CKKS).¹¹ All these schemes are based on the hardness of the ring learning with errors (RLWE) problem, where noise is added during encryption and key generation to achieve hardness properties. To understand how computations are allowed on encrypted data, it is helpful to explore the underlying mathematics used to perform partial homomorphism in RSA, ElGamal and Paillier, and full homomorphism in BFV schemes.

RSA Cryptosystem (Unbounded Number of Modular Multiplications)
If the RSA public key has modulus n and encryption exponent e, then the encryption of a message m is given by Ɛ(m)=me mod n. ¹² The multiplication of two encrypted messages in RSA is:

Ɛ(m₁) ‧ Ɛ(m₂)=m₁^e m₂^e mod n
=(m₁ m₂)^e mod n
=Ɛ(m₁ ‧ m₂)

As shown in figure 2, where the cells with darker (orange) backgrounds represent a correct result, adding two integers only yields an accurate result when the addition is zero or when adding any positive integer with a zero. In all other cases, it generates an incorrect summation.

Figure 3 shows the multiplicative nature of RSA, where it produces a correct result if the multiplication is nonnegative and an inaccurate result if the multiplication is negative.

ElGamal Cryptosystem (Unbounded Number of Modular Multiplications)
In the ElGamal cryptosystem, in a cyclic group G of order q with generator g, if the public key is (G, q, g, h), where h=gx and x is the secret key, then the encryption of a message m is Ɛ(m)=(gr, m ‧ hr ), for some random r Ɛ{0,…, q-1}.¹³ Multiplication of two ciphers in ElGamal is:

Ɛ(m₁) ‧ Ɛ(m₂ )=(g^r1, m₁ ‧ h^r1 ) (g^r2, m₂ ‧ h^r2)
=(g^r1+^r2, (m₁ ‧ m₂) h^r1+^r2 )
=Ɛ(m₁ ‧ m₂)

As shown in figure 4, ElGamal does not predictably produce a correct result for adding two integers. However, figure 5 shows the multiplicative nature of ElGamal, where it generates an accurate result for both negative and nonnegative multiplications.

Paillier Cryptosystem (Unbounded Number of Modular Additions)
In the Paillier cryptosystem, if the public key is the modulus n and the base g, then the encryption of a message m is Ɛ(m)=gm rn mod n2, for some random r Ɛ {0,…, n-1}.¹⁴ The addition of two encrypted messages in Pallier is:

Ɛ(m₁) ‧ Ɛ(m₂)=(g^m1r₁ⁿ)(g^m2r₂ⁿ) mod n²
=g^m1^+m2 (r₁ r₂)ⁿ mod n²
=Ɛ(m₁+m₂)

Fan-Vercauteren (FV) or Brakerski-FanVercauteren (BFV) Scheme
FV/BFV and BGV schemes are very similar, and the computations are performed on integers. However, in CKKS, calculations can be performed on complex numbers with limited precision.¹⁵ This implies that BFV and BGV are better choices to obtain accurate results, and CKKS is best suited for machine learning (ML) tasks as results in CKKS are approximated values.

BFV and CKKS allow batching to put a plaintext vector (batch) inside a single ciphertext. These so-called batched schemes pack multiple values into a single ciphertext (typically thousands) and perform operations on all the values for the cost of a single homomorphic operation. Batching is one of the more prominent sources of speedup since the discovery of FHE. CKKS is especially good for numeric and ML applications because the approximation it implies can be managed, and it uses faster encryption parameters than BGV and BFV.

To encrypt a plaintext message M in the plaintext domain P:¹⁶

• Generate a random polynomial u from R_2, where R_2 is the key distribution used to generate polynomials with integer coefficients -1,0 or 1.
• Generate two small random polynomials, e₁ and e₂ from χ, where χ is the error distribution (usually a discrete Gaussian distribution) defined with parameters mean μ and standard deviation σ over R bounded by some integer β. e₁ and e₂ are referred to as error or noise terms..
• A ciphertext C for a message M is a pair of values C₁ and C₂. C=(C₁,C₂) in encrypted domain C can be described as:

C₁=[PK₁ ‧ u+ e₁+ ∆M]_q
C₂=[PK₂ ‧ u+ e₂]_q

R_q is a uniform random distribution over R_q. The notation [ ‧ ] _q means that polynomial arithmetic should be done modulo q.¹⁷

For reference, homomorphic addition H₊ for two ciphertexts is:

H₊ (C⁽¹⁾ ,C⁽²⁾)=([C₁⁽¹⁾+C₁⁽²⁾]_q,[C₂⁽¹⁾+C₂⁽²⁾]_q )= (C₁⁽³⁾,C₂⁽³⁾
=([PK₁ ‧ (u⁽¹⁾+u⁽²⁾)+(e₁⁽¹⁾+e₁⁽²⁾)+ ∆(M⁽¹⁾+M⁽²⁾])_q,
([PK₂ ‧ (u⁽¹⁾+u⁽²⁾)+(e₂⁽¹⁾+e₂⁽²⁾)]_q
([PK₁ ‧ u⁽³⁾+e₁⁽³⁾+ ∆(M⁽¹⁾+M⁽²⁾)]_q, ([PK₂ ‧ u ⁽³⁾+e₂⁽³⁾]_q

Adding error to ciphers provides security but introduces limitations for multiplications as the error grows with each multiplication of ciphers. If the error grows large enough, the cipher can no longer be decrypted successfully.

Conclusion

FHE is the emerging champion of cryptography with potential use cases for PIR, MPC, private contact discovery and privacy-preserving log anomaly detection. FHE allows computations on encrypted data without decryption, which can help organizations comply with privacy regulations. The mathematical operations of partially homomorphic schemes—such as RSA, ElGamal and Paillier—and fully homomorphic BFV schemes are helpful for practitioners who wish to dive deep into FHE and incorporate it into their security projects. Tech giants are rooting for fully homomorphic encryption schemes (e.g., IBM Security offers fully homomorphic encryption as a service).^{18, 19} However, current computation limitations regarding the types of operations allowed and computation time remain a hurdle for immediate adaption.

Endnotes

¹ California Privacy Protection Agency (CPPA), “California Consumer Privacy Act Regulations,” USA, https://cppa.ca.gov/regulations/consumer_privacy_act.html
² US Senate, S.3195 Consumer Online Privacy Rights Act, 117^th Congress, USA, 2021, https://www.congress.gov/bill/117th-congress/senate-bill/3195
³ GDPR, “Complete Guide to GDPR Compliance,” https://gdpr.eu/
⁴ Dilmegani, C.; “What Is Homomorphic Encryption? Benefits and Challenges,” AI Multiple, 12 October 2022, https://research.aimultiple.com/homomorphic-encryption/
⁵ Zagakos, A.; “What Is Homomorphic Encryption?” FreeCodeCamp, 26 April 2022, https://www.freecodecamp.org/news/introduction-to-homomorphic-encryption
⁶ Rivest, R. L.; L. Adleman; M. L. Dertouzos; “On Data Banks and Privacy Homomorphisms,” Massachusetts Institute of Technology, Cambridge, Massachusetts, USA, 1978, https://luca-giuzzi.unibs.it/corsi/Support/papers-cryptography/RAD78.pdf
⁷ Gentry, C.; “Fully Homomorphic Encryption Using Ideal Lattices,” Proceedings of the 41^st Annual ACM Symposium on Theory of Computing, May 2009, https://dl.acm.org/doi/10.1145/1536414.1536440
⁸ Op cit Dilmegani
⁹ Bhattacharya, A.; “Homomorphic Encryption—Basics,” Encryption Consulting, 24 December 2020, https://www.encryptionconsulting.com/introduction-to-homomorphic-encryption/
¹⁰ Lauter, K.; S. Kannepalli; K. Laine; R. Cruz Moreno; “Password Monitor: Safeguarding Passwords in Microsoft Edge,” Microsoft Research Blog, 21 January 2021, https://www.microsoft.com/en-us/research/blog/password-monitor-safeguarding-passwords-in-microsoft-edge/
¹¹ Thaine, P.; “Homomorphic Encryption for Beginners: A Practical Guide (Part 1),” Medium, 26 December 2018, https://medium.com/privacy-preserving-natural-language-processing/homomorphic-encryption-for-beginners-a-practical-guide-part-1-b8f26d03a98a
¹² Vadhan, S.; A. Rosen; “Public-Key Encryption in Practice,” Introduction to Cryptography, Harvard John A. Paulson School of Engineering and Applied Sciences, Cambridge, Massachusetts, USA, 16 November 2006, https://people.seas.harvard.edu/~salil/cs120/docs/lec15.pdf
¹³ Chen, N.; “A Comparison of El Gamal and Paillier Cryptosystems,” University of California Santa Barbara, California, USA, June 2018, http://koclab.cs.ucsb.edu/teaching/cren/project/2018/Chen.pdf
¹⁴ Mohammed, S. J.; D. B. Taha; “Performance Evaluation of RSA, ElGamal, and Paillier Partial Homomorphic Encryption Algorithms,” IEEE 2022
International Conference on Computer Science and Software Engineering (CSASE), Mach 2022
¹⁵ Op cit
¹⁶ Inferati Inc., Introduction to the BFV FHE Scheme, USA, https://inferati.azureedge.net/docs/inferati-fhe-bfv.pdf
¹⁷ Ibid.
¹⁸  IBM, “Homomorphic Encryption Services,” https://www.ibm.com/security/services/homomorphic-encryption
¹⁹ Eatwell, A.; “Intel, Microsoft Push Homomorphic Encryption With Open-Source Moves,” Spiceworks, 10 January 2019, https://www.spiceworks.com/tech/artificial-intelligence/articles/intel-microsoft-push-homomorphic-encryption-with-open-source-moves/

Devharsh Trivedi

Is a Ph.D. candidate in cybersecurity at Stevens Institute of Technology (Hoboken, New Jersey, USA). He has worked as a senior software engineer at Philips and Oracle. He is a member of the Institute of Electrical and Electronics Engineers (IEEE) and enjoys volunteering at Positive Planet US as a chief information officer (CIO) and the ISACA New York, USA, Metropolitan Chapter as a data scientist. His publications are available at https://scholar.google.com/citations?user=zxkRN_MAAAAJ&hl=en&oi=ao and https://www.researchgate.net/profile/Devharsh-Trivedi