problems ([@DBLP:journals/fttcs/ChenKW11; @DBLP:conf/eurocrypt/Perret05]). To go along with the proof of Theorem \[th:ip\], we design Algorithm \[al:ip\] at the end of Section \[s:ip\].

Normalization - Canonical form of [`IP1S`]{} {#s:normalization}
============================================

In this section, we prove Theorem \[th:normal\]. In other words, we explain how to reduce, under Assumption \[as:regular\], any quadratic homogeneous instance $({{\mathbf}{f}},{{\mathbf}{g}}) \in
{{\mathbb}{K}}[x_1,\ldots,x_n]^m \times {{\mathbb}{K}}[x_1,\ldots,x_n]^m$ of [`IP1S`]{}to a suitable canonical form, *i.e.* an instance of [`IP1S`]{}where all the Hessian matrices are invertible and the first two equal the same diagonal invertible matrix. We emphasize that the reduction presented is randomized.

#### Homogenization {#par:homo}

We show here that the equivalence problem over inhomogeneous polynomials with affine transformation on the variables reduces to the equivalence problem over homogeneous polynomials with linear transformation on the variables. To do so, we simply homogenize the polynomials. Let $x_0$ be a new variable. For any polynomial $p\in{{\mathbb}{K}}[{{\mathbf}{x}}]$ of degree $2$, we denote by $p^{\star}(x_0,x_1,\ldots,x_n)=x_0^2\,p(x_1/x_0,\ldots, x_n/x_0)$ its *homogenization*.

\[prop:homo\] ${\texttt{IP1S}\xspace}$ with quadratic polynomials and affine transformation on the variables can be reduced in polynomial-time to [`IP1S`]{}with homogeneous quadratic polynomials and linear transformation on the variables.

Let $({{\mathbf}{f}},{{\mathbf}{g}})\in{{\mathbb}{K}}[{{\mathbf}{x}}]^m \times {{\mathbb}{K}}[{{\mathbf}{x}}]^m$ be inhomogeneous polynomials of degree $2$. We consider the transformation which maps $({{\mathbf}{f}},{{\mathbf}{g}})$ to $\big({{\mathbf}{f}}^{\star}=(f_0^{\star}=x_0^2,f_1^{\star},\ldots,f_m^{\star}),
  {{\mathbf}{g}}^{\star}=(g_0^{\star}=x_0^2,g_1^{\star},\ldots,g_m^{\star})\big)$. 