1use super::{traits::TryConvertFrom, Context, Poly, Representation};
4use crate::{
5 proto::rq::{Representation as RepresentationProto, Rq},
6 Error, Result,
7};
8use itertools::{izip, Itertools};
9use ndarray::{Array2, ArrayView, Axis};
10use num_bigint::BigUint;
11use std::borrow::Cow;
12use std::sync::Arc;
13use zeroize::{Zeroize, Zeroizing};
14
15impl From<&Poly> for Rq {
16 fn from(p: &Poly) -> Self {
17 assert!(!p.has_lazy_coefficients);
18
19 let needs_transform = p.representation != Representation::PowerBasis;
20 let q: Cow<'_, Poly> = if needs_transform {
21 let mut owned = p.clone();
22 owned.change_representation(Representation::PowerBasis);
23 Cow::Owned(owned)
24 } else {
25 Cow::Borrowed(p)
26 };
27
28 let mut proto = Rq::default();
29 match p.representation {
30 Representation::PowerBasis => {
31 proto.representation = RepresentationProto::Powerbasis as i32;
32 }
33 Representation::Ntt => {
34 proto.representation = RepresentationProto::Ntt as i32;
35 }
36 Representation::NttShoup => {
37 proto.representation = RepresentationProto::Nttshoup as i32;
38 }
39 }
40 let serialization: Vec<u8> = izip!(q.coefficients.outer_iter(), p.ctx.q.iter())
41 .flat_map(|(v, qi)| qi.serialize_vec(v.as_slice().unwrap()))
42 .collect();
43 proto.coefficients = serialization;
44 proto.degree = p.ctx.degree as u32;
45 proto.allow_variable_time = p.allow_variable_time_computations;
46 proto
47 }
48}
49
50impl TryConvertFrom<Vec<u64>> for Poly {
51 fn try_convert_from<R>(
52 mut v: Vec<u64>,
53 ctx: &Arc<Context>,
54 variable_time: bool,
55 representation: R,
56 ) -> Result<Self>
57 where
58 R: Into<Option<Representation>>,
59 {
60 let repr = representation.into();
61 match repr {
62 Some(Representation::Ntt) => {
63 if let Ok(coefficients) = Array2::from_shape_vec((ctx.q.len(), ctx.degree), v) {
64 Ok(Self {
65 ctx: ctx.clone(),
66 representation: repr.unwrap(),
67 allow_variable_time_computations: variable_time,
68 coefficients,
69 coefficients_shoup: None,
70 has_lazy_coefficients: false,
71 })
72 } else {
73 Err(Error::Default(
74 "In Ntt representation, all coefficients must be specified".to_string(),
75 ))
76 }
77 }
78 Some(Representation::NttShoup) => {
79 if let Ok(coefficients) = Array2::from_shape_vec((ctx.q.len(), ctx.degree), v) {
80 let mut p = Self {
81 ctx: ctx.clone(),
82 representation: repr.unwrap(),
83 allow_variable_time_computations: variable_time,
84 coefficients,
85 coefficients_shoup: None,
86 has_lazy_coefficients: false,
87 };
88 p.compute_coefficients_shoup();
89 Ok(p)
90 } else {
91 Err(Error::Default(
92 "In NttShoup representation, all coefficients must be specified"
93 .to_string(),
94 ))
95 }
96 }
97 Some(Representation::PowerBasis) => {
98 if v.len() == ctx.q.len() * ctx.degree {
99 let coefficients =
100 Array2::from_shape_vec((ctx.q.len(), ctx.degree), v).unwrap();
101 Ok(Self {
102 ctx: ctx.clone(),
103 representation: repr.unwrap(),
104 allow_variable_time_computations: variable_time,
105 coefficients,
106 coefficients_shoup: None,
107 has_lazy_coefficients: false,
108 })
109 } else if v.len() <= ctx.degree {
110 let mut out = Self::zero(ctx, repr.unwrap());
111 if variable_time {
112 unsafe {
113 izip!(out.coefficients.outer_iter_mut(), ctx.q.iter()).for_each(
114 |(mut w, qi)| {
115 let wi = w.as_slice_mut().unwrap();
116 wi[..v.len()].copy_from_slice(&v);
117 qi.reduce_vec_vt(wi);
118 },
119 );
120 out.allow_variable_time_computations();
121 }
122 } else {
123 izip!(out.coefficients.outer_iter_mut(), ctx.q.iter()).for_each(
124 |(mut w, qi)| {
125 let wi = w.as_slice_mut().unwrap();
126 wi[..v.len()].copy_from_slice(&v);
127 qi.reduce_vec(wi);
128 },
129 );
130 v.zeroize();
131 }
132 Ok(out)
133 } else {
134 Err(Error::Default("In PowerBasis representation, either all coefficients must be specified, or only coefficients up to the degree".to_string()))
135 }
136 }
137 None => Err(Error::Default(
138 "When converting from a vector, the representation needs to be specified"
139 .to_string(),
140 )),
141 }
142 }
143}
144
145impl TryConvertFrom<&Rq> for Poly {
146 fn try_convert_from<R>(
147 value: &Rq,
148 ctx: &Arc<Context>,
149 variable_time: bool,
150 representation: R,
151 ) -> Result<Self>
152 where
153 R: Into<Option<Representation>>,
154 {
155 let repr = value
156 .representation
157 .try_into()
158 .map_err(|_| Error::Default("Invalid representation".to_string()))?;
159 let representation_from_proto = match repr {
160 RepresentationProto::Powerbasis => Representation::PowerBasis,
161 RepresentationProto::Ntt => Representation::Ntt,
162 RepresentationProto::Nttshoup => Representation::NttShoup,
163 _ => return Err(Error::Default("Unknown representation".to_string())),
164 };
165
166 let variable_time = variable_time || value.allow_variable_time;
167
168 if let Some(r) = representation.into() as Option<Representation> {
169 if r != representation_from_proto {
170 return Err(Error::Default("The representation asked for does not match the representation in the serialization".to_string()));
171 }
172 }
173
174 let degree = value.degree as usize;
175 if degree % 8 != 0 || degree < 8 {
176 return Err(Error::Default("Invalid degree".to_string()));
177 }
178
179 let mut expected_nbytes = 0;
180 ctx.q
181 .iter()
182 .for_each(|qi| expected_nbytes += qi.serialization_length(degree));
183 if value.coefficients.len() != expected_nbytes {
184 return Err(Error::Default("Invalid coefficients".to_string()));
185 }
186
187 let mut index = 0;
188 let power_basis_coefficients: Vec<u64> = ctx
189 .q
190 .iter()
191 .flat_map(|qi| {
192 let size = qi.serialization_length(degree);
193 let v = qi.deserialize_vec(&value.coefficients[index..index + size]);
194 index += size;
195 v
196 })
197 .collect();
198
199 let mut p = Poly::try_convert_from(
200 power_basis_coefficients,
201 ctx,
202 variable_time,
203 Representation::PowerBasis,
204 )?;
205 p.change_representation(representation_from_proto);
206 Ok(p)
207 }
208}
209
210impl TryConvertFrom<Array2<u64>> for Poly {
211 fn try_convert_from<R>(
212 a: Array2<u64>,
213 ctx: &Arc<Context>,
214 variable_time: bool,
215 representation: R,
216 ) -> Result<Self>
217 where
218 R: Into<Option<Representation>>,
219 {
220 if a.shape() != [ctx.q.len(), ctx.degree] {
221 Err(Error::Default(
222 "The array of coefficient does not have the correct shape".to_string(),
223 ))
224 } else if let Some(repr) = representation.into() {
225 let mut p = Self {
226 ctx: ctx.clone(),
227 representation: repr,
228 allow_variable_time_computations: variable_time,
229 coefficients: a,
230 coefficients_shoup: None,
231 has_lazy_coefficients: false,
232 };
233 if p.representation == Representation::NttShoup {
234 p.compute_coefficients_shoup()
235 }
236 Ok(p)
237 } else {
238 Err(Error::Default("When converting from a 2-dimensional array, the representation needs to be specified".to_string()))
239 }
240 }
241}
242
243impl<'a> TryConvertFrom<&'a [u64]> for Poly {
244 fn try_convert_from<R>(
245 v: &'a [u64],
246 ctx: &Arc<Context>,
247 variable_time: bool,
248 representation: R,
249 ) -> Result<Self>
250 where
251 R: Into<Option<Representation>>,
252 {
253 Poly::try_convert_from(v.to_vec(), ctx, variable_time, representation)
254 }
255}
256
257impl<'a> TryConvertFrom<&'a [i64]> for Poly {
258 fn try_convert_from<R>(
259 v: &'a [i64],
260 ctx: &Arc<Context>,
261 variable_time: bool,
262 representation: R,
263 ) -> Result<Self>
264 where
265 R: Into<Option<Representation>>,
266 {
267 if representation.into() != Some(Representation::PowerBasis) {
268 Err(Error::Default(
269 "Converting signed integer require to import in PowerBasis representation"
270 .to_string(),
271 ))
272 } else if v.len() <= ctx.degree {
273 let mut out = Self::zero(ctx, Representation::PowerBasis);
274 if variable_time {
275 unsafe { out.allow_variable_time_computations() }
276 }
277 izip!(out.coefficients.outer_iter_mut(), ctx.q.iter()).for_each(|(mut w, qi)| {
278 let wi = w.as_slice_mut().unwrap();
279 if variable_time {
280 unsafe { wi[..v.len()].copy_from_slice(&qi.reduce_vec_i64_vt(v)) }
281 } else {
282 wi[..v.len()].copy_from_slice(Zeroizing::new(qi.reduce_vec_i64(v)).as_ref());
283 }
284 });
285 Ok(out)
286 } else {
287 Err(Error::Default("In PowerBasis representation with signed integers, only `degree` coefficients can be specified".to_string()))
288 }
289 }
290}
291
292impl<'a> TryConvertFrom<&'a Vec<i64>> for Poly {
293 fn try_convert_from<R>(
294 v: &'a Vec<i64>,
295 ctx: &Arc<Context>,
296 variable_time: bool,
297 representation: R,
298 ) -> Result<Self>
299 where
300 R: Into<Option<Representation>>,
301 {
302 Poly::try_convert_from(v.as_ref() as &[i64], ctx, variable_time, representation)
303 }
304}
305
306impl<'a> TryConvertFrom<&'a [BigUint]> for Poly {
307 fn try_convert_from<R>(
308 v: &'a [BigUint],
309 ctx: &Arc<Context>,
310 variable_time: bool,
311 representation: R,
312 ) -> Result<Self>
313 where
314 R: Into<Option<Representation>>,
315 {
316 let repr = representation.into();
317
318 if v.len() > ctx.degree {
319 Err(Error::Default(
320 "The slice contains too many big integers compared to the polynomial degree"
321 .to_string(),
322 ))
323 } else if repr.is_some() {
324 let mut coefficients = Array2::zeros((ctx.q.len(), ctx.degree));
325
326 izip!(coefficients.axis_iter_mut(Axis(1)), v).for_each(|(mut c, vi)| {
327 c.assign(&ArrayView::from(&ctx.rns.project(vi)));
328 });
329
330 let mut p = Self {
331 ctx: ctx.clone(),
332 representation: repr.unwrap(),
333 allow_variable_time_computations: variable_time,
334 coefficients,
335 coefficients_shoup: None,
336 has_lazy_coefficients: false,
337 };
338
339 match p.representation {
340 Representation::PowerBasis => Ok(p),
341 Representation::Ntt => Ok(p),
342 Representation::NttShoup => {
343 p.compute_coefficients_shoup();
344 Ok(p)
345 }
346 }
347 } else {
348 Err(Error::Default(
349 "When converting from a vector, the representation needs to be specified"
350 .to_string(),
351 ))
352 }
353 }
354}
355
356impl<'a> TryConvertFrom<&'a Vec<u64>> for Poly {
357 fn try_convert_from<R>(
358 v: &'a Vec<u64>,
359 ctx: &Arc<Context>,
360 variable_time: bool,
361 representation: R,
362 ) -> Result<Self>
363 where
364 R: Into<Option<Representation>>,
365 {
366 Poly::try_convert_from(v.to_vec(), ctx, variable_time, representation)
367 }
368}
369
370impl<'a, const N: usize> TryConvertFrom<&'a [u64; N]> for Poly {
371 fn try_convert_from<R>(
372 v: &'a [u64; N],
373 ctx: &Arc<Context>,
374 variable_time: bool,
375 representation: R,
376 ) -> Result<Self>
377 where
378 R: Into<Option<Representation>>,
379 {
380 Poly::try_convert_from(v.as_ref(), ctx, variable_time, representation)
381 }
382}
383
384impl<'a, const N: usize> TryConvertFrom<&'a [BigUint; N]> for Poly {
385 fn try_convert_from<R>(
386 v: &'a [BigUint; N],
387 ctx: &Arc<Context>,
388 variable_time: bool,
389 representation: R,
390 ) -> Result<Self>
391 where
392 R: Into<Option<Representation>>,
393 {
394 Poly::try_convert_from(v.as_ref(), ctx, variable_time, representation)
395 }
396}
397
398impl<'a, const N: usize> TryConvertFrom<&'a [i64; N]> for Poly {
399 fn try_convert_from<R>(
400 v: &'a [i64; N],
401 ctx: &Arc<Context>,
402 variable_time: bool,
403 representation: R,
404 ) -> Result<Self>
405 where
406 R: Into<Option<Representation>>,
407 {
408 Poly::try_convert_from(v.as_ref(), ctx, variable_time, representation)
409 }
410}
411
412impl From<&Poly> for Vec<u64> {
413 fn from(p: &Poly) -> Self {
414 p.coefficients.as_slice().unwrap().to_vec()
415 }
416}
417
418impl From<&Poly> for Vec<BigUint> {
419 fn from(p: &Poly) -> Self {
420 izip!(p.coefficients.axis_iter(Axis(1)))
421 .map(|c| p.ctx.rns.lift(c))
422 .collect_vec()
423 }
424}
425
426#[cfg(test)]
427mod tests {
428 use crate::{
429 proto::rq::Rq,
430 rq::{traits::TryConvertFrom, Context, Poly, Representation},
431 Error as CrateError,
432 };
433 use num_bigint::BigUint;
434 use rand::rng;
435 use std::{error::Error, sync::Arc};
436
437 static MODULI: &[u64; 3] = &[1153, 4611686018326724609, 4611686018309947393];
438
439 #[test]
440 fn proto() -> Result<(), Box<dyn Error>> {
441 let mut rng = rng();
442 for modulus in MODULI {
443 let ctx = Arc::new(Context::new(&[*modulus], 16)?);
444 let p = Poly::random(&ctx, Representation::PowerBasis, &mut rng);
445 let proto = Rq::from(&p);
446 assert_eq!(Poly::try_convert_from(&proto, &ctx, false, None)?, p);
447 assert_eq!(
448 Poly::try_convert_from(&proto, &ctx, false, Representation::PowerBasis)?,
449 p
450 );
451 assert_eq!(
452 Poly::try_convert_from(&proto, &ctx, false, Representation::Ntt)
453 .expect_err("Should fail because of mismatched representations"),
454 CrateError::Default("The representation asked for does not match the representation in the serialization".to_string())
455 );
456 assert_eq!(
457 Poly::try_convert_from(&proto, &ctx, false, Representation::NttShoup)
458 .expect_err("Should fail because of mismatched representations"),
459 CrateError::Default("The representation asked for does not match the representation in the serialization".to_string())
460 );
461 }
462
463 let ctx = Arc::new(Context::new(MODULI, 16)?);
464 let p = Poly::random(&ctx, Representation::PowerBasis, &mut rng);
465 let proto = Rq::from(&p);
466 assert_eq!(Poly::try_convert_from(&proto, &ctx, false, None)?, p);
467 assert_eq!(
468 Poly::try_convert_from(&proto, &ctx, false, Representation::PowerBasis)?,
469 p
470 );
471 assert_eq!(
472 Poly::try_convert_from(&proto, &ctx, false, Representation::Ntt)
473 .expect_err("Should fail because of mismatched representations"),
474 CrateError::Default("The representation asked for does not match the representation in the serialization".to_string())
475 );
476 assert_eq!(
477 Poly::try_convert_from(&proto, &ctx, false, Representation::NttShoup)
478 .expect_err("Should fail because of mismatched representations"),
479 CrateError::Default("The representation asked for does not match the representation in the serialization".to_string())
480 );
481
482 let ctx = Arc::new(Context::new(&MODULI[0..1], 16)?);
483 assert_eq!(
484 Poly::try_convert_from(&proto, &ctx, false, None)
485 .expect_err("Should fail because of incorrect context"),
486 CrateError::Default("Invalid coefficients".to_string())
487 );
488
489 Ok(())
490 }
491
492 #[test]
493 fn try_convert_from_slice_zero() -> Result<(), Box<dyn Error>> {
494 for modulus in MODULI {
495 let ctx = Arc::new(Context::new(&[*modulus], 16)?);
496
497 assert_eq!(
499 Poly::try_convert_from(&[0u64], &ctx, false, Representation::PowerBasis)?,
500 Poly::zero(&ctx, Representation::PowerBasis)
501 );
502 assert_eq!(
503 Poly::try_convert_from(&[0i64], &ctx, false, Representation::PowerBasis)?,
504 Poly::zero(&ctx, Representation::PowerBasis)
505 );
506 assert_eq!(
507 Poly::try_convert_from(&[0u64; 16], &ctx, false, Representation::PowerBasis)?,
508 Poly::zero(&ctx, Representation::PowerBasis)
509 );
510 assert_eq!(
511 Poly::try_convert_from(&[0i64; 16], &ctx, false, Representation::PowerBasis)?,
512 Poly::zero(&ctx, Representation::PowerBasis)
513 );
514 assert!(Poly::try_convert_from(
515 &[0u64; 17], &ctx,
517 false,
518 Representation::PowerBasis,
519 )
520 .is_err());
521
522 assert!(Poly::try_convert_from(&[0u64], &ctx, false, Representation::Ntt).is_err());
524 assert!(Poly::try_convert_from(&[0i64], &ctx, false, Representation::Ntt).is_err());
525 assert_eq!(
526 Poly::try_convert_from(&[0u64; 16], &ctx, false, Representation::Ntt)?,
527 Poly::zero(&ctx, Representation::Ntt)
528 );
529 assert!(Poly::try_convert_from(&[0i64; 16], &ctx, false, Representation::Ntt).is_err());
530 assert!(Poly::try_convert_from(
531 &[0u64; 17], &ctx,
533 false,
534 Representation::Ntt,
535 )
536 .is_err());
537 }
538
539 let ctx = Arc::new(Context::new(MODULI, 16)?);
540 assert_eq!(
541 Poly::try_convert_from(
542 Vec::<u64>::default(),
543 &ctx,
544 false,
545 Representation::PowerBasis,
546 )?,
547 Poly::zero(&ctx, Representation::PowerBasis)
548 );
549 assert!(
550 Poly::try_convert_from(Vec::<u64>::default(), &ctx, false, Representation::Ntt)
551 .is_err()
552 );
553
554 assert_eq!(
555 Poly::try_convert_from(&[0u64], &ctx, false, Representation::PowerBasis)?,
556 Poly::zero(&ctx, Representation::PowerBasis)
557 );
558 assert!(Poly::try_convert_from(&[0u64], &ctx, false, Representation::Ntt).is_err());
559
560 assert_eq!(
561 Poly::try_convert_from(&[0u64; 16], &ctx, false, Representation::PowerBasis)?,
562 Poly::zero(&ctx, Representation::PowerBasis)
563 );
564 assert!(Poly::try_convert_from(&[0u64; 16], &ctx, false, Representation::Ntt).is_err());
565
566 assert!(
567 Poly::try_convert_from(&[0u64; 17], &ctx, false, Representation::PowerBasis).is_err()
568 );
569 assert!(Poly::try_convert_from(&[0u64; 17], &ctx, false, Representation::Ntt).is_err());
570
571 assert_eq!(
572 Poly::try_convert_from(&[0u64; 16], &ctx, false, Representation::PowerBasis)?,
573 Poly::zero(&ctx, Representation::PowerBasis)
574 );
575 assert_eq!(
576 Poly::try_convert_from(&[0u64; 48], &ctx, false, Representation::Ntt)?,
577 Poly::zero(&ctx, Representation::Ntt)
578 );
579
580 Ok(())
581 }
582
583 #[test]
584 fn try_convert_from_vec_zero() -> Result<(), Box<dyn Error>> {
585 for modulus in MODULI {
586 let ctx = Arc::new(Context::new(&[*modulus], 16)?);
587 assert_eq!(
588 Poly::try_convert_from(vec![], &ctx, false, Representation::PowerBasis)?,
589 Poly::zero(&ctx, Representation::PowerBasis)
590 );
591 assert!(Poly::try_convert_from(vec![], &ctx, false, Representation::Ntt).is_err());
592
593 assert_eq!(
594 Poly::try_convert_from(vec![0], &ctx, false, Representation::PowerBasis)?,
595 Poly::zero(&ctx, Representation::PowerBasis)
596 );
597 assert!(Poly::try_convert_from(vec![0], &ctx, false, Representation::Ntt).is_err());
598
599 assert_eq!(
600 Poly::try_convert_from(vec![0; 16], &ctx, false, Representation::PowerBasis)?,
601 Poly::zero(&ctx, Representation::PowerBasis)
602 );
603 assert_eq!(
604 Poly::try_convert_from(vec![0; 16], &ctx, false, Representation::Ntt)?,
605 Poly::zero(&ctx, Representation::Ntt)
606 );
607
608 assert!(
609 Poly::try_convert_from(vec![0; 17], &ctx, false, Representation::PowerBasis)
610 .is_err()
611 );
612 assert!(Poly::try_convert_from(vec![0; 17], &ctx, false, Representation::Ntt).is_err());
613 }
614
615 let ctx = Arc::new(Context::new(MODULI, 16)?);
616 assert_eq!(
617 Poly::try_convert_from(vec![], &ctx, false, Representation::PowerBasis)?,
618 Poly::zero(&ctx, Representation::PowerBasis)
619 );
620 assert!(Poly::try_convert_from(vec![], &ctx, false, Representation::Ntt).is_err());
621
622 assert_eq!(
623 Poly::try_convert_from(vec![0], &ctx, false, Representation::PowerBasis)?,
624 Poly::zero(&ctx, Representation::PowerBasis)
625 );
626 assert!(Poly::try_convert_from(vec![0], &ctx, false, Representation::Ntt).is_err());
627
628 assert_eq!(
629 Poly::try_convert_from(vec![0; 16], &ctx, false, Representation::PowerBasis)?,
630 Poly::zero(&ctx, Representation::PowerBasis)
631 );
632 assert!(Poly::try_convert_from(vec![0; 16], &ctx, false, Representation::Ntt).is_err());
633
634 assert!(
635 Poly::try_convert_from(vec![0; 17], &ctx, false, Representation::PowerBasis).is_err()
636 );
637 assert!(Poly::try_convert_from(vec![0; 17], &ctx, false, Representation::Ntt).is_err());
638
639 assert_eq!(
640 Poly::try_convert_from(vec![0; 48], &ctx, false, Representation::PowerBasis)?,
641 Poly::zero(&ctx, Representation::PowerBasis)
642 );
643 assert_eq!(
644 Poly::try_convert_from(vec![0; 48], &ctx, false, Representation::Ntt)?,
645 Poly::zero(&ctx, Representation::Ntt)
646 );
647
648 Ok(())
649 }
650
651 #[test]
652 fn biguint() -> Result<(), Box<dyn Error>> {
653 let mut rng = rng();
654 for _ in 0..100 {
655 for modulus in MODULI {
656 let ctx = Arc::new(Context::new(&[*modulus], 16)?);
657 let p = Poly::random(&ctx, Representation::PowerBasis, &mut rng);
658 let p_coeffs = Vec::<BigUint>::from(&p);
659 let q = Poly::try_convert_from(
660 p_coeffs.as_slice(),
661 &ctx,
662 false,
663 Representation::PowerBasis,
664 )?;
665 assert_eq!(p, q);
666 }
667
668 let ctx = Arc::new(Context::new(MODULI, 16)?);
669 let p = Poly::random(&ctx, Representation::PowerBasis, &mut rng);
670 let p_coeffs = Vec::<BigUint>::from(&p);
671 assert_eq!(p_coeffs.len(), ctx.degree);
672 let q = Poly::try_convert_from(
673 p_coeffs.as_slice(),
674 &ctx,
675 false,
676 Representation::PowerBasis,
677 )?;
678 assert_eq!(p, q);
679 }
680 Ok(())
681 }
682}