基于格的变色龙签名方案

与普通数字签名相比,变色龙签名不仅满足不可否认性,而且具有非交互式、不可传递的特点。然而,基于传统数学难题构造的变色龙签名方案不能抵杭量子计算机的攻击。为了设计在量子计算机环境下依然安全的变色龙签名,利用格上小整数解问题SIS(Small Integer Solution)和非齐次小整数解问题ISIS(Inhomogeneous Small Integer Solution)的困难性假设,构造了基于格的变色龙签名方案。在随机预言模型下,证明了该方案在适应性选择消息攻击下 是安全的。     

基于大整数分解可公开验证的秘密共享方案

基于不定方程整数解的存在性及大整数分解的困难性,以Shamir(t,n)门限方案为基础,提出了一种可公开验证的秘密共享方案.方案利用大整数分解的困难性为共享者建立秘密份额,通过不定方程整数解的存在性计算方程的特解组合,共享秘密由共享者的秘密份额和特解组合元素共同计算恢复;方案实现了对秘密份额、参与者之间及参与者对分发者的有效性验证.安全分析表明,该方案是安全的,具有一定的实际应用价值.     

一种格上基于身份的环签名方案

基于身份的环签名是基于身份密码学和环签名的结合,具有较高的实际应用价值.现有的基于身份的环签名方案大多基于双线性对问题.然而,双线对问题在量子环境下是不安全的.为了设计量子环境下安全的基于身份的环签名方案,本文基于格困难假设,提出一种标准模型下基于身份的格上环签名方案.该方案的安全性基于格中标准的小整数解(SIS)困难假设.与其他标准模型下基于身份的格上环签名方案相比,该签名方案的计算效率进一步提高.     

基于单向累加器的高效可分电子现金方案

基于单向累加器理论和二叉树技术,提出了一个同时具有用户匿名性和交易无连接性的离线可分电子现金方案,方案无需可信第三方参与;加入了概率验证算法,既能有效震慑不法用户、保证银行利益不受损失,又能有效降低系统开销。方案安全性基于决策Diffie-Hellman（DDH）假设、计算离散对数困难性假设以及单向散列函数存在性假设。     

标准模型下格上基于身份的盲签名方案

随机预言模型下的盲签名方案都依赖于随机预言假设,即使方案被证明安全,在实际应用时未必安全。构造了一个标准模型下格上基于身份的盲签名方案。该方案中引入一个短格基派生算法,根据用户的身份产生对应的私钥,并利用Gentry等人提出的原像抽样陷门单向函数产生消息的签名。在标准模型下依据Juels和Pointcheval等人提出的安全模型,基于小整数解问题(small integer solutions,SIS)的困难性,证明了该方案满足one-more不可伪造性。分析表明,与同类方案相比,该方案密钥长度和签名长度有所减小,效率更高。     

高效的基于格的环签名方案

安全高效的环签名方案有很多重要应用.文中提出了一种新的基于格的环签名方案并在标准模型下给出了正式的安全性证明.在标准的小整数解(SIS)困难假设下,该方案对适应性选择消息攻击是强不可伪造的.与现有的标准模型下基于格的环签名方案相比,新方案签名长度更短,计算效率更高,安全性更强.     

纯公钥模型下对NP语言的高效并发零知识证明系统

提出了一种从3轮公开掷币的对任何NP语言的诚实验证者零知识证明系统到纯公钥模型下4轮(轮最优)对同一语言的具有并发合理性的并发零知识证明系统.该转化方法有如下优点:1)它只引起O(1)(常数个)额外的模指数运算,相比Di Crescenzo等人在ICALP05上提出的需要Θ(n)个额外的模指数运算的转化方法,该系统在效率上有着本质上的提高,而所需的困难性假设不变;2)在离散对数假设下,该转化方法产生一个完美零知识证明系统.注意到Di Crescenzo等人提出的系统只具有计算零知识性质.该转化方法依赖于一个特殊的对承诺中的离散对数的3轮诚实验证者零知识的证明系统.构造了两个基于不同承诺方案的只需要常数个模指数运算的系统,这种系统可能有着独立价值.     

一种基于CL的新型可分电子现金系统

基于CL签名给出了一种新型的可分电子现金系统,有效地将压缩支付和批处理支付加入到系统中,给出了实用的压缩可分电子现金方案,使得系统的效率较高.系统中无需可信第三方的参与,系统开销较小.方案的安全性基于LRSW假设、计算离散对数困难性假设以及单向散列函数存在性假设.     

基于四元整数的ElGamal公钥密码体制

介绍了既约剩余类的概念以及四元整数的一些基本性质,提出了基于四元整数群的ElGamal公钥密码体制(PKC),其安全性基于大整数分解和离散对数问题的困难性,并在计算机上进行模拟实现,分析了其安全性。     

基于双曲线映射签名的高效可分电子现金系统

基于双曲线映射的签名设计了一种新型可分电子现金方案,方案中有效地加入了压缩支付和批处理支付,计算时间复杂度较小,从而使得系统的整体效率较高。另外,方案中无需可信第三方(TTP)的参与,因而系统的整体开销较小。方案的安全性基于q-SDK假设、计算离散对数困难性假设以及单向散列函数存在性假设。     

基于模运算的新颖离散差分演化算法求解多背包问题

多背包问题（MKP）是一个求解难度极大的背包问题。为了基于差分演化（DE）求解MKP,首先建立了MKP的整数规划模型,在利用模运算构造简单且有效的新型传递函数基础上,提出了一个新颖离散差分演化算法MODDE;基于贪心策略提出了消除MKP不可行解的一个有效算法GROA,由此利用MODDE给出了求解MKP的一种新方法。最后,利用MODDE求解30个国际通用的MKP实例,通过与四个代表性演化算法的比较表明,MODDE不仅计算结果优,而且算法的稳定性强,是求解MKP的一个高效算法。     

电梯群控系统调度模型及其改进ADMM分解算法

电梯群控系统调度问题(EDP)是具有非线性目标函数、较短求解时间要求的一类组合优化问题,针对此问题,提出一种基于时空状态网络的EDP问题线性化方法,并构建对应的线性0-1整数规划模型.为高效求解上述模型,在ADMM分解算法框架的基础上,为拉格朗日乘子次梯度迭代过程引入空间膨胀法(space dilation)应对算法迭代时间较短的问题,为二次项乘子设计基于迭代时间的更新形式,进而给出更加适配短时求解的改进ADMM分解算法.数值实验结果表明,在实际问题规模与500ms系统响应时间要求下,所提出的方法相较既有启发式算法具有更好的求解效果,相较商用求解器Gurobi-9.0.1提供的分支定界算法具有更短的求解时间,能够稳定高效地求解EDP问题.     

求解公共自行车再平衡问题的克隆选择算法

公共自行车系统再平衡调度事关城市公共自行车系统的运营效率与客户服务水平高低。在已有研究基础上,设计了求解BRP的人工免疫克隆选择算法,算法采用多维整数编码方法,结合问题特点设计了新的抗体相似性度量方法及抗体抑制策略,并在算法框架中引入二次应答求解机制。运用标准算例测试一次应答表明:该算法在求解规模小于50个点的问题上均能找到最优解,但平均CPU消耗比精确算法快96.80%,在求解规模为50个点到100个点的问题上,该算法求解质量比精确算法低7.43%,与遗传算法相当,平均CPU消耗比精确算法快96.8%;运用改进标准算例进行二次应答测试表明:二次应答的求解质量比一次应答略高,二次应答的求解CPU消耗比一次应答快39%以上。     

整数质因子分解算法新进展与传统密码学面临的挑战

大整数的质因子分解研究是现代数论领域的一个重要课题,其中涉及很多开问题.随着信息时代的来临,大整数质因子分解的复杂性更成为现代密码学的重要理论基础.著名的RSA公钥密码系统的安全性即建立在解决此问题的困难性之上.本文系统地综述了现代理论计算机科学研究中提出的几种解决该问题的新算法,并介绍了量子计算机高效解决此问题的原理和实现方式.最后,本文讨论了在未来量子计算时代传统密码学所面临的挑战并展望了量子密码学的前景.     

A solution approach based on Benders decomposition for the preventive maintenance scheduling problem of a stochastic large-scale energy system

This paper describes a Benders decomposition-based framework for solving the large scale energy management problem that was posed for the ROADEF 2010 challenge. The problem was taken from the power industry and entailed scheduling the outage dates for a set of nuclear power plants, which need to be regularly taken down for refueling and maintenance, in such a way that the expected cost of meeting the power demand in a number of potential scenarios is minimized. We show that the problem structure naturally lends itself to Benders decomposition; however, not all constraints can be included in the mixed integer programming model. We present a two phase approach that first uses Benders decomposition to solve the linear programming relaxation of a relaxed version of the problem. In the second phase, integer solutions are enumerated and a procedure is applied to make them satisfy constraints not included in the relaxed problem. To cope with the size of the formulations arising in our approach we describe efficient preprocessing techniques to reduce the problem size and show how aggregation can be applied to each of the subproblems. Computational results on the test instances show that the procedure competes well on small instances of the problem, but runs into difficulty on larger ones. Unlike heuristic approaches, however, this methodology can be used to provide lower bounds on solution quality.     

Effective reformulations for task allocation in distributed systems with a large number of communicating tasks

In any distributed processing environment, decisions need to be made concerning the assignment of computational task modules to various processors. Many versions of the task allocation problem have appeared in the literature. Intertask communication makes the assignment decision difficult; capacity limitations at the processors increase the difficulty. This problem is naturally formulated as a nonlinear integer program, but can be linearized to take advantage of commercial integer programming solvers. While traditional approaches to linearizing the problem perform well when only a few tasks communicate, they have considerable difficulty solving problems involving a large number of intercommunicating tasks. This paper introduces new mixed integer formulations for three variations of the task allocation problem. Results from extensive computational tests conducted over real and generated data indicate that the reformulations are particularly efficient when a large number of tasks communicate, solving reasonablylarge problems faster than other exact approaches available.     

An Interactive Reference Direction Algorithm For Solving Multi-Objective Convex Nonlinear Integer Programming Problems

We present a learning-oriented interactive reference direction algorithm for solving multi-objective convex nonlinear integer programming problems. At each iteration the decision-maker (DM) sets his/her preferences as aspiration levels of the objective functions. The modified aspiration point and the solution found at the previous iteration define the reference direction. Based on the reference direction, we formulate a mixed-integer scalarizing problem with specific properties. By solving this problem approximately, we find one or more integer solutions located close to the efficient surface. At some iteration (usually at the last iteration), the DM may want to solve the scalarizing problem to obtain an exact (weak) efficient solution. Based on the proposed algorithm, we have developed a research-decision support system that includes one exact and one heuristic algorithm. Using this system, we illustrate the proposed algorithm with an example, and report some computational results.     

基于格结构优化的环签名认证安全强化机制

针对当前国内外环签名安全机制在具体实践中的安全隐患,本文提出了基于格结构的强约束验证方环签名安全机制(SCLS_IM)算法。该算法根据已有的小整数解困难问题,引入强约束概念,完善了SDVS机制,在很大程度上降低了签名时间周期,充分确保安全性的基础上,减小了签名长度,能够有效抵抗适应性选择消息攻击,对其具有强不可伪造性。通过安全性与性能分析,SCLS_IM机制存在诸多方面的优势,其安全性相对较高,同时性能效率相对较高。     

基于单纯形法和局部枚举解混合整数线性规划问题

提出了一种基于单纯形法和局部枚举求解整数线性规划问题的新方法。它通过单纯形法得到松弛问题的最优解并确定变量以及目标函数取值范围,然后基于目标函数,进行局部枚举,从而得到其整数线性规划问题的最优解,与现有方法比较,新解法简单,计算量少,尤其是对于大规模整数线性规划问题,计算量少体现地更明显。     

结束时间不确定的投资组合选择问题建模与模型求解方法

针对结束时间具有不确定性的投资问题,建立以区间风险值(PVaR)度量市场风险的收益最大化投资组合选择模型.PVaR计算的复杂性使得模型难以运用一般优化方法求解,因此提出并证明可以通过求解等效的混合整数规划模型来得到原模型的最优解.利用实际股价数据进行数值实验分析,结果表明,求解混合整数规划模型针对小规模短期投资问题可以快速给出最优投资决策方案.