可逆有限自动机的结构与分解
|
摘要
前馈逆有限自动机的结构是有限自动机可逆性理论中的基本问题。对延迟步数≥3的前馈逆结构的刻划则是一个长期的未解决问题,尤其是当希望给出输出函数的显表达式时,这种刻划更加困难。弱可逆有限自动机的分解是有限自动机可逆性理论中的另一个问题,由鲍丰在1993年首次提出,目前它并没有得到深入的研究。本文主要研究了这两个课题。
在第一章,我们介绍有限自动机可逆性理论产生的背景、核心概念、主要研究内容、以及它在公钥密码学上的应用-有限自动机公开钥密码体制(FAPKC)。
在第二章,我们研究了二元延迟3步前馈逆有限自动机的结构。对于输入输出字母表大小相等且为2的c阶半输入存贮有限自动机M=c(M_a,f),其中自治有限自动机M_a的状态为一回路。当C(M_a,f)延迟3步弱可逆时,可将其按长3极小输出权W_3,M分为W_3,M=1,2,4,8四种所有可能情形。我们给出了延迟3步弱可逆的C(M_a,f)在长3极小输出权W_3,M=1,2,8三种情形下f的表达式和某些关系式,并证明了满足这些表达式和关系式的C(M_a,f)就是延迟3步弱可逆的。由于C(M_a,f)延迟3步弱可逆当且仅当它是延迟3步弱逆,因此这就给出了二元延迟3步前馈逆有限自动机结构的一种部分刻划,这是一个在刻划延迟步数≥3的前馈逆有限自动机的结构方面有科学意义的结果。
在第三章,我们利用有限自动机输出权研究了弱可逆有限自动机的分解,得到如下结果。(1)主要定理:假设M是一个n元延迟T步弱可逆有限自动机,则M可分解为一个延迟0步弱可逆有限自动机和一个T阶延迟元当且仅当|W_(T,S)~M|=1对M中任何状态s成立。应用这一定理我们证明了(2)存在一类不能进行这种分解的弱可逆有限自动机。(3)从(2)中构造出例子,否定回答了1993年的一个未解决问题。(4)给出了二元严格延迟T步强连通弱可逆有限自动机可分解为严格延迟T-1步弱可逆有限自动机和严格延迟1步弱可逆有限自动机的一种充分条件。(5)找到了一类可以通过合成的方法构造出的n元延迟T步,且所有状态的延迟步数都为T的弱可逆有限自动机。
在第四章,我们提出了一种基于有限自动机签名体制的同时签名方案。该方案满足同时签名的安全性要求,即正确性、不可伪造性、模糊性和公平性。
在第五章,我们列出了一些目前未解决的问题及将来进一步要做的工作。
The structure of feedforward inverse finite automata is a fundamental problem in the invertibility theory of finite automata. The characterization of the structure of feedforward inverses with delay steps ≥ 3 is a long-term unsolved problem, especially when we wish give the explicit expressions of the functions, the work get more difficult. The decomposition of weakly invertible finite automata is another problem in the invertibility theory of finite automata. It was first raised by Bao Feng in 1993. However, this issue hasnot been studied in depth since then . This thesis mainly deals with these two topics.In Chapter 1, we introduce the background, core notions, main contents of the invertibility theory of finite automata, and its applications in public key cryptography-the Finite Automaton Public Key Crypotsystem(FAPKC).In Chapter 2, we investigate the structure of binary feedforward inverse finite automata with delay 3. For a semi - input - memory finite automaton C(Ma, f) , where both the input alphabet and the output alphabet have two elements, the state graph of the autonomous finite automaton Ma is cyclic, when it is weakly invertible with delay3, we give the expressions of functions f and some other relationships when the minimal 3 - output weight w3,m = 1, 2, 8, respectively. Furthermore, we also show that if C(Ma,f) satisfies these conditions, then it is weakly invertible with delay 3. Due to the fact that C(Ma, f) is weakly invertible with delay 3 iff it is weak inverse with delay 3, we actually give a partial characterization of the structure of binary feedforward inverse finite automata with delay 3. Our results are of scientific meaning in characterizing the structure of feedforward inverses with delay steps ≥ 3.In Chapter 3, we consider the decomposition of weakly invertible finite automata by using the output weight of finite automaton, and obtain the following results. (1)Main Theorem: Let
M be an n-ary weakly invertible finite automaton with delay r, then M can be decomposed into a weakly finite automaton with delay 0 and a so-called τ-order delay unit iff |WMT,S|= 1 holds for each state s of M. Applying the main theorem we show that (2) There exist a class of weakly invertible finite automata that cannot be decomposed into weakly finite automata with delay 0 and delay units. (3) By (2) we construct an example which negatively answer an unsolved question proposed in 1993. (4) We also give a sufficient condition that a binary strongly connected weakly invertible M with delay τ can be decomposed into a weakly invertible finite automaton with strict delay τ - 1 and a weakly invertible finite automaton with strict delay 1 . (5) Using the composition method we obtain a class of n-ary weakly invertible finite automata with strict delay τ, where the delay step of each state of M is τ.In Chapter 4, we propose a concurrent signature based on finite automata signature scheme. Our scheme satisfies the security properties of concurrent signature, such as correctness, unforge-ability, Ambiguity and fairness.In Chapter 5, we list some unsolved questions, problems , and further directions for research in these areas .
在第一章,我们介绍有限自动机可逆性理论产生的背景、核心概念、主要研究内容、以及它在公钥密码学上的应用-有限自动机公开钥密码体制(FAPKC)。
在第二章,我们研究了二元延迟3步前馈逆有限自动机的结构。对于输入输出字母表大小相等且为2的c阶半输入存贮有限自动机M=c(M_a,f),其中自治有限自动机M_a的状态为一回路。当C(M_a,f)延迟3步弱可逆时,可将其按长3极小输出权W_3,M分为W_3,M=1,2,4,8四种所有可能情形。我们给出了延迟3步弱可逆的C(M_a,f)在长3极小输出权W_3,M=1,2,8三种情形下f的表达式和某些关系式,并证明了满足这些表达式和关系式的C(M_a,f)就是延迟3步弱可逆的。由于C(M_a,f)延迟3步弱可逆当且仅当它是延迟3步弱逆,因此这就给出了二元延迟3步前馈逆有限自动机结构的一种部分刻划,这是一个在刻划延迟步数≥3的前馈逆有限自动机的结构方面有科学意义的结果。
在第三章,我们利用有限自动机输出权研究了弱可逆有限自动机的分解,得到如下结果。(1)主要定理:假设M是一个n元延迟T步弱可逆有限自动机,则M可分解为一个延迟0步弱可逆有限自动机和一个T阶延迟元当且仅当|W_(T,S)~M|=1对M中任何状态s成立。应用这一定理我们证明了(2)存在一类不能进行这种分解的弱可逆有限自动机。(3)从(2)中构造出例子,否定回答了1993年的一个未解决问题。(4)给出了二元严格延迟T步强连通弱可逆有限自动机可分解为严格延迟T-1步弱可逆有限自动机和严格延迟1步弱可逆有限自动机的一种充分条件。(5)找到了一类可以通过合成的方法构造出的n元延迟T步,且所有状态的延迟步数都为T的弱可逆有限自动机。
在第四章,我们提出了一种基于有限自动机签名体制的同时签名方案。该方案满足同时签名的安全性要求,即正确性、不可伪造性、模糊性和公平性。
在第五章,我们列出了一些目前未解决的问题及将来进一步要做的工作。
The structure of feedforward inverse finite automata is a fundamental problem in the invertibility theory of finite automata. The characterization of the structure of feedforward inverses with delay steps ≥ 3 is a long-term unsolved problem, especially when we wish give the explicit expressions of the functions, the work get more difficult. The decomposition of weakly invertible finite automata is another problem in the invertibility theory of finite automata. It was first raised by Bao Feng in 1993. However, this issue hasnot been studied in depth since then . This thesis mainly deals with these two topics.In Chapter 1, we introduce the background, core notions, main contents of the invertibility theory of finite automata, and its applications in public key cryptography-the Finite Automaton Public Key Crypotsystem(FAPKC).In Chapter 2, we investigate the structure of binary feedforward inverse finite automata with delay 3. For a semi - input - memory finite automaton C(Ma, f) , where both the input alphabet and the output alphabet have two elements, the state graph of the autonomous finite automaton Ma is cyclic, when it is weakly invertible with delay3, we give the expressions of functions f and some other relationships when the minimal 3 - output weight w3,m = 1, 2, 8, respectively. Furthermore, we also show that if C(Ma,f) satisfies these conditions, then it is weakly invertible with delay 3. Due to the fact that C(Ma, f) is weakly invertible with delay 3 iff it is weak inverse with delay 3, we actually give a partial characterization of the structure of binary feedforward inverse finite automata with delay 3. Our results are of scientific meaning in characterizing the structure of feedforward inverses with delay steps ≥ 3.In Chapter 3, we consider the decomposition of weakly invertible finite automata by using the output weight of finite automaton, and obtain the following results. (1)Main Theorem: Let
M be an n-ary weakly invertible finite automaton with delay r, then M can be decomposed into a weakly finite automaton with delay 0 and a so-called τ-order delay unit iff |WMT,S|= 1 holds for each state s of M. Applying the main theorem we show that (2) There exist a class of weakly invertible finite automata that cannot be decomposed into weakly finite automata with delay 0 and delay units. (3) By (2) we construct an example which negatively answer an unsolved question proposed in 1993. (4) We also give a sufficient condition that a binary strongly connected weakly invertible M with delay τ can be decomposed into a weakly invertible finite automaton with strict delay τ - 1 and a weakly invertible finite automaton with strict delay 1 . (5) Using the composition method we obtain a class of n-ary weakly invertible finite automata with strict delay τ, where the delay step of each state of M is τ.In Chapter 4, we propose a concurrent signature based on finite automata signature scheme. Our scheme satisfies the security properties of concurrent signature, such as correctness, unforge-ability, Ambiguity and fairness.In Chapter 5, we list some unsolved questions, problems , and further directions for research in these areas .
引文
[1] W. Diffie and M.Hellman. New Directions in Cryptogryphy. IEEE Trans On Info. Theory. IT-22(6), 1976, 644-654.
[2] R. L. Rivest, A. Shamir and L. Adleman. A Method for Obtaining Digital Signatures and Public-key Cryptosystem. Communations of the ACM. 21(2), 1978, 120-126.
[3] R. C. Merkle and M. E. Mellman. Hinding Information and Signatures in Trapdoor Knapsacks. IEEE trans, on IT. 24(5), 1978, 525-530.
[4] R. J. McEliece. A Public-key Cryptosystem Based on Algebraic Coding Theory. DSN Progress Report. 42-44, 1978, 114-116.
[5] L. ElGamal. A Public Key Cryptosystem and a Signature Scheme Based on Discrete Logarithm. IEEE Trans, on IT. 31, 1985, 469-472.
[6] V. Miller. Uses of Elliptic Curves in Cryptography. Advances in Cryptology-Crypto'85. Springer-Verlag. 1986, 417-426.
[7] N. Koblitz. Elliptic Curve Cryptosystems. Mathematics of Computation. 48, 1987, 203-209.
[8] S. Goldwasser and A. Micali. Probabilistic Encryption. J. of Computer and Systems Science. 28, 1984, 270-299.
[9] W. S. McCulloch and W. Pitts. A Logical Calculus of the Ideas Immanent in Nervous Activity. Bull. Math. Biophys. 5, 1943, 115-133.
[10] M. L. Minsky. Neural Nets and the Brain Model Problem. Ph.D. Dissertation in Mathematics. Princeton. 1954.
[11] D. A. Huffman. The Synthesis of Sequential Switching Circuits. Journal of the Franklin Institute. 257, 1954, 161-190, 275-303.
[12] C. E. Shannon and J. McCarthy. Automata Studies. Princeton: Princeton University Press. 1956.
[13] S. C. Kleene. Representation of Events in Nerve Nets and Finite Automata. Automata Studies. Princeton: Princeton University Press. 1956, 3-41.
[14] E. F. Moore. Gcdanken-Experiments on Sequential Machines. Automa Studies. Princeton: Pricenton University Press. 1956, 129-153.
[15] C.E.申南,J.麦克卡赛.自动机研究.北京:科学出版社. 1963.
[16] D. A. Huffman. Canonical Forms of Information-Lossless Finite-State Logical Machines. IRE Trans. on Circuit Theory. May, Special Supplement. 6, 1959, 41-59.
[17] S. Even.Tests for Synchronizability of Finite Automata and Varible Length Codes. IEEE Trans. on Information Theory.IT-10(7), 1964, 185-189.
[18] S. Even. On Information Lossless Automata of Finite Order. IEEE Trans. on Electronic Computers. c-14(4), 1965, 561-569.
[19] J. L. Massey and M. K. Sain. Inverse of Linear Sequential Circuits. IEEE Trains. on Computers. c-17(4), 1968, 330-337.
[20] Forney G.D. Convolutional Codes Ⅰ: Algebraic Structure. IEEE Trans. on Information Theory. IT-16(6), 1970, 720-738.
[21] 陶仁骥.可逆线性有限自动机.中国科学.16(4),1973,454-467.
[22] A. S. Willsky. On the Invertibility of Linear System. IEEE trans, on Automata Control. 19(3), 1974, 272-274.
[23] A. S. Willsky. Invertibility of Finite Group Homorphic Sequential system. Infor. and Control. 27(2),1975, 126-149.
[24] 陶仁骥.有限自动机可逆性的研究概况.中国科学院计算技术研究所.1977.
[25] 陈世华.关于弱可逆线性有限自动机的弱逆的结构.计算机学报.4(6),1981,409-419.
[26] 陶仁骥,陈世华.关于延迟T步(可)逆有限自动机结构的一些性质.计算机学报.3(4),1980,289-297.
[27] Chen Shihua. On the Structure of Finite Automata of which M' Is an (Weak) Inverse with Delay T. J. of Computer Science and Technology. 1(2), 1986, 54-59.
[28] Chen Shihua. On the Structure of (Weak) Inverses of an (Weakly) Invertible Finite Automata. J. of Computer Science and Technology. 1(3), 1986, 92-100.
[29] 陶仁骥.有限自动机的可逆性.北京:科学出版社.1979.
[30] Tao Renji, Chen Shihua. Generating a kind of Nonlinear Finite Automata with Invertibility by Transformation method. Technical Report No.ISCAS-LCS-95-05. Laboratory for Computer Science, Institute of Software, Chinese Academy of Sciences, Beijing. 1995.
[31] 陶仁骥.自动机引论.北京:科学出版社.1986.
[32] Tao Ren-ji and Chen Shi-hua. Structure of Weakly Invertible Semi-Input-Memory Finite Automata with Delay 1. J. of Computer Science and Technology. 17(4), 2002, 369-376.
[33] 陶仁骥,陈世华.一种有限自动机公开钥密码体制和数字签名.计算机学报.8(6),1985,401-409.
[34] A. Salomma. Public-key Cryptography. Berlin: Springer-Verlag, 1990.
[35] Bruce Schneier. Applied Cryptography : Protocols, Algorithms, and Source Code in C. New York: Wiley. 1994.
[36] A.萨洛马.公钥密码学.北京:国防工业出版社.1998.
[37] Tao Renji and Chen Shihua. Two Varieties of Finite Automaton Public Key Cryptosystem and Digital Signatures. J. of Computer Science and Technology. 1(1), 1986, 9-18.
[38] 高翔.有限自动机公开钥密码体制和数字签名-分析、设计与实现.中国科学院软件研究所博士学位论文.中国科学院软件研究所.1994.
[39] Tao Renji, Chen Shihua and Chen Xuemei. FAPKC3: A New Finite Automaton Public Key Cryptosystem. Technical Report No.ISCAS-LCS-95-07. Laboratory for Computer Science, Institute of Software, Chinese Academy of Sciences, Beijing. 1995.
[40] Tao Ren-ji and Chen Shi-hua. A Variant of the Public Key Cryptosystem FAPKC3. J. of Network and Computer Applications. 20(3), 1997, 283-303.
[41] Tao Renji and Chen Shihua. Note on Finite Automaton Public Key Cryptosystems.密码学进展—CHINACRYPT'94.北京:科学出版社.1994,76-81.
[42] A. Shamir. Identity-based Cryptosystems and Signature Schemes. Proceedings of CRYPTO'84 on Advances in Cryptology. Springer-Verlag, 1985, 47-53.
[43] 陈世华,陶仁骥.拟线性有限自动机的可逆性.密码学进展—CHINACRYPT’92.北京:科学出版社.1992,77-86.
[44] 陶仁骥,陈世华.基于身份的密码体制和数字签名的有限自动机公开钥密码实现.密码学进展—CHINACRYPT’92.北京:科学出版社.1992,87-104.
[45] 鲍丰.线性有限自动机的递增秩与FA公开钥密码体制的复杂性.中国科学(A辑).24(2),1994,193-200.
[46] 戴大为,吴逵,张焕国.有限自动机公钥密码体制的密码分析.中国科学(A辑).25(11),1995,1226-1232.
[47] Tao Renji. On R_aR_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. 1995.
[48] F. Bao and Y. Igarashi. Break Finite Automata Public Key Cryptosystem. in Proc. of ICALP'95, LNCS 944. Springer-Verlag. 1995, 147-158.
[49] 覃中平,张焕国,有限自动机公开钥密码攻击算法A(T)M.计算机学报.18(3),1995,199-204.
[50] 覃中平,张焕国.分析有限自动机公开钥密码.密码学进展—CHINACRYPT'96.北京:科学出版社.1996,75-86.
[51] 戴宗铎.一类可分非线性有限自动机—兼对FAPKC3加密和签名体制的分析.密码学进展—CHINACRYPT'96.北京:科学出版社.1996,87-94.
[52] Z. D. Dai, D. F. Ye and Kwok Yan Lam. Weak Invertibility of Finite Automata and Cryptanalysis of a Public Key Cryptosystem Based on Finite Automata (FAPKC). Advances in Cryptology-Asia Crypt'98, LNCS 1514. Spring-Verlag. 1998, 227-241.
[53] 王浩.一类约化梯阵的R_aR_b表示.软件学报.8,1997,772-780.
[54] Tao Renji and Feng Peirong. On Relations between R_aR_b Transformation and Canonical Diagonal Form of λ-matrix. Science in China (Ser. E). 40, 1997, 258-268.
[55] 陶仁骥.矩阵多项式的几种特殊分解.计算机学报.22(1),1999,1-10.
[56] Tao Renji. Remark on "Weak Invertibility of Finite Automata and Cryptanalysis on FAPKC". 密码学进展—CHINACRYPT'2000.北京:科学出版社.2000,65-75.
[57] 陶仁骥.有界误差传播和前馈可逆的关系.科学通报.27(7),1982,406-408.
[58] 陶仁骥.关于前馈逆的结构的若干结果.中国科学(A辑).28(12),1983,1073-1078.
[59] 鲍丰.n元延迟1步前馈逆的结构.中国科学院软件研究所硕士论文.1986.
[60] Zhu Xin-jie. On the Structure of Feedforward Inverses with Delay 2. J. of Computer Science and Technology. 4(2), 1989, 163-171.
[61] Tao Ren-ji and Chen Shi-hua. Structure of Weakly Invertible Semi-Input-Memory Finite Automata with Delay 2. J. of Computer Science and Technology. 17(6), 2002, 682-688.
[62] 姚刚.有限自动机可逆性的若干结果.中国科学院软件研究所博士学位论文.中国科学院软件研究所.2003.
[63] Tao Ren-ji and Chen Shi-hua. Input-trees of Finite Automata and Application to Cryptanalysis. J. of Computer Science and Technology. 15(4), 2000, 305-325.
[64] 鲍丰.关于弱可逆有限自动机延迟步数分解的两个结果.计算机学报.16(8),1993,629-632.
[65] 鲍丰.弱可逆有限自动机的化合与分解.中国科学(A辑).23(7),1993,759-766.
[66] 高翔,鲍丰.二元弱可逆有限自动机延迟步数的分解.计算机学报.17(5),1994,330-337.
[67] Yao Gang. Decomposing a kind of Weakly Invertible Finite Automata with Delay 2. J. of Computer Science and Technology. 18(3), 2003, 354-360.
[68] 周善有.关于第Ⅰ型Abel FGHSS的弱可逆性.计算机学报.5(3),1982,220-227.
[69] Tao Renji. Invertibility of Linear Finite Automata over a Ring. ICALP'88, Automata, Languages and Programming, LNCS 317. Berlin: Springer-Verlag, 1988, 489-501.
[70] 吕书志.环上线性有限自动机可逆性的一些结果.计算机学报.14(8),1991,570-578.
[71] 戴宗铎,叶顶峰.交换环上线性有限自动机的弱可逆性—传输矩阵的分类与枚举.科学通报,40(15),1995,1357-1360.
[72] 陈小明.二次型有限自动机可逆性理论与应用.中国科学院软件研究所博士学位论文.中国科学院软件研究所.1996.
[73] 王浩.有限自动机的可逆性研究.中国科学院软件研究所博士学位论文.中国科学院软件研究所.1996.
[74] O. Goldreich. A simple protocol for signing contracts. In Advances in Cryptology—CRYPTO 1983, Berlin: Springer-Verlag, 1983, 133-136.
[75] D. Boneh, and M. Naor. Timed commitments (extended abstract). In Advances in Cryptology—CRYPTO 2000, LNCS 1880. Berlin: Springer-Verlag, 2000, 236-254.
[76] N. Asokan, V. Shoup, and M. Waidner. Optimistic fair exchange of signatures. In Advances in Cryptology—EUROCRYPT 1998, LNCS 1403. Berlin: Springer-Verlag, 1998, 591-606
[77] J. Park, E. Chong, and H. Siegel. Constructing fair exchange protocols for e-commerce via distributed computation of RSA signatures. In 22nd Annual ACM Symp. On Principles of Distributed Computing. 2003, 172-181.
[78] L. Chen, C. Kudla, and K. G. Paterson. Concurrent signatures. In Advances in Cryptology—Eurocrypt 2004, LNCS 3027. Berlin: Springer-Verlag, 2004, 287-305.
[79] W. Susilo, Y. Mu, and F. Zhang. Perfect concurrent signature schemes. In Information and Communications Security—ICICS2004, LNCS 3269. Berlin: Springer-Verlag, 2004, 14-26.
[80] D. Wagner. A generalized birthday problem. In Advances in Cryptology—CRYPTO 2002, LNCS 2442. Berlin: Springer-Verlag, 2002, 288-304.
[81] 陶仁骥.密码学与数学.自然杂志.7(7),1984,227-234.
[82] K. Wagner and G. Wechsung. Computational Complexity. Dordrecht, Holland: D. Reidel Publishing Company. 1986.
[83] 陶仁骥.密码学中的一些数学问题.数学季刊.2(1),1987,73-90.
[84] 肖国镇,卿斯汉.密码学的现状与发展.电子学报.15(5),1987,89-96.
[85] 张立昂.可计算性和计算复杂性导引.北京:北京大学出版社.1996.
[86] Harry R. Lewis and Christos H. Papalimitriou. Elements of the Theory of Computation, 2nd Ed. Englewood Cliffs, New Jersey: Prentice-Hall Inc. 1998.
[87] 冯登国,裴定一.密码学导引.北京:科学出版社.1999.
[88] M.Sipser.计算理论导引.北京:机械工业出版社.2000.
[89] 蔡吉人.信息安全与密码学.信息安全与通信保密.1(3),2001,15-17.
[90] 陈克非.信息安全—密码的作用与局限.通信学报.22(8),2001,93-99.
[2] R. L. Rivest, A. Shamir and L. Adleman. A Method for Obtaining Digital Signatures and Public-key Cryptosystem. Communations of the ACM. 21(2), 1978, 120-126.
[3] R. C. Merkle and M. E. Mellman. Hinding Information and Signatures in Trapdoor Knapsacks. IEEE trans, on IT. 24(5), 1978, 525-530.
[4] R. J. McEliece. A Public-key Cryptosystem Based on Algebraic Coding Theory. DSN Progress Report. 42-44, 1978, 114-116.
[5] L. ElGamal. A Public Key Cryptosystem and a Signature Scheme Based on Discrete Logarithm. IEEE Trans, on IT. 31, 1985, 469-472.
[6] V. Miller. Uses of Elliptic Curves in Cryptography. Advances in Cryptology-Crypto'85. Springer-Verlag. 1986, 417-426.
[7] N. Koblitz. Elliptic Curve Cryptosystems. Mathematics of Computation. 48, 1987, 203-209.
[8] S. Goldwasser and A. Micali. Probabilistic Encryption. J. of Computer and Systems Science. 28, 1984, 270-299.
[9] W. S. McCulloch and W. Pitts. A Logical Calculus of the Ideas Immanent in Nervous Activity. Bull. Math. Biophys. 5, 1943, 115-133.
[10] M. L. Minsky. Neural Nets and the Brain Model Problem. Ph.D. Dissertation in Mathematics. Princeton. 1954.
[11] D. A. Huffman. The Synthesis of Sequential Switching Circuits. Journal of the Franklin Institute. 257, 1954, 161-190, 275-303.
[12] C. E. Shannon and J. McCarthy. Automata Studies. Princeton: Princeton University Press. 1956.
[13] S. C. Kleene. Representation of Events in Nerve Nets and Finite Automata. Automata Studies. Princeton: Princeton University Press. 1956, 3-41.
[14] E. F. Moore. Gcdanken-Experiments on Sequential Machines. Automa Studies. Princeton: Pricenton University Press. 1956, 129-153.
[15] C.E.申南,J.麦克卡赛.自动机研究.北京:科学出版社. 1963.
[16] D. A. Huffman. Canonical Forms of Information-Lossless Finite-State Logical Machines. IRE Trans. on Circuit Theory. May, Special Supplement. 6, 1959, 41-59.
[17] S. Even.Tests for Synchronizability of Finite Automata and Varible Length Codes. IEEE Trans. on Information Theory.IT-10(7), 1964, 185-189.
[18] S. Even. On Information Lossless Automata of Finite Order. IEEE Trans. on Electronic Computers. c-14(4), 1965, 561-569.
[19] J. L. Massey and M. K. Sain. Inverse of Linear Sequential Circuits. IEEE Trains. on Computers. c-17(4), 1968, 330-337.
[20] Forney G.D. Convolutional Codes Ⅰ: Algebraic Structure. IEEE Trans. on Information Theory. IT-16(6), 1970, 720-738.
[21] 陶仁骥.可逆线性有限自动机.中国科学.16(4),1973,454-467.
[22] A. S. Willsky. On the Invertibility of Linear System. IEEE trans, on Automata Control. 19(3), 1974, 272-274.
[23] A. S. Willsky. Invertibility of Finite Group Homorphic Sequential system. Infor. and Control. 27(2),1975, 126-149.
[24] 陶仁骥.有限自动机可逆性的研究概况.中国科学院计算技术研究所.1977.
[25] 陈世华.关于弱可逆线性有限自动机的弱逆的结构.计算机学报.4(6),1981,409-419.
[26] 陶仁骥,陈世华.关于延迟T步(可)逆有限自动机结构的一些性质.计算机学报.3(4),1980,289-297.
[27] Chen Shihua. On the Structure of Finite Automata of which M' Is an (Weak) Inverse with Delay T. J. of Computer Science and Technology. 1(2), 1986, 54-59.
[28] Chen Shihua. On the Structure of (Weak) Inverses of an (Weakly) Invertible Finite Automata. J. of Computer Science and Technology. 1(3), 1986, 92-100.
[29] 陶仁骥.有限自动机的可逆性.北京:科学出版社.1979.
[30] Tao Renji, Chen Shihua. Generating a kind of Nonlinear Finite Automata with Invertibility by Transformation method. Technical Report No.ISCAS-LCS-95-05. Laboratory for Computer Science, Institute of Software, Chinese Academy of Sciences, Beijing. 1995.
[31] 陶仁骥.自动机引论.北京:科学出版社.1986.
[32] Tao Ren-ji and Chen Shi-hua. Structure of Weakly Invertible Semi-Input-Memory Finite Automata with Delay 1. J. of Computer Science and Technology. 17(4), 2002, 369-376.
[33] 陶仁骥,陈世华.一种有限自动机公开钥密码体制和数字签名.计算机学报.8(6),1985,401-409.
[34] A. Salomma. Public-key Cryptography. Berlin: Springer-Verlag, 1990.
[35] Bruce Schneier. Applied Cryptography : Protocols, Algorithms, and Source Code in C. New York: Wiley. 1994.
[36] A.萨洛马.公钥密码学.北京:国防工业出版社.1998.
[37] Tao Renji and Chen Shihua. Two Varieties of Finite Automaton Public Key Cryptosystem and Digital Signatures. J. of Computer Science and Technology. 1(1), 1986, 9-18.
[38] 高翔.有限自动机公开钥密码体制和数字签名-分析、设计与实现.中国科学院软件研究所博士学位论文.中国科学院软件研究所.1994.
[39] Tao Renji, Chen Shihua and Chen Xuemei. FAPKC3: A New Finite Automaton Public Key Cryptosystem. Technical Report No.ISCAS-LCS-95-07. Laboratory for Computer Science, Institute of Software, Chinese Academy of Sciences, Beijing. 1995.
[40] Tao Ren-ji and Chen Shi-hua. A Variant of the Public Key Cryptosystem FAPKC3. J. of Network and Computer Applications. 20(3), 1997, 283-303.
[41] Tao Renji and Chen Shihua. Note on Finite Automaton Public Key Cryptosystems.密码学进展—CHINACRYPT'94.北京:科学出版社.1994,76-81.
[42] A. Shamir. Identity-based Cryptosystems and Signature Schemes. Proceedings of CRYPTO'84 on Advances in Cryptology. Springer-Verlag, 1985, 47-53.
[43] 陈世华,陶仁骥.拟线性有限自动机的可逆性.密码学进展—CHINACRYPT’92.北京:科学出版社.1992,77-86.
[44] 陶仁骥,陈世华.基于身份的密码体制和数字签名的有限自动机公开钥密码实现.密码学进展—CHINACRYPT’92.北京:科学出版社.1992,87-104.
[45] 鲍丰.线性有限自动机的递增秩与FA公开钥密码体制的复杂性.中国科学(A辑).24(2),1994,193-200.
[46] 戴大为,吴逵,张焕国.有限自动机公钥密码体制的密码分析.中国科学(A辑).25(11),1995,1226-1232.
[47] Tao Renji. On R_aR_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. 1995.
[48] F. Bao and Y. Igarashi. Break Finite Automata Public Key Cryptosystem. in Proc. of ICALP'95, LNCS 944. Springer-Verlag. 1995, 147-158.
[49] 覃中平,张焕国,有限自动机公开钥密码攻击算法A(T)M.计算机学报.18(3),1995,199-204.
[50] 覃中平,张焕国.分析有限自动机公开钥密码.密码学进展—CHINACRYPT'96.北京:科学出版社.1996,75-86.
[51] 戴宗铎.一类可分非线性有限自动机—兼对FAPKC3加密和签名体制的分析.密码学进展—CHINACRYPT'96.北京:科学出版社.1996,87-94.
[52] Z. D. Dai, D. F. Ye and Kwok Yan Lam. Weak Invertibility of Finite Automata and Cryptanalysis of a Public Key Cryptosystem Based on Finite Automata (FAPKC). Advances in Cryptology-Asia Crypt'98, LNCS 1514. Spring-Verlag. 1998, 227-241.
[53] 王浩.一类约化梯阵的R_aR_b表示.软件学报.8,1997,772-780.
[54] Tao Renji and Feng Peirong. On Relations between R_aR_b Transformation and Canonical Diagonal Form of λ-matrix. Science in China (Ser. E). 40, 1997, 258-268.
[55] 陶仁骥.矩阵多项式的几种特殊分解.计算机学报.22(1),1999,1-10.
[56] Tao Renji. Remark on "Weak Invertibility of Finite Automata and Cryptanalysis on FAPKC". 密码学进展—CHINACRYPT'2000.北京:科学出版社.2000,65-75.
[57] 陶仁骥.有界误差传播和前馈可逆的关系.科学通报.27(7),1982,406-408.
[58] 陶仁骥.关于前馈逆的结构的若干结果.中国科学(A辑).28(12),1983,1073-1078.
[59] 鲍丰.n元延迟1步前馈逆的结构.中国科学院软件研究所硕士论文.1986.
[60] Zhu Xin-jie. On the Structure of Feedforward Inverses with Delay 2. J. of Computer Science and Technology. 4(2), 1989, 163-171.
[61] Tao Ren-ji and Chen Shi-hua. Structure of Weakly Invertible Semi-Input-Memory Finite Automata with Delay 2. J. of Computer Science and Technology. 17(6), 2002, 682-688.
[62] 姚刚.有限自动机可逆性的若干结果.中国科学院软件研究所博士学位论文.中国科学院软件研究所.2003.
[63] Tao Ren-ji and Chen Shi-hua. Input-trees of Finite Automata and Application to Cryptanalysis. J. of Computer Science and Technology. 15(4), 2000, 305-325.
[64] 鲍丰.关于弱可逆有限自动机延迟步数分解的两个结果.计算机学报.16(8),1993,629-632.
[65] 鲍丰.弱可逆有限自动机的化合与分解.中国科学(A辑).23(7),1993,759-766.
[66] 高翔,鲍丰.二元弱可逆有限自动机延迟步数的分解.计算机学报.17(5),1994,330-337.
[67] Yao Gang. Decomposing a kind of Weakly Invertible Finite Automata with Delay 2. J. of Computer Science and Technology. 18(3), 2003, 354-360.
[68] 周善有.关于第Ⅰ型Abel FGHSS的弱可逆性.计算机学报.5(3),1982,220-227.
[69] Tao Renji. Invertibility of Linear Finite Automata over a Ring. ICALP'88, Automata, Languages and Programming, LNCS 317. Berlin: Springer-Verlag, 1988, 489-501.
[70] 吕书志.环上线性有限自动机可逆性的一些结果.计算机学报.14(8),1991,570-578.
[71] 戴宗铎,叶顶峰.交换环上线性有限自动机的弱可逆性—传输矩阵的分类与枚举.科学通报,40(15),1995,1357-1360.
[72] 陈小明.二次型有限自动机可逆性理论与应用.中国科学院软件研究所博士学位论文.中国科学院软件研究所.1996.
[73] 王浩.有限自动机的可逆性研究.中国科学院软件研究所博士学位论文.中国科学院软件研究所.1996.
[74] O. Goldreich. A simple protocol for signing contracts. In Advances in Cryptology—CRYPTO 1983, Berlin: Springer-Verlag, 1983, 133-136.
[75] D. Boneh, and M. Naor. Timed commitments (extended abstract). In Advances in Cryptology—CRYPTO 2000, LNCS 1880. Berlin: Springer-Verlag, 2000, 236-254.
[76] N. Asokan, V. Shoup, and M. Waidner. Optimistic fair exchange of signatures. In Advances in Cryptology—EUROCRYPT 1998, LNCS 1403. Berlin: Springer-Verlag, 1998, 591-606
[77] J. Park, E. Chong, and H. Siegel. Constructing fair exchange protocols for e-commerce via distributed computation of RSA signatures. In 22nd Annual ACM Symp. On Principles of Distributed Computing. 2003, 172-181.
[78] L. Chen, C. Kudla, and K. G. Paterson. Concurrent signatures. In Advances in Cryptology—Eurocrypt 2004, LNCS 3027. Berlin: Springer-Verlag, 2004, 287-305.
[79] W. Susilo, Y. Mu, and F. Zhang. Perfect concurrent signature schemes. In Information and Communications Security—ICICS2004, LNCS 3269. Berlin: Springer-Verlag, 2004, 14-26.
[80] D. Wagner. A generalized birthday problem. In Advances in Cryptology—CRYPTO 2002, LNCS 2442. Berlin: Springer-Verlag, 2002, 288-304.
[81] 陶仁骥.密码学与数学.自然杂志.7(7),1984,227-234.
[82] K. Wagner and G. Wechsung. Computational Complexity. Dordrecht, Holland: D. Reidel Publishing Company. 1986.
[83] 陶仁骥.密码学中的一些数学问题.数学季刊.2(1),1987,73-90.
[84] 肖国镇,卿斯汉.密码学的现状与发展.电子学报.15(5),1987,89-96.
[85] 张立昂.可计算性和计算复杂性导引.北京:北京大学出版社.1996.
[86] Harry R. Lewis and Christos H. Papalimitriou. Elements of the Theory of Computation, 2nd Ed. Englewood Cliffs, New Jersey: Prentice-Hall Inc. 1998.
[87] 冯登国,裴定一.密码学导引.北京:科学出版社.1999.
[88] M.Sipser.计算理论导引.北京:机械工业出版社.2000.
[89] 蔡吉人.信息安全与密码学.信息安全与通信保密.1(3),2001,15-17.
[90] 陈克非.信息安全—密码的作用与局限.通信学报.22(8),2001,93-99.