How can we evaluate a polynomials in a group instead of a field? (verifiable secret sharing on elliptic curves)

Question

I am trying to understand how we can have cryptographic schemes that builds on both secret sharing, which is build on top of a finite field, and bilinear maps, which are built on top of elliptic curve groups.

An example of this is section 4 in Public Verifiability from Pairings in Secret Sharing Schemes, where publicly verifiable secret sharing is obtained with bilinear maps as proofs of correctness. The relevant part of the scheme for the question is:

1. Setup: $q$ is a prime and $h$ generates a group $G$ of order $q$. Each participant publishes the public key $h_i = h^{d_i}$, where $d_i$ is a random number in $F^*_q$.

2. Distribution: the dealer chooses a random polynomial of degree $t -1$ with coefficients, $\alpha_j$ in $F_q$: $P(x) = \sum^{t-1}_{j=0} \alpha_j x^j$ and publishes the encrypted shares: $Y_i = h_i^{P(i)}$.

   and publishes commitments to the coefficients $C_j = g^{\alpha_j}$.

3. Verification: A step in the verification process involves calculating $X_i = \prod_{j=0}^{t-1} {C_j^{i}}^j = g^{ \sum^{t-1}_{j=0} \alpha_j i^j}$ and then evaluating whether the bilinear equation $e(X_i,h_i) = e(g,Y_i)$ holds.

The question then is:

How is this possible? The use of bilinear maps implies using elliptic curves groups, while calculating $X_i$ involves both addition, multiplication and exponentiation, i.e. it requires a field. But since we have transitioned to the group of curve points when we calculated $Y_i$ and $C_j$ we will have lost the multiplicative and exponentiation operations, right? What am I missing here?

Answer 1

It is correct to me. Polynomial is not evaluated in the elliptic curve group $G$, but in $F_q$ (where $q$ is the order of $G$), which is a field because $q$ is a prime number.

To be clearer, I add brackets to the equation you gave: $$X_i = \prod_{j=0}^{t-1} (C_j)^{{i}^j} = \prod_{j=0}^{t-1} (g^{\alpha_j})^{ i^j}= (g)^{ \sum^{t-1}_{j=0} \alpha_j i^j}$$ You can see the polynomial is evaluated in the exponent, that why it is in $F_q$.

Maybe it is easier to see if using the Elliptic curve notation (let $P$ be a generator of the EC group $G$, i.e. $g$ in the above equation):

$$X_i = \sum_{j=0}^{t-1} ({i}^j\cdot C_j) = \sum_{j=0}^{t-1} ({i}^j\cdot a_j\cdot P)= (\sum_{j=0}^{t-1} a_j\cdot {i}^j )\cdot P$$