#![deny(missing_docs)]
#![feature(external_doc)]
#![feature(const_generics)]
#![doc(include = "../README.md")]
#![doc(include = "../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 rand::rngs::OsRng;
use serde::{de::Visitor, Deserialize, Deserializer, Serialize, Serializer};
use sha3::Sha3_512;
use std::convert::TryFrom;
use std::fmt;
use std::fmt::{Display, Formatter};
use std::ops::{Mul, Sub};
#[cfg(feature = "entangled")]
use brute_force::adaptors;
#[cfg(feature = "entangled")]
use brute_force::brute_force;
#[cfg(feature = "bulk_verify")]
use rayon::iter::IndexedParallelIterator;
#[cfg(feature = "bulk_verify")]
use rayon::iter::IntoParallelRefIterator;
#[cfg(feature = "bulk_verify")]
use rayon::iter::ParallelIterator;
#[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,
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+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, 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 fuzzytags::RootSecret;
/// let secret = RootSecret::<24>::generate();
/// 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();
/// 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.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};
/// let secret = RootSecret::<24>::generate();
/// 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();
/// 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 {
let (u_bytes, rest) = bytes.split_at(32);
let (y_bytes, ciphertext) = rest.split_at(32);
// 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)) {
(Some(u), Some(y)) => Some(Tag { u, y, 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.ciphertexts.to_bytes())
)
}
}
/// 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};
/// let secret = RootSecret::<24>::generate();
/// ```
pub fn generate() -> RootSecret<{ GAMMA }> {
let mut rng = OsRng::default();
let mut secret = vec![];
for _i in 0..GAMMA {
let sk_i = Scalar::random(&mut rng);
secret.push(sk_i);
}
RootSecret::<GAMMA> { secret: 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};
/// let secret = RootSecret::<24>::generate();
/// 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;
/// let secret = RootSecret::<24>::generate();
/// 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 }
}
/// 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(&[GAMMA]);
hash.update(u.compress().as_bytes());
hash.update(h.compress().as_bytes());
hash.update(w.compress().as_bytes());
return hash.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;
/// let secret = RootSecret::<24>::generate();
/// 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;
/// let secret = RootSecret::<24>::generate();
/// 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();
///
/// // 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 m = RootSecret::<GAMMA>::g(tag.u, &tag.ciphertexts);
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]);
// for each secret part...
let mut result = true;
for (i, x_i) in self.0.iter().enumerate() {
// re-derive the key from the tag
let k_i = RootSecret::<GAMMA>::h(tag.u, tag.u.mul(x_i), w);
// calculate the "original" plaintext
let c_i = match tag.ciphertexts.get(i) {
Some(true) => 0x01,
Some(false) => 0x00,
_ => 0x00,
// we've run out of ciphertext, it doesn't really matter what we put here, the rest of the test will fail
// since the security of k_i is modelled as a random oracle, (k_i ^ 0) should also be random
};
let b_i = k_i ^ c_i;
if b_i != 1 {
return false;
}
// assert that the plaintext is all 1's
result = result & (b_i == 1);
}
return result;
}
/// 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;
/// let secrets: Vec<RootSecret<24>> = (0..2).map(|_x| RootSecret::<24>::generate()).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, 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 m = RootSecret::<GAMMA>::g(tag.u, &tag.ciphertexts);
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();
// 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 = true;
for (i, x_i) in detection_key.0.iter().enumerate() {
// re-derive the key from the tag
let k_i = RootSecret::<GAMMA>::h(tag.u, tag.u.mul(x_i), w);
// calculate the "original" plaintext
let c_i = match tag.ciphertexts.get(i) {
Some(true) => 0x01,
Some(false) => 0x00,
_ => 0x00,
// we've run out of ciphertext, it doesn't really matter what we put here, the rest of the test will fail
// since the security of k_i is modelled as a random oracle, (k_i ^ 0) should also be random
};
let b_i = k_i ^ c_i;
if b_i != 1 {
result = false;
break;
}
// assert that the plaintext is all 1's
result = result & (b_i == 1);
}
if result {
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};
/// let secret = RootSecret::<24>::generate();
/// let tagging_key = secret.tagging_key(); // give this to a sender
/// let tag = tagging_key.generate_tag();
/// ```
pub fn generate_tag(&self) -> Tag<{ GAMMA }> {
let mut rng = OsRng::default();
let g = RISTRETTO_BASEPOINT_POINT;
// generate some random points...
let r = Scalar::random(&mut rng);
let u = g.mul(r);
let z = Scalar::random(&mut rng);
let w = g.mul(z);
// construct the ciphertext portion of the tag
let mut ciphertexts = BitVec::new();
for (_i, h_i) in self.0.iter().enumerate() {
let k_i = RootSecret::<GAMMA>::h(u, h_i.mul(r), w);
// 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 m = RootSecret::<GAMMA>::g(u, &ciphertexts);
let y = r.invert().mul(z.sub(m));
return Tag { u, y, 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};
/// let secret_1 = RootSecret::<24>::generate();
/// let secret_2 = RootSecret::<24>::generate();
/// 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], 8);
/// ```
pub fn generate_entangled_tag(tagging_keys: Vec<TaggingKey<{ GAMMA }>>, length: usize) -> Tag<{ GAMMA }> {
let mut rng = OsRng::default();
let g = RISTRETTO_BASEPOINT_POINT;
// generate some random points...
let r = Scalar::random(&mut 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);
}
let config = brute_force::Config::default();
let f = |z: &Scalar| {
let w = g.mul(z);
let mut key = vec![];
for (i, precompute) in tagging_key_precomputes[0].iter().enumerate() {
let k_i = RootSecret::<GAMMA>::h(u, *precompute, w);
if i < length {
for precompute in tagging_key_precomputes.iter().skip(1) {
let n_k_i = RootSecret::<GAMMA>::h(u, precompute[i], w);
if k_i != n_k_i {
return None;
}
}
key.push(k_i)
}
}
// 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 m = RootSecret::<GAMMA>::g(u, &ciphertexts);
let y = r.invert().mul(z.sub(m));
return Some(Tag { u, y, ciphertexts });
};
brute_force(config, adaptors::auto_advance(f))
}
}
#[cfg(test)]
mod tests {
use crate::{DetectionKey, RootSecret, Tag};
use bit_vec::BitVec;
use curve25519_dalek::ristretto::RistrettoPoint;
use curve25519_dalek::scalar::Scalar;
#[test]
fn test_compression() {
let secret = RootSecret::<24>::generate();
let tagging_key = secret.tagging_key();
// Give tagging key to a another party...
// and then they can do...
let tag = tagging_key.generate_tag();
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 secret = RootSecret::<15>::generate();
let tag = secret.tagging_key().generate_tag();
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();
let tag = secret.tagging_key().generate_tag();
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 secrets: Vec<RootSecret<24>> = (0..2).map(|_x| RootSecret::<24>::generate()).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, 16);
println!("{}", entangled_tag);
for secret in secrets.iter() {
let detection_key = secret.extract_detection_key(16);
assert!(detection_key.test_tag(&entangled_tag));
println!("{}", detection_key);
}
}
#[test]
#[cfg(feature = "bulk_verify")]
fn test_check_multiple() {
use crate::TaggingKey;
let secrets: Vec<RootSecret<24>> = (0..2).map(|_x| RootSecret::<24>::generate()).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, 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);
}
#[test]
fn correctness() {
let number_of_messages = 100;
let secret = RootSecret::<16>::generate();
for i in 0..number_of_messages {
let tag = secret.tagging_key().generate_tag();
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(),
ciphertexts: BitVec::from_elem(24, false),
};
tag
}
fn gen_zero_tag_one() -> Tag<24> {
let mut tag = Tag {
u: RistrettoPoint::default(),
y: Scalar::default(),
ciphertexts: BitVec::from_elem(24, false),
};
tag.ciphertexts.set_all();
tag
}
#[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 secret = RootSecret::<24>::generate();
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 number_of_messages = 1000;
let secret = RootSecret::<24>::generate();
let mut false_positives = 0;
for _i in 0..number_of_messages {
let secret2 = RootSecret::<24>::generate();
let tag = secret2.tagging_key().generate_tag();
assert!(secret2.extract_detection_key(3).test_tag(&tag));
if secret.extract_detection_key(3).test_tag(&tag) == true {
false_positives += 1;
}
}
println!(
"Expected False Positive Rate: {}\nActual False Positive Rate: {}",
secret.extract_detection_key(3).false_positive_probability(),
(false_positives as f64 / number_of_messages as f64)
);
}
}