Provable Security of Symmetric-keyCryptographic Schemes

Abstract

Abstract: A symmetric-key cryptographic scheme is deemed to be provably secure if one can formally argue that it is secure given the hardness of some underlying computational problem. This thesis is a study of the provable security of symmetric-key cryptographic schemes, encompassing major information security goals, viz. data authentication, encryption and authenticated encryption. Along the way, we provide quantitative (better security bounds) and/or qualitative (relaxation in security preconditions) improvements in the provable security of several schemes. Among authentication schemes, we study CBC-MAC and XMAC family of message authentication codes. In case of the CBC-MAC family, we provide improved security bounds for several members, and in case of the XMAC family, we generalize the underlying counter-based encoding to derive simplified security arguments and several efficient variants. Among encryption schemes, we explore possible ways to construct beyond-the-birthday bound online ciphers using tweakable block ciphers. We show that an existing BBB scheme POEx is only birthday bound secure, and as a consequence propose a variant called XTC that achieves (almost) optimal security. On a related topic, we study the security of CLRW2, a tweakable block cipher construction based on block ciphers. We show tight security for CLRW2 under the assumption that the underlying hash functions are 3-wise AXU hash. We conclude our study with an exploration of the scope of random read access in OCB authentication encryption scheme. We observe that the existing versions of OCB are highly inefficient in random read access due to a strong assumption (AXU hash) on the underlying mask generating function. We define a relaxed notion of universal hash, called locally imperfect XOR universal (LIXU), and show that generalized OCB is secure even under this relaxed notion. Finally, we give some efficient candidates for LIXU hash that are apt for efficient random read access in OCB.