It is not fundamentally impossible. It has been shown [1] that forward-secure public-key encryption can be done without the key size blowing up with the expecte

It is not fundamentally impossible. It has been shown [1] that forward-secure public-key encryption can be done without the key size blowing up with the expected number of encrypted messages, though it's not very practical. The trivial case of §3.2, in which the key is simply a tuple of N keys which are erased as messages are encrypted/decrypted, seems similar to what TextSecure does. [1] https://eprint.iacr.org/2003/083 https://eprint.iacr.org/2003/083