基于量子克隆的二面体群隐含子群问题量子算法的研究

基于最短向量问题的格公钥密码体制是典型的抗量子计算密码体制。格的唯一最短向量问题可转化为二面体群的隐含子群问题。有效地求解二面体群的隐含子群问题可攻破基于格的唯一最短向量问题的公钥密码体制。Kuperberg提出了二面体群隐含子群问题的半指数级量子算法。通过研究Kuperberg量子算法,利用概率量子克隆,文中提出了二面体群隐含子群问题的多项式时间量子算法。     

基于辫群的代理盲签名方案

由Shor等人构造的量子算法可以在多项式时间内解决传统三大难解问题而利用辫群构造的很多数学困难问题,在量子计算机条件下均无有效的解法,辫群是一种适合构造抵抗量子密码分析的计算平台。利用左右子群元素的可交换性,基于CSP问题、SCSP问题和p次方根问题的难解性,提出了一个新的代理盲签名方案,并通过方案分析验证了该方案的有效性和可行性。     

密码体制的量子算法分析

很多快速量子算法都可以归结为隐子群问题的讨论,本文回顾了隐子群问题量子算法的基本思想,分析了群上量子算法的优越性。分析了可以归结为隐子群问题的公钥密码体制,描述了求解椭圆曲线上离散对数问题的量子算法,讨论了隐子群问题量子算法的局限性。     

辫群上的非平衡比特承诺协议*

为构造抗量子攻击的密码协议,以非交换的辫群为平台,基于求根问题的难解性提出了一个非平衡比特承诺协议。分析表明,协议具有绑定性和隐藏性,且协议执行过程不涉及共轭判断运算,在计算上比基于共轭搜索问题的比特承诺协议更有效。     

蚁群与粒子群混合算法求解TSP问题

旅行商问题（TSP）是最古老而且研究最广泛的组合优化问题。针对TSP问题,提出一种蚁群与粒子群混合算法（HAPA）。HAPA首先将蚁群划分成多个蚂蚁子群,然后把蚂蚁子群的参数作为粒子,通过粒子群算法来优化蚂蚁子群的参数,并在蚂蚁子群中引入了信息素交换操作。实验结果表明,HAPA在求解TSP问题中比传统算法和同类算法更具优越性。     

基于多层量子粒子群优化算法和Toy模型的蛋白质结构预测研究

蛋白质结构预测,作为计算生物学基本问题之一,是个典型的NP难解问题.研究表明合理运用算法,借助物理模型,可用于预测蛋白质结构.Toy模型就是较为简单的类,其势能最低状态的确定则为结构预测的关键所在.量子粒子群算法是典型的智能优化算法,己广泛应用于多种系统寻优问题中.本篇文章提出使用1种改进的量子粒子群优化算法,并结合Toy模型,进行蛋白质结构预测.算法的改进在于对每次迭代的粒子,排序之后将种群分成精英子群、开采子群和勘探子群来区别处理,并通过实验进行运算和预测.结果表明运用改进的量子粒子群优化算法来进行蛋自质折叠结构预测是可行的且高效的.     

基于辫群的指定验证者的签名方案

辫群是一种非交换的无限群,该群中有许多困难问题是不可解的,如字问题、共轭问题和根问题等,利用这些困难问题可以去设计一些密码协议。介绍了辫群的基本概念和辫群中的困难问题,在此基础之上,利用辫群中左右子群的元素可交换性,提出了一个基于辫群上的共轭查找问题和p次根问题的指定验证者的签名方案,通过分析可知,该方案具有简单实用、算法速度快和高效安全的特性。     

多群多策略差分大规模多目标优化算法

针对差分进化算法在解决大规模多目标优化问题时,出现优化后期多样性不足、收敛速度慢等问题,提出一种多群多策略差分大规模多目标优化算法.根据个体特性不同,将种群分为3个等级不同的子群,利用多群策略的优势维持种群多样性.为减少种群陷入局部最优的概率,在不同等级的子群中引入多个变异策略以较好地平衡子群个体的多样性和收敛性.为保证不同子群间信息得到有效交换,根据3个子群的进化状态确定重新分群时机,既保证个体在本群内得到充分进化,又保证个体在一定的条件下进行信息交换.为利用更多的信息生成优秀的子代,将更新后的子群与其父代子群合并,选出下一代子群.为验证所提出算法的有效性,在一组大规模基准测试问题上评估算法的性能,实验结果表明,所提出算法在两个常用测试指标IGD和HV上明显优于其他对比算法.     

辫群上的不经意传输协议*

量子计算的快速发展给基于整数分解或离散对数问题的密码协议带来严重威胁。为了研究抵抗量子分析的密码协议,基于非交换的辫群提出了一个2取1不经意传输协议,并将其扩展为N取1不经意传输协议。在共轭搜索问题和多重共轭搜索问题难解的前提下协议能同时保证发送方和接收方的隐私性。     

辫群上的可转换认证加密方案

量子计算的快速发展给目前的公钥密码体制带来严重威胁,非交换的辫群为构造安全密码协议提供了新平台。基于辫群上共轭搜索问题和多重共轭搜索问题的难解性,提出一个可转换认证加密方案,只有指定的接收者才能恢复认证的原始消息;当发送者否认签名时,接收者不需要发送方的参与即可将收到的签名转换为一般签名,并向第三方证明发送者的不诚实。与基于交换代数的方案相比,该方案在抗量子攻击上更有优势。     

Unconditionally secure cryptosystems based on quantum cryptography

Most modern cryptographic studies design cryptosystems and algorithms using mathematical concepts. In designing and analyzing cryptosystems and protocols, mathematical concepts are critical in supporting the claim that the intended cryptosystem is secure. Most early cryptographic algorithms are based either on factorization or on discrete logarithm problem. Such systems generally adopt rather simple mathematics, and, therefore, need extensive secondary index computation. This study discusses quantum cryptosystems, protection of system security, and optimization of system efficiency. Quantum cryptography detects intrusion and wiretap. In quantum mechanics, a wiretap is neither external nor passive; rather it modifies its entity based on the internal component of the system. The status of the quantum system changes once a wiretap is detected. Hence, only the designer of the system can discover the quantum status of the system; an eavesdropper can neither determine the quantum state nor duplicate the system. The quantum cryptosystem can achieve unconditional security, and thus guarantees secure communication.     

Quadratic and higher-order unconstrained binary optimization of railway rescheduling for quantum computing

Quantum Information Processing - The dihedral coset problem (DCP) that comes from the hidden subgroup problem over dihedral group is one of the fundamental problems in quantum computation, and its...     

Is Grover’s Algorithm a Quantum Hidden Subgroup Algorithm?

The arguments given in this paper suggest that Grover’s and Shor’s algorithms are more closely related than one might at first expect. Specifically, we show that Grover’s algorithm can be viewed as a quantum algorithm which solves a non-abelian hidden subgroup problem (HSP). But we then go on to show that the standard non-abelian quantum hidden subgroup (QHS) algorithm can not find a solution to this particular HSP. This leaves open the question as to whether or not there is some modification of the standard non-abelian QHS algorithm which is equivalent to Grover’s algorithm.      

基于分治的子集积问题DNA计算机算法

如何减少DNA计算机在求解大型科学问题中以问题输入纯指数增长的DNA链数,已成为DNA计算机研究的重要内容。本文将分治策略应用于子集积问题的DNA分子计算中,提出一种求解子集积问题的新的DNA计算机算法。该算法由n位数据搜索器和其它五个子算法组成,其DNA链数可达到亚指数的O（2^q/2）,其中q为子集积问题的维数。与最近文献结结论进行的对比分析表明：新算法将求解子集积问题所需的DNA链数从O（2^q）减少至O（2^q/2）,最大链长度减少为原来的1／2。因此,利用新算法在试管级水平上能将可
破解的子集积公钥的维数从60提高到120。     

后量子可证明安全研究

后量子密码经过数十年的发展，其效率已经趋于实用化，其标准化工作也正在开展中。与此同时，对量子环境中的密码方案的可证明安全理论的研究在近十年也备受关注。本文将介绍近年来后量子可证明安全领域的发展和研究现状，包括经典密码方案在量子环境中的安全模型建立、安全概念定义，以及经典环境和量子环境中的安全性的分离结论和蕴含结论，并重点介绍量子随机谕言模型中的安全性证明。对后量子可证明安全理论的研究，对于合理评估密码算法在量子环境中的安全性、实现到后量子密码算法的安全平稳过渡具有重要意义。     

量子密码与公钥密码体制

现今普遍应用的公钥密码体系,其安全性建立在数学函数问题的计算复杂性基础上。随着量子计算的发展,这种密码体制的安全隐患越来越突出。量子密码安全性基于物理基本原理,具有无条件的安全性,能够实现真正意义上的保密通信。     

An Efficient Quantum Algorithm for the Hidden Subgroup Problem in Nil-2 Groups

In this paper we show that the hidden subgroup problem in nil-2 groups, that is in groups of nilpotency class at most 2, can be solved efficiently by a quantum procedure. The algorithm is an extension of our earlier method for extraspecial groups in Ivanyos et al. (Proceedings of the 24th Symposium on Theoretical Aspects of Computer Science (STACS), vol. 4393, pp. 586–597, 2007), but it has several additional features. It contains a powerful classical reduction for the hidden subgroup problem in nilpotent groups of constant nilpotency class to the specific case where the group is a p-group of exponent p and the subgroup is either trivial or cyclic. This reduction might also be useful for dealing with groups of higher nilpotency class. The quantum part of the algorithm uses well chosen group actions based on some automorphisms of nil-2 groups. The right choice of the actions requires the solution of a system of quadratic and linear equations. The existence of a solution is guaranteed by the Chevalley-Warning theorem, and we prove that it can also be found efficiently.