Authentication System

Abstract

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.