Introduction to FHE and our compiler

Fully homomorphic encryption (FHE) is the next generation of public key encryption schemes. Standard public key encryption allows anyone to share data in a secure way. However, you can't really do anything with this encrypted data, apart from decrypting it. That's where FHE comes in!

Using FHE, anyone can perform computations directly on private (i.e. encrypted) data—no need to decrypt.

We recommend starting with this article if you're new to FHE.

Why should I care about FHE?

FHE has applications to a variety of fields. We'll briefly consider two applications of FHE in the blockchain and machine learning space.

In blockchain, FHE enables privacy-preserving smart contracts. We have two parties in this setting: users and miners. Users can share their private data to the chain in the form of transactions. Miners can then run computations (encoded as smart contracts) directly on users' private data.

In machine learning, FHE allows for private inference. We have two parties in this setting: the user (who owns the data) and the server (who owns the trained machine learning model). The user can share her private data with the server. The server can then run the model on the user's encrypted data to give her a private prediction (which only she knows!).

Why haven't I already used FHE?

FHE used to be incredibly slow. Performance has come a long way in the past few years; operations that used to take seconds (or even minutes) now take milliseconds (if not microseconds).

As magical as FHE is, it's actually very hard to write FHE programs unless you're a cryptography expert (even then it's pretty hard). Researchers built various FHE compilers in an attempt to improve usability. Unfortunately, these compilers failed for one of the following reasons: they introduced a huge performance overhead, expected the user to know quite a bit about how FHE works, or were poorly designed for the target applications.

For FHE to see widespread adoption, we need usability and great performance.

Preliminary knowledge

To effectively use our library, we assume some basic knowledge of public key cryptography as well as Rust.

Cryptography and math

• Plaintext vs. ciphertext: Plaintext refers to unencrypted data (i.e. data in the clear) whereas ciphertext refers to encrypted data.
• Public key vs. private key: In public key cryptography, there are two types of keys. The public key (aka the encryption key) can be shared with others. Using the public key, people can send encrypted messages. The private key (aka the decryption key) should not be shared. Whoever holds the private key can decrypt the messages addressed to them (which are encrypted under the corresponding public key). Usually, each person has their own public/private key pair.
• "Homomorphic": We use this term to denote computations performed directly on encrypted data. For example, if we say "homomorphic addition," we are referring to addition of two ciphertexts.
• Modulus: We use this term in the context of discussing modular arithmetic (aka clock arithmetic). Under modular arithmetic, values "wrap around" when they exceed the modulus. In the example 7 mod 4 = 3, 4 is the modulus.

Rust and programming

• Rust basics (e.g. rust types, traits, .unwrap() and other error handling techniques)
• Generic types
• Generic functions

Why is a compiler needed for FHE?

Why is it so hard to write FHE programs?

Note: The following is not a precise description of the math behind FHE. Our goal is to give you a high level overview as to why it's hard to work with FHE directly.

FHE makes use of some pretty fancy math—namely, lattices. In fact, all known FHE schemes use lattice-based cryptography. Something special about lattice-based cryptography is that it's post-quantum.

You're likely familiar with matrices and vectors. Imagine that instead of having numbers as the entries in a matrix or vector, we replace them with polynomials (e.g. \(8x^5+5x^2+x+13\)). You might wonder: why would we want to have polynomials instead of numbers as entries? Well, replacing a number with a polynomial allows us to embed many numbers (as coefficients) in a single matrix entry, thus leading to better efficiency/performance. Recall that polynomials consist of coefficients (these would be 8, 5, 1, 13 in our example) and a degree/order (this is 5 in our example). However, these polynomials behave a bit differently than what you've seen in grade school.

Let's take a brief detour and discuss modular arithmetic (aka clock arithmetic). Modular arithmetic is just integer arithmetic that "wraps" around. Alternatively, you can think of it as division with remainder. For example, 13 mod 12 = 1.

The polynomials in FHE make use of modular arithmetic. The degree is actually mod some value; we'll say degree mod N. The coefficients are also mod some value; we'll say coefficient mod P.

So if I tell you to take the degree mod 3 and the coefficients mod 7, \(8x^5+5x^2+x+13\) becomes \(1x^2+5x^2+x+6\).

To get good performance in FHE, you need to know how to set these parameters (N, P) just right. If the parameters are too small, you'll be very limited in terms of the computations you can do. Alternatively, if you make the parameters too big, you'll end with poor performance and large ciphertext sizes. Even worse, you need to base your parameter choices off the maximum sequence of multiplications you plan on doing along with the desired security level.

Finally, I've neglected to mention how FHE programs actually work. Under the hood, FHE uses circuits. For the BFV scheme, we have arithmetic circuits (some other FHE schemes use binary circuits). When was the last time you tried to work directly with circuits (if ever)?

Our compiler handles picking all parameters and the appropriate keys for you. We abstract away the polynomials and circuits too.

Sunscreen's compiler

Our goal is to make it easy for any engineer to write an FHE program. To accomplish this, we've been working to get the API just right (we're always excited to hear feedback from users!). A large part of this was choosing the right language for our compiler— we chose Rust. In addition to having a powerful and expressive type system, Rust is very well suited to cryptography. It's highly performant (like C/C++) and safe by design (unlike C/C++).

Our compiler relies on Microsoft's SEAL library. There are many different types of FHE schemes out there; we've chosen to use the BFV fully homomorphic encryption scheme—named for the authors (Brakerski-Fan-Vercauteren) who came up with the scheme.

What features does our compiler offer?

This list isn't comprehensive. These are just the main features we'd like to call attention to:

• Type support for fractions, rationals, and signed integers (even 64-bit integers!)
• Ability to perform computations on combinations of plaintexts and ciphertexts (e.g. you can multiply a ciphertext and plaintext together)
• Can run computations without FHE (useful for testing purposes)
• Private computation with literals
• Automated parameter and key selection
• Ciphertext maintenance operations inserted automatically (these operations need to be done for optimal performance)
• Compiler generates FHE programs for you (no need to work with circuits)
• Compiler automatically parallelizes program (i.e. circuit) execution for you
• Support for WASM
• Support for serialization
• Can compile natively to Apple's M1

Note: Although we have performed a number of optimizations, we don't take advantage of all possible compiler transforms (yet!). Additionally, we do not currently allow users to author their own types.

Who should use our compiler?

You're building an application that operates on user data but you want to ensure all user data remains private.

You're a web3 engineer.

Our compiler was primarily designed with your web3 needs in mind!

You likely need all of the following features:

• Exact computation (since you're working with account balances and currency transfer)
• Compatibility with efficient ZKP schemes for trustless decentralized applications (we plan to provide the appropriate libraries for this)
• Support for fractions/rationals/big integers
• Fast arithmetic
• Exceptional performance overall

You may notice that FHE ciphertexts can sometimes be quite large. In the future, we'll help you manage this issue.

You're a web2 engineer.

Performance is very important to you; more importantly, the code needs to be easy to understand and write since you don't have the time to learn the intricacies of FHE or (god forbid) an entirely new language. You may need to perform 32 or even 64 bit computation.

Our compiler is great for many web2 applications (e.gg data analysis on private data). Comparisons on encrypted data are not currently supported; please keep this in mind when deciding if our compiler is best suited to your application. We will likely expand support to other FHE schemes in the future. The CKKS scheme, for example, is often better suited to privacy-preserving machine learning applications than the BFV scheme.

You're a researcher.

You want to quickly prototype FHE applications without fussing over the optimal parameter choice. However, performance is very important and you don't want to introduce a significant slowdown by working with an FHE compiler (over the FHE scheme directly).

We also provide advanced features that allow you to fine tune the plaintext modulus choice and noise margin if desired.

Compiler performance

We've benchmarked Sunscreen's compiler against existing FHE compilers (that support exact computation). We run a chi-squared test according to the criteria set out in this SoK paper on FHE compilers.

Time includes key generation + encryption + (homomorphic) computation + decryption.

Experiments were performed on an Intel Xeon @ 3.00 GHz with 8 cores and 16 GB RAM.

Our compiler is built on SEAL's implementation of the BFV scheme. For reference, if coded directly in SEAL and optimized manually by an expert, the chi-squared test can run in 0.053 s.

Getting started

This chapter walks through installation. We also provide an overview of Sunscreen through a simple example of multiplying two encrypted numbers.

Installation

Using Sunscreen in your app no different than any other Rust crate. However, while in private release, you must use Sunscreen's private registry.

In your repository, add/edit .cargo/config.toml and add the following line

sunscreen = { index = "https://crates.sunscreen.tech/git/index" }

under the [registries] section (or create one if not present).

In your Cargo.toml simply add

sunscreen = { version="0.4.0", registry="sunscreen" }

to your application's Cargo.toml [dependencies] section.

You also need cmake, clang, and a C++ compiler toolchain installed on your machine and visible in your $PATH. If you have ever built any other crate that wraps a C++ library, you may already be done.

Linux

Using Yum (e.g. CentOS)

In your terminal, run

sudo yum install cmake3 clang git

Use gcc10-g++ as your compiler

In some distros (e.g Amazon Linux), the default compiler (i.e. gcc7 from the gcc-c++ package), crashes when building SEAL. If g++ --version yields version 7, you need to install and use gcc10.

Run

sudo yum install gcc10 gcc10-c++

then

export CC=/usr/bin/gcc10-gcc
export CXX=/usr/bin/gcc10-g++

before building your application with Cargo. You may wish to add these exports to your shell's rc file (e.g. ~/.bash_profile).

Using Apt (e.g. Debian)

sudo apt install build-essential cmake3 clang git

On some distros (e.g. Ubuntu), the cmake package is already version 3 and you can just use it directly.

Alias cmake3 as cmake

Then, make cmake3 appear in your $PATH as cmake. A simple way to do this is run

sudo ln /usr/bin/cmake3 /usr/bin/cmake

However, this globally creates a hard link for all users and may conflict with also installing the cmake (CMake 2.x) package. As an alternative, you can simply create the hard link or symlink somewhere under your $PATH with higher search precedence than /usr/bin.

MacOS

Using Brew

brew install cmake git

When you first attempt to build your application, MacOS will prompt you to install the command-line developer tools. Do this.

Windows

Install Rust toolchain

Install the MSVC C++ toolchain

When prompted for what to install, ensure you additionally check the Windows 10 SDK. You'll need to rerun the tool and modify your installation if you forget to do this.

Install Rustup. Run the executable and hit return a bunch of times to accept the default options.

Cmake

Install cmake 3.

When prompted, add cmake to either the system or user path. You can also do this later by editing your system's environment variables.

Clang

Install llvm+clang. In the installer, select the option to add LLVM to your %PATH%. If you forget to do check this option, add C:\Program Files\LLVM\bin to your %PATH%.

git

Install git. Defaults are fine.

My first FHE program

Now that we have installed the Sunscreen crate as a dependency, let's get started writing our first private app using FHE! Writing our program will be a gradual process and we'll add more code as we progress through this section.

In this example, we'll just multiply two encrypted integers.

use sunscreen::{
    fhe_program,
    types::{bfv::Signed, Cipher},
    Compiler, Error, Runtime,
};

#[fhe_program(scheme = "bfv")]
fn simple_multiply(a: Cipher<Signed>, b: Cipher<Signed>) -> Cipher<Signed> {
    a * b
}

fn main() {
}

Notice that the simple_multiply function is like any other function in Rust, except for the #[fhe_program(...)] attribute. This is where the magic happens— it declares your function as an FHE program that can be compiled. The scheme argument should always be "bfv", though we may support additional FHE schemes in the future.

simple_multiply's signature specifies that it takes in two Cipher<Signed> values and returns one. Cipher<T> indicates the contained type T is encrypted (i.e. a ciphertext) and Signed is Sunscreen's signed integer type; thus, Cipher<Signed> indicates that we have an encrypted signed integer. The body of simple_multiply multiplies the ciphertexts a and b together. As with any function in Rust, omitting a ; returns an expression's value from the current scope.

Having specified our program, let's compile it.

use sunscreen::{
    fhe_program,
    types::{bfv::Signed, Cipher},
    Compiler, Error, Runtime,
};

#[fhe_program(scheme = "bfv")]
fn simple_multiply(a: Cipher<Signed>, b: Cipher<Signed>) -> Cipher<Signed> {
    a * b
}

fn main() -> Result<(), Error> {
    let fhe_program = Compiler::with_fhe_program(simple_multiply)
        .compile()?;

    Ok(())
}

The Compiler::with_fhe_program(simple_multiply) line creates a compiler and .compile(), tells it to compile our FHE program. Compilation performs optimization and fills in implementation details, including figuring out FHE scheme parameters and inserting special operations.

What's the ? after at the end of .compile()? For the uninitiated, the ? operator propagates errors. Fallible expressions in Rust emit Results, which can contain either a value or an error. Using ? unwraps the value in a successful result or immediately returns the error from a failed one, letting the caller of the current function deal with it. We should see the former after compilation, as our program is well-formed.

Next, we need a public and private key pair. In order to generate keys, we'll first construct a Runtime with the parameters we got from compilation. This allows us to encrypt/decrypt data and run FHE programs.

use sunscreen::{
    fhe_program,
    types::{bfv::Signed, Cipher},
    Compiler, Error, Runtime,
};

#[fhe_program(scheme = "bfv")]
fn simple_multiply(a: Cipher<Signed>, b: Cipher<Signed>) -> Cipher<Signed> {
    a * b
}

fn main() -> Result<(), Error> {
    let fhe_program = Compiler::with_fhe_program(simple_multiply)
        .compile()?;

    let runtime = Runtime::new(&fhe_program.metadata.params)?;

    let (public_key, private_key) = runtime.generate_keys()?;

    let a = runtime.encrypt(Signed::from(15), &public_key)?;
    let b = runtime.encrypt(Signed::from(5), &public_key)?;

    Ok(())
}

After constructing our runtime, we generate a public and private key pair by calling runtime.generate_keys().

Next, we call Signed::from(15) to make an unencrypted Signed integer equal to 15. Rust doesn't allow implicit type conversion as some languages do, so we use the From trait to explicitly convert a Rust i64 into a Sunscreen Signed.

Once we have our plaintext value 15, we encrypt it by calling runtime.encrypt(...), passing in the value and our public key. We repeat this process for b with the value 5. Now that we have the two ciphertexts a and b to give to simple_multiply, we're ready to run our FHE program!

use sunscreen::{
    fhe_program,
    types::{bfv::Signed, Cipher},
    Compiler, Error, Runtime,
};

#[fhe_program(scheme = "bfv")]
fn simple_multiply(a: Cipher<Signed>, b: Cipher<Signed>) -> Cipher<Signed> {
    a * b
}

fn main() -> Result<(), Error> {
    let fhe_program = Compiler::with_fhe_program(simple_multiply)
        .compile()?;

    let runtime = Runtime::new(&fhe_program.metadata.params)?;

    let (public_key, private_key) = runtime.generate_keys()?;

    let a = runtime.encrypt(Signed::from(15), &public_key)?;
    let b = runtime.encrypt(Signed::from(5), &public_key)?;
    
    let results = runtime.run(&fhe_program, vec![a, b], &public_key)?;
    
    let c: Signed = runtime.decrypt(&results[0], &private_key)?;
    assert_eq!(c, 75.into());

    Ok(())
}

We call runtime.run(...) to execute our FHE program. For the first argument, we pass in our previously compiled program fhe_program. The second argument is always a Vec containing the arguments to the FHE program. In this case, we pass in the encrypted a and b values. You'll need to pass in the public_key as well.

What would happen if we forgot to encrypt one of our values or gave an encrypted Fractional value where the program wanted an encrypted Signed value? Fortunately, the run method first performs some sanity checks to ensure the arguments match the call signature. If the types of the values we pass in don't match the signature, the run method returns an error Result. The ? propagates this error, but our program exits because this is the main() method!

Next, we call runtime.decrypt(...) with the first result and our private key. Programs can return more than one value; hence, results is a Vec. Since our FHE program only returns one value, we decrypt the value at index 0. The left hand side of the assignment denotes the decrypted data is a Signed whereas runtime.decrypt(...) ensures this type matches the ciphertext's encrypted value before decryption. If we had assigned a different type to c, say Fractional, then decrypt would return an error.

Finally, we verify the result equals 75 (i.e. 15 * 5) as expected.

What's in an FHE program?

This section describes the anatomy of an FHE program, what you can and can't do, and the different data types FHE programs support.

Types

Sunscreen supports a number of data types for different scenarios. Each of these data types is located in the sunscreen_compiler::types::bfv module.

All types T support +, -, * operations on plaintext, ciphertext, and literals. Note that at least one of the operands must be a ciphertext.

• Use Signed if you need to work with integers.
• Use Fractional if you need to work with decimals (but don't anticipate needing to divide by ciphertexts).
• UseRational if ciphertext division is absolutely necessary to your application. This type incurs more overhead than Fractional.

Cipher

The Cipher type is special in that you don't directly create Cipher values. Cipher<T> should only appear in an FHE program's call signature and denotes that an argument or return value is an encrypted T. The absence of this wrapper indicates that T is unencrypted.

While arguments may be unencrypted (i.e. of type T), return values must always be encrypted (i.e. of type Cipher<T>).

For example:

#![allow(unused)]
fn main() {
use sunscreen::{
    fhe_program,
    types::{bfv::Signed, Cipher},
};

#[fhe_program(scheme = "bfv")]
fn my_program(a: Cipher<Signed>, b: Signed) -> (Cipher<Signed>, Cipher<Signed>) {
    // Do things
    (a, a + b)
}
}

• Argument a is an encrypted Signed value.
• Argument b is an unencrypted Signed value.
• my_program returns 2 encrypted Signed values via a tuple.

Arrays

Sunscreen supports fixed-length arrays¹ that behave as you'd expect. You declare and use them as any other fixed-length array in Rust:

#![allow(unused)]
fn main() {
use sunscreen::{
    fhe_program,
    types::{bfv::Fractional, Cipher},
};

#[fhe_program(scheme = "bfv")]
fn matrix_vector_multiply(a: [[Cipher<Fractional<64>>; 10]; 10], b: [Cipher<Fractional<64>>; 10]) -> [Cipher<Fractional<64>>; 10] {
    // Clone b just so we get an initialized object of the right
    // type in col.
    let mut col = b.clone();

    // Perform matrix-vector multiplication with col_query to extract
    // Alice's desired column
    for i in 0..10 {
        for j in 0..10 {
            if j == 0 {
                col[i] = a[i][j] * b[j];
            } else {
                col[i] = col[i] + a[i][j] * b[j];
            }
        }
    }

    col
}
}

You can make arrays of encrypted or unencrypted data types. In the former case, the Cipher must go inside the array; you can't declare a Cipher<[T; 2]>.

TODO: add discussion on using arrays as inputs to FHE programs (readable vs writeable). having to initialize writeable arrays. cannot return arrays from FHE programs.

Working with literals

Sometimes, you simply want to double a value or add 15. Fortunately, most FHE types and operations support literal operands.

For example, Signed values work with i64 values

#![allow(unused)]
fn main() {
use sunscreen::{
    fhe_program,
    types::{bfv::Signed, Cipher},
};

#[fhe_program(scheme = "bfv")]
fn answer(a: Cipher<Signed>) -> Cipher<Signed> {
    a + 42
}
}

while Fractional and Rational values support f64 values

#![allow(unused)]
fn main() {
use sunscreen::{
    fhe_program,
    types::{bfv::Fractional, Cipher},
};

#[fhe_program(scheme = "bfv")]
fn answer_2(a: Cipher<Fractional<64>>) -> Cipher<Fractional<64>> {
    42.0 * a
}
}

Signed

Signed values allow you to perform integer arithmetic as follows (recall that at least one operand must be a ciphertext):

Additionally, you can perform unary negation on encrypted Signed values.

Representation

Signed values contain thousands of binary digits of precision, easily enough to store any i64 value.

Fractional

Fractional values allow you to perform decimal arithmetic. You can think of Fractional as being similar to a fixed-point representation.

Sunscreen represents Fractional values as an integer and fractional part. The INT_BITS type argument specifies how many binary digits store the integer part. Setting INT_BITS to 64 should be more than sufficient for most applications since Fractional<64> values can exactly represent every i64 with thousands (!!) of binary digits for the decimal portion.

You can perform operations on Fractional values as follows (recall at least one operand must be a ciphertext):

Additionally, you perform unary negation on Fractional ciphertexts.

While division by only literals may seem limiting, this is one of the more common use cases. For example, you can average 3 values:

#![allow(unused)]
fn main() {
use sunscreen::{
    fhe_program,
    types::{bfv::Fractional, Cipher},
    Compiler, Runtime, PublicKey
};

#[fhe_program(scheme = "bfv")]
fn avg(
    a: Cipher<Fractional<64>>,
    b: Cipher<Fractional<64>>,
    c: Cipher<Fractional<64>>
) -> Cipher<Fractional<64>> {
    (a + b + c) / 3.0
}
}

Additionally, division by literals is sufficient to compute many transcendental functions (e.g. sin, cos, exp) via a power series.

Representation

A scheme parameter lattice_dimension (chosen by the Sunscreen compiler) determines the number of decimal places such that INT_BITS + DECIMAL_BITS = lattice_dimension. This scheme parameter is always at least 1024. You can find the compiler's chosen value with my_compiled_program.metadata.params.lattice_dimension.

Fractional values use exact arithmetic and don't suffer from roundoff errors as floating point values do. In fact, if INT_BITS=1024 and lattice_dimension >= 2048 they can exactly store every double precision value with a fixed decimal point!

Efficiency

Unlike the Rational type, storing and computing Fractional values is as efficient as Signed values.

Rational

The Rational type allows you to perform all decimal arithmetic:

Additionally, you can perform unary negation on Rational ciphertexts (i.e., given a, compute -a).

Representation

Rational encodes a numerator and denominator as two independent Signed values. This results in ciphertexts twice as large as when using the Fractional type.

Efficiency

In addition to the increased size, each Rational operation (except negation) requires multiple FHE operations. Thus, even addition can quickly increase FHE program complexity. Using Rational ciphertexts in prolonged computation may require larger scheme parameters (hence resulting in slower computations).

Writing an FHE program

An FHE program is simply a Rust function with an annotation and a few restrictions. However, unlike standard Rust functions, FHE programs work with encrypted data!

The #[fhe_program(...)] attribute

To indicate that a function is an FHE program, simply add the #[fhe_program()] attribute to an fn function:

#![allow(unused)]
fn main() {
use sunscreen::{
   fhe_program,
};

#[fhe_program(scheme = "bfv")]
fn my_fhe_program() {
}
}

This attribute takes a single scheme argument. Currently, this argument value should always be "bfv", our supported FHE scheme.

FHE program interface requirements

FHE programs implement their logic in the fn function beneath the #[fhe_program()] attribute. The function you write must satisfy some conditions:

• Your fn function must be non-generic and stand-alone (i.e. not a struct method, closure, trait method, etc).
• Your fn function may take any number of arguments.
• Each argument must be of either type T (i.e. plaintext) or Cipher<T> (i.e. ciphertext), where T is a type supported in FHE programs. Every argument need not be the same T.
• Your fn function must return either a Cipher<T> or a tuple of (Cipher<T1>, Cipher<T2>, ...) values (i.e. return values are always encrypted). As with arguments, types must be supported in FHE programs.

Here's an example of an FHE program that returns a tuple containing two encrypted values: a * b and a + c.

#![allow(unused)]
fn main() {
use sunscreen::{
    fhe_program,
    types::{bfv::Signed, Cipher},
};

#[fhe_program(scheme = "bfv")]
fn multiple_returns(a: Cipher<Signed>, b: Cipher<Signed>, c: Signed) -> (Cipher<Signed>, Cipher<Signed>) {
    (a * b, a + c)
}
}

Operations

In FHE programs, you can:

• Perform basic operations (+, -, *, /, <<, >>). The supported set of operations vary from type to type. Note that at least one of the operands must be a ciphertext.
• Call functions.
• Use any Rust construct (e.g. match, for i in ..., if...else) on data not derived from any argument. We walk through a number of examples in the limitations chapter.

Factoring FHE programs

In this section we'll show you how to factor your programs in a specific way that allows for

• Reusing algorithms with different data types.
• Running your algorithm without FHE. This allows you to debug the algorithm without encryption getting in your way and measure FHE's performance overhead.

Let's begin by rewriting our simple_multiply example with a common implementation (simple_multiply_impl):

#![allow(unused)]
fn main() {
use sunscreen::{
    fhe_program,
    types::{bfv::{Signed, Fractional}, Cipher},
};
use std::ops::Mul;

fn simple_multiply_impl<T, U>(a: T, b: U) -> T
where T: Mul<U, Output=T> + Copy
{
    a * b
}

#[fhe_program(scheme = "bfv")]
fn simple_multiply_signed(a: Cipher<Signed>, b: Cipher<Signed>) -> Cipher<Signed> {
    simple_multiply_impl(a, b)
}


#[fhe_program(scheme = "bfv")]
fn simple_multiply_fractional(a: Cipher<Fractional<64>>, b: Fractional<64>) -> Cipher<Fractional<64>> {
    simple_multiply_impl(a, b)
}
}

The first FHE program multiplies encrypted Signed values. In the second, a is an encrypted Fractional value while b is an unencrypted Fractional value. We can run both of these programs using runtime.run() as normal.

Running your implementation without FHE

If we inspect the trait bounds on simple_multiply_impl, we'll notice there is no mention of anything Sunscreen related. This means we can directly run our implementation with Rust i64 values by simply calling:

use std::ops::Mul;

fn simple_multiply_impl<T, U>(a: T, b: U) -> T
where T: Mul<U, Output=T> + Copy
{
    a * b
}

fn main() {
    simple_multiply_impl(7, 5);
}

It's worth explicitly pointing out that T and U may be of the same or different types; the trait bounds merely require that you can multiply T and U values.

Limitations

FHE programs have some limitations you'll need to keep in mind.

Comparisons not supported

Performing comparisons on encrypted data is complex. Thus, we do not currently support comparisons.

The following is not allowed:

#![allow(unused)]
fn main() {
use sunscreen::types::{bfv::Signed, Cipher};

#[fhe_program(scheme = "bfv")]
fn invalid(a: Cipher<Signed>) -> Cipher<Signed> {
    // Return value mismatch aside, comparisons
    // are not supported
    a == 42
}
}

Branching restricted to constant expressions

Branches (i.e. for, if/else, match) cannot depend on function arguments, encrypted¹ or otherwise.

For example, you cannot do the following:

#![allow(unused)]
fn main() {
use sunscreen::types::{bfv::Signed, Cipher};

#[fhe_program(scheme = "bfv")]
fn invalid(a: Cipher<Signed>, b: Signed) -> Cipher<Signed> {
    let mut c = a;

    // For loop runs during compilation, but b isn't known until
    // you call `run`.
    for i in 0..b {
        c = c + a;
    }

    c
}
}

You can, however, use loops and if statements so long as their conditions don't depend on FHE program arguments. The examples below show allowed loop and if statements:

#![allow(unused)]
fn main() {
use sunscreen::{
   types::{bfv::{Fractional, Signed}, Cipher},
   fhe_program
};

#[fhe_program(scheme = "bfv")]
fn loopy(x: Cipher<Fractional<64>>) -> Cipher<Fractional<64>> {
    let mut y = x;

    for _ in 0..5 {
        y = y + x;
    }

    y
}

#[fhe_program(scheme = "bfv")]
fn iffy(x: Cipher<Signed>) -> Cipher<Signed> {
    let mut ans = x;

    for i in 1..5 {
        if i % 2 == 0 {
            ans = ans + i * x;
        } else {
            ans = ans - i * x;
        }
    }

    ans
}
}

Notice that their conditions don't depend on their argument x, so they're legal.

Bounded computation

You currently cannot perform computations indefinitely on ciphertexts. See here for a more in-depth discussion of this.

Avoid "transparent" ciphertexts

Some trivial operations destroy the randomness essential to the security of the resultant ciphertext — an outside observer can trivially decode them! Sunscreen will detect this and cause run() to fail to prevent data from leaking. Fortunately, such operations are not particularly useful in the first place.

Avoid doing the following:

• Subtracting a ciphertext from itself. However, it's fine to subtract 2 different ciphertexts that happen to contain the same value (i.e. the ciphertexts encrypt the same data but using different randomness).
• Multiplying a ciphertext by the plaintext or literal value 0. However, if a ciphertext encrypts 0, that's totally fine.

Troubleshooting

How do I debug my algorithm?

You can write your algorithm in a generic way, run it without FHE, and single step through it. You can also compare results executing with and without FHE.

Another technique that can be helpful is to call the render() method on your compiled FheProgram. This returns a String containing the compiled execution graph in DOT format. You can write this to a file and render it with Graphviz, a standard graph rendering library.

My FHE program yields the wrong answer. I'm certain the algorithm is correct.

Your issue might be one of 2 things:

1. You exceeded the noise budget. You can check the noise budget remaining on a ciphertext (this requires the private key) by calling (runtime.measure_noise_budget(&ciphertext, &private_key)). If this value is 0, you exceeded the noise budget and your value is corrupted. The most common scenario where you will encounter this issue is when chaining multiple FHE program executions.
2. Overflow. Try increasing the plaintext modulus. Due to carryless arithmetic, understanding overflow can be a bit tricky. Usually, overflow occurs when your plaintext modulus is too small and a digit wraps. Values can also overflow during multiplication due to running out of digits. However, this is very rare in FHE.

I need to use the output of one FHE program as the input to another (i.e. chain program executions).

We will likely improve the experience in the future, but you can do this today as follows:

1. Compile all your FHE programs with an increased noise_margin and look at their metadata.params.lattice_dimension values.
2. Change your application so the that the program with the largest lattice dimension (program x) compiles as it does in step 1, while the remaining programs call .with_params(&x.metadata.params) during compilation. This causes the remaining programs to use the same parameters verbatim.

The noise_margin you chose in step 1 determines how many times you can chain together program executions.

What the heck is an FheProgramNode?

It's a type wrapper needed to compile your FHE program. Internally, the #[fhe_program] macro turns all your program inputs and outputs into graph nodes — i.e. FheProgramNodes. Operator inputs and outputs are actually FheProgramNodes, which build up the execution graph during compilation. Unfortunately, they tend to be a leaky abstraction that wind up in error messages.

Usually, these errors tell you an FheProgramNode's inner type doesn't support an operation you're trying to perform. In the example below, the compiler is saying you can't divide Signed values:

error[E0369]: cannot divide `FheProgramNode<Cipher<Signed>>` by `FheProgramNode<Cipher<Signed>>`
  --> examples/simple_multiply/src/main.rs:22:7
   |
22 |     a / b
   |     - ^ - FheProgramNode<Cipher<Signed>>
   |     |
   |     FheProgramNode<Cipher<Signed>>

For more information about this error, try `rustc --explain E0369`.

This can also crop up when using explicit annotations. For example, the following will fail to compile:

#![allow(unused)]
fn main() {
#[fhe_program(scheme = "bfv")]
fn simple_multiply(a: Cipher<Signed>, b: Cipher<Signed>) -> Cipher<Signed> {
    // This assignment will fail because a * b results in an
    // `FheProgramNode<Cipher<Signed>>`, not a Cipher<Signed>
    let c: Cipher<Signed>  = a * b;

    c
}
}

Unnecessary type annotations are unidiomatic and thus we advise against them. Usually, type inference is sufficient, but if you really need one you can import and use sunscreen::types::intern::FheProgramNode.

Runtime

To create a runtime, you simply call Runtime::new, passing a Params object. You get a params object from compiling an FHE program as we did in our example.

use sunscreen::{
    fhe_program,
    types::{bfv::Signed, Cipher},
    Compiler, Runtime, PublicKey
};

#[fhe_program(scheme = "bfv")]
fn noop() {
}

fn main() {
   let fhe_program = Compiler::with_fhe_program(noop)
       .compile()
       .unwrap();

    let runtime = Runtime::new(&fhe_program.metadata.params).unwrap();
}

Once you're created a runtime, you can:

• generate public/private keys
• encrypt plaintexts
• run FHE programs
• decrypt ciphertexts

Parameter compatibility

Note that to use artifacts produced by a runtime (e.g. ciphertexts, keys), they must have been produced under a runtime using exactly the same parameters. This situation may have ramifications if you're attempting to re-use ciphertexts across multiple FHE programs; those programs must be compiled with the same set of parameters.

Key Generation

Once you've created a runtime, generating keys is simple:

use sunscreen::{
    fhe_program,
    types::{bfv::Signed, Cipher},
    Compiler, Runtime, PublicKey
};

#[fhe_program(scheme = "bfv")]
fn noop() {
}

fn main() {
   let fhe_program = Compiler::with_fhe_program(noop)
       .compile()
       .unwrap();

   let runtime = Runtime::new(&fhe_program.metadata.params).unwrap();

    let (public_key, private_key) = runtime.generate_keys().unwrap();
}

This produces a public key (which allows you to encrypt data and run FHE programs) and a private key (which allows you to decrypt).

Encryption

To encrypt data, simply call encrypt() on Runtime:

use sunscreen::{
    fhe_program,
    types::{bfv::Signed, Cipher},
    Compiler, Runtime, PublicKey
};

#[fhe_program(scheme = "bfv")]
fn noop() {
}

fn main() {
   let fhe_program = Compiler::with_fhe_program(noop)
       .compile()
       .unwrap();

   let runtime = Runtime::new(&fhe_program.metadata.params).unwrap();
   let (public_key, private_key) = runtime.generate_keys().unwrap();

    let val = Signed::from(15);
    let val_enc = runtime.encrypt(val, &public_key).unwrap();
}

This produces a Ciphertext value suitable for use in run(). Be careful not to confuse the Ciphertext type, which represents an actual encrypted value, with Cipher, which is a marker type to indicate a value in an FHE program is encrypted! Sunscreen can encrypt any of its provided types or fixed-length arrays¹ of them. Note that arrays encrypt as multiple values in a single large Ciphertext.

[DW: if the user is sending many ciphertexts (e.g., a vector of ciphertexts) under the same scheme, wouldn't it make sense to only communicate the scheme parameters once for all of the ciphertexts rather than attaching them on each one? That would help save some space.]

Cleartext metadata

Sunscreen attaches scheme parameters and the underlying datatype metadata to each Ciphertext. The former aids in serialization, while the latter prevents honest mistakes and improves the developer experience. When you serialize Ciphertext values to send over the network, this metadata appears in the clear. For most applications, this will be public information and part of the protocol. If, for some reason, you need the data type or scheme parameters to also be encrypted, you should encrypt the serialized ciphertext (e.g. use TLS for communication).

Running FHE Programs

In our simple example, we called runtime.run to execute our FHE program

use sunscreen::{*, types::{{bfv::Signed}, Cipher}};

fn main() { 
  #[fhe_program(scheme = "bfv")]
  fn multiply(a: Cipher<Signed>, b: Cipher<Signed>) -> Cipher<Signed> {
  a * b
  }

  let fhe_program = Compiler::with_fhe_program(multiply)
      .plain_modulus_constraint(PlainModulusConstraint::Raw(64))
      .compile()
      .unwrap();

  let runtime = Runtime::new(&fhe_program.metadata.params).unwrap();
  let (public_key, _) = runtime.generate_keys().unwrap();
    let a_enc = runtime.encrypt(Signed::from(5), &public_key).unwrap();
    let b_enc = runtime.encrypt(Signed::from(15), &public_key).unwrap();

    let results = runtime.run(&fhe_program, vec![a_enc, b_enc], &public_key).unwrap();
}

Let's break down the arguments to runtime.run:

1. The first fhe_program argument is the compiled program you wish to run.
2. The second vec![a, b] argument contains the input arguments to the program in a Vec.
3. The final public_key argument is the public key used to generate the encrypted program inputs (i.e. a_enc and b_enc).

FHE program inputs

Rust requires collections be homogenous (i.e. each item is the same type). However, program arguments may not be always be of the same type!

Our FheProgramInput wrapper enum solves this problem; it wraps values so they can exist in a homogeneous collection. The run function's second argument is a Vec<T> where T readily converts into an FheProgramInput (i.e. T impl Into<FheProgramInput>¹). Ciphertext and all types under sunscreen::bfv::types::* do this.

If your FHE program only accepts ciphertexts (a common scenario), it's sufficient to simply pass a Vec<Ciphertext> as we did in the above example. However, if you want to mix Ciphertext and unencrypted values, you'll need to make a Vec<FheProgramInput> manually, converting each argument yourself:

use sunscreen::{*, types::{{bfv::Signed}, Cipher}};

fn main() {
    // Note the lack of the `Cipher` type on b. This declares
    // it as a unencrypted.
    #[fhe_program(scheme = "bfv")]
    fn multiply(a: Cipher<Signed>, b: Signed) -> Cipher<Signed> {
        a * b
    }

    let fhe_program = Compiler::with_fhe_program(multiply)
        .compile()
        .unwrap();

    let runtime = Runtime::new(&fhe_program.metadata.params).unwrap();
    let (public_key, _) = runtime.generate_keys().unwrap();

    let a_enc = runtime.encrypt(Signed::from(5), &public_key).unwrap();

    // a is encrypted, but the second argument, b, is not.
    // We make a Vec<FheProgramInput> by calling `.into()`
    // on each value.
    let args: Vec<FheProgramInput> = vec![a_enc.into(), Signed::from(15).into()];
    let results = runtime.run(&fhe_program, args, &public_key).unwrap();
}

Validation

When you compile your FHE program, the compiler marks down the call signature (argument and return types). The run function validates that the inputs you gave are appropriately encrypted/unencrypted and are of the correct type.

Return value

On success, the run method returns a Vec<Ciphertext> containing each output of the FHE program.

• If the underlying FHE program returns a tuple, the entries of the Vec are each of the tuple's entries.
• If the underlying FHE program returns a single value, the Vec contains a single entry.
• If the underlying FHE program doesn't return anything, you should write more useful programs. The Vec will be empty.

Decryption

To decrypt, simply call decrypt() using your private key and the data you want to decrypt

use sunscreen::{
    fhe_program,
    types::{bfv::Signed, Cipher},
    Compiler, Runtime, PublicKey, PlainModulusConstraint
};

#[fhe_program(scheme = "bfv")]
fn noop() {
}

fn main() {
   let fhe_program = Compiler::with_fhe_program(noop)
       .plain_modulus_constraint(PlainModulusConstraint::Raw(5))
       .compile()
       .unwrap();

   let runtime = Runtime::new(&fhe_program.metadata.params).unwrap();
   let (public_key, private_key) = runtime.generate_keys().unwrap();

   let val = Signed::from(15);
   let val_enc = runtime.encrypt(val, &public_key).unwrap();

    // val_enc is an encrypted `Signed` value coming from an FHE program
    // or just directly encrypted.
    let a: Signed = runtime.decrypt(&val_enc, &private_key).unwrap();
}

Validation

Unlike with encrypt, you must specify the unencrypted data type (either on the left-hand side as above or using turbofish). The encrypted value's type must match the assigned type; if the specified data type doesn't match that on the ciphertext, decrypt will return an error. In the above example, decrypt will fail if the encrypted value is not a Signed type.

Serialization

While most examples compute everything in one place, in practice, data will be split amongst multiple machines. You can serialize many things in Sunscreen:

• Ciphertexts
• Keys
• Scheme parameters
• FHE programs

Sunscreen uses serde for serialization and can serialize data in a number of formats including JSON and bincode. Since most data in Sunscreen is high entropy byte arrays, we recommend using bincode since it reduces storage and network requirements by efficiently packing byte arrays.

The process to serialize and deserialize any type is the same, but this example shows how to do it with a ciphertext:

use sunscreen::{
    fhe_program,
    types::{bfv::Signed, Cipher},
    Compiler, Runtime, PublicKey, Ciphertext
};

#[fhe_program(scheme = "bfv")]
fn noop() {
}

fn main() {
   let fhe_program = Compiler::with_fhe_program(noop)
       .compile()
       .unwrap();

   let runtime = Runtime::new(&fhe_program.metadata.params).unwrap();
   let (public_key, _) = runtime.generate_keys().unwrap();
    let c = runtime
        .encrypt(Signed::from(20), &public_key)
        .unwrap();

    // ser is now a Vec<u8> that can be written to disk, socket, etc.
    let ser = bincode::serialize(&c).unwrap();

    // Upon receiving a serialized byte array, deserialize it
    // back into a Ciphertext. You may now use it normally.
    let c: Ciphertext = bincode::deserialize(&ser).unwrap();
}

As with any dependency, you'll need to add bincode as a dependency in your Cargo.toml.

Applications

In this section, we'll look at some (hopefully) interesting applications of FHE to web2 and web3.

Private token swap (via automated market makers)

We'll now walk through a less trivial computation that can be done with FHE. Our program is inspired by computations used in automated market makers (AMMs). While some of the code and ideas presented here could be useful for constructing an automated market maker with swap privacy, many details have been omitted.

Alice would like to swap some NU tokens for some ETH tokens. She'd like to perform this token swap without revealing to anyone her order amount. This might be done to prevent malicious actors from front-running her order.

To swap her tokens, she interacts with a "pool" that has reserves of both NU and ETH (implemented as a smart contract). For this example, we'll say the pool contains 100 ETH tokens and 1000 NU tokens. The reserve values here are public information. The exchange rate for NU ⇔ ETH changes based on the pool's reserves of the two tokens.

Alice will encrypt her order (i.e. the amount of NU tokens she wants to swap) and then submit it to the blockchain miner. The miner can then calculate how much encrypted ETH Alice should receive in exchange for her encrypted amount of NU tokens via FHE.

An intro to AMMs for the uninitiated

If you're not familiar with AMMs, we suggest starting here.

AMMs can be a great alternative to centralized exchanges since they allow you to exchange one type of a token for another with (generally) lower fees. Each token pair (in our example, we have NU and ETH) has its own "pool" which users interact with when performing a trade between those two particular tokens. You can also earn passive income from your tokens by providing liquidity (i.e. depositing two tokens) to a specific pool.

The exchange rate between the two tokens evolves automatically based on a known mathematical formula.

Unfortunately, the open and public nature of AMMs combined with the predictable behavior of the exchange rate allows for front-running attacks. Bad actors observe pending trades and then submit their own trades to "manipulate" the exchange rate in a way favorable to themselves. What does this mean for you as a potential AMM user? You may end up with a worse price than expected when your trade executes as these front-running attacks are fairly common and widespread.

Privacy (specifically hiding trade values) is one solution to this front-running problem.

Program walkthrough

Let's look at how to implement this now.

Setup

#![allow(unused)]
fn main() {
use sunscreen::{
    fhe_program,
    types::{bfv::Rational, Cipher},
    Ciphertext, CompiledFheProgram, Compiler, Params, PrivateKey, PublicKey,
    Runtime,
};

#[fhe_program(scheme = "bfv")]
/// This program swaps NU tokens for ETH.
fn swap_nu(
    nu_tokens_to_trade: Cipher<Rational>,
) -> Cipher<Rational> {
    let total_eth = 100.0;
    let total_nu = 1_000.0;

    -(total_eth * total_nu / (total_nu + nu_tokens_to_trade) - total_eth)
}
}

We begin by importing the stuff we're going to use.

We declare our swap_nu function as an FHE program with the appropriate attribute (#[fhe_program(scheme = "bfv")]).

swap_nu computes how much encrypted ETH a user will receive in exchange for nu_tokens_to_trade some amount of encrypted NU . Since we'll need to divide by a ciphertext, we'll have to use the Rational type here. Thus, notice that swap_nu takes in a Cipher<Rational> and returns a Cipher<Rational>. If you're wondering where the formula for swap_nu came from, it's from the constant product formula used by some automated market makers.

Notice that the other values in swap_nu (i.e. the pool reserves for ETH total_eth and NU total_nu) are in the clear.

Alice

#![allow(unused)]
fn main() {
use sunscreen::{
    fhe_program,
    types::{bfv::Rational, Cipher},
    Ciphertext, CompiledFheProgram, Compiler, Params, PrivateKey, 
    Error,
    PublicKey,
    Runtime,
};

/// Alice is a party that would like to trade some NU for ETH.
struct Alice {
    /// Alice's public key
    pub public_key: PublicKey,

    /// Alice's private key
    private_key: PrivateKey,

    /// Alice's runtime
    runtime: Runtime,
}
}

Alice wants to swap some encrypted (i.e. hidden) amount of NU for an encrypted (i.e. hidden) amount of ETH. She'll need a public/private key pair to do this (since she needs to encrypt her order with respect to her public key).

#![allow(unused)]
fn main() {
use sunscreen::{
    fhe_program,
    types::{bfv::Rational, Cipher},
    Ciphertext, CompiledFheProgram, Compiler, Params, PrivateKey, 
    Error,
    PublicKey,
    Runtime,
};

/// Alice is a party that would like to trade some NU for ETH.
struct Alice {
    /// Alice's public key
    pub public_key: PublicKey,

    /// Alice's private key
    private_key: PrivateKey,

    /// Alice's runtime
    runtime: Runtime,
}

impl Alice {
    pub fn setup(params: &Params) -> Result<Alice, Error> {
        let runtime = Runtime::new(params)?;

        let (public_key, private_key) = runtime.generate_keys()?;

        Ok(Alice {
            public_key,
            private_key,
            runtime,
        })
    }

    pub fn create_transaction(&self, amount: f64) -> Result<Ciphertext, Error> {
        Ok(self.runtime
            .encrypt(Rational::try_from(amount)?, &self.public_key)?
        )
    }

    pub fn check_received_eth(&self, received_eth: Ciphertext) -> Result<(), Error> {
        let received_eth: Rational = self
            .runtime
            .decrypt(&received_eth, &self.private_key)?;

        let received_eth: f64 = received_eth.into();

        println!("Alice received {}ETH", received_eth);

        Ok(())
    }
}
}

Alice first constructs a runtime and then can generate her public/private key pair.

To encrypt her order amount, she'll call create_transaction passing in the amount of NU she wants to trade and herpublic_key. We need try_from here to help us perform the appropriate type conversion.

We won't use this until the very end but check_received_eth will allow Alice to see how many ETH tokens she's received after performing the swap. Recall that Alice will receive an encrypted amount of ETH tokens, so in check_received_eth Alice will decrypt this value by passing in her private_key and received_eth the encrypted amount of ETH she received.

Miner

Let's look at the miner next.

#![allow(unused)]
fn main() {
use sunscreen::{
    fhe_program,
    types::{bfv::Rational, Cipher},
    Ciphertext, CompiledFheProgram, Compiler, Params, PrivateKey, 
    Error,
    PublicKey,
    Runtime,
};
/// Imagine this is a miner in a blockchain application. They're responsible
/// for processing transactions
struct Miner {
    /// The compiled swap_nu program
    pub compiled_swap_nu: CompiledFheProgram,

    /// The Miner's runtime
    runtime: Runtime,
}
}

Recall that the miner is responsible for processing Alice's order; thus, he'll have to run the compiled swap_nu program (compiled_swap_nu).

#![allow(unused)]
fn main() {
use sunscreen::{
    fhe_program,
    types::{bfv::Rational, Cipher},
    Ciphertext, CompiledFheProgram, Compiler, Params, PrivateKey, 
    Error,
    PublicKey,
    Runtime,
};

#[fhe_program(scheme = "bfv")]
/// This program swaps NU tokens for ETH.
fn swap_nu(
    nu_tokens_to_trade: Cipher<Rational>,
) -> Cipher<Rational> {
    let total_eth = 100.0;
    let total_nu = 1_000.0;

    -(total_eth * total_nu / (total_nu + nu_tokens_to_trade) - total_eth)
}

/// Imagine this is a miner in a blockchain application. They're responsible
/// for processing transactions
struct Miner {
    /// The compiled FHE swap program
    pub compiled_swap_nu: CompiledFheProgram,

    /// The Miner's runtime
    runtime: Runtime,
}

impl Miner {
    pub fn setup() -> Result<Miner, Error> {
        let compiled_swap_nu = Compiler::with_fhe_program(swap_nu).compile()?;

        let runtime = Runtime::new(&compiled_swap_nu.metadata.params)?;

        Ok(Miner {
            compiled_swap_nu,
            runtime,
        })
    }

    pub fn run_contract(
        &self,
        nu_tokens_to_trade: Ciphertext,
        public_key: &PublicKey,
    ) -> Result<Ciphertext, Error> {
        let results = self.runtime.run(&self.compiled_swap_nu, vec![nu_tokens_to_trade], public_key)?;

        Ok(results[0].clone())
    }
}
}

In setup, we compile swap_nu and save the runnable program as compiled_swap_nu. We also construct and save a Runtime for our miner to allow him to run it.

The miner can run the token swap contract (see run_contract) by calling runtime.run with the compiled_swap_nu program, Alice's encrypted order amount (nu_tokens_to_trade), and Alice's public_key. Recall that we must pass in arguments to an FHE program (such as compiled_swap_nu) via a Vec.

Swapping the tokens privately

use sunscreen::{
    fhe_program,
    types::{bfv::Rational, Cipher},
    Ciphertext, CompiledFheProgram, Compiler, Params, PrivateKey, 
    Error,
    PublicKey,
    Runtime,
};

 #[fhe_program(scheme = "bfv")]
/// This program swaps NU tokens to receive ETH.
fn swap_nu(
    nu_tokens_to_trade: Cipher<Rational>,
) -> Cipher<Rational> {
    let total_eth = 100.0;
    let total_nu = 1_000.0;

    -(total_eth * total_nu / (total_nu + nu_tokens_to_trade) - total_eth)
}

/// Imagine this is a miner in a blockchain application. They're responsible
/// for processing transactions
struct Miner {
    /// The compiled swap_nu program
    pub compiled_swap_nu: CompiledFheProgram,

    /// The Miner's runtime
    runtime: Runtime,
}

impl Miner {
    pub fn setup() -> Result<Miner, Error> {
        let compiled_swap_nu = Compiler::with_fhe_program(swap_nu).compile()?;

        let runtime = Runtime::new(&compiled_swap_nu.metadata.params)?;

        Ok(Miner {
            compiled_swap_nu,
            runtime,
        })
    }

    pub fn run_contract(
        &self,
        nu_tokens_to_trade: Ciphertext,
        public_key: &PublicKey,
    ) -> Result<Ciphertext, Error> {
        let results = self.runtime.run(&self.compiled_swap_nu, vec![nu_tokens_to_trade], public_key)?;

        Ok(results[0].clone())
    }
}

/// Alice is a party that would like to trade some NU for ETH.
struct Alice {
    /// Alice's public key
    pub public_key: PublicKey,

    /// Alice's private key
    private_key: PrivateKey,

    /// Alice's runtime
    runtime: Runtime,
}

impl Alice {
    pub fn setup(params: &Params) -> Result<Alice, Error> {
        let runtime = Runtime::new(params)?;

        let (public_key, private_key) = runtime.generate_keys()?;

        Ok(Alice {
            public_key,
            private_key,
            runtime,
        })
    }

    pub fn create_transaction(&self, amount: f64) -> Result<Ciphertext, Error> {
        Ok(self.runtime
            .encrypt(Rational::try_from(amount)?, &self.public_key)?
        )
    }

    pub fn check_received_eth(&self, received_eth: Ciphertext) -> Result<(), Error> {
        let received_eth: Rational = self
            .runtime
            .decrypt(&received_eth, &self.private_key)?;

        let received_eth: f64 = received_eth.into();

        println!("Alice received {}ETH", received_eth);

        Ok(())
    }
}

fn main() -> Result<(), Error> {
    // Set up the miner with some NU and ETH tokens.
    let miner = Miner::setup()?;

    // Alice sets herself up. The FHE scheme parameters are public to the
    // protocol, so Alice has them.
    let alice = Alice::setup(&miner.compiled_swap_nu.metadata.params)?;

    let transaction = alice.create_transaction(20.0)?;

    let encrypted_received_eth =
        miner.run_contract(transaction, &alice.public_key)?;

    alice.check_received_eth(encrypted_received_eth)?;

    Ok(())
}

We set up the miner and then Alice (notice that Alice relies on parameters generated from the Miner's setup). Both of them must use the same set of FHE scheme parameters for compatibility. In deployment, these values would likely be fixed at the protocol level.

Alice calls create_transaction to encrypt her trade amount of 20.0 NU tokens.

The miner calls run_contract to calculate how much encrypted ETH Alice will receive for her encrypted NU (based on the formula from swap_nu). The miner passes in Alice's encrypted trade amount (the result of alice.create_transaction(20.0) which is a ciphertext) along with Alice's public key (alice.public_key).

Finally, Alice can determine how much ETH she actually received from the swap via check_received_eth.

Performance

The entire program (not including compilation time) takes ~25 ms on an Intel Xeon @ 3.0 GHz (with 8 cores and 16 GB RAM) and ~100 ms on a Macbook Air M1.

What's missing?

For simplicity, we've omitted many details that are needed to actually execute a private token swap in real life. You may have noticed we mentioned nothing about Alice's account balance (deducting the amount of NU she wants to swap or adding the amount of ETH she receives), ensuring that Alice is behaving honestly (e.g. she actually has enough NU in her account to make the swap, she isn't creating tokens out of thin air), or how to determine the new reserve values of the pool (i.e. how much NU and ETH are in the pool after Alice has made her swap).

If you're curious about the answers:

• we've omitted account balances for simplicity (but such account balances would be encrypted as well)
• to ensure Alice is behaving honestly, we would need additional cryptographic tools such as zero-knowledge proofs
• the primary goal of private token swaps would be to prevent front-running, thus there would be some additional step to "reveal" the new reserve values

Private information retrieval

With private information retrieval (PIR), a user can retrieve an item from a database without revealing to the server which item she's interested in. PIR is useful for both web2 and web3 applications. In web2, for example, PIR can be used to help detect harmful images in end-to-end encrypted messaging. For private cryptocurrencies, PIR can help light clients retrieve relevant transactions.

To make this section easy to understand, we'll implement two simple PIR algorithms with our compiler.

The first algorithm does not require the full power of FHE since we only perform ciphertext-plaintext multiplication via a vector dot product; thus, an additively homomorphic encryption scheme would actually suffice.

The second algorithm does require the full power of FHE as we'll perform both ciphertext-ciphertext multiplication and ciphertext-plaintext multiplication via a matrix-vector product and vector dot product.

Warm up: a very simple PIR algorithm

We'll start with a very simple algorithm that uses a dot product to return an item privately.

How will our algorithm work?

Everything in the database will be unencrypted. We'll represent our database as a vector of n items.

Let's say that Alice wants to retrieve the 2nd item from the database. Alice will send a query to the server; we'll represent this query as a vector of length n as well.

Information retrieval (without privacy)

Every element of this query vector, except the one Alice is interested in, will have a 0 in its place. Alice will place a 1 in the 2nd entry (since she's interested in the 2nd item). When the server take the dot product of these two vectors, Alice will get back the item she wanted to retrieve:

[item₁, item₂, item₃, ... , item_n] · [0, 1, 0, ... , 0]^t

= item₁ · 0 + item₂ · 1 + item₃ · 0 + ... + item_n · 0

= item₂

Of course, the server can observe that Alice is interested in retrieving the 2nd item. How do we make this query private?

Making the query private

For simplicity, let Enc(x) denote that we encrypt x.¹

Since Alice doesn't want to reveal to the server which item she's interested in, she encrypts each of the elements in her query vector with respect to her FHE public key. Voila! We can now retrieve the information privately:

[item₁, item₂, item₃, ... , item_n] · [Enc(0), Enc(1), Enc(0), ... , Enc(0)]^t

= item₁ · Enc(0) + item₂ · Enc(1) + item₃ · Enc(0) + ... + item_n · Enc(0)

= Enc(item₂)

Program walkthrough

Our database will have 100 items in it. We'll represent the vectors from earlier as arrays, one of Sunscreen's supported types.

Setup

#![allow(unused)]
fn main() {
use sunscreen::{
    fhe_program,
    types::{bfv::Signed, Cipher},
};

const DATABASE_SIZE: usize = 100;

#[fhe_program(scheme = "bfv")]
/// This program takes a user's query and looks up the entry in the database.
/// Queries are arrays containing a single 1 element at the
/// desired item's index and 0s elsewhere.
fn lookup(query: [Cipher<Signed>; DATABASE_SIZE], database: [Signed; DATABASE_SIZE]) -> Cipher<Signed> {
    let mut sum = query[0] * database[0];

    for i in 1..DATABASE_SIZE {
        sum = sum + query[i] * database[i]
    }

    sum
}
}

We begin by importing the stuff we're going to use.

We declare our lookup function as an FHE program with the appropriate attribute (#[fhe_program(scheme = "bfv")]).

lookup implements the dot product formula discussed above. It takes in the unencrypted database and the encrypted query from the user to retrieve an item privately. The database is an array of length DATABASE_SIZE where each item in the database is a signed integer (Signed). Hence, the user's query is an array of length DATABASE_SIZE as well, where each entry is of type Cipher<Signed>.

Alice

#![allow(unused)]
fn main() {
use sunscreen::{
    fhe_program,
    types::{bfv::Signed, Cipher},
    Ciphertext, CompiledFheProgram, Compiler, Error, FheProgramInput, Params, PrivateKey,
    PublicKey, Runtime,
};

/// Alice is a party that wants to look up a value in the database without
/// revealing what she looked up.
struct Alice {
    /// Alice's public key
    pub public_key: PublicKey,

    /// Alice's private key
    private_key: PrivateKey,

    /// Alice's runtime
    runtime: Runtime,
}
}

Alice wants to retrieve an item from the database privately. She'll need a public/private key pair to do this (since she needs to encrypt her query with respect to her public key).

#![allow(unused)]
fn main() {
use sunscreen::{
    fhe_program,
    types::{bfv::Signed, Cipher},
    Ciphertext, CompiledFheProgram, Compiler, Error, FheProgramInput, Params, PrivateKey,
    PublicKey, Runtime,
};

const DATABASE_SIZE: usize = 100;

/// Alice is a party that wants to look up a value in the database without
/// revealing what she looked up.
struct Alice {
    /// Alice's public key
    pub public_key: PublicKey,

    /// Alice's private key
    private_key: PrivateKey,

    /// Alice's runtime
    runtime: Runtime,
}

impl Alice {
    pub fn setup(params: &Params) -> Result<Alice, Error> {
        let runtime = Runtime::new(params)?;

        let (public_key, private_key) = runtime.generate_keys()?;

        Ok(Alice {
            public_key,
            private_key,
            runtime,
        })
    }

    pub fn create_query(&self, index: usize) -> Result<Ciphertext, Error> {
        let mut query = [Signed::from(0); DATABASE_SIZE];
        query[index] = Signed::from(1);

        Ok(self.runtime.encrypt(query, &self.public_key)?)
    }

    pub fn check_response(&self, value: Ciphertext) -> Result<(), Error> {
        let value: Signed = self.runtime.decrypt(&value, &self.private_key)?;

        let value: i64 = value.into();

        println!("Alice received {}", value);

        Ok(())
    }
}
}

Alice will need to construct a runtime. Once that's done, she can generate her public/private key pair.

Alice can create her unencrypted query "vector" (actually an array) of 0's and 1's by calling create_query. Recall that the we'll have a 1 in the place of her desired item's index and a 0 elsewhere. Since she wants her query to be private, she'll encrypt her query, passing in her public_key as necessary.

We won't use this until the very end but check_response allows Alice to decrypt the server's response by passing in the ciphertext she received (value) along with her private_key.

Server

Let's look at the server next.

#![allow(unused)]
fn main() {
use sunscreen::{
    fhe_program,
    types::{bfv::Signed, Cipher},
    Ciphertext, CompiledFheProgram, Compiler, Error, FheProgramInput, Params, PrivateKey,
    PublicKey, Runtime,
};
/// This is the server that processes Alice's query.
struct Server {
    /// The compiled database lookup program
    pub compiled_lookup: CompiledFheProgram,

    /// The server's runtime
    runtime: Runtime,
}
}

Recall that the server is responsible for retrieving Alice's item from the database; thus, it will have to run the compiled lookup program (compiled_lookup).

#![allow(unused)]
fn main() {
use sunscreen::{
    fhe_program,
    types::{bfv::Signed, Cipher},
    Ciphertext, CompiledFheProgram, Compiler, Error, FheProgramInput, Params, PrivateKey,
    PublicKey, Runtime,
};

const DATABASE_SIZE: usize = 100;

#[fhe_program(scheme = "bfv")]
/// This program takes a user's query and looks up the entry in the database.
/// Queries are arrays containing a single 1 element at the
/// desired item's index and 0s elsewhere.
fn lookup(query: [Cipher<Signed>; DATABASE_SIZE], database: [Signed; DATABASE_SIZE]) -> Cipher<Signed> {
    let mut sum = query[0] * database[0];

    for i in 1..DATABASE_SIZE {
        sum = sum + query[i] * database[i]
    }

    sum
}

/// This is the server that processes Alice's query.
struct Server {
    /// The compiled database lookup program
    pub compiled_lookup: CompiledFheProgram,

    /// The server's runtime
    runtime: Runtime,
}

impl Server {
    pub fn setup() -> Result<Server, Error> {
        let compiled_lookup = Compiler::with_fhe_program(lookup).compile()?;

        let runtime = Runtime::new(&compiled_lookup.metadata.params)?;

        Ok(Server {
            compiled_lookup,
            runtime,
        })
    }

    pub fn run_query(
        &self,
        query: Ciphertext,
        public_key: &PublicKey,
    ) -> Result<Ciphertext, Error> {
        // Our database will consist of values between 400 and 500.
        let database: [Signed; DATABASE_SIZE] = (400..(400 + DATABASE_SIZE))
            .map(|x| Signed::from(x as i64))
            .collect::<Vec<Signed>>()
            .try_into()
            .unwrap();

        let args: Vec<FheProgramInput> = vec![query.into(), database.into()];

        let results = self.runtime.run(&self.compiled_lookup, args, public_key)?;

        Ok(results[0].clone())
    }
}
}

The server constructs a runtime so that it can run the compiled FHE program compiled_lookup.

Using run_query, the server can return an (encrypted) response to Alice's query.

The items in the database will be the integers from 400 to 499, stored in ascending order. Recall that lookup takes in two arguments---the encrypted query and the unencrypted database. Unfortunately, we'll need to do some type conversion for the database as Sunscreen's compiler needs the Signed type not i64 for its programs.

Additionally, to run FHE programs, we need to pass in arguments as a vec. Thus, we create a vec called args that contains our encrypted query and unencrypted database (which now has Signed entries rather than i64 entries in it).

Once all that's done, the server can run the FHE program by passing in the compiled_lookup program, the arguments to the program args (now contained in a vec), and Alice's public_key.

Retrieving the item privately

use sunscreen::{
    fhe_program,
    types::{bfv::Signed, Cipher},
    Ciphertext, CompiledFheProgram, Compiler, Error, FheProgramInput, Params, PrivateKey,
    PublicKey, Runtime,
};

const DATABASE_SIZE: usize = 100;

#[fhe_program(scheme = "bfv")]
/// This program takes a user's query and looks up the entry in the database.
/// Queries are arrays containing a single 1 element at the
/// desired item's index and 0s elsewhere.
fn lookup(query: [Cipher<Signed>; DATABASE_SIZE], database: [Signed; DATABASE_SIZE]) -> Cipher<Signed> {
    let mut sum = query[0] * database[0];

    for i in 1..DATABASE_SIZE {
        sum = sum + query[i] * database[i]
    }

    sum
}

/// Alice is a party that wants to look up a value in the database without
/// revealing what she looked up.
struct Alice {
    /// Alice's public key
    pub public_key: PublicKey,

    /// Alice's private key
    private_key: PrivateKey,

    /// Alice's runtime
    runtime: Runtime,
}

impl Alice {
    pub fn setup(params: &Params) -> Result<Alice, Error> {
        let runtime = Runtime::new(params)?;

        let (public_key, private_key) = runtime.generate_keys()?;

        Ok(Alice {
            public_key,
            private_key,
            runtime,
        })
    }

    pub fn create_query(&self, index: usize) -> Result<Ciphertext, Error> {
        let mut query = [Signed::from(0); DATABASE_SIZE];
        query[index] = Signed::from(1);

        Ok(self.runtime.encrypt(query, &self.public_key)?)
    }

    pub fn check_response(&self, value: Ciphertext) -> Result<(), Error> {
        let value: Signed = self.runtime.decrypt(&value, &self.private_key)?;

        let value: i64 = value.into();

        println!("Alice received {}", value);

        Ok(())
    }
}

/// This is the server that processes Alice's query.
struct Server {
    /// The compiled database lookup program
    pub compiled_lookup: CompiledFheProgram,

    /// The server's runtime
    runtime: Runtime,
}

impl Server {
    pub fn setup() -> Result<Server, Error> {
        let compiled_lookup = Compiler::with_fhe_program(lookup).compile()?;

        let runtime = Runtime::new(&compiled_lookup.metadata.params)?;

        Ok(Server {
            compiled_lookup,
            runtime,
        })
    }

    pub fn run_query(
        &self,
        query: Ciphertext,
        public_key: &PublicKey,
    ) -> Result<Ciphertext, Error> {
        // Our database will consist of values between 400 and 500.
        let database: [Signed; DATABASE_SIZE] = (400..(400 + DATABASE_SIZE))
            .map(|x| Signed::from(x as i64))
            .collect::<Vec<Signed>>()
            .try_into()
            .unwrap();

        let args: Vec<FheProgramInput> = vec![query.into(), database.into()];

        let results = self.runtime.run(&self.compiled_lookup, args, public_key)?;

        Ok(results[0].clone())
    }
}

fn main() -> Result<(), Error> {
    // Set up the database
    let server = Server::setup()?;

    // Alice sets herself up. The FHE scheme parameters are public to the
    // protocol, so Alice has them.
    let alice = Alice::setup(&server.compiled_lookup.metadata.params)?;

    let query = alice.create_query(94)?;

    let response = server.run_query(query, &alice.public_key)?;

    alice.check_response(response)?;

    Ok(())
}

We set up the server first and then Alice (notice that Alice relies on parameters generated from the server's setup). Both of them must use the same set of FHE scheme parameters for compatibility. In deployment, these values would likely be fixed at the protocol level.

Alice would like to privately retrieve the item at the 94th position from the database so she calls create_query which encrypts her query value of 94 (i.e. we get an array that has encryptions of 0 in all positions except the 94th position which contains an encryption of 1).

The server calls run_query to privately retrieve Alice's desired item to her. It passes in Alice's encrypted query along with Alice's public key (alice.public_key).

Finally, Alice can decrypt to check what item she received via check_response.

Performance

The entire program (not including compilation time) takes ~5 ms on an Intel Xeon @ 3.0 GHz (with 8 cores and 16 GB RAM) and ~42 ms on a Macbook Air M1.

A better PIR algorithm

In the previous PIR algorithm, the user had to send a query vector of the same size as the database itself. Can we do better than that? Yes!

Let's look at how to reduce the user's query size by making use of matrix-vector product and dot prodct.

How will our improved algorithm work?

Instead of representing the database as a vector of length n, we'll represent it as a matrix of dimension sqrt(n) by sqrt(n). As prior, everything in the database is unencrypted.

Let's say Alice wants to retrieve item_1,2 from the database. This time, Alice will send two query vectors to the server; each query vector is of length sqrt(n) so Alice's communication cost will be reduced from n to 2 · sqrt(n).

Information retrieval (without privacy)

What goes in the query vectors?

• Query Vector #1: Used in the matrix-vector product. The query vector will have a 0 in every place, except for the column number Alice is interested in. Since Alice wants the 2nd column, the vector takes the following form: [0, 1, 0, ..., 0].
• Query Vector #2: Used in the dot product. This query vector will have a 0 in every place, except for the row number Alice is interested in. Since Alice wants the 1st row, the vector takes the following form: [1, 0, ..., 0].

When we take the matrix-vector product of the database with query vector #1, we get a vector back. What's in this vector?

[item_1,2, item_2,2, item_3,2, ..., item_sqrt(n),2]

When we take the dot product of the previous result with query vector #2, we get the item Alice is interested in. Why? Well:

[item_1,2, item_2,2, item_3,2, ..., item_sqrt(n),2] · [1, 0, ..., 0]^t = item_1,2

Making the query private

Since Alice doesn't want to reveal to the server which item she's interested in, she encrypts her two query vectors with respect to her FHE public key.

• Query Vector #1: [Enc(0), Enc(1), Enc(0), ..., Enc(0)]
• Query Vector #2: [Enc(1), Enc(0), ..., Enc(0)]

When the server takes the matrix-vector product of the database with encrypted query vector #1, we get:

[Enc(item_1,2), Enc(item_2,2), Enc(item_3,2), ..., Enc(item_sqrt(n),2)]

When the server takes the dot product of the above vector with encrypted query vector #2, voila, we get Alice's desired item:

[Enc(item_1,2), Enc(item_2,2), Enc(item_3,2), ..., Enc(item_sqrt(n),2)] · [Enc(1), Enc(0), ..., Enc(0)]^t = Enc(item_1,2)

Program walkthrough

Our database will have 100 items in it. We'll use an array to represent our database.

Setup

#![allow(unused)]
fn main() {
use sunscreen::{
    fhe_program,
    types::{bfv::Signed, Cipher},
};

const SQRT_DATABASE_SIZE: usize = 10;

#[fhe_program(scheme = "bfv")]
/// This program takes a user's query and looks up the entry in the database.
/// Queries are arrays containing a single 1 element at the
/// desired item's index and 0s elsewhere.
fn lookup(
    col_query: [Cipher<Signed>; SQRT_DATABASE_SIZE],
    row_query: [Cipher<Signed>; SQRT_DATABASE_SIZE],
    database: [[Signed; SQRT_DATABASE_SIZE]; SQRT_DATABASE_SIZE],
) -> Cipher<Signed> {
    // Copy col_query just so we get an initialized object of the right
    // type in col.
    let mut col = [col_query[0]; SQRT_DATABASE_SIZE];

    // Perform matrix-vector multiplication with col_query to extract
    // Alice's desired column
    for i in 0..SQRT_DATABASE_SIZE {
        for j in 0..SQRT_DATABASE_SIZE {
            if j == 0 {
                col[i] = database[i][j] * col_query[j];
            } else {
                col[i] = col[i] + database[i][j] * col_query[j];
            }
        }
    }

    let mut sum = col[0] * row_query[0];

    // Dot product the result with the row query to get the result
    for i in 1..SQRT_DATABASE_SIZE {
        sum = sum + col[i] * row_query[i];
    }

    sum
}
}

We begin by importing the stuff we're going to use.

We declare our lookup function as an FHE program with the appropriate attribute (#[fhe_program(scheme = "bfv")]).

We'll represent our database as an array of length SQRT_DATABASE_SIZE (in this case = 10) with entries that are arrays of length SQRT_DATABASE_SIZE (also = 10). Since we want to write into the database, we'll need to initialize the array in the FHE program's function body.

lookup implements the matrix-vector and dot product formulas explained above to retrieve Alice's item privately. It takes in an unencrypted database along with Alice's encrypted query "vectors" (actually arrays). Recall that we have two queries— col_query will be used to select the appropriate column of the database whereas row_query will be used to select the appropriate row of the database.

Alice

#![allow(unused)]
fn main() {
use sunscreen::{
    PrivateKey, PublicKey, Runtime,
};

/// Alice is a party that wants to look up a value in the database without
/// revealing what she looked up.
struct Alice {
    /// Alice's public key
    pub public_key: PublicKey,

    /// Alice's private key
    private_key: PrivateKey,

    /// Alice's runtime
    runtime: Runtime,
}
}

Alice wants to retrieve an item from the database privately. She'll need a public/private key pair to do this (since she needs to encrypt her query with respect to her public key).

#![allow(unused)]
fn main() {
use sunscreen::{
    fhe_program,
    types::{bfv::Signed, Cipher},
    Ciphertext, CompiledFheProgram, Compiler, Error, FheProgramInput, Params, PrivateKey,
    PublicKey, Runtime,
};

const SQRT_DATABASE_SIZE: usize = 10;

/// Alice is a party that wants to look up a value in the database without
/// revealing what she looked up.
struct Alice {
    /// Alice's public key
    pub public_key: PublicKey,

    /// Alice's private key
    private_key: PrivateKey,

    /// Alice's runtime
    runtime: Runtime,
}

impl Alice {
    pub fn setup(params: &Params) -> Result<Alice, Error> {
        let runtime = Runtime::new(params)?;

        let (public_key, private_key) = runtime.generate_keys()?;

        Ok(Alice {
            public_key,
            private_key,
            runtime,
        })
    }

    pub fn create_query(&self, index: usize) -> Result<(Ciphertext, Ciphertext), Error> {
        let col = index % SQRT_DATABASE_SIZE;
        let row = index / SQRT_DATABASE_SIZE;

        let mut col_query = [Signed::from(0); SQRT_DATABASE_SIZE];
        let mut row_query = [Signed::from(0); SQRT_DATABASE_SIZE];
        col_query[col] = Signed::from(1);
        row_query[row] = Signed::from(1);

        Ok((
            self.runtime.encrypt(col_query, &self.public_key)?,
            self.runtime.encrypt(row_query, &self.public_key)?,
        ))
    }

    pub fn check_response(&self, value: Ciphertext) -> Result<(), Error> {
        let value: Signed = self.runtime.decrypt(&value, &self.private_key)?;

        let value: i64 = value.into();

        println!("Alice received {}", value);

        Ok(())
    }
}
}

Alice will need to construct a runtime. Once that's done, she can generate her public/private key pair.

create_query will allow Alice to create and encrypt her two query "vectors" (i.e. arrays). Alice will pass in an index which contains her desired column and row indices. Notice the 1's place of the index will allow Alice to select her desired column #, whereas the 10's place will allow Alice to select her desired row # (e.g. if index is 85, this denotes Alice is interested in entry located in the 5th column, 8th row).

We won't use this until the very end but check_response allows Alice to decrypt the server's response by passing in the ciphertext she received (value) along with her private_key.

Server

Let's look at the server next.

#![allow(unused)]
fn main() {
use sunscreen::{
    fhe_program,
    types::{bfv::Signed, Cipher},
    Ciphertext, CompiledFheProgram, Compiler, Error, FheProgramInput, Params, PrivateKey,
    PublicKey, Runtime,
};

/// This is the server that processes Alice's query.
struct Server {
    /// The compiled database query program
    pub compiled_lookup: CompiledFheProgram,

    /// The server's runtime
    runtime: Runtime,
}
}

Recall that the server is responsible for retrieving Alice's item from the database; thus, it will have to run the compiled lookup program (compiled_lookup).

#![allow(unused)]
fn main() {
use sunscreen::{
    fhe_program,
    types::{bfv::Signed, Cipher},
    Ciphertext, CompiledFheProgram, Compiler, Error, FheProgramInput, Params, PrivateKey,
    PublicKey, Runtime,
};

#[fhe_program(scheme = "bfv")]
/// This program takes a user's query and looks up the entry in the database.
/// Queries are arrays containing a single 1 element at the
/// desired item's index and 0s elsewhere.
fn lookup(
    col_query: [Cipher<Signed>; SQRT_DATABASE_SIZE],
    row_query: [Cipher<Signed>; SQRT_DATABASE_SIZE],
    database: [[Signed; SQRT_DATABASE_SIZE]; SQRT_DATABASE_SIZE],
) -> Cipher<Signed> {
    // Copy col_query just so we get an initialized object of the right
    // type in col.
    let mut col = [col_query[0]; SQRT_DATABASE_SIZE];

    // Perform matrix-vector multiplication with col_query to extract
    // Alice's desired column
    for i in 0..SQRT_DATABASE_SIZE {
        for j in 0..SQRT_DATABASE_SIZE {
            if j == 0 {
                col[i] = database[i][j] * col_query[j];
            } else {
                col[i] = col[i] + database[i][j] * col_query[j];
            }
        }
    }

    let mut sum = col[0] * row_query[0];

    // Dot product the result with the row query to get the result
    for i in 1..SQRT_DATABASE_SIZE {
        sum = sum + col[i] * row_query[i];
    }

    sum
}

const SQRT_DATABASE_SIZE: usize = 10;

/// This is the server that processes Alice's query.
struct Server {
    /// The compiled database query program
    pub compiled_lookup: CompiledFheProgram,

    /// The server's runtime
    runtime: Runtime,
}

impl Server {
    pub fn setup() -> Result<Server, Error> {
        let compiled_lookup = Compiler::with_fhe_program(lookup).compile()?;

        let runtime = Runtime::new(&compiled_lookup.metadata.params)?;

        Ok(Server {
            compiled_lookup,
            runtime,
        })
    }

    pub fn run_query(
        &self,
        col_query: Ciphertext,
        row_query: Ciphertext,
        public_key: &PublicKey,
    ) -> Result<Ciphertext, Error> {
        // Our database will consist of values between 400 and 500.
        let mut database = [[Signed::from(0); SQRT_DATABASE_SIZE]; SQRT_DATABASE_SIZE];
        let mut val = Signed::from(400);

        for i in 0..SQRT_DATABASE_SIZE {
            for j in 0..SQRT_DATABASE_SIZE {
                database[i][j] = val;
                val = val + 1;
            }
        }

        let args: Vec<FheProgramInput> = vec![col_query.into(), row_query.into(), database.into()];

        let results = self.runtime.run(&self.compiled_lookup, args, public_key)?;

        Ok(results[0].clone())
    }
}
}

The server constructs a runtime so that it can run the compiled FHE program compiled_lookup.

Using run_query, the server can return an (encrypted) response to Alice's query.

The items in the database will be the integers from 400 to 499, stored in ascending order. Recall that lookup takes in three arguments---the encrypted query for the column index (col_query), the encrypted query for the row index (row_query), and the unencrypted database. Unfortunately, we'll need to do some type conversion for the database as Sunscreen's compiler needs entries of the Signed type not i64 for its programs.

Additionally, to run FHE programs, we need to pass in arguments as a vec. Thus, we create a vec called args that contains our encrypted queries and unencrypted database (which now has Signed entries rather than i64 entries in it).

Once all that's done, the server can run the FHE program by passing in the compiled_lookup program, the arguments to the program args (now contained in a vec), and Alice's public_key.

Retrieving the item privately

use sunscreen::{
    fhe_program,
    types::{bfv::Signed, Cipher},
    Ciphertext, CompiledFheProgram, Compiler, Error, FheProgramInput, Params, PrivateKey,
    PublicKey, Runtime,
};

const SQRT_DATABASE_SIZE: usize = 10;

#[fhe_program(scheme = "bfv")]
/// This program takes a user's query and looks up the entry in the database.
/// Queries are arrays containing a single 1 element at the
/// desired item's index and 0s elsewhere.
fn lookup(
    col_query: [Cipher<Signed>; SQRT_DATABASE_SIZE],
    row_query: [Cipher<Signed>; SQRT_DATABASE_SIZE],
    database: [[Signed; SQRT_DATABASE_SIZE]; SQRT_DATABASE_SIZE],
) -> Cipher<Signed> {
    // Copy col_query just so we get an initialized object of the right
    // type in col.
    let mut col = [col_query[0]; SQRT_DATABASE_SIZE];

    // Perform matrix-vector multiplication with col_query to extract
    // Alice's desired column
    for i in 0..SQRT_DATABASE_SIZE {
        for j in 0..SQRT_DATABASE_SIZE {
            if j == 0 {
                col[i] = database[i][j] * col_query[j];
            } else {
                col[i] = col[i] + database[i][j] * col_query[j];
            }
        }
    }

    let mut sum = col[0] * row_query[0];

    // Dot product the result with the row query to get the result
    for i in 1..SQRT_DATABASE_SIZE {
        sum = sum + col[i] * row_query[i];
    }

    sum
}

/// Alice is a party that wants to look up a value in the database without
/// revealing what she looked up.
struct Alice {
    /// Alice's public key
    pub public_key: PublicKey,

    /// Alice's private key
    private_key: PrivateKey,

    /// Alice's runtime
    runtime: Runtime,
}

impl Alice { 
    pub fn setup(params: &Params) -> Result<Alice, Error> { 
        let runtime = Runtime::new(params)?; 
 
        let (public_key, private_key) = runtime.generate_keys()?; 
 
        Ok(Alice { 
            public_key, 
            private_key, 
            runtime, 
        }) 
    } 
 
    pub fn create_query(&self, index: usize) -> Result<(Ciphertext, Ciphertext), Error> { 
        let col = index % SQRT_DATABASE_SIZE; 
        let row = index / SQRT_DATABASE_SIZE; 
 
        let mut col_query = [Signed::from(0); SQRT_DATABASE_SIZE]; 
        let mut row_query = [Signed::from(0); SQRT_DATABASE_SIZE]; 
        col_query[col] = Signed::from(1); 
        row_query[row] = Signed::from(1); 
 
        Ok(( 
            self.runtime.encrypt(col_query, &self.public_key)?, 
            self.runtime.encrypt(row_query, &self.public_key)?, 
        )) 
    } 
 
    pub fn check_response(&self, value: Ciphertext) -> Result<(), Error> { 
        let value: Signed = self.runtime.decrypt(&value, &self.private_key)?; 
 
        let value: i64 = value.into(); 
 
        println!("Alice received {}", value); 
 
        Ok(()) 
    }
}

/// This is the server that processes Alice's query.
struct Server {
    /// The compiled database query program
    pub compiled_lookup: CompiledFheProgram,

    /// The server's runtime
    runtime: Runtime,
}

impl Server { 
    pub fn setup() -> Result<Server, Error> { 
        let compiled_lookup = Compiler::with_fhe_program(lookup).compile()?; 
 
        let runtime = Runtime::new(&compiled_lookup.metadata.params)?; 
 
        Ok(Server { 
            compiled_lookup, 
            runtime, 
        }) 
    } 
 
    pub fn run_query( 
        &self, 
        col_query: Ciphertext, 
        row_query: Ciphertext, 
        public_key: &PublicKey, 
    ) -> Result<Ciphertext, Error> { 
        // Our database will consist of values between 400 and 500. 
        let mut database = [[Signed::from(0); SQRT_DATABASE_SIZE]; SQRT_DATABASE_SIZE]; 
        let mut val = Signed::from(400); 
 
        for i in 0..SQRT_DATABASE_SIZE { 
            for j in 0..SQRT_DATABASE_SIZE { 
                database[i][j] = val; 
                val = val + 1; 
            } 
        } 
 
        let args: Vec<FheProgramInput> = vec![col_query.into(), row_query.into(), database.into()]; 
 
        let results = self.runtime.run(&self.compiled_lookup, args, public_key)?; 
 
        Ok(results[0].clone()) 
    } 
}
fn main() -> Result<(), Error> {
    // Set up the database
    let server = Server::setup()?;

    // Alice sets herself up. The FHE scheme parameters are public to the
    // protocol, so Alice has them.
    let alice = Alice::setup(&server.compiled_lookup.metadata.params)?;

    let (col_query, row_query) = alice.create_query(94)?;

    let response = server.run_query(col_query, row_query, &alice.public_key)?;

    alice.check_response(response)?;

    Ok(())
}

We set up the server first and then Alice (notice that Alice relies on parameters generated from the server's setup). Both of them must use the same set of FHE scheme parameters for compatibility. In deployment, these values would likely be fixed at the protocol level.

Alice would like to privately retrieve the item at the 94th "position" (this will mean the entry located in the 4th row, 9th column) from the database so she calls create_query. create_query encrypts her query value of 94 properly (i.e. creates col_query and row_query which has encryptions of 0s and 1s in the appropriate places).

The server calls run_query to privately retrieve Alice's desired item to her. It passes in Alice's encrypted queries along with Alice's public key (alice.public_key).

Finally, Alice can decrypt to check what item she received via check_response.

Performance

The entire program (not including compilation time) takes ~376 ms on an Intel Xeon @ 3.0 GHz (with 8 cores and 16 GB RAM) and ~716 ms on a Macbook Air M1.

What's missing?

If you're interested in using PIR in a real application, there are much better PIR algorithms out there (e.g. SealPIR, Spiral) that are faster and compress the query vector further.

Additionally, in PIR, we assume that the user knows the index of the item she wants to retrieve. For many applications though, this might not be the case. Oblivious message detection allows the user to detect which item she's interested in and can be combined with PIR.

FAQ

I've worked with FHE libraries before. What does your compiler actually do?

A challenge in working with the BFV scheme is having to set polynomial modulus degree, coefficient modulus, as well as the plaintext modulus for your specific application to ensure good performance. Additionally, bootstrapping is not supported so you need to be careful in choosing the correct parameters for your application so that you don't run out of noise budget before you finish your computation. Our compiler chooses the best polynomial modulus degree and coefficient modulus for your particular program, ensuring you’ll have enough noise budget to perform the entire computation. We do not yet choose the best plaintext modulus for your specific program (this will likely be implemented in the next release). Right now, we simply hard code a value for the plaintext modulus that works for almost any computation you'd likely do. Advanced users can go in and change this value manually if they'd like though.

You’ll also notice there’s no encoding process to do before encryption (we’ve abstracted that away). You also don’t have to worry about inserting relinearizations in manually (done for ciphertext maintenance purposes).

Can I perform computations on private data belonging to different parties?

Our compiler currently only supports a single-key FHE scheme, meaning that all data needs to be encrypted with respect to the same key if you want to perform computations on it. There are certainly ways to get around the single key limitation to enable computation on private data belonging to different parties. However, it's highly application dependent and often requires the use of additional tools (e.g. zero-knowledge proofs).

There are also variants of FHE—multi-party FHE and multi-key FHE— that support computation on private data belonging to different parties out of the box.

What are your future plans?

In terms of plans for our compiler specifically, we'd like to add support for:

• batching
• choosing scheme parameters based on multiple FHE programs as inputs
• using the outputs of one FHE program as the inputs to another FHE program

In terms of broader plans for Sunscreen, some of our next milestones include:

• helping users manage large FHE ciphertexts
• providing a complementary zero-knowledge proof library for our FHE compiler

Advanced

Now that you've gotten the basics down, let's dive into some more complex topics.

BFV scheme

There are many different FHE schemes out there. Our compiler uses the BFV scheme.

Why did we choose the BFV scheme?

The BFV scheme provides the following nice features:

• Exact integer arithmetic (it may surprise you but some FHE schemes can't support exact integer arithmetic)
• "Fast" integer arithmetic¹
• "Small" public key sizes¹
• Potential for "batching" (aka "SIMD"-like) operation for improved performance
• Compatibility with fairly efficient zero-knowledge proof systems

What are some of the drawbacks to the BFV scheme?

No FHE scheme is perfect. Some drawbacks to working with BFV include:

• Certain operations are difficult (i.e. more expensive) to perform. This notably includes comparisons of two private values.
• You can't perform private computations indefinitely on data. What that means for you is that you'll need to choose an upper bound (ahead of time) for how many private computations you'd like to perform. There is an advanced technique called bootstrapping to get around this issue but we do not currently support it.

Writing even better FHE programs

In this section, we're going to cover a few techniques to get the most out of your FHE applications.

Specifically, we'll look at:

• Manually changing the plaintext modulus to better suit your data and computation
• Manually changing the noise margin to allow for more efficient computations
• Manually pruning unused public keys for space savings

Plaintext modulus

FHE uses some funky math. At the lowest level, plaintexts are polynomials where the coefficient of each term is an integer modulo the plaintext modulus. The plaintext modulus parameter impacts correctness and performance — overflow occurs when the plaintext modulus is too small, but increasing it can negatively impact performance. Sunscreen balances these two considerations by setting a default plaintext modulus that prevents overflow in most applications while maintaining good performance.¹ However, you may at times wish to change it.

Why you might want to change the default plaintext modulus

A few reasons you would change the plain modulus include:

• If the default is too conservative, decreasing the plaintext modulus can improve performance.
• Very very rarely, the default can cause overflow in some FHE programs. Increasing the plaintext modulus solves this issue at the expense of performance.
• You wish to use batching, which requires very specific values.

When setting the plaintext modulus, you call compiler.plain_modulus_constraint() and pass a PlainModulusConstraint, which comes in two forms:

• Raw(x) sets the plaintext modulus to x.
• BatchingMinimum(x) chooses a value suitable for use with batching with at least x bits of precision. As noted in the name, this modulus should be used with batching.

How to change the plaintext modulus

You can manually set the PlainModulusConstraint when compiling your program like so:

use sunscreen::{
    fhe_program,
    types::{bfv::Signed, Cipher},
    Compiler, Runtime, PublicKey, PlainModulusConstraint
};

#[fhe_program(scheme = "bfv")]
fn my_program() {
}

fn main() {
    let fhe_program = Compiler::with_fhe_program(my_program)
        .plain_modulus_constraint(PlainModulusConstraint::Raw(1_000_000))
        .compile()
        .unwrap();
}

Noise

Every FHE operation introduces noise into ciphertexts.¹ If too much noise accrues, then the message becomes garbled and cannot be decrypted. The total amount of allowed noise before this problem occurs is referred to as the noise budget.

Fortunately, our compiler handles this noise issue for you. It uses a value known as the noise_margin that influences how conservative it needs to be in parameter selection. So long as noise_budget >= noise_margin, we're good to go. Sunscreen's default noise margin prevents garbled ciphertexts coming from a single FHE program.

Why you might want to change the default noise margin

There are a few reasons you may wish to change the noise margin:

• If you wish to use an output of one FHE program as an input to another FHE program, you need to allow for additional noise growth in subsequent programs. See our calculator for a complete example of this scenario.
• Decreasing the noise margin can result in improved performance if your application can tolerate a higher rate of faults.

How to change the noise margin

To change the noise margin, simply call .additional_noise_budget() when compiling your program. For example:

use sunscreen::{
    fhe_program,
    types::{bfv::Signed, Cipher},
    Compiler, Runtime, PublicKey
};

#[fhe_program(scheme = "bfv")]
fn my_program() {
}

fn main() {
    let fhe_program = Compiler::with_fhe_program(my_program)
        .additional_noise_budget(60)
        .compile()
        .unwrap();
}

Pruning public keys

For convenience, the generate_keys function creates several keys in the returned PublicKey object.

Why you might want to prune PublicKey

Some of these keys can be fairly large, the size of which is determined by scheme parameters. However, they may or may not be needed in your application:

• Galois keys (galois_key) are needed to run FHE programs that perform batching rotations or row swapping.
• Relinearization keys (relin_key) are needed to run FHE programs that multiply ciphertexts.

How to prune PublicKey

You can compile() an FHE program and look at fhe_program.metadata.required_keys to get a list of required keys for your specific program.

You can then remove unneeded keys. For example:

use sunscreen::{
    fhe_program,
    types::{bfv::Signed, Cipher},
    Compiler, Runtime, PublicKey
};

#[fhe_program(scheme = "bfv")]
fn noop() {
}

fn main() {
   let fhe_program = Compiler::with_fhe_program(noop)
       .compile()
       .unwrap();

   let runtime = Runtime::new(&fhe_program.metadata.params).unwrap();
let (public_key, private_key) = runtime.generate_keys().unwrap();

// Shadow and overwrite the public_key, removing the galois_key and relin_key
let public_key = PublicKey {
    galois_key: None, // only do this if not using batching
    relin_key: None, // only do this if your FHE program never multiplies ciphertexts
    ..public_key
};
}

WASM support

Need to run Sunscreen in your browser or NodeJS app? Simply build your app targeting WebAssembly (WASM).

WASM is an instruction set for a sandboxed virtual machine that allows you to safely run Rust and C++ code in your browser more efficiently than Javascript. This includes your Sunscreen app!

Rust features multiple targets for building WASM binaries, but Sunscreen currently only supports wasm32-unknown-emscripten. As the target's name suggests, this leverages emscripten, which SEAL needs during compilation and runtime.

Setup

Install emscripten

git clone https://github.com/emscripten-core/emsdk.git
emsdk/emsdk install 3.1.3
emsdk/emsdk activate

You can try installing other toolchain versions if you wish, but we've seen the compiler seg fault and other strange errors when building our examples 🙃.

Load the emscripten environment

source emsdk/emsdk_env.sh

Put this command in your shell's .rc file so you don't need to rerun it each time you launch a shell.

Add the wasm32-unknown-emscripten target to Rust

rustup target add wasm32-unknown-emscripten

Building

To compile your program with Rust+emscripten, you'll need to do a few extra things.

Required emscripten features

Add the following lines to your .cargo/config.toml¹:

[env]
EMCC_CFLAGS = "-sERROR_ON_UNDEFINED_SYMBOLS=0 -sDISABLE_EXCEPTION_CATCHING=0 -sALLOW_MEMORY_GROWTH"

ERROR_ON_UNDEFINED_SYMBOLS=0 works around a known issue when Rust's panic handling is set to unwind (the default). Alternatively, you can set the handling mode to abort when building for WASM.

DISABLE_EXCEPTION_CATCHING=0 allows C++ code to catch exceptions. Without this, you'll get an error complaining that Rust can't catch foreign exceptions and your application will terminate via abort().

Finally, ALLOW_MEMORY_GROWTH allows the heap to resize. Without this, your app will quickly run out of memory and seg fault.

Building your app

Simply run:

cargo build --bin myapp --release --target wasm32-unknown-emscripten

where myapp is the name of your executable.

On success, you should see the following files:

target/wasm32-unknown-emscripten/release/myapp.js
target/wasm32-unknown-emscripten/release/myapp.wasm

Running with node

node target/wasm32-unknown-emscripten/release/myapp.js

Running in browser

Put myapp.js in a script tag in an index.html file:

<!DOCTYPE html>
<html>
    <head>
        <script src="myapp.js"></script>
    </head>
    <body></body>
</html>

and serve the index.html, myapp.js, and myapp.wasm files on a web server. Your app will run when the user loads the page in their browser.

Alternatively, you can bundle your .js and .wasm into a larger application with webpack.

Running with wasmer/wasmtime

Unfortunately, these scenarios are currently unsupported 😞.

Running tests

Build your tests with:

cargo test --no-run --release --target wasm32-unknown-emscripten

You'll find your tests' entry points in target/wasm32-unknown-emscripten/release/deps/*.js. Simply select the desired test and run:

node target/wasm32-unknown-emscripten/release/mytest-xxxx.js

Debugging

Debugging WASM is challenging. If possible, you should debug issues running your app natively. For debugging WASM-specific issues, emscripten can emit both DWARF symbols and traditional source maps. While DWARF symbols are more useful, browser support at this stage is terrible.

Build in debug mode

To use source maps, simply build in debug mode²:

cargo build --bin myapp --target wasm32-unknown-emscripten

where myapp is the name of your executable.

Make a webpage

In our experiments debugging with node --inspect-brk, the Chrome debugger failed to find the source maps. Debugging raw WASM is unpleasant, so we recommend an alternative — make a simple webpage that hosts your app.

Make an index.html with the following contents in the root of your git repository:

<!DOCTYPE html>
<html>
    <head>
        <script src="./target/wasm32-unknown-emscripten/debug/myapp.js"></script>
    </head>
    <body></body>
</html>

Serve your page

In another terminal, run:

npm install -g http-server
node http-server /git/repo/root/dir

Debug your program on the website

Open Chrome and navigate to http://localhost:8080/index.html. Hit F12 to open the debugger. Chrome should find your source maps allowing you to navigate the stack, set breakpoints, step, continue, etc. all with real source code. Unfortunately, you can't see variables.

You can also use the log crate to print information to the debug console. If you go this route, use simple-logger as the logger backend; don't use a WASM-specific crate (e.g. wasm-logger) for this because emscripten already routes stdout and stderr to the console.

Carryless arithmetic

When learning arithmetic in grade school, you learned the base 10 system where digits range from 0-9. Whenever adding digits exceeds 9, you have to carry the 1. However, this is not the only way to do arithmetic; we can instead omit the carry and allow digits to exceed 9!

Why would we want to do this? FHE operations actually add and multiply polynomials under the hood. If we treat each coefficient of the polynomial as a digit and use carryless arithmetic, we can trick them into behaving like numbers. This results in more efficient data types.

Addition

Let's start with a simple carryless addition example. Adding 99 + 43 without propagating carries gives us:

  9  9
+ 4  3
------
 13 12

That is 13 in the 10s place and 12 in the 1s place which is 13 * 10 + 12 * 1 = 142. This is the same value as if we had propagated carries (1 * 100 + 4 * 10 + 2 * 1 = 142). Under carryless arithmetic, both are valid ways to represent the value 142; representations are no longer unique!

Furthermore, we can represent negative values by negating each digit. For example, -123 is -1 * 100 + -2 * 10 + -3 * 1. Mechanically, we simply treat each polynomial coefficient as p's complement¹ value to allow negative numbers.

We can easily extend this reasoning to base 2 (binary). Under carryless arithmetic, base 2 simply means that each digit is a multiple of a power of 2. For example, we can compute 3 + 2 + (-4) as follows:

3 + 2 =
  1 1 = 3
+ 1 0 = 2
-----
  2 1 = 2*2^1 + 1*2^0 = 5

5 + (-4) =
   0 2 1 = 5
+ -1 0 0 = -4
--------
  -1 2 1 = -1*2^2 + 2*2^1 + 1*2^0 = 1 

Again -1 2 1 equals 1, as does 0 0 1; the representation is not unique.

Adding polynomials

To see why carryless arithmetic is useful, let's take the values of our previous example (3, 2, -4) and map their digits onto polynomials like so:

\[3 = 0\times 2^2 + 1\times 2^1 + 1\times 2^0 \rightarrow 0x^2 + 1x + 1\]

\[2 = 0\times 2^2 + 1\times 2^1 + 0\times 2^0 \rightarrow 0x^2 + 1x + 0\]

\[-4 = -1\times 2^2 + 0\times 2^1 + 0\times 2^0 \rightarrow -1x^2 + 0x + 0\]

To add polynomials, recall that you simply collect the terms:

\[3 + 2 \rightarrow (0x^2 + 1x + 1) + (0x^2 + 1x + 0) = 0x^2 + 2x + 1\]

Now, let's subtract 4:

\[5 + (-4) \rightarrow (0x^2 + 2x + 1) + (-1x^2 + 0x + 0) = -1x^2 + 2x + 1 \]

Note that the coefficients are the same as the digits in our carryless arithmetic result. We can convert the polynomial back into an integer by evaluating it at x = 2, yielding 1!

Multiplication

Now, lets go through a multiplication example with binary carryless arithmetic. Here, we multiply 7 * 13 = 91:

        0 1 1 1 = 7
*       1 1 0 1 = 13
---------------
        0 1 1 1
+     0 0 0 0
+   0 1 1 1
+ 0 1 1 1
---------------
  0 1 2 2 2 1 1 = 1*2^5 + 2*2^4 + 2*2^3 + 2*2^2 + 1*2^1 + 1*2^0 = 91

Notice that when we collected each place, we didn't propagate carries when values exceeded 1.

As another example, when we square 1 0 0 0 0 = 16, we get 1 0 0 0 0 0 0 0 0 = 256. Compared to the previous example, the operands are larger (16 * 16 vs. 7 * 13), but the result's largest digit is smaller — 1 in 1 0 0 0 0 0 0 0 0 vs. 2 in 0 1 2 2 2 1 1. This will come up again when we talk about overflow.

Multiplying polynomials

As with addition, we'll now show how carryless multiplication directly maps to polynomial multiplication. Let's encode 7 and 13 as polynomials:

\[7 = 0\times 2^3 + 1\times 2^2 + 1\times 2^1 + 1\times 2^0 \rightarrow 0x^3 + 1x^2 + 1x^1 + 1\]

\[13 = 1\times 2^3 + 1\times 2^2 + 0\times 2^1 + 1\times 2^0 \rightarrow 1x^3 + 1x^2 + 0x^1 + 1\]

Let's multiply these polynomials:

\[7 \times 13 \rightarrow (0x^3 + 1x^2 + 1x^1 + 1)(1x^3 + 1x^2 + 0x^1 + 1) \] \[= 1x^3(0x^3 + 1x^2 + 1x^1 + 1) + 1x^2(0x^3 + 1x^2 + 1x^1 + 1)\] \[ + 0x^1(0x^3 + 1x^2 + 1x^1 + 1) + 1(0x^3 + 1x^2 + 1x^1 + 1) \]

\[=(0x^6 + 1x^5 + 1x^4 + 1x^3) + (0x^5 + 1x^4 + 1x^3 + 1x^2)\] \[+(0x^4 + 0x^3 + 0x^2 + 0x^1) + (0x^3 + 1x^2 + 1x^1 + 1) \]

\[=0x^6 + 1x^5 + 2x^4 + 2x^3 + 2x^2 + 1x^1 + 1\]

Again, the coefficients of this polynomial exactly match our carryless addition result, so we can trivially map our polynomial back into a number to recover our answer!

You might be wondering: "can polynomial coefficients grow indefinitely?"

Unfortunately, they can't.

Overflow

As with normal computer arithmetic, values in FHE can overflow. In Sunscreen, plaintext polynomials have p's complement coefficients, where p is the plaintext modulus. Assuming p is odd, this means each coefficient must be in the range \([\frac{-p}{2}, \frac{p}{2}] \) ². The result of any operation that falls outside this range will wrap around — it overflows.

Suppose p = 7 and we try to add 3 + 1. Values should be within the range \([-3,3]\), but 3 + 1 = 4 is not and thus wraps around to -3! This example looks at a single value, but polynomials feature many coefficients, each of which has the same range restriction.

Addition

Let's look at an addition example, treating the coefficients as carryless arithmetic binary digits. Take p = 9 (meaning digits are in the interval \([-4,4]\)) and add 15 = 4 0 -1³ with 8 = 2 2 -4.

  4 0 -1 = 15
+ 2 2 -4 = 8
--------
 -3 2  4 = -3*2^2 + 2*2^1 + 4*2^0 = -4

From this example, we have two observations:

• We expected 6 2 -5 = 23, but both the 4s and 1s places overflowed, giving us a very strange -4!
• Operands' digits only contribute to their respective place in the result (i.e. the 4s place contributes only to the 4s place, the 2s place to only the 2s place, etc).

If we increase p to 13 and repeat the example, we do get the correct answer because 6 and -5 are within \([-6,6]\).

Multiplication

Next, let's consider canonical representations of 31 = 1 1 1 1 1 and 15 = 0 1 1 1 1 when p = 7 (i.e. digits in interval \([-3, 3]\)). Adding these numbers doesn't lead to overflow, but what about multiplication? Let's find out:

             1  1  1  1  1 = 31
*            0  1  1  1  1 = 15
--------------------------
             1  1  1  1  1
          1  1  1  1  1
       1  1  1  1  1
    1  1  1  1  1
 0  0  0  0  0
--------------------------
 0  1  2  3 -1 -1  3  2  1
 = 0*256 + 1*128 + 2*64 + 3*32 + -1*16 + -1*8 + 3*4 + 2*2 + 1
 = 345

We draw 2 observations from this example:

• We expected 465 = 0 1 2 3 4 4 3 2 1, but got 345 because the 16s and 8s places overflowed.
• The number of non-zero digits in each operand contributes to the result digits' magnitudes.

Increasing p to 9 eliminates the overflow since 4 is in the interval \([-4, 4]\).

If we multiply canonical representations of 32 = 1 0 0 0 0 0 and 16 = 0 1 0 0 0 0 when p = 7, surely this will overflow as well, right? After all, they're bigger numbers than in our previous example! As it turns out, this gives exactly the right answer: 512 = 1 0 0 0 0 0 0 0 0 0. The operands feature far fewer non-zero digits, and thus are less impacted by our second observation.

We chose operand digits with value 1 in this example to reveal the second observation, but larger values further compound digit growth! You can see this by redoing the example with 4's: 124 = 4 4 4 4 4 times 60 = 0 4 4 4 4 equals 7440 = 0 16 32 48 64 64 48 32 16.

Preventing overflow

Overflow is a bit counterintuitive under carryless arithmetic, but you can prevent it — simply increase the plaintext modulus. Understanding your computation and knowing the range of your inputs can help you choose the appropriate value.