ring_lwe/
lib.rs

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

ring_lwe/
lib.rs
