Skip to main content
2 of 2
optional step 3
joro
  • 25.4k
  • 10
  • 66
  • 121

Cryptography signature scheme based on hardness of finding points on varieties?

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?

joro
  • 25.4k
  • 10
  • 66
  • 121