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
use crate::oracle::query_bits_range;
use crate::oracle::*;
use fnv::FnvHashMap;
use m4ri_rust::friendly::BinVector;
use std::default::Default;
use std::ops;
pub fn bkw(mut oracle: LpnOracle, a: u32, b: u32) -> BinVector {
bkw_reduce(&mut oracle, a, b);
majority(oracle)
}
pub fn partition_reduce(oracle: &mut LpnOracle, b: u32) {
bkw_reduce(oracle, 2, b);
}
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);
let maxj = 2usize.pow(b);
let query_capacity = num_samples / maxj;
let mut vector_partitions: Vec<Vec<&Sample>> = Vec::with_capacity(maxj);
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);
});
}
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
);
}
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)>>();
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);
let mut secret = oracle.secret.clone();
secret.truncate((oracle.k - (a - 1) * b) as usize);
let solution = bkw(oracle, a, b);
assert_eq!(solution, secret);
}
}