search
Website

Homomorphic parity bit

This tutorial shows how to build a small function that homomorphically computes a parity bit in 2 steps:

  1. Write a non-generic function

  2. Use generics to handle the case where the function inputs are both FheBools and clear bools.

The parity bit function processes two parameters:

  • A slice of Boolean

  • A mode (Odd or Even)

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).

hashtag
Non-generic version

# Cargo.toml

# Default configuration for x86 Unix machines:
tfhe = { version = "0.9.1", features = ["integer", "x86_64-unix"]}

Refer to the installation for other configurations.

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:

hashtag
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.

hashtag
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:

PreviousAll tutorialsNextHomomorphic case changing on Ascii string

Last updated

Was this helpful?