fuzzytags/src/lib.rs

#![deny(missing_docs)]
#![doc = include_str!("../README.md")]
#![doc = include_str!("../ANONYMITY.md")]
#![doc(html_logo_url = "https://git.openprivacy.ca/openprivacy/fuzzytags/media/branch/trunk/FuzzyTags_Logo.png")]
use bit_vec::BitVec;
use curve25519_dalek::constants::RISTRETTO_BASEPOINT_POINT;
use curve25519_dalek::digest::Digest;
use curve25519_dalek::ristretto::{CompressedRistretto, RistrettoPoint};
use curve25519_dalek::scalar::Scalar;
use curve25519_dalek::traits::MultiscalarMul;
use serde::{de::Visitor, Deserialize, Deserializer, Serialize, Serializer};
use sha3::{Sha3_256, Sha3_512};
use std::convert::TryFrom;
use std::fmt;
use std::fmt::{Display, Formatter};
use std::ops::{Mul, Sub};

use rand::Rng;
use rand_core::{CryptoRng, RngCore};
#[cfg(feature = "bulk_verify")]
use rayon::iter::IndexedParallelIterator;
#[cfg(feature = "bulk_verify")]
use rayon::iter::IntoParallelRefIterator;
#[cfg(feature = "bulk_verify")]
use rayon::iter::ParallelIterator;
use std::borrow::BorrowMut;
#[cfg(feature = "bulk_verify")]
use std::sync::mpsc::channel;

/// A tag is a probabilistic cryptographic structure. When constructed for a given `TaggingKey`
/// it will pass the `DetectionKey::test_tag` 100% of the time. For other tagging keys
/// it will pass the test with probability `GAMMA` related to the security parameter of the system.
/// This system provides the following security properties:
/// * Correctness: Valid tags constructed for a specific tagging key will always validate when tested using the detection key
/// * Fuzziness: Invalid tags will produce false positives with probability _p_ related to the security property (_γ_)
/// * Security: An adversarial server with access to the detection key is unable to distinguish false positives from true positives. (Detection Ambiguity)
#[derive(Clone, Debug, Eq, PartialEq)]
pub struct Tag<const GAMMA: u8> {
    u: RistrettoPoint,
    y: Scalar,
    z: Vec<u8>,
    ciphertexts: BitVec,
}

impl<const GAMMA: u8> Serialize for Tag<{ GAMMA }> {
    fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
    where
        S: Serializer,
    {
        use serde::ser::SerializeTuple;
        let compressed = self.compress();
        let mut tup = serializer.serialize_tuple(compressed.len())?;
        for byte in compressed.iter() {
            tup.serialize_element(byte)?;
        }
        tup.end()
    }
}

impl<'de, const GAMMA: u8> Deserialize<'de> for Tag<{ GAMMA }> {
    fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
    where
        D: Deserializer<'de>,
    {
        struct FuzzyTagVisitor<const GAMMA: u8>;

        impl<'de, const GAMMA: u8> Visitor<'de> for FuzzyTagVisitor<{ GAMMA }> {
            type Value = Tag<{ GAMMA }>;

            fn expecting(&self, formatter: &mut ::core::fmt::Formatter) -> ::core::fmt::Result {
                formatter.write_str("64 bytes + GAMMA Bytes + GAMMA + bits of data")
            }

            fn visit_seq<A>(self, mut seq: A) -> Result<Tag<{ GAMMA }>, A::Error>
            where
                A: serde::de::SeqAccess<'de>,
            {
                let mut bytes = vec![];
                for i in 0..64 {
                    bytes.push(seq.next_element()?.ok_or(serde::de::Error::invalid_length(
                        i,
                        &"expected at least 64 bytes",
                    ))?);
                }
                loop {
                    match seq.next_element().unwrap_or(None) {
                        Some(x) => bytes.push(x),
                        _ => break,
                    }
                }

                Tag::<GAMMA>::decompress(&bytes).ok_or(serde::de::Error::custom("invalid fuzzytag"))
            }
        }

        // support up to GAMMA = 64
        deserializer.deserialize_tuple((72 + GAMMA) as usize, FuzzyTagVisitor::<GAMMA>)
    }
}

impl<const GAMMA: u8> Tag<{ GAMMA }> {
    /// An optimal sized copy of the tag
    /// Compressed u || y || ciphertext
    /// Ciphertext is right-padded with zeros to the nearest byte
    /// You probably want to use one of the many serde `serialize` apis instead (see README)
    /// ```
    ///    use rand::rngs::OsRng;
    ///    use fuzzytags::RootSecret;
    ///    let mut rng = OsRng;
    ///    let secret = RootSecret::<24>::generate(&mut rng);
    ///    let tagging_key = secret.tagging_key();
    ///    // extract a detection key
    ///    let detection_key = secret.extract_detection_key(5);
    ///
    ///    // Give tagging key to a another party...
    ///    // and then they can do...
    ///    let tag = tagging_key.generate_tag(&mut rng);
    ///    let compressed_tag = tag.compress();
    /// ```
    pub fn compress(&self) -> Vec<u8> {
        let mut bytes = vec![];
        bytes.extend_from_slice(self.u.compress().as_bytes());
        bytes.extend_from_slice(self.y.as_bytes());
        bytes.extend_from_slice(self.z.as_slice());
        bytes.extend_from_slice(self.ciphertexts.to_bytes().as_slice());
        bytes
    }

    /// decompress an optimally encoded fuzzytag byte array, returns None if invalid
    /// You probably want to use one of the many serde `deserialize` apis instead (see README)
    /// ```
    ///    use fuzzytags::{RootSecret, Tag};
    ///    use rand::rngs::OsRng;
    ///    let mut rng = OsRng;
    ///    let secret = RootSecret::<24>::generate(&mut rng);
    ///    let tagging_key = secret.tagging_key();
    ///    // extract a detection key
    ///    let detection_key = secret.extract_detection_key(5);
    ///
    ///    // Give tagging key to a another party...
    ///    // and then they can do...
    ///    let tag = tagging_key.generate_tag(&mut rng);
    ///    let compressed_tag = tag.compress();
    ///    let decompressed_tag = Tag::decompress(&compressed_tag).unwrap();
    ///    assert_eq!(tag, decompressed_tag);
    /// ```
    pub fn decompress(bytes: &[u8]) -> Option<Tag<{ GAMMA }>> {
        if bytes.len() > (64 + GAMMA as usize) {
            let (u_bytes, rest) = bytes.split_at(32);
            let (y_bytes, rest) = rest.split_at(32);
            let (z_bytes, ciphertext) = rest.split_at({ GAMMA } as usize);

            // if the ciphertext is too short, then this is an invalid tag
            let min_bytes = GAMMA / 8;
            if ciphertext.len() < min_bytes as usize {
                return None;
            }

            // This shouldn't actually fail, but for the safety...
            let y_bytes_fixed = match <[u8; 32]>::try_from(y_bytes) {
                Ok(fixed_size) => fixed_size,
                _ => return None,
            };

            let mut ciphertexts = BitVec::from_bytes(ciphertext);
            ciphertexts.truncate(GAMMA as usize);
            return match (
                CompressedRistretto::from_slice(u_bytes).decompress(),
                Scalar::from_canonical_bytes(y_bytes_fixed),
                z_bytes.to_vec(),
            ) {
                (Some(u), Some(y), z) => Some(Tag {
                    u,
                    y,
                    z: z,
                    ciphertexts,
                }),
                _ => None,
            };
        }
        None
    }
}

impl<const GAMMA: u8> Display for Tag<{ GAMMA }> {
    fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result {
        write!(
            f,
            "{} {} {} {}",
            hex::encode(self.u.compress().as_bytes()),
            hex::encode(self.y.as_bytes()),
            hex::encode(self.z.as_slice()),
            hex::encode(self.ciphertexts.to_bytes())
        )
    }
}

/// PrecomputeH is an encapsulation around the precomputation of the H function which
/// significantly speeds up testing. We define it for some additional type safety (to
/// prevent us from passing an uninitialized hash function to post_h
#[derive(Clone)]
struct PrecomputeH(Sha3_256);

/// The complete secret. Can't directly be used for testing. Instead you will need to generate
/// a DetectionKey using `extract_detection_key`
#[derive(Serialize, Deserialize)]
pub struct RootSecret<const GAMMA: u8> {
    /// the detection key - this can be given to adversarial servers to help probabilistically
    /// filter messages (with a false-positive rate derived from γ and a 0% false negative rate)
    secret: Vec<Scalar>,
}

impl<const GAMMA: u8> RootSecret<{ GAMMA }> {
    /// Generate a new Key Pair given a security parameter `GAMMA`. Tags generated for a given
    /// `TaggingKey::generate_tag` will pass the `DetectionKey::test_tag` for other tagging
    /// keys with probability $ 2 ^ -8 $
    /// Example:
    /// ```
    ///     use fuzzytags::{RootSecret};
    ///     use rand::rngs::OsRng;
    ///     let mut rng = OsRng;
    ///     let secret = RootSecret::<24>::generate(&mut rng);
    /// ```
    pub fn generate<R: RngCore + CryptoRng>(rng: &mut R) -> RootSecret<{ GAMMA }> {
        let mut secret = vec![];
        for _i in 0..GAMMA {
            let sk_i = Scalar::random(rng);
            secret.push(sk_i);
        }
        RootSecret::<GAMMA> { secret }
    }

    /// extract a detection key for a given false positive (p = 2^-n)
    /// This is the key that can be given to adversarail servers so that they can
    /// detected messages that *may* be tagged for a given detection key with an
    /// ideal false positive rate 2^{-n}
    /// Example:
    /// ```
    ///     use fuzzytags::{RootSecret};
    ///     use rand::rngs::OsRng;
    ///     let mut rng = OsRng;
    ///     let secret = RootSecret::<24>::generate(&mut rng);
    ///     let detection_key = secret.extract_detection_key(2);
    /// ```
    pub fn extract_detection_key(&self, n: usize) -> DetectionKey<{ GAMMA }> {
        let parts = self.secret.iter().take(n).cloned().collect();
        DetectionKey::<GAMMA> { 0: parts }
    }

    /// derive the tagging key for this secret
    /// Example:
    /// ```
    ///     use fuzzytags::RootSecret;
    ///     use rand::rngs::OsRng;
    ///     let mut rng = OsRng;
    ///     let secret = RootSecret::<24>::generate(&mut rng);
    ///     let tagging_key = secret.tagging_key();
    /// ```
    pub fn tagging_key(&self) -> TaggingKey<{ GAMMA }> {
        let g = RISTRETTO_BASEPOINT_POINT;
        let mut tagging_key = vec![];
        for sk_i in self.secret.iter() {
            let pk_i = g.mul(sk_i);
            tagging_key.push(pk_i);
        }
        TaggingKey::<GAMMA> { 0: tagging_key }
    }

    /// derive the tagging key for this secret
    /// Example:
    /// ```
    ///     use fuzzytags::RootSecret;
    ///     use rand::rngs::OsRng;
    ///     let mut rng = OsRng;
    ///     let secret = RootSecret::<24>::generate(&mut rng);
    ///     let anti_key = secret.anti_key();
    /// ```
    pub fn anti_key(&self) -> TaggingKey<{ GAMMA }> {
        let g = RISTRETTO_BASEPOINT_POINT;
        let mut tagging_key = vec![];
        for sk_i in self.secret.iter() {
            let pk_i = g.mul(sk_i.invert());
            tagging_key.push(pk_i);
        }
        TaggingKey::<GAMMA> { 0: tagging_key }
    }

    /// precompute the first part of h
    fn pre_h(u: RistrettoPoint, w: RistrettoPoint) -> PrecomputeH {
        let mut hash = sha3::Sha3_256::new();
        hash.update(&[GAMMA]);
        hash.update(u.compress().as_bytes());
        hash.update(w.compress().as_bytes());
        return PrecomputeH(hash);
    }

    fn nonce_h(mut hash: PrecomputeH, nonce: u8) -> PrecomputeH {
        hash.0.update(vec![nonce]);
        hash
    }

    /// compute the rest of h from a precomputed hash
    fn post_h(mut hash: PrecomputeH, h: RistrettoPoint) -> u8 {
        hash.0.update(h.compress().as_bytes());
        return hash.0.finalize().as_slice()[0] & 0x01;
    }

    /// a hash function which takes a ristretto point and a vector of ciphertexts and outputs a
    /// ristretto scalar.
    fn g(u: RistrettoPoint, points: &BitVec) -> Scalar {
        let mut input = vec![];
        input.push(GAMMA);
        input.extend_from_slice(points.to_bytes().as_slice());
        input.extend_from_slice(u.compress().as_bytes());
        Scalar::hash_from_bytes::<Sha3_512>(input.as_slice())
    }
}

/// A collection of "secret" data that can be used to determine if a `FuzzyTag` was intended for
/// the derived tagging key with probability p
#[derive(Clone, Debug, Serialize, Deserialize)]
pub struct DetectionKey<const GAMMA: u8>(Vec<Scalar>);

impl<const GAMMA: u8> DetectionKey<{ GAMMA }> {
    /// a convenient id for a detection key for internal accounting purposes
    /// do not expose this to applications
    pub fn id(&self) -> String {
        let mut hash = sha3::Sha3_256::new();
        for s in self.0.iter() {
            hash.update(s.as_bytes())
        }
        format!("{}", hex::encode(hash.finalize().as_slice()),)
    }
}

impl<const GAMMA: u8> Display for DetectionKey<{ GAMMA }> {
    fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result {
        write!(f, "{}", self.id())
    }
}

impl<const GAMMA: u8> DetectionKey<{ GAMMA }> {
    /// calculate the ideal false positive rate of this detection key
    /// ```
    ///    use fuzzytags::RootSecret;
    ///     use rand::rngs::OsRng;
    ///     let mut rng = OsRng;
    ///    let secret = RootSecret::<24>::generate(&mut rng);
    ///    let tagging_key = secret.tagging_key();
    ///    // extract a detection key
    ///    let detection_key = secret.extract_detection_key(5);
    ///    detection_key.false_positive_probability();
    /// ```
    pub fn false_positive_probability(&self) -> f64 {
        (2.0_f64).powi(0 - (self.0.len() as i32))
    }

    /// returns true if the tag was intended for this key
    /// Example:
    /// ```
    ///    use fuzzytags::RootSecret;
    ///    use rand::rngs::OsRng;
    ///    let mut rng = OsRng;
    ///    let secret = RootSecret::<24>::generate(&mut rng);
    ///    let tagging_key = secret.tagging_key();
    ///    // extract a detection key
    ///    let detection_key = secret.extract_detection_key(5);
    ///
    ///    // Give tagging key to a another party...
    ///    // and then they can do...
    ///    let tag = tagging_key.generate_tag(&mut rng);
    ///
    ///    // The server can now do this:
    ///    if detection_key.test_tag(&tag) {
    ///    // the message attached to this tag *might* be for the party associated with the detection key
    ///    } else {
    ///    // the message attached to this tag is definitely *not* for the party associated with the detection key.
    ///    }
    /// ```
    pub fn test_tag(&self, tag: &Tag<{ GAMMA }>) -> bool {
        // A few checks to make sure the tag is well formed.
        // All zeros in u or y can lead to a tag that validates against *all* tagging keys
        // That doesn't seem like a great idea, so we return false to be safe.
        // Zero values should never appear in well generated tags.
        if tag.u.eq(&RistrettoPoint::default()) || tag.y.eq(&Scalar::zero()) {
            return false;
        }

        let mut bitvec = BitVec::from_bytes(&*tag.z);
        bitvec.append(tag.ciphertexts.clone().borrow_mut());
        let m = RootSecret::<GAMMA>::g(tag.u, &bitvec);
        let g = RISTRETTO_BASEPOINT_POINT;

        // Re-derive w = g^z from the public tag.
        // y = (1/r) * (z-m)
        // u = g^r
        // so   w = g^m + u^y
        //      w = g^m + g^(r * 1/r * (z-m))
        //      w = g^m + g^(z-m)
        //      w = g^z
        // See below for a full explanation as to the reason for this:
        let w = RistrettoPoint::multiscalar_mul(&[m, tag.y], &[g, tag.u]);

        let pre_h = RootSecret::<GAMMA>::pre_h(tag.u, w);

        // for each secret part...
        let mut result = 0;
        for (nonce_i, (x_i, c_i)) in self.0.iter().zip(&tag.ciphertexts).enumerate() {
            // re-derive the key from the tag
            let nonce_h = RootSecret::<GAMMA>::nonce_h(pre_h.clone(), tag.z[nonce_i]);
            let k_i = RootSecret::<GAMMA>::post_h(nonce_h, tag.u.mul(x_i));

            // calculate the "original" plaintext
            let b_i = k_i ^ (c_i as u8);
            // short circuit
            if b_i != 0x01 {
                return false;
            }
            // assert that the plaintext is all 1's
            result += 1;
        }
        // Assert that number of sequential ones is equal to the length of the detection key
        // If it isn't it indicates that the tag ciphertext is shorter than the verification key,
        // Given the checks on deserialization that should never happen, but we throw in a check
        // here anyway for defense in depth.
        return result == self.0.len();
    }

    /// A bulk testing function that takes in an vector of detection keys and returns a vector
    /// of indexes where the tag matched. (Indexes not guarenteed to be ordered).
    /// This function may spin up additional threads depending on the number of detection
    /// keys provided.
    /// ```
    ///         use fuzzytags::{TaggingKey, DetectionKey};
    ///         use fuzzytags::RootSecret;
    ///         use rand::rngs::OsRng;
    ///         let mut rng = OsRng;
    ///         let secrets: Vec<RootSecret<24>> = (0..2).map(|_x| RootSecret::<24>::generate(&mut rng)).collect();
    ///         let tagging_keys: Vec<TaggingKey<24>> = secrets.iter().map(|x| x.tagging_key()).collect();
    ///         // it takes ~15 minutes on a standard desktop to find a length=24 match for 2 parties, so for testing let's keep things light
    ///         let entangled_tag = TaggingKey::generate_entangled_tag(tagging_keys,  &mut rng, 16);
    ///         let detection_keys = secrets.iter().map(|x| x.extract_detection_key(16)).collect();
    ///
    ///         let results = DetectionKey::test_tag_bulk(&detection_keys, &entangled_tag);
    ///         assert_eq!(results.len(), 2);
    /// ```
    #[cfg(feature = "bulk_verify")]
    pub fn test_tag_bulk(detection_keys: &Vec<DetectionKey<{ GAMMA }>>, tag: &Tag<{ GAMMA }>) -> Vec<usize> {
        // A few checks to make sure the tag is well formed.
        // All zeros in u or y can lead to a tag that validates against *all* tagging keys
        // That doesn't seem like a great idea, so we return false to be safe.
        // Zero values should never appear in well generated tags.
        if tag.u.eq(&RistrettoPoint::default()) || tag.y.eq(&Scalar::zero()) {
            return vec![];
        }

        let mut bitvec = BitVec::from_bytes(&*tag.z);
        bitvec.append(tag.ciphertexts.clone().borrow_mut());
        let m = RootSecret::<GAMMA>::g(tag.u, &bitvec);

        let g = RISTRETTO_BASEPOINT_POINT;

        // Re-derive w = g^z from the public tag.
        // y = (1/r) * (z-m)
        // u = g^r
        // so   w = g^m + u^y
        //      w = g^m + g^(r * 1/r * (z-m))
        //      w = g^m + g^(z-m)
        //      w = g^z
        // See below for a full explanation as to the reason for this:
        let w = RistrettoPoint::multiscalar_mul(&[m, tag.y], &[g, tag.u]);
        let (tx, rx) = channel();
        let pre_h = RootSecret::<GAMMA>::pre_h(tag.u, w);

        // for each secret part...
        let mut results: Vec<usize> = vec![];
        detection_keys
            .par_iter()
            .enumerate()
            .for_each_with(tx.clone(), |tx, (index, detection_key)| {
                let mut result = 0;
                for (nonce_i, (x_i, c_i)) in detection_key.0.iter().zip(&tag.ciphertexts).enumerate() {
                    // re-derive the key from the tag
                    let nonce_h = RootSecret::<GAMMA>::nonce_h(pre_h.clone(), tag.z[nonce_i]);
                    let k_i = RootSecret::<GAMMA>::post_h(nonce_h, tag.u.mul(x_i));

                    // calculate the "original" plaintext
                    let b_i = k_i ^ (c_i as u8);

                    if b_i != 1 {
                        break;
                    }
                    // assert that the plaintext is all 1's
                    result += 1;
                }
                if result == detection_key.0.len() {
                    match tx.send(index) {
                        _ => {
                            // TODO...surface this error...
                        }
                    }
                }
            });

        std::mem::drop(tx);
        loop {
            let result = rx.recv();
            match result {
                Ok(index) => results.push(index),
                _ => {
                    break;
                }
            }
        }

        return results;
    }
}

/// A public identity that others can create tags for.
#[derive(Clone, Debug, Serialize, Deserialize)]
pub struct TaggingKey<const GAMMA: u8>(Vec<RistrettoPoint>);

impl<const GAMMA: u8> TaggingKey<{ GAMMA }> {
    /// a convenient id for a tagging key for internal accounting purposes
    /// do not expose this to applications
    pub fn id(&self) -> String {
        let mut hash = sha3::Sha3_256::new();
        for s in self.0.iter() {
            hash.update(s.compress().as_bytes())
        }
        format!("{}", hex::encode(hash.finalize().as_slice()),)
    }

    /// generate a new tag for this tagging key
    /// Example:
    /// ```
    ///     use fuzzytags::{RootSecret};
    ///     use rand::rngs::OsRng;
    ///     let mut rng = OsRng;
    ///     let secret = RootSecret::<24>::generate(&mut rng);
    ///     let tagging_key = secret.tagging_key(); // give this to a sender
    ///     let tag = tagging_key.generate_tag(&mut rng);
    /// ```
    pub fn generate_tag<R: RngCore + CryptoRng>(&self, rng: &mut R) -> Tag<{ GAMMA }> {
        // generate some random points...
        let r = Scalar::random(rng);
        let u = RISTRETTO_BASEPOINT_POINT.mul(r);

        let z = Scalar::random(rng);
        let w = RISTRETTO_BASEPOINT_POINT.mul(z);

        // precompute the first part of the `H` hash function
        let pre_h = RootSecret::<GAMMA>::pre_h(u, w);

        // construct the ciphertext portion of the tag
        let mut ciphertexts = BitVec::with_capacity(GAMMA.into());

        let mut nonces = vec![];
        for _i in 0..GAMMA {
            nonces.push(rng.gen())
        }

        for (nonce_i, h_i) in self.0.iter().enumerate() {
            let nonce_h = RootSecret::<GAMMA>::nonce_h(pre_h.clone(), nonces[nonce_i]);
            let k_i = RootSecret::<GAMMA>::post_h(nonce_h, h_i.mul(r));
            // encrypt a plaintext of all 1's
            let c_i = k_i ^ 0x01;
            ciphertexts.push(c_i == 0x01);
        }

        // Without this next part, this scheme would not be CCA-secure. Consider a scheme with just
        // u = ^r and and h_i^r = g^(x_i*r)
        // An adversarial server with access to a Test oracle (i.e. the decryption key) may be able
        // to maul a challenge ciphertext by e.g. replacing the order of the ciphertexts.

        // From the paper:
        // "The value w corresponds to a chameleon hash [KR00] computed on the message (0,z), where z is chosen at random.
        // Once the ciphertext has been computed, we use a master trapdoor for the chameleon hash (which is part of the scheme’s DetectionKey) in order to compute a collision (y,m) where m
        // is a hash of the remaining components of the ciphertext"

        // Translated, m is a challenge over the random element u and the ordered ciphertexts
        // It is then used to construct a response y which can be used to recover w the random element
        // used to derive the key.

        // finally calculate a `y` = 1/r * (z-m) which will be used to re-derive `w`
        let mut bitvec = BitVec::from_bytes(&*nonces);
        bitvec.append(ciphertexts.clone().borrow_mut());
        let m = RootSecret::<GAMMA>::g(u, &bitvec);
        let y = r.invert().mul(z.sub(m));

        return Tag {
            u,
            y,
            z: nonces,
            ciphertexts,
        };
    }

    #[cfg(feature = "entangled")]
    /// WARNING: if you pass in a large length into this function it will take a long time!
    /// This begins a very slow, but parallel, search for a tag that will validate of the given
    /// tagging keys up to a given false positive rate 2^-l
    /// Example:
    /// ```
    ///     use fuzzytags::{RootSecret, TaggingKey};
    ///     use rand::rngs::OsRng;
    ///     let mut rng = OsRng;
    ///     let secret_1 = RootSecret::<24>::generate(&mut rng);
    ///     let secret_2 = RootSecret::<24>::generate(&mut rng);
    ///     let tagging_key_1 = secret_1.tagging_key(); // give this to a sender
    ///     let tagging_key_2 = secret_2.tagging_key(); // give this to a sender
    ///     // Will validate for detection keys derived from both secret_1 and secret_2 up
    ///     // to n=8
    ///     // Sender can now do...tag will validate on detection keys of length 8 or lower.
    ///     let tag = TaggingKey::generate_entangled_tag(vec![tagging_key_1,tagging_key_2], &mut rng, 8);
    /// ```
    pub fn generate_entangled_tag<R: RngCore + CryptoRng>(tagging_keys: Vec<TaggingKey<{ GAMMA }>>, rng: &mut R, length: usize) -> Tag<{ GAMMA }> {
        let g = RISTRETTO_BASEPOINT_POINT;
        // generate some random points...
        let r = Scalar::random(rng);
        let u = g.mul(r);

        // Compute and cache some public points that we will be using over and over again
        let mut tagging_key_precomputes = vec![];
        for tagging_key in tagging_keys.iter() {
            let mut precompute = vec![];
            for i in tagging_key.0.iter() {
                precompute.push(i.mul(r));
            }
            tagging_key_precomputes.push(precompute);
        }

        // generate some random points...

        loop {
            let z = Scalar::random(rng);
            let w = g.mul(z);
            let pre_h = RootSecret::<GAMMA>::pre_h(u, w);
            let mut key = vec![];

            let mut nonces = vec![];

            for (i, precompute) in tagging_key_precomputes[0].iter().enumerate() {
                for _nonce_attmepts in 0..=255 {
                    let nonce: u8 = rng.gen();
                    let mut success = true;
                    let nonce_h = RootSecret::<GAMMA>::nonce_h(pre_h.clone(), nonce);
                    let k_i = RootSecret::<GAMMA>::post_h(nonce_h.clone(), *precompute);

                    if i < length {
                        for precompute in tagging_key_precomputes.iter().skip(1) {
                            let n_k_i = RootSecret::<GAMMA>::post_h(nonce_h.clone(), precompute[i]);
                            if k_i != n_k_i {
                                success = false;
                                break;
                            }
                        }
                    }

                    if success {
                        nonces.push(nonce);
                        key.push(k_i);
                        break;
                    }
                }

                continue;
            }

            // generate the tag
            let mut ciphertexts = BitVec::new();
            for k_i in key.iter() {
                // encrypt a plaintext of all 1's
                let c_i = k_i ^ 0x01;
                ciphertexts.push(c_i == 0x01);
            }

            // This is the same as  generate_tag, kept separate to avoid over-decomposition
            let mut bitvec = BitVec::from_bytes(&*nonces);
            bitvec.append(ciphertexts.clone().borrow_mut());
            let m = RootSecret::<GAMMA>::g(u, &bitvec);
            let y = r.invert().mul(z.sub(m));
            return Tag {
                u,
                y,
                z: nonces,
                ciphertexts,
            };
        }
    }
}

#[cfg(test)]
mod tests {
    use crate::{DetectionKey, RootSecret, Tag};
    use bit_vec::BitVec;
    use curve25519_dalek::ristretto::RistrettoPoint;
    use curve25519_dalek::scalar::Scalar;
    use rand::rngs::OsRng;
    use sha3::Digest;

    #[test]
    fn test_compression() {
        let mut rng = OsRng;
        let secret = RootSecret::<24>::generate(&mut rng);
        let tagging_key = secret.tagging_key();

        // Give tagging key to a another party...
        // and then they can do...
        let tag = tagging_key.generate_tag(&mut rng);
        let compressed_tag = tag.compress();
        let decompressed_tag = Tag::<24>::decompress(&compressed_tag).unwrap();
        assert_eq!(tag, decompressed_tag);
    }

    #[test]
    fn test_serialization() {
        // generate some new keys...
        let mut rng = OsRng;
        let secret = RootSecret::<15>::generate(&mut rng);
        let tag = secret.tagging_key().generate_tag(&mut rng);
        let detection_key = secret.extract_detection_key(10);
        let serialized_tag = serde_json::to_string(&tag).unwrap();
        println!("{}", serialized_tag);
        let deserialized_tag: Tag<15> = serde_json::from_str(&serialized_tag).unwrap();
        assert_eq!(tag.compress(), deserialized_tag.compress());
        assert_eq!(true, detection_key.test_tag(&deserialized_tag));

        // generate some new keys...
        let secret = RootSecret::<24>::generate(&mut rng);
        let tag = secret.tagging_key().generate_tag(&mut rng);
        let detection_key = secret.extract_detection_key(10);
        let serialized_tag = serde_json::to_string(&tag).unwrap();
        let deserialized_tag: Tag<24> = serde_json::from_str(&serialized_tag).unwrap();
        assert_eq!(tag.compress(), deserialized_tag.compress());
        assert_eq!(true, detection_key.test_tag(&deserialized_tag));

        // Test some bincode...
        let bincode_tag = bincode::serialize(&tag);
        //  println!("Serialized: {:?}", bincode_tag);
        let deserialized_tag: Tag<24> = bincode::deserialize(&bincode_tag.unwrap()).unwrap();
        //println!("Deserialized: {}", deserialized_tag);
        //assert_eq!(tag.compress(), deserialized_tag.compress());
        assert_eq!(true, detection_key.test_tag(&deserialized_tag));
    }

    #[test]
    fn test_invalid_serializations() {
        let deserialized_tag: Option<Tag<24>> = serde_json::from_str("[0,1,2]").unwrap_or(None);
        assert_eq!(deserialized_tag, None);

        // too short (ciphertext)
        let deserialized_tag: Result<Tag<15>, serde_json::Error> = serde_json::from_str("[140,198,182,161,124,132,111,222,62,235,59,249,152,203,170,89,150,27,251,252,41,159,134,34,112,61,117,249,35,126,29,1,100,157,229,106,42,68,167,89,109,137,234,37,124,139,59,116,221,74,24,229,97,154,7,34,236,248,90,130,150,116,182,11]
");
        assert_eq!(deserialized_tag.is_ok(), false);

        // much too short
        let deserialized_tag: Option<Tag<15>> = serde_json::from_str("[140,198,182,161,124,132,111,222,62,235,59,249,152,203,170,89,150,27,251,252,41,159,134,34,112,61,117,249,35,126,29,1,100,157,229,106,42,68,167,89,109,137,234,37,124,139,59,116,221,74,24,229,97,154,7,34,236]
").unwrap_or(None);
        assert_eq!(deserialized_tag, None);
    }

    #[test]
    #[cfg(feature = "entangled")]
    fn test_multiple() {
        use crate::TaggingKey;
        let mut rng = OsRng;
        let secrets: Vec<RootSecret<24>> = (0..2)
            .map(|_x| RootSecret::<24>::generate(&mut rng))
            .collect();
        let tagging_keys: Vec<TaggingKey<24>> = secrets.iter().map(|x| x.tagging_key()).collect();

        // it takes ~2 minutes on a standard desktop to find a length=24 match for 2 parties, so for testing let's keep things light
        let len = 16;
        let entangled_tag = TaggingKey::generate_entangled_tag(tagging_keys, &mut rng, len);
        println!("entangled tag: {}", entangled_tag);
        for secret in secrets.iter() {
            let detection_key = secret.extract_detection_key(len);
            assert!(detection_key.test_tag(&entangled_tag));
            println!("{}", detection_key);
        }
    }

    #[test]
    #[cfg(feature = "bulk_verify")]
    fn test_check_multiple() {
        use crate::TaggingKey;
        let mut rng = OsRng;
        let secrets: Vec<RootSecret<24>> = (0..5)
            .map(|_x| RootSecret::<24>::generate(&mut rng))
            .collect();
        let tagging_keys: Vec<TaggingKey<24>> = secrets.iter().map(|x| x.tagging_key()).collect();
        // it takes ~2 minutes on a standard desktop to find a length=24 match for 2 parties, so for testing let's keep things light
        let entangled_tag = TaggingKey::generate_entangled_tag(tagging_keys, &mut rng, 24);
        let detection_keys = secrets
            .iter()
            .map(|x| x.extract_detection_key(16))
            .collect();

        let results = DetectionKey::test_tag_bulk(&detection_keys, &entangled_tag);
        assert_eq!(results.len(), 5);
    }

    #[test]
    fn correctness() {
        let number_of_messages = 100;
        let mut rng = OsRng;
        let secret = RootSecret::<24>::generate(&mut rng);
        for i in 0..number_of_messages {
            let tag = secret.tagging_key().generate_tag(&mut rng);
            println!("{}: {}", i, tag);
            assert!(secret.extract_detection_key(5).test_tag(&tag));
        }
    }

    fn gen_zero_tag_zero() -> Tag<24> {
        let tag = Tag {
            u: RistrettoPoint::default(),
            y: Scalar::default(),
            z: vec![],
            ciphertexts: BitVec::from_elem(24, false),
        };
        tag
    }

    fn gen_zero_tag_one() -> Tag<24> {
        let mut tag = Tag {
            u: RistrettoPoint::default(),
            y: Scalar::default(),
            z: vec![],
            ciphertexts: BitVec::from_elem(24, false),
        };
        tag.ciphertexts.set_all();
        tag
    }

    /// a hash function that takes 3 ristretto points as a parameter and outputs 0 or 1.
    fn h(u: RistrettoPoint, h: RistrettoPoint, w: RistrettoPoint) -> u8 {
        let mut hash = sha3::Sha3_256::new();
        hash.update(&[24]);
        hash.update(u.compress().as_bytes());
        hash.update(w.compress().as_bytes());
        hash.update(h.compress().as_bytes());
        return hash.finalize().as_slice()[0] & 0x01;
    }

    #[test]
    fn assert_h_and_pre_post_h() {
        let mut rng = OsRng;

        for _ in 0..100 {
            let a = RistrettoPoint::random(&mut rng);
            let b = RistrettoPoint::random(&mut rng);
            let c = RistrettoPoint::random(&mut rng);
            assert_eq!(
                RootSecret::<24>::post_h(RootSecret::<24>::pre_h(a, b), c),
                h(a, c, b)
            );
        }
    }

    #[test]
    // Thanks to Lee Bousfield who noticed an all zeros or all ones tag would
    // validate against a tagging key with 50% probability, allowing universal
    // broadcast, which overall seems like a bad idea...
    // Test to make sure that doesn't happen.
    fn test_zero_tag() {
        let mut rng = OsRng;
        let secret = RootSecret::<24>::generate(&mut rng);
        let tag = gen_zero_tag_zero();
        assert_eq!(false, secret.extract_detection_key(6).test_tag(&tag));
        let tag = gen_zero_tag_one();
        assert_eq!(false, secret.extract_detection_key(6).test_tag(&tag));
    }

    #[test]
    fn false_positives() {
        let mut rng = OsRng;
        let number_of_reference_checks = 100;
        let number_of_messages = 100;
        let limit = 1;
        let mut false_positives = 0;
        let total_attempts = number_of_reference_checks * number_of_messages;

        let secret = RootSecret::<24>::generate(&mut rng);
        for _i in 0..number_of_reference_checks {
            let secret = RootSecret::<24>::generate(&mut rng);
            for _i in 0..number_of_messages {
                let secret2 = RootSecret::<24>::generate(&mut rng);
                let tag = secret2.tagging_key().generate_tag(&mut rng);
                assert!(secret2.extract_detection_key(limit).test_tag(&tag));
                if secret.extract_detection_key(limit).test_tag(&tag) == true {
                    false_positives += 1;
                }
            }
        }
        println!(
            "Expected False Positive Rate: {}\nActual False Positive Rate: {}",
            secret
                .extract_detection_key(limit)
                .false_positive_probability(),
            (false_positives as f64 / (total_attempts) as f64)
        );
        assert!(
            secret
                .extract_detection_key(limit)
                .false_positive_probability()
                - (false_positives as f64 / (total_attempts) as f64)
                < 0.01
        );
    }
}