Cryptology ePrint Archive: Report 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.

Category / Keywords: foundations / PRP, pseudo random permutation, block ciphers, format preserving encryption, deterministic encryption, small domain

Date: received 5 May 2012, last revised 15 Jun 2012

Contact author: emil at cs berkeley edu

Available format(s): PDF | BibTeX Citation

Version: 20120615:160224 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]