tlepoint / fhe.rs

Fully Homomorphic Encryption library in Rust

fhe.rs: Fully Homomorphic Encryption in Rust

This repository contains the fhe.rs library, an experimental cryptographic library in Rust for Ring-LWE-based homomorphic encryption, developed by Tancrède Lepoint. For more information about the library, see fhe.rs.

The library features:

• An implementation of a RNS-variant of the Brakerski-Fan-Vercauteren (BFV) homomorphic encryption scheme;
• Performances comparable or better than state-of-the-art libraries in C++ and Go.

Warning fhe.rs is a beta library, and should be considered unstable with potential breaking API changes until version 1.0.0 is released!

Note This library is not related to the tfhe-rs library (a.k.a. concrete), Zama's fully homomorphic encryption in Rust, available at tfhe.rs.

fhe.rs crates

fhe.rs is implemented using the Rust programming language. The ecosystem is composed of four public crates (packages):

• fhe: This crate contains the implementations of the homomorphic encryption schemes;
• fhe-math: This crate contains the core mathematical operations for the fhe crate;
• fhe-traits: This crate contains traits for homomorphic encryption schemes;
• fhe-util: This crate contains utility functions for the fhe crate.

Installation

To install, add the following to your project's Cargo.toml file:

[dependencies]
fhe = "0.1.0-beta.8"
fhe-traits = "0.1.0-beta.8"

Minimum supported version / toolchain

Rust 1.73 or newer.

⚠️ Security / Stability

The implementations contained in the fhe.rs ecosystem have never been independently audited for security. Additionally, no promise on the API and ABI stability will be made until version 1.0.0 of the crates.

Use at your own risk.

fhe.rs's Issues

Enable error variances of more than 16

The variance for sampling according to the centered binomial distribution is currently capped at 16:

pub fn sample_vec_cbd(vector_size: usize, variance: usize) -> Result<Vec<i64>, &'static str> {
	if !(1..=16).contains(&variance) {
		return Err("The variance should be between 1 and 16");
	}

It would be good to enable larger values.

Make a more consistent API with respect to RNGs and seeds

The current API (both in the and the-math is all over the place:

• It doesn't enable to pass a RNG as input (which would enable determinism);
• The seed is hardcoded to be a <ChaCha8Rng as SeedableRng>::Seed(aka a [u8; 32]), but there is no need to be that restrictive;
• etc.

What is the meaning of the "Shoup"?

hi, first of all a big thanks to fhe.rs for this great work, it helped me a lot. However I have some doubts.
In the source code, "shoup"-related names often appear, such as NTTShoup, Shoup multiplication. Is this an optimization algorithm? Are there any papers or materials that can be referred to?

Investigate the use of portable_simd

Rust has an experimental portable SIMD abstraction which could be particularly useful to speed up some of the vector modular operations / NTTs in a "generic" way (i.e., without needing to specialize for AVX2 or Neon). I did some minimal investigation in the branch simd-2, and observe some speedup in a virtual machine with Intel CPU when enabling avx2 and avx512f in RUSTFLAGS. Such a feature may require a lot of care to properly handle alignment, and this issue is created to centralize the discussions about SIMD.

Why are the implementation styles of forward and backward different?

In crates/fhe-math/src/zq/ntt.rs , this file provides the implementation of forward_vt and backward_vt, where forward_vt calls forward_lazy, and then calls reduce3. However, in the implementation of backward_vt, the same pattern is not used. Why?

Moreover, I read the codes of the forward_vt and backward_vt carefully and found that the two are not completely symmetrical, which has some deviations from my understanding of NTT. I always thought that NTT forward and backward are completely symmetrical, the only difference is that the input is different. Is there any more detailed material for the implementation here?

Remove the requirement of using `nightly`

It is not necessary to use a nightly toolchain for the crates in this repository.

sealpir and mulpir fail

When removing the utilities crate, the value plaintext.ilog2() has been replaced by 64 - (plaintext - 1).leading_zeros(), but however this is not correct.

Serialization of secret key

Serialization and deserialization of a SecretKey is not yet implemented, but will be required for anything that goes beyond "example" code.

Question on correctness of decryption

Hi 👋 I've been implementing a prototype of multiparty BFV on top of your library (here for reference). The public key and relinearization key generated by the multiparty protocols induce quite a bit more noise than the single-key variants, but I've seen some unexpected decryption failures after relinearization, even when using rather large ciphertext moduli (e.g. I've even tried a modulus with ~ 62 * 16 bits). For context, everything works fine if the public key $p = (p_0, p_1)$ used to encrypt the ciphertexts has been generated such that $p_1$ has small coefficients, rather than sampled uniformly from $R_q$, leading me to believe this is an issue related to noise or the handling of large coefficients.

In debugging this, I'm wondering if the issue lies in SecretKey::try_decrypt, which only reduces the coefficients according to the first ciphertext modulus factor, rather than the entire modulus. However, given a ciphertext modulus $q = q_1 \cdots q_\ell$, plaintext modulus $p$, and coefficient $c$ such that $q_1 < c < q$, it is not necessarily the case that $(c \mod q) \mod p = (c \mod q_1) \mod p$. The LHS is the textbook decryption, while the RHS is the current implementation (if I'm reading correctly).

Curious if I'm missing something or if the current version needs a fix to reduce via the full ciphertext modulus. Thanks for any help!

Code coverage shouldn't look at automatically generated proto files

Clippy reports casting of the same type

See clippy report of #153

Encrypter -> Encryptor

This would break backward compatibility, but typos suggest to change Encrypter to Encryptor (and probably similarly for Decrypter).

Improve the polynomial extender / RNS converter performance

The polynomial extender is slower than I would like too. In my original implementation, to go from 3 to 6 moduli, it was taking

poly::extend/1024/3->6  time:   [62.700 us 62.733 us 62.773 us]

and this implementation is

rq_switchers/extender/1024/3_to_6                                                                            
                        time:   [96.108 µs 96.225 µs 96.368 µs]

It is noticeably higher, so we need to investigate more. Part of it is due to the use of u256 instead of ~u192, but I am not sure it accounts for all the difference.

Originally posted by @tlepoint in #32 (comment)

Question on constant time reduce.

// x \in [0, 2p) => x mod p 
pub(crate) const fn reduce1(x: u64, p: u64) -> u64 {
        debug_assert!(p >> 63 == 0);
        debug_assert!(x < 2 * p);

        let (y, _) = x.overflowing_sub(p);
        let xp = x ^ p;
        let yp = y ^ p;
        let xy = xp ^ yp;
        let xxy = x ^ xy;
        let xxy = xxy >> 63;
        let (c, _) = xxy.overflowing_sub(1);
        let r = (c & y) | ((!c) & x);

        debug_assert!(r == x % p);

        r
    }

How about using the following

// return cond ? a : b
uint64_t const_select(uint64_t a, uint64_t b, bool cond) {
    uint64_t c = -static_cast<uint64_t>(cond);
    uint64_t x = a ^ b;
    return (x & c) ^ b;
}

uint64_t const_reduce(uint64_t x, uint64_t p) {
    return x - const_select(0, p, x < p)
}

Serialize ciphertext in Power Basis

The ciphertext (and probably the keys?) is currently serialized in Ntt representation; it should be in power basis.

Incorrect crate version in the README

fhe = "0.1.0-beta.1"
should be
fhe = "0.1.0-beta.2"

RGSW marked as depending on a feature in the doc

In https://docs.rs/fhe/0.1.0-beta.2/fhe/bfv/index.html, RGSWCiphertext is mistakenly marked as depending on a feature.

Make ciphertext in power basis representation by default

Currently, the lib handles plaintext and ciphertexts in NTT representation.
Instead, it may be desirable to handle them in PowerBasis representation.

• We should make sure that such a change doesn't impact the performances (it will some of them, so it's important to measure to decide if the change is worth it);
• The expansion, instead of multiplying with a monomial, should use the fact that we are in power basis representation to easily multiply.
• To still allow for fast multiplication by plaintext, it should probably store both the poly and poly_ntt

Can you provide me some guide about how to understand code in this repo?

Hello, I am very interested in Fully Homomorphic Encryption (FHE) and the Rust programming language. I would like to understand your code better. Where would be a good starting point?