This is where most cookie schemes wind up -- sending and retrieving HMACs.

I wrote my honours dissertation on an opt-in scheme that used cookies, HTTPS and javascript to track users visiting multiple websites.

What you have here is what I called "Protocol 1": the first elaboration of the naive protocol. An additional elaboration (Protocols 2 and 3) is to remove user identification from cookies entirely. Each cookie is regenerated on each HTTP request with a new ID and HMAC. This means that if a cookie is successfully harvested, its useful lifetime is limited.

There are more attacks after this. I got as far as Protocol 10; it transpires that Protocol 10 is broken anyhow. Depending on the sophistication of your attacker, there's no safe way to do what I was trying to do.