

Intrinsic ID PUFs: An Antidote to PostQuantum UncertaintyBy Intrinsic ID You’ve probably been hearing a lot lately about the quantumcomputing threat to cryptography. If so, you probably also have a lot of questions about what this “quantum threat” is and how it will impact your cryptographic solutions. Let’s take a look at some of the most common questions about quantum computing and its impact on cryptography What is a quantum computer? A quantum computer is not a very fast generalpurpose supercomputer, nor can it magically operate in a massively parallel manner. Instead, it efficiently executes unique quantum algorithms. These algorithms can in theory perform certain very specific computations much more efficiently than any traditional computer could. However, the development of a meaningful quantum computer, i.e., one that can in practice outperform a modern traditional computer, is exceptionally difficult. Quantum computing technology has been in development since the 1980s, with gradually improving operational quantum computers since the 2010s. However, even extrapolating the current state of the art into the future, and assuming an exponential improvement equivalent to Moore’s law for traditional computers, experts estimate that it will still take at least 15 to 20 years for a meaningful quantum computer to become a reality. ^{1, 2} What is the quantum threat to cryptography ? In the 1990s, it was discovered that some quantum algorithms can impact the security of certain traditional cryptographic techniques. Two quantum algorithms have raised concern:
These quantum algorithms, if they can be executed on a meaningful quantum computer, will impact the security of current cryptographic techniques. What is the impact on my publickey cryptography solutions? By far the most important and most widely used publickey primitives today are based on RSA, discretelogarithm, or elliptic curve cryptography. When meaningful quantum computers become operational, all of these can be efficiently solved by Shor’s algorithm. This will make virtually all publickey cryptography in current use insecure. For the affected publickey encryption and key exchange primitives, this threat is already real today. An attacker capturing and storing encrypted messages exchanged now (or in the past), could decrypt them in the future when meaningful quantum computers are operational. So, highly sensitive and/or longterm secrets communicated up to today are already at risk. If you use the affected signing primitives in shortterm commitments of less than 15 years, the problem is less urgent. However, if meaningful quantum computers become available, the value of any signature will be voided from that point. So, you shouldn’t use the affected primitives for signing longterm commitments that still need to be verifiable in 1520 years or more. Over the last decade, the cryptographic community has designed new publickey primitives that are based on mathematical problems that cannot be solved by Shor’s algorithm (or any other known efficient algorithm, quantum or otherwise). These algorithms are generally referred to as postquantum cryptography. NIST recently announced a selection of these algorithms for standardization ^{3}. What is the impact on my symmetric cryptography solutions? The security level of a welldesigned symmetric key primitive is equivalent to the effort needed for bruteforcing the secret key. On a traditional computer, the effort of bruteforcing a secret key is directly exponential in the key’s length. When a meaningful quantum computer can be used, Grover’s algorithm can speed up the bruteforce attack quadratically. The needed effort remains exponential, though only in half of the key’s length. So, Grover’s algorithm could be said to reduce the security of any givenlength algorithm by 50%. However, there are some important things to keep in mind:
The practical impact of quantum computers on symmetric cryptography is, for the moment, very limited. Worstcase, the security strength of currently used primitives is reduced by 50% (of their key length), but due to the limitations of Grover’s algorithm, that is an overly pessimistic assumption for the near future. Doubling the length of symmetric keys to withstand quantum bruteforce attacks is a very broad blanket measure that will certainly solve the problem, but is too conservative. Today, there are no mandated recommendations for quantumhardening symmetrickey cryptography, and 128bit security strength primitives like AES128 or SHA256 are considered safe to use now and in the foreseeable future. Is there an impact on informationtheoretical security? Informationtheoretically secure methods (also called unconditional or perfect security) are algorithmic techniques for which security claims are mathematically proven. Some important informationtheoretically secure constructions and primitives include the Vernam cipher, Shamir’s secret sharing, Quantum key distribution8 (not to be confused with postquantum cryptography), entropy sources and physical unclonable functions (PUFs), and fuzzy commitment schemes ^{9}. The practical impact of quantum computers on symmetric cryptography is, for the moment, very limited. Because an informationtheoretical proof demonstrates that an adversary does not have sufficient information to break the security claim, regardless of its computing power – quantum or otherwise – informationtheoretically secure constructions are not impacted by the quantum threat. Intrinsic ID PUFs: An antidote for postquantum security uncertainty Intrinsic ID SRAM PUFs The core technology underpinning all Intrinsic ID products is an SRAM PUF. Like other PUFs, an SRAM PUF generates deviceunique responses that stem from unpredictable variations originating in the production process of silicon chips. The operation of an SRAM PUF is based on a conventional SRAM circuit readily available in virtually all digital chips. Based on years of continuous measurements and analysis, Intrinsic ID has developed stochastic models that describe the behavior of its SRAM PUFs very accurately^{10}. Using these models, we can determine tight bounds on the unpredictability of SRAM PUFs. These unpredictability bounds are expressed in terms of entropy, and are fundamental in nature, and cannot be overcome by any amount of computation, quantum or otherwise. Intrinsic ID Quiddikey QuiddiKey is a hardware security solution based on SRAM PUF technology. The central component of QuiddiKey is a fuzzy commitment scheme^{9} that protects a root key with an SRAM PUF response and produces public helper data. It is informationtheoretically proven that the helper data discloses zero information on the root key, so the fact that the helper data is public has no impact on the root key’s security. This noleakage proof – kept intact over years of field deployment on hundreds of millions of devices – relies on the PUF employed by the system to be an entropy source, as expressed by its stochastic model. QuiddiKey uses its entropy source to initialize its root key for the very first time, which is subsequently protected by the fuzzy commitment scheme. In addition to the fuzzy commitment scheme and the entropy source, QuiddiKey also implements cryptographic operations based on certified standardcompliant constructions making use of standard symmetric crypto primitives, particularly AES and SHA256^{11}. These operations include:
Intrinsic ID: proven security for a postquantum world The security architecture of QuiddiKey is based on informationtheoretically secure components for the generation and protection of a root key, and on established symmetric cryptography for other cryptographic functions. Informationtheoretically secure constructions are impervious to quantum attacks. The impact of the quantum threat on symmetric cryptography is very limited and does not require any remediation now or in the foreseeable future. Importantly, QuiddiKey does not deploy any quantumvulnerable publickey cryptographic primitives. All variants of QuiddiKey are quantumsecure and in accordance with recommended postquantum guidelines. The use of the 256bit security strength variant of QuiddiKey will offer strong quantumresistance, even in a distant future, but also the 128bit variant is considered perfectly safe to use now and in the foreseeable time to come. ^{1} “Report on PostQuantum Cryptography”, NIST Information Technology Laboratory, NISTIR 8105, April 2016, ^{2} “2021 Quantum Threat Timeline Report”, Global Risk Institute (GRI), M. Mosca and M. Piani, January, 2022, ^{3} “PQC Standardization Process: Announcing Four Candidates to be Standardized, Plus Fourth Round Candidates”, NIST Information Technology Laboratory, July 5, 2022, ^{4} “Grover’s quantum searching algorithm is optimal”, C. Zalka, Phys. Rev. A 60, 2746, October 1, 1999, https://journals.aps.org/pra/abstract/10.1103/PhysRevA.60.2746 ^{5} “Reassessing Grover’s Algorithm”, S. Fluhrer, IACR ePrint 2017/811, ^{6} “NIST’s pleasant postquantum surprise”, Bas Westerbaan, CloudFlare, July 8, 2022, ^{7} “PostQuantum Cryptography  FAQs: To protect against the threat of quantum computers, should we double the key length for AES now? (added 11/18/18)”, NIST Information Technology Laboratory, ^{8} “Quantum cryptography: Public key distribution and coin tossing”, C. H. Bennett and G. Brassard, Proceedings of the IEEE International Conference on Computers, Systems and Signal Processing, December, 1984, ^{9} “A fuzzy commitment scheme”, A. Juels and M. Wattenberg, Proceedings of the 6th ACM conference on Computer and Communications Security, November, 1999, ^{10} “An Accurate Probabilistic Reliability Model for Silicon PUFs”, R. Maes, Proceedings of the International Workshop on Cryptographic Hardware and Embedded Systems, 2013, ^{11} NIST Information Technology Laboratory, Cryptographic Algorithm Validation Program CAVP, validation #A2516, https://csrc.nist.gov/projects/cryptographicalgorithmvalidationprogram/details?validation=35127 If you wish to download a copy of this white paper, click here

Home  Feedback  Register  Site Map 
All material on this site Copyright © 2017 Design And Reuse S.A. All rights reserved. 