Provable Security and Indifferentiability

Doctoral thesis (2012)

In this thesis we consider different problems related to provable security and indifferentiability framework. Ideal primitives such as random oracles, ideal ciphers are theoretical abstractions of ... [more ▼]

In this thesis we consider different problems related to provable security and indifferentiability framework. Ideal primitives such as random oracles, ideal ciphers are theoretical abstractions of cryptographic hash functions and block ciphers respectively. These idealized models help us to argue security guarantee for various cryptographic schemes, for which standard model security proofs are not known. In the first part of this thesis we consider the problems related to ideal primitive construction starting from a different ideal primitive. We adopt the indifferentiability framework proposed by Maurer et. al. in TCC’04 for this purpose. The indifferentiability framework helps us to preserve the security guarantee of cryptographic schemes when the ideal primitives are replaced by indifferentiable constructions, even when the ideal primitives are used in a public manner. At first, we consider the problem of ideal cipher domain extension. We show the 3-round Feistel construction, built using n-bit ideal ciphers are actually indifferentiable from a 2n-bit ideal cipher. We also consider other related issues such as, why 2-round Feistel is not sufficient, security analysis in standard indistinguishability model for both 2 and 3 round constructions, etc. Afterwards, we consider the open problem: whether 6-round Feistel construction using random round functions is indifferentiable from a random invertible permutation or not. We give a partial positive answer to this question. We show the construction is actually publicly-indifferentiable (which is a restricted version of full indifferentiability) from an in- vertible random permutation. In the later part of the thesis, we concentrate on some issues related to the security of Probabilistic Signature Scheme (PSS). PSS with RSA trapdoor is a widely deployed randomized signature scheme. It is known to be secure in Random Oracle model. However, recently randomized signature scheme such as iso/iec 9796-2 is shown to be susceptible to hardware fault attacks. In this work we show, PSS is actually secure against random fault attacks in random oracle model. Afterwards, we consider the openproblem related to standard model security of PSS. We give a general negative result in this direction. We rule out existence of any black box proof technique showing security of PSS in standard model. [less ▲]

A Domain Extender for the Ideal Cipher

in Proceedings of TCC 2010 (2010)

We describe the first domain extender for ideal ciphers, i.e. we show a construction that is indifferentiable from a 2n-bit ideal cipher, given a n-bit ideal cipher. Our construction is based on a 3-round ... [more ▼]

We describe the first domain extender for ideal ciphers, i.e. we show a construction that is indifferentiable from a 2n-bit ideal cipher, given a n-bit ideal cipher. Our construction is based on a 3-round Feistel, and is more efficient than first building a n-bit random oracle from a n-bit ideal cipher (as in [9]) and then a 2n-bit ideal cipher from a n-bit random oracle (as in [10], using a 6-round Feistel). We also show that 2 rounds are not enough for indifferentiability by exhibiting a simple attack. We also consider our construction in the standard model: we show that 2 rounds are enough to get a 2n-bit tweakable block-cipher from a n-bit tweakable block-cipher and we show that with 3 rounds we can get beyond the birthday security bound. [less ▲]