Efficient delay-based PUF implementation using optimal racing strategy

Patent metadata

Field	Value
Publication number	US-10841107-B2
Application number	US-201715818530-A
Country	US
Kind code	B2
Filing date	Nov 20, 2017
Priority date	Nov 20, 2017
Publication date	Nov 17, 2020
Grant date	Nov 17, 2020

Abstract

According to various aspects, a delay-based physical unclonable function (PUF) device is provided. According to one embodiment, the PUF device includes circuitry for generating output bits of entropy by comparing, or “racing”, a plurality of PUF cells. A PUF cell is a building block of the PUF device. For example, the PUF device may include two identically designed circuits with only process related variations and each circuit can be a PUF cell. According to another aspect, if PUF cells with same history of winning or losing are being compared in a race, adversaries cannot predict the outcome of the current race based on previous race results. Accordingly, systems and methods are described herein for generating multiple rounds of races based on the previous rounds of races. Thus, one PUF cell can be used in multiple pairwise comparisons while maximal entropy is extracted.

First claim

What is claimed is:

1. A method for generating entropy in a physical unclonable function (PUF) encoding, the method comprising:
assigning by at least one processor, in a first round, first pairings of respective ones of a plurality of PUF cells;
generating, in the first round, respective first outputs from each of the plurality of PUF cells and determining results for the first round including a winner for each pair of PUF cells in the first pairings, wherein the winner for each pair of PUF cells in the first pairings is identified based on which respective PUF of each pair of PUF cells in the first pairings generates a first output prior to another PUF of each pair of PUF cells in the first pairings;
assigning, in a second round subsequent to the first round, second pairings of respective ones of the plurality of PUF cells based on the results of the first round;
generating, in the second round, respective second outputs from each of the plurality of PUF cells and determining results for the second round including a winner for each pair of PUF cells in the second pairings, wherein the winner for each pair of PUF cells in the second pairings is identified based on which respective PUF of each pair of PUF cells in the second pairings generates a second output prior to another PUF of each pair of PUF cells in the second pairings; and
generating a PUF output based on the results of the first round and the results of the second round.

2. The method of claim 1 , further comprising obfuscating a secret using the PUF output.

3. The method of claim 1 , wherein each PUF cell, of the plurality of PUF cells, comprises one of a plurality of identically designed circuits with differences stemming from manufacturing process variations.

4. The method of claim 1 , wherein assigning, in a second round subsequent to the first round, second pairings of respective ones of the plurality of PUF cells based on the results of the first round comprises:
assigning pairings of the respective winners of each pair of PUF cells in the first pairing; and
assigning pairings of the remaining PUF cells that were not winners in the first pairing.

5. The method of claim 1 , further comprising:
assigning, in a third round subsequent to the second round, third pairings of respective ones of the plurality of PUF cells based on the results of the first round and the second round, wherein each PUF cell of the plurality of PUF cells is paired with a PUF cell of the plurality of PUF cells having been the winner of an equal number of rounds; and
generating, in the third round, respective third outputs from each of the plurality of PUF cells and determining a winner for each pair of PUF cells in the third pairings.

6. The method of claim 1 , wherein a first winner of a first pair in a previous round is paired with a second winner of a second pair in the previous round.

7. The method of claim 1 , further comprising assigning additional rounds of PUF cell pairings based on the results of previous rounds by:
grouping, into a plurality of groups, PUF cells that have been paired in a previous round; and
pairing each PUF cell in a first group with a respective PUF cell in a second group.

8. The method of claim 1 , further comprising generating a bit representing the winner of each pair of PUF cells in each round, wherein a winner of a pair of PUF cells is associated with an output of a binary comparison of respective outputs of each PUF cell in the pair, and further wherein the pairings of the first round and the second round generate a number of bits of entropy equal to the number of PUF cells.

9. The method of claim 1 , further comprising assigning additional rounds of pairings based on the results of previous rounds, wherein the total number of rounds is limited by the at least one processor to not exceed the binary logarithm of the number of PUF cells in the plurality of PUF cells.

10. The method of claim 1 , wherein the method further comprises,
applying, by the at least one processor, an error correcting code to the respective first outputs from each of the plurality of PUF cells prior to the second round.

11. A system for generating entropy in a physical unclonable function (PUF) encoding, the system comprising:
a plurality of PUF cells; and
at least one processor configured to:
assign, in a first round, first pairings of respective ones of a plurality of PUF cells;
generate, in the first round, respective first outputs from each of the plurality of PUF cells and determine results for the first round including a winner for each pair of PUF cells in the first pairings, wherein the winner for each pair of PUF cells in the first pairings is identified based on which respective PUF of each pair of PUF cells in the first pairings generates a first output prior to another PUF of each pair of PUF cells in the first pairings;
assign, in a second round subsequent to the first round, second pairings of respective ones of the plurality of PUF cells based on the results of the first round;
generate, in the second round, respective second outputs from each of the plurality of PUF cells and determine results for the second round including a winner for each pair of PUF cells in the second pairings, wherein the winner for each pair of PUF cells in the second pairings is identified based on which respective PUF of each pair of PUF cells in the second pairings generates a second output prior to another PUF of each pair of PUF cells in the second pairings; and
generate a PUF output based on the results of the first round and the results of the second round.

12. The system of claim 11 , wherein the at least one processor is further configured to obfuscate a secret using the PUF output.

13. The system of claim 11 , wherein each PUF cell, of the plurality of PUF cells, comprises one of a plurality of identically designed circuits with differences stemming from manufacturing process variations.

14. The system of claim 11 , wherein assigning, in a second round subsequent to the first round, second pairings of respective ones of the plurality of PUF cells based on the results of the first round comprises:
assigning pairings of the respective winners of each pair of PUF cells in the first pairing; and
assigning pairings of the remaining PUF cells that were not winners in the first pairing.

15. The system of claim 11 , wherein the at least one processor is further configured to:
assign, in a third round subsequent to the second round, third pairings of respective ones of the plurality of PUF cells based on the results of the first round and the second round, wherein each PUF cell of the plurality of PUF cells is paired with a PUF cell of the plurality of PUF cells having been the winner of an equal number of rounds; and
generate, in the third round, respective third outputs from each of the plurality of PUF cells and determine a winner for each pair of PUF cells in the third pairings.

16. The system of claim 11 , wherein a first winner of a first pair in a previous round is paired with a second winner of a second pair in the previous round, and further wherein the at least one processor is further configured to apply an error correcting code to respective outputs from each of the plurality of PUF cells prior to a current round.

17. The system of claim 11 , wherein the at least one processor is further configured to assign additional rounds of PUF cell pairings based on the results of previous rounds by:
grouping, into a plurality of groups, PUF cells that have been paired in a previous round; and
pairing each PUF cell

Assignees

• Analog Devices Inc

Inventors

• Poo Tze Lei
• Ahmad Sadaf

Classifications

• H04L9/0866 Primary

  involving user or device identifiers, e.g. serial number, physical or biometrical information, DNA, hand-signature or measurable physical characteristics · CPC title

• H04L9/0861

  Generation of secret information including derivation or calculation of cryptographic keys or passwords · CPC title

• H04L9/34

  Bits, or blocks of bits, of the telegraphic message being interchanged in time {(for speech signals H04K1/06)} · CPC title

• H04L9/3278 Primary

  using physically unclonable functions [PUF] · CPC title

• H04L9/088

  Usage controlling of secret information, e.g. techniques for restricting cryptographic keys to pre-authorized uses, different access levels, validity of crypto-period, different key- or password length, or different strong and weak cryptographic algorithms (network architectures or network communication protocols for using time-dependent keys in a packet data network H04L63/068) · CPC title