In practice, you do one of three things:

1. You encrypt and then authenticate data, such as user profile information, so that clients can neither read nor alter it. This doesn't involve public-key encryption.

2. You authenticate data, but don't encrypt it, because it isn't secret but must not be changed; this is what you'd do if the only semantic value being passed in your token as UUID, for instance.

3. You do neither of these things, and instead generate cryptographically random tokens of sufficient length that they can't be guessed, and then use those tokens as database lookup keys.

All three of these things are lightning fast on any decent processor, including the one on your phone.

You are very likely to cost yourself more security than you gain by trying to do anything more complicated than one of these three things. Again: don't ever use public-key crypto unless you really need it.

Thanks. Sounds like I need to do some more research on this. This isn't how I thought this was generally implemented by the big players, but I've not worked closely on auth either.

I guess for 2 and 3, you handle revocation by just deleting the relevant row or flagging a "revoked" column. For 1, add a unique id that you can add to a revocation list? Are there better/more typical ways to do this?

Revocation is a problem for encrypted tokens; it's a downside to the approach. The common solutions aren't particularly elegant.

A fourth option would be just like option 3, except you only use part of the DB token in the lookup and compare the remainder in constant-time if and only if the record exists (if you're worried about the database lookup leaking a valid authentication token).

Agreed that public key crypto isn't really appropriate here.