Links

Detect Overflow

TFHE-rs includes a list of specific operations to detect overflows. The overall idea is to have a specific ciphertext encrypting a flag reflecting the status of the computations. When an overflow occurs, this flag is set to true. Since the server is not able to evaluate this value (since it is encrypted), the client has to check the flag value when decrypting to determine if an overflow has happened. These operations might be slower than their equivalent which do not detect overflow, so they are not enabled by default (see the table below). In order to use them, specific operators must be called. At the moment, only additions, subtractions, multiplications are supported. Missing operations will be added soon.
The list of operations along with their symbol is:
name
symbol
type
Add
overflow_add
Binary
Sub
overflow_sub
Binary
Mul
overflow_mul
Binary
These operations are then used exactly in the same way than the usual ones. The only difference lies into the decryption, 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_eq!(overflowed.decrypt(&client_key), true);
The current benchmarks are given in the following tables (the first one for unsigned homomorphic integers and the second one for the signed integers):
Operation\Size
FheUint8
FheUint16
FheUint32
FheUint64
FheUint128
FheUint256
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
Operation\Size
FheInt8
FheInt16
FheInt32
FheInt64
FheInt128
FheInt256
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