lpn 0.1.2

Software to study attacks on the Learning Parity with Noise problem
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
132
133

//! Describes the LPN problem oracle on which we apply reductions and solving algorithms
use m4ri_rust::friendly::*;
use rand;
use rand::distributions::{Bernoulli, Distribution};
use std::ops::Range;

use rayon::prelude::*;

/// Represents a sample in the oracle
///
/// `<a, s> + e = c`
#[derive(Debug, Clone, PartialEq)]
pub struct Sample {
    /// The vector of this sample
    pub a: BinVector,
    /// The noisy inner product
    pub c: bool,
    /// The noise bit
    pub e: bool,
}

impl Sample {
    /// Get the Hamming weight of the sample
    pub fn count_ones(&self) -> u32 {
        self.a.count_ones()
    }
}

/// This struct represents the oracle of the LPN problem.
///
/// We need to obtain the queries needed before applying reductions or transformations.
#[derive(Clone)]
pub struct LpnOracle {
    /// The samples held by this oracle.
    ///
    /// Can be obtained via `get_samples`
    pub samples: Vec<Sample>,
    /// The secret of this problem
    pub secret: BinVector,
    /// The size of this problem
    pub k: u32,
    /// The bias of this problem
    pub delta: f64,
    /// The bias of the secret
    pub delta_s: f64,
    /// The transformation matrix used by the sparse secret reduction
    pub(crate) sparse_transform_matrix: Option<BinMatrix>,
    /// The vector used by the sparse secret reduction
    pub(crate) sparse_transform_vector: Option<BinVector>,
}

impl LpnOracle {
    /// Create a new LPN problem with a random secret
    pub fn new(k: u32, tau: f64) -> LpnOracle {
        debug_assert!(0.0 <= tau && tau < 1.0, "0 <= tau < 1");
        debug_assert!(k > 0, "k > 0");
        let secret = BinVector::random(k as usize);
        println!("Constructed Oracle with k={}, τ={:0.5}", k, tau);

        LpnOracle {
            samples: vec![],
            secret,
            k,
            delta: 1f64 - 2f64 * tau,
            delta_s: 0f64, // uniformly random
            sparse_transform_matrix: None,
            sparse_transform_vector: None,
        }
    }

    /// Create a new LPN problem with a set secret
    pub fn new_with_secret(secret: BinVector, tau: f64) -> LpnOracle {
        let mut lpn = Self::new(secret.len() as u32, tau);
        lpn.secret = secret;
        lpn
    }

    /// Get new samples from the oracle
    ///
    /// These samples are stored in ``oracle.samples``
    ///
    /// Uses parallelism
    pub fn get_samples(&mut self, n: usize) {
        println!("Getting {} samples", n);
        self.samples.reserve(n);
        let k = self.k as usize;
        let len = if k % 8 == 0 { k / 8 } else { k / 8 + 1 };
        debug_assert!(len > 0);

        let tau = (1.0 - self.delta) / 2.0;
        let dist = Bernoulli::new(tau).unwrap();
        let secret = self.secret.clone();
        self.samples.par_extend((0..n).into_par_iter().map(|_| {
            let mut rng = rand::thread_rng();
            let vector = BinVector::random(k);
            debug_assert_eq!(vector.len(), k);
            let e = dist.sample(&mut rng);

            Sample {
                c: (&secret * &vector) ^ e,
                a: vector,
                e,
            }
        }));
    }
}

pub(crate) fn query_bits_range(v: &BinVector, range: &Range<usize>) -> u64 {
    // FIXME speed up
    let len = range.end - range.start;
    debug_assert!(len < 64, "Needs to fit in u64");
    let mut result = 0u64;
    for (i, ri) in (range.clone()).rev().enumerate() {
        result ^= (v[ri] as u64) << i;
    }
    debug_assert_eq!(result >> len, 0);
    result
}

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

    #[test]
    fn bitrange() {
        let v = BinVector::from_bytes(&[0b1001_1101u8]);
        assert_eq!(query_bits_range(&v, &(0..3)), 0b0000_0100);
        assert_eq!(query_bits_range(&v, &(2..4)), 0b0000_0001);
        assert_eq!(query_bits_range(&v, &(3..4)), 0b0000_0001);
        assert_eq!(query_bits_range(&v, &(3..5)), 0b0000_0011);
        assert_eq!(query_bits_range(&v, &(3..8)), 0b0001_1101);
    }
}