From the paper Predicate Encryption Supporting Disjunctions, Polynomial Equations, and Inner Products, the vector of the secret key is generated from a polynomial $p(x)$. I understand the univariate polynomial, but what does the vector of a bivariate polynomial look like? For example:

univariate polynomial

$$p(x) = (x - a) \cdot (x - b) = x^2 -(a+b)x + ab$$

  • Secret vector $p = (1, -(a+b), ab)$
  • Vector $w$ (with attribute $a$) = $(a^2, a, 1)$ (I am not sure if I understand it correctly)
  • Inner product: $\left<p,w\right> = a^2 - a^2 - ab + ab = 0$

bivariate polynomial

$$p(x) = (x_1 - a) \cdot (x_2 - b)$$

  • Secret vector $p = ?$
  • Vector $w$ with attribute $a = ?$

Many thanks.


1 Answer 1


In general, to encode a polynomial $p(x) = a_n x^n + a_{n-1} x^{n-1} + ... a_1 x + a_0$, $$\mathbb{p} = (a_n, a_{n-1}, ... a_1, a_0)$$ and $$\mathbb{w} = (x^n, x^{n-1}, ... x, 1)$$

So for your univariate case, $\mathbb{w} = (x^2, x, 1)$. You can see that $\left<\mathbb{p}, \mathbb{w} \right> = p(x)$, and you substitute the attribute as you need. So I think your univariate case is correct.

For the bivariate case, it's the same, but with mixed powers. You'll have terms like $x_1^i x_2^j$, where $i+j \leq n$. So in the general case where $n=2$ with two variables / attributes, you have:

$$ p(x_1, x_2) = a_{20}x_1^2 + a_{11}x_1 x_2 + a_{02} x_2^2 + a_{10}x_1 + a_{01}x_2 + a_{00}$$

In your case, you have:

$$ p(x_1, x_2) = x_1 x_2 - x_1 b - x_2 a + ab$$

So $a_{20} = a_{02} = 0$, $a_{11} = 1$, $a_{10} = -b$, $a_{01} = -a$, and $a_{00} = ab$. Finally,

$$\mathbb{p} = (0,1,0,-b,-a,ab)$$


$$\mathbb{w} = (x_1^2, x_1 x_2, x_2^2, x_1, x_2, 1)$$

Again, you can see that $\left<\mathbb{p}, \mathbb{w} \right> = p(x_1, x_2)$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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