目录
• 8 分钟阅读

TFHE-rs深度解析之一：总览

密码学 #全同态加密 #隐私保护 #TFHE
TFHE-rs repo
TFHE-rs系列

TFHE使用流程

TFHE-rs是Zama用Rust从头实现的TFHE算法，与C++版本的TFHE同态密码库没有承接关系。在Rust中使用TFHE-rs的方式很简单直观，另外官方也提供了C的API接口，方便绑定到其他语言使用。

生成密钥

首先导入thfe中的模块，并使用默认参数生成密钥对。

tfhe-simple-ops.rs
use tfhe::prelude::*;
use tfhe::{generate_keys, set_server_key, ConfigBuilder, FheUint8};
 
fn main() {
    let config = ConfigBuilder::default().build();
 
    let (client_key, server_key) = generate_keys(config);
 
    set_server_key(server_key);
 
    // Do stuff with generated keys
}

加密数据

加密两个输入整数，并得到对应密文。在Rust中，为避免数据移动，借用密文数据。

tfhe-simple-ops.rs
    let clear_a = 35u8;
    let clear_b = 7u8;
 
    // Encryption
    let a = FheUint8::encrypt(clear_a, &client_key);
    let b = FheUint8::encrypt(clear_b, &client_key);
 
    // Take a reference to avoid moving data when doing the computation
    let a = &a;
    let b = &b;

计算加密数据

大部分加密数据可以直接使用Rust内置操作符运算。

tfhe-simple-ops.rs
    // Computation using Rust's built-in operators
    let add = a + b;
    let sub = a - b;
    let mul = a * b;
    let div = a / b;
    let rem = a % b;
    let and = a & b;
    let or = a | b;
    let xor = a ^ b;
    let neg = -a;
    let not = !a;
    let shl = a << b;
    let shr = a >> b;
 
    // Comparison operations need to use specific functions as the definition of the operators in
    // rust require to return a boolean which we cannot do in FHE
    let eq = a.eq(b);
    let ne = a.ne(b);
    let gt = a.gt(b);
    let lt = a.lt(b);

解密结果

解密密文计算的结果，并通过Rust的assert_eq!宏验证结果。

tfhe-simple-ops.rs
    // Decryption and verification of proper execution
    let decrypted_add: u8 = add.decrypt(&client_key);
 
    let clear_add = clear_a + clear_b;
    assert_eq!(decrypted_add, clear_add);
 
    let decrypted_sub: u8 = sub.decrypt(&client_key);
 
    let clear_sub = clear_a - clear_b;
    assert_eq!(decrypted_sub, clear_sub);
 
    let decrypted_mul: u8 = mul.decrypt(&client_key);
 
    let clear_mul = clear_a * clear_b;
    assert_eq!(decrypted_mul, clear_mul);
 
    let decrypted_div: u8 = div.decrypt(&client_key);
 
    let clear_div = clear_a / clear_b;
    assert_eq!(decrypted_div, clear_div);
 
    let decrypted_rem: u8 = rem.decrypt(&client_key);
 
    let clear_rem = clear_a % clear_b;
    assert_eq!(decrypted_rem, clear_rem);
 
    let decrypted_and: u8 = and.decrypt(&client_key);
 
    let clear_and = clear_a & clear_b;
    assert_eq!(decrypted_and, clear_and);
 
    let decrypted_or: u8 = or.decrypt(&client_key);
 
    let clear_or = clear_a | clear_b;
    assert_eq!(decrypted_or, clear_or);
 
    let decrypted_xor: u8 = xor.decrypt(&client_key);
 
    let clear_xor = clear_a ^ clear_b;
    assert_eq!(decrypted_xor, clear_xor);
 
    let decrypted_neg: u8 = neg.decrypt(&client_key);
 
    let clear_neg = clear_a.wrapping_neg();
    assert_eq!(decrypted_neg, clear_neg);
 
    let decrypted_not: u8 = not.decrypt(&client_key);
 
    let clear_not = !clear_a;
    assert_eq!(decrypted_not, clear_not);
 
    let decrypted_shl: u8 = shl.decrypt(&client_key);
 
    let clear_shl = clear_a << clear_b;
    assert_eq!(decrypted_shl, clear_shl);
 
    let decrypted_shr: u8 = shr.decrypt(&client_key);
 
    let clear_shr = clear_a >> clear_b;
    assert_eq!(decrypted_shr, clear_shr);
 
    let decrypted_eq = eq.decrypt(&client_key);
 
    let eq = clear_a == clear_b;
    assert_eq!(decrypted_eq, eq);
 
    let decrypted_ne = ne.decrypt(&client_key);
 
    let ne = clear_a != clear_b;
    assert_eq!(decrypted_ne, ne);
 
    let decrypted_gt = gt.decrypt(&client_key);
 
    let gt = clear_a > clear_b;
    assert_eq!(decrypted_gt, gt);
 
    let decrypted_lt = lt.decrypt(&client_key);
 
    let lt = clear_a < clear_b;
    assert_eq!(decrypted_lt, lt);
}

TFHE-rs生态

围绕TFHE-rs，Zama构建了：

  • fhEVM，一个支持链上智能合约、链下进行加密数据运算的符号运算框架，扩展了EVM的可编程隐私保护。
  • Concrete及Concrete ML，自动把Python中的运算编译成加密数据运算的框架，支持保密数据上训练和推理机器学习模型。

此外，一些合作伙伴也基于TFHE-rs或fhEVM扩展了全同态密码在不同场景的应用。

TFHE-rs ecosystem

fhEVM框架

Zama主要通过网关服务收取费用，所有的费用都以 $ZAMA 代币支付。

Fhenix L2网络

计划以FHE-Rollup锚定以太坊主网，提供比ZK-Rollup扩容更强的隐私保护。

设计和实现

TFHE-rs采用分层的架构设计，从下往上依次是：

  • 硬件抽象层，包括CPU、GPU和HPU上FFT、NTT和CSPRNG实现。
  • 核心密码学层，包括参数定义、LWE/GLWE/RLWE、密钥切换和可编程自举。
  • 细粒度API层，暴露boolean、shortint和integer等模块接口。
  • 高层次API层，提供密钥管理和包含FheString、FheInt、FheUint和FheBool等密文类。

TFHE-rs architectural layers

数学结构

TFHE使用的环面（Torus）上的元素定义在实数环面T=R/Z\mathbb{T} = \mathbb{R} / \mathbb{Z}上，即所有元素都取模11后在区间[0,1)[0,1)上。为便于运算，这些浮点数都用定点整数表示。相关的文档说明如下。

tfhe/src/core_crypto/commons/math/torus/mod.rs
//! Converting to torus values.
//!
//! The theory behind some of the homomorphic operators of the library, uses the real torus
//! $\mathbb{T} = \mathbb{R} / \mathbb{Z}$, or the set or real numbers modulo 1 (elements of the
//! torus are in $[0,1)$). In practice, floating-point number are not well suited to performing
//! operations on the torus, and we prefer to use unsigned integer values to represent them.
//! Indeed, unsigned integer can be used to encode the decimal part of the torus element with a
//! fixed precision.
//!
//! Still, in some cases, we may need to represent an unsigned integer as a torus value in
//! floating point representation. For this reason we provide the [`IntoTorus`] and [`FromTorus`]
//! traits which allow to go back and forth between an unsigned integer representation and a
//! floating point representation.

高层次API接口

高层次API接口提供开发者友好的接口，屏蔽复杂密码学实现，让开发者集中精力在加密数据计算上。

密文数据类型

高层次API接口主要提供加密数据类型，包括无符号整型和带符号整型：

tfhe/src/high_level_api/mod.rs
pub use crate::high_level_api::booleans::{
    CompressedFheBool, FheBool, FheBoolConformanceParams, SquashedNoiseFheBool,
};
tfhe/src/high_level_api/mod.rs
expand_pub_use_fhe_type!(
    pub use crate::high_level_api::integers{
        FheUint2, FheUint4, FheUint6, FheUint8, FheUint10, FheUint12, FheUint14, FheUint16,
        FheUint32, FheUint64, FheUint128, FheUint160, FheUint256, FheUint512, FheUint1024,
        FheUint2048,
 
        FheInt2, FheInt4, FheInt6, FheInt8, FheInt10, FheInt12, FheInt14, FheInt16, FheInt32,
        FheInt64, FheInt128, FheInt160, FheInt256, FheInt512, FheInt1024, FheInt2048,
    };
);

还包括数组类型：

tfhe/src/high_level_api/array/mod.rs
pub use cpu::{
    CpuFheBoolArray, CpuFheBoolSlice, CpuFheBoolSliceMut, CpuFheIntArray, CpuFheIntSlice,
    CpuFheIntSliceMut, CpuFheUintArray, CpuFheUintSlice, CpuFheUintSliceMut, FheBoolId,
};
pub use dynamic::{
    FheBoolArray, FheBoolSlice, FheBoolSliceMut, FheIntArray, FheIntSlice, FheIntSliceMut,
    FheUintArray, FheUintSlice, FheUintSliceMut,
};

参数配置和密钥管理

对于密钥管理，高层次API提供以下类型：

  • tfhe::ClientKey，客户端密钥，用于加密和解密；
  • tfhe::ServerKey，服务端密钥，用户同态操作；
  • tfhe::generate_keys()，生成密钥对。

此外，还提供tfhe::ConfigBuilder作为参数配置。

使用方法

使用高层次API通常以下面的步骤进行：

  1. 配置参数：通过tfhe::ConfigBuilder设置参数；
  2. 密钥生成：调用tfhe::generate_keys()生成密钥；
  3. 设置服务端密钥：通过上一步的客户端密钥生成一个服务端密钥，也可以反序列化接受的密钥并通过thfe::set_server_key()设置；
  4. 加密：用客户端密钥加密数据；
  5. 计算：在密文上执行密文运算；
  6. 解密：用客户端密钥解密。

一个最简单的使用高层次API的代码片段：

single_tfhe_hl.rs
use tfhe::{ConfigBuilder, generate_keys, set_server_key, FheUint8};
 
let config = ConfigBuilder::default().build();
let (client_key, server_key) = generate_keys(config);
set_server_key(server_key);
 
let encrypted_a = FheUint8::encrypt(10, &client_key);
let encrypted_b = FheUint8::encrypt(5, &client_key);
let encrypted_result = encrypted_a + encrypted_b;
let decrypted_result: u8 = encrypted_result.decrypt(&client_key);

细粒度API接口

细粒度API提供更多控制，是扩展TFHE的主要接口。

什么时候用细粒度API？

不像高层次API生产环境可用并保持稳定，细粒度API更多是内部模块使用，并且可能经常会改变。因此，大部分情况下都不推荐直接使用细粒度API开发应用。 但有一些场景下，如要提供精细的控制（性能测试等）和增加新的后端支持（如ASIC后端），则只能通过细粒度API完成。

这一层提供的API主要包括：

  • 布尔类型API（tfhe::boolean模块），单个数据位的加密数据上逻辑运算；
  • 小整数类型API（tfhe::shortint模块），支持最高8位二进制整数的密文运算，支持自举，无操作次数限制；
  • 整数类型API（tfhe::integer模块），构建在小整数API之上，支持大整数运算。
不同后端对应不同的实现

除了上面导出的几个模块外，不同的后端如GPU和HPU也导出了类似的模块，便于直接使用与后端相关的操作。这样的模块包括tfhe::integer::gpu和tfhe::integer::hpu。 布尔类型和小整数类型并没有除CPU后端外的定义。

核心密码API接口

核心密码API提供最底层的接口，包含密码原语和TFHE同态密码方案的实现。其中关键组件由：

  • FFT实现和数学运算；
  • LWE/GLWE密文原语；
  • 可编程自举算法；
  • 参数管理和其他密码学原语。

使用这一层的常见用法如下。

core_crypto_api_example.ts
use tfhe::core_crypto::prelude::*;
// Access to low-level cryptographic primitives

密文算术运算

原始TFHE算法仅支持密文上的逻辑运算，如AND、OR、XOR等。TFHE-rs通过对shortint精巧的编码技巧和PBS设计，支持shortint的算术运算，并通过大整数的基分解表示拆分成多个shortint，从而实现了整数的密文算术运算。

shortint消息/进位编码

shortint层引入了最关键的编码技巧，将其密文编码成通过message_modulus和carry_modulus参数化的结构，从而把明文空间则划分为消息比特（message bits）和进位比特（carry bits）。需要注意的是，这里的进位比特并不限于单独的比特位，而可以是多个，保证自举过程中累加溢出位的空间。例如内置参数PARAM_MESSAGE_2_CARRY_2_KS_PBS使用2位消息比特和2位进位比特，可以在PBS前进行多次加法都不会超出进位比特的范围。

tfhe/src/shortint/ciphertext/standard.rs
#[derive(Debug, PartialEq, Eq, Serialize, Deserialize, Versionize)]
#[versionize(CiphertextVersions)]
#[must_use]
pub struct Ciphertext {
    pub ct: LweCiphertextOwned<u64>,
    pub degree: Degree,
    // For correctness reasons this field MUST remain private, this forces the use of the accessor
    // which has noise checks enabled on demand
    noise_level: NoiseLevel,
    pub message_modulus: MessageModulus,
    pub carry_modulus: CarryModulus,
    pub atomic_pattern: AtomicPatternKind,
}

可编程自举处理进位

可编程自举（Programmable Bootstrapping）可以同时完成两件事：

  • 刷新密文的噪声到正常水平；
  • 对查找表（LUT）编码的任意函数求值。

这其中第二项就用于处理密文中的进位，从而保证密文上的算术结果的正确性。AtomicPattern通过定义一系列的线性操作，跟随着一次KS和PBS，把加密的u64值转化成另一个u64值。基于LUT的累加器通过fill_accumulator_with_encoding闭包施加到所有的输入上，并形成GLWE多项式。

tfhe/src/shortint/atomic_pattern/mod.rs
/// The set of operations needed to implement an Atomic Pattern.
///
/// Here the definition of Atomic Pattern is a bit more TFHE-specific and includes the evaluation of
/// a lookup table. It does not, however, include the sequence of linear operations.
///
/// The atomic pattern can be seen as a black box that will apply a lookup table and refresh the
/// ciphertext noise to a nominal level. Between applications of the AP, it is possible to do a
/// certain number of linear operations.
pub trait AtomicPattern {
    /// The LWE dimension of the ciphertext used as input and output of the AP
    fn ciphertext_lwe_dimension(&self) -> LweDimension {
        let key_choice = EncryptionKeyChoice::from(self.kind().pbs_order());
        self.ciphertext_lwe_dimension_for_key(key_choice)
    }
 
    /// The LWE dimension of a ciphertext encrypted using the provided key choice
    fn ciphertext_lwe_dimension_for_key(&self, key_choice: EncryptionKeyChoice) -> LweDimension;
 
    /// The modulus of the ciphertext used as input and output of the AP
    fn ciphertext_modulus(&self) -> CiphertextModulus {
        let key_choice = EncryptionKeyChoice::from(self.kind().pbs_order());
        self.ciphertext_modulus_for_key(key_choice)
    }
 
    /// The modulus of a ciphertext encrypted using the provided key choice
    fn ciphertext_modulus_for_key(&self, key_choice: EncryptionKeyChoice) -> CiphertextModulus;
 
    /// Decompression method used to extract cipherexts compressed with the modulus switch
    /// compression
    fn ciphertext_decompression_method(&self) -> MsDecompressionType;
 
    /// Performs a full application of the atomic pattern, and modify the input [`Ciphertext`]
    /// in-place.
    ///
    /// After a call to this function, the ciphertext should encrypt a value that is the output of
    /// the lookup table, and the noise should be set to a nominal level.
    fn apply_lookup_table_assign(&self, ct: &mut Ciphertext, acc: &LookupTableOwned);

通过二元PBS实现密文乘法

两个密文的乘法不能通过线性操作实现，因此TFHE-rs使用二元PBS（bivariate PBS）。具体而言，把两个密文ClhsC_{\mathrm{lhs}}和CrhsC_{\mathrm{rhs}}通过C=Clhs⋅Δ+CrhsC=C_{\mathrm{lhs}}\cdot \Delta+ C_{\mathrm{rhs}}（Δ\Delta是缩放因子）打包成单个密文，接下来在PBS阶段对下面函数求值：

f(C)=Clhs⋅Crhsmod  qf(C) = C_{\mathrm{lhs}} \cdot C_{\mathrm{rhs}} \mod q
tfhe/src/shortint/server_key/bivariate_pbs.rs
impl<AP: AtomicPattern> GenericServerKey<AP> {
    /// Generates a bivariate accumulator
    pub fn generate_lookup_table_bivariate_with_factor<F>(
        &self,
        f: F,
        left_message_scaling: MessageModulus,
    ) -> BivariateLookupTableOwned
    where
        F: Fn(u64, u64) -> u64,
    {
        // Depending on the factor used, rhs and / or lhs may have carries
        // (degree >= message_modulus) which is why we need to apply the message_modulus
        // to clear them
        let factor_u64 = left_message_scaling.0;
        let message_modulus = self.message_modulus.0;
        let wrapped_f = |input: u64| -> u64 {
            let lhs = (input / factor_u64) % message_modulus;
            let rhs = (input % factor_u64) % message_modulus;
 
            f(lhs, rhs)
        };
        let accumulator = self.generate_lookup_table(wrapped_f);
 
        BivariateLookupTable {
            acc: accumulator,
            ct_right_modulus: left_message_scaling,
        }
    }

大整数基分解

在integer层，对超过一定范围的整数如FheUint32表示成一个shortint组成的向量块（从LSB到MSB）。相关的代码在RadixCiphertext中。

跨块进位传播

基分解后的密文运算后，进位需要跨块传播，相关代码如下。

tfhe/src/integer/server_key/radix_parallel/mod.rs
    pub fn propagate_parallelized<T>(&self, ctxt: &mut T, index: usize) -> Ciphertext
    where
        T: IntegerRadixCiphertext,
    {
        let (carry, message) = rayon::join(
            || self.key.carry_extract(&ctxt.blocks()[index]),
            || self.key.message_extract(&ctxt.blocks()[index]),
        );
        ctxt.blocks_mut()[index] = message;
 
        //add the carry to the next block
        if index < ctxt.blocks().len() - 1 {
            self.key
                .unchecked_add_assign(&mut ctxt.blocks_mut()[index + 1], &carry);
        }
 
        carry
    }

多块密文乘法

实现完整的整数密文乘法，TFHE-rs通过二元PBS逐块（block-by-block）计算每一块LSB和MSB的积，然后移位、汇总部分积得到最终的结果。

执行后端

HPU后端

从逻辑看，TFHE-rs对HPU指令分成两层抽象：

  • 整数操作（Integer Operations或IOp），IOp是TFHE-rs定义的高层次操作，通过PCIe发送到HPU控制器，表示一些对加密数据的操作。
  • 数位操作（Digit Operations或DOp），DOp则对应着HPU处理单元的微代码指令。

TFHE-rs代码库通过大量的条件编译完成对不同后端的支持。典型的代码片段如：

tfhe/src/high_level_api/config.rs
impl Config {
    #[cfg(feature = "hpu")]
    pub fn from_hpu_device(hpu_device: &tfhe_hpu_backend::prelude::HpuDevice) -> Self {
        let pbs_params =
            crate::shortint::parameters::KeySwitch32PBSParameters::from(hpu_device.params());
        ConfigBuilder::with_custom_parameters(pbs_params).build()
    }
 
    pub fn public_key_encryption_parameters(
        &self,
    ) -> Result<crate::shortint::parameters::CompactPublicKeyEncryptionParameters, crate::Error>
    {
        self.inner.public_key_encryption_parameters()
    }
}

扩展后端

增加新的后端支持需要大量改动包括细粒度和高层次API和模块。