No description, website, or topics provided.
Switch branches/tags
Nothing to show
Clone or download
Latest commit 43ee650 Sep 8, 2017

README.md

Simple Homomorphic Encryption Library with Lattices (SHELL)

Introduction

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.

This library is designed to be compact and readable. The library includes just 1500 lines of heavily-commented source (700 lines of source, 600 lines of comments and 200 blank lines) and 900 lines of unit tests.

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

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 XPIR: Private Information Retrieval for Everyone.)

Ring Learning with Errors

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:

Preliminaries

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 Gaussian 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.

Key Generation

A secret key s is a polynomial whose n coefficients are drawn from the distribution Y.

Encryption

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. e is a random amount of error that makes it difficult to extract the error from the ciphertext.

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).

Decryption

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).

Homomorphic Addition

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.

Homomorphic Absorbtion

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.

Homomorphic Multiplication

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.

Error Growth

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

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

This library consists of four major components that form a RLWE stack.

Montgomery Integers

This library is implemented in montgomery.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 64-bit integers, meaning that it can support a modulus of up to 30-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.

NTT Polynomial

This library is implemented in ntt_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).

NTT Parameters

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.

Symmetric Encryption.

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.

Dependencies

This library requires the following external dependencies:

  • Bazel for building the library.

  • Google Test for unit testing the library. Bazel will automatically download Google Test from Github.

  • Protocol Buffers for data serialization. Bazel will automatically download Protocol Buffers from Github.

Acknowledgements

Although this library was written independently, the organization and several of the optimizations present in this library were drawn from the code underlying the New Hope RLWE key exchange protocol. This library benefited greatly from both the New Hope paper and New Hope codebase. We also thank Jonathan Frankle, who led the development of this library during an internship at Google.