okvs 0.2.0

WIP implementation of Oblivious Key-Value Stores
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131

use rand::{thread_rng, Rng};

use crate::{bits::Bits, hashable::Hashable};

use super::Okvs;

const LOG_2_E: f64 = 1.4426950408889634073599246810018921374266459541529859341354494069;

/// A garbled Bloom filter with H hash functions proposed by Dong, Chen, and Wen. See https://eprint.iacr.org/2013/515.
pub struct GarbledBf<V: Bits> {
    bins: Vec<V>,
    hash_seeds: Vec<u64>,
}

impl<V: Bits> Okvs<V> for GarbledBf<V> {
    fn try_encode<K: Hashable>(key_value_pairs: &[(K, V)], lambda: usize) -> Option<Self> {
        // Choose parameters according to Dong et al.
        let hash_count = lambda;
        let bin_count = ((hash_count * key_value_pairs.len()) as f64 * LOG_2_E).ceil() as usize;

        let mut bins = vec![None; bin_count];
        let hash_seeds: Vec<u64> = (0..hash_count).map(|_| thread_rng().gen()).collect();

        // Try to encode the pairs in the bins
        for (key, value) in key_value_pairs {
            let mut empty_slot = None;
            let mut final_share = *value;

            for seed in &hash_seeds {
                let index = key.hash_to_index(*seed, bin_count);

                match bins[index] {
                    None => {
                        match empty_slot {
                            None => {
                                // Reserve this location for the final share
                                empty_slot = Some(index);
                            }
                            Some(slot) => {
                                // If this is the same slot as the empty slot, we need to retry
                                if index == slot {
                                    return None;
                                }

                                // Generate a new share
                                let random = V::random();
                                final_share ^= random;
                                bins[index] = Some(random);
                            }
                        }
                    }
                    Some(share) => {
                        // Reuse the share
                        final_share ^= share;
                    }
                }
            }

            // Store the final share
            match empty_slot {
                Some(slot) => bins[slot] = Some(final_share),
                None => return None, // Technically we can still go on if the final_share is 0, but the chance of this happening is small
            }
        }

        // Fill up any empty bins
        Some(Self {
            bins: bins
                .into_iter()
                .map(|bin| match bin {
                    Some(share) => share,
                    None => V::random(),
                })
                .collect(),
            hash_seeds,
        })
    }

    fn decode<K: Hashable>(&self, key: &K) -> V {
        let mut iterator = self
            .hash_seeds
            .iter()
            .map(|seed| self.bins[key.hash_to_index(*seed, self.bins.len())]);
        let mut result = iterator.next().unwrap();

        for share in iterator {
            result ^= share;
        }

        result
    }

    fn to_bytes(self) -> Vec<u8> {
        todo!()
    }

    fn from_bytes(_bytes: &[u8]) -> Self {
        todo!()
    }
}

#[cfg(test)]
mod tests {
    use super::GarbledBf;
    use crate::{bits::Bits, schemes::Okvs};

    #[test]
    fn encode_decode_u64() {
        let r1 = u64::random();
        let r2 = u64::random();
        let r3 = u64::random();

        let okvs = GarbledBf::encode(&[(1u64, r1), (1000u64, r2), (123u64, r3)], 40);

        assert_eq!(okvs.decode(&1u64), r1);
        assert_eq!(okvs.decode(&1000u64), r2);
        assert_eq!(okvs.decode(&123u64), r3);

        assert_ne!(okvs.decode(&0u64), r1);
        assert_ne!(okvs.decode(&0u64), r2);
        assert_ne!(okvs.decode(&0u64), r3);

        assert_ne!(okvs.decode(&2u64), r1);
        assert_ne!(okvs.decode(&2u64), r2);
        assert_ne!(okvs.decode(&2u64), r3);

        assert_ne!(okvs.decode(&u64::MAX), r1);
        assert_ne!(okvs.decode(&u64::MAX), r2);
        assert_ne!(okvs.decode(&u64::MAX), r3);
    }
}