Office of Technology Transfer – University of Michigan

A Method for Randomness Expansion Using Untrusted Quantum Devices

Technology #6000

Questions about this technology? Ask a Technology Manager

Download Printable PDF

Categories
Researchers
Yaoyun Shi
Managed By
Drew Bennett
Associate Director - Software Licensing 734-615-4004
Patent Protection
US Patent 9,471,279
US Patent 9,471,280

Researchers at the University of Michigan have developed a protocol for randomness expansion using untrusted quantum devices that achieves quantum security and an exponential rate of expansion. Random number generation plays a vital role in the fields of cryptography, fast information processing through randomized algorithms, and accurate physics simulations. Most extant solutions use seeds obtained from sources such as the current time, temperature, or computer mouse movements and then apply a deterministic transformation to produce an output. However, mathematically, no deterministic process can increase the amount of randomness. Consequently, current implementations of public key cryptography suffer from vulnerabilities due to a lack of randomness. Quantum technologies promise increased randomness, but access to trusted quantum devices is essential to leverage the randomness offered.

Design Details

The protocol for randomness expansion developed at the University of Michigan relaxes the requirement of trusted devices. The algorithm starts with ‘k’ perfect random bits, and expands them to an arbitrary number of output bits that are close to perfect randomness. The output of the algorithm is unconditionally secure against the most general adversary, even when no limit on the computational power of the adversary is assumed. The algorithm guarantees that the probability of generating less than near perfect randomness is negligibly small. Further, the protocol allows quantum devices to deviate from the ideal specifications by a sufficiently small constant amount. Overall, the protocol expands randomness at an exponential rate while making minimal assumptions about the quantum devices. The invention can be adapted for key distributions tasks which are extremely important to current public key cryptography algorithms. The algorithm can also be applied to all situations that require a large amount of high quality and trustworthy randomness. Compared to the only other known method for randomness expansion using untrusted quantum devices that achieves quantum security and an exponential rate of expansion, the protocol offers increased robustness, does not require a large amount of long-term quantum memory, and supports a wide range of quantum building blocks.

Applications

  • Applications that require a large amount of high quality and trustworthy randomness
  • Cryptographic protocols
  • Gambling and lottery applications
  • Physics simulations

Advantages

  • Randomness expansion on untrusted devices
  • Increased robustness
  • No requirement for large amounts of long-term quantum memory
  • Support for a wide range of quantum building blocks