Table of Contents
    Home / Definitions / Homomorphic Encryption Explained
    Technology 9 min read

    Homomorphic Encryption Explained

    Medical clipboard and personal ID card with a padlock  connecting both

    Key Takeaways
    • Homomorphic Encryption computes encrypted data without decryption, ensuring data privacy.
    • The types include Partially Homomorphic Encryption (PHE), Somewhat Homomorphic Encryption (SHE), and Fully Homomorphic Encryption (FHE), each varying in operation complexity.
    • Useful in supply chain security, regulatory compliance, and private data analytics, enabling secure data sharing and processing.
    • Challenges include computational overhead, storage requirements, and implementation complexity, though ongoing research aims to address these issues.

    Homomorphic encryption

    “Is online data really secure?”

    Anyone who understands how the internet works and its potential vulnerabilities must ask this question at least once daily. Data breaches are a major concern for businesses, governments, and individuals worldwide. It has to be, considering the average time to identify a data breach inside an organization is about 206 days. 

    But what happens behind the scenes? What encryption algorithm protects our most sensitive data from falling into the wrong hands? Well, let’s discuss homomorphic encryption (HE), a cyber security approach to keeping data secure through encryption schemes even while it’s being processed.

    What is homomorphic encryption?

    Homomorphic encryption algorithms are an encryption method that allows computational calculations on the encrypted data before decryption. Traditional encryption requires decryption before any operations, but homomorphic encryption keeps your data secure through robust encryption schemes.

    So, how do we know when to use homomorphic encryption? 

    A simple illustration with George and Alice

    Consider a simple example to illustrate homomorphic encryption. Suppose Alice wants to share sensitive data with George so he can perform computations on it. Instead of sending the plaintext data, Alice encrypts it using homomorphic encryption schemes with her secret key.

    George receives the encrypted data and performs the computations directly on this encrypted data. He then returns the encrypted result to Alice, who uses her secret key to decrypt it and get the final output. Throughout this process, Bob never has access to the raw data or the secret key, ensuring its confidentiality.

    History of homomorphic encryption

    Homomorphic encryption schemes have been around for decades. The idea first took shape in 1978 when encryption functions known as privacy homomorphisms were first proposed. Cryptographer Craig Gentry developed the first applicable solution known as lattice-based cryptography, which is commonly thought of as first generation fully homomorphic encryption.

    Let’s take a walk through homomorphic encryption schemes history to understand the technology behind encrypted or decrypted data.

    Pre-FHE

    In 1978, researchers came up with the idea of fully homomorphic encryption, but it took them over 30 years to figure it out. Early cryptosystems like RSA and ElGamal allowed unlimited modular multiplications, while schemes like Goldwasser-Micali and Benaloh enabled unbounded XOR operations and modular additions, respectively. Although these schemes made progress, they couldn’t support arbitrary computations fully.

    First-generation FHE

    In 2009, Craig Gentry made significant advancements in HE by introducing the first functional fully homomorphic encryption scheme, which used lattice-based cryptography. His approach started with a somewhat homomorphic encryption scheme capable of limited computations. Gentry introduced bootstrapping to refresh noisy ciphertexts, maintaining their usability for more operations.

    His breakthrough allowed for theoretically infinite computations on encrypted data grounded in lattice problem complexity. However, early homomorphic encryption implementations were slow, taking about 30 minutes per bit operation.

    Second-generation FHE

    From 2011 to 2012, researchers like Zvika Brakerski and Vinod Vaikuntanathan developed more efficient FHE schemes, such as Brakerski-Gentry-Vaikuntanathan (BGV) and Boldyreva-Fan-Vercauteren (BFV), all named after the researchers. These leveraged the Ring Learning With Errors (RLWE) problem for security.

    Notably, BGV and BFV reduced noise growth during computations, enabling practical applications without constant bootstrapping. Innovations like packing multiple values into a single ciphertext further optimized performance, making these schemes and their encryption algorithms suitable for real-world uses.

    Third-generation FHE

    In 2013, Craig Gentry, Amit Sahai, and Brent Waters presented a novel Fully Homomorphic Encryption (FHE) method that eliminated the expensive relinearization steps required for multiplications. Subsequent advancements led to efficient bootstrapping methods, exemplified by schemes like FHEW, an FHE library, and Totally Functional Homomorphic Encryption (TFHE). FHEW and TFHE allowed rapid refreshing of ciphertexts, improving processing speed for homomorphic operations.

    Fourth-generation FHE

    In 2016, Cheon, Kim, Kim, and Song developed the CKKS scheme, named after its authors, supporting approximate fixed-point arithmetic. CKKS excelled in privacy-preserving machine learning applications due to its efficient rescaling operation, which managed noise without frequent bootstrapping. Despite introducing some approximation errors, CKKS became a preferred method for complex computations on encrypted data. Further research addressed potential vulnerabilities, enhancing the robustness of homomorphic encryption libraries.

    These generations of fully homomorphic encryption schemes highlight momentous strides in making secure, practical computations on encrypted data feasible, transforming sensitive data processing and protection.

    Types of homomorphic encryption

    There are three categories of homomorphic encryption algorithms, which vary in terms of the complexity and extent of operations on encrypted data.

    Partially Homomorphic Encryption (PHE)

    Partially homomorphic encryption offers a valuable balance between security and efficiency for applications requiring specific types of computations on encrypted data. While it lacks the flexibility of fully homomorphic encryption, its ability to perform unlimited operations of a single type makes it a practical choice for many real-world scenarios.

    Somewhat Homomorphic Encryption (SHE)

    Somewhat Homomorphic Encryption offers more flexibility. It can handle addition and multiplication, but only up to a certain complexity. This makes SHE suitable for a wider range of calculations, but can’t handle overly intricate computations.

    Fully Homomorphic Encryption (FHE)

    Fully Homomorphic Encryption is the ultimate power user of this cryptographic technology. It’s like having a supercomputer that performs any mathematical operation, addition, multiplication, and even more complex functions on encrypted data, and all without decryption. This makes FHE ideal for highly sensitive data analysis where complex calculations are required. However, this power comes at a cost—FHE is computationally expensive and requires more resources.

    RSA was named after its inventors, Ronald Rivest, Adi Shamir, and Leonard Adleman.

    Applications of homomorphic encryption

    Let’s explore industries where you might find a homomorphic encryption scheme in real life.

    Supply Chain Security

    Supply chain security involves managing and protecting the data related to the production, shipment, and delivery of goods. Different entities exchange sensitive information in global supply chains, such as production details, shipment schedules, and supplier data.

    A homomorphic encryption system allows companies to process sensitive supply chain data without exposing it. It achieves this by transforming it into encrypted data instead. This means that the data remains secure in the event of an interception during transmission. HE ensures only allowed parties can access and compute the data, maintaining the confidentiality and integrity of sensitive supply chain information.

    At the SAP TechEd event, Axel Schroepfer from the SAP Innovation Center Network shared a homomorphic encryption example that safeguards shared information with partners across a hyperconnected supply chain

    Regulatory Compliance

    Many industries, such as healthcare and finance, are subject to strict data privacy and security regulations. Compliance with regulations like GDPR, HIPAA, and PCI DSS requires robust methods for protecting sensitive information, like homomorphic encryption.

    Healthcare providers can encrypt patient data and outsource analysis to third-party vendors. The vendor can perform computations like fraud detection or trend analysis on the encrypted data without ever decrypting it, ensuring patient privacy while fulfilling regulatory requirements.

    Find out more about health care monitoring using a homomorphic encryption schemes, as explored on ResearchGate. 

    Private Data Analytics

    Businesses often possess valuable data that can be used for analytics but may be hesitant to share because of privacy concerns. Such limitations may hinder collaborative data analysis across companies.

    Companies can encrypt their datasets and participate in joint analysis projects. Using HE, secure computations can be performed on the combined encrypted data, allowing for insights without revealing the underlying information from each company.

    A study on the secure learning of classification outcomes over encrypted data leverages homomorphic encryption as the fundamental building block to enable secure learning of classification outcomes over encrypted data, all while preserving the privacy of the input data and the machine learning model.

    Homomorphic encryption schemes

    Several encryption schemes support homomorphic encryption, each with unique characteristics and applications. These schemes include:

    Rivest-Shamir-Adleman

    RSA is one of the earliest and most widely used encryption algorithms. It is primarily known for securing online communications. RSA is a public-key encryption scheme, meaning it uses two keys: a public key for encryption and a private key for decryption.

    RSA supports a form of multiplicative homomorphism. This means that the product of two ciphertexts corresponds to the product of their plaintexts once decrypted.

    ElGamal

    ElGamal is another early HE  scheme introduced by Taher ElGamal in 1985. It is also a public-key encryption system widely used in various cryptographic protocols. ElGamal supports multiplicative homomorphism. Specifically, the product of two ElGamal ciphertexts decrypts to the product of their corresponding plaintexts.

    Paillier

    The Paillier cryptosystem, introduced by Pascal Paillier in 1999, is a public-key encryption scheme known for its additive homomorphic properties. Unlike RSA and ElGamal, which focus on multiplicative operations, Paillier enables secure additions of encrypted values. Paillier supports additive homomorphism, allowing the sum of plaintexts to be derived from the product of their ciphertexts.

    Each scheme offers distinct advantages based on the type of homomorphic operations it supports, catering to various needs in secure data processing.

    Limitations of homomorphic encryption

    While this type of encryption offers significant benefits, it also has limitations:

    • HE is computationally intensive, leading to slower performance than traditional encryption methods.
    • Implementing and managing homomorphic encryption schemes can be complex, requiring specialized knowledge and expertise.
    • Homomorphic encryption’s complexity and performance issues have hindered its widespread adoption in many industries.

    The future of homomorphic encryption

    The future of homomorphic encryption is promising, with ongoing research and advancements aimed at overcoming its current limitations. Potential developments include:

    • Optimization: Enhancing the efficiency and speed of HE algorithms to make them more practical for real-world applications using encrypted data.
    • Standardization: Developing standardized protocols and frameworks to facilitate the implementation and interoperability of HE systems.
    • Integration: Seamlessly integrating HE with existing technologies, such as cloud computing and IoT, to enhance data security across various domains.

    As these advancements continue, HE will change how we approach data security and privacy. These changes will allow us to store encrypted data and share it securely. An advancement in homomorphic encryption offers the possibility of secure and private computations in our increasingly digital society.