Cryptology ePrint Archive: Report 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 consist of three parts. One is a definitional work. We define the syntax and security of UPRE. Another is showing the (im)possibility of UPRE. We prove that the existence of UPRE implies the existence of average-case virtual black-box obfuscation for all re-encryption circuits. The other is presenting general constructions of UPRE schemes. More precisely, we present three UPRE schemes. One is a UPRE based on probabilistic indistinguishability obfuscation (PIO). It can re-encrypt ciphertexts polynomially many times. To circumvent our impossibility result, we define a notion of relaxed UPRE and show that it can be constructed from garbled circuits (GCs). It can re-encrypt ciphertexts polynomially many 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. Our second construction of relaxed UPRE based on GCs satisfies a stronger security requirement. It can re-encrypt ciphertexts a constant number of times.

Category / Keywords: public-key cryptography / universal proxy re-encryption, proxy re-encryption, public-key encryption, secret sharing

Date: received 7 Sep 2018, last revised 8 Feb 2019

Contact author: ryo nishimaki at gmail com,nico doettling@gmail com

Available format(s): PDF | BibTeX Citation

Note: Added a negative result on universal proxy re-encryption, improved relaxed universal proxy re-encryption schemes based on garbled circuits (removed OT assumption), removed function secret sharing based scheme (since obsolete). (2019/2/8)

Version: 20190208:104359 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]