Paper 2018/840

Universal Proxy Re-Encryption

Nico Döttling and Ryo Nishimaki

Abstract

We put forward the notion of universal proxy re-encryption (UPRE). A UPRE scheme enables us to convert a ciphertext under a (delegator) public key of any existing public-key encryption (PKE) scheme into another ciphertext under a (delegatee) public key of any existing PKE scheme (possibly different from the delegator one). Such a conversion is executed by a third party called proxy that has a re-encryption key generated from the delegator's secret key and the delegatee public key. Proxy re-encryption is a related notion, but it can neither convert ciphertexts into ones of possibly different PKE schemes nor treat general PKE schemes. Our contributions are twofold. One is a definitional work. We define the syntax and security of UPRE. The other is showing the feasibility of UPRE. More precisely, we present three generic constructions of UPRE. One is a UPRE based on probabilistic indistinguishability obfuscation (PIO). It can re-encrypt ciphertexts polynomially many times. Another is a relaxed variant of UPRE based on function secret sharing (FSS). It can re-encryption ciphertexts constant times. The relaxed variant means that decryption algorithms for re-encrypted ciphertext are slightly modified though we use only original delegatee secret keys for decryption. The other is the relaxed variant of UPRE based on oblivious transfer and garbled circuits. It can re-encryption ciphertexts polynomially many times. The supported PKE schemes by the first and second generic constructions vary in the underlying hard problems or cryptographic tools. The third generic construction supports any CPA-secure PKE. The security levels of our UPRE schemes vary in the underlying hard problems or cryptographic tools that they rely on.

Note: correcting typos.