I wonder how well arbitrary Diophantine equations can be used to make one time digital signature schemes.
For our one-time digital signature scheme, the public key is a collection of polynomials $f_1(x_1,\dots,x_n),\dots,f_r(x_1,\dots,x_n)$ with integer coefficients. The private key is a collection of integers $a_1,\dots,a_n$ where $f_1(a_1,\dots,a_n)=\dots=f_r(a_1,\dots,a_n)=0$. Let $H$ be a cryptographic hash function where $H(\mathbf{x})$ is a prime number for each input $\mathbf{x}$.
Key generation: A simple way to generate a key is to first select the private key $a_1,\dots,a_n$ at random. Then one can solve for $f_1(a_1,\dots,a_n)=\dots=f_r(a_1,\dots,a_n)=0$ since this equation is a linear Diophantine equation where we solve for the coefficients of $f_1,\dots,f_r$.
Signing: To sign a document $\mathbf{x}$, one first computes the large prime $p=H(\mathbf{x})$ where $H$ is a cryptographic hash function and then the signature is a tuple $(b_1,\dots,b_n)\in\mathbb{Z}^n$ where $b_i=a_i\mod p$ for $1\leq i\leq n$.
Verification: Suppose that $\mathbf{x}$ is a document. Then one accepts the signature $(b_1,\dots,b_n)$ iff $$f_1(b_1,\dots,b_n)\equiv\dots\equiv f_r(b_1,\dots,b_n)\equiv 0\mod H(\mathbf{x}).$$
Limited use: One can only use a public-private key pair to sign a limited number of documents, and every additional signature weakens the cryptographic security of this signature scheme. If $\mathbf{x}_1,\dots,\mathbf{x}_v$ are documents and $(b_{i,1},\dots,b_{i,n})$ is a signature of $\mathbf{x}_i$ for $1\leq i\leq v$, then one can compute a unique tuple $(c_1,\dots,c_n)$ where $c_j\equiv b_{i,j}\mod H(\mathbf{x}_i)$ for $1\leq j\leq n,1\leq i\leq v$ and where if $2q+1=H(\mathbf{x}_1)\dots H(\mathbf{x}_r)$, then $-q\leq c_j\leq q$ for $1\leq j\leq n$. If $-q\leq a_j\leq q$ for $1\leq j\leq n$, then $(c_1,\dots,c_n)=(a_1,\dots,a_n)$ which means that we have recovered the private key. I therefore only expect for this signature scheme to be reasonable for generating a single signature from a public-private key pair.
The Merkle signature scheme using Merkle trees can take any one-time signature scheme and return a signature scheme that can be used to sign a large but limited number of documents. One-time signatures may also be useful to mitigate the risk of double spending in unconfirmed cryptocurrency transactions.
Can this one-time digital signature scheme be secure if we use a good key pair generation algorithm?
I would consider this digital signature scheme to be questionable in the case where the cryptographic hash function $H$ is replaced with just the identity function and where an attacker is assumed to be able to select an arbitrary prime $q$ and trick the signer into signing $q$ in order to use the signature of $q$ to forge a new signature of a different prime number. To make this problem more tractible, I also would accept quantum attacks.
NP-completeness
The problem of solving a system of equations $f_1(x_1,\dots,x_n)=1,\dots,f_r(x_1,\dots,x_n)=1$ in the field $F_2$ is NP-complete whenever $f_1,\dots,f_r$ are polynomials with coefficients in $F_2$. This is because $f_1(x_1,\dots,x_n)\cdots f_r(x_1,\dots,x_n)=1$ is actually an instance of the Boolean satisfiability problem where the expression $f_1(x_1,\dots,x_n)\cdots f_r(x_1,\dots,x_n)$ is general enough to include all formulae in conjunctive normal form. Since the Boolean satisfiability problem for formulae in formulae in conjunctive normal form is NP-complete, the problem of solving a system of equations $f_1(x_1,\dots,x_n)=1,\dots,f_r(x_1,\dots,x_n)=1$ in the field $F_2$ is NP-complete as well.
With that being said, there have been examples of public key cryptosystems based on NP-complete problems which have been broken in the past including the Merkle–Hellman knapsack cryptosystem.
A universal algebraic context
This signature scheme can be generalized to a universal algebraic context. Suppose that $\mathcal{X}$ is an algebraic structure. The public key is a collection of equations $f_1(x_1,\dots,x_n)=g_1(x_1,\dots,x_n),\dots,f_r(x_1,\dots,x_n)=g_r(x_1,\dots,x_n)$ where $f_1,\dots,f_r,g_1,\dots,g_r$ are terms. The private key is a solution $a_1,\dots,a_n$ to all these equations. A signature of a document $\mathbf{x}$ consists of a surjective homomorphism $H(\mathbf{x}):\mathcal{X}\rightarrow\mathcal{X}_{\mathbf{x}}$ along with a solution to the $r$ equations in the structure $\mathcal{X}_{\mathbf{x}}$. The Lamport one-time signature scheme is a special case of this universal algebraic signature scheme when $\mathcal{X}$ is a direct product $\mathcal{X}=\prod_{i\in I}\mathcal{X}_i$, where the homomorphisms $H(\mathbf{x})$ are projections onto some of the coordinates and where each $\mathcal{X}_i$ has a one-way function as a fundamental operation (along with fundamental constants for all elements in $\mathcal{X}_i$).
