On the bit oriented trellis structure of run length limited codes on discrete local data dependent channels

We investigate bit oriented decoder trellises for binary constrained codes. In particular, we are interested in destined trellises, where each state determines the last bits leading into the state and the first bits coming out of the state. A destined trellis can be constructed from a conventional trellis by state splitting. However, we demonstrate that integrating the design of destined encoders into the conventional encoder design process for constrained codes yields simpler trellises. We also prove lower bounds on the number of states in such trellises.     

苏北盆地海安凹陷钻头优选技术

苏北盆地海安凹陷钻井存在钻头选型复杂,单井钻头数量使用过多,钻井周期长,钻井效率低等问题,迫切需要解决钻头优选问题.用模糊优化理论对常用钻头选型的效益指数法进行了改造完善,建立了新的钻头优选模型,对海安已钻27口井的钻头进行了优选,确定了实钻效果最佳的钻头.运用优选的钻头在现场进行钻井作业,取得优良的效果,极大提高了钻井效率,缩短了钻井周期,同时也极大简化了钻头选型.探索了一条有效解决苏北盆地海安凹陷及相邻区块钻头优选的技术路径,为高效勘探开发苏北盆地提供了有力的技术支撑.     

Algebraic attacks on a class of stream ciphers with unknown output function

Attacks on linear feedback shift register (LFSR) based cryptosystems typically assume that all the system details except the initial state of the LFSR are known. We address the problem assuming that the nonlinear output function is also unknown and frame the problem as one of a multivariate interpolation. The solution to this problem yields a system that produces an output identical to that of the original system with some other initial state. The attack needs to observe M bits of data and has complexity O(M ^ω) where ${M = \sum_{i=0}^{d} C(n, i)}$ is the number of monomials of degree at most d in n variables, n being the state size and d the degree of the output function. When the output function has annihilators of degree e < d then with O(D) bits of data one can reconstruct parts of the keystream where ${D = \sum_{i=0}^{e} C(n, i)}$ .     

A mathematical theory of strong emergence using multiscale variety

We argue conceptually and then demonstrate mathematically that it is possible to define a scientifically meaningful notion of strong emergence. A strong emergent property is a property of the system that cannot be found in the properties of the system's parts or in the interactions between the parts. The possibility of strong emergence follows from an ensemble perspective, which states that physical systems are only meaningful as ensembles rather than individual states. Emergent properties reside in the properties of the ensemble rather than of any individual state. A simple example is the case of a string of bits including a parity bit, i.e. the bits are constrained to have, e.g., an odd number of ON bits. This constraint is a property of the entire system that cannot be identified through any set of observations of the state of any or all subsystems of the system. It is a property that can only be found in observations of the state of the system as a whole. A collective constraint is a property of the system, however, the constraint is caused when the environment interacts with the system to select the allowable states. Although selection in this context does not necessarily correspond to biological evolution, it does suggest that evolutionary processes may lead to such emergent properties. A mathematical characterization of multiscale variety captures the implications of strong emergent properties on all subsystems of the system. Strong emergent properties result in oscillations of multiscale variety with negative values, a distinctive property. Examples of relevant applications in the case of social systems include various allocation, optimization, and functional requirements on the behavior of a system. Strongly emergent properties imply a global to local causality that is conceptually disturbing (but allowed!) in the context of conventional science, and is important to how we think about biological and social systems. © 2004 Wiley Periodicals, Inc. Complexity 9: 15–24, 2004     

Construction of sequences of zeros and ones with complex finite sequences

We construct infinite sequences of zeros and ones under some restrictions (not to contain subwords of some definite type or definite bits at definite positions, etc.). This paper concerns probabilistic methods of constructing such sequences with application of the Lovász lemma and their reformulation in terms of the Kolmogorov complexity and Martin-Löf randomness.     

On ε‐biased generators in NC0

Cryan and Miltersen (Proceedings of the 26th Mathematical Foundations of Computer Science, 2001, pp. 272–284) recently considered the question of whether there can be a pseudorandom generator in NC⁰, that is, a pseudorandom generator that maps n‐bit strings to m‐bit strings such that every bit of the output depends on a constant number k of bits of the seed. They show that for k = 3, if m ≥ 4n + 1, there is a distinguisher; in fact, they show that in this case it is possible to break the generator with a linear test, that is, there is a subset of bits of the output whose XOR has a noticeable bias. They leave the question open for k ≥ 4. In fact, they ask whether every NC⁰ generator can be broken by a statistical test that simply XORs some bits of the input. Equivalently, is it the case that no NC⁰ generator can sample an ε‐biased space with negligible ε? We give a generator for k = 5 that maps n bits into cn bits, so that every bit of the output depends on 5 bits of the seed, and the XOR of every subset of the bits of the output has bias 2. For large values of k, we construct generators that map n bits to bits such that every XOR of outputs has bias . We also present a polynomial‐time distinguisher for k = 4,m ≥ 24n having constant distinguishing probability. For large values of k we show that a linear distinguisher with a constant distinguishing probability exists once m ≥ Ω(2^kn^?k/2?). Finally, we consider a variant of the problem where each of the output bits is a degree k polynomial in the inputs. We show there exists a degree k = 2 pseudorandom generator for which the XOR of every subset of the outputs has bias 2^?Ω(n) and which maps n bits to Ω(n²) bits. © 2005 Wiley Periodicals, Inc. Random Struct. Alg., 2006     

移位交换网的最优路由算法

移位交换网是重要的互联网络之一 ,在并行计算中有着广泛应用 .然而 ,它缺少任意点对间的最短路由算法 .已有的路由算法都不能保证其任意节点对间都是最短路由 .文中给出了一个最短路由算法 ,也是最优路由算法 ,它使得从源节点到目的节点的任何信息都是沿最短路由传输 .同时 ,我们还得到了任意节点对间的距离公式     

Upper bounds on the complexity of algebraic cryptanalysis of ciphers with a low multiplicative complexity

Lightweight cipher designs try to minimize the implementation complexity of the cipher while maintaining some specified security level. Using only a small number of AND gates lowers the implementation costs, and enables easier protections against side-channel attacks. In our paper we study the connection between the number of AND gates (multiplicative complexity) and the complexity of algebraic attacks. We model the encryption with multiple right-hand sides (MRHS) equations. The resulting equation system is transformed into a syndrome decoding problem. The complexity of the decoding problem depends on the number of AND gates, and on the relative number of known output bits with respect to the number of unknown key bits. This allows us to apply results from coding theory, and to explicitly connect the complexity of the algebraic cryptanalysis to the multiplicative complexity of the cipher. This means that we can provide asymptotic upper bounds on the complexity of algebraic attacks on selected families of ciphers based on the hardness of the decoding problem.     

Improved Pseudorandom Generators for Combinatorial Rectangles

We construct a pseudorandom generator which uses bits and approximates the volume of any combinatorial rectangle in to within error. This improves on the previous construction using bits by Armoni, Saks, Wigderson, and Zhou [4]. For a subclass of rectangles with at most nontrivial dimensions and each dimension being an interval, we also give a pseudorandom generator using bits. This again improves the previous upper bound by Chari, Rohatgi, and Srinivasan [5]. Received July 29, 1998     

The (related-key) impossible boomerang attack and its application to the AES block cipher

The Advanced Encryption Standard (AES) is a 128-bit block cipher with a user key of 128, 192 or 256 bits, released by NIST in 2001 as the next-generation data encryption standard for use in the USA. It was adopted as an ISO international standard in 2005. Impossible differential cryptanalysis and the boomerang attack are powerful variants of differential cryptanalysis for analysing the security of a block cipher. In this paper, building on the notions of impossible differential cryptanalysis and the boomerang attack, we propose a new cryptanalytic technique, which we call the impossible boomerang attack, and then describe an extension of this attack which applies in a related-key attack scenario. Finally, we apply the impossible boomerang attack to break 6-round AES with 128 key bits and 7-round AES with 192/256 key bits, and using two related keys we apply the related-key impossible boomerang attack to break 8-round AES with 192 key bits and 9-round AES with 256 key bits. In the two-key related-key attack scenario, our results, which were the first to achieve this amount of attacked rounds, match the best currently known results for AES with 192/256 key bits in terms of the numbers of attacked rounds. The (related-key) impossible boomerang attack is a general cryptanalytic technique, and can potentially be used to cryptanalyse other block ciphers.     

Ordering of nested square roots of 2 according to the Gray code

In this paper, we discuss some relations between zeros of Lucas–Lehmer polynomials and the Gray code. We study nested square roots of 2 applying a “binary code” that associates bits 0 and 1 to “plus” and “minus” signs in the nested form. This gives the possibility to obtain an ordering for the zeros of Lucas–Lehmer polynomials, which take the form of nested square roots of 2.     

Local primitivity of matrices and graphs

We develop a matrix-graph approach to the estimation of the communicative properties of a system of connected objects. In particular, this approach can be applied to analyzing the mixing properties of iterative cryptographic transformations of binary vector spaces, i.e. dependence of the output block bits on the input bits. In some applied problems, the saturation of the connections between the objects corresponds to the required level if the matrix modeling the connections or its certain submatrix is positive (the graph modeling the connections or its certain subgraph is complete). The concepts of local primitivity and local exponents of a nonnegative matrix (graph) are introduced. These concepts generalize and expand the area of application as compared to the familiar concepts of primitivity and exponent.We obtain a universal criterion for the local primitivity of a digraph and both a universal bound for the local exponents and its refinements for various particular cases. The results are applied to analyzing the mixing properties of a cryptographic generator constructed on the basis of two shift registers.     

On the Security of the Digital Signature Algorithm

We present a key-recovery attack against the Digital Signature Algorithm (DSA). Our method is based on the work of Coppersmith [7], and is similar in nature to the attacks of Boneh et al. [5,9] which use lattice reduction techniques to determine upper bounds on the size of an RSA decryption exponent under which it will be revealed by the attack. This work similarly determines provable upper bounds on the sizes of the two key parameters in the DSA for which the system can be broken. Specifically if about half of the total number of bits in the secret and ephemeral keys, assuming contiguous unknown bits in each key, are known, the system can be shown to be insecure. The same technique shows that if about half of the total number of bits in two ephemeral keys are known, again assumed contiguous unknown bits in each key, but with no knowledge of the secret key, the system can be shown to be insecure.     

Fault analysis of Trivium

As a hardware-oriented stream cipher, Trivium is on the edge of low cost and compactness. In this paper we discuss how brittle Trivium is under fault attack. Our fault model is based on the following two assumptions: (1) We can make fault injection on the state at a random time and (2) after each fault injection, the fault positions are from random one of three registers, and from a random area within eight neighboring bits. Our fault model has extremely weak assumptions for effective attack , and much weaker than that of Hojsík and Rudolf, in their fault attack on Trivium. We present a checking method such that, by observing original key-stream segment and fault injected key-stream segment, the injecting time and fault positions can be determined. Then, for several distributions of the injecting time, our random simulations always show that the attacker can break Trivium by a small number of repeated fault injections. For example, suppose that the injecting time has an uniform distribution over {0, 1, . . . , 32}, then averagely no more than 16 repeated fault injection procedures will break Trivium, by averagely observing no more than 195 × 17 key-stream bits.     

Fast compact prime number sieves (among others)

A parameterized family of algorithms is presented for the problem of finding all prime numbers up to a limit N. Many previous algorithms for this problem are shown to correspond to members of this family. A particular choice of parameters leads to an algorithm that requires only Θ(N) additions and that runs in bits. The small storage requirement is made possible by a provably compact method of storing all the primes up to some limit.     

Optimal random coding

We consider a stochastic method for representing a real number x by a finite sequence of bits. The method is symmetrical with respect to interchange of the bits: it is characterized by a single function p (x) which gives the probability that any particular bit is on as a function of the real number x that is being encoded. We then consider the problem of reconstructing x from its representation. In the limiting case in which the number of bits is large, we determine the function p (x) that minimizes the expected k-th power of the absolute error in this reconstruction. The optimal choice of p (x) is independent of k.     

A novel image encryption algorithm using chaos and reversible cellular automata

In this paper, a novel image encryption scheme is proposed based on reversible cellular automata (RCA) combining chaos. In this algorithm, an intertwining logistic map with complex behavior and periodic boundary reversible cellular automata are used. We split each pixel of image into units of 4 bits, then adopt pseudorandom key stream generated by the intertwining logistic map to permute these units in confusion stage. And in diffusion stage, two-dimensional reversible cellular automata which are discrete dynamical systems are applied to iterate many rounds to achieve diffusion on bit-level, in which we only consider the higher 4 bits in a pixel because the higher 4 bits carry almost the information of an image. Theoretical analysis and experimental results demonstrate the proposed algorithm achieves a high security level and processes good performance against common attacks like differential attack and statistical attack. This algorithm belongs to the class of symmetric systems.