Paper 2018/137

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

Pratik Soni and Stefano Tessaro


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.

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

Available format(s)
Publication info
A minor revision of an IACR publication in EUROCRYPT 2018
known-key securitypseudorandomnesspsPRPscorrelation-intractabilitylimited independence
Contact author(s)
pratik_soni @ cs ucsb edu
2018-02-07: received
Short URL
Creative Commons Attribution


      author = {Pratik Soni and Stefano Tessaro},
      title = {Naor-Reingold Goes Public: The Complexity of Known-key Security},
      howpublished = {Cryptology ePrint Archive, Paper 2018/137},
      year = {2018},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.