Secure digital signatures using physical unclonable function devices with reduced error rates

Patent metadata

Field	Value
Publication number	US-11271759-B2
Application number	US-201916560502-A
Country	US
Kind code	B2
Filing date	Sep 4, 2019
Priority date	Sep 5, 2018
Publication date	Mar 8, 2022
Grant date	Mar 8, 2022

Abstract

Systems and methods for securing blockchain and other cryptographically signed ledgers are disclosed. Client devices with arrays of physical-unclonable-function devices are respond to challenges from a server. Characteristics of the arrays are stored by the server during a secure enrollment process. Subsequently, the server issues challenges to the clients and receives responses generated by the clients from characteristics of portions of the arrays specified by the challenges. The challenge responses are used to authenticate the clients and are also used as cryptographic private keys for signing transaction blocks. Public keys corresponding to the private keys are generated allowing signed transaction blocks to be validated as well as allowing clients originating the transactions to be authenticated by other clients. Ternary PUF characterization schemes are used to achieve acceptable authentication error rates.

First claim

The invention claimed is:

1. A method, comprising:
performing an enrollment procedure including:
issuing a set of enrollment challenges to a client possessing a physical-unclonable-function (“PUF”) array having a plurality of PUF devices;
receiving and storing respective enrollment responses to each of the enrollment challenges generated by the client in a database by measuring physical characteristics of PUF devices belonging to portions of the PUF array specified by each enrollment challenge;

selecting, as an authentication challenge, a first enrollment challenge of the set of enrollment challenges; and issuing the authentication challenge to the client;
generating a cryptographic public key by:
determining an expected response to the authentication challenge by retrieving the respective enrollment response corresponding to the first enrollment challenge from the database; and
determining the cryptographic public key by using the expected response as a private key input to a first asymmetric public key generator (“APKG”); and

receiving a cryptographic public key generated by the client using a client-generated authentication response to the authentication challenge as a private key input to a second asymmetric public key generator (APKG) associated with the client; and
comparing the generated cryptographic public key and the received cryptographic public key to determine whether the authentication response is consistent with the expected response, and if so, publishing the received public key in a ledger of authenticated public.

2. The method of claim 1 , wherein the method further comprises authenticating a candidate public key associated with the client to another client by:
receiving a verification request containing the candidate public key from the other client;
comparing the candidate key with cryptographic public keys associated with the client and stored in the ledger; and
transmitting a verification message to the other client indicating that the candidate public key is an authentic public key of the client in response to determining that the candidate public key matches a cryptographic key stored in the ledger and associated with the client.

3. The method of claim 1 , wherein comparing the received cryptographic public key and the generated cryptographic public key to determine whether the authentication response is consistent with the expected response comprises determining that a Hamming distance between the received public key and the generated public key is less than a first predetermined maximum distance.

4. The method of claim 3 , further comprising, when the Hamming distance between the received public key and the generated public key is at least one, determining that the received authentication response is consistent with the expected response by:
generating additional private keys having a Hamming distance less than a second predetermined maximum distance from the expected response and producing additional public keys corresponding to the additional private keys; and
determining that one of the additional public keys is identical to the generated public key.

5. The method of claim 1 , wherein issuing the transaction challenge to the client includes transmitting helper instructions to the client, the helper instructions including rules for generating the transaction-challenge response based on measurements of physical characteristics of PUF devices of a portion of the PUF array, the portion of the PUF array being specified by the transaction challenge.

6. The method of claim 1 , wherein receiving the respective enrollment responses to each of the enrollment challenges includes receiving multiple responses from the client to each enrollment challenge generated by repeated measurements by the client of the PUF devices belonging to the portion of the PUF array specified by each challenge;
wherein performing the enrollment procedure further comprises:
receiving, as each challenge response, a set of signals representing physical characteristics of respective PUF devices belonging to portion of the PUF array specified by that challenge, as measured by the client; and
recording, for each physical characteristic, a range of values for each signal; and

wherein transmitting the helper instructions to the client includes transmitting rules instructing the client to generate the transactions challenge response by:
assigning a first ternary state to any measured physical characteristic having a value within a first range; and
assigning a second ternary state to any measured physical characteristic having a value within a second range of values exclusive of the first range;
assigning a third ternary state to any measured physical characteristic having a value within a third range of values exclusive of the first and second ranges.

7. The method of claim 5 , wherein receiving the respective enrollment responses to each of the enrollment challenges includes receiving multiple responses from the client to each enrollment challenge generated by repeated measurements by the client of the PUF devices belonging to the portion of the PUF array specified by each challenge;
wherein performing the enrollment procedure further comprises:
receiving, as each challenge response, a set of signals representing physical characteristics of respective PUF devices belonging to the PUF array specified by that challenge, as measured by the client; and
recording, for each physical characteristic, a range of values for each signal and:
assigning a first ternary state to any measured physical characteristic having a value within a first range; and
assigning a second ternary state to any measured physical characteristic having a value within a second range of values exclusive of the first range;
assigning a third ternary state to any measured physical characteristic having a value within a third range of values exclusive of the first and second ranges;

and

wherein transmitting the helper instructions to the client includes transmitting masking instructions causing the client to exclude PUF devices having measured physical characteristics assigned to the third ternary state when generating the transaction response.

8. The method of claim 5 , wherein transmitting the helper instructions to the client includes transmitting error-correction instructions that produce the expected response when executed upon an authentication response having a Hamming distance less than a predetermined maximum distance from the expected response by the client.

9. The method of claim 1 , wherein the method further comprises transmitting an index instruction to the client together with the transaction challenge; and
wherein the index instruction is configured to cause the client to:
select instructions indicated by the index instruction from a plurality of instructions stored by client, each of the plurality of instructions specifying distinct rules for generating challenge responses from measurements of physical characteristics of respective PUF devices belonging to the PUF array; and
execute the selected instructions to generate the transaction challenge response.

10. A system, comprising:
a processor, an asymmetric public key generator (APKG), and memory coupled to the processor, the memory storing:
(a) sets of enrollment challenges and respective sets of enrollment responses to the enrollment challenges, the enrollment responses obtained from a plurality of client devices, each of the plurality of client devices having a respective physical-unclonable-function (“PUF”) array having pluralities of PUF devices, each enrollment challenge response being derived from measurements of physical characteristics of PUF devic

Assignees

• Univ Northern Arizona

Inventors

• Cambou Bertrand F

Classifications

• H04L9/50

  using hash chains, e.g. blockchains or hash trees · CPC title

• H04L9/3278 Primary

  using physically unclonable functions [PUF] · CPC title

• H04L9/0861

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

• H04L9/3239 Primary

  involving non-keyed hash functions, e.g. modification detection codes [MDCs], MD5, SHA or RIPEMD · CPC title

• H04L9/0844

  with user authentication or key authentication, e.g. ElGamal, MTI, MQV-Menezes-Qu-Vanstone protocol or Diffie-Hellman protocols using implicitly-certified keys · CPC title