Linearization of nonlinear filter generators and its application to cryptanalysis of stream ciphers

Nonlinear filter generators are commonly used as keystream generators in stream ciphers. A nonlinear filter generator utilizes a nonlinear filtering function to combine the outputs of a linear feedback shift register (LFSR) to improve the linear complexity of keystream sequences. However, the LFSR-based stream ciphers are still potentially vulnerable to algebraic attacks that recover the key from some keystream bits. Although the known algebraic attacks only require polynomial time complexity of computations, all have their own constraints. This paper uses the linearization of nonlinear filter generators to cryptanalyze LFSR-based stream ciphers. Such a method works for any nonlinear filter generators. Viewing a nonlinear filter generator as a Boolean network that evolves as an automaton through Boolean functions, we first give its linearization representation. Compared to the linearization representation in Limniotis et al. (2008), this representation requires lower spatial complexity of computations in most cases. Based on the representation, the key recoverability is analyzed via the observability of Boolean networks. An algorithm for key recovery is given as well. Compared to the exhaustive search to recover the key, using this linearization representation requires lower time complexity of computations, though it leads to exponential time complexity.     

H-contact unit tangent sphere bundles of Riemannian manifolds

A contact metric manifold is said to be H-contact, if its characteristic vector field is harmonic. We prove that the unit tangent bundle of a Riemannian manifold M equipped with the standard contact metric structure is H-contact if and only if M is 2-stein.     

Allostatic load as a complex clinical construct: A case‐based computational modeling approach

Allostatic load (AL) is a complex clinical construct, providing a unique window into the cumulative impact of stress. However, due to its inherent complexity, AL presents two major measurement challenges to conventional statistical modeling (the field's dominant methodology): it is comprised of a complex causal network of bioallostatic systems, represented by an even larger set of dynamic biomarkers; and, it is situated within a web of antecedent socioecological systems, linking AL to differences in health outcomes and disparities. To address these challenges, we employed case‐based computational modeling (CBM), which allowed us to make four advances: (1) we developed a multisystem, 7‐factor (20 biomarker) model of AL's network of allostatic systems; (2) used it to create a catalog of nine different clinical AL profiles (causal pathways); (3) linked each clinical profile to a typology of 23 health outcomes; and (4) explored our results (post hoc) as a function of gender, a key socioecological factor. In terms of highlights, (a) the Healthy clinical profile had few health risks; (b) the pro‐inflammatory profile linked to high blood pressure and diabetes; (c) Low Stress Hormones linked to heart disease, TIA/Stroke, diabetes, and circulation problems; and (d) high stress hormones linked to heart disease and high blood pressure. Post hoc analyses also found that males were overrepresented on the High Blood Pressure (61.2%), Metabolic Syndrome (63.2%), High Stress Hormones (66.4%), and High Blood Sugar (57.1%); while females were overrepresented on the Healthy (81.9%), Low Stress Hormones (66.3%), and Low Stress Antagonists (stress buffers) (95.4%) profiles. © 2015 Wiley Periodicals, Inc. Complexity 21: 291–306, 2016     

On the Linear Complexity Profile of Nonlinear Congruential Pseudorandom Number Generators with Dickson Polynomials

Linear complexity and linear complexity profile are important characteristics of a sequence for applications in cryptography and Monte-Carlo methods. The nonlinear congruential method is an attractive alternative to the classical linear congruential method for pseudorandom number generation. Recently, a weak lower bound on the linear complexity profile of a general nonlinear congruential pseudorandom number generator was proven by Gutierrez, Shparlinski and the first author. For most nonlinear generators a much stronger lower bound is expected. Here, we obtain a much stronger lower bound on the linear complexity profile of nonlinear congruential pseudorandom number generators with Dickson polynomials.     

有预算限制的最大多种物资流问题

研究有预算限制的最大多种物资流问题,给出了这个问题的不依赖物资数k的全多项式时间近似算法,其算法复杂性是O~(-ε2m2).同时,利用有预算限制的最大多种物资流问题的研究结果,我们也得到了费用最小的最大多种物资流问题的近似算法和算法复杂性.     

Dirichlet外问题与漂移布朗运动

利用Dirichlet外问题与漂移布朗运动之间存在的密切联系,对Dirichlet外问题提出了一种新的有效的概率数值方法,这种方法运用了解的随机表达式、布朗运动、漂移布朗运动以及球面首中位置和时间的分布等．     

146号初等元胞自动机的演化语言的复杂性

Symbolic dynamics of cellular automata is introduced by coarse-graining the temporal evolution orbits. Evolution languages are defined. By using the theory of formal languages and automata, the complexity of evolution languages of the elementary cellular automaton of rule 146 is studied and it is proved that its width 1-evolution language is regular, but for every n ≥ 2 its width n-evolution language is not context-free but context-sensitive. Also, the same results hold for the equivalent （under conjugation） elementary cellular automaton of rule 182.     

Reducing structural changes in van Emde Boas' data structure to the lower bound for the dynamic predecessor problem

We consider the problem of maintaining a dynamic ordered set of n integers in a universe U under the operations of insertion, deletion and predecessor queries. The computation model used is a unit-cost RAM, with a word length of w bits, and the universe size is |U|=2^w. We present a data structure that uses O(|U|/log|U|+n) space, performs all the operations in O(loglog|U|) time and needs O(loglog|U|/logloglog|U|) structural changes per update operation. The data structure is a simplified version of the van Emde Boas' tree introducing, in its construction and functioning, new concepts, which help to keep the important information for searching along the path of the tree, in a more compact and organized way.     

The property of being polynomial for Mal’tsev constraint satisfaction problems

A combinatorial constraint satisfaction problem aims at expressing in unified terms a wide spectrum of problems in various branches of mathematics, computer science, and AI. The generalized satisfiability problem is NP-complete, but many of its restricted versions can be solved in a polynomial time. It is known that the computational complexity of a restricted constraint satisfaction problem depends only on a set of polymorphisms of relations which are admitted to be used in the problem. For the case where a set of such relations is invariant under some Mal’tsev operation, we show that the corresponding constraint satisfaction problem can be solved in a polynomial time. __________ Translated from Algebra i Logika, Vol. 45, No. 6, pp. 655–686, November–December, 2006.