Ants can orienteer a thief in their robbery

The Thief Orienteering Problem (ThOP) is a multi-component problem that combines features of two classic combinatorial optimization problems: Orienteering Problem and Knapsack Problem. The ThOP is challenging due to the given time constraint and the interaction between its components. We propose an Ant Colony Optimization algorithm together with a new packing heuristic to deal individually and interactively with problem components. Our approach outperforms existing work on more than 90% of the benchmarking instances, with an average improvement of over 300%.     

Solving multiobjective,multiconstraint knapsack problems using mathematical programming and evolutionary algorithms

In this paper, we solve instances of the multiobjective multiconstraint (or multidimensional) knapsack problem (MOMCKP) from the literature, with three objective functions and three constraints. We use exact as well as approximate algorithms. The exact algorithm is a properly modified version of the multicriteria branch and bound (MCBB) algorithm, which is further customized by suitable heuristics. Three branching heuristics and a more general purpose composite branching and construction heuristic are devised. Comparison is made to the published results from another exact algorithm, the adaptive ε-constraint method [Laumanns, M., Thiele, L., Zitzler, E., 2006. An efficient, adaptive parameter variation scheme for Metaheuristics based on the epsilon-constraint method. European Journal of Operational Research 169, 932–942], using the same data sets. Furthermore, the same problems are solved using standard multiobjective evolutionary algorithms (MOEA), namely, the SPEA2 and the NSGAII. The results from the exact case show that the branching heuristics greatly improve the performance of the MCBB algorithm, which becomes faster than the adaptive ε -constraint. Regarding the performance of the MOEA algorithms in the specific problems, SPEA2 outperforms NSGAII in the degree of approximation of the Pareto front, as measured by the coverage metric (especially for the largest instance).     

A multi-level search strategy for the 0-1 Multidimensional Knapsack Problem

We propose an exact method based on a multi-level search strategy for solving the 0-1 Multidimensional Knapsack Problem. Our search strategy is primarily based on the reduced costs of the non-basic variables of the LP-relaxation solution. Considering that the variables are sorted in decreasing order of their absolute reduced cost value, the top level branches of the search tree are enumerated following Resolution Search strategy, the middle level branches are enumerated following Branch & Bound strategy and the lower level branches are enumerated according to a simple Depth First Search enumeration strategy. Experimentally, this cooperative scheme is able to solve optimally large-scale strongly correlated 0-1 Multidimensional Knapsack Problem instances. The optimal values of all the 10 constraint, 500 variable instances and some of the 30 constraint, 250 variable instances of the OR-Library were found. These values were previously unknown.     

Cryptanalysis of a Matrix-based MOR System

We cryptanalyze a recently proposed matrix-based MOR cryptosystem. The security of the system depends on the difficulty of solving the following discrete logarithm problem: given an inner automorphism φ of SL(d, 𝔽 _q ) and φ ^a (each given in terms of their images on generators of SL(d, 𝔽 _q )), find a. We show that this problem can be reduced to a small number of similar problems in quotients of polynomial rings and solved in subexponential-time.     

一种改进的2w-ary快速标量乘算法

标量乘是椭圆曲线密码体制(ECC)的基本运算,也是最耗时和极易受到攻击的运算之一。针对利用重编码和R-L技术实现2w-ary快速标量乘算法的不足,对该算法进行了改进。在保持抗SPA的前提下,改进算法使用绝对值,避免了负数做数组下标的使用,减少了50%的存储量,节约了赋值后的消除操作。理论分析表明,改进算法优于原算法,算法的运算量降低2w次。数字验证表明,改进算法比原算法快约17%。     

Knapsack problems with setups

Knapsack problems with setups find their application in many concrete industrial and financial problems. Moreover, they also arise as subproblems in a Dantzig–Wolfe decomposition approach to more complex combinatorial optimization problems, where they need to be solved repeatedly and therefore efficiently. Here, we consider the multiple-class integer knapsack problem with setups. Items are partitioned into classes whose use implies a setup cost and associated capacity consumption. Item weights are assumed to be a multiple of their class weight. The total weight of selected items and setups is bounded. The objective is to maximize the difference between the profits of selected items and the fixed costs incurred for setting-up classes. A special case is the bounded integer knapsack problem with setups where each class holds a single item and its continuous version where a fraction of an item can be selected while incurring a full setup. The paper shows the extent to which classical results for the knapsack problem can be generalized to these variants with setups. In particular, an extension of the branch-and-bound algorithm of Horowitz and Sahni is developed for problems with positive setup costs. Our direct approach is compared experimentally with the approach proposed in the literature consisting in converting the problem into a multiple choice knapsack with pseudo-polynomial size.     

基于椭圆曲线密码体制的无线传感器网络对偶密钥管理的研究

提出了一种适用于无线传感器网络的基于椭圆曲线密码体制的对偶密钥管理方案,引入了证书服务,可以实现密钥的分配、更新、撤销以及新加入节点时的密钥生成．分析结果表明,与现有的密钥更新方案比较,基于椭圆曲线密码体制的无线传感器密钥更新方案有效地减少了密钥的存储空间;在密钥更新阶段中加入保密和认证功能,增加了网络攻击的难度．     

基于神经网络混沌吸引子公钥加密算法的FPGA实现

利用具有顺序和并行执行的特点的VHDL语言,设计并实现了基于神经网络混沌吸引子的公钥加密算法,在编解码器设计中采用专用的控制模块来控制加密和解密操作;同时,在RAM模块中自主设计了具有并行读写功能的子模块,以进一步提高算法的数据加密速度;整个系统在DE2实验平台中经过反复实验测试和试运行,结果表明该算法是可以硬件实现的,并且具有较高的数据加密速度,时钟频率可达50 MHz以上.     

基于Polar码改进的抗量子密码方案

为了促进抗量子密码方案的实用化,在Mostafa Esmaeili方案的基础上,利用Polar码的极化性质改进抗量子密码方案,把信息比特作为原方案中的明文,把冻结比特作为原方案中的随机比特串。改进后的方案没有改变原方案的结构,可以抵御目前已知的信息集译码攻击,达到了IND-CPA(indistinguishability chosen ciphertext attacks)安全。选择合理的参数,使得改进方案的整体密钥尺寸比McEliece的整体密钥尺寸减少了70%,提高了方案的实用性,为即将来临的5G时代提供了一种新型抗量子密码方案。