On the Optimality of Non-Linear Computations of Length-Preserving Encryption Schemes.
Mridul Nandi · 2015
Abstract. It is well known that three and four rounds of balanced Feis-tel cipher or Luby-Rackoff (LR) encryption for two blocks messages are pseudorandom permutation (PRP) and strong pseudorandom permuta-tion (SPRP) respectively. A block is n-bit long for some positive integer n and a (possibly keyed) block-function is a nonlinear function map-ping all blocks to themselves, e.g. blockcipher. XLS (eXtended Latin Square) encryption defined over two block inputs with three blockcipher calls was claimed to be SPRP. However, later Nandi showed that it is not a SPRP. Motivating with these observations, we consider the following questions in this paper: What is the minimum number of invocations of block-functions required to achieve PRP or SPRP security over ` blocks inputs? To answer this question, we consider all those length-preserving encryption schemes, called linear encryption mode, for which only nonlinear operations are block-functions. Here, we prove the following results for these encryption schemes: 1. At least 2 ` (or 2` − 1) invocations of block-functions are required to achieve SPRP (or PRP respectively). These bounds are also tight. 2. To achieve the above bound for PRP over `> 1 blocks, either we need at least two keys or it can not be inverse-free (i.e., need to apply the inverses of block-functions in the decryption). In particular, we show that a single-keyed inverse-free PRP needs 2 ` invocations of block functions. 3. We show that 3-round LR using a single-keyed pseudorandom func-tion (PRF) is PRP if we xor a block of input by a masking key.