2
$\begingroup$

Related to this question Cryptography signature scheme based on hardness of finding points on varieties.

Working over $K=\mathbb{Q}[x_1,...,x_n,y_1,...y_m]$.

By abuse of notation, for polynomial $f$, let $f(x_i)$ mean $f$ depends only on the $x$ variables and $f(y_i)$ mean it depends only on $y$ variables.

Let $f_i=g_i \cdot (h_i(y_i)+l_i(x_i))$ where $l_i$ is linear and depends on only $x$ variables and $h_i$ depends on only $y$ variables. There are no restrictions on $g_i$.

Let $F=\sum_{i=1}^k f_i$ be given as sum of monomials.

If we know the set of $f_i$ (the secret trapdoor) and we are given $y_i$ , for sufficiently general $l_i$, we can find the solutions of $F=0$ as the solutions of the linear in $x_i$ system of linear equations $(h_i(y_i)+l_i(x_i))=0$

Q1 Can we find $f_i$ such that solving $F=0$ is hard without knowing the trapdoor?

Q2 Assume an oracle gives many solutions to $F=0$, can we still get hardness results for new solutions?

Working symbolically trying to equate coefficients using sagmath's groebner basis takes at least one CPU hour (I didn't wait to finish) for $n=m=2,\deg f_i=3$, which defines elliptic curve.

Improve this question
$\endgroup$
2
  • $\begingroup$ Your notation is a bit confusing. $f(x_i)$ suggests that $f$ depends only on $x_i$, but I think you intended to say $f$ depends on more than one variable since you stated "let $f(x_i)$ mean $f$ depends only on the $x$ variables". $\endgroup$
    – Pedro Juan Soto
    Commented May 9, 2023 at 20:55
  • 1
    $\begingroup$ @PedroJuanSoto Thanks. I was trying to avoid the confusion by writing: let f(x_i) mean f depends only on the x variables $\endgroup$
    – joro
    Commented May 10, 2023 at 6:28

0

Reset to default

You must log in to answer this question.