International Association
for Cryptologic Research

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 a strong multi-challenge setting, with a tight security reduction. Our multi-challenge setting allows the adversary to obtain multiple challenge ciphertexts for multiple target users, which models a more realistic and powerful adversary. In contrast, prior works established adaptive security only in the weaker single-challenge setting, where the adversary is limited to a single challenge query. Moreover, these schemes suffer from significant security losses of n^{O(log n)} 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 the security is proven 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.