0
$\begingroup$

Recently, I began researching fully homomorphic encryption. I'm reading the "Efficient Fully Homomorphic Encryption from (Standard) LWE" paper by Brakerski and Vaikuntanathan and came across this piece where they are multiplying two symbolic functions together where the function is defined as:

$$ f_{a,b}(x) = b-\langle a,x\rangle \mod q = b - \sum_{i=1}^{n}a[i]x[i] $$ and the multiplication: $$ f_{a,b}(x)f_{a',b'}(x) = (b-\sum a[i]x[i])\cdot(b'-\sum a'[i]x[i])=h_0+\sum_{i}h_i\cdot x[i]+\sum_{i,j} h_{i,j}\cdot x[i]\cdot x[j] $$

The introduction of $h$ confuses me. The paper says coefficients $h_{i,j}$ can be computed from $(a,b)$ and $(a',b')$ by opening the parenthesis of the expression above. How is this done? I’m particularly confused about the $h_i$ in the linear term. How is this found?

$\endgroup$

1 Answer 1

0
$\begingroup$

Note that $$\left(b-\sum a[i]x[i]\right)\cdot\left(b'-\sum a'[i]x[i]\right) =bb'-b\sum a'[i]x[i]-b'\sum a[i]x[i] +\sum\sum a[i]a'[j]x[i]x[j]$$ and we can extract the coefficients $$h_0=bb'$$ $$h_i=-ba'[i]-ba[i]$$ $$h_{i,j}=a[i]a'[j].$$

$\endgroup$

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.