simple_ring/
sampling.rs

1//Code for sampling of polynomials, and generation of coefficients
2use crate::{Polynomial, RingParams};
3use rand::{Rng, RngCore, rngs::OsRng};
4use std::ops::Deref;
5use shake::{Shake128};
6use shake::digest::{Update, ExtendableOutput, XofReader};
7
8pub enum SeedType {
9    NotGiven,
10    Given([u8; 32])
11}
12
13#[derive(Clone, Debug)]
14pub struct Sample(pub Vec<i32>);
15
16impl Deref for Sample {
17    type Target = Vec<i32>;
18
19    fn deref(&self) -> &Self::Target {
20        &self.0
21    }
22}
23
24impl Sample {
25    pub fn to_poly(self, q:u64) -> Polynomial {
26        let coeffs = self.iter().map(|v| (*v as i128).rem_euclid(q as i128) as u64).collect();
27        Polynomial::new(coeffs)
28    }
29}
30
31impl Polynomial {
32    pub fn random_binary(n: usize) -> Self {
33        let mut coeffs = vec![0u64; n];
34        for c in coeffs.iter_mut() {
35        *c = OsRng.next_u64() & 1;
36        }
37        Polynomial::new(coeffs)
38    }
39}
40
41#[inline]
42pub fn generate_cbd_sample(n: usize, eta: usize) -> Sample { //Inter function to create Centered Binomial Distribution
43
44    /*
45    This is how it works (on the left, explanations and on the right, example) :
46    For each coefficient, we randomly choose bits for two parts, a and b.           | a = [0, 1, 1, 1]           b = [1, 0, 1, 1]    
47    Then, we sum this coefficients for each part.                                   | a = 0 + 1 + 1 + 1 = 3      b = 1 + 0 + 1 + 1 = 3
48    Finally, the value of our coefficient is equal to a - b                         | coeff = a - b = 3 - 3 = 0
49    */
50
51    let mut coeffs = vec![0i32; n]; // So first we create an empty vector which will contain the coefficients.
52
53    let bits_per_coeff = eta; //Then we choose the number of bits for each part (a and b) -> if bit_number == 4, a and be will be the sum of 4 bits, like in the example
54
55    let total_bits = 2 * coeffs.len() * bits_per_coeff; 
56
57    let total_bytes = (total_bits + 7) / 8; 
58
59    let mut rng_buf = vec![0u8; total_bytes];
60
61    OsRng.fill_bytes(&mut rng_buf); //We generate a single vector of u8s of which we will choose the bits.
62    let mut bit_index = 0;
63    for coeff in coeffs.iter_mut() {
64        let mut a = 0;
65        let mut b = 0;
66
67        for _ in 0..bits_per_coeff { //Then we choose the bits in the sequence of bytes generated before. (for example : generated = [00001111; 10101010; ...], then we pick the bits one by one as first bit = 0, second one = 0...)
68            let byte = rng_buf[bit_index / 8];
69            let bit = (byte >> (bit_index % 8)) & 1; 
70            a += bit as u64;
71            bit_index += 1;
72        }
73
74        for _ in 0..bits_per_coeff { //We continue picking
75            let byte = rng_buf[bit_index / 8];
76            let bit = (byte >> (bit_index % 8)) & 1;
77            b += bit as u64;
78            bit_index += 1;
79        }
80
81        *coeff = a as i32 - b as i32; //And we finally do a - b
82    }
83    
84    Sample(coeffs)
85}
86
87
88#[inline]
89pub fn generate_small_sample(params: &RingParams) -> Sample { //Intern function that generates the small-coeffs sample
90    let mut rng = OsRng; 
91    let mut coeffs: Vec<i32> = Vec::with_capacity(params.n);
92    
93    for _ in 0..params.n {
94        let small: i32 = rng.gen_range(-1..=1); //We generate coeffs in the alphabet A = {-1, 0, 1}
95        coeffs.push(small);
96    }
97    
98    Sample(coeffs)
99}
100
101#[inline]
102pub fn generate_uniform_polynomial(params: &RingParams) -> Polynomial { //Intern function for generating a polynomial with uniform distribution, in the ring
103    let mut rng = OsRng;
104    let mut coeffs = Vec::with_capacity(params.n);
105
106    for _ in 0..params.n {
107        let uniform: u64 = rng.gen_range(0..=params.q - 1); // We generate values that are in the ring 
108        coeffs.push(uniform);
109    }
110
111    Polynomial { coeffs: coeffs.into_boxed_slice() }
112}
113
114#[inline]
115pub fn generate_then_shake(params: &RingParams, seed_type: SeedType) -> (Sample, [u8; 32]) {
116    let mut rng = OsRng;
117
118    match seed_type {
119        SeedType::Given(seed) => {
120            let buf = shake_128(seed, params.n);
121            let coeffs: Vec<i32> = buf
122                .into_iter()
123                .map(|b| (b as i32) - 128) 
124                .collect(); 
125            
126            return (Sample(coeffs), seed)
127        }
128        SeedType::NotGiven => {
129            let mut seed = [0u8; 32];
130            rng.fill_bytes(&mut seed);
131            let buf = shake_128(seed, params.n);
132            let coeffs: Vec<i32> = buf
133                .into_iter()
134                .map(|b| (b as i32) - 128) 
135                .collect(); 
136            
137            return (Sample(coeffs), seed)
138        }
139    }
140}
141
142pub fn shake_128(seed: [u8; 32], n: usize) -> Vec<u8> {
143    let mut hasher = Shake128::default();
144    hasher.update(&seed);
145    let mut reader = hasher.finalize_xof();
146
147    let mut buf = vec![0u8; n];
148    reader.read(&mut buf);
149    buf
150}
simple_ring/sampling.rs

simple_ring/
sampling.rs
