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

论文题目: 可逆有限自动机的结构与分解

论文类型: 博士论文

论文专业: 计算机软件与理论

作者: 王鸿吉

导师: 李昂生,陶仁骥

关键词: 有限自动机,延迟,弱可逆,半输入存贮,前馈可逆,合成,分解,同时签名

文献来源: 中国科学院研究生院（软件研究所）

发表年度: 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

第一章绪论

第一节有限自动机可逆性理论

第二节有限自动机公开钥密码体制(FAPKC)

第三节问题的提出、相关的结果及本文的工作

第二章二元延迟3步前馈逆有限自动机的结构

第一节引言

第二节 w_3,M=2的二元延迟3步弱可逆有限自动机

第三节 W_3,M=2的二元延迟3步弱可逆半输入存储有限自动机

第四节 w_3，M=1的二元延迟3步弱可逆半输入存储有限自动机

第五节 W_3,M=8的二元延迟3步弱可逆半输入存储有限自动机

第六节二元延迟3步弱可逆C阶半输入存储有限自动机的结构

第七节二元延迟3步前馈逆有限自动机的结构

第三章弱可逆有限自动机的分解

第一节引言

第二节分解n元延迟τ步弱可逆有限自动机的一种充要条件

第三节二元延迟τ步弱可逆有限自动机的特殊分解

第四节一个应用

第四章基于有限自动机的同时签名方案

第一节引言

第二节基于有限自动机的同时签名方案

第三节安全性分析

第五章结束语

在学期间发表文章

致谢

参考文献

发布时间: 2005-07-08

参考文献

[1].有限自动机可逆性的若干结果[D]. 姚刚.中国科学院研究生院（软件研究所）2003

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

猜你喜欢