ABSTRACT
This chapter focuses on comparatively heuristic—but far more efficient—constructions of these primitives that are widely used in practice. It explores the heuristic in the sense that they cannot be proven secure based on any weaker assumption. The primary difference is that the former assumption relates to a weaker requirement: the assumption that large integers are hard to factor is arguably simpler and more natural than the assumption that AES with a uniform key is indistinguishable from a random permutation. Other relevant differences are that factoring has been studied much longer than the problem of distinguishing AES from a random permutation, and that factoring was recognized as a hard problem by mathematicians independent of any cryptographic applications. The way in which the output streams of the underlying LFSRs are combined must be done so as to ensure the final output is unbiased.
