Two varieties of finite automaton public key cryptosystem and digital signatures (Q1820751)

Recall that in a public-key cryptosystem (PKCS) each user has a public encryption algorithm E and a secret decryption algorithm D such that D is NP-hard to compute from E. Of course, there are many NP-hard cryptosystems which are easy to penetrate so crypto-complexity is clearly inequivalent to computational complexity. I.e., secure secrecy systems must not be based on NP-hardness alone. There are many ways to implement a PKCS with varying degrees of security; e.g., by using a trapdoor word problem, knapsack or factorization. The autors' scheme, using finite automata theory, is based on the extreme difficulty, in general, of finding weak inverses of nonlinear finite automata and of factoring matrix polynomials over finite fields. Since E can be constructed to be an inverse of D, the authors' cryptosystems can be used to implement digital signatures. They claim that their type of PKCS is secure, easy to implement and uses a relatively small public key in size, since it is a sequential or stream PKCS. As yet, there is no effective method to estimate a sharp lower bound on the computing time and storage requirements to determine weak inverses of nonlinear finite automata.