Correlation properties of a general binary combiner with memory

DOI10.1007/BF00190805MaRDI QIDQ1916030zbMATH OpenFDO

Authors J. Dj. Golić

Publication date 2 November 1997

Published in Journal of Cryptology (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/BF00190805

zbMATH Keywords

balanced functionbinary combinerscorrelationsequencesshift register

Mathematics Subject Classification ID

Shift register sequences and sequences over finite alphabets in information and communication theory (94A55) Cryptography (94A60)

Review text

In this paper correlation properties of a general binary combiner with memory are studied. There are two functions that play important roles: the next state function that computes a next state based on the current state and a time dependent input vector, and the output function that computes an output based upon the current state and the input vector. The inputs are assumed to be mutually independent, balanced uniformly distributed binary random variables. The state space is associated with the memory size. It is proved that a pair of certain mutually correlated functions of at most \(M+1\) successive outputs and inputs exists. The minimum value of 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 minimal if and only if any \(M\) successive output bits are balanced and statistically independent of the corresponding \(M\) successive inputs. The output function must then be balanced for each memory state. For large \(M\) the author developed a method (Linear Sequential Circuit Approximation) that can be used for finding linear functions on outputs and inputs with comperatively large correlation coefficients.

Recommendations

• scientific article; zbMATH DE number 503332
• Correlation properties of combiners with memory in stream ciphers
• scientific article; zbMATH DE number 177035

Cites work

• A spectral characterization of correlation-immune combining functions
• Analysis and design of stream ciphers
• Correlation properties of combiners with memory in stream ciphers
• Correlation-immunity of nonlinear combining functions for cryptographic applications (Corresp.)
• Fast correlation attacks on certain stream ciphers
• scientific article; zbMATH DE number 1024088 (Why is no real title available?)
• scientific article; zbMATH DE number 4195884 (Why is no real title available?)
• scientific article; zbMATH DE number 3276159 (Why is no real title available?)
• Linear models for keystream generators

Cited in

(9)

• Cryptanalysis of an E0-like combiner with memory
• Practical cryptanalysis of Bluetooth encryption with condition masking
• On the linear complexity of feedforward clock-controlled sequence
• Fast Correlation Attacks: Methods and Countermeasures
• scientific article; zbMATH DE number 177035 (Why is no real title available?)
• scientific article; zbMATH DE number 503332 (Why is no real title available?)
• Extended BDD-Based Cryptanalysis of Keystream Generators
• Correlation theorems in cryptanalysis
• Edit distance correlation attacks on clock-controlled combiners with memory

This page was built for publication: Correlation properties of a general binary combiner with memory

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1916030)