Improved distinguishers for HC-128

HC-128 is an eSTREAM final portfolio stream cipher. Several authors have investigated its security and, in particular, distinguishing attacks have been considered. Still, no one has been able to provide a distinguisher stronger than the one presented by Wu in the original HC-128 paper. In this paper we first argue that the keystream requirement in Wu’s original attack is underestimated by a factor of almost 2⁸. Our revised analysis shows that the keystream complexity of Wu’s original attack is 2^160.471 32-bit keystream blocks. We then go on to investigate two new types of distinguishers on HC-128. One of them, a distinguisher counting the number of zeros in created blocks of bits, gives a biased distribution that requires 2^143.537 such constructed block samples (2^152.537 32-bit keystream blocks). For fairness, the same metric is used to compare our attack to Wu’s, and our improvement is significant compared to Wu’s original result. Furthermore, the vector-based methodology used is general and can be applied to any cryptographic primitive that reveals a suitable probability distribution.     

A Random-number Generator for Microcomputers

A very efficient and statistically sound random-number generator of the prime modulus multiplicative congruential method is devised for 16-bit microcomputers (8-bit machines have to be double-precisioned). This generator combines several generators, and cycles every (2¹⁵-20)² numbers with 2¹⁵-20 different numbers in one cycle. When precision is relatively unimportant, this generator is demonstrated to be a good random-number generator.     

Boundary Homogenization of an Inverse Non-local Elliptic Boundary-Value Problem

In this paper, a mathematical analysis is given of an inversenon–local elliptic boundary–value problem for conductivityprospecting with a patched–electrode well-log instrument.As the electrode cells of the patched electrode system becomesmaller and smaller, the microscopic structure of the electrodesystem becomes increasingly complicated and themathematicalanalysis becomes much more difficult. Nevertheless, it is shownthat the electrode system can be homogenized macroscopically;that is, the solution of the inverse problem for the patchedelectrode system converges to the solution of the correspondinginverse problem for the original electrode system.     

The method of lines for parabolic differential-functional equations

Parabolic differential–functional equations with initial-boundaryconditions of Dirichlet type are studied. Spatial derivativesoccurring in the original problem are replaced by suitable differencesand the problem is transformed into an initial-boundary valueproblem for a system of ordinary differential–functionalequations. The Pen-on-type estimation for the right-hand sideof the original equation with respect to the functional argumentis assumed. The convergence of the numerical method of linesis proved. The differential inequalities technique is applied.     

On the hill stability of motion in the three-body problem

We consider the special case of the three-body problem where the mass of one of the bodies is considerably smaller than the masses of the other two bodies and investigate the relationship between the Lagrange stability of a pair of massive bodies and the Hill stability of the system of three bodies. We prove a theorem on the existence of Hill stable motions in the case considered. We draw an analogy with the restricted three-body problem. The theorem obtained allows one to conclude that there exist Hill stable motions for the elliptic restricted three-body problem. Translated from Ukrains’kyi Matematychnyi Zhurnal, Vol. 60, No. 10, pp. 1434–1440, October, 2008.     

Evolutionary methods for unsupervised feature selection using Sammon’s stress function

In this paper, four methods are proposed for feature selection in an unsupervised manner by using genetic algorithms. The proposed methods do not use the class label information but select a set of features using a task independent criterion that can preserve the geometric structure (topology) of the original data in the reduced feature space. One of the components of the fitness function is Sammon’s stress function which tries to preserve the topology of the high dimensional data when reduced into the lower dimensional one. In this context, in addition to using a fitness criterion, we also explore the utility of unfitness criterion to select chromosomes for genetic operations. This ensures higher diversity in the population and helps unfit chromosomes to become more fit. We use four different ways for evaluation of the quality of the features selected: Sammon error, correlation between the inter-point distances in the two spaces, a measure of preservation of cluster structure found in the original and reduced spaces and a classifier performance. The proposed methods are tested on six real data sets with dimensionality varying between 9 and 60. The selected features are found to be excellent in terms of preservation topology (inter-point geometry), cluster structure and classifier performance. We do not compare our methods with other methods because, unlike other methods, using four different ways we check the quality of the selected features by finding how well the selected features preserve the “structure” of the original data.     

Orbits and Lattices for Linear Random Number Generators with Composite Moduli

In order to analyze certain types of combinations of multiple recursive linear congruential generators (MRGs), we introduce a generalized spectral test. We show how to apply the test in large dimensions by a recursive procedure based on the fact that such combinations are subgenerators of other MRGs with composite moduli. We illustrate this with the well-known RANMAR generator. We also design an algorithm generalizing the procedure to arbitrary random number generators.

     

A Variational Principle with Applications in Finite Elements

One of the difficulties which arise when finite element methodsare applied to the solution of fourth order differential equationsvia the Rayleigh–Ritz method is that compatible basisfunctions are required to have continuous derivatives acrossthe interelement boundaries. In this paper a method is proposedwhich requires only continuity of the basis functions acrossthe inter-element boundaries. A perturbed variational problem containing a parameter is proposed.The solution of the original problem is the leading term inan asymptotic expansion, in powers of ^–1, for the solutionof the perturbed problem. When is taken large enough, an approximationto the solution of the perturbed problem is therefore an approximationto the solution of the original problem. As numerical examples the problems of a clamped elastic plateunder a central point load and under a uniform load are examined.     

Scheduling orders on either dedicated or flexible machines in parallel to minimize total weighted completion time

We are interested in the problem of scheduling orders for different product types in a facility with a number of machines in parallel. Each order asks for certain amounts of various different product types which can be produced concurrently. Each product type can be produced on a subset of the machines. Two extreme cases of machine environments are of interest. In the first case, each product type can be produced on one and only one machine which is dedicated to that product type. In the second case, all machines are identical and flexible; each product type can be produced by any one of the machines. Moreover, when a machine in this case switches over from one product type to another, no setup is required. Each order has a release date and a weight. Preemptions are not allowed. The objective is minimizing the total weighted completion time of the orders. Even when all orders are available at time 0, both types of machine environments have been shown to be NP-hard for any fixed number (≥2) of machines. This paper focuses on the design and analysis of approximation algorithms for these two machine environments. We also present empirical comparisons of the various algorithms. The conclusions from the empirical analyses provide insights into the trade-offs with regard to solution quality, speed, and memory space. Electronic Supplementary Material The online version of this article () contains supplementary material, which is available to authorized users. This research is supported by the National Science Foundation through grants DMI-0300156 and DMI-0245603.     

Scheduling fixtures for New Zealand Cricket

^** Email: m.wright{at}lancaster.ac.uk This paper describes the problem faced every year by New ZealandCricket in scheduling the principal inter-regional fixtures.This is a combinatorial optimization problem with few constraintsbut many objectives, which are described in detail. A techniqueknown as Subcost-Guided Simulated Annealing is used to solvethis problem, producing one or more schedules of high quality.One particular feature of the problem requires great care—thedetermination of adequate neighbourhoods for such a tightlyconstrained problem, where most simple changes lead to infeasibility.The approach adopted is to use a complex and unorthodox definitionof a perturbation, each one leading to several possible neighbouringsolutions which are generated by means of a tree search procedure.The system will be used in practice for the 2003–2004cricket season and beyond.     

Instabilities of a flexible surface in supersonic flow

The stability of a supersonic boundary layer above a flexiblesurface is considered in the limit of large Reynolds numberand for Mach numbers O(1). Asymptotic theory of viscous–inviscidinteraction has been used for this purpose. We found that fora simple elastic surface, for which deflections are proportionalto local pressure differences, the boundary-layer flow remainsstable as it is for a rigid wall. However, when either dampingor surface inertia is included the flow becomes unstable. Moreover,in a certain range of wave numbers the boundary layer developsmore then one unstable mode. It is interesting that these modesare connected to one another via saddle points in the complex-frequencyplane. A more complex Kramer-type surface is also analysed andin some parameter ranges is found to permit the evolution ofunstable Tollmien–Schlichting waves. The neutral curvesare found for a variety of situations related to the parametersassociated with the flexible surface.     

On the asymptotic distribution of the likelihood ratio under the regularity conditions due to doob

Summary The concepts of the asymptotic maximum likelihood estimates—AMLEs in short—and their asymptotic identity are introduced in section 1. They seem to be more adequate than the usual one for uses in the large sample theory. The AMLE is a slightly weakened version of the usual maximum likelihood estimate and therefore it should have a bit wider applicability than the original one. The asymptotic normality of a consistent AMLE and Wilks’ theorem concerning the asymptotic distribution of the statistic —2 log λ, where λ is the likelihood ratio, can be obtained under the regularity conditions due to Doob in section 2. A set of conditions which assure the existence of a unique and consistent AMLE is presented in section 3 and in the final section 4 the proof of the existence of the unique and consistent AMLE under those conditions is given. This work has been motivated by the work of Ogawa, Moustafa and Roy [3].     

Scheduling orders for multiple product types to minimize total weighted completion time

We consider the problem of scheduling orders for multiple different product types in an environment with m dedicated machines in parallel. The objective is to minimize the total weighted completion time. Each product type is produced by one and only one of the m dedicated machines; that is, each machine is dedicated to a specific product type. Each order has a weight and may also have a release date. Each order asks for certain amounts of various different product types. The different products for an order can be produced concurrently. Preemptions are not allowed. Even when all orders are available at time 0, the problem has been shown to be strongly NP-hard for any fixed number (?2) of machines. This paper focuses on the design and analysis of efficient heuristics for the case without release dates. Occasionally, however, we extend our results to the case with release dates. The heuristics considered include some that have already been proposed in the literature as well as several new ones. They include various static and dynamic priority rules as well as two more sophisticated LP-based algorithms. We analyze the performance bounds of the priority rules and of the algorithms and present also an in-depth comparative analysis of the various rules and algorithms. The conclusions from this empirical analysis provide insights into the trade-offs with regard to solution quality, speed, and memory space.     

Scheduling interfering job sets on parallel machines

We consider bicriteria scheduling on identical parallel machines in a nontraditional context: jobs belong to two disjoint sets, and each set has a different criterion to be minimized. The jobs are all available at time zero and have to be scheduled (non-preemptively) on m parallel machines. The goal is to generate the set of all non-dominated solutions, so the decision maker can evaluate the tradeoffs and choose the schedule to be implemented. We consider the case where, for one of the two sets, the criterion to be minimized is makespan while for the other the total completion time needs to be minimized. Given that the problem is NP-hard, we propose an iterative SPT–LPT–SPT heuristic and a bicriteria genetic algorithm for the problem. Both approaches are designed to exploit the problem structure and generate a set of non-dominated solutions. In the genetic algorithm we use a special encoding scheme and also a unique strategy – based on the properties of a non-dominated solution – to ensure that all parts of the non-dominated front are explored. The heuristic and the genetic algorithm are compared with a time-indexed integer programming formulation for small and large instances. Results indicate that the both the heuristic and the genetic algorithm provide high solution quality and are computationally efficient. The heuristics proposed also have the potential to be generalized for the problem of interfering job sets involving other bicriteria pairs.     

A modification of a solution concept of the linear programming problem with interval coefficients in the constraints

We propose a modification of a concept of solving a linear programming problem with interval coefficients in the constraints. The original concept imposes the decision maker a way comparing intervals, our modification—which is an interactive approach, comprising the original one as its special case—gives him more freedom in the choice of the preference relation. Thanks to this flexibility he may be able to find a solution which better suits his needs and attitude towards risk. What is more, our modification corrects a serious drawback of the original method.     

Efficient hybrid encryption from ID-based encryption

This paper deals with generic transformations from ID-based key encapsulation mechanisms (IBKEM) to hybrid public-key encryption (PKE). The best generic transformation known until now is by Boneh and Katz and requires roughly 704-bit overhead in the ciphertext. We present new generic transformations that are applicable to partitioned IBKEMs. A partitioned IBKEM is an IBKEM that provides some extra structure. Such IBKEMs are quite natural and in fact nearly all known IBKEMs have this additional property. Our first transformation yields chosen-ciphertext secure PKE schemes from selective-ID secure partitioned IBKEMs with a 256-bit overhead in ciphertext size plus one extra exponentiation in encryption/decryption. As the central tool a Chameleon Hash function is used to map the identities. We also propose other methods to remove the use of Chameleon Hash, which may be of independent technical interest. Applying our transformations to existing IBKEMs we propose a number of novel PKE schemes with different trade-offs. In some concrete instantiations the Chameleon Hash can be made “implicit” which results in improved efficiency by eliminating the additional exponentiation. Since our transformations preserve the public verifiability property of the IBE schemes it is possible to extend our results to build threshold hybrid PKE schemes. We show an analogue generic transformation in the threshold setting and present a concrete scheme which results in the most efficient threshold PKE scheme in the standard model.     

Reduction of hugoniot-maslov chains for trajectories of solitary vortices of the “shallow water” equations to the hill equation

According to Maslov’s idea, many two-dimensional, quasilinear hyperbolic systems of partial differential equations admit only three types of singularities that are in general position and have the property of “structure self-similarity and stability.” Those are: shock waves, “narrow” solitons, and “square-root” point singularities (solitary vortices). Their propagation is described by an infinite chain of ordinary differential equations (ODE) that generalize the well-known Hugoniot conditions for shock waves. After some reasonable closure of the chain for the case of solitary vortices in the “shallow water” equations, we obtain a nonlinear system of sixteen ODE, which is exactly equivalent to the (linear) Hill equation with a periodic potential. This means that, in some approximations, the trajectory of a solitary vortex can be described by the Hill equation. This result can be used to predict the trajectory of the vortex center if we know its observable part. Translated from Teoreticheskaya i Matematicheskaya Fizika, Vol. 112, No. 1, pp. 47–66.     

Distribution Properties of Multiply-with-Carry Random Number Generators

We study the multiply-with-carry family of generators proposed by Marsaglia as a generalization of previous add-with-carry families. We define for them an infinite state space and focus our attention on the (finite) subset of recurrent states. This subset will, in turn, split into possibly several subgenerators. We discuss the uniformity of the -dimensional distribution of the output of these subgenerators over their full period. In order to improve this uniformity for higher dimensions, we propose a method for finding good parameters in terms of the spectral test. Our results are stated in a general context and are applied to a related complementary multiply-with-carry family of generators.

     

Some remarks on Reid on primary and secondary qualities

John Locke’s distinction between primary and secondary qualities of objects has meet resistance. In this paper I bypass the traditional critiques of the distinction and instead concentrate on two specific counterexamples to the distinction: Killer yellow and the puzzle of multiple dispositions. One can accommodate these puzzles, I argue, by adopting Thomas Reid’s version of the primary/secondary quality distinction, where the distinction is founded upon conceptual grounds. The primary/secondary quality distinction is epistemic rather than metaphysical. A consequence of Reid’s primary/ secondary quality distinction is that one must deny the original version of Molyneux’s question, while one must affirm an amended version of it. I show that these two answers to Molyneux’s question are not at odds with current empirical research.