The Shrinking Generator
Lecture notes in computer sciencePublished 5 August 2007
Don Coppersmith, Hugo Krawczyk, Yishay Mansour
Citations309
SJR quartileQ2
SJR score0.35
SNIP0.55
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
A new construction of a pseudorandom generator based on a simple combination of two LFSRs is presented, suitable for practical implementation of efficient stream cipher cryptosystems.
Abstract
We present a new construction of a pseudorandom generator based on a simple combination of two LFSRs. The construction has attractive properties as simplicity (conceptual and implementation-wise), scalability (hardware and security), proven minimal security conditions (exponential period, exponential linear complexity, good statistical properties), and resistance to known attacks. The construction is suitable for practical implementation of efficient stream cipher cryptosystems.
Keywords
Computer Science
WORLD SCIENTIFIC eBooksShift Register Sequences
2,187 Citations2014Solomon W. Golomb
The Revised Edition of Shift Register Sequences contains a comprehensive bibliography of some 400 entries which cover the literature concerning the theory and applications of shift register sequences.
SIAM Journal on ComputingHow to Generate Cryptographically Strong Sequences of Pseudorandom Bits
1,323 Citations1984Manuel Blum, Silvio Micali
Theory and application of trapdoor functions
1,020 Citations1982Andrew Chi-Chih Yao
A new information theory is introduced and the concept of trapdoor functions is studied and applications of such functions in cryptography, pseudorandom number generation, and abstract complexity theory are examined.
Theory and application of trapdoor functions
938 Citations1982Andrew Chi-Chih Yao
Random Structures and AlgorithmsSimple Constructions of Almost k‐wise Independent Random Variables
569 Citations1992Noga Alon, Oded Goldreich +2 more
This work presents three alternative simple constructions of small probability spaces on n bits for which any k bits are almost independent and their simplicity is their simplicity.
SIAM Journal on ComputingLearning Decision Trees Using the Fourier Spectrum
341 Citations1993Eyal Kushilevitz, Yishay Mansour
Small-bias probability spaces: efficient constructions and applications
197 Citations1990Joseph Naor, Moni Naor
It is shown how to efficiently construct a small probability space on n binary random variables such that for every subset, its parity is either zero or one with “almost” equal probability.
Simple construction of almost k-wise independent random variables
157 Citations2002Noga Alon, Oded Goldreich +2 more
The authors present three alternative simple constructions of small probability spaces on n bits for which any k bits are almost independent, and two of the constructions are based on bit sequences that are widely believed to possess randomness properties.
Lecture notes in computer scienceEfficient Structures for Geometric Data Management
139 Citations1988Oliver Günther
A dual approach to detect polyhedral intersections in arbitrary dimensions and an approximation scheme to represent arbitrary curved shapes are presented.
Learning decision trees using the Fourier spectrum
138 Citations1991Eyal Kushilevitz, Yishay Mansour
The authors demonstrate that any functionf whose L -norm is polynomial can be approximated by a polynomially sparse function, and prove that boolean decision trees with linear operations are a subset of this class of functions.
IEEE Journal on Selected Areas in CommunicationsClock-controlled shift registers: a review
134 Citations1989Dieter Gollmann, W.G. Chambers
Key-stream generators are discussed in which shift registers are clocked in a quasi-random manner under the control of other shift registers, and it is shown how large periods and linear equivalences can readily be obtained.
Lecture notes in computer scienceAlternating Step Generators Controlled by De Bruijn Sequences
118 Citations2010Christoph Günther
The period, the distribution of short patterns and a lower bound for the linear complexity of the sequences generated by an ASG are determination and the frequency of all short patterns as well as the autocorrelations turn out to be ideal.
Journal of the ACMInferring sequences produced by pseudo-random number generators
114 Citations1989Joan Boyar
Efficient algorithms are given for inferring sequences produced by certain pseudo-random number generators and specific examples of generators having this form are shown to be cryptographically insecure.
SIAM Journal on ComputingReconstructing Truncated Integer Variables Satisfying Linear Congruences
112 Citations1988Alan Frieze, Johan Håstad +3 more
A general polynomial time algorithm is proposed to find small integer solutions to systems of linear congruences and will solve most problems when twice as much information as that necessary to uniquely determine the variables is available.
Lecture notes in computer scienceThe Stop-and-Go-Generator
89 Citations2007T. Beth, Fred Piper
Under the correct assumptions cascading of primitive shift registers leads to interesting results, but from Gollmann's work it is clear that general results on cascaded arbitrary shift registers cannot be expected.
Journal of AlgorithmsHow to predict congruential generators
80 Citations1992Hugo Krawczyk
It is proved that multivariate polynomial generators, i.e. generators where si, = P(si-n,...,si-1) (mod m), for a polynometric P of fixed degree in n variables, are efficiently predictable.
Secret linear congruential generators are not cryptographically secure
73 Citations1987Jacques Stern
This paper discusses the predictability of the sequence given by outputing a constant proportion α of the leading bits of the numbers produced by a linear congruential generator and proves that a significant proportion of the bits can be predicted from the previous ones.
An O(n <i> <sup>log log n</sup> </i> ) learning algorithm for DNF under the uniform distribution
66 Citations1992Yishay Mansour
It is shown that a DNF with terms of size at most d can be approximated by a function with at least d non zero Fourier coefficients such that the expected error squared, with respect to the uniform distribution, is at most ε.
IEEE Transactions on Information TheoryOn the linear complexity of nonuniformity decimated PN-sequences
25 Citations1988Jovan Dj. Golić, Miodrag Živković
A lower bound is derived on the probability that when a PN-sequence of period N=2/sup n/-1 is nonuniformly decimated by means of a sequence whose period divides M, the decimated sequence will have maximum linear complexity nM.