bench RSA vs Class group operations

[omershlo]

use https://github.com/KZen-networks/rust-paillier for Paillier or use a standard crypto library for RSA.

[0xmountaintop]

Following https://github.com/KZen-networks/class/blob/master/src/primitives/vdf.rs, I implement Wes19 using RSA group. And can try to open a PR.

/// Wes19(https://eprint.iacr.org/2018/623.pdf)-based Verifiable Delay Function (VDF) implementation,
/// adapted from https://github.com/KZen-networks/class/blob/master/src/primitives/vdf.rs
pub mod wes19 {
    use rug::Integer;
    use sha2::{Digest, Sha256};

    /// algo_2 from the paper
    pub fn verify(modulus: &Integer, seed: &Integer, t: u64, y: &Integer, pi: &Integer) -> bool {
        let modulus = modulus.clone();

        // g <- H_G(x)
        let g = h_g(&modulus, &seed);

        let l = hash_to_prime(&modulus, &g, &y);

        let r = Integer::from(2).pow_mod(&Integer::from(t), &l).unwrap();
        let pi_l = pi.clone().pow_mod(&l, &modulus).unwrap();
        let g_r = g.clone().pow_mod(&r, &modulus).unwrap();
        let pi_l_g_r = pi_l * g_r;

        Integer::from(pi_l_g_r.div_rem_floor(modulus.clone()).1) == y.clone()
    }

    /// algo_3 from the paper
    pub fn eval(modulus: &Integer, seed: &Integer, t: u64) -> (Integer, Integer) {
        let modulus = modulus.clone();

        // g <- H_G(x)
        let g = h_g(&modulus, &seed);

        // y <- (g^2)^t
        let mut y = g.clone();
        for _ in 0..t {
            y = y.clone() * y.clone();
            y = y.div_rem_floor(modulus.clone()).1;
        }

        let l = hash_to_prime(&modulus, &g, &y);

        // algo_4 from the paper, long division
        // TODO: consider algo_5 instead
        let mut b: Integer;
        let mut r = Integer::from(1);
        let mut r2: Integer;
        let two = Integer::from(2);
        let mut pi = Integer::from(1);

        for _ in 0..t {
            r2 = r.clone() * two.clone();
            b = r2.clone().div_rem_floor(l.clone()).0;
            r = r2.clone().div_rem_floor(l.clone()).1;
            let pi_2 = pi.clone().pow_mod(&Integer::from(2), &modulus).unwrap();
            let g_b = g.clone().pow_mod(&b, &modulus).unwrap();
            pi = pi_2 * g_b;
            pi = Integer::from(pi.div_rem_floor(modulus.clone()).1)
        }

        (y, pi)
    }

    /// int(H("residue"||x)) mod N
    fn h_g(modulus: &Integer, seed: &Integer) -> Integer {
        let modulus = modulus.clone();
        let mut hasher = Sha256::new();
        let mut hash_input = String::from("residue");
        hash_input.push_str(&seed.clone().to_string_radix(16));
        hasher.update(hash_input.as_bytes());
        let result_hex = hasher.finalize();
        let result_hex_str = format!("{:#x}", result_hex);
        let result_int = Integer::from_str_radix(&result_hex_str, 16).unwrap();
        Integer::from(result_int.div_rem_floor(modulus.clone()).1)
    }

    // TODO: refactor to similar style in https://github.com/poanetwork/vdf/blob/master/vdf/src/proof_wesolowski.rs style
    fn hash_to_prime(modulus: &Integer, x: &Integer, y: &Integer) -> Integer {
        // hashing
        let mut hasher = Sha256::new();
        let mut hash_input: String = x.clone().to_string_radix(16);
        hash_input.push_str(&y.clone().to_string_radix(16));
        hasher.update(hash_input.as_bytes());
        let hashed_hex = hasher.finalize();
        let hashed_hex_str = format!("{:#x}", hashed_hex);
        let hashed_int = Integer::from_str_radix(&hashed_hex_str, 16).unwrap();
        Integer::from(hashed_int.next_prime().div_rem_floor(modulus.clone()).1)
    }
}

[0xmountaintop]

And can try to open a PR.

Maybe after adding all alternatives using RSA group? And seems I need to add an option to make group choice configurable.

BTW, I am not sure whether my following choices suffice all the use cases

1. currently I use M13 prime as modulus
2. currently I use Sha256

[omershlo]

Very cool.

• RSA group should have a modulus N=p*q where p,q are 1024bit primes. The library supports generating such primes (see https://github.com/KZen-networks/class/blob/2a8fa3bb58a2c177ccb1a429887d680988580b68/src/primitives/cl_dl_public_setup.rs#L309) so it should be easy.

The hash (I assume you mean hash to group? )- its an interesting question, what other implementations are doing?

I suggest you start a benches folder, put the code there, build a test to compare the two VDFs and make a PR. Is that doable?

[0xmountaintop]

I suggest you start a benches folder, put the code there, build a test to compare the two VDFs and make a PR. Is that doable?

I was struggling on the code structures and how to support configurable types. You suggestion makes things easier. No problem! I will work on it.