2021-01-30 02:24:27 +00:00
#![ deny(missing_docs) ]
#![ feature(external_doc) ]
#![ doc(include = " ../README.md " ) ]
2021-01-29 23:47:40 +00:00
use bit_vec ::BitVec ;
use curve25519_dalek ::constants ::RISTRETTO_BASEPOINT_POINT ;
use curve25519_dalek ::digest ::Digest ;
2021-01-29 21:52:34 +00:00
use curve25519_dalek ::ristretto ::RistrettoPoint ;
2021-01-29 23:47:40 +00:00
use curve25519_dalek ::scalar ::Scalar ;
2021-01-29 21:52:34 +00:00
use rand ::rngs ::OsRng ;
2021-01-30 10:15:08 +00:00
use serde ::Deserialize ;
use serde ::Serialize ;
2021-01-29 23:47:40 +00:00
use sha3 ::Sha3_512 ;
2021-01-29 21:52:34 +00:00
use std ::fmt ;
2021-01-29 23:47:40 +00:00
use std ::fmt ::{ Display , Formatter } ;
use std ::ops ::{ Add , Mul , Sub } ;
2021-01-29 21:52:34 +00:00
2021-01-30 19:33:30 +00:00
/// A tag is a probabilistic cryptographic structure. When constructed for a given `FuzzyPublicKey`
/// it will pass the `FuzzyDetectionKey::test` 100% of the time. For other public keys
2021-01-30 02:18:08 +00:00
/// it will pass the test with probability `gamma` related to the security parameter of the system.
/// This system provides the following security properties:
2021-01-30 02:47:49 +00:00
/// * Correctness: Valid tags constructed for a specific public 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)
2021-01-30 10:15:08 +00:00
#[ derive(Debug, Serialize, Deserialize) ]
2021-01-30 19:33:30 +00:00
pub struct FuzzyTag {
2021-01-29 21:52:34 +00:00
u : RistrettoPoint ,
y : Scalar ,
2021-01-29 23:47:40 +00:00
ciphertexts : BitVec ,
2021-01-29 21:52:34 +00:00
}
2021-01-30 10:15:08 +00:00
/// The complete secret key. Can't directly be used for testing. Instead you will need to generate
2021-01-30 19:33:30 +00:00
/// a FuzzyDetectionKey using extract
pub struct FuzzySecretKey ( Vec < Scalar > ) ;
2021-01-30 10:15:08 +00:00
2021-01-30 19:33:30 +00:00
impl FuzzySecretKey {
2021-01-30 10:15:08 +00:00
/// extract a detection key for a given false positive (p = 2^-n)
2021-01-30 19:33:30 +00:00
pub fn extract ( & self , n : usize ) -> FuzzyDetectionKey {
2021-01-30 10:15:08 +00:00
let parts = self . 0. iter ( ) . take ( n ) . cloned ( ) . collect ( ) ;
2021-01-30 19:33:30 +00:00
FuzzyDetectionKey { 0 : parts }
2021-01-30 10:15:08 +00:00
}
}
2021-01-30 19:33:30 +00:00
/// A collection of "secret" data that can be used to determine if a `FuzzyTag` was intended for
2021-01-30 09:49:18 +00:00
/// the derived public key with probability p
2021-01-30 10:15:08 +00:00
#[ derive(Debug, Serialize, Deserialize) ]
2021-01-30 19:33:30 +00:00
pub struct FuzzyDetectionKey ( Vec < Scalar > ) ;
2021-01-30 02:18:08 +00:00
2021-01-30 19:33:30 +00:00
impl FuzzyDetectionKey {
2021-01-30 02:18:08 +00:00
/// returns true if the tag was intended for this key
2021-01-30 19:33:30 +00:00
pub fn test_tag ( & self , tag : & FuzzyTag ) -> bool {
let m = FuzzyTagKeyPair ::g ( tag . u , & tag . ciphertexts ) ;
2021-01-30 02:18:08 +00:00
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
2021-01-30 07:09:02 +00:00
// See below for a full explanation as to the reason for this:
2021-01-30 02:18:08 +00:00
let w = g . mul ( m ) . add ( tag . u . mul ( tag . y ) ) ;
// for each secret key part...
2021-01-30 07:38:20 +00:00
let mut result = true ;
2021-01-30 02:18:08 +00:00
for ( i , x_i ) in self . 0. iter ( ) . enumerate ( ) {
// re-derive the key from the tag
2021-01-30 19:33:30 +00:00
let k_i = FuzzyTagKeyPair ::h ( tag . u , tag . u . mul ( x_i ) , w ) ;
2021-01-30 02:18:08 +00:00
// calculate the "original" plaintext
2021-01-30 08:23:46 +00:00
let c_i = match tag . ciphertexts . get ( i ) {
Some ( true ) = > 0x01 ,
Some ( false ) = > 0x00 ,
_ = > 0x00 ,
// we've run our 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
2021-01-30 02:18:08 +00:00
} ;
2021-01-30 07:38:20 +00:00
2021-01-30 02:18:08 +00:00
let b_i = k_i ^ c_i ;
2021-01-30 07:38:20 +00:00
// assert that the plaintext is all 1's
result = result & ( b_i = = 1 ) ;
2021-01-30 02:18:08 +00:00
}
2021-01-30 07:38:20 +00:00
return result ;
2021-01-30 02:18:08 +00:00
}
}
/// A public identity that others can create tags for.
2021-01-30 19:33:30 +00:00
pub struct FuzzyPublicKey ( Vec < RistrettoPoint > ) ;
2021-01-30 02:18:08 +00:00
2021-01-30 19:33:30 +00:00
impl FuzzyPublicKey {
2021-01-30 07:09:02 +00:00
/// generate a new tag for this public key
2021-01-30 19:33:30 +00:00
pub fn generate_tag ( & self ) -> FuzzyTag {
2021-01-30 02:18:08 +00:00
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 ( ) {
2021-01-30 19:33:30 +00:00
let k_i = FuzzyTagKeyPair ::h ( u , h_i . mul ( r ) , w ) ;
2021-01-30 07:38:20 +00:00
// encrypt a plaintext of all 1's
2021-01-30 02:18:08 +00:00
let c_i = k_i ^ 0x01 ;
ciphertexts . push ( c_i = = 0x01 ) ;
}
2021-01-30 07:09:02 +00:00
// 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.
2021-01-30 02:18:08 +00:00
// 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 secret key) in order to compute a collision (y,m) where m
// is a hash of the remaining components of the ciphertext"
2021-01-30 07:09:02 +00:00
// 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.
2021-01-30 02:18:08 +00:00
// finally calculate a `y` = 1/r * (z-m) which will be used to re-derive `w`
2021-01-30 19:33:30 +00:00
let m = FuzzyTagKeyPair ::g ( u , & ciphertexts ) ;
2021-01-30 02:18:08 +00:00
let y = r . invert ( ) . mul ( z . sub ( m ) ) ;
2021-01-30 19:33:30 +00:00
return FuzzyTag { u , y , ciphertexts } ;
2021-01-30 02:18:08 +00:00
}
}
2021-01-30 19:33:30 +00:00
impl Display for FuzzyTag {
2021-01-29 21:52:34 +00:00
fn fmt ( & self , f : & mut Formatter < '_ > ) -> fmt ::Result {
2021-01-29 23:47:40 +00:00
write! (
f ,
" {} {} {} " ,
hex ::encode ( self . u . compress ( ) . as_bytes ( ) ) ,
hex ::encode ( self . y . as_bytes ( ) ) ,
hex ::encode ( self . ciphertexts . to_bytes ( ) )
)
2021-01-29 21:52:34 +00:00
}
}
2021-01-30 02:18:08 +00:00
/// An identity keypair for generating and validating fuzzy meta tags.
2021-01-30 19:33:30 +00:00
pub struct FuzzyTagKeyPair {
2021-01-30 02:24:27 +00:00
/// 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)
2021-01-30 19:33:30 +00:00
pub secret_key : FuzzySecretKey ,
2021-01-30 02:24:27 +00:00
/// the public key - this can be given to people who you want to contact you
2021-01-30 19:33:30 +00:00
pub public_key : FuzzyPublicKey ,
2021-01-29 21:52:34 +00:00
}
2021-01-30 19:33:30 +00:00
impl FuzzyTagKeyPair {
2021-01-30 02:18:08 +00:00
/// Generate a new Key Pair given a security parameter `gamma`. Tags generated for a given
2021-01-30 19:33:30 +00:00
/// `FuzzyPublicKey::flag` will pass the `FuzzyDetectionKey::test` for other public
2021-01-30 02:18:08 +00:00
/// keys with probability $ 2 ^ -8 $
2021-01-30 19:33:30 +00:00
pub fn generate ( gamma : usize ) -> FuzzyTagKeyPair {
2021-01-29 21:52:34 +00:00
let mut rng = OsRng ::default ( ) ;
let g = RISTRETTO_BASEPOINT_POINT ;
let mut s_keys = vec! [ ] ;
let mut p_keys = vec! [ ] ;
for _i in 0 .. gamma {
let sk_i = Scalar ::random ( & mut rng ) ;
let pk_i = g . mul ( sk_i ) ;
s_keys . push ( sk_i ) ;
p_keys . push ( pk_i ) ;
}
2021-01-30 19:33:30 +00:00
FuzzyTagKeyPair {
secret_key : FuzzySecretKey { 0 : s_keys } ,
public_key : FuzzyPublicKey { 0 : p_keys } ,
2021-01-30 02:18:08 +00:00
}
2021-01-29 21:52:34 +00:00
}
2021-01-30 09:49:18 +00:00
/// extract a detection key for a given false positive (p = 2^-n)
2021-01-30 10:15:08 +00:00
/// a facade for an extraction of the encapsulated secret key
2021-01-30 19:33:30 +00:00
pub fn extract ( & self , n : usize ) -> FuzzyDetectionKey {
2021-01-30 10:15:08 +00:00
self . secret_key . extract ( n )
2021-01-30 09:49:18 +00:00
}
2021-01-30 02:18:08 +00:00
/// a hash function that takes 3 risretto points as a parameter and outputs 0 or 1.
2021-01-29 23:47:40 +00:00
fn h ( u : RistrettoPoint , h : RistrettoPoint , w : RistrettoPoint ) -> u8 {
let hash = sha3 ::Sha3_256 ::digest (
format! (
" {}{}{} " ,
hex ::encode ( u . compress ( ) . as_bytes ( ) ) ,
hex ::encode ( h . compress ( ) . as_bytes ( ) ) ,
hex ::encode ( w . compress ( ) . as_bytes ( ) )
)
. as_bytes ( ) ,
) ;
return hash . as_slice ( ) [ 0 ] & 0x01 ;
2021-01-29 21:52:34 +00:00
}
2021-01-30 02:18:08 +00:00
/// a hash function which takes a ristretto point and a vector of ciphertexts and ouputs a
/// ristretto scalar.
2021-01-29 21:52:34 +00:00
fn g ( u : RistrettoPoint , points : & BitVec ) -> Scalar {
Scalar ::hash_from_bytes ::< Sha3_512 > ( format! ( " {} {} " , hex ::encode ( u . compress ( ) . as_bytes ( ) ) , hex ::encode ( points . to_bytes ( ) ) ) . as_bytes ( ) )
}
}
#[ cfg(test) ]
mod tests {
2021-01-30 19:33:30 +00:00
use crate ::FuzzyTagKeyPair ;
2021-01-29 21:52:34 +00:00
2021-01-30 10:15:08 +00:00
#[ test ]
fn test_serialization ( ) {
2021-01-30 19:33:30 +00:00
let key = FuzzyTagKeyPair ::generate ( 24 ) ;
2021-01-30 10:15:08 +00:00
let tag = key . public_key . generate_tag ( ) ;
let detection_key = key . extract ( 10 ) ;
println! ( " {} " , serde_json ::to_string ( & tag ) . unwrap ( ) ) ;
println! ( " {} " , serde_json ::to_string ( & detection_key ) . unwrap ( ) ) ;
}
2021-01-29 21:52:34 +00:00
#[ test ]
fn correctness ( ) {
let number_of_messages = 100 ;
2021-01-30 19:33:30 +00:00
let key = FuzzyTagKeyPair ::generate ( 16 ) ;
2021-01-29 21:52:34 +00:00
for i in 0 .. number_of_messages {
2021-01-30 07:09:02 +00:00
let tag = key . public_key . generate_tag ( ) ;
2021-01-29 21:52:34 +00:00
println! ( " {} : {} " , i , tag ) ;
2021-01-30 09:53:44 +00:00
assert! ( key . extract ( 5 ) . test_tag ( & tag ) ) ;
2021-01-29 21:52:34 +00:00
}
}
2021-01-30 08:23:46 +00:00
#[ test ]
fn false_postives ( ) {
2021-01-30 09:53:44 +00:00
let gamma = 8 ;
2021-01-29 23:47:40 +00:00
let number_of_messages = 1000 ;
2021-01-30 19:33:30 +00:00
let key = FuzzyTagKeyPair ::generate ( gamma ) ;
2021-01-29 23:47:40 +00:00
let mut false_positives = 0 ;
for _i in 0 .. number_of_messages {
2021-01-30 19:33:30 +00:00
let key2 = FuzzyTagKeyPair ::generate ( gamma ) ;
2021-01-30 07:09:02 +00:00
let tag = key2 . public_key . generate_tag ( ) ;
2021-01-30 09:53:44 +00:00
assert! ( key2 . extract ( 3 ) . test_tag ( & tag ) ) ;
2021-01-30 10:15:08 +00:00
if key . secret_key . extract ( 3 ) . test_tag ( & tag ) = = true {
2021-01-29 23:47:40 +00:00
false_positives + = 1 ;
}
}
println! (
" Expected False Positive Rate: {} \n Actual False Positive Rate: {} " ,
2021-01-30 09:53:44 +00:00
( 2.0_ f64 ) . powi ( - 3 ) ,
2021-01-29 23:47:40 +00:00
( false_positives as f64 / number_of_messages as f64 )
) ;
2021-01-29 21:52:34 +00:00
}
2021-01-29 23:47:40 +00:00
}