Skip to main content

​
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:
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:

​
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)=∑j=02n−1vj⋅yj0⋅xj1⋅π(x)j2⋅π2(x)j3⋯πn−2(x)jn−1p(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, vjv_j are the coefficients from SecureField (i.e. QM31\mathsf{QM31}). We can represent the coefficient vjv_j using four elements from the BaseField (i.e. M31\mathsf{M31}) as follows: vj=(aj+i⋅bj)+(cj+i⋅dj)⋅uv_j = (a_j + i \cdot b_j) + (c_j + i \cdot d_j) \cdot u where aj,bj,cj,dj∈M31a_j, b_j, c_j, d_j \in \mathsf{M31}. Substituting the above representation in the equation of p(x,y)p(x, y) we get: p(x,y)=∑j=02n−1(aj+i⋅bj+u⋅cj+i⋅u⋅dj)⋅yj0⋅xj1⋅π(x)j2⋅π2(x)j3⋯πn−2(x)jn−1p(x, y) = \sum_{j=0}^{2^n -1} \Big(a_j + i \cdot b_j + u \cdot c_j + i \cdot u \cdot d_j \Big) \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}} p(x,y)=∑j=02n−1aj⋅yj0⋅xj1⋅π(x)j2⋯πn−2(x)jn−1+i⋅∑j=02n−1bj⋅yj0⋅xj1⋅π(x)j2⋯πn−2(x)jn−1+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}} \\ + \\ u⋅∑j=02n−1cj⋅yj0⋅xj1⋅π(x)j2⋯πn−2(x)jn−1+iu⋅∑j=02n−1dj⋅yj0⋅xj1⋅π(x)j2⋯πn−2(x)jn−1\\ \\ 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}} Thus we can represent a SecureCirclePoly using four CirclePoly: pa(x,y),pb(x,y),pc(x,y)p_a(x, y), p_b(x, y), p_c(x, y) and pd(x,y)p_d(x, y) as follows: p(x,y)=pa(x,y)+i⋅pb(x,y)+u⋅pc(x,y)+iu⋅pd(x,y)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 pa(x,y)p_a(x,y) is a CirclePoly with coefficients aj∈M31a_j \in \mathsf{M31}, similarly for pb(x,y),pc(x,y)p_b(x, y), p_c(x, y) and pd(x,y)p_d(x, y). This is implemented as follows:
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.
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.