Broadcast-free threshold post-quantum key generation and verification over unencrypted channels from hardware-based correlated randomness

A system comprising one or more computers and one or more storage devices storing instructions that are operable, when executed by the one or more computers, to cause the one or more computers to perform operations for generating an encryption key, the operations comprising:

• receiving, by a first device, first learning parity with noise (LPN) instances from a plurality of other devices to provide combined first LPN instances, each device of the plurality of other devices providing a respective first LPN instance by:
• processing, by a physically unclonable function (PUF), a stream of random challenges to obtain pairs of responses, and
• generating the respective first LPN instance using a pre-stored public matrix, a partial encryption key generated by the device, and a first error matrix;
• and
• generating, by the first device, the encryption key, comprising computing a difference between the combined first LPN instances and an estimated combined error of PUFs to recover a summation of each partial encryption key encoded in the combined first LPN instances.

A non-transitory computer-readable storage medium comprising instructions stored thereon that are executable by a processing device and upon such execution cause the processing device to perform operations for generating an encryption key, the operations comprising:

• receiving, by a first device, first learning parity with noise (LPN) instances from a plurality of other devices to provide combined first LPN instances, each device of the plurality of other devices providing a respective first LPN instance by:
• processing, by a physically unclonable function (PUF), a stream of random challenges to obtain pairs of responses, and
• generating the respective first LPN instance using a pre-stored public matrix, a partial encryption key generated by the device, and a first error matrix;
• and
• generating, by the first device, the encryption key, comprising computing a difference between the combined first LPN instances and an estimated combined error of PUFs to recover a summation of each partial encryption key encoded in the combined first LPN instances.