视觉密码方案的构造

视觉密码学是在最近十余年间逐渐发展起来的新型密码学分支。近年从事视觉密码学研究的学者越来越多，研究结果频现于三大密码学会和Journal of Cryptology, Designs, codes and cryptography和IEEE Transactions on Image Processing等高水平期刊上。视觉密码方案（VCS）具有的针对图片加解密，视觉解密，秘密共享和无条件安全等特点，较之传统的秘密共享方案，它具有解密设备简单的优点，解密过程不需要使用者拥有任何密码学知识，可以直接观察到解密图片。而较之传统的秘密隐藏方案，他具有信息容量大的优点，可以加密整幅图片的秘密信息，而且由于其加解密的对象是图片，因此其信息内容可以灵活多变。视觉密码方案可以应用在秘密共享，信息隐藏，身份认证/鉴别以及版权保护等方面。随着具有更多特殊性质的视觉密码方案的提出，其应用范围也会越来越广。本文的工作主要集中在两个方面：视觉密码方案的构造和分析以及视觉密码相关问题的研究。 在视觉密码方案的构造和分析方面，本文所做的工作主要包括： 本文在第二章提出一个利用嵌入技术构造有意义分享图片视觉密码方案（EVCS）的方法。与已知的构造相比，其优点包括：(1) 可以直接处理灰度图片；(2) 具有较小的秘密图片像素扩张；(3) 可以针对一般存取结构构造，且总是无条件安全的；(4)每个参与者只分配一张分享图片；(5) 具有在分享图片像素扩张、分享图片视觉效果和秘密图片像素扩张之间相互取舍的灵活性。 本文在第三章提出了一种针对一般存取结构的VCS的递归构造方法，与过往的VCS相比，在大多数存取结构下，本文的方法在平均像素扩张，像素扩张和对比度方面都有所改进。根据本文的构造方法，可知针对一般存取结构的VCS的构造可以通过递归调用(2,2)-VCS来实现，而无论其所基于的是“OR”还是“XOR”运算。本文的方案最终可能分配给某个参与者多张分享图片，由于平均像素扩张的降低，因此这一点并不能称之为缺点。另外，利用本文中的方案可以构造出针对一般存取结构的基于“XOR”运算的VCS。 对于彩色视觉密码方案（CVCS），基于Naor-Shamir视觉密码模型，本文在第四章提出一个的没有像素扩张的(k,n)-CVCS，以及与对应的黑白(k,n)-EVCS具有相同像素扩张的(k,n)-CEVCS；基于Tuyls视觉密码模型，本文首先分别提出了黑白(k,n)-VCS和黑白(k,n)-EVCS，并以此为构件提出(k,n)-CVCS和(k,n)-CEVCS。仿真实验结果表明，本文提出的方案具有较好的视觉效果。 对于防止欺骗的视觉密码方案，本文在第五章首先分析了已知的几种防止欺骗的视觉密码方案（CIVCS）的缺陷，然后提出一个新的CIVCS来避免这些缺陷。本文所提出的CIVCS构建于已知的VCS之上，在只泄漏极少量秘密图片的信息的情况下达到了很高的安全性。并且可以针对一般存取结构。本文所提出的CIVCS也可以应用在底层运算为“XOR”运算的VCS之上。另外，本文所提出的CIVCS可以根据参与者携带验证信息的多少，可以检测出欺骗行为或者可以揪出具体的欺骗者。 本文在第六章研究了基于“XOR”运算的(2,n)-VCS的最优化问题。给出了基于“XOR”运算的(2,n)-VCS的最小像素扩张，以及具有最小像素扩张条件限制下的最大对比度和最大平均对比度。另外给出了基于“XOR”运算的(2,n)-VCS的最大对比度，以及具有最大对比度条件限制下的最小像素扩张。上述四类方案在本文中都给出了具体的构造方法，以及相关对比度，像素扩张和基矩阵的结构性质的证明。本文中的结果表明基于“XOR”运算下的(2,n)-VCS的各个参数都要比基于“OR”运算下的对应的参数要好。本文还证明了构造具有最大对比度的(2,n)-VCS的基矩阵等价于构造具有相应参数且达到最大容量的二元码。故根据本文的研究结果，便可以通过利用已知的构造达到最大容量的二元码的方法来构造具有最大对比度的(2,n)-VCS，最后对于n=2^k-1的情况，本文还给出了一个利用m-序列来构造具有最大对比度的(2,n)-VCS的方法。 本文在第七章证明了Droste提出的基于“OR”运算的(k,n)-VCS同样在“XOR”运算下也成立。同时基于“OR”运算和“XOR”运算的VCS会给参与者带来便利，他们可以根据不同的环境而选择不同的视觉密码模型。另外，本文还提出一个进一步降低VCS的像素扩张的方法，与Tuyls等人所提出的(k,n)-VCS比较，本文的方法可以显著的降低方案的像素扩张。本文在第七章还提出一个可以运行在Tuyls视觉密码模型之上的同色(k,n)-VCS的构造方法，其中每个分享图片都是同色的，而叠加k个分享图片可以得到黑白的秘密图片。本文证明了当k为奇数时，同色的(k,n)-VCS是不存在的，并给出了当k为偶数时，同色(k,n)-VCS的构造方法。同色(k,n)-VCS可以用来防止分享图片被隐蔽的监控摄像头窃取。 在视觉密码相关问题的研究方面，本文所做的工作主要包括： 本文在第八章研究了视觉密码方案的幻灯片对齐问题，证明了，在幻灯片没有精确对齐的情况下，人眼仍能观察到秘密图片，且其平均对比度满足-(m-r)e/(m2(m-1))。这项研究可以为确定幻灯片中像素的尺寸做参考。本研究也证明了视觉密码方案本身具有一定的纠错能力。 本文在第九章研究了视觉密码中的对比度定义的表示问题。首先给出了四个关于VCS对比度的观察结论，并分析了已知的几种对比度定义的缺陷，从而提出了一个新的对比度定义。本文在理论和实验上说明了，其所提出的对比度定义符合上述观察结论，可以更精确的衡量所恢复的秘密图片的视觉效果。本文最后还针对概率视觉密码方案的定义给出了针对概率视觉密码方案的对比度的定义。 最后我们对本文的工作进行了总结，并对今后的一些研究方向进行了展望。

并行最优路径算法及K优路径算法研究

最优路径问题是计算机科学、运筹学、工程设计等领域很多问题的基础。它的应用包括网络路由、电路设计、交通运输、机器人运动规划、事务调度中关键路径的计算以及VLSI设计等。同时，它也为很多最优化问题提供了解决框架，如背包问题、分子生物学中的序列比对、内接多边形的构造和长度受限的霍夫曼编码等都可以转化成最优路径问题进行求解。 求解网络中最优路径的方法可以分为两大类。一种是标号设定算法（label setting ,LS）,另一种是标号改变算法（label correcting ,LC）。由于网络路径算法的应用越来越强调动态性和及时性，使得高效求解最优路径问题变得越来越重要。在这里，我们利用一种高效的网络划分方法，实现了基于网络划分的LS/LC并行算法。实验结果表明，基于这种网络划分的并行算法对于求解最优路径有很好的加速比和扩展比。 在许多更加复杂的应用中，不仅要求计算出最优路径，而且要求给出前K优路径。K优路径是长期研究的泛化最优路径问题，即不但要求得到最优路径，还要得到次短、再次短等路径。 节点s到节点t的K优路径问题可以分为两大类：一类是求解K优非简单路径，即得到的路径可以包含环路；另一类是求解K优简单路径，即路径是简单通路，不包含环路。经过大量学者的研究，求解K优非简单路径相对容易。Fox 于1975年提出了复杂度为O(m+nlogn) 的求解K优非简单路径的算法，最近， Eppstein于1998年给出了一种优化的求解K优非简单路径的算法，时间复杂度达到了O(m+nlogn+k) ，基本上达到了理论下限。 在2000年对E 的算法进行并行化，时间复杂度为 。求解K优简单路径已被证明是更为具有挑战性，这个问题最先由Hofman和Pavley 在1957年进行开始研究，但几乎所有试图解决该问题的算法时间复杂度都达到指数时间。众所周知，Yen提出了一结果比较好的算法，利用现代的数据结构达到O(kn(n+nlogn)) 时间复杂度。John Hershberger于2007年给出了一个新的求K优路径的算法，该算法基于有效率的替代路径算法,相对于以前的替代路径算法，其加速比可达到O(n) 。在本文中，我们基于John Hershberger给出的K优路径算法，尝试给出其并行的方法，并在SMP的高性能计算机上进行了测试。 关键词 并行算法、最优路径、K优路径、网络划分

一种基于动态自适应数据窗口的模糊k-均值聚类缺失数据估算算法

完整性是数据质量的一个重要维度,由于数据本身固有的不确定性、采集的随机性及不准确性,导致现实应用中产生了大量具有如下特点的数据集:1)数据规模庞大;2)数据往往是不完整、不准确的.因此将大规模数据集分段到不同的数据窗口中处理是数据处理的重要方法,但缺失数据估算的相关研究大都忽视了数据集的特点和窗口的应用,而且回定大小的数据窗17容易造成算法的准确性和性能受窗口大小及窗口内数据值分布的影响.假设数据满足一定的领域相关的约束,首先提出了一种新的基于时间的动态自适应数据窗口检测算法,并基于此窗口提出了一种改进的模糊k-均值聚类算法来进行不完整数据的缺失数据估算.实验表明较之其他算法,不仅能更适应数据集的特点,具有较好的性能,而且能够保证准确性.

missing data imputation: a fuzzy k-means clustering algorithm over sliding window

Tianjin University of Technology