Homomorphic Encryption - CSU1530 - Shoolini U

Homomorphic Encryption

1. Introduction to Homomorphic Encryption

Homomorphic Encryption is a cryptographic technique that enables computations on encrypted data without needing to decrypt it first. When the result is decrypted, it matches the outcome as if the operations were performed on the original unencrypted data.

2. Basic Principles

The core idea is to allow mathematical operations on ciphertexts that correspond to operations on the plaintexts. This is achieved by constructing encryption schemes where specific algebraic structures are preserved during encryption.

2.1 Mathematical Foundations

Homomorphic Encryption relies on mathematical concepts that support operations on encrypted data. Key areas include:

2.1.1 Modular Arithmetic

In modular arithmetic, numbers wrap around upon reaching a certain value, called the modulus. This property is used in encryption schemes to perform operations on encrypted data without changing the modulus.

For example, the additive property:

$$ (a \mod n) + (b \mod n) \equiv (a + b) \mod n $$

This means that adding the remainders of \( a \) and \( b \) modulo \( n \) yields the same result as adding \( a \) and \( b \) first and then taking the modulo \( n \).

2.1.2 Lattice-Based Cryptography

Lattices are regular grids of points in multidimensional space. Cryptographic schemes based on lattices are considered secure against attacks from quantum computers. They provide a foundation for constructing Homomorphic Encryption schemes due to their mathematical properties.

3. Types of Homomorphic Encryption

Homomorphic Encryption schemes are categorized based on the types and number of operations they support on ciphertexts. The main categories are:

3.1 Partially Homomorphic Encryption (PHE)

PHE schemes support an unlimited number of operations of a single type (either addition or multiplication) on encrypted data. Examples include:

3.2 Somewhat Homomorphic Encryption (SHE)

SHE schemes support a limited number of both additions and multiplications on encrypted data. The limitation arises due to the accumulation of noise with each operation, which can eventually prevent correct decryption.

3.3 Fully Homomorphic Encryption (FHE)

FHE schemes allow unlimited additions and multiplications on ciphertexts. This enables arbitrary computations on encrypted data, making FHE highly versatile but also more complex and resource-intensive.

4. Applications

Homomorphic Encryption has significant implications in fields where data privacy is crucial. Some applications include:

4.1 Secure Cloud Computing

Users can outsource computations to cloud services without revealing their data. The cloud performs computations on encrypted data, and only the user can decrypt the results.

4.2 Privacy-Preserving Data Analysis

Allows analysis of encrypted datasets, such as medical or financial records, without compromising individual privacy.

4.3 Secure Voting Systems

Homomorphic Encryption can be used to tally encrypted votes, ensuring that individual votes remain confidential while providing an accurate election result.

5. Challenges and Limitations

Despite its potential, Homomorphic Encryption faces several challenges that affect its practical deployment.

5.1 Computational Overhead

Operations on encrypted data are much slower than on unencrypted data due to the complexity of the mathematical computations involved.

5.2 Ciphertext Size

Encrypted data can be several times larger than the original plaintext, leading to increased storage and transmission requirements.

5.3 Noise Management

Many Homomorphic Encryption schemes introduce noise into ciphertexts to ensure security. With each operation, the noise level increases, and excessive noise can render the ciphertext undecryptable.

6. Implementation Methods

Several Homomorphic Encryption schemes have been developed, each with specific features and suitable use cases.

6.1 RSA Cryptosystem

RSA is an example of a multiplicatively homomorphic scheme. It allows multiplication of ciphertexts to correspond to the multiplication of plaintexts.

Given plaintext messages \( m_1 \) and \( m_2 \), and public key exponent \( e \), the ciphertexts are:

$$ c_1 = m_1^e \mod n $$

$$ c_2 = m_2^e \mod n $$

The product of the ciphertexts corresponds to the product of the plaintexts:

$$ c_1 \cdot c_2 \mod n = (m_1 \cdot m_2)^e \mod n $$

This property can be useful in scenarios where multiplication of encrypted values is required.

6.2 Paillier Cryptosystem

Paillier is an additive homomorphic encryption scheme. It allows addition of ciphertexts to correspond to the addition of plaintexts.

Given plaintext messages \( m_1 \) and \( m_2 \), and random values \( r_1 \) and \( r_2 \), the ciphertexts are:

$$ c_1 = g^{m_1} r_1^n \mod n^2 $$

$$ c_2 = g^{m_2} r_2^n \mod n^2 $$

The product of the ciphertexts corresponds to the sum of the plaintexts:

$$ c_1 \cdot c_2 \mod n^2 = g^{m_1 + m_2} (r_1 r_2)^n \mod n^2 $$

This allows for the aggregation of encrypted data without revealing individual values.

6.3 Gentry's Fully Homomorphic Encryption

In 2009, Craig Gentry presented the first FHE scheme. It uses ideal lattices and introduces a technique called bootstrapping to manage noise.

Key Concepts:

Gentry's work paved the way for practical FHE implementations, though they remain computationally intensive.

7. Practical Illustration

Understanding Homomorphic Encryption can be enhanced by exploring real-world examples.

7.1 Secure Sum Calculation

Suppose two companies want to calculate the total of their confidential sales figures without revealing them to each other.

Steps:

  1. Each company encrypts its sales figure using an additive homomorphic encryption scheme.
  2. The encrypted values are sent to a third party or combined directly.
  3. The combined ciphertext is decrypted by an authorized party to obtain the total sales figure.

Benefits:

7.2 Encrypted Data Processing in the Cloud

A user wants to perform statistical analysis on their sensitive data using cloud computing resources.

Process:

  1. The user encrypts their data using a Homomorphic Encryption scheme.
  2. The encrypted data is uploaded to the cloud service provider.
  3. The cloud performs computations on the encrypted data.
  4. The results are sent back to the user, who decrypts them to obtain the analysis results.

Advantages:

8. Live Example

Homomorphic Encryption offers a powerful tool for performing computations on encrypted data, preserving privacy and security. Let's explore some live examples to illustrate its application.

9. Implementation of a Secure Voting System Using Homomorphic Encryption

This section outlines the development of a secure electronic voting system utilizing Homomorphic Encryption. The system ensures voter privacy and vote integrity by enabling vote tallying on encrypted ballots without decrypting individual votes.

9.1 Overview of the Voting System

The voting system allows voters to encrypt their choices using an additive homomorphic encryption scheme. The encrypted votes are sent to a central authority that aggregates them. The final tally is decrypted to reveal the election outcome without exposing individual votes.

9.2 System Components

The main components of the system include:

9.3 Homomorphic Encryption Scheme Used

The Paillier Cryptosystem is employed due to its additive homomorphic properties. It allows the addition of encrypted votes to correspond to the sum of the plaintext votes.

9.4 Implementation Details

The implementation involves the following steps:

9.4.1 Key Generation

The Election Authority generates a public and private key pair.

from Crypto.Util import number

def generate_keys(key_size):
    # Generate two large primes, p and q
    p = number.getPrime(key_size)
    q = number.getPrime(key_size)
    n = p * q
    g = n + 1
    λ = (p - 1) * (q - 1)
    μ = pow(λ, -1, n)
    public_key = (n, g)
    private_key = (λ, μ)
    return public_key, private_key
9.4.2 Vote Encryption

Each voter encrypts their vote using the public key.

def encrypt_vote(vote, public_key):
    n, g = public_key
    r = number.getRandomRange(1, n)
    c = pow(g, vote, n ** 2) * pow(r, n, n ** 2) % n ** 2
    return c

The variable vote represents the voter's choice, typically encoded as an integer.

9.4.3 Vote Collection

Encrypted votes are collected in the ballot box.

encrypted_votes = []
encrypted_votes.append(encrypt_vote(vote, public_key))
9.4.4 Homomorphic Tallying

The Election Authority aggregates the encrypted votes by multiplying them.

def aggregate_votes(encrypted_votes, public_key):
    n, _ = public_key
    total = 1
    for c in encrypted_votes:
        total = total * c % n ** 2
    return total

The product of the ciphertexts corresponds to the sum of the plaintext votes.

9.4.5 Decryption of Total Votes

The Election Authority decrypts the aggregated ciphertext to reveal the total vote count.

def decrypt_total(total_ciphertext, public_key, private_key):
    n, _ = public_key
    λ, μ = private_key
    x = pow(total_ciphertext, λ, n ** 2) - 1
    plaintext = ((x // n) * μ) % n
    return plaintext

9.5 Full Implementation Code

The complete code integrating all components is presented below.

from Crypto.Util import number

def generate_keys(key_size):
    p = number.getPrime(key_size)
    q = number.getPrime(key_size)
    n = p * q
    g = n + 1
    λ = (p - 1) * (q - 1)
    μ = pow(λ, -1, n)
    public_key = (n, g)
    private_key = (λ, μ)
    return public_key, private_key

def encrypt_vote(vote, public_key):
    n, g = public_key
    r = number.getRandomRange(1, n)
    c = pow(g, vote, n ** 2) * pow(r, n, n ** 2) % n ** 2
    return c

def aggregate_votes(encrypted_votes, public_key):
    n, _ = public_key
    total = 1
    for c in encrypted_votes:
        total = total * c % n ** 2
    return total

def decrypt_total(total_ciphertext, public_key, private_key):
    n, _ = public_key
    λ, μ = private_key
    x = pow(total_ciphertext, λ, n ** 2) - 1
    plaintext = ((x // n) * μ) % n
    return plaintext

# Key generation by Election Authority
public_key, private_key = generate_keys(512)

# Votes cast by voters (e.g., 0 for 'No', 1 for 'Yes')
votes = [1, 0, 1, 1, 0]

# Voters encrypt their votes
encrypted_votes = [encrypt_vote(vote, public_key) for vote in votes]

# Encrypted votes are aggregated
total_encrypted = aggregate_votes(encrypted_votes, public_key)

# Decryption of the total votes
total_votes = decrypt_total(total_encrypted, public_key, private_key)
print(f"Total 'Yes' votes: {total_votes}")

This code demonstrates a simplified voting system where voters cast a 'Yes' or 'No' vote encoded as 1 or 0. The total number of 'Yes' votes is calculated without revealing individual choices.

9.6 Security Considerations

To ensure the system's security and integrity, several factors must be addressed:

9.7 Extending the System for Multiple Candidates

For elections with multiple candidates, the system can be extended by representing votes as vectors and using more advanced homomorphic schemes.

Approach:

This method allows tallying votes for each candidate without revealing individual selections.

9.8 Practical Challenges

Implementing a real-world voting system involves additional complexities:

9.9 Testing and Validation

Thorough testing is essential to validate the system's correctness and security.