Authentication system and device including physical unclonable function and threshold cryptography

Patent metadata

Field	Value
Publication number	US-9946858-B2
Application number	US-201514746054-A
Country	US
Kind code	B2
Filing date	Jun 22, 2015
Priority date	May 5, 2014
Publication date	Apr 17, 2018
Grant date	Apr 17, 2018

Abstract

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.

First claim

What is claimed is:

1. An authenticatable device for use with an authentication system for processing arbitrary cryptographic operations on auxiliary data communicated to the device, comprising:
one or more physical unclonable function (‘PUF’) devices internal to the authenticatable device; and
at least one processor internal to the authenticable device and operatively connected to the one or more PUF devices, wherein the at least one processor is configured to:
issue a first challenge to a first PUF device of the one or more PUF devices and receive a first output value from the first PUF device in response to issuing the first challenge;
recover, internal to the authenticatable device, a first share of a private key or secret encoded with the one or more PUFs, wherein the first share is mapped to the first output value;
perform a first threshold cryptographic operation with the first share and the auxiliary data;
issue a second challenge to the first PUF device or a second PUF device of the one or more PUF devices having a mapping to a second share and receive a second output value mapped to the second share in response to issuing the second challenge;
recover, internal to the authenticatable device, a second share of the private key or secret, encoded with the one or more PUFs, the second share different from the first share and mapped to the second output value;
perform a second threshold cryptographic operation with the second share and the auxiliary data; and
enable processing of the arbitrary cryptographic operation with a combined output of at least the first and second threshold cryptographic operations.

2. The authenticatable device of claim 1 , wherein the authenticatable device comprises more than one PUF device internal to the authenticatable device.

3. The authenticatable device of claim 2 , wherein the at least one processor comprises more than one logical core.

4. The authenticatable device of claim 1 , wherein the at least one processor is further configured to perform a share refresh procedure to refresh shares of the private key or secret.

5. The authenticatable device of claim 4 , wherein the at least one 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 at least one processor is further configured to perform a preparation phase that comprises generating share update information, and to perform an application phase that comprises applying the share update information to one or more shares.

7. The authenticatable device of claim 6 , wherein the at least one processor is further configured to perform the preparation and application phases such that only one share refresh procedure is performed at once.

8. The authenticatable device of claim 7 , wherein the authenticatable device includes a reconfigurable PUF device.

9. The authenticatable device of claim 1 , wherein the at least one processor is further configured to combine multiple internal cryptographic operations to yield a cryptographic output.

10. The authenticatable device of claim 1 , wherein the at least one processor is further configured to perform a zero knowledge proof authentication protocol.

11. The authenticatable device of claim 1 , wherein the at least one processor is further configured to perform distributed key generation.

12. The authenticatable device of claim 1 , wherein the at least one processor comprises more than one logical core, and the at least one processor is configured so that a first one of the more than one logical core can issue a challenge, recover a share, and perform a cryptographic operation in parallel with a second one of the more than one logical core.

13. The authenticatable device of claim 1 , wherein the at least one processor is further configured to combine cryptographic operations on the first and the second shares without generating the private key or secret in memory.

14. The authenticatable device of claim 1 , wherein the first share recovered is associated with the output received from the first PUF device based on at least a respective helper value.

15. The authenticatable device of claim 14 , wherein the helper value is stored on the authenticatable device.

16. The authenticatable device of claim 1 , wherein the at least one processor is configured to issue a different challenge for each challenge.

17. A computer implemented method of authenticating an authenticatable device for processing arbitrary cryptographic operations on auxiliary data communicated to the authenticatable device, the method comprising:
issuing, by at least one processor internal to the authenticatable device, a first challenge to a first PUF device operatively connected with the at least one processor;
receiving, by the at least one processor, a first output value from the first PUF device in response to issuing the first challenge;
recovering, internal to the authenticatable device by the at least one processor, a first share of a private key or secret encoded with the one or more PUFs, wherein the first share is mapped to the first output value;
performing a first threshold cryptographic operation with the first share;
issuing, by the at least one processor, a second challenge to the first PUF device or a second PUF device of the at least one PUF device having a mapping to a second share;
receiving, by the at least one processor, a second output value in response to issuing the second challenge;
recovering, internal to the authenticable device by the at least one processor, the second share of the private key or secret, encoded with the one or more PUFs, the second share different from the first share, and mapped to the second output value;
performing a second threshold cryptographic operation with the second share; and
enabling processing of the arbitrary cryptographic operation with a combined output of at least the first and second threshold cryptographic operations.

18. The method according to claim 17 , further comprising an act of enabling arbitrary operations to be performed without generating the private key or the secret in memory, wherein the act of enabling includes combining threshold cryptographic operations on the first and second shares.

19. The method according to claim 17 , further comprising an act of refreshing, by the at least one processor, shares of the private key or secret.

20. At least one non-transitory computer-readable storage medium containing processor-executable instructions that, when executed, perform a method for processing arbitrary cryptographic operations on auxiliary data communicated to an authenticatable device comprising:
issuing a first challenge to a first PUF device operatively connected to at least one processor internal to the authenticatable device;
receiving a first output value from the first PUF device in response to issuing the first challenge;
recovering, internal to the authenticatable device, a first share of a private key or secret encoded with the one or more PUFs, wherein the first share is mapped to the first output value;
performing a first threshold cryptographic operation with the first share;
issuing a second challenge to the first PUF device or a second PUF device of the at least one PUF device having a mapping to a second share;
receiving a second output value in response to issuing the second challenge;
recovering, internal to the authenticatable device, a second share of the private key or secret, different fro

Assignees

• Analog Devices Inc

Inventors

• Wallrabenstein John Ross

Classifications

• G06F2221/2129

  Authenticate client device independently of the user · CPC title

• G09C1/00 Primary

  Apparatus or methods whereby a given sequence of signs, e.g. an intelligible text, is transformed into an unintelligible sequence of signs by transposing the signs or groups of signs or by replacing them by others according to a predetermined system (cryptographic typewriters G09C3/00) · CPC title

• G06F21/31 Primary

  User authentication · CPC title

• H04L9/3278

  using physically unclonable functions [PUF] · CPC title

• H04L2209/12

  Details relating to cryptographic hardware or logic circuitry · CPC title