2
$\begingroup$

Related to this question Complexity of finding solutions of trapdoored polynomial.

I am trying to build signature scheme based on hardness of finding points on varieties.

Let $K$ be field and $M=K[x_1,...x_n,y_1,...,y_m]$.

Let $V$ be the variety $f_1(x_i,y_i)=...f_k(x_i,y_i)=0$.

Alice constructs $V$ with some secret $S$ (trapdoor) such that for all $y_i$, Alice can efficiently find $X_i$ such that $F(X_i,y_i=Y_i)=0$. Correctness of the signature of $Y_i$ is the vanishing of $F$.

So $V$ must satisfy the following properties:

  1. For all $y_i$, Alice can find efficiently $X_i$ such that $F$ vanishes.
  2. Without knowing the secret $S$, adversary can't efficiently find points on $V$ given $Y_i$.
  3. (optional, feel free to skip) Given many points on $V$, resulting from valid signatures, adversary can't find the secret $S$ or otherwise forge signatures.

Potential approach is to start from "basis" and then obfuscate them.

I am looking for hardness results and even high degree polynomial time would be of interest.

Q1 What complexity of hardness can we get for the above construction?

$\endgroup$
3
  • $\begingroup$ Here is my similar question, but I was more focused on a one-time-signature scheme. mathoverflow.net/questions/435613/… $\endgroup$ Commented May 1, 2023 at 11:38
  • $\begingroup$ @JosephVanName For one time usage I suspect modification of the linked trapdoor question might work. $\endgroup$ Commented May 1, 2023 at 13:20
  • $\begingroup$ @JosephVanName I tried another trapdoor at mathoverflow.net/questions/445974/… $\endgroup$ Commented May 2, 2023 at 9:42

0

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.