节点文献

可逆有限自动机的结构与分解

【作者】 王鸿吉

【导师】 李昂生; 陶仁骥;

【作者基本信息】 中国科学院研究生院(软件研究所) , 计算机软件与理论, 2005, 博士

【摘要】 前馈逆有限自动机的结构是有限自动机可逆性理论中的基本问题。对延迟步数≥3的前馈逆结构的刻划则是一个长期的未解决问题,尤其是当希望给出输出函数的显表达式时,这种刻划更加困难。弱可逆有限自动机的分解是有限自动机可逆性理论中的另一个问题,由鲍丰在1993年首次提出,目前它并没有得到深入的研究。本文主要研究了这两个课题。 在第一章,我们介绍有限自动机可逆性理论产生的背景、核心概念、主要研究内容、以及它在公钥密码学上的应用-有限自动机公开钥密码体制(FAPKC)。 在第二章,我们研究了二元延迟3步前馈逆有限自动机的结构。对于输入输出字母表大小相等且为2的c阶半输入存贮有限自动机M=c(Ma,f),其中自治有限自动机Ma的状态为一回路。当C(Ma,f)延迟3步弱可逆时,可将其按长3极小输出权W3,M分为W3,M=1,2,4,8四种所有可能情形。我们给出了延迟3步弱可逆的C(Ma,f)在长3极小输出权W3,M=1,2,8三种情形下f的表达式和某些关系式,并证明了满足这些表达式和关系式的C(Ma,f)就是延迟3步弱可逆的。由于C(Ma,f)延迟3步弱可逆当且仅当它是延迟3步弱逆,因此这就给出了二元延迟3步前馈逆有限自动机结构的一种部分刻划,这是一个在刻划延迟步数≥3的前馈逆有限自动机的结构方面有科学意义的结果。 在第三章,我们利用有限自动机输出权研究了弱可逆有限自动机的分解,得到如下结果。(1)主要定理:假设M是一个n元延迟T步弱可逆有限自动机,则M可分解为一个延迟0步弱可逆有限自动机和一个T阶延迟元当且仅当|WT,SM|=1对M中任何状态s成立。应用这一定理我们证明了(2)存在一类不能进行这种分解的弱可逆有限自动机。(3)从(2)中构造出例子,否定回答了1993年的一个未解决问题。(4)给出了二元严格延迟T步强连通弱可逆有限自动机可分解为严格延迟T-1步弱可逆有限自动机和严格延迟1步弱可逆有限自动机的一种充分条件。(5)找到了一类可以通过合成的方法构造出的n元延迟T步,且所有状态的延迟步数都为T的弱可逆有限自动机。 在第四章,我们提出了一种基于有限自动机签名体制的同时签名方案。该方案满足同时签名的安全性要求,即正确性、不可伪造性、模糊性和公平性。 在第五章,我们列出了一些目前未解决的问题及将来进一步要做的工作。

【Abstract】 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: LetM 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 .

节点文献中: 

本文链接的文献网络图示:

本文的引文网络