Online Encryption Schemes: New Security Notions and Constructions

We investigate new strong security notions for on-line symmetric encryption schemes, which are the schemes whose encryption and decryption algorithms operate “on-the-fly” and in one pass, namely can compute and return an output block given only the key, the current input block and the previous input and output blocks. We define the strongest achievable notion of privacy which takes into account both chosen-ciphertext attacks and the recently introduced blockwise-adaptive [15,12] attacks. We show that all the schemes shown to be secure against blockwise-adaptive chosen-plaintext attacks are subject to blockwise-adaptive chosen-ciphertext attacks. We present an on-line encryption scheme which is provably secure under our notion. It uses any strong on-line cipher, the primitive introduced in [1]. We finally discuss the notion of authenticated on-line schemes and provide a secure construction.