Paper 2012/254

FastPRP: Fast Pseudo-Random Permutations for Small Domains

Emil Stefanov and Elaine Shi

Abstract

We propose a novel small-domain pseudo-random permutation, also referred to as a small-domain cipher or small-domain (deterministic) encryption. We prove that our construction achieves "strong security", i.e., is indistinguishable from a random permutation even when an adversary has observed all possible input-output pairs. More importantly, our construction is 1,000 to 8,000 times faster in most realistic scenarios, in comparison with the best known construction (also achieving strong security). Our implementation leverages the extended instruction sets of modern processors, and we also introduce a smart caching strategy to freely tune the tradeoff between time and space.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Published elsewhere. Unknown where it was published
Keywords
PRPpseudo random permutationblock ciphersformat preserving encryptiondeterministic encryptionsmall domain
Contact author(s)
emil @ cs berkeley edu
History
2012-06-15: revised
2012-05-09: received
See all versions
Short URL
https://ia.cr/2012/254
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2012/254,
      author = {Emil Stefanov and Elaine Shi},
      title = {FastPRP: Fast Pseudo-Random Permutations for Small Domains},
      howpublished = {Cryptology ePrint Archive, Paper 2012/254},
      year = {2012},
      note = {\url{https://eprint.iacr.org/2012/254}},
      url = {https://eprint.iacr.org/2012/254}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.