Cargo.toml

[package]
name = "homomorphic_min_max"
version = "0.1.0"
edition = "2021"

[dependencies]
concrete = "0.1.11"

lib.rs

pub use concrete::*;


// compute the maximum of two encrypted numbers
//
// Arguments: 
//  
//  cipher_1: the first cipher
//  cipher_2: the second cipher
//  ksk: the key-changing key needed to revert the key change induced by the bootstrap
//  bsk: the boostrapping key
//  encoder: the encoder to use in the bootstrap
//  zero: an encryption of 0 with inverted encoder with respect to cipher_1 and cipher_2
fn compute_max(cipher_1: &LWE, cipher_2: &LWE, ksk: &LWEKSK, bsk: &LWEBSK, 
               encoder: &Encoder, zero: &LWE)
    -> Result<LWE, CryptoAPIError>
{
    
    // difference between the two ciphers
    let cipher_diff = cipher_2.add_centered(&cipher_1.opposite()?)?;

    // programmable bootstrap to check if the difference is positive
    let mut cipher_diff_pos = cipher_diff.bootstrap_with_function(bsk, 
                                                              |x| if x >= 0. { x } else { 0. }, 
                                                              encoder)?;

    // change the key back to the original one
    cipher_diff_pos = cipher_diff_pos.keyswitch(ksk)?;

    // add the result to cipher_1
    let mut result = cipher_1.add_centered(&cipher_diff_pos)?;

    // subtract 0 to reset the encoder offset
    result.add_centered_inplace(zero)?;

    Ok(result)
}


// compute the minimum of two encrypted numbers
//
// Arguments: 
//  
//  cipher_1: the first cipher
//  cipher_2: the second cipher
//  ksk: the key-changing key needed to revert the key change induced by the bootstrap
//  bsk: the boostrapping key
//  encoder: the encoder to use in the bootstrap
//  zero: an encryption of 0
fn compute_min(cipher_1: &LWE, cipher_2: &LWE, ksk: &LWEKSK, bsk: &LWEBSK, 
               encoder: &Encoder, zero: &LWE)
    -> Result<LWE, CryptoAPIError>
{
    
    // difference between the two ciphers
    let cipher_diff = cipher_2.add_centered(&cipher_1.opposite()?)?;

    // programmable bootstrap to check if the difference is positive
    let mut cipher_diff_pos = cipher_diff.bootstrap_with_function(bsk, 
                                                              |x| if x >= 0. { x } else { 0. }, 
                                                              encoder)?;

    // change the key back to the original one
    cipher_diff_pos = cipher_diff_pos.keyswitch(ksk)?;

    // subtract the result from cipher_2
    let mut result = cipher_2.add_centered(&cipher_diff_pos.opposite()?)?;

    // add 0 to reset the encoder offset
    result.add_centered_inplace(zero)?;

    Ok(result)
}


/// compute the maximum of an array of encrypted numbers
///
///  ciphers: an array of ciphertexts
///  ksk: the key-changing key needed to revert the key change induced by the bootstrap
///  bsk: the boostrapping key
///  encoder: the encoder to use in the bootstrap
///  zero: an encryption of 0 with inverted encoder with respect to cipher_1 and cipher_2
pub fn compute_max_array(ciphers: &[LWE], ksk: &LWEKSK, bsk: &LWEBSK, encoder: &Encoder, zero: &LWE) 
    -> Result<LWE, Box<dyn std::error::Error>> 
{
    // compute the opposite of 0 to reverse the encoder
    let zero = zero.opposite()?;

    // convert the array of ciphers into an iterator
    let mut ciphers_iter = ciphers.iter();

    // set the result to the first cipher, or return an error if the iterator is empty
    let mut result = ciphers_iter.next().ok_or("Empty cipher array!".to_string())?.clone();

    // loop over the other ciphers
    for cipher in ciphers_iter {

        // get the maximum of the current result and next cipher
        result = compute_max(&result, cipher, ksk, bsk, encoder, &zero)?;
    }

    Ok(result)
}


/// compute the minimum of an array of encrypted numbers
///
///  ciphers: an array of ciphertexts
///  ksk: the key-changing key needed to revert the key change induced by the bootstrap
///  bsk: the boostrapping key
///  encoder: the encoder to use in the bootstrap
///  zero: an encryption of 0 with inverted encoder with respect to cipher_1 and cipher_2
pub fn compute_min_array(ciphers: &[LWE], ksk: &LWEKSK, bsk: &LWEBSK, encoder: &Encoder, zero: &LWE) 
    -> Result<LWE, Box<dyn std::error::Error>> 
{

    // convert the array of ciphers into an iterator
    let mut ciphers_iter = ciphers.iter();

    // set the result to the first cipher, or return an error if the iterator is empty
    let mut result = ciphers_iter.next().ok_or("Empty cipher array!".to_string())?.clone();

    // loop over the other ciphers
    for cipher in ciphers_iter {

        // get the minimum of the current result and next cipher
        result = compute_min(&result, cipher, ksk, bsk, encoder, &zero)?;
    }

    Ok(result)
}


// compute the maximum and minimum of two encrypted numbers
//
// Arguments: 
//  
//  cipher_1: the first cipher
//  cipher_2: the second cipher
//  ksk: the key-changing key needed to revert the key change induced by the bootstrap
//  bsk: the boostrapping key
//  encoder: the encoder to use in the bootstrap
fn compute_max_min(cipher_1: &LWE, cipher_2: &LWE, ksk: &LWEKSK, bsk: &LWEBSK, encoder: &Encoder)
    -> Result<(LWE, LWE), CryptoAPIError>
{
    
    // difference between the two ciphers
    let cipher_diff = cipher_2.sub_with_padding(&cipher_1)?;

    // programmable bootstrap to check if the difference is positive
    let mut cipher_diff_pos = cipher_diff.bootstrap_with_function(bsk, 
                                                              |x| if x >= 0. { x } else { 0. }, 
                                                              encoder)?;

    // change the key back to the original one
    cipher_diff_pos = cipher_diff_pos.keyswitch(ksk)?;

    // add the result to cipher_1
    let mut result_max = cipher_1.add_with_padding(&cipher_diff_pos)?;
    
    // subtract the result from cipher_2
    let mut result_min = cipher_2.sub_with_padding(&cipher_diff_pos)?;

    // reset the encoder
    result_max = result_max.bootstrap_with_function(bsk, |x| x, encoder)?;
    result_min = result_min.bootstrap_with_function(bsk, |x| x, encoder)?;
    result_max = result_max.keyswitch(ksk)?;
    result_min = result_min.keyswitch(ksk)?;

    Ok((result_max, result_min))
}


/// sort an array of ciphertexts
pub fn sort_array(ciphers: &[LWE], ksk: &LWEKSK, bsk: &LWEBSK, encoder: &Encoder) 
    -> Result<Vec<LWE>, Box<dyn std::error::Error>> 
{
    // if ciphers contains less than two elements, just return it
    if ciphers.len() < 2 {
        return Ok(ciphers.to_vec())
    }
    
    // vector containing the result
    let mut results = ciphers.to_vec();

    for i in 0..(ciphers.len()-1) {
        for j in (i+1)..ciphers.len() {
            let (c_max, c_min) = compute_max_min(&results[i], &results[j], ksk, bsk, encoder)?;
            results[i] = c_min;
            results[j] = c_max;
        }
    }

    Ok(results)

}

lib1.rs

fn compute_max(cipher_1: &LWE, cipher_2: &LWE, ksk: &LWEKSK, bsk: &LWEBSK, 
               encoder: &Encoder, zero: &LWE)
    -> Result<LWE, CryptoAPIError>
{
    
    // difference between the two ciphers
    let cipher_diff = cipher_2.add_centered(&cipher_1.opposite()?)?;

    // programmable bootstrap to check if the difference is positive
    let mut cipher_diff_pos = cipher_diff.bootstrap_with_function(bsk, 
                                                              |x| if x >= 0. { x } else { 0. }, 
                                                              encoder)?;

    // change the key back to the original one
    cipher_diff_pos = cipher_diff_pos.keyswitch(ksk)?;

    // add the result to cipher_1
    let mut result = cipher_1.add_centered(&cipher_diff_pos)?;

    // subtract 0 to reset the encoder offset
    result.add_centered_inplace(zero)?;

    Ok(result)
}

lib2.rs

fn compute_min(cipher_1: &LWE, cipher_2: &LWE, ksk: &LWEKSK, bsk: &LWEBSK, 
               encoder: &Encoder, zero: &LWE)
    -> Result<LWE, CryptoAPIError>
{
    
    // difference between the two ciphers
    let cipher_diff = cipher_2.add_centered(&cipher_1.opposite()?)?;

    // programmable bootstrap to check if the difference is positive
    let mut cipher_diff_pos = cipher_diff.bootstrap_with_function(bsk, 
                                                              |x| if x >= 0. { x } else { 0. }, 
                                                              encoder)?;

    // change the key back to the original one
    cipher_diff_pos = cipher_diff_pos.keyswitch(ksk)?;

    // subtract the result from cipher_2
    let mut result = cipher_2.add_centered(&cipher_diff_pos.opposite()?)?;

    // add 0 to reset the encoder offset
    result.add_centered_inplace(zero)?;

    Ok(result)
}

lib3.rs

pub fn compute_max_array(ciphers: &[LWE], ksk: &LWEKSK, bsk: &LWEBSK, encoder: &Encoder, zero: &LWE) 
    -> Result<LWE, Box<dyn std::error::Error>> 
{
    // compute the opposite of 0 to reverse the encoder
    let zero = zero.opposite()?;

    // convert the array of ciphers into an iterator
    let mut ciphers_iter = ciphers.iter();

    // set the result to the first cipher, or return an error if the iterator is empty
    let mut result = ciphers_iter.next().ok_or("Empty cipher array!".to_string())?.clone();

    // loop over the other ciphers
    for cipher in ciphers_iter {

        // get the maximum of the current result and next cipher
        result = compute_max(&result, cipher, ksk, bsk, encoder, &zero)?;
    }

    Ok(result)
}

lib4.rs

pub fn compute_min_array(ciphers: &[LWE], ksk: &LWEKSK, bsk: &LWEBSK, encoder: &Encoder, zero: &LWE) 
    -> Result<LWE, Box<dyn std::error::Error>> 
{

    // convert the array of ciphers into an iterator
    let mut ciphers_iter = ciphers.iter();

    // set the result to the first cipher, or return an error if the iterator is empty
    let mut result = ciphers_iter.next().ok_or("Empty cipher array!".to_string())?.clone();

    // loop over the other ciphers
    for cipher in ciphers_iter {

        // get the minimum of the current result and next cipher
        result = compute_min(&result, cipher, ksk, bsk, encoder, &zero)?;
    }

    Ok(result)
}

line1.rs

let cipher_diff = cipher_2.add_centered(&cipher_1.opposite()?)?;

line2.rs

let mut cipher_diff_pos = cipher_diff.bootstrap_with_function(bsk, 
                                                         |x| if x >= 0. { x } else { 0. }, 
                                                         encoder)?;

line3.rs

cipher_diff_pos = cipher_diff_pos.keyswitch(ksk)?;

line4.rs

let mut result = cipher_1.add_centered(&cipher_diff_pos)?;

line5.rs

result.add_centered_inplace(zero)?;

main.rs

use homomorphic_min_max::*;

fn main() -> Result<(), Box<dyn std::error::Error>> {

    // encoder
    let encoder = Encoder::new(0., 1., 4, 2)?;

    // expected precision
    let precision = 0.2;

    // secret keys
    let sk_rlwe = RLWESecretKey::new(&RLWE128_1024_1);
    let sk_in = LWESecretKey::new(&LWE128_1024);
    let sk_out = sk_rlwe.to_lwe_secret_key();

    // encryption of 0
    let zero = LWE::encode_encrypt(&sk_in, 0., &encoder)?;

    // key switching key
    let ksk = LWEKSK::new(&sk_out, &sk_in, 5, 5);

    // bootstrapping key
    let bsk = LWEBSK::new(&sk_in, &sk_rlwe, 5, 5);

    // messages 
    let messages: Vec<f64> = vec![0.2, 0.4, 0.2, 0.6, 0.2, 0.4];

    // encrypt the messages
    let ciphers: Vec<LWE>
        = messages.iter().map(|m| LWE::encode_encrypt(&sk_in, *m, &encoder))
                  .collect::<Result<Vec<LWE>, CryptoAPIError>>()?;
    
    // perform the calculation
    let cipher_max = compute_max_array(&ciphers, &ksk, &bsk, &encoder, &zero)?;
    let cipher_min = compute_min_array(&ciphers, &ksk, &bsk, &encoder, &zero)?;

    // decrypt
    let mut max_val = cipher_max.decrypt_decode(&sk_in)?;
    let mut min_val = cipher_min.decrypt_decode(&sk_in)?;

    // round the results
    max_val = (max_val / precision).round() * precision;
    min_val = (min_val / precision).round() * precision;

    // print the result
    println!("maximum: {}", max_val);
    println!("minimum: {}", min_val);

    // sort the array
    let ciphers_sorted = sort_array(&ciphers, &ksk, &bsk, &encoder)?;

    // decrypt the results
    let mut decrypted 
        = ciphers_sorted.iter().map(|c| { c.decrypt_decode_round(&sk_in) })
                        .collect::<Result<Vec<f64>, CryptoAPIError>>()?;

    // round the results
    for i in 0..decrypted.len() {
        decrypted[i] = (decrypted[i] / precision).round() * precision;
    }

    // print the result
    println!("{:?}", decrypted);

    Ok(())
}

main1.rs

use homomorphic_min_max::*;

fn main() -> Result<(), Box<dyn std::error::Error>> {

}

main10.rs

    println!("maximum: {}", max_val);
    println!("minimum: {}", min_val);

    Ok(())

main2.rs

    // encoder
    //
    // minimum value: 0
    // maximum value: 1
    // number of levels: 2^4
    // number of bits of padding: 2
    let encoder = Encoder::new(0., 1., 4, 2)?;

main3.rs

    // secret keys
    //
    // polynomial size: 1024
    // security level: 128 bits
    let sk_rlwe = RLWESecretKey::new(&RLWE128_1024_1);
    let sk_in = LWESecretKey::new(&LWE128_1024);
    let sk_out = sk_rlwe.to_lwe_secret_key();

main4.rs

    // define the key-changing key and bootstrapping key
    //
    // base log: 2^5
    // number of levels: 2^5
    let ksk = LWEKSK::new(&sk_out, &sk_in, 5, 5);
    let bsk = LWEKSK::new(&sk_out, &sk_in, 5, 5);

main5.rs

    // messages 
    let messages: Vec<f64> = vec![0.3, 0.5, 0.3, 0.6, 0.1, 0.3];

main6.rs

    // encrypt the messages
    let ciphers: Vec<LWE>
        = messages.iter().map(|m| LWE::encode_encrypt(&sk_in, *m, &encoder))
                  .collect::<Result<Vec<LWE>, CryptoAPIError>>()?;

main7.rs

    let cipher_max = compute_max_array(&ciphers, &ksk, &bsk, &encoder, &zero)?;
    let cipher_min = compute_min_array(&ciphers, &ksk, &bsk, &encoder, &zero)?;

main8.rs

    let mut max_val = cipher_max.decrypt_decode(&sk_in)?;
    let mut min_val = cipher_min.decrypt_decode(&sk_in)?;

main9.rs

    max_val = (10.*max_val).round() / 10.;
    min_val = (10.*min_val).round() / 10.;

main_bis.rs

// sort the array
let ciphers_sorted = sort_array(&ciphers, &ksk, &bsk, &encoder)?;

// decrypt the results
let mut decrypted 
    = ciphers_sorted.iter().map(|c| { c.decrypt_decode_round(&sk_in) })
                    .collect::<Result<Vec<f64>, CryptoAPIError>>()?;

// round the results
for i in 0..decrypted.len() {
    decrypted[i] = (decrypted[i] / precision).round() * precision;
}

// print the result
println!("{:?}", decrypted);

Ok(())

min_and_max.rs

// compute the maximum and minimum of two encrypted numbers
//
// Arguments: 
//  
//  cipher_1: the first cipher
//  cipher_2: the second cipher
//  ksk: the key-changing key needed to revert the key change induced by the bootstrap
//  bsk: the boostrapping key
//  encoder: the encoder to use in the bootstrap
fn compute_max_min(cipher_1: &LWE, cipher_2: &LWE, ksk: &LWEKSK, bsk: &LWEBSK, encoder: &Encoder)
    -> Result<(LWE, LWE), CryptoAPIError>
{
    
    // difference between the two ciphers
    let cipher_diff = cipher_2.sub_with_padding(&cipher_1)?;

    // programmable bootstrap to check if the difference is positive
    let mut cipher_diff_pos = cipher_diff.bootstrap_with_function(bsk, 
                                                              |x| if x >= 0. { x } else { 0. }, 
                                                              encoder)?;

    // change the key back to the original one
    cipher_diff_pos = cipher_diff_pos.keyswitch(ksk)?;

    // add the result to cipher_1
    let mut result_max = cipher_1.add_with_padding(&cipher_diff_pos)?;
    
    // subtract the result from cipher_2
    let mut result_min = cipher_2.sub_with_padding(&cipher_diff_pos)?;

    // reset the encoder
    result_max = result_max.bootstrap_with_function(bsk, |x| x, encoder)?;
    result_min = result_min.bootstrap_with_function(bsk, |x| x, encoder)?;
    result_max = result_max.keyswitch(ksk)?;
    result_min = result_min.keyswitch(ksk)?;

    Ok((result_max, result_min))
}

output_1.txt

maximum: 0.6
minimum: 0.1

sort_array.rs

pub fn sort_array(ciphers: &[LWE], ksk: &LWEKSK, bsk: &LWEBSK, encoder: &Encoder) 
    -> Result<Vec<LWE>, Box<dyn std::error::Error>> 
{
    // if ciphers contains less than two elements, just return it
    if ciphers.len() < 2 {
        return Ok(ciphers.to_vec())
    }
    
    // vector containing the result
    let mut results = ciphers.to_vec();

    for i in 0..(ciphers.len()-1) {
        for j in (i+1)..ciphers.len() {
            let (c_max, c_min) = compute_max_min(&results[i], &results[j], ksk, bsk, encoder)?;
            results[i] = c_min;
            results[j] = c_max;
        }
    }

    Ok(results)
}