Homomorphic Encryption with CKKS

Those in cryptography have a dream. And that dream is for data to be encrypted in every state: over-air, on-storage and in-process. While over-air and on-storage are typically well covered, the in-process element still remains a challenge. With this, in-process means that we process encrypted values with arithmetic operations.

Overall, we could have three values (x, y and z), and then encrypt with a public key (pk). We can then perform a homomorphic addition. The result can then be decrypted using the associated private key:

Overall, we have seen four generations of homomorphic encryption:

• 1st generation: Gentry’s method uses integers and lattices including the DGHV method [1].
• 2nd generation. Brakerski, Gentry and Vaikuntanathan’s (BGV) work in 2014 for FHE using Learning With Errors [4].
• 3rd generation: Lattice-based methods as defined by Brakerski and Vaikuntanathan (BFV) [2,3].
• 4th generation: CKKS (Cheon, Kim, Kim, Song) and which uses floating-point numbers [5].

Introduction

Homomorphic encryption can either be partially homomorphic somewhat homomorphic, levelled fully homomorphic, or fully homomorphic encryption. For security, the best case is full homomorphic encryption. HEAAN (Homomorphic Encryption for Arithmetic of Approximate Numbers) is a homomorphic encryption (HE) method proposed by Cheon, Kim, Kim and Song (CKKS) [paper].

Overall, it is a leveled approach which involves the evaluation of arbitrary circuits of bounded (pre-determined) depth. These circuits can include ADD (X-OR) and Multiply (AND). HEAAN uses a rescaling procedure to measure the size of the plaintext. It then produces an approximate rounding due to the truncation of the ciphertext into a smaller modulus.

The method is especially useful in that it can be applied to carry out encryption computations in parallel. Unfortunately, the ciphertext modulus can become too small, and where it is not possible to carry out any more operations. The HEAAN (CKKS) method uses approximate arithmetic over complex numbers (ℂ), and is based on Ring Learning With Errors (RLWE). It focuses on defining an encryption error within the computational error that will happen within approximate computations. We initially take a message (M) and convert to a cipher message (ct) using a secret key sk. To decrypt ([⟨ct,sk⟩]q), we produce an approximate value along with a small error (e).

The main parameters are:

• logN. Number of slots of plaintext values. This must be less than logP.
• logQ. The ciphertext modulus.
• logP. The scaling factor. The larger this is, the more accurace the answer will be.

RWLE

With RLWE [here] use the coefficients of polynomials and which can be added and multiplied within a finite field (Fq) [theory] and where all the coefficients will be less than q. Initially Alice and Bob agree on a complexity value of n, and which is the highest co-efficient power to be used. They then generate q which is 2n−1. All the polynomial operations will then be conducted with a modulus of q and where the largest coefficient value will be q−1. She then creates ai(x) which is a set of polynomial values:

Next Alice will divide by Φ(x), which is xn+1:

In Python this is achieved with:

xN_1 = [1] + [0] * (n-1) + [1]
A = np.floor(p.polydiv(A,xN_1)[1])

Practical examples

So let’s create a .NET program which integrates the Microsoft SEAL library. First we create a folder named “seal01”, and then go into that folder. We can create a Dotnet console project for .NET 8.0 with:

dotnet new console --framework net8.0

and go into the folder, and create a link to the SEAL library with:

dotnet add package Microsoft.Research.SEALNet --version 4.1.1

We then get a project file of [here]:

<Project Sdk="Microsoft.NET.Sdk">
<PropertyGroup>
    <OutputType>Exe</OutputType>
    <TargetFramework>net8.0</TargetFramework>
    <ImplicitUsings>enable</ImplicitUsings>
    <Nullable>enable</Nullable>
  </PropertyGroup>
  <ItemGroup>
    <PackageReference Include="Microsoft.Research.SEALNet" Version="4.1.1" />
  </ItemGroup>

</Project>

We then build with:

dotnet build

The code is [here]:

namespace SEALExample
{
    using System;
    using System.Text;
    using Microsoft.Research.SEAL;
class Examples
    {
        static void Main(string[] args)
        {

            var x=1.1;
            var y=2.2;
       
          if (args.Length >0) x=Convert.ToDouble(args[0]);
          if (args.Length >1) y=Convert.ToDouble(args[1]);

            using EncryptionParameters parms = new EncryptionParameters(SchemeType.CKKS);
          
            ulong polyModulusDegree = 8192;
            parms.PolyModulusDegree = polyModulusDegree;
            parms.CoeffModulus = CoeffModulus.Create(
                polyModulusDegree, new int[]{ 60, 40, 40, 60 });

            using SEALContext context = new SEALContext(parms);

            using KeyGenerator keygen = new KeyGenerator(context);
            using SecretKey secretKey = keygen.SecretKey;
            keygen.CreatePublicKey(out PublicKey publicKey);
    
            using Encryptor encryptor = new Encryptor(context, publicKey);
            using Evaluator evaluator = new Evaluator(context);
            using Decryptor decryptor = new Decryptor(context, secretKey);
            using CKKSEncoder encoder = new CKKSEncoder(context);
            ulong slotCount = encoder.SlotCount;
           
            List input1= new List((int)1);
            input1.Add(x);
            List input2= new List((int)1);
            input2.Add(y);
            double scale = Math.Pow(2.0, 30);
 
            Plaintext xPlain = new Plaintext();
            encoder.Encode(input1, scale, xPlain);
            using Ciphertext xEncrypted = new Ciphertext();
            encryptor.Encrypt(xPlain, xEncrypted);
            Plaintext yPlain = new Plaintext();
            encoder.Encode(input2, scale, yPlain);
            using Ciphertext yEncrypted= new Ciphertext();
            encryptor.Encrypt(yPlain, yEncrypted);

            using Ciphertext res = new Ciphertext();
            evaluator.Add(xEncrypted, yEncrypted,res);

            using Plaintext plainResult = new Plaintext();
            decryptor.Decrypt(res, plainResult);
            List result = new List();
            encoder.Decode(plainResult, result);
            
            Console.WriteLine("Secret key size: {0}",getSize(secretKey)); 
            Console.WriteLine("Public key size: {0}",getSize(publicKey.Data)); 
            Console.WriteLine("Encrypted size: {0}",getSize(xEncrypted)); 
         Console.Write ("\n{0}+{1}=",x,y); 
            Console.WriteLine(String.Format("{0:0.000}", result[0]));
        }

        static  int getSize(SecretKey obj )
        {
          var m = new MemoryStream();
          var p = obj; p.Save(m);
         return( m.ToArray().Length);
        }
        static  int getSize(Ciphertext obj )
        {
          var m = new MemoryStream();
          var p = obj; p.Save(m);
         return( m.ToArray().Length);
        }
  
    }

}

A sample run is:

Secret key size: 235369
Public key size: 470027
Encrypted size: 334149
1.1+2.2=3.300

We can see that we are using a polyModulusDegree of 8,192, and whic his the degree of the polynomial modulus parameter. The public key is 470,027 bytes and the secret key of 235,369 bytes. Overall, we have a number of slots for CKKS processing, and where we can run the processing in parallel for the number of slots. In this case we only use a single slot.

Other examples

The following are a few other examples of CKKS:

• CKKS Addition SEAL and C#. CKKS Addition using SEAL and C#. The SEAL library implements the CKKS homomorphic encryption method. This page will add two encrypted floating point values. .
• CKKS Multiplication SEAL and C#. CKKS Multiplication using SEAL and C#. The SEAL library implements the CKKS homomorphic encryption method. This page will multiply two encrypted floating point values. .
• CKKS Subtraction SEAL and C#. CKKS Subtraction using SEAL and C#. The SEAL library implements the CKKS homomorphic encryption method. This page will subtract two encrypted floating point values. .
• CKKS using SEAL and C#. CKKS using SEAL and C#. Homomorphic encryption can either be partially homomorphic, somewhat homomorphic, leveled fully homomorphic, or fully homomorphic encryption. For security, the best case is full homomorphic encryption. HEAAN (Homomorphic Encryption for Arithmetic of Approximate Numbers) is a homomorphic encryption (HE) method proposed by Cheon, Kim, Kim and Song (CKKS) [1]. We will evaluate y=a.x3+b.x+c.

Conclusions

The dream is alive, and is now developing at pace. This includes integrating homomorphic encryption with machine learning, and which would protect data from revealing its contents.

References

[1] Van Dijk, M., Gentry, C., Halevi, S., & Vaikuntanathan, V. (2010). Fully homomorphic encryption over the integers. In Advances in Cryptology–EUROCRYPT 2010: 29th Annual International Conference on the Theory and Applications of Cryptographic Techniques, French Riviera, May 30–June 3, 2010. Proceedings 29 (pp. 24–43). Springer Berlin Heidelberg.

[2] Zvika Brakerski. Fully homomorphic encryption without modulus switching from classical gapsvp. In Annual Cryptology Conference, pages 868–886. Springer, 2012

[3] Junfeng Fan and Frederik Vercauteren. Somewhat practical fully homomorphic encryption. 2012. https://eprint.iacr.org/2012/144.

[4] Brakerski, Z., Gentry, C., & Vaikuntanathan, V. (2014). (Leveled) fully homomorphic encryption without bootstrapping. ACM Transactions on Computation Theory (TOCT), 6(3), 1–36.

[5] Cheon, J. H., Kim, A., Kim, M., & Song, Y. (2017). Homomorphic encryption for arithmetic of approximate numbers. In Advances in Cryptology–ASIACRYPT 2017: 23rd International Conference on the Theory and Applications of Cryptology and Information Security, Hong Kong, China, December 3–7, 2017, Proceedings, Part I 23 (pp. 409–437). Springer International Publishing. [paper]