Overflow detection

This document explains how TFHE-rs implements specific operations to detect overflows in computations.

The mechanism of detecting overflow consists in returning an encrypted flag with a specific ciphertext that reflects the state of the computation. When an overflow occurs, this flag is set to true. Since the server is not able to evaluate this encrypted value, the client has to check the flag value when decrypting to determine if an overflow has happened.

These operations might be slower than their non-overflow-detecting equivalent, so they are not enabled by default. To use them, you must explicitly call specific operators. At the moment, only additions, subtractions, and multiplications are supported. We plan to add more operations in future releases.

Here's the list of operations supported along with their symbol:

namesymboltype

overflow_add

Binary

overflow_sub

Binary

overflow_mul

Binary

The usage of these operations is similar to the standard ones. The key difference is in the decryption process, as shown in following example:

/// Adds two [FheUint] and returns a boolean indicating overflow.
///
/// * The operation is modular, i.e on overflow the result wraps around.
/// * On overflow the [FheBool] is true, otherwise false

use tfhe::prelude::*;
use tfhe::{generate_keys, set_server_key, ConfigBuilder, FheUint16};

let (client_key, server_key) = generate_keys(ConfigBuilder::default());
set_server_key(server_key);

let a = FheUint16::encrypt(u16::MAX, &client_key);
let b = FheUint16::encrypt(1u16, &client_key);

let (result, overflowed) = (&a).overflowing_add(&b);
let result: u16 = result.decrypt(&client_key);
assert_eq!(result, u16::MAX.wrapping_add(1u16));
assert_eq!(
	overflowed.decrypt(&client_key),
	u16::MAX.overflowing_add(1u16).1
);
assert!(overflowed.decrypt(&client_key));

The following tables show the current benchmarks result.

Unsigned homomorphic integers:

Operation\SizeFheUint8FheUint16FheUint32FheUint64FheUint128FheUint256

unsigned_overflowing_add

63.67 ms

84.11 ms

107.95 ms

120.8 ms

147.38 ms

191.28 ms

unsigned_overflowing_sub

68.89 ms

81.83 ms

107.63 ms

120.38 ms

150.21 ms

190.39 ms

unsigned_overflowing_mul

140.76 ms

191.85 ms

272.65 ms

510.61 ms

1.34 s

4.51 s

Signed homomorphic integers:

Operation\SizeFheInt8FheInt16FheInt32FheInt64FheInt128FheInt256

signed_overflowing_add

76.54 ms

84.78 ms

104.23 ms

134.38 ms

162.99 ms

202.56 ms

signed_overflowing_sub

82.46 ms

86.92 ms

104.41 ms

132.21 ms

168.06 ms

201.17 ms

signed_overflowing_mul

277.91 ms

365.67 ms

571.22 ms

1.21 s

3.57 s

12.84 s

Last updated