Stateless user-generated one-time passwords I've been working on my course project lately and got stuck with the problem which I reduced to the following abstract protocol:


Alice generates an ID key and gives it to Bob.
Bob generates some random data, combines it with that ID key to produce a token and sends it back to Alice. It is essential that data is random, i.e. Bob does not maintain any state.
Alice verifies that token is generated by Bob and also is able to tell whether it was used before. This can obviously be achived by keeping all previous tokens in a database, but if we are talking about passwords for example, it would be great to maintain as little state as possible.


The idea behind these requirements is that existing one-time password schemes require either interaction with the service (challenge-based OTPs) or maintaining some state (TOTP, HOTP, etc). What I would like to do is, basically, to generate a new password for every session, be able to generate those passwords upfront and be sure that once used, password can never be used again. 

Is there any one-time password scheme that would satisfy these requirements?
What you are asking for is demonstratively impossible.

Say you only have some initial shared state, for instance a shared secret key and some values. Now you are asking to disallow a previously used authentication; however without additional state, there is no way that you can even detect that a previous authentication has happened.

So you need some kind of state, even if it is just a simple counter, for instance to identify which one-time-passwords have been used.