Paper 2019/608

Symmetric Primitives with Structured Secrets

Navid Alamati, Hart Montgomery, and Sikhar Patranabis

Abstract

Securely managing encrypted data on an untrusted party is a challenging problem that has motivated the study of a variety of cryptographic primitives. A special class of such primitives allows an untrusted party to transform a ciphertext encrypted under one key to a ciphertext under another key, using some auxiliary information that does not leak the underlying data. Prominent examples of such primitives in the symmetric-key setting are key-homomorphic PRFs, updatable encryption, and proxy re-encryption. Although these primitives differ significantly in terms of their constructions and security requirements, they share two important properties: (a) they have secrets with structure or extra functionality, and (b) all known constructions of these primitives satisfying reasonably strong definitions of security are based on concrete public-key assumptions, e.g., DDH and LWE. This raises the question of whether these objects inherently belong to the world of public-key primitives, or they can potentially be built from simple symmetric-key objects such as pseudorandom functions. In this work, we show that the latter possibility is unlikely. More specifically, we show that: • Any (bounded) key-homomorphic weak PRF with an abelian output group implies a (bounded) input-homomorphic weak PRF, which has recently been shown to imply not only public-key encryption (PKE), but also a variety of primitives such as PIR, lossy TDFs, and even IBE. • Any ciphertext-independent updatable encryption scheme that is forward and post-compromise secure implies PKE. Moreover, any symmetric-key proxy re-encryption scheme with reasonably strong security guarantees implies a forward and post-compromise secure ciphertext-independent updatable encryption, and hence PKE. In addition, we show that unbounded (or exact) key-homomorphic weak PRFs over abelian groups are impossible in the quantum world. In other words, over abelian groups, bounded key-homomorphism is the best that we can hope for in terms of post-quantum security. Our attack also works over other structured primitives with abelian groups and exact homomorphisms, including homomorphic one-way functions and input-homomorphic weak PRFs.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
A minor revision of an IACR publication in CRYPTO 2019
Contact author(s)
alamati @ umich edu
History
2019-08-12: revised
2019-06-02: received
See all versions
Short URL
https://ia.cr/2019/608
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2019/608,
      author = {Navid Alamati and Hart Montgomery and Sikhar Patranabis},
      title = {Symmetric Primitives with Structured Secrets},
      howpublished = {Cryptology ePrint Archive, Paper 2019/608},
      year = {2019},
      note = {\url{https://eprint.iacr.org/2019/608}},
      url = {https://eprint.iacr.org/2019/608}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.