ring_lwe/
utils.rs

1use polynomial_ring::Polynomial;
2use rand_distr::{Uniform, Normal, Distribution};
3use ntt::polymul_ntt;
4use rand::SeedableRng;
5use rand::rngs::StdRng;
6use base64::{engine::general_purpose, Engine as _};
7use bincode;
8
9/// Ring-LWE parameters
10#[derive(Debug)]
11pub struct Parameters {
12    pub n: usize,       // Polynomial modulus degree
13    pub q: i64,       // Ciphertext modulus
14    pub t: i64,       // Plaintext modulus
15    pub omega: i64,   // n-th root of unity mod q
16    pub f: Polynomial<i64>, // Polynomial modulus (x^n + 1 representation)
17    #[allow(dead_code)]
18    pub sigma: f64,    // Standard deviation for normal distribution
19}
20
21/// Default parameters for ring-LWE
22impl Default for Parameters {
23    fn default() -> Self {
24        let n = 1024;
25        let q = 12289;
26        let t = 2;
27        let omega = ntt::omega(q, 2*n);
28        let mut poly_vec = vec![0i64;n+1];
29        poly_vec[0] = 1;
30        poly_vec[n] = 1;
31        let f = Polynomial::new(poly_vec);
32        let sigma = 8.0;
33        Parameters {n, q, t, omega, f, sigma}
34    }
35}
36
37/// Take remainder of the coefficients of a polynom by a given modulus
38/// # Arguments:
39/// * `x` - polynomial in Z[X]
40///	* `modulus` - coefficient modulus
41/// # Returns:
42/// polynomial in Z_modulus[X]
43pub fn mod_coeffs(x : Polynomial<i64>, modulus : i64) -> Polynomial<i64> {
44
45	let coeffs = x.coeffs();
46	let mut newcoeffs = vec![];
47	let mut c;
48	if coeffs.len() == 0 {
49		// return original input for the zero polynomial
50		x
51	} else {
52		for i in 0..coeffs.len() {
53			c = coeffs[i].rem_euclid(modulus);
54			if c > modulus/2 {
55				c = c-modulus;
56			}
57			newcoeffs.push(c);
58		}
59		Polynomial::new(newcoeffs)
60	}
61}
62
63/// Polynomial emainder of x modulo f assuming f=x^n+1
64/// # Arguments:
65/// * `x` - polynomial in Z[X]
66///	* `f` - polynomial modulus
67/// # Returns:
68/// polynomial in Z[X]/(f)
69pub fn polyrem(x: Polynomial<i64>, f: &Polynomial<i64>) -> Polynomial<i64> {
70	let n = f.coeffs().len()-1;
71	let mut coeffs = x.coeffs().to_vec();
72	if coeffs.len() < n+1 {
73		return Polynomial::new(coeffs)
74	} else{
75		for i in n..coeffs.len() {
76			coeffs[i % n] = coeffs[i % n]+(-1 as i64).pow((i/n).try_into().unwrap())*coeffs[i];
77		}
78		coeffs.resize(n,0);
79		Polynomial::new(coeffs)
80	}
81}
82
83/// Multiply two polynomials
84/// # Arguments:
85///	* `x` - polynomial to be multiplied
86/// * `y` - polynomial to be multiplied.
87/// * `modulus` - coefficient modulus.
88///	* `f` - polynomial modulus.
89/// # Returns:
90///	polynomial in Z_q[X]/(f)
91#[allow(dead_code)]
92pub fn polymul(x : &Polynomial<i64>, y : &Polynomial<i64>, q : i64, f : &Polynomial<i64>) -> Polynomial<i64> {
93	let mut r = x*y;
94    r = polyrem(r,f);
95    if q != 0 {
96        mod_coeffs(r, q)
97    }
98    else{
99        r
100    }
101}
102
103/// Multiply two polynomials using fast NTT algorithm
104/// # Arguments:
105///	* `x` - polynomial to be multiplied
106/// * `y` - polynomial to be multiplied.
107/// * `q` - coefficient modulus.
108///	* `f` - polynomial modulus.
109/// * `omega` - n-th root of unity
110/// # Returns:
111///	polynomial in Z_q[X]/(f)
112/// # Example:
113/// ```
114/// let p: i64 = 17; // Prime modulus
115/// let n: usize = 8;  // Length of the NTT (must be a power of 2)
116/// let omega = ntt::omega(p, n); // n-th root of unity
117/// let params = ring_lwe::utils::Parameters::default();
118/// let a = polynomial_ring::Polynomial::new(vec![1, 2, 3, 4]);
119/// let b = polynomial_ring::Polynomial::new(vec![5, 6, 7, 8]);
120/// let c_std = ring_lwe::utils::polymul(&a, &b, p, &params.f);
121/// let c_fast = ring_lwe::utils::polymul_fast(&a, &b, p, &params.f, omega);
122/// assert_eq!(c_std, c_fast, "test failed: {} != {}", c_std, c_fast);
123/// ```
124pub fn polymul_fast(
125    x: &Polynomial<i64>, 
126    y: &Polynomial<i64>, 
127    q: i64, 
128    f: &Polynomial<i64>, 
129    omega: i64
130) -> Polynomial<i64> {
131    let n1 = x.coeffs().len();
132    let n2 = y.coeffs().len();
133    // Compute the nearest power of 2 at least twice the max of input degrees+1
134    let n = 2*(std::cmp::max(n1, n2)).next_power_of_two();
135    // Pad coefficients
136    let x_pad = {
137        let mut coeffs = x.coeffs().to_vec();
138        coeffs.resize(n, 0);
139        coeffs
140    };
141    let y_pad = {
142        let mut coeffs = y.coeffs().to_vec();
143        coeffs.resize(n, 0);
144        coeffs
145    };
146
147    // Perform the polynomial multiplication
148    let r_coeffs = polymul_ntt(&x_pad, &y_pad, n, q, omega);
149
150    // Construct the result polynomial and reduce modulo f
151    let mut r = Polynomial::new(r_coeffs);
152    r = polyrem(r,f);
153    mod_coeffs(r, q)
154}
155
156
157/// Add two polynomials
158/// # Arguments:
159///	* `x` - polynomial to be added
160/// * `y` - polynomial to be added.
161/// * `modulus` - coefficient modulus.
162///	* `f` - polynomial modulus.
163/// # Returns:
164///	polynomial in Z_modulus[X]/(f)
165pub fn polyadd(x : &Polynomial<i64>, y : &Polynomial<i64>, modulus : i64, f : &Polynomial<i64>) -> Polynomial<i64> {
166	let mut r = x+y;
167    r = polyrem(r,f);
168    if modulus != 0 {
169        mod_coeffs(r, modulus)
170    }
171    else{
172        r
173    }
174}
175
176/// Additive inverse of a polynomial
177/// # Arguments:
178///	* `x` - polynomial to be inverted
179/// * `modulus` - coefficient modulus.
180/// # Returns:
181///	polynomial in Z_modulus[X]
182pub fn polyinv(x : &Polynomial<i64>, modulus: i64) -> Polynomial<i64> {
183    //Additive inverse of polynomial x modulo modulus
184    let y = -x;
185    if modulus != 0{
186      mod_coeffs(y, modulus)
187    }
188    else {
189      y
190    }
191  }
192
193/// Subtract two polynomials
194/// # Arguments:
195///	* `x` - polynomial to be subtracted
196/// * `y` - polynomial to be subtracted.
197/// * `modulus` - coefficient modulus.
198///	* `f` - polynomial modulus.
199/// # Returns:
200///	polynomial in Z_modulus[X]/(f)
201#[allow(dead_code)]
202pub fn polysub(x : &Polynomial<i64>, y : &Polynomial<i64>, modulus : i64, f : &Polynomial<i64>) -> Polynomial<i64> {
203	polyadd(x, &polyinv(y, modulus), modulus, f)
204}
205
206/// Generate a binary polynomial
207/// # Arguments:
208///	* `size` - number of coefficients
209/// * `seed` - random seed
210/// # Returns:
211///	polynomial in Z_modulus[X]/(f) with coefficients in {0,1}
212#[allow(dead_code)]
213pub fn gen_binary_poly(size : usize, seed: Option<u64>) -> Polynomial<i64> {
214	let between = Uniform::new(0,2);
215    let mut rng = match seed {
216        Some(seed) => StdRng::seed_from_u64(seed),
217        None => StdRng::from_entropy(),
218    };
219    let mut coeffs = vec![0i64;size];
220	for i in 0..size {
221		coeffs[i] = between.sample(&mut rng);
222	}
223	Polynomial::new(coeffs)
224}
225
226/// Generate a ternary polynomial
227/// # Arguments:
228///	* `size` - number of coefficients
229/// * `seed` - random seed
230/// # Returns:
231///	ternary polynomial with coefficients in {-1,0,+1}
232pub fn gen_ternary_poly(size : usize, seed: Option<u64>) -> Polynomial<i64> {
233	let between = Uniform::new(-1,2);
234    let mut rng = match seed {
235        Some(seed) => StdRng::seed_from_u64(seed),
236        None => StdRng::from_entropy(),
237    };
238    let mut coeffs = vec![0i64;size];
239	for i in 0..size {
240		coeffs[i] = between.sample(&mut rng);
241	}
242	Polynomial::new(coeffs)
243}
244
245/// Generate a uniform polynomial
246/// # Arguments:
247///	* `size` - number of coefficients
248/// * `q` - coefficient modulus
249/// * `seed` - random seed
250/// # Returns:
251///	uniform polynomial with coefficients in {0,1,...,q-1}
252pub fn gen_uniform_poly(size: usize, q: i64, seed: Option<u64>) -> Polynomial<i64> {
253	let between = Uniform::new(0,q);
254    let mut rng = match seed {
255        Some(seed) => StdRng::seed_from_u64(seed),
256        None => StdRng::from_entropy(),
257    };
258    let mut coeffs = vec![0i64;size];
259	for i in 0..size {
260		coeffs[i] = between.sample(&mut rng);
261	}
262	mod_coeffs(Polynomial::new(coeffs),q)
263}
264
265/// Generate a normal polynomial
266/// # Arguments:
267///	* `size` - number of coefficients
268/// * `sigma` - standard deviation
269/// * `seed` - random seed
270/// # Returns:
271///	polynomial with coefficients sampled from a normal distribution
272#[allow(dead_code)]
273pub fn gen_normal_poly(size: usize, sigma: f64, seed: Option<u64>) -> Polynomial<i64> {
274	let normal = Normal::new(0.0 as f64, sigma).unwrap();
275    let mut rng = match seed {
276        Some(seed) => StdRng::seed_from_u64(seed),
277        None => StdRng::from_entropy(),
278    };
279    let mut coeffs = vec![0i64;size];
280	for i in 0..size {
281		coeffs[i] = normal.sample(&mut rng).round() as i64;
282	}
283	Polynomial::new(coeffs)
284}
285
286/// nearest integer to the ratio a/b
287/// # Arguments:
288///	* `a` - numerator
289/// * `b` - denominator
290/// # Returns:
291///	nearest integer to the ratio a/b
292pub fn nearest_int(a: i64, b: i64) -> i64 {
293    if a > 0 {
294		(a + b / 2) / b
295	}else {
296		-((-a + b / 2) / b)
297	}
298}
299
300/// seralize and encode a vector of i64 to a base64 encoded string
301/// # Arguments
302/// * `data` - vector of i64
303/// # Returns
304/// * `encoded` - base64 encoded string
305pub fn compress(data: &Vec<i64>) -> String {
306    let serialized_data = bincode::serialize(data).expect("Failed to serialize data");
307    general_purpose::STANDARD.encode(&serialized_data)
308}
309
310/// decode and deserialize a base64 encoded string to a vector of i64
311/// # Arguments
312/// * `base64_str` - base64 encoded string
313/// # Returns
314/// * `decoded_data` - vector of i64
315pub fn decompress(base64_str: &str) -> Vec<i64> {
316    let decoded_bytes = general_purpose::STANDARD.decode(base64_str).expect("Failed to decode base64 string");
317    bincode::deserialize(&decoded_bytes).expect("Failed to deserialize data")
318}
ring_lwe/utils.rs

ring_lwe/
utils.rs
