A one-time password (OTP) based security scheme is described, where a provider pre-generates a number of verification codes (e.g., OTP codes) which will be valid for a predetermined interval. The provider then encodes the verification codes (e.g., by hashing each code with a time value), and stores the verification codes into a data structure. The data structure can be provided to a verification system that can use the set of pre-generated OTP codes to authenticate requests received from users having personal security tokens.