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:
- For all $y_i$, Alice can find efficiently $X_i$ such that $F$ vanishes.
- Without knowing the secret $S$, adversary can't efficiently find points on $V$ given $Y_i$.
- (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?