网络安全协议中的非等计算能力问题

摘要

在论文的前几个章节,我们介绍了两个相关的理论：实例隐藏理论和计算复杂性理论.其中给出了实例隐藏的概念和主要结论,以及确定性计算的时间和宽间层次定理.在对这两个理论讨论的基础上,我们提出了该文的主要结果：实例隐藏在一定条件下的时间层次性和空间层次性.结果包括两个定理：实例隐藏的空间层次性定理和实例隐藏的时间层次性定理.这两个定理从一定的程度上,去除了复杂函数可以被某个实例隐藏的通用隐藏机制简化计算的可能性.另外,文章前面章节提出的安全协议新框架从逻辑上可以进行修订,在这个修订后的框架中,论文的结论仍然适用,但是修订框架给了我们一个研究安全协议的新的视角.

目录

摘要

Abstract

一引言

二通用记号和基本概念

三相关的计算复杂性理论和实例隐藏理论

1.P/poly类及其NP/poly类的相关理论

2.实例隐藏的相关理论

3.复杂性类的层次关系

四确定型计算的时间与空间层次定理

1.空间层次定理

2.时间层次定理

五通用隐藏机制的空间层次性

六通用隐藏机制的时间层次性

七通用隐藏机制的层次性证明的讨论

1.两个主要定理证明的讨论

2.通用隐藏机制的层次性与网络安全协议的新框架

八结论

九未完成的问题

致谢

参考书目及文献

附：攻读硕士学位期间发表的论文