Zero-knowledge based authentication method, system, and apparatus

A method for a device to authenticate itself to a host, wherein the device has stored data and a stored key and a stored device identification, the method comprising the acts of:

• receiving from the host an authentication request including selection parameters over a communications link;
• responsive to the request, transmitting a response to the host, the response including the stored device identification and a computed value,
• wherein the stored device identification includes a batch identification and a key identification,
• the batch identification identifies a data batch stored in a memory of the host and assigned uniquely to the remote device, and the key identification identifies a key stored in the memory and assigned uniquely to the device,
• the data batch stored in the memory of the host corresponds to the stored data, and
• the key stored in the memory corresponds to the stored key;
• wherein the device computes the compound value as a message authentication code of the selection parameters and the stored data keyed by the stored key, including the data batch and the key.

A device which authenticates itself to a host, the device comprising:

• a port adapted to receive data from the host;
• a computer readable medium which stores data and a key and a device identification;
• wherein the port receives from the host over a communications link an authentication request including selection parameters;
• a processor coupled to the port and to the computer readable medium and which, responsive to the request, transmits a response to the host via the port, the response including the device identification and a computed value
• wherein the device identification includes a batch identification and a key identification,
• the batch identification identifies a data batch stored in a memory of the host and assigned uniquely to the device, and the key identification identifies a key stored in the memory and assigned uniquely to the device,
• the data batch stored in the memory of the host corresponds to the stored data, and
• the key stored in the memory corresponds to the stored key;
• wherein the processor computes the computed value as a message authentication code of the selection parameters and the stored data keyed by the stored key.

A host apparatus which authenticates a device, the host apparatus comprising:

• a port adapted to couple to a communications link to transmit data to the device;
• a computer readable medium which stores data and a plurality of keys and associated device identifications;
• a processor coupled to the computer readable medium and to the port and which transmits to the device via the port an authentication request including selection parameters over a communications link;
• wherein the processor, responsive to the request, receives via the port a device identification and a received digest value,
• wherein the device identification includes a batch identification and a key identification,
• the batch identification identifies a data batch in the stored data, the data batch assigned uniquely to the device, and the key identification identifies a key from the stored plurality of keys, the identified key assigned uniquely to the device;
• wherein the processor verifies the received batch identification and key identification and is verified computes a message authentication code of the selection parameters and the data batch keyed by the identified and authenticates the device if the received digest value matches the computed message authentication code.

A method of authenticating a device to a host, each having stored data with an associated batch identification and a stored key with an associated key identification, the method comprising:

• generating selection parameters at the host;
• sending an authentication request including the selection parameters to the remote device over a communications link;
• at the device, responsive to the authentication request, transmitting a response to the host over the communications link, the response including the batch identification and key identification and a value computed as a message authentication code of the selection parameters and the stored data keyed by the key,
• wherein the batch identification identifies a data batch in the stored data, the data batch assigned uniquely to the device, and the key identification identifies a key in the stored data, the identified key assigned uniquely to the device;
• receiving the response host;
• verifying the batch identification and the key identification;
• and
• authenticating the remote device by computing the message authentication code of the Selection parameters and the data batch keyed by the identified key stored at the host.