The Advanced Encryption Standard (AES) is one of the most studied symmetric encryption schemes. During the last years, several attacks have been discovered in different adversarial models. In this paper, we focus on r...
详细信息
The Advanced Encryption Standard (AES) is one of the most studied symmetric encryption schemes. During the last years, several attacks have been discovered in different adversarial models. In this paper, we focus on related-key differential attacks, where the adversary may introduce differences in plaintext pairs and also in keys. We show that Constraint Programming (CP) can be used to model these attacks, and that it allows us to efficiently find all optimal related-key differential characteristics for AES-128, AES-192 and AES-256. In particular, we improve the best related-key differential for the whole AES-256 and give the best related-key differential on 10 rounds of AES-192, which is the differential trail with the longest path. Those results allow us to improve existing related-key distinguishers, basic related-key attacks and q-multicollisions on AES-256. (C) 2018 Elsevier B.V. All rights reserved.
The paper addresses a problem of finding critical paths in PERT networks (digraphs) with variable are lengths depending on a parameter. By equipping the Bellman-Ford label-correcting algorithm with variable vectorial ...
详细信息
The paper addresses a problem of finding critical paths in PERT networks (digraphs) with variable are lengths depending on a parameter. By equipping the Bellman-Ford label-correcting algorithm with variable vectorial labels depending on the parameter, we derive its version that solves the problem in O(mn(2)) time, for all possible parameter values (where nz stands for the number of arcs, and n is the number of nodes in the digraph). An application related to cyclic scheduling of tasks in a robotic cell is considered. (C) 1998 Elsevier Science B.V. All rights reserved.
We present a new sorting algorithm, called Splitsort, which adapts to existing order within the input sequence. The algorithm is optimal with respect to several known measures of presortedness, including the number of...
详细信息
We present a new sorting algorithm, called Splitsort, which adapts to existing order within the input sequence. The algorithm is optimal with respect to several known measures of presortedness, including the number of inversions, for which no such simple and space efficient algorithm was known before. The amount of extra space needed is only n pointers. Splitsort uses a simple data structure and is easy to code. In the worst case Splitsort performs 2.5nlog2n comparisons, but if the input is presorted according to some of the measures it completes the sorting task considerably faster. We also show how a variant of the algorithm can be implemented to run in-place.
Given nodes s and t, the quickest path problem is to find a path p from s to t, such that the total transmission time in the communication network for sigma units of data, with sigma greater than or equal to zero, fro...
详细信息
Given nodes s and t, the quickest path problem is to find a path p from s to t, such that the total transmission time in the communication network for sigma units of data, with sigma greater than or equal to zero, from s to t is minimum among all possible paths from s to t in the network. An algorithm was developed for the single pair quickest path problem with a certain time complexity as a function of sigma. An extension of this algorithm solves the single source i.e. one to all quickest path problem. The all-pairs quickest path problem for a particular sigma can be solved with a certain time complexity by applying the single source quickest path algorithm several times. The all-pairs quickest path problem is discussed as a function of sigma. The network is preprocessed in such a way that given any pair of nodes, the quickest path is found to transmit data between the nodes for sigma greater than or equal to zero. The time complexity and data structure are discussed.
We present a comprehensive review on probabilistic arithmetic automata (PAAs), a general model to describe chains of operations whose operands depend on chance, along with two algorithms to numerically compute the dis...
详细信息
We present a comprehensive review on probabilistic arithmetic automata (PAAs), a general model to describe chains of operations whose operands depend on chance, along with two algorithms to numerically compute the distribution of the results of such probabilistic calculations. PAAs provide a unifying framework to approach many problems arising in computational biology and elsewhere. We present five different applications, namely 1) pattern matching statistics on random texts, including the computation of the distribution of occurrence counts, waiting times, and clump sizes under hidden Markov background models;2) exact analysis of window-based pattern matching algorithms;3) sensitivity of filtration seeds used to detect candidate sequence alignments;4) length and mass statistics of peptide fragments resulting from enzymatic cleavage reactions;and 5) read length statistics of 454 and IonTorrent sequencing reads. The diversity of these applications indicates the flexibility and unifying character of the presented framework. While the construction of a PAA depends on the particular application, we single out a frequently applicable construction method: We introduce deterministic arithmetic automata (DAAs) to model deterministic calculations on sequences, and demonstrate how to construct a PAA from a given DAA and a finite-memory random text model. This procedure is used for all five discussed applications and greatly simplifies the construction of PAAs. Implementations are available as part of the MoSDi package. Its application programming interface facilitates the rapid development of new applications based on the PAA framework.
Local search with k-change neighborhoods is perhaps the oldest and most widely used heuristic method for the traveling salesman problem, yet almost no theoretical performance guarantees for it were previously known. T...
详细信息
Local search with k-change neighborhoods is perhaps the oldest and most widely used heuristic method for the traveling salesman problem, yet almost no theoretical performance guarantees for it were previously known. This paper develops several results, some worst-case and some probabilistic, on the performance of 2- and k-opt local search for the traveling salesman problem, with respect to both the quality of the solution and the speed with which it is obtained.
We present a THETA(n2) worst-case-time algorithm to determine the minimum finishing time for a preemptive schedule of n independent jobs on a hypercube of fixed dimension.
We present a THETA(n2) worst-case-time algorithm to determine the minimum finishing time for a preemptive schedule of n independent jobs on a hypercube of fixed dimension.
This paper investigates semi-online scheduling on two uniform machines with the known largest size. Denote by s (j) the speed of each machine, j=1,2. Assume 0 < s (1)a parts per thousand currency signs (2), and let...
详细信息
This paper investigates semi-online scheduling on two uniform machines with the known largest size. Denote by s (j) the speed of each machine, j=1,2. Assume 0 < s (1)a parts per thousand currency signs (2), and let s=s (2)/s (1) be the speed ratio.
We improve the famous divide-and-conquer algorithm by Bentley and Shamos for the planar closest-pair problem. For n points on the plane, our algorithm keeps the optimal O（n log n） time complexity and, using a circle...
详细信息
We improve the famous divide-and-conquer algorithm by Bentley and Shamos for the planar closest-pair problem. For n points on the plane, our algorithm keeps the optimal O（n log n） time complexity and, using a circle-packing property, computes at most 7n/2 Euclidean distances, which improves Ge et al.＇s bound of （3n log n）/2 Euclidean distances. We present experimental results of our comparative studies on four different versions of the divide-and-conquer closest pair algorithm and propose two effective heuristics.
Speranza and Tuza [Ann. Oper. Res. 86 (1999) 494-506] studied the on-line problem of scheduling jobs on m identical machines with extendable working time. In this problem, each machine is assumed to have an identical ...
详细信息
Speranza and Tuza [Ann. Oper. Res. 86 (1999) 494-506] studied the on-line problem of scheduling jobs on m identical machines with extendable working time. In this problem, each machine is assumed to have an identical regular working time, which can be extended if necessary. The working time of a machine is the larger one between its regular working time and the total processing time of jobs assigned to it. The objective is to minimize the total working time of machines. They presented an on-line algorithm H, with a competitive ratio at most 1.228 for any number of machines by choosing an appropriate parameter x. In this paper we consider a small number of machines. The best choices of x are given for m = 2, 3, 4 and the tight bounds, 7/6, 11/9 and 19/16, respectively, are proved. Among them, the algorithm for m = 2 is best possible. We then derive a new algorithm for m = 3 with a competitive ratio 7/6. (C) 2002 Elsevier Science B.V. All rights reserved.
暂无评论