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 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(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 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.

We improve the first and the only existing prime-order fully adaptively secure decentralized Multi-Authority Attribute-Based Encryption (MA-ABE) scheme for NC1 in Datta-Komargodski-Waters [Eurocrypt '23]. Compared with Datta-Komargodski-Waters, our decentralized MA-ABE scheme extra enjoys shorter parameters and meanwhile supports many-use of attribute. Shorter parameters is always the goal for Attribute-Based Encryption (ABE), and many-use of attribute is a native property of decentralized MA-ABE for NC1. Our scheme relies on the Matrix Decision Diffie-Hellman (MDDH) assumption and is in the random oracle model, as Datta-Komargodski-Waters.