FuzzyTags

匿名消息系统（及其他隐私保护应用）通常需要一个机制，让一方知道另一方已经给他们发送了消息（“通知”）。

许多方案依赖于带宽密集型的“下载所有内容并尝试解密”方法。其他方案则依赖于可信的第三方，或各种非勾结假设，以提供“私有”服务。其他方案要求各方将自己组织成“桶”或“邮箱”，实际上创建了“下载所有内容”方法的较小实例。

如果能让我们得到一个 不可信的、对抗性的 服务器为我们做这些工作，而不损害抗元数据特性或要求各方分成桶（实际上是将系统的匿名集分割成更小的部分）那就太棒了！

fuzzytags 就是为了实现这一目的而设计的实验性概率性加密标记结构！

与根据接收者将消息放入确定性桶不同，fuzzytags 允许每条消息除了对预期的接收者进行概率性地址外，还可以向其他几个参与者进行概率性地址 - 利用整个参与者集的匿名性，而不是在给定轮次中恰好共享一个桶的参与者。

具体来说，fuzzytags 提供以下特性

• 正确性：为特定标记密钥构建的有效标签在使用派生的检测密钥进行测试时始终有效。
• 模糊性：标签在与它们未针对的检测密钥进行测试时，将以概率 p 产生假阳性匹配，该概率与安全性属性 (γ) 相关。
• 安全性：具有访问检测密钥的对抗性服务器无法区分假阳性和真阳性。（这个特性被称为 检测模糊性）

安全性（龙在这里）

这个存储库提供了一个实验性的 FMD2 方案的实现，该方案在 "模糊消息检测" 中描述。使用 Ristretto 作为素数阶群。

此代码尚未经过任何重大审查。

此外，此系统提供的特性高度依赖于为您的系统选择一个 假阳性率 p 和 方案常数 γ。没有一种通用的方法。

如果 p 太低，则给定参与者的假阳性概率将非常高。

如果 p 太高，则对抗性服务器将能够以接近 1 的概率将消息链接到接收者。

同样，一个大的 γ 意味着更高的带宽成本，但一个小的 γ 会向服务器透露更多根密钥，同时也会增加所有各方之间完美（但错误）匹配的可能性。

我们还在构建一个模拟器，以了解在将模糊标签部署到实际系统中时，除了其他因素外，这些参数选择如何影响。

有关将模糊标签集成到隐私保护应用的更多指导（和警告），请参阅文档

构建

这个crate需要目前只有Rust nightly提供的实验性功能

rustup默认nightly

术语和更详细的系统描述

存在一种抵抗元数据的程序，它使用不可信的服务器来调解各方之间的通信。

每个参与者可以用一组加密标识符来识别，且系统内或系统外存在安全、真实地分发密钥的方法。

现在，我们不再要求每个参与者采取下载所有内容的元数据隐私方法（或调用非勾结或其他假设），我们可以利用模糊标签来减少每个参与者从服务器下载的消息数量，同时保持元数据隐私的正式概念。

每个参与者生成一个RootSecret，从中可以派生出DetectionKey和TaggingKey。这些密钥将与参数γ一起生成，该参数与2^-γ的最小误报概率相关。

当向服务器提交给特定recipient的消息时，sender将根据参与者的TaggingKey生成一个新的标签。

所有参与者将从他们的密钥对中extract一个DetectionKey。这个密钥的长度为n，提供0 <= 2^-n <= 2^-γ的误报检测概率。这个检测密钥可以被给一个敌对服务器。

当从敌对服务器获取新消息时，服务器首先对消息的标签进行test，以检测参与者的检测密钥。如果标签通过了测试，则将消息（包括标签）提供给recipient。

最后，recipient将运行自己的test，将标签与提取的检测密钥进行比较，这样误报的概率将是2^-n == 2^-γ。这将产生一个可能为recipient意图的子集消息，误报的概率较小。

或者，recipient可以直接尝试解密服务器提供的消息子集中的每条消息（取决于解密方法的效率）。

用法

一方首先需要生成RootSecret

use fuzzytags::RootSecret;
use rand::rngs::OsRng;
let mut rng = OsRng;
let secret = RootSecret::<24>::generate(&mut rng);

从秘密检测密钥中，一方可以派生出可以给敌对服务器以模糊检测标签的DetectionKey。

从秘密检测密钥中，一方还可以派生出可以公开的TaggingKey，可以给其他方，用于生成指向特定方的模糊标签。

上述代码中的24是该系统的一个安全属性（γ）。对于给定的gamma，为特定公钥生成的标签将与随机公钥验证，最大概率为2^-gamma。

生成标签

一旦获得一个标记密钥，一个在元数据抵抗型应用中的参与者可以使用它来生成标签

    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 public key to a another party...
    // and then they can do...
    let tag = tagging_key.generate_tag(&mut rng);

这些标签可以附加到一个元数据抵抗型系统中的消息上。

测试标签

首先，需要为给定的误报概率0 <= 2^-n <= 2^-γ提取一个检测密钥。

提取的密钥可以提供给对抗性服务器。然后服务器可以对给定的标签与检测密钥进行测试，例如：

    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 the 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.
    }

纠缠标签

启用 entangled 功能后，将可用 TaggingKey::generate_entangled_tag 函数。这允许您生成可验证的标签，这些标签可以对来自 不同 标签密钥的 多个 检测密钥进行验证，并开启了 多播 和 否认发送 等应用。

   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
    #[cfg(feature = "entangled")]
   let tag = TaggingKey::generate_entangled_tag(vec![tagging_key_1,tagging_key_2], &mut rng, 8);

序列化

该包依赖于 serde 进行序列化。FuzzyTags 首先被压缩成 64 字节加 γ 比特的字节数组，用零填充到最近的字节。这种表示可以用多种方式交换，例如：

use fuzzytags::RootSecret;
use fuzzytags::Tag;
use rand::rngs::OsRng;

let mut rng = OsRng;
let secret = RootSecret::<24>::generate(&mut rng);
let tagging_key = secret.tagging_key();

// Give public key to a another party...
// and then they can do...
let tag = tagging_key.generate_tag(&mut rng);

// An example using JSON serialization...see serde doc for other formats:
let serialized_tag = serde_json::to_string(&tag).unwrap();
println!("Serialized: {}", serialized_tag);

// We can then deserialize with:
let deserialized_tag: Result<Tag<24>, serde_json::Error> = serde_json::from_str(&serialized_tag);
println!("Deserialized: {}", deserialized_tag.unwrap());

基准测试

我们使用 criterion 进行基准测试，可以使用 cargo bench --bench fuzzy_tags_benches 运行基准测试

结果将在 target/criterion/report/index.html 中。

要基准测试纠缠标签，运行

cargobench --features "entangled" --benchentangled

AVX2

此包在 simd 功能下支持 avx2，要利用此功能，必须使用以下命令构建：RUSTFLAGS="-C target_feature=+avx2" 例如：

环境RUSTFLAGS="-C target_feature=+avx2"cargo test--发布--features"bulk_verify,entangled,simd"

这将在提供的基准测试中带来 40% 以上的性能提升。

致谢和贡献

• 基于 Gabrielle Beck 和 Julia Len 以及 Ian Miers 和 Matthew Green 的 Fuzzy Message Detection
• 性能和 API 改进由 Henry de Valence 贡献
• 通用标签错误由 Lee Bousfield 发现
• Fuzzytags 徽标由 Marcia Díaz Agudelo 设计
• 感谢 Henry de Valence、George Tankersly、Lee Bousfield 以及其他人的有益讨论。