FIELD OF THE DISCLOSURE

The present disclosure relates to techniques for authenticating devices using garbled circuits and physical unclonable functions.

BACKGROUND

Devices may need to be authenticated to access resources provided by other devices, such as databases or application servers. Authentication may ensure the actual identity of a device, allowing enforcement of rules governing access to resources.

Garbled circuits are a cryptographic technique that allows for two or more parties to securely compute a function. A physical unclonable function (PUF) includes circuitry configured to generate an output whose value depends on unique physical properties of the circuitry. Even tightly controlled manufacturing processes will include variations. Thus, even when circuit components are intended to have identical characteristics, these variations result in circuit components with unique characteristics.

SUMMARY OF THE DISCLOSURE

According to various aspects, systems and methods are provided for using a garbled circuit and a physical unclonable function (PUF) value to authenticate a device. During enrollment, the device and at least one computer collaboratively construct multiple garbled circuits corresponding to bits of an enrollment PUF value generated by PUF circuitry coupled to the device. During authentication, the device and the at least one computer evaluate the multiple garbled circuits using an authentication PUF value. Using the results of this evaluation, the at least one computer compares the enrollment PUF value with the authentication PUF value and determines a distance between them. The at least one computer may authenticate the device when the calculated distance is less than a threshold value.

According to one aspect of the present application, a device is provided. The device includes processing circuitry configured to perform acts. The acts include obtaining a physically unclonable function (PUF) value comprising a plurality of bits representing a digitized value of a signal generated by PUF circuitry coupled to the device providing, using at least one communication network, the PUF value to at least one computer; and for each one bit of multiple bits in the plurality of bits: receiving, from the at least one computer using the at least one communication network, first and second input values for a garbled circuit corresponding to the each one bit, wherein the first input value corresponds to a bit value of zero and the second input value corresponds to a bit value of one; encrypting the first and second input values using a device key associated with the device to generate respective encrypted input entries; and providing the encrypted entries to the at least one computer using the at least one communication network.

In some embodiments, the first input value and the second input value may each comprise a symmetric key. The device key associated with the device may comprise a symmetric key. The digitized value of the signal generated by the PUF circuitry may depend on physical characteristics of the PUF circuitry. The PUF circuitry may include a plurality of PUF circuits, and obtaining the PUF value may include selecting from a plurality of signals generated by the plurality of PUF circuits. The device may include one or more sensors; one or more Internet of Things appliances; and/or one or more components, such as one or more Application Specific Integrated Circuits; one or more Field-Programmable Gate Arrays; one or more processors (e.g., processors configured for use with mobile devices, such as, for example, ARM Cortex-M Processors); one or more Micro-Electro-Mechanical Systems; one or more Analog to Digital Converters; one or more Radio-Frequency Identification Tags; and/or one or more Near Field Communications Tags.

According to one aspect of the present application, at least one computer is provided. The at least one computer includes processing circuitry configured to perform acts. The acts include receiving, from a device using at least one communication network, a physically unclonable function (PUF) value comprising a plurality of bits representing a digitized value of a signal generated by PUF circuitry coupled to the device; and for each one bit of multiple bits in the plurality of bits: creating input values and encrypted output entries for a garbled circuit corresponding to the each one bit; providing, to the device and using the at least one communication network, the input values; receiving, from the device using the at least one communication network, input entries for the garbled circuit, each input entry comprising one of the input values encrypted with a device key associated with the device; and storing the input entries in association with the encrypted output entries for the garbled circuit.

In some embodiments, the input values comprise a first input value and a second input value; creating the first input value may include generating a first symmetric key; and creating the second input value may include generating a second symmetric key. Receiving the input entries for the garbled circuit may include receiving a first input entry and a second entry. The first input entry may include a first symmetric key encrypted with the device key associated with the device. The second input entry may include a second symmetric key encrypted with the device key associated with the device. Creating the encrypted output entries for the garbled circuit corresponding to the each one bit may include generating a first value corresponding to zero and a second value corresponding to one; encrypting the first value with a computer key associated with the at least one computer to generate a first output entry and the second value with the computer key associated with the at least one computer to generate a second output entry; and encrypting the first output entry with a first input key to generate the encrypted first output entry and the second output entry with a second input key to generate the encrypted second output entry. Generating the first value may include evaluating a function of zero and a value of the each one bit. Generating the second value may include evaluating a function of one and a value of the each one bit. Generating the first value may include combining a distance value with a device identifier. Generating the first value may include combining a distance value with a nonce. The processing circuitry is configured to further perform acts of: deleting the first input key after generating the encrypted first output entries for the garbled circuits corresponding to the multiple bits; deleting the second input key after generating the encrypted second output entries for the garbled circuits corresponding to the multiple bits; and deleting the PUF value after generating the first values and the second values for the garbled circuits corresponding to the multiple bits. The garbled circuit corresponding to the each one bit may have a depth of one.

In some embodiments, creating encrypted output entries for the garbled circuit may include: generating a first symmetric key and a second symmetric key; generating a first distance value by performing a logical XOR of the value zero and a value of the each one bit; generating a second distance value by performing a logical XOR of the value one and the value of the each one bit; generating a first output value by concatenating the first distance, an identifier of the device, and a nonce; generating a second output value by concatenating the second distance, the identifier of the device, and the nonce; generating a first output entry by encrypting the first output value using a computer key associated with the at least one computer; generating a second output entry by encrypting the second output value using the computer key associated with the at least one computer; generating a first encrypted output entry by encrypting the first output entry using the first symmetric key; and generating a second encrypted output entry by encrypting the second output entry using the second symmetric key.

According to one aspect of the present application, a device is provided. The device includes processing circuitry configured to perform acts. The acts include processing circuitry configured to perform: obtaining a physically unclonable function (PUF) value comprising a plurality of bits representing a digitized value of a signal generated by PUF circuitry coupled to the device; and for each one bit of multiple bits in the plurality of bits: receiving, from at least one computer using at least one communication network, garbled circuit entries for a garbled circuit corresponding to the each one bit, each of the garbled circuit entries comprising respective input and encrypted output entries; selecting, from among the received garbled circuit entries, a first garbled circuit entry based on a value of the each one bit, the first garbled circuit entry including a first input entry and a first encrypted output entry; generating a first input key by decrypting the first input entry using a device key associated with the device; generating a first output entry by decrypting, using the first input key, the first encrypted output entry; and providing the first output entry to the at least one computer using the at least one communication network.

In some embodiments, a structure of the garbled circuit entries may indicate a correspondence between the garbled circuit entries and a value of the each one bit; and the first garbled circuitry entry may be selected based the indicated correspondence. The first garbled circuitry entry may further comprise a value indicating a correspondence between the garbled circuit entries and a value of the each one bit; and the first garbled circuitry entry may be selected based the indicated correspondence. The processing circuitry is configured to further perform acts of: receiving, from the at least one computer in a first order, garbled circuit entries for garbled circuits corresponding to the multiple bits in the plurality of bits; and providing, to the at least one computer in a second order differing from the first order, output entries generated from the garbled circuit entries for the garbled circuits.

According to one aspect of the present application, at least one computer is provided. The at least one computer includes processing circuitry configured to perform, for each one bit of multiple bits in a plurality of bits: providing, to a device using at least one communication network, garbled circuit entries for a garbled circuit corresponding to the each one bit, the garbled circuit entries including a first garbled circuit entry including: a first input entry comprising a first input key encrypted with a device key associated with the device; and a first encrypted output entry comprising a first output entry encrypted with the first input key; receiving, from the device using the at least one communication network, the first output entry; generating a first output value by decrypting the first output entry using a computer key associated with the at least one computer; determining whether to authenticate the device using output values, the output values including the first output value; and providing an indication of the authentication determination to the device.

In some embodiments, providing the garbled circuit entries further may include: providing the first garbled circuit entry corresponding to a first bit value; and providing the second garbled circuit entry corresponding to a second bit value. Providing the first garbled circuit entry may include providing a first value indicating that the first garbled circuit entry corresponds to a first bit value. The first input key may be a symmetric key. Receiving the first output entry may include receiving a combination of a distance value, a device identifier, and a nonce. The output values may include first device identifiers; and determining whether to authenticate the device may include determining whether the first device identifiers match a second device identifier of the device. The output values may include nonces; and determining whether to authenticate the device may include determining whether any of the nonces match. The output values may include distance values; and determining whether to authenticate the device may include determining whether a sum of the distance values exceeds a maximum distance threshold. The distance values may depend on bit values of an enrollment PUF value received from the device by the at least one computer during an enrollment process. The garbled circuit entries for garbled circuits corresponding to different bits may include different input keys.

