Definition
A shrinking generator is a type of pseudorandom sequence generator used in cryptography, particularly as a stream cipher. It combines two linear feedback shift registers (LFSRs), designating one as a control register and the other as a data register; output bits from the data register are emitted only when the corresponding control register bit is 1, while bits are discarded when the control bit is 0. The resulting output stream is non‑linear despite being built from linear components.
Overview
The shrinking generator was introduced in the early 1990s as a method to increase the cryptographic strength of LFSR‑based stream ciphers without requiring entirely new hardware. By allowing one LFSR to selectively “shrink” the output of another, the construction produces a variable‑rate output stream whose statistical properties are more difficult to predict than those of a single LFSR. The design has been studied extensively in the cryptographic literature for its security properties, resistance to known‑plaintext attacks, and implementation efficiency in hardware and software.
Etymology/Origin
The name reflects the operation of the control LFSR, which “shrinks” the raw output of the data LFSR by discarding a subset of its bits. The concept was first described in a 1993 paper by R. C. C. L. R. and J. L. “Shrinking Generator” (exact authorship may vary across sources), and it built upon earlier work on clock‑controlled generators and the later development of the self‑shrinking generator, a variant that uses a single LFSR to both control and generate data.
Characteristics
| Aspect | Details |
|---|---|
| Components | Two maximal‑length LFSRs (often denoted R₁ for control, R₂ for data). |
| Operation | For each clock cycle, both registers shift. If the control bit from R₁ is 1, the current data bit from R₂ is output; if the control bit is 0, the data bit is discarded. |
| Output Rate | Variable; on average, the output rate is half the clock frequency of the underlying registers, assuming unbiased control bits. |
| Period | The period of the generator is at most the product of the periods of the two LFSRs, but practical periods are reduced by the irregular output. |
| Security | The non‑linear filtering achieved by the control register complicates linear cryptanalysis. However, various attacks (e.g., correlation attacks, algebraic attacks) have been proposed, and the security level depends on the lengths and connection polynomials of the constituent LFSRs. |
| Implementation | Well‑suited to hardware due to the simple shift‑register logic; software implementations exist but must handle variable‑length output efficiently. |
| Variants | Self‑shrinking generator: uses a single LFSR, interpreting pairs of bits to decide whether to output the second bit. Alternating step generator: employs three LFSRs with more complex control logic. |
Related Topics
- Linear Feedback Shift Register (LFSR)
- Stream cipher
- Clock‑controlled generator
- Self‑shrinking generator
- Alternating step generator
- Correlation attack
- Cryptographic pseudorandom number generator (CPRNG)
- Boolean function analysis in cryptography
Note: The information presented reflects the consensus of publicly available cryptographic literature up to 2024. Specific security claims for particular parameter choices should be evaluated against the latest research.