A table key capable of decrypting a first table from a plurality of encrypted tables may be received. Each of the encrypted tables may include at least one pair of values corresponding to a challenge value and a response value. A request to authenticate a secondary device may be received and in response to the request to authenticate the secondary device, a challenge value obtained by using the table key to decrypt an entry in the first table may be transmitted to the secondary device. A second challenge value may be transmitted to the secondary device and a cryptographic proof may be received from the secondary device. The validity of the cryptographic proof received from the secondary device may be authenticated based on the second challenge value and the response value obtained by using the table key to decrypt the entry in the first table.