Paper 2017/410

Fast Proxy Re-Encryption for Publish/Subscribe Systems

Yuriy Polyakov, Kurt Rohloff, Gyana Sahu, and Vinod Vaikuntanthan


We develop two IND-CPA-secure multi-hop unidirectional Proxy Re-Encryption (PRE) schemes by applying the Ring-LWE (RLWE) key switching approach from the homomorphic encryption literature. Unidirectional PRE is ideal for secure publish-subscribe operations where a publisher encrypts information using a public key without knowing upfront who the subscriber will be and what private key will be used for decryption. The proposed PRE schemes provide a multi-hop capability, meaning that when PRE-encrypted information is published onto a PRE-enabled server, the server can either delegate access to specific clients or enable other servers the right to delegate access. Our first scheme (which we call NTRU-ABD-PRE) is based on a variant of the NTRU-RLWE homomorphic encryption scheme. Our second and main PRE scheme (which we call BV-PRE) is built on top of the Brakerski-Vaikuntanathan (BV) homomorphic encryption scheme and relies solely on the RLWE assumption. We present an open-source C++ implementation of both schemes and discuss several algorithmic and software optimizations. We examine parameter selection tradeoffs in the context of security, runtime/latency, throughput, ciphertext expansion, memory usage, and multi-hop capabilities. Our experimental analysis demonstrates that BV-PRE outperforms NTRU-ABD-PRE both in single-hop and multi-hop settings. The BV-PRE scheme has a lower time and space complexity than existing IND-CPA-secure lattice-based PRE schemes, and requires small concrete parameters, making the scheme computationally efficient for use on low-resource embedded systems while still providing 100 bits of security. We present practical recommendations for applying the PRE schemes to several use cases of ad-hoc information sharing for publish-subscribe operations.

Note: Fixing some typos and references

Available format(s)
Publication info
Published elsewhere. ACM TOPS 2017
lattice cryptopublic-key cryptographyproxy re-encryption
Contact author(s)
polyakov @ njit edu
2017-09-06: last of 4 revisions
2017-05-13: received
See all versions
Short URL
Creative Commons Attribution


      author = {Yuriy Polyakov and Kurt Rohloff and Gyana Sahu and Vinod Vaikuntanthan},
      title = {Fast Proxy Re-Encryption for Publish/Subscribe Systems},
      howpublished = {Cryptology ePrint Archive, Paper 2017/410},
      year = {2017},
      doi = {10.1145/3128607},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.