Implementing the Regev Cryptosystem

Purpose:

The purpose of this deliverable was to implement the public key system from [Regev2009]. The system is a candidate for post-quantum cryptography.

Code:

main.rs

// main.rs
mod text;
use rand_distr::{Normal, Distribution};
use rand::{thread_rng, Rng};
use std::process;
use rand::prelude::SliceRandom;
use std::time::Instant;
use std::time::Duration;
use std::collections::HashMap;

fn main() {

    // Example use
    let (public_key, private_key) = create_system(5, 0.5);
    let ciphertext = encrypt(String::from("one two three four five"), &public_key);
    let plaintext = decrypt(&ciphertext, &private_key);
    println!("plaintext = {}", plaintext);

}

// Takes in the security parameter n and the error E
// Sets m and p according to the parameter requirements 
// and returns the resulting private and public key
fn create_system(n:u64, E:f64) -> (public_key, private_key, Vec<u64>) {
    let mut lower = n*n;
    let mut upper = 2*lower;
    let mut p = rand::thread_rng().gen_range(lower..upper) as u64;
    if p < 2 {  
        println!("Error: p must be >= 2");
        process::exit(1);
    }
    let m = ((1.0 + E) * (n as f64 + 1.0) * (p as f64).log2());
    let m = m.round() as u64;
    let mut B = alpha(n as f64);
    let private_key = private_key {
        p: p,
        s: draw_vector_from_Znp(n, p)
    };
    let (lst, e_vector) = get_list(m, n, p, B, &private_key.s);
    let public_key = public_key {
        m: m,
        n: n,
        p: p,
        list: lst
    };
    return (public_key, private_key, e_vector);
}

// Holds the tuple used in the public key and the encrypted message
#[derive(Clone)]
pub struct pair {
    pub a: Vec<u64>,
    pub b: u64
}

// Holds the private key
pub struct private_key {
    pub s: Vec<u64>,
    pub p: u64
}

// Holds the public key
pub struct public_key {
    pub m: u64,
    pub n: u64,
    pub p: u64,
    pub list: Vec<pair>
}

// Takes in a String and returns the ciphertext as a vector of tuples
pub fn encrypt(message:String, public_key:&public_key) -> Vec<pair> {
    let mut plaintext = string_to_binary_vec(message);
    return encrypt_vector(&plaintext, &public_key);
}

// Takes in ciphertext in the form of a vector of tuples 
// Returns the plaintext as a String
pub fn decrypt(ciphertext:&Vec<pair>, private_key:&private_key) -> String {
    let mut plaintext = decrypt_vector(ciphertext, &private_key);
    let mut plaintext = binary_vec_to_string(&plaintext);
    plaintext
}

// Takes in a vector of zeros and ones and encrypts each bit at a time
// Returns a vector of tuples representing the ciphertext
fn encrypt_vector(message:&Vec<u64>, public_key:&public_key) -> Vec<pair> {
    let mut encrypted_bits = Vec::new();
    for bit in message {
        let (pair, error_sum) = encrypt_bit(*bit, &public_key);
        encrypted_bits.push(pair);
    }
    encrypted_bits
}

// Takes in a vector of tuples 
// Returns a vector of zeros and ones representing the plaintext
fn decrypt_vector(encrypted_bits:&Vec<pair>, private_key:&private_key) -> Vec<u64> {
    let mut decrypted_bits = Vec::new();
    for bit in encrypted_bits {
        let mut decrypted_bit = decrypt_bit(bit, &private_key);
        decrypted_bits.push(decrypted_bit);
    }
    decrypted_bits
}

// Decrypts a single bit 
fn decrypt_bit(encrypted_bit:&pair, private_key:&private_key) -> u64 {
    let s = private_key.s.clone();
    let p = private_key.p;
    let mut a = encrypted_bit.a.clone();
    let mut b = encrypted_bit.b.clone();
    let mut inner_product = inner_product(&a, &s, p);
    let mut point = (b as i64 - inner_product as i64).rem_euclid(p as i64) as u64;
    let mut q = (p as f64 / 2 as f64).floor() as u64;
    let mut circular_distance_to_0 = circular_distance(point as u64, 0, p);
    let mut circular_distance_to_q = circular_distance(point as u64, q, p);
    if circular_distance_to_0 < circular_distance_to_q {
        return 0;
    } else {
        return 1;
    }
}

// This method is used in the decryption of a bit
// https://stackoverflow.com/questions/6192825/c-calculating-the-distance-between-2-floats-modulo-12 
fn circular_distance(point:u64, target:u64, modulus:u64) -> u64 {
    let diff = (point as i64 - target as i64).abs() as u64;
    return std::cmp::min(diff, modulus-diff);
}

// Encrypts a single bit and returns the result
fn encrypt_bit(bit:u64, public_key:&public_key) -> (pair, Vec<u64>) {
    let m = public_key.m;
    let n = public_key.n;
    let p = public_key.p;
    let list = public_key.list.clone();
    let mut subset = choose_subset(m); 
    let mut x = vec![0; n as usize];
    let mut y = 0 as u64;
    for index in subset.clone() {
        let mut a = list[index as usize].a.clone();
        let mut b = list[index as usize].b.clone();
        x = add_vector(&x, &a, p);
        y += b; 
        y = y.rem_euclid(p);
        
    }
    if bit == 0 {
        let pair = pair {
            a: x,
            b: y
        };
        return (pair, subset);
    } else {
        y += (p as f64 / 2 as f64).floor() as u64;
        y = y.rem_euclid(p);
        let pair = pair {
            a: x,
            b: y
        };
        return (pair, subset);
    }
}

// Adds two vectors modulo p and returns the result
fn add_vector(a:&Vec<u64>, b:&Vec<u64>, p:u64) -> Vec<u64> {
    let mut sum = Vec::new();
    for i in 0..a.len() {
        sum.push((a[i] + b[i]).rem_euclid(p));
    }
    sum
}

// This method chooses a subset for the encryption of a single bit
// and returns a vector of indices
fn choose_subset(m:u64) -> Vec<u64> {
    let mut set = Vec::new();
    let mut num = Vec::new();
    while num.len() < m as usize { // create length m vector of 1s and 0s
        num.push(rand::thread_rng().gen_range(0..2) as u8); // 0 or 1
    }
    for index in 0..num.len() {
        if num[index]==1 {
            set.push((index) as u64);
        }
    }
    set
}

// Returns a list of tuples used in the public key
fn get_list(m:u64, n:u64, p:u64, B:f64, private_key:&Vec<u64>) -> (Vec<pair>, Vec<u64>) {
    let mut s = private_key.clone();
    let mut public_key = Vec::new();
    let mut e_vector = Vec::new();
    for i in 0..m {
        let mut a = draw_vector_from_Znp(n, p);
        let mut e = draw_element_from_X(p, B);
        e_vector.push(e);
        let mut b = (inner_product(&a, &s, p) + e).rem_euclid(p); 
        let mut pair = pair {
            a: a, 
            b: b
        };
        public_key.push(pair);
    }
    (public_key, e_vector)
} 

// Computes the dot product of two vectors modulo p and returns the result
fn inner_product(a:&Vec<u64>, b:&Vec<u64>, p:u64) -> u64 {
    let mut sum = 0;
    if a.len() != b.len() {
        println!("Error in inner product - lengths were different");
        process::exit(1);
    }
    for i in 0..a.len() {
        sum += a[i] * b[i];
    }
    return (sum).rem_euclid(p);
}

// Draws a vector of length n with elements 
// in {0,...,p-1} for use in the public and private keys
fn draw_vector_from_Znp(n:u64, p:u64) -> Vec<u64> {
    let mut vec = Vec::new();
    for i in 0..n {
        vec.push(rand::thread_rng().gen_range(0..p));
    }
    vec
}

// Draws an error from the specified error distribution
fn draw_element_from_X(p:u64, B:f64) -> u64 {
    let mut mean = 0.0;
    // mean 0, standard deviation B/sqrt(2pi)
    let mut std_dev = B/(2 as f64*std::f64::consts::PI).sqrt(); 
    // create normal distribution 
    let normal = Normal::new(mean, std_dev).unwrap(); 
    // sample from normal distribution
    let mut v = normal.sample(&mut rand::thread_rng()); 
    // reduce result modulo 1
    let mut w = (v).rem_euclid(1.0); 
    // multiply by p
    let mut x = w * p as f64; 
    // round to nearest integer modulo p
    let mut y = (x.round()).rem_euclid(p as f64); 
    return y as u64;
}


// Returns B E R+, a parameters used in the error distribution
fn alpha(n:f64) -> f64 {
    return 1 as f64/(n.sqrt() * n.log2() * n.log2());
}


// Returns vector of all possible binary vectors of width width
pub fn all_possible_messages(width:u64) -> Vec<Vec<u64>> {
    let mut vectors = Vec::new();
    for i in 0..2_u64.pow(width as u32) {
        let mut vec = vec(i, width);
        vectors.push(vec);
    }
    vectors
}

// Converts a u64 to a binary vector
pub fn vec(u:u64, length:u64) -> Vec<u64> {
    let mut vec = vec![0 as u64; length as usize];
    let mut u = u.clone();
    for i in (0..vec.len()).rev() {
        if u%2 == 0 {
            vec[i] = 0 as u64;
        } else {
            vec[i] = 1 as u64;
        }
        u = u >> 1;
    }
    vec
}

// Checks if two vectors are equal
pub fn is_equal(a:&Vec<u64>, b:&Vec<u64>, width:u64) -> bool {
    for i in 0..width as usize {
        if a[i] != b[i] {
            return false;
        }
    }
    return true;
}

// Converts a String to a binary vector for encrypting
pub fn string_to_binary_vec(s:String) -> Vec<u64> {
    let mut binary_string = String::from("");
    for character in s.into_bytes() {
        if character == 32 {
            binary_string += &format!("00{:b}", character);
        } else {
            binary_string += &format!("0{:b}", character);
        }
    }
    let mut binary_vector = Vec::new();
    for ch in binary_string.chars() {
        if ch == '1' {
            binary_vector.push(1);
        } else {
            binary_vector.push(0);
        }
    }
    binary_vector
}

// Converts a binary vector to a String for decrypting
pub fn binary_vec_to_string(v:&Vec<u64>) -> String {
    let mut vec_of_chars = Vec::new();
    let mut binary_string = String::from("");
    for i in 0..v.len() {
        if v[i] == 0 {
            binary_string += "0";
        } else {
            binary_string += "1";
        }
        if binary_string.len() == 8 {
            vec_of_chars.push(binary_string.clone());
            binary_string = String::from("");
        }
    }
    let mut w = Vec::new();
    for i in 0..vec_of_chars.len() {
        let bin = vec_of_chars[i].clone();
        w.push(isize::from_str_radix(&vec_of_chars[i].clone(), 2).unwrap() as u8);
    }
    while w[w.len()-1] == 0 {
        w.pop();
    }
    let mut w = &w[..];
    let st = String::from("");
    st
}

Cargo.toml

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

[dependencies]
rand = "0.8.5"
rand_distr = "0.4.3"