Microsoft SEAL and the Dawn of Homomorphic Encryption

While full homomorphic encryption (FHE) was originally achieved in 2009, it's starting to receive more attention now that computing power has caught up to its computational demands; however, the goal of homomorphic encryption goes back a decade.

A cursory search will find multiple definitions for it. This is the most direct and succinct:

A form of encryption that allows computation on ciphertexts generating an encrypted result that, when decrypted, matches the result of the operations as if they had been performed on plaintext.

— Massimo Bertaccini (Cryptography Algorithms)

Consider that statement for a moment. Homomorphic encryption enables operations to be performed on encrypted values such that the decrypted results produce the result of the operations as though they were performed on the original unencrypted values. The earliest mention I found is On Data Banks and Privacy Homomorphisms (1978) in which the authors are attempting to prevent sensitive financial data stored in an on-premise system from being accessed by system programmers using a remote time-sharing service.

Sensitive financial data is stored in the data bank. Time-sharing services that compute the data do not implement adequate security. System programmers have access to financial data. The paper states:

Use a special privacy homomorphism to encrypt its data so that the time-share computer can operate on the data without the necessity of decrypting it first.

To put it another way, I want to delete the processing of my data without giving away access to it.

To put it another yet another way, function(A, B) = function (A, B) where A and B are encrypted values of A and B, respectively. This enables third parties to compute encrypted data and provide the results without having any knowledge of the original value. With RSA, two values encrypted with the same key can be multiplied, and the product can be decrypted yielding the product of the encrypted values.

Obtain 5_6 using RSA(5)_ RSA(6):

1. RSA(5) = (5^17) mod 3233 = 3096

2. RSA(6) = (6^17) mod 3233 = 824

3. 3096*824 = 254864

4. RSA^-1(254864) = 254864^2753 (mod 3233) = 30

5. 5*6 = 30

   
   

However, this does not work for addition. RSA is a Partially Homomorphic Encryption (PHE) scheme in that it supports only multiplication. The timeline below shows the progression from (PHE) schemes through Somewhat Homomorphic Encryption (SHWE) which permits limited combinations of addition and multiplication. These operations could be repeated up to five times before reaching an invalid result. Then along came the first FHE scheme from Craig Gentry which enabled repeated addition and multiplication without fidelity loss.

Homomorphic Encryption Libraries

Since 2009, FHE schemes and libraries have proliferated.

Microsoft SEAL (Simple Encrypted Arithmetic Library) is developed in C++ 17 along with a C# wrapper. Originally released in 2015, it is still under active development. The github repo includes in-depth C# examples that should be explored if you are interested in diving further.

These schemes are supported by SEAL and include homomorphic operations for addition, division, subtractions, and exponentiation, but not division.

• Brakerski-Gentry-Vaikuntanathan (BGV)/Fan-Vercauteren (BFV)

  
  

  • Whole numbers (long)

  • Use if precision is a requirement

  • Computation is slower than CKKS

  • Values encrypted with BGV can be used with values encrypted with BFV

  • Values encrypted with BGV/BVF cannot be used with values encrypted with CKKS

  • Revisiting Homomorphic Encryption Schemes for Finite Fields

    
    

• Cheon-Kim-Kim-Song (CKKS)

  
  

  • Floating points (double)
  • Use if precision is not required
  • Values encrypted with CKKS cannot be used with values encrypted with BGV/BFV
  • Computation is faster than BFV/BGF

Encryption and Computation with Microsoft SEAL

These examples use the Microsoft.Research.SEALNet Nuget package and the CKKS scheme. Health trackers, like FitBit and AppleHeath, require giving up some privacy. They collect personal information like the number of steps and geocoordinates of the wearer's movements, heartbeat frequency, and other vital statistics. With homomorphic encryption, these health metric aggregators can still operate on our data without having access to the raw data.

In this simple example, the client sends run metrics including distance and time. The server aggregates the encrypted data and computes the average speed.

To get started, a public key is created by the client and shared with the server. It is used to encrypt data and also to perform arithmetic operations on encrypted data. Both client and server use an Encryptor. The client generates and retains a private key used for decryption used by the aptly named Decryptor.

A malicious party that intercepts the data could use the public key on the encrypted data and return it to the caller by spoofing the server. The server should sign the result and the client should verify the signature to ensure it's being returned from a trusted party.

using Microsoft.Research.SEAL;
protected SEALContext _context;
private KeyGenerator _keyGenerator;
private Encryptor _encryptor;
private Decryptor _decryptor;
protected IFitnessTrackerApiClient _apiClient;
. . .
_context = SEALUtils.GetContext(_config.Value.PolyModulusDegree, this.SchemeType);

_keyGenerator = new KeyGenerator(_context);

_keyGenerator.CreatePublicKey(out PublicKey publicKey);
_keyGenerator.CreateRelinKeys(out RelinKeys relinKeys);

_encryptor = new Encryptor(_context, _publicKey);
_decryptor = new Decryptor(_context, _keyGenerator.SecretKey);
. . .
PublicKeyModelCKKS keyModelCKKS = new(
  SEALUtils.KeyToBase64String(_publicKey), 
  SEALUtils.KeyToBase64String(relinKeys));
    await _apiClient.SendPublicKeyCKKSAsync(keyModelCKKS);

Relinearization keys are passed from client to server. Per Microsoft SEAL, they have no semantic meaning other than to reduce the size of Ciphertext following a multiplication operation.

At the command line, the user enters time and distance.

Each value is encoded to PlainText, then encrypted to Ciphertext, and finally encoded to base64 prior to sending it to the server.

using Microsoft.Research.SEAL;
var plaintext = new Plaintext();
_encoder.Encode(value, _scale, plaintext);

var ciphertext = new Ciphertext();
_encryptor.Encrypt(value, ciphertext);

using (var ms = new MemoryStream())
{
  ciphertext.Save(ms);
  return Convert.ToBase64String(ms.ToArray());
}

Since homomorphic encryption schemes don't support division (CKKS is no exception), the client needs to give the server an assist. The formula for speed is:

• distance/time

  
  

Another way to write it is,

• distance * (1/time)

  
  

So, the client sends:

RunItemCKKS metricsRequest = new(
  EncryptBase64(runItem.Distance), 
  EncryptBase64(runItem.Time), 
  EncryptBase64(1 / runItem.Time));

await _apiClient.AddNewRunningDistanceCKKSAsync(metricsRequest);

The server performs a similar bootstrapping function creating a SEALContext using only the public key and re-linearization keys, then processes the request:

var distance = SEALUtils.BuildCiphertextFromBase64String(request.Distance, _sealContext);
var time = SEALUtils.BuildCiphertextFromBase64String(request.Time, _sealContext);
var timeReciprocal = SEALUtils.BuildCiphertextFromBase64String(request.TimeReciprocal, _sealContext);
Ciphertext speed = new();

_evaluator.Multiply(distance, timeReciprocal, speed);
_evaluator.RelinearizeInplace(speed, _relinKeys);

_runListCKKS.Add(new EncryptedRunInfoCKKS(distance, time, speed));

A reciprocal of the time is used to calculate the speed for the submitted run and the RelinearizeInplace method reduces the size of the resulting Ciphertext. Distance, time, and speed are saved to an in-memory List.

The GetMetrics method aggregates the list and returns:

• total number of runs

• total distance

• total time

• average speed

  
  

  public SummaryItemCKKS GetMetrics()
  {
  int count = _runListCKKS.Count;
  
  var totalDistanceCKKS = SumEncryptedValues(_runListCKKS.Select(m => m.Distance));
  var totalTimeCKKS = SumEncryptedValues(_runListCKKS.Select(m => m.Time));
  var totalSpeed = SumEncryptedValues(_runListCKKS.Select(m => m.Speed));
  . . .
  protected Ciphertext SumEncryptedValues(IEnumerable<Ciphertext> encryptedData)
  {
  . . .
  Ciphertext encTotal = new();
  _evaluator.AddMany(encryptedData, encTotal);
  return encTotal;
  . . .
  }
  

  
  

To get the average speed, the reciprocal of the count is used, so rather than using:

(sum of speed)/number or runs we use:

(sum of speed) * (1/number of runs)

Since the server keeps track of the number of run submissions, the total number of runs is not an encrypted value. That unencrypted value can be converted to Plaintext and used in an operation performed on Ciphertext. While this is a simple example, the implications are worth noting. The server can provide additional values used on encrypted data enabling third-party providers to apply proprietary data to computations against customer-provided encrypted data.

In the example below, the total count is converted to a reciprocal and added to a List<double>. CKKS operations expect encrypted list values, even if the list only contains a single value. So, the List<double> is encoded to a PlainText. The MultiplyPlainInplace multiplies totalSpeed by (1/number of runs) resulting in the average speed. To conserve space, the result is applied to the totalSpeed Ciphertext and the re-linearization keys reduce the size of the output.

Plaintext encodedCountReciprocal = new();
List<double> averagePaceList = new();
double runCountReciprocal = 1 / (double)count;
averagePaceList.Add(runCountReciprocal);
_encoder.Encode(averagePaceList, _scale, encodedCountReciprocal);
        
_evaluator.MultiplyPlainInplace(totalSpeed, encodedCountReciprocal);
_evaluator.RelinearizeInplace(totalSpeed, _relinKeys);

The values are base64 encoded, returned, and decrypted on the client. The client takes the additional step of converting decrypted Plaintext to List<double>.

var payload = Convert.FromBase64String(encryptedDistanceText);

using var ms = new MemoryStream(payload);
var ciphertext = new Ciphertext();
ciphertext.Load(_context, ms);

var decryptedText = new Plaintext();
_decryptor.Decrypt(cypherText, decryptedText);

List<double> distanceList = new();
_encoder.Decode(decryptedText, distanceList);

Sending the following values yields totals and the average pace calculated by a service that tabulated the total and average without decrypting data sent from the client.

The server computes the data and returns the total runs, distance, time, and pace without decrypting any of the data sent.

Summary

Microsoft SEAL is a Microsoft Research project and is not ready for a production application. All classes implement IDisposable and used unmanaged resources. Production code would need to protect against a memory leak. The SEALContext class does not follow the single responsibility principle. It includes methods for both BGV/BVF and CKKS. Further, CKKS supports vector operations, but not vector addition. A single List<double> can be encrypted to a single CipherText but there is no means of summing the values in a single CipherText. It can be done with vector rotation, but that is a suboptimal solution.

This Fitness Tracker code sample is a simple introduction to a complex topic.  There are a number of compelling use cases with more involved logic:

• Gene marker detection

• Biometric template protection

• Secure human monitoring for aging in place

• Credit card fraud detection

  
  

Homomorphic encryption has largely been used in academia and in prototypes. Practical applications have been limited by the computing power required by homomorphic encryption schemes. GPU acceleration and ASIC processors will continue to erode this barrier. Intel is developing the FHE Hardware Accelerator, purpose-built for homomorphic encrypt schemes, in collaboration with Microsoft and DARPA. NASDAQ is also funding an R&D project using homomorphic encryption with machine learning for fraud detection. The FHE.org community is an excellent resource for the most current developments in this space. It has an active Discord server.

All code samples in this article are available at johniwasz/microsoft-seal-samples. For more in-depth Microsoft SEAL example, see these .NET examples.

Also published here.