ark_mpc/algebra/poly/
authenticated_poly.rs

1//! An authenticated polynomial over a `CurveGroup`'s scalar field
2//!
3//! Modeled after the `ark_poly::DensePolynomial` type, but allocated in an MPC
4//! fabric
5
6use std::{
7    cmp, iter,
8    ops::{Add, Div, Mul, Neg, Sub},
9    pin::Pin,
10    task::{Context, Poll},
11};
12
13use ark_ec::CurveGroup;
14use ark_poly::{univariate::DensePolynomial, DenseUVPolynomial, Polynomial};
15use futures::{ready, Future, FutureExt};
16use itertools::Itertools;
17
18use crate::{
19    algebra::{
20        macros::{impl_borrow_variants, impl_commutative},
21        AuthenticatedScalarOpenResult, AuthenticatedScalarResult, Scalar, ScalarResult,
22    },
23    error::MpcError,
24    MpcFabric,
25};
26
27use super::DensePolynomialResult;
28
29/// An authenticated polynomial; i.e. a polynomial in which the coefficients are
30/// secret shared between parties
31///
32/// This is modeled after the `ark_poly::DensePolynomial` [source](https://github.com/arkworks-rs/algebra/blob/master/poly/src/polynomial/univariate/dense.rs#L22)
33#[derive(Debug, Clone, Default)]
34pub struct AuthenticatedDensePoly<C: CurveGroup> {
35    /// A vector of coefficients, the coefficient for `x^i` is stored at index
36    /// `i`
37    pub coeffs: Vec<AuthenticatedScalarResult<C>>,
38}
39
40impl<C: CurveGroup> AuthenticatedDensePoly<C> {
41    /// Constructor
42    pub fn from_coeffs(coeffs: Vec<AuthenticatedScalarResult<C>>) -> Self {
43        assert!(
44            !coeffs.is_empty(),
45            "AuthenticatedDensePoly must have at least one coefficient"
46        );
47        Self { coeffs }
48    }
49
50    /// Allocate the zero polynomial (additive identity) in the given fabric
51    pub fn zero(fabric: &MpcFabric<C>) -> Self {
52        let coeffs = vec![fabric.zero_authenticated()];
53        Self::from_coeffs(coeffs)
54    }
55
56    /// Allocate the one polynomial (multiplicative identity) in the given
57    /// fabric
58    pub fn one(fabric: &MpcFabric<C>) -> Self {
59        let coeffs = vec![fabric.one_authenticated()];
60        Self::from_coeffs(coeffs)
61    }
62
63    /// Get the degree of the represented polynomial
64    pub fn degree(&self) -> usize {
65        self.coeffs.len() - 1
66    }
67
68    /// Sample a random polynomial of given degree
69    pub fn random(d: usize, fabric: &MpcFabric<C>) -> Self {
70        let coeffs = fabric.random_shared_scalars_authenticated(d + 1);
71        Self::from_coeffs(coeffs)
72    }
73
74    /// Get the fabric underlying the polynomial
75    pub fn fabric(&self) -> &MpcFabric<C> {
76        self.coeffs[0].fabric()
77    }
78
79    /// Evaluate the polynomial at a given point
80    ///
81    /// TODO: Opt for a more efficient implementation that allocates fewer
82    /// gates, i.e. by awaiting all results then creating the evaluation
83    pub fn eval(&self, x: &ScalarResult<C>) -> AuthenticatedScalarResult<C> {
84        // Evaluate the polynomial at the given point
85        let mut result = x.fabric().zero_authenticated();
86        for coeff in self.coeffs.iter().rev() {
87            result = result * x + coeff;
88        }
89
90        result
91    }
92
93    /// Open the polynomial to the base type `DensePolynomial`
94    pub fn open(&self) -> DensePolynomialResult<C> {
95        // Open the coeffs directly
96        let open_coeffs = AuthenticatedScalarResult::open_batch(&self.coeffs);
97        DensePolynomialResult::from_coeffs(open_coeffs)
98    }
99
100    /// Open the polynomial and authenticate the shares
101    pub fn open_authenticated(&self) -> AuthenticatedDensePolyOpenResult<C> {
102        // Open the coeffs directly
103        let coeff_open_results = AuthenticatedScalarResult::open_authenticated_batch(&self.coeffs);
104        AuthenticatedDensePolyOpenResult { coeff_open_results }
105    }
106}
107
108/// Inversion and division helpers
109impl<C: CurveGroup> AuthenticatedDensePoly<C> {
110    /// Reduce a given polynomial mod x^n
111    ///
112    /// For a modulus of this form, this is equivalent to truncating the
113    /// coefficients
114    pub fn mod_xn(&self, n: usize) -> Self {
115        let mut coeffs = self.coeffs.clone();
116        coeffs.truncate(n);
117
118        Self::from_coeffs(coeffs)
119    }
120
121    /// Reverse the coefficients of the polynomial and return a new polynomial
122    ///
123    /// This is useful when implementing division between authenticated
124    /// polynomials as per:     https://iacr.org/archive/pkc2006/39580045/39580045.pdf
125    /// Effectively, for a given polynomial a(x), the operation rev(a) returns
126    /// the polynomial:     rev(a)(x) = x^deg(a) * a(1/x)
127    /// which is emulated by reversing the coefficients directly.
128    ///
129    /// See the division docstring below for a more detailed explanation
130    pub fn rev(&self) -> Self {
131        let mut coeffs = self.coeffs.clone();
132        coeffs.reverse();
133
134        Self::from_coeffs(coeffs)
135    }
136
137    /// Get a random, shared masking polynomial of degree `n`
138    pub fn random_polynomial(n: usize, fabric: &MpcFabric<C>) -> Self {
139        let coeffs = fabric.random_shared_scalars_authenticated(n + 1);
140        Self::from_coeffs(coeffs)
141    }
142
143    /// Compute the multiplicative inverse of a polynomial in the quotient ring
144    /// F[x] / (x^t)
145    ///
146    /// Uses an extension of the inverse method defined in:
147    ///     https://dl.acm.org/doi/pdf/10.1145/72981.72995
148    pub fn mul_inverse_mod_t(&self, t: usize) -> Self {
149        let fabric = self.fabric();
150        let masking_poly = Self::random_polynomial(t /* degree */, fabric);
151
152        // Mask the polynomial and open the result
153        let masked_poly = (&masking_poly * self).open_authenticated();
154
155        // Invert the public, masked polynomial without interaction
156        let masked_poly_res = DensePolynomialResult::from_coeffs(
157            masked_poly
158                .coeff_open_results
159                .into_iter()
160                .map(|c| c.value)
161                .collect_vec(),
162        );
163        let inverted_masked_poly = masked_poly_res.mul_inverse_mod_t(t);
164
165        // Multiply out this inversion with the masking polynomial to cancel the masking
166        // term and reduce modulo x^t
167        let res = &inverted_masked_poly * &masking_poly;
168        res.mod_xn(t)
169    }
170}
171
172/// The result of opening an `AuthenticatedDensePoly` to its base type
173///
174/// Encapsulates a potential error in opening the polynomial
175pub struct AuthenticatedDensePolyOpenResult<C: CurveGroup> {
176    /// The opening results of each coefficient
177    pub coeff_open_results: Vec<AuthenticatedScalarOpenResult<C>>,
178}
179
180impl<C: CurveGroup> Future for AuthenticatedDensePolyOpenResult<C>
181where
182    C::ScalarField: Unpin,
183{
184    type Output = Result<DensePolynomial<C::ScalarField>, MpcError>;
185
186    fn poll(mut self: Pin<&mut Self>, cx: &mut Context<'_>) -> Poll<Self::Output> {
187        // Poll each coeff open result
188        let mut coeffs = Vec::new();
189        for coeff_open_result in self.coeff_open_results.iter_mut() {
190            match ready!(coeff_open_result.poll_unpin(cx)) {
191                Ok(coeff) => coeffs.push(coeff),
192                Err(e) => return Poll::Ready(Err(e)),
193            }
194        }
195
196        // Map all coefficients back into their Arkworks types
197        let inner_coeffs = coeffs
198            .into_iter()
199            .map(|coeff| coeff.inner())
200            .collect::<Vec<_>>();
201
202        Poll::Ready(Ok(DensePolynomial::from_coefficients_vec(inner_coeffs)))
203    }
204}
205
206// --------------
207// | Arithmetic |
208// --------------
209
210// --- Addition --- //
211impl<C: CurveGroup> Add<&DensePolynomial<C::ScalarField>> for &AuthenticatedDensePoly<C> {
212    type Output = AuthenticatedDensePoly<C>;
213    fn add(self, rhs: &DensePolynomial<C::ScalarField>) -> Self::Output {
214        assert!(!self.coeffs.is_empty(), "cannot add to an empty polynomial");
215        let fabric = self.coeffs[0].fabric();
216
217        let max_degree = cmp::max(self.degree(), rhs.degree());
218
219        // Pad the coefficients to the same length
220        let padded_coeffs0 = self
221            .coeffs
222            .iter()
223            .cloned()
224            .chain(iter::repeat(fabric.zero_authenticated()));
225        let padded_coeffs1 = rhs
226            .coeffs
227            .iter()
228            .copied()
229            .map(Scalar::<C>::new)
230            .chain(iter::repeat(Scalar::zero()));
231
232        // Add the coefficients component-wise
233        let mut coeffs = Vec::new();
234        for (lhs_coeff, rhs_coeff) in padded_coeffs0.zip(padded_coeffs1).take(max_degree + 1) {
235            coeffs.push(lhs_coeff + rhs_coeff);
236        }
237
238        AuthenticatedDensePoly::from_coeffs(coeffs)
239    }
240}
241impl_borrow_variants!(AuthenticatedDensePoly<C>, Add, add, +, DensePolynomial<C::ScalarField>, C: CurveGroup);
242impl_commutative!(AuthenticatedDensePoly<C>, Add, add, +, DensePolynomial<C::ScalarField>, C: CurveGroup);
243
244impl<C: CurveGroup> Add<&DensePolynomialResult<C>> for &AuthenticatedDensePoly<C> {
245    type Output = AuthenticatedDensePoly<C>;
246    fn add(self, rhs: &DensePolynomialResult<C>) -> Self::Output {
247        assert!(!self.coeffs.is_empty(), "cannot add to an empty polynomial");
248
249        // Pad both polynomials to the same length
250        let n_coeffs = cmp::max(self.coeffs.len(), rhs.coeffs.len());
251        let zero = self.fabric().zero();
252        let zero_authenticated = self.fabric().zero_authenticated();
253
254        let padded_lhs = self
255            .coeffs
256            .iter()
257            .chain(iter::repeat(&zero_authenticated))
258            .take(n_coeffs);
259        let padded_rhs = rhs.coeffs.iter().chain(iter::repeat(&zero)).take(n_coeffs);
260
261        // Add the coefficients component-wise
262        let mut coeffs = Vec::with_capacity(n_coeffs);
263        for (lhs_coeff, rhs_coeff) in padded_lhs.zip(padded_rhs) {
264            coeffs.push(lhs_coeff + rhs_coeff);
265        }
266
267        AuthenticatedDensePoly::from_coeffs(coeffs)
268    }
269}
270impl_borrow_variants!(AuthenticatedDensePoly<C>, Add, add, +, DensePolynomialResult<C>, C: CurveGroup);
271impl_commutative!(AuthenticatedDensePoly<C>, Add, add, +, DensePolynomialResult<C>, C: CurveGroup);
272
273impl<C: CurveGroup> Add<&AuthenticatedDensePoly<C>> for &AuthenticatedDensePoly<C> {
274    type Output = AuthenticatedDensePoly<C>;
275    fn add(self, rhs: &AuthenticatedDensePoly<C>) -> Self::Output {
276        // Don't pad the coefficients as it requires fewer gates when we don't have to
277        let (shorter, longer) = if self.coeffs.len() < rhs.coeffs.len() {
278            (&self.coeffs, &rhs.coeffs)
279        } else {
280            (&rhs.coeffs, &self.coeffs)
281        };
282
283        let mut coeffs = Vec::new();
284        for (i, longer_coeff) in longer.iter().enumerate() {
285            let new_coeff = if i < shorter.len() {
286                &shorter[i] + longer_coeff
287            } else {
288                longer_coeff.clone()
289            };
290            coeffs.push(new_coeff);
291        }
292
293        AuthenticatedDensePoly::from_coeffs(coeffs)
294    }
295}
296impl_borrow_variants!(AuthenticatedDensePoly<C>, Add, add, +, AuthenticatedDensePoly<C>, C: CurveGroup);
297
298// --- Negation --- //
299impl<C: CurveGroup> Neg for &AuthenticatedDensePoly<C> {
300    type Output = AuthenticatedDensePoly<C>;
301
302    fn neg(self) -> Self::Output {
303        let coeffs = self
304            .coeffs
305            .iter()
306            .map(|coeff| coeff.neg())
307            .collect::<Vec<_>>();
308
309        AuthenticatedDensePoly::from_coeffs(coeffs)
310    }
311}
312impl_borrow_variants!(AuthenticatedDensePoly<C>, Neg, neg, -, C: CurveGroup);
313
314// --- Subtraction --- //
315#[allow(clippy::suspicious_arithmetic_impl)]
316impl<C: CurveGroup> Sub<&DensePolynomial<C::ScalarField>> for &AuthenticatedDensePoly<C> {
317    type Output = AuthenticatedDensePoly<C>;
318
319    fn sub(self, rhs: &DensePolynomial<C::ScalarField>) -> Self::Output {
320        let negated_rhs_coeffs = rhs.coeffs.iter().map(|coeff| coeff.neg()).collect_vec();
321        self + DensePolynomial::from_coefficients_vec(negated_rhs_coeffs)
322    }
323}
324impl_borrow_variants!(AuthenticatedDensePoly<C>, Sub, sub, -, DensePolynomial<C::ScalarField>, C: CurveGroup);
325
326#[allow(clippy::suspicious_arithmetic_impl)]
327impl<C: CurveGroup> Sub<&AuthenticatedDensePoly<C>> for &AuthenticatedDensePoly<C> {
328    type Output = AuthenticatedDensePoly<C>;
329
330    fn sub(self, rhs: &AuthenticatedDensePoly<C>) -> Self::Output {
331        self + (-rhs)
332    }
333}
334impl_borrow_variants!(AuthenticatedDensePoly<C>, Sub, sub, -, AuthenticatedDensePoly<C>, C: CurveGroup);
335
336// --- Multiplication --- //
337// TODO: We can use an FFT-based approach here, it takes a bit more care because
338// evaluations needed are more expensive, but it could provide a performance
339// boost
340//
341// For now we leave this as an optimization, the current implementation can be
342// executed in one round, although with many gates
343impl<C: CurveGroup> Mul<&DensePolynomial<C::ScalarField>> for &AuthenticatedDensePoly<C> {
344    type Output = AuthenticatedDensePoly<C>;
345
346    fn mul(self, rhs: &DensePolynomial<C::ScalarField>) -> Self::Output {
347        assert!(
348            !self.coeffs.is_empty(),
349            "cannot multiply an empty polynomial"
350        );
351        let fabric = self.coeffs[0].fabric();
352
353        // Setup the zero coefficients
354        let result_degree = self.degree() + rhs.degree();
355        let mut coeffs = Vec::with_capacity(result_degree + 1);
356        for _ in 0..(result_degree + 1) {
357            coeffs.push(fabric.zero_authenticated());
358        }
359
360        // Multiply the coefficients component-wise
361        for (i, lhs_coeff) in self.coeffs.iter().enumerate() {
362            for (j, rhs_coeff) in rhs.coeffs.iter().enumerate() {
363                coeffs[i + j] = &coeffs[i + j] + (lhs_coeff * Scalar::<C>::new(*rhs_coeff));
364            }
365        }
366
367        AuthenticatedDensePoly::from_coeffs(coeffs)
368    }
369}
370
371impl<C: CurveGroup> Mul<&DensePolynomialResult<C>> for &AuthenticatedDensePoly<C> {
372    type Output = AuthenticatedDensePoly<C>;
373
374    fn mul(self, rhs: &DensePolynomialResult<C>) -> Self::Output {
375        assert!(
376            !self.coeffs.is_empty(),
377            "cannot multiply an empty polynomial"
378        );
379        let fabric = self.coeffs[0].fabric();
380
381        // Setup the zero coefficients
382        let result_degree = self.degree() + rhs.degree();
383        let mut coeffs = Vec::with_capacity(result_degree + 1);
384        for _ in 0..(result_degree + 1) {
385            coeffs.push(fabric.zero_authenticated());
386        }
387
388        // Multiply the coefficients component-wise
389        for (i, lhs_coeff) in self.coeffs.iter().enumerate() {
390            for (j, rhs_coeff) in rhs.coeffs.iter().enumerate() {
391                coeffs[i + j] = &coeffs[i + j] + (lhs_coeff * rhs_coeff);
392            }
393        }
394
395        AuthenticatedDensePoly::from_coeffs(coeffs)
396    }
397}
398impl_borrow_variants!(AuthenticatedDensePoly<C>, Mul, mul, *, DensePolynomialResult<C>, C: CurveGroup);
399impl_commutative!(AuthenticatedDensePoly<C>, Mul, mul, *, DensePolynomialResult<C>, C: CurveGroup);
400
401impl<C: CurveGroup> Mul<&AuthenticatedDensePoly<C>> for &AuthenticatedDensePoly<C> {
402    type Output = AuthenticatedDensePoly<C>;
403
404    fn mul(self, rhs: &AuthenticatedDensePoly<C>) -> Self::Output {
405        assert!(
406            !self.coeffs.is_empty(),
407            "cannot multiply an empty polynomial"
408        );
409        let fabric = self.coeffs[0].fabric();
410
411        // Setup the zero coefficients
412        let result_degree = self.degree() + rhs.degree();
413        let mut coeffs = Vec::with_capacity(result_degree + 1);
414        for _ in 0..(result_degree + 1) {
415            coeffs.push(fabric.zero_authenticated());
416        }
417
418        // Multiply the coefficients component-wise
419        for (i, lhs_coeff) in self.coeffs.iter().enumerate() {
420            for (j, rhs_coeff) in rhs.coeffs.iter().enumerate() {
421                coeffs[i + j] = &coeffs[i + j] + (lhs_coeff * rhs_coeff);
422            }
423        }
424
425        AuthenticatedDensePoly::from_coeffs(coeffs)
426    }
427}
428
429// --- Scalar Multiplication --- //
430
431impl<C: CurveGroup> Mul<&Scalar<C>> for &AuthenticatedDensePoly<C> {
432    type Output = AuthenticatedDensePoly<C>;
433
434    fn mul(self, rhs: &Scalar<C>) -> Self::Output {
435        let new_coeffs = self.coeffs.iter().map(|coeff| coeff * rhs).collect_vec();
436        AuthenticatedDensePoly::from_coeffs(new_coeffs)
437    }
438}
439impl_borrow_variants!(AuthenticatedDensePoly<C>, Mul, mul, *, Scalar<C>, C: CurveGroup);
440impl_commutative!(AuthenticatedDensePoly<C>, Mul, mul, *, Scalar<C>, C: CurveGroup);
441
442impl<C: CurveGroup> Mul<&ScalarResult<C>> for &AuthenticatedDensePoly<C> {
443    type Output = AuthenticatedDensePoly<C>;
444
445    fn mul(self, rhs: &ScalarResult<C>) -> Self::Output {
446        let new_coeffs = self.coeffs.iter().map(|coeff| coeff * rhs).collect_vec();
447        AuthenticatedDensePoly::from_coeffs(new_coeffs)
448    }
449}
450impl_borrow_variants!(AuthenticatedDensePoly<C>, Mul, mul, *, ScalarResult<C>, C: CurveGroup);
451impl_commutative!(AuthenticatedDensePoly<C>, Mul, mul, *, ScalarResult<C>, C: CurveGroup);
452
453impl<C: CurveGroup> Mul<&AuthenticatedScalarResult<C>> for &AuthenticatedDensePoly<C> {
454    type Output = AuthenticatedDensePoly<C>;
455
456    fn mul(self, rhs: &AuthenticatedScalarResult<C>) -> Self::Output {
457        let new_coeffs = self.coeffs.iter().map(|coeff| coeff * rhs).collect_vec();
458        AuthenticatedDensePoly::from_coeffs(new_coeffs)
459    }
460}
461impl_borrow_variants!(AuthenticatedDensePoly<C>, Mul, mul, *, AuthenticatedScalarResult<C>, C: CurveGroup);
462impl_commutative!(AuthenticatedDensePoly<C>, Mul, mul, *, AuthenticatedScalarResult<C>, C: CurveGroup);
463
464// --- Division --- //
465/// Given a public divisor b(x) and shared dividend a(x) = a_1(x) + a_2(x) for
466/// party shares a_1, a_2 We can divide each share locally to obtain a secret
467/// sharing of \floor{a(x) / b(x)}
468///
469/// To see this, consider that a_1(x) = q_1(x)b(x) + r_1(x) and a_2(x) =
470/// q_2(x)b(x) + r_2(x) where:
471///     - deg(q_1) = deg(a_1) - deg(b)
472///     - deg(q_2) = deg(a_2) - deg(b)
473///     - deg(r_1) < deg(b)
474///     - deg(r_2) < deg(b)
475/// The floor division operator for a(x), b(x) returns q(x) such that there
476/// exists r(x): deg(r) < deg(b) where a(x) = q(x)b(x) + r(x)
477/// Note that a_1(x) + a_2(x) = (q_1(x) + q_2(x))b(x) + r_1(x) + r_2(x), where
478/// of course deg(r_1 + r_2) < deg(b), so \floor{a(x) / b(x)} = q_1(x) + q_2(x);
479/// making q_1, q_2 additive secret shares of the result as desired
480impl<C: CurveGroup> Div<&DensePolynomialResult<C>> for &AuthenticatedDensePoly<C> {
481    type Output = AuthenticatedDensePoly<C>;
482
483    fn div(self, rhs: &DensePolynomialResult<C>) -> Self::Output {
484        // We cannot break early if the remainder is exhausted because this will cause
485        // the gate sequencing to differ between parties in the MPC. Instead we
486        // execute the whole computation on both ends of the MPC
487        assert!(!rhs.coeffs.is_empty(), "cannot divide by zero polynomial");
488        let fabric = self.coeffs[0].fabric();
489
490        let quotient_degree = self.degree().saturating_sub(rhs.degree());
491        if quotient_degree == 0 {
492            return AuthenticatedDensePoly::zero(fabric);
493        }
494
495        let mut remainder = self.clone();
496        let mut quotient_coeffs = fabric.zeros_authenticated(quotient_degree + 1);
497
498        let divisor_leading_inverse = rhs.coeffs.last().unwrap().inverse();
499        for deg in (0..=quotient_degree).rev() {
500            // Compute the quotient coefficient for this round
501            let remainder_leading_coeff = remainder.coeffs.last().unwrap();
502            let next_quotient_coeff = remainder_leading_coeff * &divisor_leading_inverse;
503
504            // Update the remainder and record the coefficient
505            for (i, divisor_coeff) in rhs.coeffs.iter().enumerate() {
506                let remainder_ind = deg + i;
507                remainder.coeffs[remainder_ind] =
508                    &remainder.coeffs[remainder_ind] - divisor_coeff * &next_quotient_coeff;
509            }
510
511            quotient_coeffs[deg] = next_quotient_coeff;
512
513            // Pop the leading coefficient (now zero) from the remainder
514            remainder.coeffs.pop();
515        }
516
517        AuthenticatedDensePoly::from_coeffs(quotient_coeffs)
518    }
519}
520impl_borrow_variants!(AuthenticatedDensePoly<C>, Div, div, /, DensePolynomialResult<C>, C: CurveGroup);
521
522/// Authenticated division, i.e. division in which the divisor is a secret
523/// shared polynomial
524///
525/// We follow the approach of: https://iacr.org/archive/pkc2006/39580045/39580045.pdf (Section 4)
526///
527/// To see why this method holds, consider the `rev` operation for a polynomial
528/// a(x):     rev(a) = x^deg(a) * a(1/x)
529/// Note that this operation is equivalent to reversing the coefficients of a(x)
530/// For f(x) / g(x) where deg(f) = n, deg(g) = m, the objective of a division
531/// with remainder algorithm is to solve:
532///     f(x) = g(x)q(x) + r(x)
533/// for q(x), r(x) uniquely where deg(r) < deg(g).
534///
535/// We could solve for q(x) easily if:
536///     1. We could "mod out" r(x) and
537///     2. If g^{-1}(x) exists
538/// The rev operator provides a transformation that makes both of these true:
539///     rev(f) = rev(g) * rev(q) + x^{n - m + 1} * rev(r)
540/// Again, we have used the `rev` operator to reverse the coefficients of each
541/// polynomial so that the leading coefficients are those of r(x). Now we can
542/// "mod out" the highest terms to get:
543///     rev(f) = rev(g) * rev(q) mod x^{n - m + 1}
544/// And now that we are working in the quotient ring F[x] / (x^{n - m + 1}), we
545/// can be sure that rev(g)^{-1}(x) exists if its lowest degree coefficient
546/// (constant coefficient) is non-zero. For random (blinded) polynomials, this
547/// is true with probability 1 - 1/p.
548///
549/// So we:
550///     1. apply the `rev` transformation,
551///     2. mod out rev{r} and solve for rev(q)
552///     3. undo the `rev` transformation to get q(x)
553///     4. solve for r(x) = f(x) - q(x)g(x), though for floor division we skip
554///        this step
555impl<C: CurveGroup> Div<&AuthenticatedDensePoly<C>> for &AuthenticatedDensePoly<C> {
556    type Output = AuthenticatedDensePoly<C>;
557
558    // Let f = self, g = rhs
559    fn div(self, rhs: &AuthenticatedDensePoly<C>) -> Self::Output {
560        let n = self.degree();
561        let m = rhs.degree();
562        if n < m {
563            return AuthenticatedDensePoly::zero(self.fabric());
564        }
565
566        let modulus = n - m + 1;
567
568        // Apply the rev transformation
569        let rev_f = self.rev();
570        let rev_g = rhs.rev();
571
572        // Invert `rev_g` in the quotient ring
573        let rev_g_inv = rev_g.mul_inverse_mod_t(modulus);
574
575        // Compute rev_f * rev_g_inv and "mod out" rev_r; what is left is `rev_q`
576        let rev_q = (&rev_f * &rev_g_inv).mod_xn(modulus);
577
578        // Undo the `rev` transformation
579        rev_q.rev()
580    }
581}
582impl_borrow_variants!(AuthenticatedDensePoly<C>, Div, div, /, AuthenticatedDensePoly<C>, C: CurveGroup);
583
584#[cfg(test)]
585mod test {
586    use ark_poly::Polynomial;
587    use rand::thread_rng;
588
589    use crate::{
590        algebra::{
591            poly_test_helpers::{allocate_poly, random_poly, share_poly},
592            Scalar,
593        },
594        test_helpers::execute_mock_mpc,
595        PARTY0, PARTY1,
596    };
597
598    /// The degree bound used for testing
599    const DEGREE_BOUND: usize = 100;
600
601    /// Test evaluating a polynomial at a given point
602    #[tokio::test]
603    async fn test_eval() {
604        let mut rng = thread_rng();
605        let poly = random_poly(DEGREE_BOUND);
606        let point = Scalar::random(&mut rng);
607
608        let expected_res = poly.evaluate(&point.inner());
609
610        let (res, _) = execute_mock_mpc(|fabric| {
611            let poly = poly.clone();
612            async move {
613                let shared_poly = share_poly(poly, PARTY0, &fabric);
614                let point = fabric.allocate_scalar(point);
615
616                shared_poly.eval(&point).open_authenticated().await
617            }
618        })
619        .await;
620
621        assert!(res.is_ok());
622        assert_eq!(res.unwrap(), Scalar::new(expected_res));
623    }
624
625    /// Tests adding a constant polynomial to an authenticated polynomial
626    #[tokio::test]
627    async fn test_add_constant_poly() {
628        let poly1 = random_poly(DEGREE_BOUND);
629        let poly2 = random_poly(DEGREE_BOUND);
630
631        let expected_res = &poly1 + &poly2;
632
633        let (res, _) = execute_mock_mpc(|fabric| {
634            let poly1 = poly1.clone();
635            let poly2 = poly2.clone();
636
637            async move {
638                let shared_poly1 = share_poly(poly1, PARTY0, &fabric);
639
640                let res = &shared_poly1 + &poly2;
641                res.open_authenticated().await
642            }
643        })
644        .await;
645
646        assert!(res.is_ok());
647        assert_eq!(res.unwrap(), expected_res);
648    }
649
650    /// Tests adding a public polynomial to an authenticated polynomial
651    #[tokio::test]
652    async fn test_add_public_poly() {
653        let poly1 = random_poly(DEGREE_BOUND);
654        let poly2 = random_poly(DEGREE_BOUND);
655
656        let expected_res = &poly1 + &poly2;
657
658        let (res, _) = execute_mock_mpc(|fabric| {
659            let poly1 = poly1.clone();
660            let poly2 = poly2.clone();
661
662            async move {
663                let shared_poly1 = share_poly(poly1, PARTY0, &fabric);
664                let poly2 = allocate_poly(&poly2, &fabric);
665
666                let res = &shared_poly1 + &poly2;
667                res.open_authenticated().await
668            }
669        })
670        .await;
671
672        assert!(res.is_ok());
673        assert_eq!(res.unwrap(), expected_res);
674    }
675
676    /// Tests adding two authenticated polynomials
677    #[tokio::test]
678    async fn test_add_poly() {
679        let poly1 = random_poly(DEGREE_BOUND);
680        let poly2 = random_poly(DEGREE_BOUND);
681
682        let expected_res = &poly1 + &poly2;
683
684        let (res, _) = execute_mock_mpc(|fabric| {
685            let poly1 = poly1.clone();
686            let poly2 = poly2.clone();
687
688            async move {
689                let shared_poly1 = share_poly(poly1, PARTY0, &fabric);
690                let shared_poly2 = share_poly(poly2, PARTY0, &fabric);
691
692                let res = &shared_poly1 + &shared_poly2;
693                res.open_authenticated().await
694            }
695        })
696        .await;
697
698        assert!(res.is_ok());
699        assert_eq!(res.unwrap(), expected_res);
700    }
701
702    /// Tests subtracting a constant polynomial from an authenticated polynomial
703    #[tokio::test]
704    async fn test_subtract_constant_poly() {
705        let poly1 = random_poly(DEGREE_BOUND);
706        let poly2 = random_poly(DEGREE_BOUND);
707
708        let expected_res = &poly1 - &poly2;
709
710        let (res, _) = execute_mock_mpc(|fabric| {
711            let poly1 = poly1.clone();
712            let poly2 = poly2.clone();
713
714            async move {
715                let shared_poly1 = share_poly(poly1, PARTY0, &fabric);
716
717                let res = &shared_poly1 - &poly2;
718                res.open_authenticated().await
719            }
720        })
721        .await;
722
723        assert!(res.is_ok());
724        assert_eq!(res.unwrap(), expected_res);
725    }
726
727    /// Tests subtracting two authenticated polynomials
728    #[tokio::test]
729    async fn test_subtract_poly() {
730        let poly1 = random_poly(DEGREE_BOUND);
731        let poly2 = random_poly(DEGREE_BOUND);
732
733        let expected_res = &poly1 - &poly2;
734
735        let (res, _) = execute_mock_mpc(|fabric| {
736            let poly1 = poly1.clone();
737            let poly2 = poly2.clone();
738
739            async move {
740                let shared_poly1 = share_poly(poly1, PARTY0, &fabric);
741                let shared_poly2 = share_poly(poly2, PARTY0, &fabric);
742
743                let res = &shared_poly1 - &shared_poly2;
744                res.open_authenticated().await
745            }
746        })
747        .await;
748
749        assert!(res.is_ok());
750        assert_eq!(res.unwrap(), expected_res);
751    }
752
753    /// Test multiplying a constant polynomial with an authenticated polynomial
754    #[tokio::test]
755    async fn test_mul_constant_polynomial() {
756        let poly1 = random_poly(DEGREE_BOUND);
757        let poly2 = random_poly(DEGREE_BOUND);
758
759        let expected_res = &poly1 * &poly2;
760
761        let (res, _) = execute_mock_mpc(|fabric| {
762            let poly1 = poly1.clone();
763            let poly2 = poly2.clone();
764
765            async move {
766                let shared_poly1 = share_poly(poly1, PARTY0, &fabric);
767
768                let res = &shared_poly1 * &poly2;
769                res.open_authenticated().await
770            }
771        })
772        .await;
773
774        assert!(res.is_ok());
775        assert_eq!(res.unwrap(), expected_res);
776    }
777
778    /// Tests multiplying by a public polynomial result
779    #[tokio::test]
780    async fn test_mul_public_polynomial() {
781        let poly1 = random_poly(DEGREE_BOUND);
782        let poly2 = random_poly(DEGREE_BOUND);
783
784        let expected_res = &poly1 * &poly2;
785
786        let (res, _) = execute_mock_mpc(|fabric| {
787            let poly1 = poly1.clone();
788            let poly2 = poly2.clone();
789
790            async move {
791                let shared_poly1 = share_poly(poly1, PARTY0, &fabric);
792                let poly2 = allocate_poly(&poly2, &fabric);
793
794                let res = &shared_poly1 * &poly2;
795                res.open_authenticated().await
796            }
797        })
798        .await;
799
800        assert!(res.is_ok());
801        assert_eq!(res.unwrap(), expected_res);
802    }
803
804    /// Test multiplying two authenticated polynomials
805    #[tokio::test]
806    async fn test_mul_polynomial() {
807        let poly1 = random_poly(DEGREE_BOUND);
808        let poly2 = random_poly(DEGREE_BOUND);
809
810        let expected_res = &poly1 * &poly2;
811
812        let (res, _) = execute_mock_mpc(|fabric| {
813            let poly1 = poly1.clone();
814            let poly2 = poly2.clone();
815
816            async move {
817                let shared_poly1 = share_poly(poly1, PARTY0, &fabric);
818                let shared_poly2 = share_poly(poly2, PARTY0, &fabric);
819
820                let res = &shared_poly1 * &shared_poly2;
821                res.open_authenticated().await
822            }
823        })
824        .await;
825
826        assert!(res.is_ok());
827        assert_eq!(res.unwrap(), expected_res);
828    }
829
830    /// Tests multiplying by a public constant scalar
831    #[tokio::test]
832    async fn test_scalar_mul_constant() {
833        let mut rng = thread_rng();
834        let poly = random_poly(DEGREE_BOUND);
835        let scaling_factor = Scalar::random(&mut rng);
836
837        let expected_res = &poly * scaling_factor.inner();
838
839        let (res, _) = execute_mock_mpc(|fabric| {
840            let poly = poly.clone();
841            async move {
842                let shared_poly = share_poly(poly, PARTY0, &fabric);
843                (shared_poly * scaling_factor).open_authenticated().await
844            }
845        })
846        .await;
847
848        assert!(res.is_ok());
849        assert_eq!(res.unwrap(), expected_res);
850    }
851
852    /// Tests multiplying by a public result
853    #[tokio::test]
854    async fn test_scalar_mul_public() {
855        let mut rng = thread_rng();
856        let poly = random_poly(DEGREE_BOUND);
857        let scaling_factor = Scalar::random(&mut rng);
858
859        let expected_res = &poly * scaling_factor.inner();
860
861        let (res, _) = execute_mock_mpc(|fabric| {
862            let poly = poly.clone();
863            async move {
864                let shared_poly = share_poly(poly, PARTY0, &fabric);
865                let scaling_factor = fabric.allocate_scalar(scaling_factor);
866
867                (shared_poly * scaling_factor).open_authenticated().await
868            }
869        })
870        .await;
871
872        assert!(res.is_ok());
873        assert_eq!(res.unwrap(), expected_res);
874    }
875
876    /// Tests multiplying by a shared scalar
877    #[tokio::test]
878    async fn test_scalar_mul() {
879        let mut rng = thread_rng();
880        let poly = random_poly(DEGREE_BOUND);
881        let scaling_factor = Scalar::random(&mut rng);
882
883        let expected_res = &poly * scaling_factor.inner();
884
885        let (res, _) = execute_mock_mpc(|fabric| {
886            let poly = poly.clone();
887            async move {
888                let shared_poly = share_poly(poly, PARTY0, &fabric);
889                let scaling_factor = fabric.share_scalar(scaling_factor, PARTY0);
890
891                (shared_poly * scaling_factor).open_authenticated().await
892            }
893        })
894        .await;
895
896        assert!(res.is_ok());
897        assert_eq!(res.unwrap(), expected_res);
898    }
899
900    /// Tests dividing a shared polynomial by a public polynomial
901    #[tokio::test]
902    async fn test_div_polynomial_public() {
903        let poly1 = random_poly(DEGREE_BOUND);
904        let poly2 = random_poly(DEGREE_BOUND);
905
906        let expected_res = &poly1 / &poly2;
907
908        let (res, _) = execute_mock_mpc(|fabric| {
909            let poly1 = poly1.clone();
910            let poly2 = poly2.clone();
911            async move {
912                let dividend = share_poly(poly1, PARTY0, &fabric);
913                let divisor = allocate_poly(&poly2, &fabric);
914
915                let quotient = dividend / divisor;
916                quotient.open_authenticated().await
917            }
918        })
919        .await;
920
921        assert!(res.is_ok());
922        assert_eq!(res.unwrap(), expected_res);
923    }
924
925    /// Tests dividing two shared polynomial
926    #[tokio::test]
927    async fn test_div_polynomial() {
928        let poly1 = random_poly(DEGREE_BOUND);
929        let poly2 = random_poly(DEGREE_BOUND);
930
931        let expected_res = &poly1 / &poly2;
932
933        let (res, _) = execute_mock_mpc(|fabric| {
934            let poly1 = poly1.clone();
935            let poly2 = poly2.clone();
936            async move {
937                let dividend = share_poly(poly1, PARTY0, &fabric);
938                let divisor = share_poly(poly2, PARTY1, &fabric);
939
940                let quotient = dividend / divisor;
941                quotient.open_authenticated().await
942            }
943        })
944        .await;
945
946        assert!(res.is_ok());
947        assert_eq!(res.unwrap(), expected_res);
948    }
949}
ark_mpc/algebra/poly/authenticated_poly.rs

ark_mpc/algebra/poly/
authenticated_poly.rs
