Skip to content

Instantly share code, notes, and snippets.

@FlorentCLMichel
Last active Nov 11, 2021
Embed
What would you like to do?
[package]
name = "homomorphic_min_max"
version = "0.1.0"
edition = "2021"
[dependencies]
concrete = "0.1.11"
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)
}
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)
}
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)
}
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)
}
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)
}
let cipher_diff = cipher_2.add_centered(&cipher_1.opposite()?)?;
let mut cipher_diff_pos = cipher_diff.bootstrap_with_function(bsk,
|x| if x >= 0. { x } else { 0. },
encoder)?;
cipher_diff_pos = cipher_diff_pos.keyswitch(ksk)?;
let mut result = cipher_1.add_centered(&cipher_diff_pos)?;
result.add_centered_inplace(zero)?;
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(())
}
use homomorphic_min_max::*;
fn main() -> Result<(), Box<dyn std::error::Error>> {
}
println!("maximum: {}", max_val);
println!("minimum: {}", min_val);
Ok(())
// 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)?;
// 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();
// 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);
// messages
let messages: Vec<f64> = vec![0.3, 0.5, 0.3, 0.6, 0.1, 0.3];
// encrypt the messages
let ciphers: Vec<LWE>
= messages.iter().map(|m| LWE::encode_encrypt(&sk_in, *m, &encoder))
.collect::<Result<Vec<LWE>, CryptoAPIError>>()?;
let cipher_max = compute_max_array(&ciphers, &ksk, &bsk, &encoder, &zero)?;
let cipher_min = compute_min_array(&ciphers, &ksk, &bsk, &encoder, &zero)?;
let mut max_val = cipher_max.decrypt_decode(&sk_in)?;
let mut min_val = cipher_min.decrypt_decode(&sk_in)?;
max_val = (10.*max_val).round() / 10.;
min_val = (10.*min_val).round() / 10.;
// 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(())
// 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))
}
maximum: 0.6
minimum: 0.1
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)
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment