In this paper by Kate et al, a constant size polynomial commitment scheme is described.

The commitment scheme assumes a public reference string:

\begin{align*} \Big\{ \{ g^{ \tau^i }, g^{ \alpha \tau^i } \}_{i=-d}^{d} \}, \ \ \{ h^{ \tau^i }, h^{ \alpha \tau^i } \}_{i=-d}^{d}, \ \ e(g, h^{\alpha} ) \Big\} \end{align*}

where $\alpha, \tau \in \mathbb{F}$ are two secret values and $d$ is a large integer. The commitment goes as follows:

  • Commit: let $f \in \mathbb{F}[x]$ with degree at most $d$. The commitment is a group element $F$ defined by \begin{align*} F := g^{\alpha f(\tau) }. \end{align*}

  • To open the commitment to a certain value $z$, compute the proof $W$ which is another field element, defined by: \begin{align*} W := g^{ \frac{ f(\tau) -f(z) }{ \tau-z } } \end{align*}

  • To verify a correct opening given $(F, z, (v, W) )$: \begin{align*} e(W, h^{\alpha \tau} ) \cdot e(g^v \cdot W^{-z}, h^{\alpha} ) == e(F, h^{\alpha } ) \end{align*}

We note that the the commitment to the polynomial $f$ is constant size, as well as the proof of correct opening for a given value $z$.

My question is,

Given the above reference string, or a similar reference string of roughly the same size (linear in $d$), is there a known constant size commitment scheme to a bivariate polynomial?


I think the main issue for the bivariate polynomials is the coefficients of the polynomial $f(x,y)$. Since $\tau$ is a secret value then to calculate $g^{\alpha f(\tau)}$ we can use the public parameters. As you know, the users can obtain the coefficients based on a standard basis and then solve a multiplication. $$g^{\alpha f(\tau)}=\prod_{i=0}^{n}{(g^{ \alpha \tau^i })}^{f_i}$$ For a univariate polynomial, the coefficients of $f_i$ are constant while if we consider bivariate polynomials then it is necessary to evaluate a second polynomial on the $\tau$. Precisely, the standard basis $(1,X,X^2,...,X^d)$ forms the univariate polynomials and the coefficients for a bivariate polynomial are changing by the second variable.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.