This is related to cryptography and [this question](https://mathoverflow.net/questions/445899/complexity-of-finding-solutions-of-trapdoored-polynomial)
and [another question](https://mathoverflow.net/questions/445898/cryptography-signature-scheme-based-on-hardness-of-finding-points-on-varieties).

In short, we are asking about decomposing multivariate polynomial
as sum of perfect powers of linear polynomials.

Working over $\mathbb{Q}[x_1,\ldots,x_n]$

Let $\ell_i(x_i)$ be $k$ linear polynomials such
that the linear system $\ell_1=\ell_2=\cdots =\ell_k=0$ has
solution $S_0$.

Let $D$ be positive integer and define $F=\sum_{i=1}^k \ell_i^D$.

$F$ is given as sum of monomials and $F(S_0)=0$.

$\ell_i$ are kept secret as trapdoor.

>Q1 Are the there choices of $n,k,D,\ell_i$ such that
finding solution of $F=0$ is infeasible?

>Q2 Same as Q1, but in addition we are given one solution
$S_1$ such that $F(S_1)=0$.

>Q3 Same as Q1, but in addition we are given many solutions
$S_i$ such that $F(S_i)=0$.