Approved algorithmic security enhancement of stream cipher for advanced mobile communications

ABSTRACT

Confidentiality and integrity processes are based on SNOW and ZUC algorithms. These standardized algorithms are designed by the 3rd Generation Partnership Project (3GPP) for advanced mobile communication systems. Each algorithm has two S-boxes in its nonlinear layer structure. This paper proposes three different approaches to enhance the security level of both algorithms. The first approach aims to select the best combination of two S-boxes in the nonlinear part of each algorithm. Results showed that the best randomness properties are achieved by combining the Feistel structure (S1-box) and Rijndael (S2-box) in the SNOW algorithm and New Rijndael (S1-box) and Rijndael (S2-box) in the ZUC algorithm. The second approach aims to increase the nonlinearity and complexity of these algorithms by selecting a strong S-box to cascade the best-existing two S-boxes for both algorithms. The third approach is an extension of the former, based on a dynamic reform of such S-boxes as a function of the “Authentication Token” to increase the computational complexity of the upgraded two algorithms. These proposed upgrades are simulated by C language and tested successfully for their statistical properties using the standard NIST SP 800-22 test suite.     

4 bit S盒输入及输出低次代数关系分析

随着4 bit S盒在轻量级密码算法中的广泛应用,如何捕获这些4 bit S盒输入及输出的代数关系成为了目前的研究热点之一。根据S盒的输入及输出关系,提出了◢n◣ bit S盒的非线性回路代数关系的通用求解算法。针对4 bit S盒设计了高效的非线性回路代数关系求解算法,并对国际公认的16类最优4 bit S盒及多个著名的轻量级密码算法中的S盒进行了测试分析。同时,还对上述轻量级密码算法中S盒所属等价类进行了检测。研究结果表明：16类S盒代表元中只有3类不存在二次回路代数关系;同属等价类S盒可能会有不同的二次回路代数关系;MANTIS、PRIDE、Marvin等轻量级算法的S盒存在多个二次回路代数关系。即这些包含低次回路代数关系的S盒存在潜在的安全缺陷。     

Energy-aware allocation for delay-sensitive multitask in mobile edge computing

With lower network latency and powerful hardware, mobile edge computing (MEC) is effective for computation-intensive and delay-sensitive tasks. The rising energy and low-latency demands of mobile applications for MEC pose challenges to task allocation. In this work, we consider computation offloading in MEC that is composed of a set of mobile devices, each with multiple tasks to offload to a nearby MEC server, with both single and multiple access points (APs). With multiple APs deployed, each mobile device can directly communicate with one or more APs, and their tasks can offload to different MEC servers that are within direct communication range. By considering binary computation offloading mode and limited subchannels, we formulate the multitask allocation problem as an integer programming problem, with the objective of minimizing the total energy consumption of all mobile devices while meeting deadline requirements. To solve this complicated problem, we propose efficient algorithms for single and multiple APs, and analyze related properties, including the approximation ratio and complexity. Experiments show that the algorithm can find high-quality solutions in a short time.

     

带运输考虑的多阶段动态可重入混合流水车间调度

可重入混合流水车间调度允许一个工件多次进入某些加工阶段,它广泛出现在许多工业制造过程中,如半导体制造、印刷电路板制造等.本文研究了带运输时间的多阶段动态可重入混合流水车间问题,目标是最小化总加权完成时间.针对该问题,建立了整数规划模型,进而基于工件解耦方式提出了两种改进的拉格朗日松弛(LR)算法.在这些算法中,设计了动态规划的改进策略以加速工件级子问题的求解,提出了异步次梯度法以得到有效的乘子更新方向.测试结果说明了所提出的两种改进算法在解的质量和运行时间方面均优于常规LR算法,两种算法都能在可接受的计算时间内得到较好的近优解.     

Studying the effect of population size in distributed evolutionary algorithms on heterogeneous clusters

Distributed Evolutionary Algorithms are traditionally executed on homogeneous dedicated clusters, despite most scientists have access mainly to networks of heterogeneous nodes (e.g., desktop PCs in a lab). Fitting this kind of algorithms to these environments, so that they can take advantage of their heterogeneity to save running time, is still an open problem. The different computational power of the nodes affects the performance of the algorithm, and tuning or fitting it to each node properly could reduce execution time.Since the distributed Evolutionary Algorithms include a whole range of parameters that influence the performance, this paper proposes a study on the population size. This parameter is one of the most important, since it has a direct relationship with the number of iterations needed to find the solution, as it affects the exploration factor of the algorithm. The aim of this paper consists in validating the following hypothesis: fitting the sub-population size to the computational power of the heterogeneous cluster node can lead to an improvement in running time with respect to the use of the same population size in every node.Two parameter size schemes have been tested, an offline and an online parameter setting, and three problems with different characteristics and computational demands have been used.Results show that setting the population size according to the computational power of each node in the heterogeneous cluster improves the time required to obtain the optimal solution. Meanwhile, the same set of different size values could not improve the running time to reach the optimum in a homogeneous cluster with respect to the same size in all nodes, indicating that the improvement is due to the interaction of the different hardware resources with the algorithm. In addition, a study on the influence of the different population sizes on each stage of the algorithm is presented. This opens a new research line on the fitting (offline or online) of parameters of the distributed Evolutionary Algorithms to the computational power of the devices.     

Single facility scheduling with nonlinear processing times

This paper considers the static single facility scheduling problem where the processing times of jobs are a monotonically increasing function of their starting (waiting) times and the objective is to minimize the total elapsed time (called the makespan) in which all jobs complete their processing. Based on the combinatorial analysis of the problem, an exact optimization algorithm is developed for the general processing time function which is then specialized for the linear case. In view of the excessive computational burden of the exact optimization algorithm for the nonlinear processing time functions, heuristic algorithms are proposed. The effectiveness of these proposed alogrithms is empirically evaluated and found to indicate that these heuristic algorithms yield optimal or near optimal schedules in many cases.     

Labeled Search Trees and Amortized Analysis: Improved Upper Bounds for NP-Hard Problems

A sequence of exact algorithms to solve the Vertex Cover and Maximum Independent Set problems have been proposed in the literature. All these algorithms appeal to a very conservative analysis that considers the size of the search tree, under a worst-case scenario, to derive an upper bound on the running time of the algorithm. In this paper we propose a different approach to analyze the size of the search tree. We use amortized analysis to show how simple algorithms, if analyzed properly, may perform much better than the upper bounds on their running time derived by considering only a worst-case scenario. This approach allows us to present a simple algorithm of running time O(1.194^kk² + n) for the parameterized Vertex Cover problem on degree-3 graphs, and a simple algorithm of running time O(1.1255ⁿ) for the Maximum Independent Set problem on degree-3 graphs. Both algorithms improve the previous best algorithms for the problems.     

A computationally efficient multi-domain active learning method for crop mapping using satellite image time-series

Crop mapping through classification of Satellite Image Time-Series (SITS) data can provide precious information for several agricultural applications, such as crop monitoring, yield forecasting, and crop inventory. However, several issues affect the classification performance of SITS data. As one of the most challenging problems, constituent images of time-series provide different levels of information about crops. These differences are the result of dynamic spectral responses of crops and also the variable atmospheric and sensor conditions. The second issue is the unavailability of adequate high-quality samples for training the classifier. In this study, we proposed a novel computationally efficient Multi-Domain Active Learning (MDAL) method which takes advantage of Multiple Kernel Learning (MKL) and Active Learning (AL) algorithms to address these two issues. The proposed method uses MKL algorithms to address the issues associated with different information level of the data, which generally cannot be modelled using the well-known classification algorithms. AL algorithms were also used for semi-automatic selection of training samples. However, most of the MKL algorithms are very computationally demanding. Consequently, using them in the MDAL method can dramatically increase the computational costs. Thus, in this paper, we presented the similarity-based MKL algorithms. Thanks to their low computational complexities, these algorithms are the most suitable MKL algorithms that can be used in the MDAL method. We evaluated the proposed method using two multispectral SITS datasets, acquired by RapidEye and SPOT sensors. The obtained results of the MDAL method for these datasets respectively showed 8.2% and 5.87% increase in the overall accuracy of classification as compared to the accuracy of the standard AL algorithm. The results also showed that in the case of adopting the SimpleMKL algorithm (a common MKL algorithm in the literature) the computational time of the MDAL method is 577 and 474 seconds for RapidEye and SPOT datasets, respectively. However, in the case of adopting the similarity-based MKL algorithms, these computational times respectively decreases to 4 and 2 seconds.     

基于GPU的密码S盒代数性质评估方法

密码S盒即黑盒,作为对称密码算法中的非线性部件,其代数性质往往决定着密码算法的安全性能。差分均匀度、非线性度及透明阶作为衡量密码S盒安全性质的三个基本指标,分别刻画了S盒抵御差分密码分析、线性密码分析及差分功耗攻击的能力。当密码S盒输入尺寸较大（如S盒输入长度大于15比特）时在中央处理器（CPU）中的求解所需时间仍过长,甚至求解不可行。如何针对大尺寸输入密码S盒的代数性质进行快速评估是目前业界的研究热点。基于图形处理器（GPU）提出一种快速评估密码S盒代数性质的方法。该方法利用切片技术将内核函数拆分至多线程,并结合求解差分均匀度、非线性度及透明阶的特征提出优化方案,从而实现并行计算。测试结果表明,与基于CPU的实现环境相比,基于单块GPU的环境下的实现效率得到了显著的提升。具体来说,计算差分均匀度、非线性度及透明阶所花时间分别节省了90.28%、78.57%、60%,验证了该方法的有效性。     

Scheduling image processing tasks in a multilayer system

Multilayer multiprocessor systems are generally employed in real-time applications such as robotics and computer vision. This paper introduces three heuristic algorithms for multiprocessor task scheduling in such systems. In our model, tasks with arbitrary processing times and arbitrary processor requirements are considered. The scheduling aims at minimising completion time of processes in a two-layer system. We employed an effective lower bound (LB) for the problem. Then, we analysed the average performance of the heuristic algorithms by computing the average percentage deviation of each heuristic solution from the LB on a set of randomly generated problems. We have also applied these algorithms for scheduling computer vision tasks running on prototype multilayer architecture. Our computational and empirical results showed that the proposed heuristic algorithms perform well.     

Analysis of FPTASes for the multi-objective shortest path problem

We propose a new FPTAS for the multi-objective shortest path problem with non-negative and integer arc costs. The algorithm uses elements from both an exact labeling algorithm and an FPTAS proposed by Tsaggouris and Zaroliagis [25]. We analyze the running times of these three algorithms both from a theoretical and a computational point of view. Theoretically, we show that there are instances for which the new FPTAS runs arbitrarily faster than the other two algorithms. Furthermore, for the bi-objective case, the number of approximate solutions generated by the proposed FPTAS is at most the number of Pareto-optimal points multiplied by the number of nodes. By performing a set of computational tests, we show that the new FPTAS performs best in terms of running time in case there are many dominated paths and the number of Pareto-optimal points is not too small.     

基于多重映射的安全S盒构造方法

将构造S盒的问题转化为寻找满足一定条件的映射的问题。利用 Tent映射的混沌特性,提出初始映射算法,并使用该算法得到可作为初始S盒的初始映射。为了提高S盒的安全性,提出了使用多个初始映射对初始S盒做非线性操作的多重映射算法,经安全性准则检验,该算法能够获得安全性更高的S盒。最后通过设定一个安全指标统计了该算法能够生成的优良S盒的个数,表明优良S盒的个数随着算法采用初始映射个数的增加而增加,并且实现算法所需的时间与算法中采用的初始映射的个数成正比。     

Combined new nonnegative matrix factorization algorithms with two-dimensional nonnegative matrix factorization for image processing

In recent years, nonnegative matrix factorization (NMF) has attracted significant amount of attentions in image processing, text mining, speech processing and related fields. Although NMF has been applied in several application successfully, its simple application on image processing has a few caveats. For example, NMF costs considerable computational resources when performing on large databases. In this paper, we propose two enhanced NMF algorithms for image processing to save the computational costs. One is modified rank-one residue iteration (MRRI) algorithm , the other is element-wisely residue iteration (ERI) algorithm. Here we combine CAPG (a NMF algorithm proposed by Lin), MRRI and ERI with two-dimensional nonnegative matrix factorization (2DNMF) for image processing. The main difference between NMF and 2DNMF is that the former first aligns images into one-dimensional (1D) vectors and then represents them with a set of 1D bases, while the latter regards images as 2D matrices and represents them with a set of 2D bases. The three combined algorithms are named CAPG-2DNMF, MRRI-2DNMF and ERI-2DNMF. The computational complexity and convergence analyses of proposed algorithms are also presented in this paper. Three public databases are used to test the three NMF algorithms and the three combinations, the results of which show the enhancement performance of our proposed algorithms (MRRI and ERI algorithms) over the CAPG algorithm. MRRI and ERI have similar performance. The three combined algorithms have better image reconstruction quality and less running time than their corresponding 1DNMF algorithms under the same compression ratio. We also do some experiments on a real-captured image database and get similar conclusions.     

超平面覆盖问题的参数化改进算法

超平面覆盖问题是计算几何领域中一类典型的NP难问题,在实际生活中有着广泛的应用.针对NP难问题的难解性,人们提出了一些传统的方法用来求解这些NP难问题.但由于这些方法具有各自的局限性,不能满足实际应用中的各种需求,人们从新的理论角度为固定参数可解的NP难问题设计参数算法.通过深入分析直线覆盖问题(超平面覆盖问题的一个特例)的结构特征,并利用深度有界搜索树的方法,提出了一个时间复杂度为O(k3(0.736k)k+nlogk)的确定性参数算法,极大地改进了当前最好的结果O((k/2.2)2k+nlogk).通过对上述算法在高维空间中的进一步扩展,提出了关于超平面覆盖问题时间复杂度为O(dkd+1(dk)!/((d!)kk!)+nd+1)确定性参数算法,对当前的最好结果O(kd(k+1)+nd+1)有较大改进.     

Algorithms for Pre-Compiling Programs by Parallel Compilers

The paper addresses the challenge of transmitting a big number of files stored in a data center (DC), encrypting them by compilers, and sending them through a network at an acceptable time. Face to the big number of files, only one compiler may not be sufficient to encrypt data in an acceptable time. In this paper, we consider the problem of several compilers and the objective is to find an algorithm that can give an efficient schedule for the given files to be compiled by the compilers. The main objective of the work is to minimize the gap in the total size of assigned files between compilers. This minimization ensures the fair distribution of files to different compilers. This problem is considered to be a very hard problem. This paper presents two research axes. The first axis is related to architecture. We propose a novel pre-compiler architecture in this context. The second axis is algorithmic development. We develop six algorithms to solve the problem, in this context. These algorithms are based on the dispatching rules method, decomposition method, and an iterative approach. These algorithms give approximate solutions for the studied problem. An experimental result is implemented to show the performance of algorithms. Several indicators are used to measure the performance of the proposed algorithms. In addition, five classes are proposed to test the algorithms with a total of 2350 instances. A comparison between the proposed algorithms is presented in different tables discussed to show the performance of each algorithm. The result showed that the best algorithm is the Iterative-mixed Smallest-Longest- Heuristic (ISL) with a percentage equal to 97.7% and an average running time equal to 0.148 s. All other algorithms did not exceed 22% as a percentage. The best algorithm excluding ISL is Iterative-mixed Longest-Smallest Heuristic (ILS) with a percentage equal to 21,4% and an average running time equal to 0.150 s.     

一种子群体个数动态变化的多目标优化协同进化算法

给出一种新型的在多目标优化条件下的进化算法群体停滞判别准则,并基于该准则提出一种合作型多目标优化协同进化算法．该算法在运行过程中自适应地决定子群体的新增和灭绝．使得子群体个数依据需要动态变化,减小了对计算资源的消耗,并解决了对复杂多目标优化问题难以事先进行分解的问题．对所提算法的计算复杂度进行了理论分析,并把它与已有的多目标进化算法进行了比较,结果表明所提算法具有较高的搜索性能．     

A learning approach to the bandwidth multicolouring problem

In this article, a generalisation of the vertex colouring problem known as bandwidth multicolouring problem (BMCP), in which a set of colours is assigned to each vertex such that the difference between the colours, assigned to each vertex and its neighbours, is by no means less than a predefined threshold, is considered. It is shown that the proposed method can be applied to solve the bandwidth colouring problem (BCP) as well. BMCP is known to be NP-hard in graph theory, and so a large number of approximation solutions, as well as exact algorithms, have been proposed to solve it. In this article, two learning automata-based approximation algorithms are proposed for estimating a near-optimal solution to the BMCP. We show, for the first proposed algorithm, that by choosing a proper learning rate, the algorithm finds the optimal solution with a probability close enough to unity. Moreover, we compute the worst-case time complexity of the first algorithm for finding a 1/(1–?) optimal solution to the given problem. The main advantage of this method is that a trade-off between the running time of algorithm and the colour set size (colouring optimality) can be made, by a proper choice of the learning rate also. Finally, it is shown that the running time of the proposed algorithm is independent of the graph size, and so it is a scalable algorithm for large graphs. The second proposed algorithm is compared with some well-known colouring algorithms and the results show the efficiency of the proposed algorithm in terms of the colour set size and running time of algorithm.     

几类高强度密码S盒的安全性新分析

针对几类高强度密码S盒是否存在新的安全性漏洞问题,提出了一种求解S盒非线性不变函数的算法。该算法主要基于密码S盒输入和输出的代数关系来设计。利用该算法对这几类密码S盒进行测试,发现其中几类存在相同的非线性不变函数;此外,如果将这些S盒使用于分组密码Midori-64的非线性部件上,将会得到一个新的变体算法。利用非线性不变攻击对其进行安全性分析,结果表明：该Midori-64变体算法存在严重的安全漏洞,即在非线性不变攻击下,存在2⁶⁴个弱密钥,并且攻击所需的数据、时间及存储复杂度可忽略不计,因此这几类高强度密码S盒存在新的安全缺陷。     

A charging-scheme decision model for electric vehicle battery swapping station using varied population evolutionary algorithms

This paper proposes a new battery swapping station (BSS) model to determine the optimized charging scheme for each incoming Electric Vehicle (EV) battery. The objective is to maximize the BSS’s battery stock level and minimize the average charging damage with the use of different types of chargers. An integrated objective function is defined for the multi-objective optimization problem. The genetic algorithm (GA), differential evolution (DE) algorithm and three versions of particle swarm optimization (PSO) algorithms have been implemented to solve the problem, and the results show that GA and DE perform better than the PSO algorithms, but the computational time of GA and DE are longer than using PSO. Hence, the varied population genetic algorithm (VPGA) and varied population differential evolution (VPDE) algorithm are proposed to determine the optimal solution and reduce the computational time of typical evolutionary algorithms. The simulation results show that the performances of the proposed algorithms are comparable with the typical GA and DE, but the computational times of the VPGA and VPDE are significantly shorter. A 24-h simulation study is carried out to examine the feasibility of the model.     

利用坐标下降实现并行稀疏子空间聚类

随着数据规模的不断扩大,稀疏子空间聚类问题面临计算上的巨大挑战。现有稀疏子空间聚类算法如交替方向乘子法(ADMM)往往基于串行实现,难以利用多核处理器提高处理大规模聚类问题的效率。针对这个问题,提出一种基于坐标下降的并行稀疏子空间聚类方法。该方法利用稀疏子空间聚类可以建模为求解一系列的样本自稀疏表达子问题的特点,使用坐标下降方法来求解每个子问题,具有参数少、收敛快的优点;同时结合自稀疏表达子问题独立的特点,在处理器的各个核心上同时求解不同样本对应的子问题,因此可以充分利用计算机资源,减少运行时间开销。在模拟数据和运动分割数据集Hopkins-155上与常用的ADMM算法进行对比实验,结果表明该算法在多核处理器上可以显著提升运行速度且聚类精度与ADMM相当。