Secure Evaluations

Similar to CircleEvaluation, SecureEvaluation is a point-value representation of a polynomial whose evaluations over the CircleDomain are from the SecureField (an alias for QM31). This is implemented as follows:

pub struct SecureEvaluation<B: ColumnOps<BaseField>, EvalOrder> {
    pub domain: CircleDomain,
    pub values: SecureColumnByCoords<B>,
    _eval_order: PhantomData<EvalOrder>,
}

As discussed in the previous subsection, each SecureField element is represented by four base field elements and stored in four consecutive columns. Thus the evaluations are represented as SecureColumnByCoords, as shown above.

Similar to CircleEvaluation, we can interpolate a SecureCirclePoly with coefficients from the SecureField as shown below:

impl<B: PolyOps> SecureEvaluation<B, BitReversedOrder> {
    /// Computes a minimal [`SecureCirclePoly`] that evaluates to the same values as this
    /// evaluation, using precomputed twiddles.
    pub fn interpolate_with_twiddles(self, twiddles: &TwiddleTree<B>) -> SecureCirclePoly<B> {
        let domain = self.domain;
        let cols = self.values.columns;
        SecureCirclePoly(cols.map(|c| {
            CircleEvaluation::<B, BaseField, BitReversedOrder>::new(domain, c)
                .interpolate_with_twiddles(twiddles)
        }))
    }
}

Secure Circle Polynomials

Similar to CirclePoly, SecureCirclePoly is a coefficient representation of a polynomial whose coefficients are from the SecureField. As discussed in the earlier section, we can define a circle polynomial as follows: $$p(x,y)=\sum _{j=0}^{2^n-1}{v}_j\cdot y^{j_0}\cdot x^{j_1}\cdot \pi (x{)}^{j_2}\cdot {\pi }^2(x{)}^{j_3}\cdots {\pi }^{n-2}(x{)}^{j_{n-1}}$$ Here, $v_j$ are the coefficients from SecureField (i.e. $QM31$). We can represent the coefficient $v_j$ using four elements from the BaseField (i.e. $M31$) as follows: $$v_j=(a_j+i\cdot b_j)+(c_j+i\cdot d_j)\cdot u$$

where $a_j,b_j,c_j,d_j\in M31$. Substituting the above representation in the equation of $p(x,y)$ we get: $$p(x,y)=\sum _{j=0}^{2^n-1}(a_j+i\cdot b_j+u\cdot c_j+i\cdot u\cdot d_j)\cdot y^{j_0}\cdot x^{j_1}\cdot \pi (x{)}^{j_2}\cdot {\pi }^2(x{)}^{j_3}\cdots {\pi }^{n-2}(x{)}^{j_{n-1}}$$

$$\begin{gathered} p(x,y)=\sum _{j=0}^{2^n-1}{a}_j\cdot y^{j_0}\cdot x^{j_1}\cdot \pi (x{)}^{j_2}\cdots {\pi }^{n-2}(x{)}^{j_{n-1}} \\ + \\ i\cdot \sum _{j=0}^{2^n-1}{b}_j\cdot y^{j_0}\cdot x^{j_1}\cdot \pi (x{)}^{j_2}\cdots {\pi }^{n-2}(x{)}^{j_{n-1}} \\ + \end{gathered}$$

$$\begin{gathered} u\cdot \sum _{j=0}^{2^n-1}{c}_j\cdot y^{j_0}\cdot x^{j_1}\cdot \pi (x{)}^{j_2}\cdots {\pi }^{n-2}(x{)}^{j_{n-1}} \\ + \\ iu\cdot \sum _{j=0}^{2^n-1}{d}_j\cdot y^{j_0}\cdot x^{j_1}\cdot \pi (x{)}^{j_2}\cdots {\pi }^{n-2}(x{)}^{j_{n-1}} \end{gathered}$$

Thus we can represent a SecureCirclePoly using four CirclePoly: $p_a(x,y),p_b(x,y),p_c(x,y)$ and $p_d(x,y)$ as follows: $$p(x,y)=p_a(x,y)+i\cdot p_b(x,y)+u\cdot p_c(x,y)+iu\cdot p_d(x,y)$$

where $p_a(x,y)$ is a CirclePoly with coefficients $a_j\in M31$, similarly for $p_b(x,y),p_c(x,y)$ and $p_d(x,y)$. This is implemented as follows:

pub struct SecureCirclePoly<B: ColumnOps<BaseField>>(pub [CirclePoly<B>; SECURE_EXTENSION_DEGREE]);

Here, SECURE_EXTENSION_DEGREE is the degree of extension of the SecureField, which is 4.

Similar to CirclePoly, we can evaluate the SecureCirclePoly at points on the given CircleDomain which outputs the SecureEvaluation.

    pub fn evaluate_with_twiddles(
        &self,
        domain: CircleDomain,
        twiddles: &TwiddleTree<B>,
    ) -> SecureEvaluation<B, BitReversedOrder> {
        let polys = self.0.each_ref();
        let columns = polys.map(|poly| poly.evaluate_with_twiddles(domain, twiddles).values);
        SecureEvaluation::new(domain, SecureColumnByCoords { columns })
    }

In the next section, we will see how the interpolate and evaluate functions convert between the two polynomial representations using Circle FFT. As you may have noticed, the twiddles are precomputed for efficiency, and we will explore this in the next section on Circle FFT.