I need to keep sensitive data in a de fact public place (i.e. with a user, e.g. in a cookie) and only there (no copy or hash of that data should be kept on the server).
The data was encrypted AES/CBC and the private AES key is kept secret on the server (the kind and safety of this key should not be a concern here, let's say it is beyond doubt).
To make use of the data the user sends the encrypted data to the server, which decrypts it with the private key.
So far so good, but here is my question: I need to ensure the integrity of the data (i.e. make sure the user did not temper with the data).
What are my options to ensure the integrity?
Constraint: ideally I would not have to store any derivate of the encrypted data on the server, not even its HMAC hash.