General PVSS Scheme

[stanbar]

Hello @vincenthz, I've analysed your codebase and found it the best implementation of Special PVSS Scheme. I'm interested in extending your codebase to General PVSS Scheme from paper "A Simple Publicly Verifiable Secret Sharing Scheme and its Application to Electronic Voting". Is there any reason why you didn't implement it? Can you give me any suggestions ho two do it?

[vincenthz]

Thanks for the interests, but what are you looking for those 'General PVSS Schemes' ?

1. is just a XOR cipher using the output of the PVSS scheme (g^s) as the key through a hash function; While it's entertaining from a theoretical perspective, practically it's full of pet peeves, and it's much better to consider the PVSS output as a seed to an authenticated cipher (chacha20poly1305, aes-gcm), and have the actual secret using this symmetric cipher.
2. is just an elgamal encryption, it's got lot of limitations; if you need this, the current code allow you to build such a thing easily, but I don't think it has benefits to provide this scheme, as there's lots of variations of it to make it actually useful.

[stanbar]

@vincenthz thanks for your response.

I need the reconstructed secret to be a scalar as it's a share of another secret-sharing scheme.

Correct me if I'm wrong. As far as I understand, General PVSS Scheme enjoys the freedom of choosing the input secret $s$ and reconstruct also to the secret $s$. Whereas the Special PVSS Scheme allows choosing the secret scalar $s$, but reconstructing to a point $S=G^s$ and there is no way to get back the scalar $s$.

In other words, I need 1) the reconstructed secret to be a scalar, and 2) to be able to specify the secret.

This Rust implementation allows specifying the secret.

let secret_message = String::from("Hello MPVSS.");

let mut dealer = Participant::new();
let mut p1 = Participant::new();
let mut p2 = Participant::new();
let mut p3 = Participant::new();

// Dealer that shares the secret among p1, p2 and p3.
let distribute_shares_box = dealer.distribute_secret(
        &string_to_secret(&secret_message),
        &vec![p1.publickey, p2.publickey, p3.publickey],
        3,
    );

Again, as far as I understand it's the property of General PVSS Schemes.

[vincenthz]

The implementation you pointed above just does this on top of the 'special pvss scheme':

        // Reconstruct the secret = H(G^s) xor U
        let secret_hash = sha2::Sha256::digest(
            secret.to_biguint().unwrap().to_str_radix(10).as_bytes(),
        );
        let hash_big_uint = BigUint::from_bytes_be(&secret_hash[..])
            .mod_floor(&self.q.to_biguint().unwrap());
        let decrypted_secret =
            hash_big_uint ^ distribute_share_box.U.to_biguint().unwrap();
        Some(decrypted_secret.to_bigint().unwrap())

You're free to do the exact same thing, but this is quite a dangerous scheme as one can read here https://en.wikipedia.org/wiki/One-time_pad#Problems

Note that the above implementation is :

• highly inefficient, using 2048 bits DH fields (256 bytes elements)
• using a general big number scheme, so likely expose side-channel timing problem all the over place
• Doesn't check that the U is within the expected bounded, so if U is above 2048 bits, you do a silent partial 'encryption' of the content (some content is in the clear !)

A much better implementation would use something like an authenticated cipher, which would detect modification and able to cope with a secret of any size:

use ::pvss::crypto;
use cryptoxide::chacha20poly1305::ChaCha20Poly1305;
use cryptoxide::hashing::sha2::Sha256;
use pvss::simple as pvss;

fn create_ctx(point: &crypto::Point) -> ChaCha20Poly1305 {
    let out = Sha256::new().update(&point.to_bytes()).finalize();
    ChaCha20Poly1305::new(&out[0..16], &out[16..24], &[])
}

fn main() {
    let mut drg = crypto::Drg::new();
    let my_secret = "my secret";
    let my_secret_len = my_secret.as_bytes().len();

    /* run the PVSS */
    let p1 = crypto::create_keypair(&mut drg);
    let p2 = crypto::create_keypair(&mut drg);

    let pubs = [p1.0.clone(), p2.0.clone()];
    let e = pvss::escrow(&mut drg, 1);
    let shares = pvss::create_shares(&mut drg, &e, &pubs);

    /* create the box */
    let my_secret_box = {
        let mut tag = [0; 16];
        let mut my_secret_box = vec![0u8; my_secret_len + 16];

        let mut ctx = create_ctx(&e.secret);
        ctx.encrypt(
            my_secret.as_bytes(),
            &mut my_secret_box[0..my_secret_len],
            &mut tag,
        );
        my_secret_box[my_secret_len..].copy_from_slice(&tag);
        my_secret_box
    };

    /* recover the PVSS */
    let share = pvss::decrypt_share(&mut drg, &p1.1, &p1.0, &shares[0]);
    let recovered = pvss::recover(1, &[share]).unwrap();

    /* open the box */
    let my_secret_out = {
        let mut my_secret_out = vec![0; my_secret_len];
        let mut ctx = create_ctx(&recovered);
        if !ctx.decrypt(
            &my_secret_box[0..my_secret_len],
            &mut my_secret_out,
            &my_secret_box[my_secret_len..],
        ) {
            panic!("secret is not valid")
        };
        String::from_utf8(my_secret_out).expect("valid string")
    };

    assert_eq!(my_secret, my_secret_out);
    println!("{} {}", my_secret, my_secret_out);
}

some tweak on the above scheme would allow you to encode a biguint (serialized in bytes)

[stanbar]

Wow, thank you very much for such a detailed explanation! I'm afraid I can not use your scheme as it requires parties to recover the secret $G^s$ to decrypt the final secret $s$. I want the final secret to never be recovered by any single party, rather use it for a threshold ElGamal decryption (each party multiplies its share by ciphertext and publishes the output), the sum of the outputs (and Lagrange basis polynomials) gives a final plaintext.

The secret is recovered in MPC (hidden from any single party) and used as a share of a decryption key to the final ElGamal secret box only.

What you described doesn't allow for that as it uses "ChaCha20Poly1305" which is probably not MPC friendly. It is because parties can not compute the partial decryption using their own shares. I wonder if the same could be achieved with ElGamal, which allows for threshold/partial/MPC decryptions. Probably yes, however, the scheme gets quite complicated.

---

This is off-topic but just for your information I think that it may be easier to just construct a zkSNARK where

An arithmetic circuit which takes as inputs

• $f(x)$, a polynomial used to distribute secret share $s=f(0)$,
• $(x, y)$, a point on a polynomial $f$ which represents a share of a secret for party $x$,
• $C$, the encryption of a point on a polynomial $C=ElGamal(y, P)$, where $P$ an the receiver public key.

and output 1 if $y = f(x)$ and C is a valid ElGamal encryption of a point (x, y), and 0 otherwise.

To generate proof we use Public input consisting of

• $C$, ciphertext
• $P$, recipient public key
• $x$, recipient index

Private input consisting of

• $f(x)$, polynomial coefficients
• $y=f(x)$, share of the secret for party $x$

The verification takes public input and

• $\pi$, the proof
• $p$, recipient private key And validates that the output is a valid encryption of a point $(x,y)$ on a polynomial $f$.