Welcome to the resource topic for 2015/414
Title:
On the Optimality of Non-Linear Computations of Length-Preserving Encryption Schemes
Authors: Mridul Nandi
Abstract:It is well known that three and four rounds of balanced Feistel cipher or Luby-Rackoff (LR) encryption for two blocks messages are pseudorandom permutation (PRP) and strong pseudorandom permutation (SPRP) respectively. A {\bf block} is n-bit long for some positive integer n and a (possibly keyed) {\bf block-function} is a nonlinear function mapping all blocks to themselves, e.g. blockcipher. XLS (eXtended Latin Square) with three blockcipher calls was claimed to be SPRP and later which is shown to be wrong. Motivating with these observations, we consider the following questions in this paper: {\em What is the minimum number of invocations of block-functions required to achieve PRP or SPRP security over \ell blocks inputs}? To answer this question, we consider all those length-preserving encryption schemes, called {\bf 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\ell (or 2\ell-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 \ell > 1 blocks, either we need at least two keys or it can not be {\em inverse-free} (i.e., need to apply the inverses of block-functions in the decryption). In particular, we show that a single-keyed block-function based, inverse-free PRP needs 2\ell invocations. (3) We show that 3-round LR using a single-keyed pseudorandom function (PRF) is PRP if we xor a block of input by a masking key.
ePrint: https://eprint.iacr.org/2015/414
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .