Paper 2015/414

On the Optimality of Non-Linear Computations of Length-Preserving Encryption Schemes

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.

Note: A small changes in the SPRP distinguisher has been done as pointed out by Lear Bahack in the crypto-competition google forum.

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
Preprint. MINOR revision.
Keywords
XLSCMCLuby-RackoffPRPSPRPBlockcipher.
Contact author(s)
mridul nandi @ gmail com
History
2015-05-27: last of 2 revisions
2015-05-05: received
See all versions
Short URL
https://ia.cr/2015/414
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2015/414,
      author = {Mridul Nandi},
      title = {On the Optimality of Non-Linear Computations of Length-Preserving Encryption Schemes},
      howpublished = {Cryptology ePrint Archive, Paper 2015/414},
      year = {2015},
      note = {\url{https://eprint.iacr.org/2015/414}},
      url = {https://eprint.iacr.org/2015/414}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.