Authentication system and device including physical unclonable function and threshold cryptography
An authentication system and device including physical unclonable function (PUF) and threshold cryptography comprising: a PUF device having a PUF input and a PUF output and constructed to generate, in response to the input of a challenge, an output value characteristic to the PUF and the challenge; and a processor having a processor input that is connected to the PUF output, and having a processor output connected to the PUF input, the processor configured to: control the issuance of challenges to the PUF input via the processor output, receive output from the PUF output, combine multiple received PUF output values each corresponding to a share of a private key or secret, and perform threshold cryptographic operations. The system and device may be configured so that shares are refreshable, and may be configured to perform staggered share refreshing.
1. An authenticatable device for use with an authentication system, comprising:
a physically-unclonable function (“PUF”) device, internal to the authenticatable device, having a PUF input and a PUF output and constructed to generate, in response to receipt of a challenge at the PUF input, an output value at the PUF output that is characteristic to the PUF device and the challenge; and
a processor, internal to the authenticatable device, connected to the PUF device, the processor configured to, internal to the authenticatable device:
control issuance of and communicate challenges to the PUF device;
receive, in response to issuance of challenges to the PUF device, multiple output values from the PUF device corresponding to multiple shares of a secret;
internal to the authenticatable device, generate threshold output values from threshold cryptographic operations on respective shares of the secret, wherein the threshold output values obscure the respective shares during reconstruction; and
internal to the authenticatable device, combine at least two of the threshold output values of the threshold cryptographic operations to enable execution of a cryptographic operation.
2. The authenticatable device of claim 1 , wherein the processor is further configured to perform at least one of LaGrange polynomial interpolation, elliptic curve cryptography, a zero knowledge proof authentication protocol, or distributed key generation.
3. The authenticatable device of claim 1 , wherein the processor is further configured to perform a share refresh procedure to refresh shares of the secret.
4. The authenticatable device of claim 1 , wherein the processor is further configured to perform the threshold cryptographic operations obscuring the shares of the secret, and prevent regeneration of the secret in memory.
5. The authenticatable device of claim 3 , wherein the processor is further configured to divide the share refresh procedure into a preparation phase and an application phase.
6. The authenticatable device of claim 5 , wherein the processor is further configured to, as part of the preparation phase of the share refresh procedure, generate share update information, and, as part of the application phase, apply the share update information to one or more shares.
7. The authenticatable device of claim 6 , wherein the processor is further configured to:
perform the preparation and application phases such that only one share refresh procedure is performed at a time; and
prevent regeneration of the secret in memory.
8. The authenticable device of claim 1 , wherein the processor and the PUF device are further configured to enable execution of the cryptographic operation without generating the secret in memory.
9. The authenticable device of claim 1 , wherein the processor is configured to sequentially operate on one PUF output value and respective helper value in memory at a time.
10. The authenticable device of claim 3 , wherein the processor is further configured to perform, as part of the refresh procedure, at least one of:
removing at least one share of the multiple shares of the secret, or
adding at least one new share of the secret to the multiple shares of the threshold sharing.
11. A computer-implemented method for authenticating a device, the method comprising:
internal to the device:
issuing and communicating multiple challenges;
generating, in response to receiving at least one challenge of the multiple challenges, an output value that is characteristic to physical properties of a hardware based identity component and at least one challenge of the multiple challenges;
receiving, in response to the issuing, output values corresponding to multiple shares of a secret;
internal to the device, generating threshold output values from threshold cryptographic operations on respective shares of the secret, wherein the threshold output values obscure the respective shares during reconstruction; and
internal to the authenticatable device, combining at least two of the threshold output values of the threshold cryptographic operations to enable execution of a cryptographic operation.
12. The method of claim 11 , further comprising performing at least one of LaGrange polynomial interpolation, elliptic curve cryptography, a zero knowledge proof authentication protocol, and distributed key generation.
13. The method of claim 11 , further comprising performing a share refresh procedure to refresh shares of the secret.
14. The method of claim 13 , wherein performing the share refresh procedure includes executing a preparation phase and an application phase.
15. The method of claim 14 , wherein executing the preparation phase includes generating share update information, and executing the application phase includes applying the share update information to one or more shares.
16. The method of claim 15 , wherein executing the preparation and application phases includes performing the share refresh procedure for only one share at a time.
17. The method of claim 11 , further comprising performing the threshold cryptographic operations and the cryptographic operation without generating the secret in memory.
18. The method of claim 11 , further comprising limiting operation to have only one of the output values received from the identity component in memory at a time.
19. The method of claim 13 , wherein the act of performing the share refresh procedure further comprises at least one of:
removing at least one share of the multiple shares of the secret, and
adding at least one share to the multiple shares of the secret.
20. An authenticatable device comprising:
means for generating, internal to the authenticatable device, in response to receiving a challenge, an output that is characteristic to physical properties of a hardware identity circuit and the received challenge;
a processor configured to, internal to the authenticatable device:
issue and communicate multiple challenges to the means for generating the output;
receive multiple output values corresponding to multiple shares of a secret;
internal to the authenticatable device, generate threshold output values from threshold cryptographic operations on respective shares of the secret, wherein the threshold output values obscure the respective shares during reconstruction; and
internal to the authenticatable device, combine at least two of the threshold output values of the threshold cryptographic operations to enable execution of a cryptographic operation.