[DrJosiah]

> How slow would this be with thousands of emails on a mobile device ?

Not that much slower than email is now. A B+tree index of (for example) 1 gb of total content and index is only about 1-2 gigs in size. You could just store that shit on your phone encrypted. Or 1-5 megs of index on your phone, with 2 round-trips for any email/first page search result per word.

> What happens if this password got into the wrong hands or even lost? Is it possible to change? Must I re-encrypt every single email ?

Overall yes, re-encryption is necessary. But that can be a batch process done while your phone is charging and on wifi over night. Is a drawback, but re-keying always is. But just because you got to change the keys every once in a while, doesn't mean you toss the locks.

[deathanatos]

> Overall yes, re-encryption is necessary. But that can be a batch process done while your phone is charging and on wifi over night. Is a drawback, but re-keying always is. But just because you got to change the keys every once in a while, doesn't mean you toss the locks.

Encrypted hard disks utilize a simple scheme whereby the password/key derived from the password decrypts a small set of keys or single key that's just randomly generated, and decrypts the rest of the drive. So, to change the password, all you need to reencrypt are the real keys.

  Password -- decrypts --> master key -- decrypts --> rest of hard drive
                           ^^^^^^^^^^
                           this is what gets re-encrypted on password change
                           and is small; ~a few KiB

Similar could be had for email.

The approach above also lends itself well to supporting multiple passwords. (If you share an account w/ someone, for example, though email has other tools like mailing lists that might be better suited.)