Faster attack on certain stream ciphers

A number of keystream generators can be attacked by guessing the contents of one shift register and then checking to see whether this guess is consistent with the observed keystream. Where the target register is n bits long, this gives an attack of complexity 2/sup n-0(1)/. A further optimisation is presented which appears to reduce the complexity to about 2/sup n/2/ in many cases of practical interest.<>     

A `liub(log2(N))-2' resilient decentralized commitprotocol

In distributed database systems, commit protocols are used to ensure the transaction atomicity. In the presence of failures, nonblocking commit protocols can guarantee the transaction atomicity without blocking the transaction execution. A (resilient) decentralized nonblocking commit protocol (RDCP) is proposed for distributed database systems. This protocol is based on the hypercube network topology and is `liub(log₂ (N))-2' resilient to node failures (N=number of system-nodes). The number of messages sent among the N nodes is O(N·log₂² (N)) which is only a factor of log₂ (N) over the message complexity lower bound O(N·log₂ (N)) of decentralized commit protocols. Furthermore, RDCP is an optimistic nonblocking protocol. It aborts the transaction only when some nodes want to abort or some nodes fail before they make local decisions     

钟控密钥流生成器及其密码性能

提出了一种新的钟控密钥流生成器,由3个移位寄存器组成：两个被钟控的线性反馈移位寄存器A和B,一个提供钟控信息的非线性反馈移位寄存器C。设A、B和C的长度分别为l1、l2和l3。移位寄存器A和B的钟控信息由从移位寄存器C选取的两个比特串提供,移位的次数分别是两个比特串的汉明重量。研究了该生成器的周期、线性复杂度和k错线性复杂度,分析了这种密钥流生成器的安全性。     

Yet another result on multi-log2N networks

One-to-many connection (i.e., multicast) is an important communication primitive used in parallel processing and high-speed switching in order to simultaneously send data from an input to more than one output. We prove that for even (respectively, odd) n, a multi-log₂N network is strictly nonblocking for a one-to-many connection traffic if it is designed by vertically stacking at least (δn)/4+1((δ/2)(n-1)+1) planes of a log₂N network together, where N=2ⁿ, δ=2^[n/2], and [x] denotes the greatest integer less than or equal to x. We thus give answer to the open problem and introduce yet another strictly nonblocking multicast network. The characterized network has self-routing capability, regular topology, O(2log₂N+2log₂(log₂N)) stages, and fewer crosspoints than the Clos network for N⩾512. We then extend multi log₂N multicast networks to the fanout restricted nonblocking networks. It turns out that the multi-log₂N network nonblocking in a strict-sense for a one-to-one connection traffic is also wide-sense nonblocking for a multicast traffic in which the fanout of any connection does not exceed δ, provided that for even (respectively, odd) n, the fanout capability of each log₂N network is restricted to stage (n/2)(((n-1)/2)+1) through n-1     

Linear models for a time-variant permutation generator

A keystream generator, known as RC4, consisting of a permutation table that slowly varies in time under the control of itself, is analyzed by the linear model approach. The objective is to find linear relations among the keystream bits that hold with probability different from one half by using the linear sequential circuit approximation method. To estimate the corresponding correlation coefficients, some interesting correlation properties of random Boolean functions are derived. It is thus shown that the second binary derivative of the least significant hit output sequence is correlated to 1 with the correlation coefficient close to 15·2^-3n where n is the variable word size of RC4. The output sequence length required for the linear statistical weakness detection is then around 64ⁿ/225. The result can be used to distinguish RC4 from other keystream generators and to determine the unknown parameter n, as well as for the plaintext uncertainty reduction if n is small     

Attacking the Pollard Generator

Let p be a prime and let c be an integer modulo p. The Pollard generator is a sequence (u_n) of pseudorandom numbers defined by the relation u_n+1equivu_n ²+c mod p. It is shown that if c and 9/14 of the most significant bits of two consecutive values u_n,u_n+1 of the Pollard generator are given, one can recover in polynomial time the initial value u₀ with a probabilistic algorithm. This result is an improvement of a theorem in a recent paper which requires that 2/3 of the most significant bits be known     

基于E0算法的猜测决定攻击

对短距离无线蓝牙技术中使用的E0序列密码算法进行了猜测决定攻击,攻击中利用线性逼近的方法做出了一个巧妙的攻击假设,降低了攻击所需的猜测量,并且通过一个检验方程降低了候选状态的数量,攻击的计算复杂度为O(276),需要约988bit密钥流,属于短密钥流攻击.相对于长密钥流攻击,短密钥流攻击所需的密钥流不超过2745bit,对E0的安全性更具威胁.与目前已有的针对E0的短密钥流攻击相比,所提出猜测决定的攻击结果是最好的.     

Vesta-2M流密码的密码分析

分析了俄国商用密码Vesta-2M流密码的安全性。流密码Vesta-2M的密钥流发生器的初始密钥规模为O(2^536)。本文指出文献[1]中攻击方法的错误，并提出一种已知明文攻击方法，所需明文量很小(约几百比特)，计算复杂度的上界为O(2^372)。     

Low-complexity centralized joint power and admission control in cognitive radio networks

This letter introduces a centralized joint power and admission control algorithm for cognitive radio networks. Its novelty lies in the proposed admission metric. Unlike those in existing algorithms, our metric predetermines the admission order of N secondary users which intend to access the network. This allows us to search a group of admitted secondary users with the bisection method. The proposed algorithm is shown by simulation to achieve a comparable performance to existing algorithms, and the computational complexity is reduced from O(N³) to O(N² log₂ N).     

An O(n·(log2(n))2) algorithm forcomputing the reliability of k-out-of-n:G and k-to-l-out-of-n:G systems

This paper presents the RAFFT-GFP (Recursively Applied Fast Fourier Transform for Generator Function Products) algorithm as a computationally superior algorithm for expressing and computing the reliability of k-out-of-n:G and k-to-l-out-of-n:G systems using the fast Fourier transform. Originally suggested by Barlow and Heidtmann (1984), generating functions provide a clear, concise method for computing the reliabilities of such systems. By recursively applying the FFT to computing generator function products, the RAFFT-GFP achieves an overall asymptotic computational complexity of O(n·(log₂(n)) ²) for computing system reliability. Algebraic manipulations suggested by Upadhyaya and Pham (1993) are reformulated in the context of generator functions to reduce the number of computations. The number of computations and the CPU time are used to compare the performance of the RAFFT-GFP algorithm to the best found in the literature. Due to larger overheads required, the RAFFT-GFP algorithm is superior for problem sizes larger than about 4000 components, in terms of both computation and CPU time for the examples studied in this paper. Lastly, studies of very large systems with unequal reliabilities indicate that the binomial distribution gives a good approximation for generating function coefficients, allowing algebraic solutions for system reliability     

High-order spectral-null codes-constructions and bounds

Let 𝒮(n.k) denote the set of all words of length n over the alphabet {+1,-1}, having a k th order spectral-null at zero frequency. A subset of 𝒮(n,k) is a spectral-null code of length n and order k. Upper and lower bounds on the cardinality of 𝒮(n,k) are derived. In particular we prove that (k-1) log₂ (n/k)⩽n-log₂ |𝒮(n,k)|⩽O(2^klog₂n) for infinitely many values of n. On the other hand, we show that 𝒮(n.k) is empty unless n is divisible by 2^m, where m=[log₂k]+1. Furthermore, bounds on the minimum Hamming distance d of 𝒮(n,k) are provided, showing that 2k⩽d⩽k(k-1)+2 for infinitely many n. We also investigate the minimum number of sign changes in a word x∈𝒮(n,k) and provide an equivalent definition of 𝒮(n,k) in terms of the positions of these sign changes. An efficient algorithm for encoding arbitrary information sequences into a second-order spectral-null code of redundancy 3 log₂n+O(log log n) is presented. Furthermore, we prove that the first nonzero moment of any word in 𝒮(n,k) is divisible by k!. This leads to an encoding scheme for spectral-null codes of length n and any fixed order k, with rate approaching unity as n→∞     

Asymptotically exact bounds on the size of high-order spectral-nullcodes

The spectral-null code S(n, k) of kth order and length n is the union of n-tuples with ±1 components, having kth-order spectral-null at zero frequency. We determine the exact asymptotic in n behavior of the size of such codes. In particular, we prove that for n satisfying some divisibility conditions, log₂|S(n, k)|=n-k ²/2log₂n+c_k+o(1), where c_k is a constant depending only on k and o(1) tends to zero when n grows. This is an improvement on the earlier known bounds due to Roth, Siegel, and Vardy (see ibid., vol40, p.1826-40, 1994)     

Low complexity affine MMSE detector for iterative detection-decoding MIMO OFDM systems

Iterative turbo processing between detection and decoding shows near-capacity performance on a multiple-antenna system. Combining iterative processing with optimum front-end detection is particularly challenging because the front-end maximum a posteriori (MAP) algorithm has a computational complexity that is exponential. Sub-optimum detector such as the soft interference cancellation linear minimum mean square error (SIC-LMMSE) detector with near front-end MAP performance has been proposed in the literature. The asymptotic computational complexity of SIC-LMMSE is O(n_t ²n_r + n_tn_r ³ + n_tM_c2^Mc) per detection-decoding cycle where n_t is number of transmit antenna, nr is number of receive antenna, and Mc is modulation size. A lower complexity detector is the hard interference cancellation LMMSE (HIC-LMMSE) detector. HIC-LMMSE has asymptotic complexity of O(n_t ²n_r + n_tM_c2^Mc) but suffers extra performance degradation. In this paper, two front-end detection algorithms are introduced that not only achieve asymptotic computational complexity of O(n_t ²n_r + n_tn_r ² [Gamma (beta) + 1] + n_tM_c2^Mc) where Gamma(beta) is a function with discrete output {-1, 2, 3, ...,n_t} and O(n_tM_c2^Mc) respectively. Simulation results demonstrate that the proposed low complexity detection algorithms offer exactly same performance as their full complexity counterpart in an iterative receiver while being computational more efficient.     

Fast evaluation of an integral occurring in digital filteringapplications

A fast evaluation procedure for the integral I_m,n,p=1/2πj∯_|z|=1H_m,n(z)H _m,n(z^-1)z^p-1dz for arbitrary nonnegative integer-valued m, n, and p, is presented, where H_m,n (z)=Σ_k=0^mb_m,kz^-k /Σ_l=0ⁿa_n,lz^-1,a _n,0≠0 is the transfer function of an arbitrary digital filter. Evaluation of this integral frequently appears in control, communication, and digital filtering. A notable result is the one-term recursion on p, for arbitrary but fixed nonnegative integers m and n. The computational complexity is analyzed, and two illustrative examples demonstrate some of the advantages of this approach     

Information rates by oversampling the sign of a bandlimited process

A sequence of binary (±1) random variables is generated by sampling a hard-limited version of a bandlimited process at n times the Nyquist rate. The information rate ℐ carried by these binary samples is investigated. It is shown by constructing a specific nonstationary, bounded, bandlimited process (the real zeros of which are independent and identically distributed, isolated, and lying in different Nyquist intervals) that ℐ=log₂(n+1) bits per Nyquist interval is achievable. A more complicated construction in which L distinct zeros are placed in L consecutive Nyquist intervals yields achievable rates that approach (for L→∞) ℐ arbitrarily closely, where ℐ=log₂n + (n-1)log₂[n/(n-1)], n⩾2 (and ℐ=1 for n=1 and L=1). By exploiting the constraints imposed on the autocorrelation function of a stationary sign (bilevel) process with a given average transition rate, the latter expression is shown also to yield an upper bound on the achievable values of ℐ. The logarithmic behavior with n (n≫1) is due to the high correlation between the oversampled binary samples, and it is established that this trend is also achievable with stationary sign processes. This model may be used to gain insight into the effect of finite resolution on the information (in Shannon's sense) conveyed by the sign of a bandlimited process, and also to assess the limiting performance of certain oversampling-based communication systems     

Binary m-sequences with three-valued crosscorrelation: a proof ofWelch's conjecture

We prove the long-standing conjecture of Welch stating that for odd n=2m+1, the power function x^d with d=2^m+3 is maximally nonlinear on GF(2ⁿ) or, in other terms, that the crosscorrelation function between a binary maximum-length linear shift register sequence of degree n and a decimation of that sequence by 2^m+3 takes on precisely the three values -1, -1±2^m+1     

On the robustness of single-loop sigma-delta modulation

Sigma-delta modulation, a widely used method of analog-to-digital (A/D) signal conversion, is known to be robust to hardware imperfections, i.e., bit streams generated by slightly imprecise hardware components can be decoded comparably well. We formulate a model for robustness and give a rigorous analysis for single-loop sigma-delta modulation applied to constant signals (DC inputs) for N time cycles, with an arbitrary (small enough) initial condition u_o, and a quantizer that may contain an offset error. The mean-square error (MSE) of any decoding scheme for this quantizer (with u_o and the offset error known) is bounded below by 1/96N^-3. We also determine the asymptotically best possible MSE as N→∞ for perfect decoding when u_o=0 and u_o=½. The robustness result is the upper bound that a triangular linear filter decoder (with both u_o and the offset error unknown) achieves an MSE of 40/3N^-3. These results establish the known result that the O(1/N³) decay of the MSE with N is optimal in the single-loop case, under weaker assumptions than previous analyses, and show that a suitable linear decoder is robust against offset error. These results are obtained using methods from number theory and Fourier analysis     

Sort-and-match algorithm for soft-decision decoding

Let a q-ary linear (n, k) code C be used over a memoryless channel. We design a decoding algorithm Ψ_N that splits the received block into two halves in n different ways. First, about √N error patterns are found on either half. Then the left- and right-hand lists are sorted out and matched to form codewords. Finally, the most probable codeword is chosen among at most n√N codewords obtained in all n trials. The algorithm can be applied to any linear code C and has complexity order of n³√N. For any N⩾q^n-k, the decoding error probability P_N exceeds at most 1+q^n-k/N times the probability P_Ψ (C) of maximum-likelihood decoding. For code rates R⩾1/2, the complexity order q^n-k/2 grows as square root of general trellis complexity q^min{n-k,k}. When used on quantized additive white Gaussian noise (AWGN) channels, the algorithm Ψ_N can provide maximum-likelihood decoding for most binary linear codes even when N has an exponential order of q^n-k     

A Balancing Method for PMEPR Reduction in OFDM Signals

A relation is established between the strength of a binary code over the alphabet {+1,-1}, and its ability to reduce peak-to-mean envelope power ratio (PMEPR) in n-subcarrier (OFDM) signals. Based on this relation, a method is proposed to deterministically bound PMEPR of such signals using coordinate-wise multiplication by a balancing vector (BV) chosen from a code of given strength. A practical probabilistic scheme considering a small number of candidate codewords is devised. For this scheme, estimates on the PMEPR reduction achievable with arbitrary high probability are derived. In particular, the scheme provides for large n PMEPR of lnn+2.01lnlnn with (ln2)middot(log₂n)²+1 bits of redundancy, the failure probability at most e^-n, and testing n/(lnlnn) candidate BVs. Finally, several practical settings are considered. For example, for quaternary phase-shift keying, n=128, the scheme with 36 bits of redundancy (18 redundant subcarriers), by testing only 4 BVs provides over 2 dB PMEPR reduction, for any failure rate below 10^-2.5     

Soft-decision majority decoding of Reed-Muller codes

We present a new soft-decision majority decoding algorithm for Reed-Muller codes RM(r,m). First, the reliabilities of 2^m transmitted symbols are recalculated into the reliabilities of 2^m-r parity checks that represent each information bit. In turn, information bits are obtained by the weighted majority that gives more weight to more reliable parity checks. It is proven that for long low-rate codes RM(r,m), our soft-decision algorithm outperforms its conventional hard-decision counterpart by 10 log₁₀(π/2)≈2 dB at any given output error probability. For fixed code rate R and m→∞, our algorithm increases almost 2^r/2 times the correcting capability of soft-decision bounded distance decoding