Paper 2025/1423

Collusion-Safe Proxy Re-Encryption

Abstract

Proxy re-encryption is a cryptographic scheme enabling a delegator (user $i$) to delegate its decryption right to a valid delegatee (user $j$) through a proxy, who cannot extract any information about the message during the procedure. An important security notion is the security against collusion between the proxy and the delegatee. In this case, the adversary has the secret key of the delegatee, $\mathsf{sk}_j$, and the re-encryption key, $\mathsf{rk}_{i\to j}$. The master secret security is first formalised by Ateniese et al. (NDSS'05) to capture the secrecy of $i$'s secret key during collusion. This notion was further formalised by Zhou et al. (ASIACRYPT'23) as the indistinguishability of re-encrypted ciphertext against chosen-message attacks, called collusion safety, which implies the master secret security. In this paper, we find that a PRE scheme is not master secret secure as they claimed, and many other schemes were not master secret secure. Then, we propose a generic construction to achieve collusion safety at the cost of doubling the key size from the IND-CPA secure PRE, enjoying a much better generality and efficiency than the existing technique by secret sharing.

Note: In the earlier pre-proceedings version of this work, the level-2 encryption algorithm $\mathsf{Enc}'(2,\cdot,\cdot)$ directly invoked the underlying $\mathsf{Enc}$. We modified this to use a temporary key pair and re-encryption. This adjustment ensures that the generated ciphertext distribution matches the simulator's distribution in our reduction, thereby closing a simulation gap in the security proof for collusion safety without requiring any additional assumptions (re-encryption simulatability).