Tightly, Adaptively Secure Proxy Re-encryption in Multi-challenge Setting

Proxy Re-Encryption (PRE) enables a proxy to transform ciphertexts encrypted under Alice’s key into ciphertexts under Bob’s key, allowing Bob to decrypt them. As a powerful cryptographic primitive, PRE has been extensively studied over the past two decades. However, an open problem remains unresolved, namely constructing an adaptively secure PRE scheme where the security reduction is tight. In this paper, we present the first PRE scheme that achieves adaptive security in multi-challenge setting, with a tight security reduction, i.e., constant security loss O(1). In our setting, the adversary can obtain multiple challenge ciphertexts for multiple target users, capturing a more realistic and powerful adversary. In contrast, previous works established adaptive security only under the single-challenge setting, where the adversary is restricted to a single challenge query, and such schemes incur security losses of n^O(logn) for trees and chains, and n^O(n) for general graphs, where n is the number of users. Our construction is based on composite-order bilinear groups, and we prove the security in the standard model. The results indicate that our security guarantees do not degrade with respect to either the number of users or the number of ciphertexts, thanks to the tight reduction.