labrador/ring/
rq_vector.rs

1//! Dynamic vector of `Rq` elements.
2
3use crate::ring::zq::Zq;
4use crate::ring::{rq::Rq, Norms};
5use core::ops::Mul;
6use rand::{CryptoRng, Rng};
7use std::ops::Add;
8
9/// Vector of polynomials in Rq
10#[derive(Debug, Clone, PartialEq, Eq)]
11pub struct RqVector {
12    elements: Vec<Rq>,
13}
14
15impl RqVector {
16    pub fn new(elements: Vec<Rq>) -> Self {
17        Self { elements }
18    }
19
20    /// Create a zero vector
21    pub fn zero(length: usize) -> Self {
22        Self {
23            elements: vec![Rq::zero(); length],
24        }
25    }
26
27    pub fn set(&mut self, index: usize, val: Rq) {
28        self.elements[index] = val;
29    }
30
31    pub fn len(&self) -> usize {
32        self.elements.len()
33    }
34
35    pub fn is_empty(&self) -> bool {
36        self.len() == 0
37    }
38
39    pub fn elements(&self) -> &Vec<Rq> {
40        &self.elements
41    }
42
43    pub fn from_zq_vector(elements: Vec<Zq>) -> Self {
44        assert!(
45            elements.len() % Rq::DEGREE == 0,
46            "slice length not multiple of DEGREE"
47        );
48        let mut result = Vec::new();
49        elements.chunks_exact(Rq::DEGREE).for_each(|chunk| {
50            result.push(Rq::new(chunk.try_into().unwrap()));
51        });
52        Self { elements: result }
53    }
54
55    /// Random vector of given length with coefficients in `(0, Zq::MAX)`.
56    pub fn random<R: Rng + CryptoRng>(rng: &mut R, length: usize) -> Self {
57        Self {
58            elements: (0..length).map(|_| Rq::random(rng)).collect(),
59        }
60    }
61
62    /// Random vector of given length with coefficients in `(-bound, bound)`.
63    pub fn random_with_bound<R: Rng + CryptoRng>(rng: &mut R, length: usize, bound: u32) -> Self {
64        Self {
65            elements: (0..length)
66                .map(|_| Rq::random_with_bound(rng, bound))
67                .collect(),
68        }
69    }
70
71    /// Flatten the coefficients of every polynomial **in order**.
72    pub fn concatenate_coefficients(&self) -> Vec<Zq> {
73        let mut concatenated_coeffs = Vec::with_capacity(self.len() * Rq::DEGREE);
74        // Iterate over each Rq, extracting the coefficients and concatenating them
75        for poly in &self.elements {
76            concatenated_coeffs.extend_from_slice(poly.coeffs());
77        }
78        concatenated_coeffs
79    }
80
81    /// Decompose the element to #num_parts number of parts,
82    /// where each part's infinity norm is less than or equal to bound/2
83    pub fn decompose(&self, b: Zq, parts: usize) -> Vec<RqVector> {
84        let mut result = vec![RqVector::zero(self.len()); parts];
85        self.elements()
86            .iter()
87            .enumerate()
88            .for_each(|(index, poly)| {
89                poly.decompose(b, parts)
90                    .into_iter()
91                    .zip(result.iter_mut())
92                    .for_each(|(decomposed_poly, decomposed_vec)| {
93                        decomposed_vec.set(index, decomposed_poly)
94                    });
95            });
96        result
97    }
98}
99
100impl Add<&RqVector> for &RqVector {
101    type Output = RqVector;
102    // add two poly vectors
103    fn add(self, other: &RqVector) -> RqVector {
104        self.elements()
105            .iter()
106            .zip(other.elements())
107            .map(|(a, b)| a + b)
108            .collect()
109    }
110}
111
112impl FromIterator<Rq> for RqVector {
113    fn from_iter<T: IntoIterator<Item = Rq>>(iter: T) -> Self {
114        let mut elements = Vec::new();
115        for item in iter {
116            elements.push(item);
117        }
118        RqVector::new(elements)
119    }
120}
121
122/// Create a new vector from a `Vec` of elements
123impl From<Vec<Rq>> for RqVector {
124    fn from(elements: Vec<Rq>) -> Self {
125        Self { elements }
126    }
127}
128
129impl Mul<&Rq> for &RqVector {
130    type Output = RqVector;
131    // A poly vector multiple by a PolyRing
132    fn mul(self, other: &Rq) -> RqVector {
133        self.elements().iter().map(|s| s * other).collect()
134    }
135}
136
137impl Mul<&Zq> for &RqVector {
138    type Output = RqVector;
139    // A poly vector multiple by a PolyRing
140    fn mul(self, other: &Zq) -> RqVector {
141        self.elements().iter().map(|s| s * other).collect()
142    }
143}
144
145impl Mul<Zq> for &RqVector {
146    type Output = RqVector;
147    // A poly vector multiple by a PolyRing
148    fn mul(self, other: Zq) -> RqVector {
149        self.elements().iter().map(|s| s * &other).collect()
150    }
151}
152
153impl Norms for RqVector {
154    type NormType = u128;
155
156    // Compute the squared l2 norm of a vector of polynomials
157    fn l2_norm_squared(&self) -> Self::NormType {
158        self.elements
159            .iter()
160            .map(|poly| poly.l2_norm_squared())
161            .sum()
162    }
163
164    fn linf_norm(&self) -> Self::NormType {
165        self.elements
166            .iter()
167            .map(|poly| poly.linf_norm())
168            .max()
169            .unwrap()
170    }
171}
172
173#[cfg(test)]
174mod tests {
175    use rand::rng;
176
177    use super::*;
178    use crate::{core::inner_product, ring::rq::tests::generate_rq_from_zq_vector};
179
180    #[test]
181    fn test_rqvector_from_iterator() {
182        let expected = vec![
183            Rq::random(&mut rng()),
184            Rq::random(&mut rng()),
185            Rq::random(&mut rng()),
186        ];
187        let vector_of_polynomials = expected.clone().into_iter();
188        let result: RqVector = vector_of_polynomials.collect();
189
190        assert_eq!(result.elements(), &expected);
191    }
192
193    #[test]
194    fn test_rq_vector_multiplication_with_zq() {
195        let poly1: Rq = generate_rq_from_zq_vector(vec![Zq::ONE, Zq::new(22)]);
196        let poly2: Rq = generate_rq_from_zq_vector(vec![Zq::new(17), Zq::new(12)]);
197        let rq_vector = RqVector::from(vec![poly1, poly2]);
198        let result = &rq_vector * Zq::new(3);
199
200        assert_eq!(
201            result.elements()[0],
202            generate_rq_from_zq_vector(vec![Zq::new(3), Zq::new(66)])
203        );
204        assert_eq!(
205            result.elements()[1],
206            generate_rq_from_zq_vector(vec![Zq::new(51), Zq::new(36)])
207        );
208
209        #[allow(clippy::op_ref)]
210        let result2 = &rq_vector * &Zq::new(3);
211        assert_eq!(
212            result2.elements()[0],
213            generate_rq_from_zq_vector(vec![Zq::new(3), Zq::new(66)])
214        );
215        assert_eq!(
216            result2.elements()[1],
217            generate_rq_from_zq_vector(vec![Zq::new(51), Zq::new(36)])
218        );
219    }
220
221    #[test]
222    fn test_rqvector_mul() {
223        let poly1: Rq = generate_rq_from_zq_vector(vec![Zq::ONE, Zq::new(2)]);
224        let poly2: Rq = generate_rq_from_zq_vector(vec![Zq::ONE, Zq::new(4)]);
225        let vec_1: RqVector = RqVector::from(vec![poly1]);
226        let vec_2: RqVector = RqVector::from(vec![poly2]);
227        let result = inner_product::compute_linear_combination(vec_1.elements(), vec_2.elements());
228        let poly_exp: Rq = generate_rq_from_zq_vector(vec![Zq::new(1), Zq::new(6), Zq::new(8)]);
229        assert_eq!(result, poly_exp);
230
231        let poly3: Rq = generate_rq_from_zq_vector(vec![Zq::ONE, Zq::ONE, Zq::ONE, Zq::ONE]);
232        let poly4: Rq = generate_rq_from_zq_vector(vec![Zq::ONE, Zq::ONE, Zq::ONE, Zq::ONE]);
233        let vec_3: RqVector = RqVector::from(vec![poly3]);
234        let vec_4: RqVector = RqVector::from(vec![poly4]);
235        let result_1 =
236            inner_product::compute_linear_combination(vec_3.elements(), vec_4.elements());
237        let poly_exp_1: Rq = generate_rq_from_zq_vector(vec![
238            Zq::new(1),
239            Zq::new(2),
240            Zq::new(3),
241            Zq::new(4),
242            Zq::new(3),
243            Zq::new(2),
244            Zq::new(1),
245        ]);
246        assert_eq!(result_1, poly_exp_1);
247
248        let poly5: Rq = generate_rq_from_zq_vector(vec![Zq::ONE, Zq::ONE, Zq::ONE, Zq::ONE]);
249        let poly6: Rq = generate_rq_from_zq_vector(vec![Zq::ONE, Zq::ONE, Zq::ONE, Zq::ONE]);
250        let poly7: Rq = generate_rq_from_zq_vector(vec![Zq::ONE, Zq::ONE, Zq::ONE, Zq::ONE]);
251        let poly8: Rq = generate_rq_from_zq_vector(vec![Zq::ONE, Zq::ONE, Zq::ONE, Zq::ONE]);
252        let vec_5: RqVector = RqVector::from(vec![poly5, poly6]);
253        let vec_6: RqVector = RqVector::from(vec![poly7, poly8]);
254        let result_2 =
255            inner_product::compute_linear_combination(vec_5.elements(), vec_6.elements());
256        let poly_exp_2: Rq = generate_rq_from_zq_vector(vec![
257            Zq::new(2),
258            Zq::new(4),
259            Zq::new(6),
260            Zq::new(8),
261            Zq::new(6),
262            Zq::new(4),
263            Zq::new(2),
264        ]);
265        assert_eq!(result_2, poly_exp_2);
266    }
267}
268
269#[cfg(test)]
270mod norm_tests {
271    use super::*;
272    use crate::ring::{rq::tests::generate_rq_from_zq_vector, Norms};
273
274    // Test the square of the norm
275    #[test]
276    fn test_l2_norm() {
277        let poly1 = generate_rq_from_zq_vector(vec![
278            Zq::ONE,
279            Zq::ZERO,
280            Zq::new(5),
281            Zq::NEG_ONE - Zq::new(1),
282        ]);
283        let poly2 = generate_rq_from_zq_vector(vec![Zq::ZERO, Zq::ZERO, Zq::new(5), Zq::ONE]);
284        let poly_vec1: RqVector = vec![poly1.clone(), poly2.clone()].into();
285        assert_eq!(
286            poly_vec1.l2_norm_squared(),
287            poly1.l2_norm_squared() + poly2.l2_norm_squared()
288        );
289
290        let zero_vec: RqVector = RqVector::zero(4);
291        assert_eq!(zero_vec.l2_norm_squared(), 0);
292    }
293
294    #[test]
295    fn test_linf_norm() {
296        let poly1 = generate_rq_from_zq_vector(vec![
297            Zq::ONE,
298            Zq::new(500),
299            Zq::new(5),
300            Zq::NEG_ONE - Zq::new(1000),
301        ]);
302        let poly2 =
303            generate_rq_from_zq_vector(vec![Zq::new(5), Zq::new(5), Zq::new(5000), Zq::new(5)]);
304        let poly_vec1: RqVector = vec![poly1.clone(), poly2.clone()].into();
305        assert_eq!(poly_vec1.linf_norm(), 5000);
306        let poly_vec2: RqVector = vec![poly2.clone(), poly1.clone()].into();
307        assert_eq!(poly_vec2.linf_norm(), 5000);
308
309        let zero_vec: RqVector = RqVector::zero(4);
310        assert_eq!(zero_vec.linf_norm(), 0);
311    }
312}
313
314#[cfg(test)]
315mod decomposition_tests {
316
317    use rand::rng;
318
319    use super::*;
320
321    fn default_base_and_parts() -> (Zq, usize) {
322        let base = Zq::new(2u32.pow(16));
323        let parts = 3; // 32 / 16 + (additional parts)
324        (base, parts)
325    }
326
327    #[test]
328    fn test_decomposition_number_of_parts() {
329        let rq_vector = RqVector::random(&mut rng(), 10);
330        let (base, parts) = default_base_and_parts();
331        let decomposed = rq_vector.decompose(base, parts);
332        assert_eq!(decomposed.len(), parts);
333    }
334
335    #[test]
336    fn test_decompositions_linf_norm() {
337        let rq_vector = RqVector::random(&mut rng(), 10);
338        let (base, parts) = default_base_and_parts();
339        let decomposed_vector = rq_vector.decompose(base, parts);
340
341        for decomposition in decomposed_vector {
342            assert!(
343                decomposition.linf_norm() <= base.div_floor_by(2).to_u128(),
344                "decomposition.linf_norm(): {} and base.div_floor_by(2): {}",
345                decomposition.linf_norm(),
346                base.div_floor_by(2)
347            );
348        }
349    }
350
351    #[test]
352    fn test_decompositions_computation_is_correct() {
353        let rq_vector = RqVector::random(&mut rng(), 10);
354        let (base, parts) = default_base_and_parts();
355        let decomposed_vector = rq_vector.decompose(base, parts);
356
357        let mut combined_vector = RqVector::zero(10);
358
359        let mut exponential_base = Zq::new(1);
360        for element in decomposed_vector {
361            combined_vector = &combined_vector + &(&element * exponential_base);
362            exponential_base *= base;
363        }
364
365        assert_eq!(combined_vector, rq_vector);
366    }
367}
labrador/ring/rq_vector.rs

labrador/ring/
rq_vector.rs
