implementing-homomorphic-encryption

Implementing Homomorphic Encryption

Overview

Homomorphic encryption (HE) enables computation on encrypted data without decryption. The data owner encrypts their data, sends the ciphertext to a computing party (e.g., a cloud processor under Article 28), and the computing party performs operations on the ciphertext. The encrypted results are returned to the data owner, who decrypts them to obtain the plaintext result. At no point does the computing party see unencrypted data.

This directly supports GDPR Article 32(1)(a), which identifies encryption as an appropriate technical measure, and Article 25(1), which requires data protection by design. HE enables a controller to outsource computation to a processor while maintaining cryptographic confidentiality of personal data.

HE Scheme Selection

Scheme Comparison

Decision Criteria

Parameter Selection Guide

For BFV/CKKS with Microsoft SEAL, the key parameters are:

Recommended parameter sets (128-bit security):

Architecture for GDPR-Compliant HE Processing

┌────────────────────────────────────────────────────────────┐
│              Data Controller (Prism Data Systems AG)        │
│  ┌──────────────────┐  ┌──────────────────────────────┐   │
│  │ Key Generator     │  │ Encrypt personal data        │   │
│  │ (sk stays here)   │  │ with public key              │   │
│  └────────┬─────────┘  └──────────┬───────────────────┘   │
│           │ pk, rlk, gk           │ ciphertext             │
└───────────┼───────────────────────┼────────────────────────┘
            │                       │
            ▼                       ▼
┌────────────────────────────────────────────────────────────┐
│              Data Processor (Cloud Service)                  │
│  ┌──────────────────────────────────────────────────────┐  │
│  │ Compute on ciphertext using pk, rlk, gk              │  │
│  │ (NEVER has access to sk — cannot decrypt)             │  │
│  │                                                        │  │
│  │ Operations: HE.Add, HE.Multiply, HE.Rotate           │  │
│  └──────────────────────────┬───────────────────────────┘  │
│                              │ encrypted result             │
└──────────────────────────────┼─────────────────────────────┘
                               │
                               ▼
┌────────────────────────────────────────────────────────────┐
│              Data Controller (Prism Data Systems AG)        │
│  ┌──────────────────────────────────────────────────────┐  │
│  │ Decrypt result using sk                               │  │
│  │ Plaintext result = f(data) computed without exposure   │  │
│  └──────────────────────────────────────────────────────┘  │
└────────────────────────────────────────────────────────────┘

Key:
  sk = Secret key (never leaves controller)
  pk = Public key (for encryption and computation)
  rlk = Relinearization keys (for ciphertext multiplication)
  gk = Galois keys (for ciphertext rotation/SIMD operations)

Performance Considerations

Benchmark Reference (Microsoft SEAL, BFV, N=8192, 128-bit security)

Optimization Strategies

Implementation Workflow

1. Identify computation — Define the exact mathematical function to compute on encrypted data. Express it as additions and multiplications (and rotations for SIMD).

1. Select scheme — Choose BFV for exact integer results, CKKS for approximate real-number results, TFHE for arbitrary boolean/integer functions.

1. Estimate circuit depth — Count the maximum number of sequential multiplications in the computation graph. This determines parameter requirements.

1. Select parameters — Choose polymodulusdegree and coeff_modulus to support the required depth at 128-bit security.

1. Implement and test — Implement the computation using an HE library. Test against plaintext reference implementation to verify correctness.

1. Benchmark — Measure encryption, computation, and decryption latency. Verify memory requirements are within infrastructure limits.

1. Deploy — Establish key management (secret key in HSM at controller, public keys distributed to processor), monitoring, and audit logging.

Key Regulatory References

• GDPR Article 25(1) — Data protection by design (encryption as a design measure)
• GDPR Article 32(1)(a) — Encryption as a security measure
• GDPR Article 28 — Processor obligations (HE enables processing without plaintext exposure)
• GDPR Recital 83 — Encryption to maintain security
• ENISA Report: Data Protection Engineering (2022)
• HomomorphicEncryption.org Standard: Homomorphic Encryption Standardization (2018)