Authentication System
A device authentication system for use with an authenticatable device having a physically-unclonable function and constructed to, in response to input of challenge C, internally generate an output O characteristic to the PUF and the challenge C, and configured to: i) upon receiving challenge C, generate a corresponding commitment value that depends upon a private value r, and ii) upon receiving an authentication query that includes the challenge C and a nonce, return a zero knowledge proof authentication value that corresponds to the commitment value. The system comprises an enrollment server having a working verification set that includes challenge C and corresponding commitment value, wherein: a) the enrollment server is configured to generate an authentication token that corresponds to the authentication value and includes a blinded value depending upon the private value r and a random value decryptable by the authenticatable device; and/or b) the system is configured to pre-process and convey data to the authenticatable device as part of an extended Boyko-Peinado-Venkatesan generation.
1 - 33 . (canceled)
34 . An authentication system for use with an authenticatable device constructed so as to, in response to the input of a specific challenge C, internally generate an output O that is characteristic to the device and the specific challenge C, and configured to: i) upon receiving the specific challenge C, generate a corresponding commitment value that depends upon the output O and a private value r, and ii) upon receiving an authentication query that includes the specific challenge C and a nonce, return a zero knowledge proof authentication value that corresponds to the commitment value; the authentication system comprising an enrollment server that:
a) has a working verification set that includes the specific challenge C and the authenticatable device's corresponding commitment value; and
b) is configured to generate an authentication token that:
i) includes a blinded value that depends upon the private value r and a random value that can be decrypted by the authenticatable device; and
ii) corresponds to the zero knowledge proof authentication value.
35 . The authentication system of claim 34 , wherein the enrollment server is configured to generate the random value.
36 . The authentication system of claim 34 , wherein the enrollment server is configured to encrypt the random value with a key that is shared with the authenticatable device.
37 . The authentication system of claim 34 , wherein the commitment value is an exponential function of the private value r.
38 . The authentication system of claim 34 , wherein the blinded value depends exponentially upon the private value r multiplied by the random value.
39 . The authentication system of claim 34 , wherein the commitment value is an exponential function of the private value r and wherein the blinded value depends exponentially upon the private value r multiplied by the random value.
40 . The authentication system of claim 34 , wherein the random value is an element of a group of prime order.
41 . The authentication system of claim 34 , wherein the enrollment server is configured to generate a limited verification set that includes the specific challenge C and authentication token.
42 . The authentication system of claim 41 , wherein the limited verification set further includes an error-correction helper string, and the dependency of the commitment value upon the output O consists of a dependency upon the error-correction helper string.
43 . The authentication system of claim 41 , further comprising an authentication server having the limited verification set.
44 . The authentication system of claim 41 , further comprising a plurality of authentication servers each having a different limited verification set, wherein each limited verification set includes the specific challenge C and a corresponding token that is specific to the particular authentication server.
45 . The authentication system of claim 34 , wherein the enrollment server has a complete verification set that includes multiple different specific challenge values and the authenticatable device's corresponding commitment values.
46 . The authentication system of claim 34 , wherein the enrollment server possesses challenge values and corresponding commitment values for multiple authenticatable devices.
47 . The authentication system of claim 34 , wherein the output O of the authenticatable device which the system is for use with is generated by a physically-unclonable function (‘PUF’) in the authenticatable device.
48 . The authentication system of claim 47 , wherein the PUF of the authenticatable device which the system is for use with is a strong PUF.
49 . The authentication system of claim 47 , wherein the PUF of the authenticatable device which the system is for use with resides in a field-programmable gate array.
50 . The authentication system of claim 34 , further comprising an authenticatable device having a physically-unclonable function (‘PUF’) capable of generating the output O.
51 . The authentication system of claim 50 , wherein the PUF resides in a field-programmable gate array.
52 . The authentication system of claim 34 , wherein the system is further configured to perform operations as part of an extended Boyko-Peinado-Venkatesan generation.
53 . An authentication system for use with an authenticatable device constructed so as to, in response to the input of a specific challenge C, internally generate an output O that is characteristic to the device and the specific challenge C, and configured to: i) upon receiving the specific challenge C, generate a corresponding commitment value that depends upon the output O and a private value r, and ii) upon receiving an authentication query that includes the specific challenge C and a nonce, return a zero knowledge proof authentication value that corresponds to the commitment value; wherein the authentication system:
a) includes an enrollment server that has a working verification set including the specific challenge C and the authenticatable device's corresponding commitment value; and
b) is configured to pre-process and convey data to the authenticatable device as part of an extended Boyko-Peinado-Venkatesan generation.
54 . The authentication system of claim 53 , wherein the data includes exponents for a prime group.
55 . The authentication system of claim 54 , wherein the data includes a group generator.
56 . The authentication system of claim 53 , wherein the data includes an error-correction helper string, and wherein the dependency of the commitment value upon the output O consists of a dependency upon the error-correction helper string.
57 . The authentication system of claim 53 , further comprising an authentication server.
58 . The authentication system of claim 53 , wherein the enrollment server is configured to pre-process and convey data to the authenticatable device as part of an extended Boyko-Peinado-Venkatesan generation.
59 . The authentication system of claim 58 , wherein the data includes exponents for a prime group, and a group generator.
60 . The authentication system of claim 53 , wherein the output O of the authenticatable device which the system is for use with is generated by a physically-unclonable function (‘PUF’) in the authenticatable device.
61 . An authenticatable device for use with an authentication system, comprising:
a) an internal input and an internal output constructed so as to, in response to the internal input of a specific challenge C, generate an internal output O that is characteristic to the device and the specific challenge C;
b) a processor having a processor input that is connected to the internal output, the processor configured to:
i) in response to the receipt of an output O from the internal output, generate a commitment value that depends upon the output O and a private value r; and
ii) in response to the contemporaneous receipt of an authentication query that includes a nonce and of an output O from the internal output, return a zero knowledge proof authentication value that corresponds to the commitment value;
wherein the zero knowledge proof authentication value further corresponds to an authentication token that includes a blinded value that depends upon the private value r and a random value, and wherein the processor is configured to decrypt the random value.
62 . The authenticatable device of claim 61 , further comprising a physically-unclonable function (‘PUF’) having a PUF input and a PUF output, wherein the PUF input is the internal input and the PUF output is the internal output, and wherein the output O is characteristic to the PUF.
63 . The authenticatable device of claim 62 , wherein the dependency of the commitment value upon the output O consists of a dependency upon an error-correction helper string.
64 . The authenticatable device of claim 61 , wherein the PUF is a strong PUF.
65 . The authenticatable device of claim 61 , further comprising a field-programmable gate array (‘FPGA’), wherein the PUF resides in the FPGA.
66 . The authenticatable device of claim 65 , wherein the FPGA is part of a Spartan®-6 FPGA SP605 development board.