Kristin Lauter (editor) - Protecting Privacy through Homomorphic Encryption

This Springer imprint is published by the registered company Springer Nature Switzerland AG

The registered company address is: Gewerbestrasse 11, 6330 Cham, Switzerland

This book is concerned with explaining methods for protecting privacy using Homomorphic Encryption. Privacy means different things to different people. In this volume, we will use the term privacy to refer to the notion defined by some social scientists as the guarantee that an individual or an organization should have the right to control how their data is used or shared. Privacy is not possible without tools from cryptography necessary to protect the security of data from unauthorized access or use.

Encryption is a tool for protecting data by transforming it using mathematical methods and the knowledge of a cryptographic key. Assuming a sound implementation of an encryption scheme and the hardness of the underlying mathematical problems, encryption can be used to protect both the security and the privacy of data. Traditional encryption schemes such as the US government standardized AES block cipher can be used to protect data while in transit or in storage. But to protect data while in use requires a new kind of encryption which allows for meaningful computation on ciphertexts without decryption. Such encryption is called Homomorphic Encryption (HE), because homomorphic is a common term in mathematics meaning to preserve structure. It means that the encryption map preserves the underlying algebraic structure of the data, resulting in the same output if the order of encryption and computation are exchanged.

The existence of a solution for Homomorphic Encryption was an open problem for more than three decades. A partially homomorphic encryption scheme was known already in the mid-1970s: RSA encryption allows for one operation on ciphertexts. But computation on todays (classical) computers is implemented as operations on bits described as circuits of AND and OR gates. So, two operations on encrypted data are required to implement general circuits for computation. The first blueprint for a solution was introduced by [1] in 2009, including the notion of bootstrapping to allow for arbitrary computation. The lattice-based solutions used in all the homomorphic encryption libraries today implement schemes based on the Ring Learning with Errors (RLWE) problem, which will be further explained in Part II. The first RLWE-based solution [2] was later extended to [3], and other proposed schemes followed, which will all be explained in Parts I and II. The first practical approach to computation on real data was introduced in [4], including the encoding of integers and real data as ciphertexts, replacing bitwise encryption. This led for example to techniques introduced in [5] for the first time to perform machine learning tasks on encrypted data, such as training models and using them for prediction, and eventually to the CryptoNets project [6] which demonstrated neural net predictions on encrypted data.

Any new proposal for cryptosystems based on hard mathematical problems must be thoroughly studied and reviewed by the scientific community before the public can be expected to adopt and trust it to protect the privacy and security of their data. New cryptographic proposals have typically seen at least a 10-year lag before widespread adoption in the industry, as was the case for Elliptic Curve Cryptography. Lattice-based cryptography was first introduced in the mid-1990s. There are no known efficient quantum attacks on general lattice-based schemes, so lattice-based key exchange and signature schemes are currently leading candidates in the ongoing 5-year National Institute of Standards and Technology (NIST) Post-Quantum Cryptography Standardization competition. But the parameters required for Homomorphic Encryption applications are quite a bit larger than for key exchange and signature schemes, and the protocols and applications are quite different. The idea of forming a community to standardize Homomorphic Encryption came out of a meeting between Kristin Lauter, Shai Halevi, Kurt Rohloff, Yuriy Polyakov, and Victor Shoup in New York City in April, 2015. Initial goals included developing common APIs to ensure interoperability of different implementations.

In 2017, Microsoft Research (MSR) Outreach funded the first Homomorphic Encryption Standardization Workshop, hosted at Microsoft in Redmond, WA, on July 1314, 2017. The workshop was co-organized by Kristin Lauter and Kim Laine from MSR, Roy Zimmermann from MSR Outreach, Lily Chen (NIST), Jung Hee Cheon (Seoul National University), Kurt Rohloff (NJIT/Duality), and Vinod Vaikuntanathan (MIT), with input from Shai Halevi (IBM/Algorand). This group now forms the Steering Committee for the Homomorphic Encryption.org open community which grew out of this meeting. This first workshop was organized as a collaboration meeting, with 36 invited participants divided into three working groups of 12. The groups were led by the workshop organizers, to work on writing three whitepapers on Security, API design, and Applications over the course of 2 days. The whitepapers were made available publicly several weeks after the workshop, after some additional work and editing. The papers were posted on the workshop webpage and on the Homomorphic Encryption.org website, which was set up along with email lists and discussion groups to continue the conversation on standardization of HE.