Implementing Impagliazzo and Naor Hash Function

Purpose:

The purpose of this deliverable was to implement a component algorithm from [Dwork1997]. By working on this deliverable I gained an understanding of worse-to-average case reductions, the Short Integer Solution problem, dual lattices, and the subset sum problem.

Impagliazzo-Naor hash function implementation:

First I write a program to generate a random matrix which takes from the command line the number of vectors in the matrix and the variable c which sets the dimension. The vectors are represented as column vectors. To generate these vectors I use a random number generator which takes a new seed from the operating system. Each element of the matrix is a 1 or a 0. I use this program to write a random matrix to a text file.

The next program reads in a matrix from a file and and creates its own copy of the matrix. Then it calculates the height of this matrix and generates every possible vector of this height. It does this by counting in decimal from zero to this number and converting each number to a vector of the binary representation. It multiplies the random matrix by each of these possible inputs using a matrix multiplication method. The matrix multiplication method computes the dot product of the input and each row of the random matrix and outputs the hash value which is a vector of the same height. The program prints out a dictionary where the key is a number of occurences and the value is a list of hash values that occurred this many times.

Code: Impagliazzo-Naor hash function

To run:

cargo run --bin generate matrix 3 .1 > m1.txt
cargo run --bin hash m1.txt

Cargo.toml

[package]
name = "hash"
version = "0.1.0"
authors = ["Michaela Molina <michaela.molina@sjsu.edu>"]
edition = "2018"

[dependencies]
rand = "0.8.3"
rand_pcg = "0.3.0"
rand_core = "0.6.2"
getrandom = "0.2.2"
rand_chacha = "0.3.0"

[[bin]]
name = "hash"
path = "src/hash.rs"

[[bin]]
name = "generate_matrix"
path = "src/generate_matrix.rs"

generate_matrix.rs

// generate_matrix.rs
use rand::Rng;
use rand::SeedableRng;
use std::env;
use rand::prelude::*;
use rand_chacha::ChaCha20Rng;

fn main() {

    // get m and c from command line
    // default m = 5, c = 0.1
    let mut rng = ChaCha20Rng::from_entropy();
    let args: Vec<String> = env::args().collect();
    let mut m:u32 = match args.get(1) {
                        Some(st) => st.parse::<u32>().unwrap(),
                        None     => 5
                    };
    let mut c:f32 = match args.get(2) {
                        Some(st) => st.parse::<f32>().unwrap(),
                        None     => 0.1
                    };
    // lm is height of matrix
    let lm:f32 = (1 as f32 - c) * m as f32;

    // construct M = a_1...a_m where a_i in {0,1}^lm
    let lm = lm.floor();
    let mut M:Vec<Vec<u8>> = Vec::new();
    for i in 0..m {
        let mut a:Vec<u8> = Vec::new();
        for j in 0..lm as u32 {
            a.push(rng.gen_range(0..2));
        }
        M.push(a);
    }
    let mut st = get_matrix_string(&M);
    println!("{}", st);
}

pub fn get_matrix_string(M:&Vec<Vec<u8>>) -> String {
        let mut s = String::new();
        for (i, column) in M.iter().enumerate() {
            for (j, element) in column.iter().enumerate() {
                if j == column.len()-1 && i != M.len()-1 {
                    s.push_str(&format!("{}\n",element));
                } else {
                    s.push_str(&format!("{} ", element));                
                }
            }
        }
        s
}

hash.rs

use rand::Rng;
use std::env;
use std::fs::File;
use std::io::{BufRead, BufReader};
use std::collections::HashMap;

fn main() {
    let args: Vec<String> = env::args().collect();   
    let filename = match args.get(1) {
        Some(st) => String::from(st),
        None     => String::from("")
    };
    if (filename == "") {
        println!("Enter a filename");   
    } else {
        let mut M: Vec<Vec<u8>> = get_matrix_from_file(filename);
        let lm = get_height(&M);
        let base:u128 = 2;
        let mut hashes = vec![0; base.pow(lm as u32) as usize];
        let mut occurrences = HashMap::new();
        // get all vectors in {0,1}^M
        let vectors = get_all_possibilities(M.len() as u32);
        println!("M:");
        print_matrix_columns(&M);
        println!();
        for vector in &vectors {
            print!("For x = {}, ", get_vector_string(&vector));
            let product:Vec<Vec<u8>> = matrix_multiply(&M,&vec![vector.clone()]);
            let hash = mod_vector(&get_column(&product,0),2);  
            println!("Mx (mod 2) = {}", get_vector_string(&hash));
            let index = vector_to_decimal(&hash);
            hashes[index as usize] += 1;
        }
        for (hash, count) in hashes.iter().enumerate() {
            if !occurrences.contains_key(count) {
                let mut hash_array:Vec<u128> = Vec::new();
                hash_array.push(hash as u128);
                occurrences.insert(count, hash_array);
            } else {    
                let mut hash_array:Vec<u128> = occurrences[count].clone();
                hash_array.push(hash as u128);  
                occurrences.insert(count, hash_array);
            }
        }
        println!();
        for (count, hashes) in &occurrences {
            print!("{} times => ", count);
            for (i, hash) in hashes.iter().enumerate() {
                if (i != hashes.len()-1) {
                    print!("{}, ", hash);
                } else {
                    println!("{}", hash);
                }
            }
        }
        println!();
        //println!("Distribution Graph:");
        //print_hash_graph(&hashes, lm);
    }
}

fn print_hash_graph(hashes:&Vec<u8>, lm:u8) {
    for (index, count) in hashes.iter().enumerate() {
        let vector = decimal_to_vector(index as u8, lm);
        println!("index: {}, hash value: {} => {} times", index,get_vector_string(&vector), count);
    }
}

fn get_matrix_from_file(filename:String) -> Vec<Vec<u8>> {
    let file = File::open(filename).unwrap();
    let reader = BufReader::new(file);
    let mut M: Vec<Vec<u8>> = Vec::new();
    for (index, line) in reader.lines().enumerate() {
        let line = line.unwrap();
        let mut column: Vec<u8> = Vec::new();
        for c in line.chars() {
            if c.is_digit(2) {
                column.push(String::from(c).parse::<u8>().unwrap());
            }
        }
        M.push(column);
    }
    M
}

// get string representation of vector
fn get_vector_string(v:&Vec<u8>) -> String {
    let mut result = String::new();
    result.push_str("[");
    for (index, element) in v.iter().enumerate() {
        if (index == v.len()-1) {
            result.push_str(&format!("{}", element));
        } else {
            result.push_str(&format!("{},", element));
        }
    }
    result.push_str("]");
    result
}

// get all vectors in {0,1}^n
fn get_all_possibilities(n:u32) -> Vec<Vec<u8>> {
    let base: u128 = 2;
    let max:u128 = base.pow((n as u32));
    let mut vectors:Vec<Vec<u8>> = Vec::new();
    for i in 0..max {
        let mut vector:Vec<u8> = Vec::new();
        let mut binary = format!("{:b}", i);
        while binary.len() < n as usize{
            binary.insert(0,'0');
        }
        for c in binary.chars() {
                vector.push(String::from(c).parse::<u8>().unwrap());
        }
        vectors.push(vector);
    }
    vectors
}

fn vector_to_decimal(v:&Vec<u8>) -> u128 {
    let mut sum:u128 = 0;
    let base:u128 = 2;
    for (index, element) in v.iter().rev().enumerate() {
        if element.clone() == 1 {
            sum += base.pow(index as u32);
        }
    }
    sum
}

fn decimal_to_vector(d:u8, n:u8) -> Vec<u8> {
    let mut vector:Vec<u8> = Vec::new();
    let mut binary = format!("{:b}", d);
    while binary.len() < n as usize{
        binary.insert(0,'0');
    }
    for c in binary.chars() {
        vector.push(String::from(c).parse::<u8>().unwrap());
    }
    vector
}

fn mod_vector(v:&Vec<u8>, q:u8) -> Vec<u8> {
    let mut result:Vec<u8> = Vec::new();
    for element in v {
         result.push(element.clone() % q);
    }
    result
}

fn matrix_multiply(M1:&Vec<Vec<u8>>, M2:&Vec<Vec<u8>>) -> Vec<Vec<u8>> {
    let h = get_height(&M1);
    let w = M2.len();
    let mut result:Vec<Vec<u8>> = Vec::new();
    for j in 0..w {
        let mut result_column:Vec<u8> = Vec::new();
        let column = get_column(&M2, j);
        for i in 0..h {
            let row = get_row(&M1, i as usize);
            let dp = dot_product(&row, &column);
            result_column.push(dp);
        }
        result.push(result_column);
    }
    result
}

fn dot_product(v1:&Vec<u8>, v2:&Vec<u8>) -> u8 {
    let mut sum = 0;
    let it = v1.iter().zip(v2.iter());
    for (x,y) in it {
        sum += (x*y);
    }
    sum
}

fn get_row(M:&Vec<Vec<u8>>, row_number:usize) -> Vec<u8> {
    let mut row:Vec<u8> = Vec::new();
    for a in M {
        match a.get(row_number) {
                Some(element) => row.push(element.clone()),
                None => (),
        }
    }
    row
}


fn get_column(M:&Vec<Vec<u8>>, column_number:usize) -> Vec<u8> {
    let mut column:Vec<u8> = Vec::new();
    match M.get(column_number) {
        Some(a) => {
            for element in a {
                column.push(element.clone());
            }
        },
        None => (),
    }
    column
}

fn get_height(M:&Vec<Vec<u8>>) -> u8 {
    match M.get(0) {
        Some(a) => a.len() as u8,
        None => 0,
    }
}

pub fn print_matrix_columns(M:&Vec<Vec<u8>>) {
        let mut index:usize = 0;
        let mut c = 0;
        for column in M {
            print!("a{} ", c);
            c += 1;
        }
        println!();
        for column in M {
            print!("-- ");
        }
        println!();
        for i in 0..get_height(M) {
            for column in M {
                match column.get(index) {
                    Some(a) => print!("{}  ", a),
                    None    => ()
                }
            }
            println!();
            index += 1;
        }
}

Analysis: See CS297 Report.