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
132
133
134
135
136
137
138
139
140
141
142
143
144
145

//! Defines the algorithms from the classic Blum, Kalai and Wasserman paper
use crate::oracle::query_bits_range;
use crate::oracle::*;
use fnv::FnvHashMap;
use m4ri_rust::friendly::BinVector;
use std::default::Default;
use std::ops;

/// The full BKW solving algorithm.
///
/// Does `a-1` applications of [`partition-reduce`] with `$b$` and solves via majority.
///
/// $k' = k - (a-1) * b$
/// $n' = n - (a-1)*2^b
/// $d' = delta^{2*(a-1)}$
pub fn bkw(mut oracle: LpnOracle, a: u32, b: u32) -> BinVector {
    bkw_reduce(&mut oracle, a, b);
    majority(oracle)
}

/// Reduces the LPN problem size using the reduction from Blum, Kalai and Wasserman.
pub fn partition_reduce(oracle: &mut LpnOracle, b: u32) {
    bkw_reduce(oracle, 2, b);
}

/// Performs the BKW reduction algorithm, see [`partition_reduce`] for public usage
fn bkw_reduce(oracle: &mut LpnOracle, a: u32, b: u32) {
    let k = oracle.k;
    assert!(a * b <= k, "a*b <= k");

    for i in 1..a {
        let num_samples = oracle.samples.len();
        println!("BKW iteration {}, {} samples left", i, num_samples);
        // Partition into V_j
        // max j:
        let maxj = 2usize.pow(b);
        let query_capacity = num_samples / maxj;

        let mut vector_partitions: Vec<Vec<&Sample>> = Vec::with_capacity(maxj);
        // using [v; n] clones and won't set capacity correctly.
        for _ in 0..maxj {
            vector_partitions.push(Vec::with_capacity(query_capacity));
        }
        let mut firsts: Vec<Option<&Sample>> = vec![None; maxj];

        let bitrange: ops::Range<usize> = ((k - (b * i)) as usize)..((k - (b * (i - 1))) as usize);
        let mut indexes = Vec::with_capacity(maxj);
        for (j, q) in oracle.samples.iter_mut().enumerate() {
            let idx = query_bits_range(&(q.a), &bitrange) as usize;
            q.a.truncate((k - (b * i)) as usize);
            if let Some(first) = firsts[idx] {
                q.a += &first.a;
                q.c ^= first.c;
            } else {
                firsts[idx] = Some(q);
                indexes.push(j);
            }
        }
        indexes.into_iter().for_each(|idx| {
            oracle.samples.swap_remove(idx);
        });
    }

    // Set the new k
    oracle.k = k - (a - 1) * b;
    oracle.secret.truncate(oracle.k as usize);
    println!(
        "BKW iterations done, {} samples left, k' = {}",
        oracle.samples.len(),
        oracle.k
    );
}

/// Recover the secret using the majority strategy from BKW
pub fn majority(oracle: LpnOracle) -> BinVector {
    println!("BKW Solver: majority");
    let b = oracle.samples[0].a.len();
    debug_assert!(b <= 20, "Don't run BKW on too large b!");
    println!(
        "Selecting all samples with hw=1 from {} samples",
        oracle.samples.len()
    );
    let range = 0..(b);
    let samples = oracle
        .samples
        .into_iter()
        .filter(|q| q.count_ones() == 1)
        .map(|q| (query_bits_range(&q.a, &range), q.c))
        .collect::<Vec<(u64, bool)>>();

    // allocate smaller vec
    let mut counts: FnvHashMap<u64, u64> =
        FnvHashMap::with_capacity_and_hasher(b, Default::default());
    let mut sums: FnvHashMap<u64, u64> =
        FnvHashMap::with_capacity_and_hasher(b, Default::default());

    println!(
        "Sorting out and counting {} samples for majority selection",
        samples.len()
    );
    for query in samples.into_iter() {
        debug_assert_eq!(query.0.count_ones(), 1);
        let count = counts.entry(query.0).or_insert(0);
        *count += 1;
        if query.1 {
            let sum = sums.entry(query.0).or_insert(0);
            *sum += 1;
        }
    }

    let mut result = BinVector::with_capacity(b as usize);
    let mut i = 1 << (b - 1);
    while i > 0 {
        let count = counts.get(&i).expect("this bucket can't be empty!");
        if let Some(sum) = sums.get(&i) {
            result.push(*count < 2 * sum);
        } else {
            result.push(false);
        }
        i >>= 1;
    }
    result
}

#[cfg(test)]
mod test {
    use super::*;

    #[test]
    fn test_bkw() {
        let a = 4;
        let b = 8;

        let mut oracle: LpnOracle = LpnOracle::new(32, 1.0 / 32.0);
        oracle.get_samples(20_000);

        // get secret for checking
        let mut secret = oracle.secret.clone();
        secret.truncate((oracle.k - (a - 1) * b) as usize);

        // run bkw
        let solution = bkw(oracle, a, b);
        assert_eq!(solution, secret);
    }
}