Communication-Efficient and Fine-Grained Forward-Secure Asynchronous Messaging

In recent years, motivated by the revelation of long-term and widespread surveillance of personal communications, extensive efforts have been putting into
store-and-forward
asynchronous messaging systems (e.g., email and SMS) for providing critical security guarantees. Of particular interest among them is forward security, which makes past messages remain secure in the event that the secret key gets exposed. Traditional forward-secure public key encryption can provide forward security for asynchronous scenarios, but it is not flexible enough for instant messaging systems. This is mainly because that, after updating his/her secret key, the user totally loses the decryption capacity of ciphertexts that have not been received. In this paper, to achieve practical forward-security of asynchronous messaging systems, we investigate the construction of a new primitive named forward-secure puncturable encryption (FSPE) that captures fine-grained forward security. Namely, the user can maintain the decryption capacity of those encrypted messages that have not been received yet. Meanwhile, even if the secret key is disclosed, those received messages can still remain secure. Specifically, we propose a communication-efficient FSPE scheme for achieving fine-grained forward-secure asynchronous messaging. Moreover, to improve the efficiency of asynchronous messaging built upon FSPE, we extend it to support outsourced decryption. We also implement the proposed scheme and evaluate a proof-of-concept of main algorithms, so as to increase confidence on its correctness and practicability.