Homogeneous quadratic parts of polynomials in Unbalanced Oil and Vinegar

37 Views Asked by At

In the book Multivariate Public Key Cryptography, the author describes the polynomials in the cryptographic system Unbalanced Oil and Vinegar in the following way:

Define $V=\{1,\dots,v\}$ and $O=\{v+1,\dots,n\}$. The central map is $\mathcal{F}=(f^{(1)},\dots, f^{(o)})$ where the polynomials $f^{(i)}$ are of the form:

$$f^{(i)} = \sum_{j,k\in V} \alpha^{(i)}_{j,k}x_jx_k + \sum_{j\in V,k\in O}\beta^{(i)}_{j,k}x_jx_k + \sum_{j\in V\cup O}\gamma^{(i)}_j x_j + \delta^{(i)}\quad (i=1,\dots,o).$$

The author then makes the following claim:

The homogeneous part of the polynomials $f^{(i)}$ can be rewritten as $$\hat{f}^{(i)}(\mathbf{x}) = \mathbf{x}^T\cdot F^{(i)}\cdot \mathbf{x}$$ with $$F^{(i)} = \begin{pmatrix}\star_{v\times v} & \star_{v\times o}\\ \star_{o\times v} & 0_{o\times o}\end{pmatrix}$$ where $\star$ means non-zero elements.

My question is then: Is the last part of the matrix full of zeros because there is no term in the $f^{(i)}$ of the form $\sum_{j,k\in O}\text{[something]}$?

1

There are 1 best solutions below

0
On BEST ANSWER

Yes, that's right. In fact we may write $f^{(i)}(\mathbf{x})=\mathbf{x}^T F^{(i)}\mathbf{x}+(\mathbf{y}^{(i)})^T\mathbf{x}+\delta^{(i)}$ where

$$ F^{(i)}=\begin{bmatrix} A^{(i)} & B^{(i)} \\ 0 & 0 \end{bmatrix} $$

and $A^{(i)}=[\alpha_{jk}^{(i)}]$, $B^{(i)}=[\beta_{jk}^{(i)}]$, $\mathbf{y}^{(i)}=[\gamma_j^{(i)}]$. It's possible to write the corner blocks $B$ and $0$ differently and get the same result, for example with $\frac{1}{2}B$ and $\frac{1}{2}B^T$ (resp.). If the corner blocks are $C$ and $D$ (resp.), the only constraint is that $C+D^T=B$ to get the same quadratic form.

To understand why this is all true, set $|V|=2,|O|=2$ and write everything out explicitly.