Some quick notes: random tokens do rely, broadly speaking, on cryptography, as the token must be generated by a cryptographically strong (P)RNG.
Signing and encryption are conceptually different ideas, don't mix them as in the description of the stateless session cookie. There's a great old Matasano blog post in the style of a play about this...
A more complete consideration of authn techniques would include mutual certificate ("SSL") authn, as well as signed-request approaches not using a shared secret.