Topic: Digital signatures from algebraic structures (Read 62 times)

One can generalize the Lamport one-time signature scheme to a signature scheme for potentially many kinds of algebraic structures. The signature scheme looks like this. I produced this template for digital signatures myself. I do not know how secure they all are, but there are reasons to believe that the ones I am going to mention are secure.

An algebraic structure X will be publicly available.

1. The public key will be a pair of polynomials f,g

2. The private key will be a collection of elements a_1,...,a_n where f(a_1,...,a_n)=g(a_1,...,a_n).

3. To sign a message x, one computes a congruence E=H(x) (H is a cryptographic hash function) and sends the data E along with the equivalence classes a_1/E,...,a_n/E.

4. To verify the message x, one verifies that E=H(x) and f(a_1/E,...,a_n/E)=g(a_1/E,...,a_n/E).

Example 0: I will leave it to the reader to see how Lamport's one-time signature scheme is a special case of this framework. Since hash based signatures fall into this framework, and since hash based signatures are more secure than all other digital signature algorithms such as ECDSA, it is possible for that our framework is useful for cryptocurrency technologies including Bitcoin.

Example 1: We can set X to be the ring of integers. The problem of solving a Diophantine equation modulo 2 is NP-complete since satisfiability is a special case of this problem. And the problem of solving an arbitrary Diophantine equation over the field of integers is undecidable. And in practice, there is no good method that solves Diophantine equations in the average case (many NP-complete problems become really easy in the average case). If we take things modulo p, it is easier to solve this problem. We can try to solve the equation f(x_1 mod p,...,x_n mod p)=g(x_1 mod p,...,x_n mod p) in the algebraic closure using Grobner bases, but we can only use solutions in the field with prime order. In practice, one cannot use this signature more than once because the Chinese remainder theorem can be used to break this signature scheme if we sign too many things with it.

Example 2: Given an algebraic structure Z, we can set X=Z[t_1,...,t_r] which is the algebra of polynomials over Z, and given b_1,...,b_r in Z, we can define the congruence E by setting p(t_1,...,t_r)=q(t_1,...,t_r) mod E precisely when p(b_1,...,b_r)=q(b_1,...,b_r). For example, we can let Z just be a finite field.

Example 3: We may be able to exploit the Galois connection between collections of functions and collections of equivalence relations on a set to optimize our algebraic structure. If we are given a collection G of equivalence relations on a set X, then we can set a function f to be a fundamental operation if each E in G is a congruence with respect to (X,f). In this case, we have a maximal quantity of fundamental operations to choose from to build our polynomials so that it will be harder to solve the equation f(x_1/E,...,x_n/E)=g(x_1/E,...,x_n/E).

-Joseph Van Name Ph.D.