I am currently working on a REST API for my Web Service. Every user who is registered, must have an individual access token for the API, but how can I generate one, without checking every token if it is the same as the new token?
[Not important]
Is that a good or bad idea when I will use a REST API so that I can use a web interface, desktop app, Android app, ...? But it won't be a "public feature"! Possibly later.
If it were up to me, I'd issue incrementing numbers as user IDs. Then I'd use something like 256-bit AES to encrypt that user ID.
Then I'd probably have the user include a JSON web token containing both their user ID and their access token--the encrypted ID.
To verify their web token, you encrypt their user ID and check whether it matches the access token (or you decrypt the access token and check that it matches the user ID).
As long as you create a truly random encryption key, and keep it secret your security should depend only on the security of the underlying encryption algorithm.
The main weakness here is that the value involved is a fixed web token, so if somebody else "sniffs" a user's packets, they can use a playback attack--that is, they can validate their requests using the same key as the real user. There are ways to prevent that, but (unless you use mostly pre-built "stuff" to implement it) they get rather more complex.
Probably the simplest of the "enhanced" protocols would be to use not only the user ID, but (for example) a session ID and a packet ID (both of which also increment), concatenate the three together and encrypt that. Then each packet will have a unique encrypted value to verify.