Scramble All, Encrypt Small

In this paper, we propose a new design tool for "block encryption", allowing the en/decryption of arbitrarily long messages, but performing en/decryption on only a single block, where the rest of the message is only processed by a good scrambling function (e.g., one based on an ideal hash function). The design can be a component in constructing various schemes where the above properties gives an advantage. A quite natural use of our scheme is for remotely keyed encryption. We actually solve an open problem (at least in the ideal hash model and where hosts are allowed to add randomness), by demonstrating the existence of a secure remotely keyed encryption scheme which performs only one interaction with the trusted device.