×

Input-trees of finite automata and application to cryptanalysis. (English) Zbl 0976.94024

Summary: In this paper, weights of output sets and of input sets for finite automata are discussed. For a weakly invertible finite automaton, we prove that for states with minimal output weight, the distribution of input sets is uniform. Then for a kind of compound finite automata, we give weights of output sets and of input sets explicitly, and a characterization of their input-trees. For finite automaton public key cryptosystems, of which automata in public keys belong to such a kind of compound finite automata, we evaluate search amounts of exhaust search algorithms in average case and in worse case for both encryption and signature, and successful probabilities of stochastic search algorithms for both encryption and signature. In addition, a result on mutual invertibility of finite automata is also given.

MSC:

94A60 Cryptography
68Q45 Formal languages and automata
68P25 Data encryption (aspects in computer science)

Software:

McEliece
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Diffie W, Hellman M. New directions in cryptography.IEEE Trans. Information Theory, 1976, IT-22: 644–654. · Zbl 0435.94018 · doi:10.1109/TIT.1976.1055638
[2] Rivest R, Shamir A, Adleman L. A method for obtaining digital signatures and public-key cryptosystems.Communications of the ACM, 1978, 21: 120–126. · Zbl 0368.94005 · doi:10.1145/359340.359342
[3] Merkle R C, Hellman M E. Hiding information and signatures in trapdoor knapsacks.IEEE Trans. Information Theory, 1978, 24: 525–530. · doi:10.1109/TIT.1978.1055927
[4] McEliece R J. A public-key cryptosystem based on algebraic coding theory. DSN Progress Report, 1978, pp. 42–44.
[5] ElGamal T. A public key cryptosystem and a signature scheme based on discrete logarithms.IEEE Trans. Information Theory, 1985, IT-31: 469–472. · Zbl 0571.94014 · doi:10.1109/TIT.1985.1057074
[6] Koblitz N. Elliptic curve cryptosystems.Mathematics of Computation, 1987, 48: 203–209. · Zbl 0622.94015 · doi:10.1090/S0025-5718-1987-0866109-5
[7] Salomaa A. Public-Key Cryptography. Springer-Verlag, Berlin, 1990. · Zbl 0712.68003
[8] Smith P. LUC public-key encryption.Dr. Dobb’s Journal, 1993, 18: 44–49.
[9] Tao R, Chen S. A finite automaton public key cryptosystem and digital signatures.Chinese J. of Computers, 1985, 8: 401–409 (in Chinese).
[10] Tao R, Chen S. Two varieties of finite automaton public key cryptosystem and digital signatures.J. of Computer Science and Technology, 1986, 1: 9–18. · Zbl 0614.94005 · doi:10.1007/BF02943296
[11] Tao R, Chen S, Chen X. FAPKC3: A new finite automaton public key cryptosystem.J. of Computer Science and Technology, 1997, 12: 289–305. · Zbl 05471900 · doi:10.1007/BF02943149
[12] Tao R, Chen S. A variant of the public key cryptosystem FAPKC3.J. of Network and Computer Applications, 1997, 20: 283–303. · doi:10.1006/jnca.1997.0057
[13] Tao R, Chen S. A note on the public key cryptosystem FAPKC3. InAdvances in Cryptology–CHI-NACRYPT’98, Science Press, Beijing, 1998.
[14] Tao R, Chen S. The generalization of public key cryptosystem FAPKC4.Chinese Science Bulletin, 1999, 44: 784–790. · Zbl 1020.68505 · doi:10.1007/BF02885019
[15] Tao R, Chen S. On finite automaton public key cryptosystem.Theoretical Computer Science, 1999, 226: 143–172. · Zbl 0956.94011 · doi:10.1016/S0304-3975(99)00070-5
[16] Dai D, Wu K, Zhang H. Cryptanalysis on a finite automaton public key cryptosystem.Science in China, Ser. A, 1996, 39: 27–36. · Zbl 0869.94015
[17] Tao R. On invertibility of some compound finite automata. Technical Report No. ISCAS-LCS-95-06, Laboratory for Computer Science, Institute of Software, Chinese Academy of Sciences, Beijing, June 1995.
[18] Bao F, Igarashi Y. Break finite automata public key cryptosystem. InICALP’95, Automata, Languages and Programming, LNCS 944, Springer-Verlag, Berlin, 1995, pp. 147–158.
[19] Tao R. OnR a R b transformation and inversion of compound finite automata. Technical Report No. ISCAS-LCS-95-10, Laboratory for Computer Science, Institute of Software, Chinese Academy of Sciences, Beijing, Sept. 1995.
[20] Wang H. TheR a R b representation of a class of the reduced echelon matrices.J. of Software, 1997, 8: 772–780. (in Chinese)
[21] Tao R, Feng P. On relations betweenR a R b transformation and canonical diagonal form of {\(\lambda\)}-matrix.Science in China, Ser. E, 1997, 40: 258–268. · Zbl 0884.15006
[22] Tao R. Several specific factorizations of matrix polynomials.Chinese J. of Computers, 1999, 22: 1–10. (in Chinese)
[23] Qin Z, Zhang H. Cryptanalysis of finite automaton public key cryptosystems. InAdvances in Cryptology– CHINACRYPT’96, Science Press, Beijing, 1996, pp. 75–86. (in Chinese)
[24] Dai Z. A class of separable nonlinear finite automata–and an analysis of a certain typed FA based public key encryption and signature scheme. InAdvances in Cryptology–CHINACRYPT’96, Science Press, Beijing, 1996, pp. 87–94. (in Chinese)
[25] Bao F. Increasing ranks of linear finite automata and complexity of FA public key cryptosystem.Science in China, Ser. A, 1994, 37: 504–512. · Zbl 0811.68078
[26] Bao F, Igarashi Y. A randomized algorithm to finite automata public key cryptosystem. InProc. ISACC’94, LNCS 834, Springer-Verlag, Berlin, 1994, pp. 678–686. · Zbl 0953.94500
[27] Tao R. Analyzing several search attacks on FAPKC1. Unpublished Manuscript, 1994. (in Chinese)
[28] Qin Z, Zhang H. Enumeration of sequences in finite automata with application to cryptanalysis. InAdvances in Cryptology–CHINACRYPT’94, Science Press, Beijing, 1994, pp. 112–119. (in Chinese)
[29] Qin Z, Zhang H. The attack algorithmAtM to finite automation public key cryptosystems.Chinese J. of Computers, 1995, 18: 199–204. (in Chinese)
[30] Tao R, Chen S. On input-trees of finite automata. InAdvances in Cryptology–CHINACRYPT’94, Science Press, Beijing, 1994, pp.65–74. (in Chinese)
[31] Bao F. Limited error-propagation, self-synchronization and finite input memory FSMa as weak invverses. InAdvances in Chinese Computer Science, World Scientific, Singapore, 1991, 3: 1–24.
[32] Bao F. Composition and decomposition of weakly invertible finite automata.Science in China, Chinese Edition, 1993, 23: 759–766.
[33] Raney G N. Sequential functions.J. of the Association for Computing Machinery, 1958, 5: 177–180. · Zbl 0088.01801
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.