Two varieties of finite automaton public key cryptosystem and digital signatures
type: Item
instance of: scholarly article
title: Two varieties of finite automaton public key cryptosystem and digital signatures
zbMATH Open document ID: 0614.94005
DOI: 10.1007/BF02943296
published in: Journal of Computer Science and Technology
publication date: 1986-01-01T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 94A60
Mathematics Subject Classification ID: 68Q70
Mathematics Subject Classification ID: 11T99
zbMATH DE Number: 3995583
zbMATH Keywords: privacy systems
zbMATH Keywords: public-key cryptosystem
zbMATH Keywords: secrecy systems
zbMATH Keywords: security
zbMATH Keywords: finite automata
zbMATH Keywords: weak inverses of nonlinear finite automata
zbMATH Keywords: factoring matrix polynomials over finite fields
zbMATH Keywords: digital signatures
author: Tao Renji
author: Shi-Hua Chen
reviewed by: Albert A. Mullin
describes a project that uses: McEliece
MaRDI profile type: Publication
cites work: New directions in cryptography
cites work: Trapdoor knapsacks without superincreasing structure
cites work: Embedding cryptographic trapdoors in arbitrary knapsack systems
cites work: A GENERALIZATION OF THE KNAPSACK ALGORITHM USING GALOIS FIELDS
cites work: A method for obtaining digital signatures and public-key cryptosystems
cites work: Q3932733
cites work: A PUBLIC-KEY CRYPTOSYSTEM BASED UPON EQUATIONS OVER A FINITE FIELD
cites work: A public key cryptosystem and a signature scheme based on discrete logarithms
cites work: Q3688303
cites work: Q3750124
cites work: Q3706505
cites work: Q3042397
cites work: On the structure of finite automata of which M' is a (weak) inverse with delay \(\tau\)
cites work: Q3939931
cites work: Algebraic coding theory
cites work: Factoring Polynomials Over Large Finite Fields
Recommended article: On finite automaton public-key cryptosystem
Recommended article: Cryptanalysis on a finite automaton public key cryptosystem
Recommended article: Q4525765
Recommended article: Finite Automata and Application to Cryptography
Recommended article: Q4499404
Recommended article: Q4251006
Recommended article: ABOUT 2-CASCADE FINITE AUTOMATA CRYPTOGRAPHIC GENERATORS AND THEIR CRYPTANALYSIS
Recommended article: Q5146196
Recommended article: Q3680287
Recommended article: Break Finite Automata Public Key Cryptosystem
description: scientific article; zbMATH DE number 3995583