On the Existence of Secure Keystream Generators

Designers of stream ciphers have generally used ad hoc methods to build systems that are secure against known attacks. There is often a sense that this is the best that can be done, that any system will eventually fall to a practical attack. In this paper we show that there are families of keystream generators that resist all possible attacks of a very general type in which a small number of known bits of a keystream are used to synthesize a generator of the keystream (called a synthesizing algorithm). Such attacks are exemplified by the Berlekamp—Massey attack. We first formalize the notions of a family of finite keystream generators and of a synthesizing algorithm. We then show that for any function h(n) that is in \cal O (2 ^n/d ) for every d>0 , there is a family \cal B of periodic sequences such that any efficient synthesizing algorithm outputs a generator of size h(log (\mathop \rm per \nolimits(B))) given the required number of bits of a sequence B∈ \cal B of large enough period. This result is tight in the sense that it fails for any faster growing function h(n) . We also consider several variations on this scenario. Received July 1996 and revised April 2000 Online publication 27 November, 2000     

Universal approximation capability of EBF neural networks with arbitrary activation functions

The purpose of this paper is to investigate the approximation capability of elliptic basis function (EBF) neural networks. The main results are: (1) A necessary and sufficient condition for a functionS (R ¹) to be qualified as an activation function in the hidden layer of an EBF neural network is given. (2) Every nonzero functionG L ²(R ⁿ ) is qualified to be an activation function in the elliptic neural network to approximate any function in L²(Rⁿ). (3) As applications, we give new proofs of the theorems concerning the approximation capability of affine basis function (ABF) neural networks and generalized radial basis function (GRBF) neural networks (including radial basis function neural networks) with arbitrary activation functions. In particular, we solve the problem of the approximation capability of sigma-pi neural networks.Work was supported in part by CNSF, the Shanghai Science Foundations and Doctoral Program of Education Commissions of China.     

针对流密码HC-256’的区分攻击

流密码HC-256’是eSTREAM计划候选密码HC-256的改进算法,至今未见关于HC-256’的安全性分析结果。该文提出了一种针对HC-256’的线性区分攻击,利用不同的非线性函数代替内部状态更新函数来寻找偶数位置上密钥流生成序列的弱点,通过线性逼近HC-256’的内部状态构造区分器。分析结果表明,需要约2 281bit,就能以0.9545的区分优势对密钥流进行区分。同时,该攻击为解决Sekar等人在2009年IWSEC会议上提出的问题进行了有益的探索。     

The Extended k-tree Algorithm

Consider the following problem: Given k=2 ^q random lists of n-bit vectors, L ₁,…,L _k , each of length m, find x ₁∈L ₁,…,x _k ∈L _k such that x ₁+⋅⋅⋅+x _k =0, where + is the XOR operation. This problem has applications in a number of areas, including cryptanalysis, coding theory, finding shortest lattice vectors, and learning theory. The so-called k-tree algorithm, due to Wagner, solves this problem in [(O)\tilde](2^q+n/(q+1))\tilde{O}(2^{q+n/(q+1)}) expected time provided the length m of the lists is large enough, specifically if m≥2 ^n/(q+1).     

An Efficient Parallel Algorithm for the Single Function Coarsest Partition Problem on the EREW PRAM

In this paper, we derive an efficient parallel algorithm to solve the single function coarsest partition problem. This algorithm runs in O(log2n) time using O(nlogn) operations on the EREW PRAM with O(n) memory cells used. Compared with the previous PRAM algorithms that consume O(n1+ε) memory cells for some positive constant ε > 0, our algorithm consumes less memory cells without increasing the total number of operations.     

An Efficient State Recovery Attack on the X-FCSR Family of Stream Ciphers

We describe a state recovery attack on the X-FCSR family of stream ciphers. In this attack we analyse each block of output keystream and try to solve for the state. The solver will succeed when a number of state conditions are satisfied. For X-FCSR-256, our best attack has a computational complexity of only 2^4.7 table lookups per block of keystream, with an expected 2^44.3 such blocks before the attack is successful. The precomputational storage requirement is 2³³. For X-FCSR-128, the computational complexity of our best attack is 2^16.3 table lookups per block of keystream, where we expect 2^55.2 output blocks before the attack comes through. The precomputational storage requirement for X-FCSR-128 is 2⁶⁷.     

Correlation properties of combiners with memory in stream ciphers

For pseudo-random generators where one or several LFSRs are combined by a memoryless function, it is known that the output sequences are correlated to certain LFSR-sequences whose correlation coefficients c _t satisfy the equation _i c ₂ ⁱ = 1. In this paper it is proved that a corresponding result also holds for generators whose LFSRs are connected to a combiner with memory.If correlation probabilities are conditioned on side information, e.g., on known output digits, it is shown that new or stronger correlations may occur. This is exemplified for the summation cipher with only two LFSRs where such correlations can be exploited in a known plaintext attack. A cryptanalytic algorithm is given which is shown to be successful for LFSRs of considerable length and with arbitrary feedback connection.A preliminary version of this paper was presented at Eurocrypt '90, May 21–24, Århus, Denmark, and has appeared in the proceedings, pp. 204–213.     

A Linear Distinguishing Attack on Scream

A linear distinguishing attack on the stream cipher Scream is proposed. When the keystream is of length 2⁹⁸ words, the distinguisher has a detectable advantage. When the keystream length is around 2¹²⁰ the advantage is very close to 1. This shows certain weaknesses of Scream. In the process, the paper introduces new general ideas on how to improve the performance of linear distinguishing attacks on stream ciphers.     

Fast correlation attacks on Bluetooth combiner

I. Introduction BluetoothTM is a standard for wireless short-range connectivity specified by the BluetoothTMspecial interest group in Ref.[1]. The specificationdefines a stream cipher algorithm E0 to be used forpoint-to-point encryption within the Bluetooth net-work. The main component of the Bluetooth streamcipher algorithm is the keystream generator (Blue-tooth combiner) which is derived from the well-known summation generator with four input LinearFeedback Shift Registers (LFSRs). A…     

Near-optimal tests for classes of write-triggered coupling faults in RAMs

This article is concerned with the detection of write-triggered coupling faults and toggling faults (certain double coupling faults) in n × 1 random-access memories (RAMs), where n is the number of one-bit words in the memory. In an earlier article we showed that any functional test that detects all multiple coupling faults must have a length of at least 2n ² + 3n. Since such a test is prohibitively long, given modern RAM capacities, we study more manageable subclasses of the class of all coupling faults. We show that there exist two hierarchies of fault models corresponding to nested subclasses of toggling faults and coupling faults, respectively, of increasing maximum multiplicities. We then identify optimal or near-optimal tests for two classes of toggling faults and five classes of coupling faults; these tests are of order n or nlog₂ n.This work was supported by the Natural Sciences and Engineering Research Council of Canada under Grants OGP0105567 and OGP0000871, and by the Information Technology Research Centre of Ontario.     

Deterministic tests for detecting singleV-coupling faults in RAMs

We consider the problem of detecting singleV-coupling faults (as defined by Nair, Thatte, and Abraham) inn×1 random-access memories (RAMs). First we derive a lower bound of 2 ^V–2 nlog₂ n+(2 ^V +3)n on the length of any test that detects all singleV-coupling faults, for 2V47 andn=2 ^e wheree{8,...,34}. In the derivation we make use of a family of binary codes which we call (n, )-exhaustive codes. We then describe a procedure which, given any (n, V–1)-exhaustive code, constructs a test that detects all singleV-coupling faults, fornV>2. Following this approach, optimal (n,1)- and (n, 2)-exhaustive codes are used to construct S2CTEST and S3CTEST, which are efficient tests of length 10n and 4nlog₂ n+18n that detect all single 2- and 3-coupling faults, respectively. S3CTEST is roughly five times shorter, for current RAM capacities, than Papachristou and Sahgal's test of length 24n[log₂ n]+n. Codes generated according to Tang and Chen are used similarly to construct S4CTEST and S5CTEST, which are tests of approximate length 8.6n(log₂ n)^1.585 and 9.6n(log₂ n)^2.322 that detect all single 4- and 5-coupling faults, respectively. S5CTEST has the interesting property of being able to detect all single physical neighborhood pattern-sensitive faults without requiring the mapping from logical cell addresses to physical cell locations. S5CTEST also detects the scrambled pattern-sensitive fault recently proposed by Franklin and Saluja; moreover, the new test is approximately fourteen times shorter (for 1 and 4 Mbit RAMs) than the test they describe.This work was supported by operating grants from the Central Research Fund of the University of Alberta and the Natural Sciences and Engineering Research Council of Canada under grant OGP0105567.     

Correlation properties of a general binary combiner with memory

Correlation properties of a general binary combiner with an arbitrary number M of memory bits are derived and novel design criteria proposed. For any positive integer m, the sum of the squares of the correlation coefficients between all nonzero linear functions of m successive output bits and all linear functions of the corresponding m successive inputs is shown to be dependent upon a particular combiner, unlike the memoryless combiners. The minimum and maximum values of the correlation sum as well as the necessary and sufficient conditions for them to be achieved are determined. It turns out that the security of combiners with memory can be considerably improved if M is not small.An efficient linear sequential circuit approximation (LSCA) method is developed for obtaining output and input linear functions with comparatively large correlation coefficients which is feasible for large M and works for any practical scheme. The method consists in deriving and solving a linear sequential circuit with additional nonbalanced inputs that is based on linear approximations of the output and the component next-state functions. The corresponding correlation attack on combiners with linear feedback shift registers is analyzed and it is shown that every such combiner with or without memory is essentially zero-order correlation immune.A preliminary version of this paper was presented at Eurocrypt '92 and was published in the proceedings. This research was supported in part by the Science Fund of Serbia, Grant #0403, through the Institute of Mathematics, Serbian Academy of Arts and Sciences.     

A method for robust stabilization

LetP(y,M) be a family of polynomials, depending on a controller parameter vector y in ⁿ⁺¹, defined as follows: a family of interval matrices, and y in ⁿ⁺¹, set Given an initial stabilizing controller y⁰, this paper provides a simple method to robustify y⁰, i.e., to obtain a controller parameter vector y¹ which is more robust than y⁰. Furthermore we define the stability factort for a given robustly stable controller y, which serves as a measure of the robustness of y.     

Robust Multi-Property Combiners for Hash Functions

A robust combiner for hash functions takes two candidate implementations and constructs a hash function which is secure as long as at least one of the candidates is secure. So far, hash function combiners only aim at preserving a single property such as collision-resistance or pseudorandomness. However, when hash functions are used in protocols like TLS they are often required to provide several properties simultaneously. We therefore put forward the notion of robust multi-property combiners and elaborate on different definitions for such combiners. We then propose a combiner that provably preserves (target) collision-resistance, pseudorandomness, and being a secure message authentication code. This combiner satisfies the strongest notion we propose, which requires that the combined function satisfies every security property which is satisfied by at least one of the underlying hash function. If the underlying hash functions have output length n, the combiner has output length 2n. This basically matches a known lower bound for black-box combiners for collision-resistance only, thus the other properties can be achieved without penalizing the length of the hash values. We then propose a combiner which also preserves the property of being indifferentiable from a random oracle, slightly increasing the output length to 2n+ω(logn). Moreover, we show how to augment our constructions in order to make them also robust for the one-wayness property, but in this case require an a priory upper bound on the input length.     

对比特搜索生成器的猜测确定攻击

针对具有低重量反馈多项式的比特搜索生成器(BSG),利用猜测确定攻击的思想提出了一种快速密钥恢复攻击。该算法基于BSG序列的差分构造特点,首先由截获的密钥流恢复出候选差分序列,然后用反馈多项式对候选差分序列进行校验,以此减少需要求解的L维线性方程系统的数量,从而大大减少了算法所需的复杂度。理论分析和仿真结果表明,对于反馈多项式的重量小于10的BSG,该算法明显优于现有的攻击方法。特别地当反馈多项式的重量为3时,该算法能够将最好的攻击结果O(L320.5L)降低到O(L20.5L)。     

Magnetotransport in a 2D system with strong scatterers: Renormalization of Hall coefficient caused by non-Markovian effects

We show that a sharp dependence of the Hall coefficient R on the magnetic field B arises in two-dimensional electron systems with strong scatterers. The phenomenon is due to classical memory effects. We calculate analytically the dependence of R on B for the case of scattering by antidots (modeled by hard disks of radius a), randomly distributed with concentration n ₀ ≪ 1/a ². We demonstrate that in very weak magnetic fields (ω _c τ_tr ≲ n ₀ a ²), memory effects lead to a considerable renormalization of the Boltzmann value of the Hall coefficient: δR/R ∼ 1. With increasing magnetic field, the relative correction to R decreases, then changes sign, and saturates at the value δR/R ∼ −n ₀ a ². We also discuss the effect of the smooth disorder on the dependence of R on B. The text was submitted by the authors in English.     

A Repeated Mapping Scheme of Task Modules with Minimum Communication Cost in Hypercube Multicomputers

This paper deals with the problem of one-to-one mapping of 2ⁿ task modules of a parallel program to an n-dimensional hypercube multicomputer so as to minimize the total communication cost during the execution of the task. The problem of finding an optimal mapping has been proven to be NP-complete. First we show that the mapping problem in a hypercube multicomputer can be transformed into the problem of finding a set of maximum cutsets on a given task graph using a graph modification technique. Then we propose a repeated mapping scheme, using an existing graph bipartitioning algorithm, for the effective mapping of task modules onto the processors of a hypercube multicomputer. The repeated mapping scheme is shown to be highly effective on a number of test task graphs; it increasingly outperforms the greedy and recursive mapping algorithms as the number of processors increases. Our repeated mapping scheme is shown to be very effective for regular graphs, such as hypercube-isomorphic or ‘almost’ isomorphic graphs and meshes; it finds optimal mappings on almost all the regular task graphs considered.     

Approximation Algorithms for the Mobile Piercing Set Problem with Applications to Clustering in Ad-Hoc Networks

The main contributions of this paper are two-fold. First, we present a simple, general framework for obtaining efficient constant-factor approximation algorithms for the mobile piercing set (MPS) problem on unit-disks for standard metrics in fixed dimension vector spaces. More specifically, we provide low constant approximations for L ₁ and L norms on a d-dimensional space, for any fixed d>0, and for the L ₂ norm on two- and three-dimensional spaces. Our framework provides a family of fully-distributed and decentralized algorithms, which adapt (asymptotically) optimally to the mobility of disks, at the expense of a low degradation on the best known approximation factors of the respective centralized algorithms: Our algorithms take O(1) time to update the piercing set maintained, per movement of a disk. We also present a family of fully-distributed algorithms for the MPS problem which either match or improve the best known approximation bounds of centralized algorithms for the respective norms and space dimensions.Second, we show how the proposed algorithms can be directly applied to provide theoretical performance analyses for two popular 1-hop clustering algorithms in ad-hoc networks: the lowest-id algorithm and the Least Cluster Change (LCC) algorithm. More specifically, we formally prove that the LCC algorithm adapts in constant time to the mobility of the network nodes, and minimizes (up to low constant factors) the number of 1-hop clusters maintained. While there is a vast literature on simulation results for the LCC and the lowest-id algorithms, these had not been formally analyzed prior to this work.We also present an O(logn)-approximation algorithm for the mobile piercing set problem for nonuniform disks (i.e., disks that may have different radii), with constant update time.     

Overflow probability for a discrete‐time queue with non‐stationary multiplexed input

Recently it has been reported that various traffic exhibit long‐range dependence and/or self‐similarity. However, there exist some reports which suggest that traffic may be non‐stationary. In this paper we discuss the average overflow probability J_N ^L(Ly)≡E[N⁻¹Σ_n=1 ^NI{Q_n ^L>Ly}] in a finite period [1,N] for a discrete‐time queue Q_n ^L with a non‐stationary multiplexed input from L sources. By using the large deviation principle, we analyze the asymptotic behavior of J_N ^L(Ly) as L increases and obtain an approximation formula of the form J_n ^L(Ly)≈C(L,y) e^−γ(y). We apply the approximation formula to two examples. One is a non‐stationary process with deterministic level shifts and the other is a Gaussian process with spectrum of the form f^−ν. The latter is non‐stationary if ν≥1. This revised version was published online in June 2006 with corrections to the Cover Date.