This project is a library for fully-homomorphic symmetric-key encryption. It uses Ring Learning with Errors (RLWE)-based encryption to make it possible to both add and multiply encrypted data. It uses modulus-switching to enable arbitrary-depth homomorphic encryption (provided sufficiently large parameters are set). RLWE is also believed to be secure in the face of quantum computers.
We intend this project to be both a useful experimental library and a comprehensible tool for learning about and extending RLWE.
Discussion group: https://groups.google.com/forum/#!forum/shell-encryption/
THIS IS NOT AN OFFICIAL GOOGLE PRODUCT
Fully homomorphic encryption is a form of encryption that makes it possible to perform arbitrary computation on encrypted data.
For example, suppose that Alice creates a secret key s that she uses to encrypt the numbers 2 and 3, creating the ciphertexts {2}s and {3}s. In an additively homomorphic encryption scheme, Bob (who does not know the numbers inside the ciphertexts) could add the ciphertexts together, generating the message {5}s (the encryption of the number 5), or multiply the ciphertexts together, generating the message {6}s (the encryption of the number 6). The contents of the resulting message remain hidden to Bob. When he gives this result back to Alice, however, she can decrypt it to reveal the result of the computation.
When an encryption scheme is both additively and multiplicatively homomorphic, it is said to be fully homomorphic.
Homomorphic encryption has a vast number of applications. As in the example above, Alice can securely offload computation to another entity without worrying that doing so will reveal any of her private information. Among many other applications, it enables private information retrieval (PIR) - databases that can serve user requests without learning which pieces of data the users requested. (For more information on PIR, see Communication--Computation Trade-offs in PIR.)
The homomorphic encryption scheme that this library implements is based off of the Ring Learning with Errors problem. The security of this system derives from the conjectured difficulty of finding the shortest vector in a lattice. This document does not delve into the mathematical underpinnings of these proofs of hardness.
The cryptosystem implemented in this library is from Fully Homomorphic Encryption from Ring-LWE and Security for Key Dependent Messages. The cryptosystem works as follows.
Each object in the cryptosystems, including keys, messages, and ciphertexts, are made of polynomials. Each of these polynomials has degree n-1, where n is a power of 2. In other words, each of these polynomials has n coefficients.
Each of the coefficients of these polynomials is an integer (mod q), where q is a prime number equal to 1 (mod 2n). When we operate on these polynomials, we do so (mod xn+1).
We also need a modulus t that is much smaller than q. log(t) is the number of bits of plaintext information we are able to fit into each coefficient of a ciphertext polynomial. The importance of t will become apparent soon.
Finally, we need two other components: a binomial distribution Y with mean 0 and standard deviation w, where w is a parameter of the cryptosystem. The importance of this distribution will become apparent soon.
A secret key s is a polynomial whose n coefficients are drawn from the distribution Y.
A message m that is to be encrypted must be a polynomial with n coefficients, each of which is smaller than t.
To encrypt m with key s, select a polynomial e from the distribution Y and a polynomial a from the uniform distribution (each coefficient of a is chosen uniformly at random). e is a random amount of error that makes it difficult to extract the error from the ciphertext. Both a and e are nonces that should be regenerated freshly for each encryption.
The ciphertext consists of two polynomials. The first polynomial c0 = as + m + et. The second polynomial c1 = -a. The products between polynomials are computed using polynomial multiplications (mod xn+1).
Given a ciphertext (c0, c1), the ciphertext is decrypted by computing m = c0 + sc1 (mod t) = as + m + et - as (mod t) = m + et (mod t) = m. Recall that each coefficient of m was already (mod t).
To add two ciphertexts, simply add them component-wise. If we added the ciphertexts (c0x, c1x) and (c0y, c1y), we would get the ciphertext (c0x + c0y, c1x + c1y) = (axs + mx + ext + ays + my + eyt, -ax - ay) = ((ax + ay)s + (mx - my) + (ex + ey)t, -(ax + ay)).
If we let az = ax + ay and mz = mx + my and ez = ex + ey, the resulting ciphertext is (azs + mz + ezt, -az), which is just another ciphertext encrypting the sum of the original messages.
We can multiply a ciphertext containing the message m by another unencrypted polynomial p to get the encryption of the message mp. To do so, we simply multiply the components of the ciphertext by p: (cxp, c1p) = (aps + mp + ept, -ap), which is simply a ciphertext containing the message mp with error ep and a value of a that has been changed to ap.
Adding homomorphic multiplication to this library requires small tweaks to the aforementioned operations.
To multiply two ciphertexts (c0x, c1x) and (c0y, c1y), compute their cross product: (c0xc0y, c1xc0y + c0xc1y, c1xc1y).
Notice that the resulting ciphertext has three components, not the usual two. This is perfectly acceptable and all the aforementioned operations will work as before with small modifications:
Decryption entails taking the inner product of the vector of ciphertext polynomials and the vector of powers of the secret key (s0, s1, s2, ...) and reducing the result (mod t).
Addition entails adding the ciphertext vectors component-wise. If one vector is shorter than the other, simply extend it with polynomials with all-zero coefficients.
Absorption entails multiplying the plaintext polynomial p by each component of the ciphertext vector.
Observe that, after each homomorphic operation, the error in the resulting ciphertext grows. When adding, it grows additively, where in absorption and multiplication it grows exponentially. When the largest coefficient of polynomial that results from taking the inner product of the ciphertext vector (c0, c1, ...) and the vector of powers of the secret key (s0, s1, ...) surpasses q/2, too much error has built up and decryption will fail.
As you choose the parameters for your particular application, you will need to trace the growth of the sum of the error and the message carefully.
Addition: The error+message grows additively. Given two ciphertext with error+message sums mx + ext and my + eyt, the result of homomorphically adding these messages will have error mx + ext + my + eyt.
Absorption: The error+message of the result is equal to the product of (m + et) from the original ciphertext and p, the plaintext with which it is multiplied, and the number of coefficients in the polynomials n. In other words, the resulting error is np(m + et). The factor of n results from the fact that we perform a polynomial multiplication between p and (m + et).
Multiplication: Multiplying two ciphertext has an error equal to the product of their error+message values times n for the same reasons as listed in absorption.
One way of managing error is to set a larger modulus. Setting a larger modulus must be done with care, however. Security of RLWE derives partly from the ratio of modulus to error. If the modulus increases in size, so must the standard deviation of the error distirbution.
Modulus switching is a strategy to slow the rate of error growth when performing many levels of homomorphic multiplications. The explanation and implementation of this technique in this library derives from Fully Homomorphic Encryption without Bootstrapping.
Modulus switching takes a ciphertext converts a ciphertext from a larger modulus to a smaller modulus. Specifically, when converting from modulus q to modulus r, each coefficient of the ciphertext kq is multiplied by r, divided by q, and rounded to the nearest integer, producing kr. This value is then shifted up or down the minimum amount to ensure that kr = kq (mod t). This shifting ensures that the ciphertext will decrypt properly. When modulus switching, the error will scale with the shift in the modulus, keeping the modulus-to-error ratio constant.
To understand the benefit of modulus switching, consider the following example. Suppose four ciphertexts initially each have error e. After homomorphically multiplying them in pairs, we will have two ciphertexts each with error O(e2). When multiplying those two ciphertexts, the resulting error will be O(e4). In other words, when multiplying ciphertexts together, the exponent of the error will grow exponentially.
Modulus switching offers a way to reduce the complexity of the error growth. After computing two ciphertexts each with error x2, we shift from modulus q to modulus q/x. Doing so reduces the error of each ciphertext to x. The modulus-to-error ratio is the same as before. Were we to convert back to modulus q, the error would return to its original value. When we multiply these ciphertexts again, the overall error will be x2 (mod q/x). Were we to convert back to the original modulus, the overall error would be x3, dramatically smaller than without modulus switching.
This library has the ability to perform modulus switching.
This library consists of four major components that form a RLWE stack.
This library is implemented in montgomery.(cch|h). At the lowest level is a library that represents modular integers in Montgomery form, which speeds up the repeated use of the modulo operator. This library supports 128-bit integers, meaning that it can support a modulus of up to 126 bits. For larger modulus sizes, the higher levels of the stack can be parameterized with a different type (such as a BigInteger). Montgomery integers require several parameters in addition to the modulus to perform the modular operations efficiently. These values have been chosen for several common moduli in constants.h.
This library is implemented in polynomial.h. We store all polynomials in NTT (Number-Theoretic Transformation) form. A polynomial multiplication on standard polynomials can be computed with a coefficient-wise product on the same polynomials in NTT form, reducing the complexity of the operation from O(n2) to O(n).
This library is implemented in ntt_parameters.(cc|h). Converting to and from NTT form requires special parameters that this file generates. In production code, these parameters should be generated ahead of time for the chosen values of q and n and compiled as part of the final binary.
This library is implemented in symmetric_encryption.h. This library implements all of the cryptographic operations described earlier in ths document. It operates on polynomials in NTT form.
This library requires the following external dependencies:
Abseil for C++ common libraries.
Bazel for building the library.
BoringSSL for underlying cryptographic operations.
GFlag for flags. Needed to use glog.
GLog for logging.
Google Test for unit testing the library.
Protocol Buffers for data serialization.
In order to run the SHELL library, you need to install Bazel, if you don't have it already. Follow the instructions for your platform on the Bazel website.
You also need to install Git, if you don't have it already. Follow the instructions for your platform on the Git website.
Once you've installed Bazel and Git, open a Terminal and clone the SHELL repository into a local folder:
git clone https://github.com/google/shell-encryption.git
Navigate into the shell-encryption folder you just created, and build the SHELL library and dependencies using Bazel. Note, the library must be built using C++17.
cd shell-encryption bazel build :all --cxxopt='-std=c++17'
You may also run all tests (recursively) using the following command:
bazel test ... --cxxopt='-std=c++17'
If you get an error, you may need to build/test with the following flags:
bazel build :all --cxxopt='-std=c++17' --incompatible_disable_deprecated_attr_params=false --incompatible_depset_is_not_iterable=false --incompatible_new_actions_api=false --incompatible_no_support_tools_in_action_inputs=false
We also thank Jonathan Frankle, who contributed to this library during an internship at Google.