International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Paper: Adaptively Secure Proxy Re-encryption

Authors:
Georg Fuchsbauer
Chethan Kamath
Karen Klein
Krzysztof Pietrzak
Download:
DOI: 10.1007/978-3-030-17259-6_11
Search ePrint
Search Google
Conference: PKC 2019
Abstract: A proxy re-encryption (PRE) scheme is a public-key encryption scheme that allows the holder of a key pk to derive a re-encryption key for any other key $$pk'$$ . This re-encryption key lets anyone transform ciphertexts under pk into ciphertexts under $$pk'$$ without having to know the underlying message, while transformations from $$pk'$$ to pk should not be possible (unidirectional). Security is defined in a multi-user setting against an adversary that gets the users’ public keys and can ask for re-encryption keys and can corrupt users by requesting their secret keys. Any ciphertext that the adversary cannot trivially decrypt given the obtained secret and re-encryption keys should be secure.All existing security proofs for PRE only show selective security, where the adversary must first declare the users it wants to corrupt. This can be lifted to more meaningful adaptive security by guessing the set of corrupted users among the n users, which loses a factor exponential in , rendering the result meaningless already for moderate .Jafargholi et al. (CRYPTO’17) proposed a framework that in some cases allows to give adaptive security proofs for schemes which were previously only known to be selectively secure, while avoiding the exponential loss that results from guessing the adaptive choices made by an adversary. We apply their framework to PREs that satisfy some natural additional properties. Concretely, we give a more fine-grained reduction for several unidirectional PREs, proving adaptive security at a much smaller loss. The loss depends on the graph of users whose edges represent the re-encryption keys queried by the adversary. For trees and chains the loss is quasi-polynomial in the size and for general graphs it is exponential in their depth and indegree (instead of their size as for previous reductions). Fortunately, trees and low-depth graphs cover many, if not most, interesting applications.Our results apply e.g. to the bilinear-map based PRE schemes by Ateniese et al. (NDSS’05 and CT-RSA’09), Gentry’s FHE-based scheme (STOC’09) and the LWE-based scheme by Chandran et al. (PKC’14).
BibTeX
@inproceedings{pkc-2019-29305,
  title={Adaptively Secure Proxy Re-encryption},
  booktitle={Public-Key Cryptography – PKC 2019},
  series={Lecture Notes in Computer Science},
  publisher={Springer},
  volume={11443},
  pages={317-346},
  doi={10.1007/978-3-030-17259-6_11},
  author={Georg Fuchsbauer and Chethan Kamath and Karen Klein and Krzysztof Pietrzak},
  year=2019
}