Permutation-Based Tweakable On-line Cipher with Improved Security Guarantees

This paper focuses on the security of permutation-based tweakable on-line ciphers against related-key attacks. We firstly formalize syntaxes of tweakable on-line ciphers and tweakable on-line authenticated encryption modes, and set up their security models, respectively. Then we propose the first new parallelizable permutation-based tweakable on-line cipher PTOC, which is constructed by a public random permutation and a universal hash function family with a tweak and a key. We prove that PTOC achieves related-key strong tweakable on-line pseudorandom permutation security using H-coefficients technique. Finally, this paper introduces a provably secure permutation-based tweakable on-line authenticated encryption scheme PTOAE, which provides both decryption-misuse resistance and related-key security. Tweakable on-line schemes can be widely applied to the data storage security, database security, cloud security, big data security, and so on.