Threshold Encryption

[afck]

Honey Badger requires threshold encryption to avoid sending the proposed transactions as plaintext. http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.119.1717&rep=rep1&type=pdf

[afck]

I'll also try to summarize this algorithm similar to #38. The assumptions and public data are the same as in #38, except that we need a different kind of hash functions:

fn hash_bytes(G1, len: usize) -> Vec<u8> produces a pseudorandom vector of length len, and fn hash_g(G1, &[u8]) -> G2 a group element. Finally, fn xor(&[u8], &[u8]) -> Vec<u8> computes the bitwise exclusive or of two slices of equal length. Let's pretend that the operator ^ is overloaded accordingly for slices and vectors.

Simple encryption scheme

Again, to generate a key pair, I pick a random sk: Zq, and publish pk: G1 = sk * g1.

To encrypt a message msg to me, you pick a random r: Zq and compute the ciphertext (u, v, w):

let u = r * g1;
let v = hash_bytes(r * pk, msg.len()) ^ msg;
let w = r * hash_g(u, v);

To check the message, anyone can verify that pair(g1, w) == pair(u, hash_g(u, v)); this defends against chosen-ciphertext attacks. What it proves is that the creator of the message actually knew the value r. (Otherwise an attacker could e.g. submit the same u with an all-zero v_fake and trick me into sending them the "decrypted" msg_fake. The real plaintext would then be msg_fake ^ v.)

To decrypt, I compute d_msg = hash_bytes(sk * u, v.len()) ^ v. That is equal to msg, because:

// Definition of `u`:
assert_eq!(d_msg, hash_bytes(sk * r * g1, v.len()) ^ v);
// Definition of `v`, commutativity of `*`:
assert_eq!(d_msg, hash_bytes(r * sk * g1, v.len()) ^ hash_bytes(r * pk, msg.len()) ^ msg);
// Definition of `pk`, and `v.len() == msg.len()`:
assert_eq!(d_msg, hash_bytes(r * pk, msg.len()) ^ hash_bytes(r * pk, msg.len())) ^ msg);
// `x ^ x ^ y == y`:
assert_eq!(d_msg, msg);

Threshold encryption scheme

Again, just like in #38, sk is a polynomial of degree t, party i for i in 1..=N (but not 0) receives sk[i], and all pk[i] = sk[i] * g1 are public. Encryption and verification work like in the simple case above.

To decrypt, party i publishes sku[i] = sk[i] * u. Everyone could detect if i cheated, because pair(g1, sku[i]) == pair(pk[i], u). Given a set of size t + 1 with valid sku[i], we can reconstruct sku[0] using Lagrange interpolation and complete the decryption as in the simple case above.