NP问题的常数轮知识的零知识证明系统

文中研究在标准复杂性假设下NP问题的常数轮知识的零知识证明系统的存在性问题.利用一种特殊的交互证明模式,在因子分解的困难性假设下,给出了NP问题的一个3轮的知识的零知识证明系统.文中给出的证明系统不仅肯定了NP问题的常数轮知识的零知识证明系统的存在性,同时也是对(NP问题的)3轮零知识证明系统的存在性这一公开问题的一个肯定性答复.     

基于可编程hash函数的短签名

数字签名中的短签名由于其签名长度的优势，特别适用于通信带宽受限的场合．现有的短签名方案大多是随机预言模型下可证明安全的，但是随机预言模型通常被认为过于理想化，现实中没有一种hash函数能够模拟随机预言模型，而少数标准模型下可证安全的短签名方案，一般被认为是低效的或者基于强困难假设，即攻击者被给于一定数量的随机的已解决问题实例，要求去解决一个它自己选择的实例．可编程hash函数fprogrammablehashflmctions，PHF）是一种能模拟随机预言的某些可编程特性的特殊hash函数．可编程hash函数可嵌入到签名的基本构造中，产生标准模型下的短签名．本文利用可编程hash函数设计了一个基于因子分解假设的短签名方案．它具有的优点是：1）签名长度短，只需要一个群上的元素和一个小整数；2）签名和验证计算量小，不需要在签名过程中进行生成素数的运算；3）不需要嵌入变色龙hash函数便可实现标准模型下可证明安全．     

使用广义奇—超位Ⅱ的一阶定理证明

证明了使用奇－超位Ⅱ的证明系统是不完备的，造成这种不完备性的原因是忽略了幂等规则的使用，通过定义一阶多项式与零的超位，适当地拓广了奇－超位Ⅱ的定义，给出了一个使用这种拓广了的奇－超位Ⅱ的完备了证明系统，此外，这一证明系统也是余式方法的改进，它的完备性实质上也说明了使用语义策略的余式方法是完备的。     

基于知识结构的认证协议验证

认知逻辑的Kripke语义,已被成功地运用到分析无黑客存在的安全网络下的通信协议.提出认知逻辑的Kripke语义的一种简单而自然的形式,称之为知识结构,并把这种语义用到分析黑客存在的非安全网络环境中的通信协议,特别是认证协议.与类BAN的那一类逻辑相比,文中的方法可以直接转化成算法实现,对协议本身进行操作,而不需对协议进行一些难以把握的抽象判断.而且,在这套理论的基础上开发了安全协议分析器SPV.文中的方法是基于证明的而不是证伪的,即证明协议的正确性而不是找协议漏洞.     

UC安全的并行可否认认证新方法

可否认认证协议允许认证者向接收者认证某个消息，但是接收者不能向第三方证明该认证消息的来源．在考虑开放的异步多方通信网络环境和自适应的主动攻击者能力的情形下，基于UC（universally composable）安全模型提出了解决并行可否认认证问题的新方法．根据可否认认证协议的安全目标，定义了形式化的并行可否认认证理想函数FCDA，然后，利用可验证平滑投影散列函数构造了一个具体的协议方案，在公共参考串模型中，新的协议方案是可证明UC安全的，即新方法能够保证可否认认证协议的不同实例在并行复合情形下是安全的，当与其他协议同时运行时具有非延展性．为了实现可否认认证的前向可否认性，新方法基于陷门承诺构造了新的投影密钥函数和可验证平滑投影散列函数，基于证人不可区分，协议的安全性可以归约为确定性复合剩余假设，改善了协议的计算效率和通信效率．     

量子安全线路评估

鉴于经典安全线路评估存在的问题, 提出了一个量子解决方案. 在该方案中, 冗余纠缠态粒子插入法和量子签名协议被用来保证协议的安全性. 理论分析证明, 该协议对于经典攻击和量子攻击均具有很高的安全性.     

Clifford代数与几何定理机器证明

Clifford代数是一种深深根植于几何学之中的代数系统。近年来,它在微分几何、理论物理、经典分析等方面取得了辉煌的成就,是现代理论数学和物理的一个核心工具,并在现代科技的各个领域,如机器人学、计算机视觉等方面有广泛的应用。本文主要介绍Clifford代数在数学机械化的核心内容－几何定理机器证明中的应用。作为一种非常优秀的描述和计算机几何问题的代数语言,Clifford代数对于几何体,几何关系和几何变换有不依赖于坐标的、易于计算的多种表示,因而应用它进行几可自动推理,不仅使困难定理的证明往往变得极为简单,而且能够解决著名的数学公开问题。目前在国际上,几何自动推理已经成为Clifford代数的一个重要应用领域。     

基于身份密码系统下Canetti-Krawczyk模型的安全扩展

Canetti-Krawczyk(CK)模型是分析密钥交换协议的一种形式化方法, 如果一个密钥交换协议用该模型证明是安全的, 则CK模型能够确保该协议具备许多安全属性. 但是我们发现在基于身份的密码系统下该模型不具有确保密钥生成中心(KGC)前向保密性的能力, 而对基于身份的密钥协商协议来说KGC前向保密性是一个重要的安全属性. 通过分析研究发现引起该缺陷的主要原因是CK模型没有充分考虑在基于身份的密码系统下攻击者的能力, 所以在该系统下通过对CK模型增添一个新的攻击能力: 攻陷KGC, 来对该模型进行了相应的扩展, 通过扩展该模型具有确保KGC前向保密性的能力.     

基于挑战——响应的安全协议分析

安全协议的本质是协议主体采用密码学方法通过挑战一响应来对协议其他方的存在做出判断，同时完成一些数据如会话密钥的协商．大部分国内外现有的分析方法或者采用状态检测等定理证明技术，或者采用认证逻辑等推理技术，存在着分析能力与可操作性之间的矛盾．为了解决这个问题，文中提出一种新的安全协议保密性和关联性的分析方法，该方法基于线空间模型理论给出了协议保密目标和认证目标的形式化定义，采用认证逻辑作为基础分析手段．保密性分析被分解为显式泄密和隐性泄密两种情况，其中隐性泄密分析依赖于关联性的判断，而关联性的分析被总结为Strand的存在关系和参数一致性分析的问题．新的分析方法既具有线空间模型的分析能力，又具有认证逻辑的易用性．     

公平交换协议的一个形式化模型

基于对现有公平交换协议的研究，使用求精过程建立了精确的形式化结构模型，在这一过程中，使用不可靠信道模拟攻击行为．模型首次给出了交换项的形式化定义，提出的公平性、可追究性目标能够更加完整地反映公平交换协议的内在要求．为了能高效而又细致地对协议进行检测、证明和设计，模型提出了适用于所有公平交换协议的不可滥用性的新性质，给出了第三方可信赖串的定义和设计安全高效的公平交换协议的一般准则．文中通过一个典型的公平交换协议分析实例，阐明了使用该模型分析公平交换协议的详细步骤．发现了一种过去从未发现过的新攻击，给出了攻击发生时系统运行的全过程，深刻揭示了攻击发生的各种原因．最后，对有缺陷的协议进行了改进，改进后的协议满足所需要的各种性质．     

扩展的语义分析的WAP协议缺陷测试

首先介绍了一种基于语义分析的缺陷测试技术.该测试方法利用语义测试及软件错误注入来进行测试.它比传统测试的成本要小,同时能达到很好的效果.但该方法只能检测协议实现级别的漏洞,而不能检测协议设计中可能存在的缺陷.本文结合了Petri网在协议测试方面的优点提出了一种扩展的语义分析的协议缺陷测试方法.它能通过对协议Petri网模型的分析来捕获协议层面的缺陷,而为此所需的额外开销是很小的.这弥补了原缺陷测试在协议层面的不足.之后对该方法各个阶段进行了介绍.对WAP-WSP协议的进行了缺陷测试,并对结果进行了分析,证明其可行性.     

常规隐信道下可证明安全隐写术的有效构造方法

隐写术是在看起来无害媒体中隐藏信息的科学.文中为了解决在常规隐信道下可证明安全隐写术的有效构造问题,在不依赖于任何采样假设的前提下,提供了一种基于计算不可区分的安全隐写术构造.文中结果表明,隐信道采样器中影射函数的不可区分性是安全隐写系统抵抗自适应选择隐文攻击的必要条件.在此基础上,完整地证明了l(-1+5-2)—安全隐写系统能在-1伪随机函数和-2无偏采样函数下有效地被构造,其中,-1和-2是任意两个可忽略错误,l是多项式的隐文长度.更为重要的,文中的研究不依赖于密码系统的密文伪随机性假设和完美采样假设,因此,我们的结果对于安全隐写系统的构造和隐写分析都具有现实意义.     

一种非阻塞消息全序化协议

消息全序化协议是主动复制技术中维护容错组成员状态一致性的关键技术之一．文中提出异步分布环境下的一种非阻塞消息全序化协议NBTOP．非阻塞表现为当主动复制容错组发生演进时，容错组中的成员无需等待进入相同组视图后再继续计算，甚至当决定消息发生冲突时，容错组成员仍能继续各自的计算．NBTOP协议采用令牌环的逻辑控制结构，成员利用再请求机制获得丢失的决定消息内容，通过后继确认机制解决决定消息冲突问题．进一步证明协议NBTOP满足全序性、一致性和终止性．对NBTOP协议进行了测试，与Totem协议做了性能比较，结果表明NBTOP协议具有较好的延迟性能，成员的非阻塞行为有利于提高协议的执行效率．     

通用可组合的可信网络连接模型和IF-T中的EAP-TNC协议

在UC框架下,研究了可信网络连接（TNC）协议.首先,设计了TNC理想函数F_TNC,EAP认证理想函数F_EAP以及EAP-TNC理想函数F_E-PA,构造了通用可组合的可信网络连接安全模型.其次,在(F_EAP,F_E-PA)-混合模型下提出了通用可组合安全的TNC协议TK-TNC.然后,通过安全性分析,得出D-H PN协议不能实现理想函数F_E-PA.最后,使用Twin DH交换技术设计了TD-H PN协议.通过证明分析,结果表明TK-TNC在(F_EAP,F_E-PA)-混合模型下安全实现F_TNC;基于CDH假设,TD-H PN可以在(F_REG,F_CERT)-混合模型下安全实现F_E-PA.     

一类同步合成网合法发射序列判定的一个多项式时间算法

研究了同步合成网的语言性质，针对一类同步合成网，提出合法发射序列的一个多项式判定算法. 从而将这类问题的多项式可解性从坚持网、无冲突网和状态机网的仅有Petri网子类，推广到更为广泛的这些子类的同步合成Petri网. 一般Petri网的这类问题的判定是NP完全问题. 因此，寻求这类问题的多项式可解性的任何更广网类的判定算法一直是重要的研究课题.     

可验证安全外包矩阵计算及其应用

矩阵计算在科学计算和密码学领域中都有着重要的作用.许多密码协议、科学和数值计算问题都涉及到了矩阵计算.然而,对那些计算能力有限的用户来说,独立完成矩阵计算并不是件容易的事情.云计算拥有强大的计算资源,它使得用户的计算能力不再受限于他们的资源约束型设备,他们可以外包工作量给云.本文围绕矩阵计算展开研究,针对矩阵乘积、矩阵的行列式以及矩阵的逆这3种运算,分别设计了切实可行的可验证安全外包协议.与已有的关于这3种可验证外包计算的协议相比,我们的协议在效率和安全性方面都有了改进,而且我们的协议不需要任何的密码学假设.本文中,还为我们的协议给出两个具体应用,即为＂大型线性方程组的求解＂以及＂基于纠错码的密码体制的实现＂这两个问题分别构造了高效的可验证外包计算协议.     

弱条件下随机梯度算法性能分析

在弱条件下,利用随机鞅理论详细研究了随机梯度辨识算法的收敛性能.分析表明,只要信息向量是持续激励的(或数据乘积矩矩阵条件数有界),过程噪声是零均值不相关的,那么参数估计一致收敛于真参数.这一结论并不要求一些文献中所作的苛刻假设成立,既没有假设噪声方差和高阶矩存在,又没有假设系统是平稳和各态遍历的,也没有假设强持续激励条件成立.这一贡献放松了随机梯度算法的收敛条件.噪声方差有界和无界时的仿真例子证明了提出的收敛结论.     

密码协议的代数模型及其安全性

引入了一个新的代数系统——称为密码协议代数(cryptographic protocol algebra, CPA), 刻画具有多种密码运算的消息代数性质, 并基于CPA提出了一个新的密码协议代数模型. 模型中, 用子代数、自由生成元和多项式代数等概念刻画主体的知识扩张过程, 并用类似于代数中的正合序列概念描述了密码协议的攻击过程, 从而为密码协议的安全性分析建立了一种数学方法. 基于这个模型, 利用代数的技巧证明了对于具有一定对称性的协议, 任意多主体参与运行的协议安全性分析可归结为几个主体与攻击者参与的协议安全性分析. 研究了密码协议安全的一致性问题, 给出了两个协议合成保持安全性的一个充分条件, 并提供两个安全的密码协议的合成安全的例子, 推广了相关工作.     

一种基于P/T网的低级并发程序验证模型

随着片上多处理器/多核技术的不断发展,采用机器级语言的并发程序(低级并发程序)有了更加广阔的应用前景.然而,低级并发程序的验证问题也成为程序语言领域一种新的挑战.并发程序安全性验证领域现有的工作多数是针对高级语言、规范或者演算,而针对机器级语言的甚少。这种情况的主要原因之一是缺少低级抽象模型.文中描述一种可验证的低级并发编程模型P-PMCC.P-PMCC程序是一个扩展的P/T网系统,其网结构用来刻画低级并发线程(原子的顺序汇编级代码)之间的并发关系.P-PMCC程序的验证采取模型检查和定理证明相结合的方法,分开考虑并发行为与顺序线程的规范和验证:前者借助于Petri网领域已有的方法,后者则借助现有的顺序程序的正确性证明方法。P-PMCC程序也可以看作并发程序的一种可验证的低级中间表示.     

基于MRF的统计预测提升算子的构造与应用研究

根据图像的统计信息, 在Markov随机场(MRF)的理论基础上, 构造了一种新的非线性算子即统计算子, 提出了基于该算子的一种非线性提升小波分析方法. 并根据MRF的条件概率分布, 在理论上证明了采用基于统计算子的非线性提升小波变换可使图像变换后, 在无量化失真的前提下, 提高高频子带的零高频系数. 将该方法与现有的几种非线性形态学小波分析方法以及S+P变换和JPEG2000采用的5/3和9/7线性提升小波变换进行了不同图像的测试分析, 实验结果显示, 利用这种基于统计算子的提升小波分析方法对医学图像和混合文档图像变换后可取得较低的加权熵.