UOV signature scheme, how does the affine transformation work? What does the composition of the core map and the affine map yield?
I am having trouble understanding part of the UOV scheme, i get how it works except for when it comes to composing the core map F with an affine transformation say T, which i understand to be an invertible square matrix? I understand F to be composed of the o number of oil-vinegar polynomials where o is the number of oil variables. So does this mean that each multivariate equation in the core map F is multiplied by a square matrix representing the affine map T? What exactly would be the product of this multiplication? Is each multivariate oil vinegar equation treated as a 1x1 matrix and multiplied with T? I know that the map T is used to do a change of basis on the system but the public key is supposed to be a system of multivariate equations so could someone help clarify what the composition of the core map F and the affine map T actually yields? Perhaps with a small example if possible? For example in the case where o = 2 if i say the core map F is given by
$F = [3x_0^2 - 4x_0x_1 - 4x_1^2 + 8x_0x_2 + 11x_2^2 - 2x_0x_3 - x_1x_3 + 9x_2x_3 + 12x_3^2 + 7x_0x_4 - 11x_1x_4 - 9x_2x_4 - 2x_3x_4 + 3x_0x_5 + 5x_1x_5 + 14x_2x_5 - 11x_3x_5]$
$[-6x_0^2 + 10x_0x_1 + 10x_1^2 + 13x_0x_2 + 4x_1x_2 + 7x_2^2 - 7x_0x_3 - x_1x_3 - 13x_2x_3 + 4x_3^2 + 6x_0x_4 + 15x_1x_4 - 11x_2x_4 - 12x_3x_4 - 12x_0x_5 + 7x_1x_5 - 13x_2x_5 - 9x_3x_5]$
And an affine transformation $T$ given by:
$\begin{bmatrix} 18 & 23 & 14 & 1 & 6 & 21 \\ 24 & 3 & 3 & 0 & 2 & 0 \\ 17 & 25 & 2 & 16 & 23 & 8 \\ 8 & 21 & 16 & 5 & 1 & 9 \\ 14 & 28 & 8 & 17& 12& 12 \\ 6 & 24& 18& 19& 3& 1& \end{bmatrix}$
what would the public key/the composition of the core map F and the map T be?
public-key cryptanalysis post-quantum-cryptography matrix-multiplication
d_s_md_s_m
The secret polynomials are multivariate polynomials whose oil-oil terms have coefficient zero. You can represent it as a sum of terms, or as a vector-matrix-vector product. Take for example the polynomial of your example, $F_0(x_0, \ldots, x_5) = x^2_0 − 4x_0x_1 − 4x^2_1 + 8x_0x_2 + 11x_2^2 − 2x_0x_3 − x_1x_3 + 9x_2x_3 + 12x^2_3 + 7x_0x_4 − 11x_1x_4 − 9x_2x_4 − 2x_3x_4+3x_0x_5+5x_1x_5 + 14x_2x_5 − 11x_3x_5$. Using the vector notation $\mathbf{x}^\mathsf{T} = (x_0, x_1, \ldots, x_5)$ we can write this polynomial as the following product: $$ F_0(\mathbf{x}) = \mathbf{x}^\mathsf{T} \left( \begin{matrix} 1 & -4 & 8 & -2 & 7 & 3 \\ 0 & -4 & 0 & -1 & -11 & 5 \\ 0 & 0 & 0 & 9 & -9 & 14 \\ 0 & 0 & 0 & 12 & -2 & -11 \\ 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 \end{matrix} \right) \mathbf{x} \enspace .$$ The coefficients in the matrix are the same as in the sum-of-terms representation. Note that in this matrix representation, the bottom-right block consists of zeros; this reflects the fact that oil-times-oil terms have coefficient zero. Also note that this matrix is not unique: whenever $F_i(\mathbf{x}) = \mathbf{x}^\mathsf{T} M_{F_i} \mathbf{x}$ then for any skew-symmetric matrix $A$ (i.e. such that $A^\mathsf{T} = -A$) you can also write $F_i(\mathbf{x}) = \mathbf{x}^\mathsf{T}(M_{F_i}+A)\mathbf{x}$. In particular, this means that (assuming odd characteristic) it is always possible to choose the central matrix to be symmetric by computing $\frac{1}{2}(M_{F_i}+M_{F_i}^\mathsf{T})$.
The secret linear transform $\mathcal{T}$ can also be represented in two ways. You give the matrix representation $$ T = \left( \begin{matrix} 18 & 23 & 14 & 1 & 6 & 21 \\ 24 & 3 & 3 & 0 & 2 & 0 \\ 17 & 25 & 2 & 16 & 23 & 8 \\ 8 & 21 & 16& 5 & 1 & 9 \\ 14 & 28 & 8 & 17 & 12 & 12 \\ 6 & 24 & 18 & 19 & 3 & 1 \end{matrix} \right) \enspace ,$$ in which case $\mathcal{T}(\mathbf{x}) = T\mathbf{x}$. You could also have chosen the list of polynomials representation, in which case there are 6 polynomials, $\mathcal{T}_0$ throught $\mathcal{T}_5$. For illustration, the first polynomial is given by $\mathcal{T}_0(x_0, x_1, x_2, x_3, x_4, x_5) = 18 x_0 + 23 x_1 + 14 x_2 + 1 x_3 + 6 x_4 + 21 x_5$.
To compute the composition $F \circ \mathcal{T}$ you must first choose a representation. In the polynomial representation we have $F \circ \mathcal{T} (\mathbf{x}) = F(\mathcal{T}(\mathbf{x})) = F(\mathcal{T}_0(\mathbf{x}), \mathcal{T}_1(\mathbf{x}), \ldots, \mathcal{T}_5(\mathbf{x}))$. So you can compute $F \circ \mathcal{T}$ by starting with a copy of $F$ and then substituting every occurrence of $x_i$ with $\mathcal{T}(\mathbf{x}) = \mathcal{T}(x_0, x_1, x_2, x_3, x_4, x_5)$. But make sure to keep track of which occurrences of $x_i$ appear as a result of the substitution, because they obviously shouldn't be substituted twice.
In the matrix representation, we have $F_i \circ \mathcal{T} (\mathbf{x}) = \mathcal{T}(\mathbf{x})^\mathsf{T} M_{F_i} \mathcal{T}(\mathbf{x}) = (T\mathbf{x})^\mathsf{T} M_{F_i} (T \mathbf{x}) = \mathbf{x}^\mathsf{T} (T^\mathsf{T} M_{F_i} T) \mathbf{x}$. So a matrix representation $M_{F_i \circ \mathcal{T}}$ of the composition can be computed just by sandwiching $M_{F_i}$ between $T^\mathsf{T}$ and $T$, i.e., $M_{F_i \circ \mathcal{T}} = T^\mathsf{T} M_{F_i} T$.
To complete the example you started, let's assume we're working modulo 31 (because otherwise the numbers get quite large). Then we have $$ M_{F_0 \circ \mathcal{T}} \cong T^\mathsf{T} M_{F_i} T = \left( \begin{matrix} 6 & 25 & 19 & 19 & 3 & 26 \\ 22 & 29 & 3 & 29 & 28 & 2 \\ 8 & 15 & 12 & 18 & 6 & 7 \\ 28 & 1 & 24 & 17 & 4 & 1 \\ 6 & 21 & 18 & 5 & 30 & 23 \\ 11 & 23 & 8 & 15 & 5 & 5 \end{matrix}\right) \cong \left( \begin{matrix} 6 & 8 & 29 & 8 & 20 & 3 \\ 8 & 29 & 9 & 15 & 9 & 28 \\ 29 & 19 & 12 & 21 & 12 & 23 \\ 8 & 15 & 21 & 17 & 20 & 8 \\ 20 & 9 & 12 & 20 & 30 & 14 \\ 3 & 28 & 23 & 8 & 14 & 5 \end{matrix}\right) \cong \left( \begin{matrix} 6 & 16 & 27 & 16 & 9 & 6 \\ 0 & 29 & 18 & 30 & 18 & 25 \\ 0 & 0 & 12 & 11 & 24 & 15 \\ 0 & 0 & 0 & 17 & 9 & 16 \\ 0 & 0 & 0 & 0 & 30 & 28 \\ 0 & 0 & 0 & 0 & 0 & 5 \end{matrix}\right) \enspace .$$ Here the congruence sign ($\cong$) indicates that the matrices represent the same quadratic form, i.e., up to addition of skew-symmetric matrices. In other words, after sandwiching them between $\mathbf{x}^\mathsf{T}$ and $\mathbf{x}$ they will result in the same polynomial. From the last upper triangular matrix we can read out the representation of the polynomial as a sum of terms, namely $$ F_0 \circ \mathcal{T}(x_0, x_1, x_2, x_3, x_4, x_5) = 6x_0^2 + 16x_0x_1 + 27x_0x_2 + 16x_0x_3 + 9x_0x_4 + 6x_0x_5 + 29x_1^2 + 18x_1x_2 + 30x_1x_3 + 18 x_1x_4 + 25x_1x_5 + 12x_2^2 + 11x_2x_3 + 24x_2x_4 + 15x_2x_5 + 17x_3^2 + 9x_3x_4 + 16x_3x_5 + 30x_4^2 + 28x_4x_5 + 5x_5^2 \enspace .$$ This should be the same result as obtained through the substitution method applied to the polynomial representations.
One more thing: it is a good idea to avoid mixing homogeneous quadratic polynomials (i.e., without linear or constant terms) with affine transforms (i.e., with constant terms) -- or vice versa. In other words, whenever your secret polynomials are homogeneous, your secret transforms should be linear; whenever they are inhomogeneous, they should be affine. This guarantees that the public polynomials are (in)homogeneous whenever the secret ones are.
AlanAlan
Thanks for contributing an answer to Cryptography Stack Exchange!
Not the answer you're looking for? Browse other questions tagged public-key cryptanalysis post-quantum-cryptography matrix-multiplication or ask your own question.
Questions on rank-attacks in Multivariate Cryptography
What is hardened SHA-1, how does it work and how much protection does it offer?
Usage of pairings in proxy re-encryption algorithm
What's a quadratic map and how do I invert it?
How does openssl signature verification work?
How does the Signature Scheme in Picnic Works
What are the security implications of knowing the private polynomial $\mathcal{F}$