Homomorphic parity bit
This tutorial shows how to build a small function that homomorphically computes a parity bit in 2 steps:
Write a non-generic function
Use generics to handle the case where the function inputs are both
FheBools and clearbools.
The parity bit function processes two parameters:
A slice of Boolean
A mode (
OddorEven)
This function returns a Boolean (true or false) so that the total count of true values across the input and the result matches with the specified parity mode (Odd or Even).
Non-generic version
# Cargo.toml
tfhe = { version = "~1.4.2", features = ["integer"] }First, define the verification function.
The function initializes the parity bit to false, then applies the XOR operation across all bits, adding negation based on the requested mode.
The validation function also adds the number of the bits set in the input to the computed parity bit and checks whether the sum is even or odd, depending on the mode.
#![allow(dead_code)]
use tfhe::FheBool;
#[derive(Copy, Clone, Debug)]
enum ParityMode {
// The sum bits of message + parity bit must an odd number
Odd,
// The sum bits of message + parity bit must an even number
Even,
}
fn compute_parity_bit(fhe_bits: &[FheBool], mode: ParityMode) -> FheBool {
let mut parity_bit = fhe_bits[0].clone();
for fhe_bit in &fhe_bits[1..] {
parity_bit = fhe_bit ^ parity_bit
}
match mode {
ParityMode::Odd => !parity_bit,
ParityMode::Even => parity_bit,
}
}
fn is_even(n: u8) -> bool {
(n & 1) == 0
}
fn is_odd(n: u8) -> bool {
!is_even(n)
}
fn check_parity_bit_validity(bits: &[bool], mode: ParityMode, parity_bit: bool) -> bool {
let num_bit_set = bits
.iter()
.map(|bit| *bit as u8)
.fold(parity_bit as u8, |acc, bit| acc + bit);
match mode {
ParityMode::Even => is_even(num_bit_set),
ParityMode::Odd => is_odd(num_bit_set),
}
}After configurations, call the function:
Generic version
To enable the compute_parity_bit function to operate with both encrypted FheBool and plain bool, we introduce generics. This approach allows for validation using clear data and facilitates debugging.
Writing generic functions that incorporate operator overloading for our Fully Homomorphic Encryption (FHE) types is more complex than usual because FHE types do not implement the Copy trait. Consequently, it is necessary to use references (&) with these types, unlike native types, which typically implement Copy.
This complicates generic bounds at first.
Writing the correct trait bounds
The function has the following signature:
To make it generic, the first steps is:
Next, define the generic bounds with the where clause.
In the function, you can use the following operators:
!(trait:Not)^(trait:BitXor)
Adding them to where, it gives:
However, the compiler will return an error:
fhe_bit is a reference to a BoolType (&BoolType), because BoolType is borrowed from the fhe_bits slice during iteration. To fix the error, the first approach could be changing the BitXor bounds to what the Compiler suggests, by requiring &BoolType to implement BitXor rather than BoolType.
However, this approach still leads to an error:
To fix this error, use Higher-Rank Trait Bounds:
The final code is as follows:
Here is a complete example that uses this function for both clear and FHE values:
Last updated
Was this helpful?