I am very inexperienced with cryptography and would like some advice on how to store some sensitive information on client machines.

I have some information stored in a central database on my server. A snapshot of this database is distributed along with my application. Every time the application is opened on the client, it checks for any new information on the server and downloads it via a web service. We need the information to be protected at all times, even when stored on the client. The only time it should be decrypted is while it is in memory and being used by the application.

I realize that the nature of our application means that no matter how strong our encryption scheme is, someone could still access our data by examining their machine's memory after the data has been decrypted. However, we have decided that we are OK with that scenario unless there is some magical way of dealing with this problem that I don't know about. We don't need absolute security for this data. We basically just need to raise the difficulty enough to deter most people from tinkering with it.

It seems to me that using a symmetric key is probably the best approach for this scenario. My concern is that if someone figures out the key, we'll have no way of knowing it. Even if we did manage to find out, it would be extremely difficult for us to change it since we would have so many clients using the old key. The natural way of solving this problem is to periodically change the key, but then how do we securely deliver the new key to our existing clients?

It is also worth noting that the user of the application doesn't know about this data and doesn't care about it. We can't ask for a password, require them to have a network connection, or impose any other limitations on them.

Looking forward to your thoughts on this. :)