Q:

Is it possible to have authentication without state

In order to login to most websites you need a username and password which is often stored in a SQL database.   You are storing per-user information that can change,  this is state.  Can you prove that someone has the rights to access your system,  such as an administrator or a user,  without the need to store per-user state?

A:

To some extent, you can offload state on the clients. You encode the access rights of a user into a blob to which you add a MAC computed with a server secret key. The blob-with-MAC is then sent to the client. Later on, the client comes back and shows the blob; the server verifies the MAC and thus makes sure that the blob is legitimate. This maps reasonably well on HTTP cookies. Possibly, the blob could contain some encrypted data (there again with a server-only symmetric key) if the server wants to store some user-related data without making it visible to the user.
Trouble begins when you want to revoke or change rights. You cannot prevent a client from showing a stale blob. This can be coped with by using a combination of expiration dates (the blob contains a date and is valid for, e.g., one week) and, if need be, revocation lists (the server knows a list of blobs that it must reject, even if their MAC looks good -- this is state, but not much because the wide majority of access rights do not get revoked).
If the entity issuing the access rights (the one which creates the blob) and the entity verifying the access rights (the one which verifies the MAC) are not the same, then you need to replace the MAC with a digital signature scheme.

