Paper 2008/091

A Generic Method to Extend Message Space of a Strong Pseudorandom Permutation

Mridul Nandi

Abstract

In this paper we present an efficient and secure generic method which can encrypt messages of size at least $n$. This generic encryption algorithm needs a secure encryption algorithm for messages of multiple of $n$. The first generic construction, XLS, has been proposed by Ristenpart and Rogaway in FSE-07. It needs two extra invocations of an independently chosen strong pseudorandom permutation or SPRP defined over $\s^n$ for encryption of an incomplete message block. Whereas our construction needs only one invocation of a weak pseudorandom function and two multiplications over a finite field (equivalently, two invocations of an universal hash function). We prove here that the proposed method preserves (tweakable) SPRP. This new construction is meaningful for two reasons. Firstly, it is based on weak pseudorandom function which is a weaker security notion than SPRP. Thus we are able to achieve stronger security from a weaker one. Secondly, in practice, finite field multiplication is more efficient than an invocation of SPRP. Hence our method can be more efficient than XLS.

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
Published elsewhere. Unknown where it was published
Contact author(s)
mridul nandi @ gmail com
History
2008-02-28: received
Short URL
https://ia.cr/2008/091
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2008/091,
      author = {Mridul Nandi},
      title = {A Generic Method to Extend Message Space of a Strong Pseudorandom Permutation},
      howpublished = {Cryptology {ePrint} Archive, Paper 2008/091},
      year = {2008},
      url = {https://eprint.iacr.org/2008/091}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.