Skip to main content
optional step 3
Source Link
joro
  • 25.4k
  • 10
  • 66
  • 121

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?

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. 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?

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?

Source Link
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. 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?