Cryptology ePrint Archive: Report 2018/137

Naor-Reingold Goes Public: The Complexity of Known-key Security

Pratik Soni and Stefano Tessaro

Abstract: We study the complexity of building secure block ciphers in the setting where the key is known to the attacker. In particular, we consider two security notions with useful implications, namely public-seed pseudorandom permutations (or psPRPs, for short) (Soni and Tessaro, EUROCRYPT '17) and correlation-intractable ciphers (Knudsen and Rijmen, ASIACRYPT '07; Mandal, Seurin, and Patarin, TCC '12).

For both these notions, we exhibit constructions which make only two calls to an underlying non-invertible primitive, matching the complexity of building a pseudorandom permutation in the secret-key setting. Our psPRP result instantiates the round functions in the Naor-Reingold (NR) construction with a secure UCE hash function. For correlation intractability, we instead instantiate them from a (public) random function, and replace the pairwise-independent permutations in the NR construction with (almost) $O(k^2)$-wise independent permutations, where $k$ is the arity of the relations for which we want correlation intractability.

Our constructions improve upon the current state of the art, requiring five- and six-round Feistel networks, respectively, to achieve psPRP security and correlation intractability. To do so, we rely on techniques borrowed from Impagliazzo-Rudich-style black-box impossibility proofs for our psPRP result, for which we give what we believe to be the first constructive application, and on techniques for studying randomness with limited independence for correlation intractability.

Category / Keywords: foundations / known-key security, pseudorandomness, psPRPs, correlation-intractability, limited independence

Original Publication (with minor differences): IACR-EUROCRYPT-2018

Date: received 5 Feb 2018

Contact author: pratik_soni at cs ucsb edu

Available format(s): PDF | BibTeX Citation

Note: A preliminary version of this paper appears at Eurocrypt 2018.

Version: 20180207:175814 (All versions of this report)

Short URL:

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]