On-Line Ciphers and the Hash-CBC Constructions

The authors initiate a study of on-line ciphers. These are ciphers that can take input plaintexts of large and varying lengths and will output the ith block of the cipher text after having processed only the first i blocks of the plaintext. Such ciphers permit length-preserving encryption of a data stream with only a single pass through the data. They provide security definitions for this primitive and study its basic properties. They then provide attacks on some possible candidates, including CBC with fixed IV. They then provide two constructions, HCBC1 and HCBC2, based on a given block cipher E and a family of computationally AXU functions.