
<html><head><meta http-equiv="Content-Type" content="text/html charset=utf-8"></head><body style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space;" class="">One of the statements made at IETF ’95 was that various parties believe that they can build a Quantum Computer with ‘significant’ capabilities as early as 2020. <div class=""><br class=""></div><div class="">It is thus important that we start looking at contingency planning as an industry. Even if the claims are wildly optimistic and it will be decades before such a machine could break current public key algorithms, we will have to deal with the press and increasingly government concerns. If we don’t have a contingency plan, we risk having to create one in a hurry.</div><div class=""><br class=""></div><div class="">As a general rule, I have always wanted to keep the WebPKI at least ten years ahead of the state of the art in cryptanalysis. We have a long tail of legacy browsers that can be attacked. As it says in Bill 14:7, “Windows XP will always be with you”.</div><div class=""><br class=""></div><div class="">We do not know at this stage what restrictions there will be on the purported QC machines or whether it will prove possible to maintain coherence for enough Qbits to break public key algorithms. What we do know is that RSA, DH, and ECDH are all affected. We also know that our symmetric algorithms are not. AES and SHA-2/SHA-3 remain strong.</div><div class=""><br class=""></div><div class="">Another bit of gut instinct I have is that any new system is likely to be a variant of Diffie Hellman. RSA is vulnerable because it is a trapdoor system. The encryption and decryption systems are symmetrical. We can imagine QC approaches to be the wave mechanics equivalent of filling up a swimming pool and letting it find its own level. Diffie Hellman does not have that symmetry. The scheme works by taking two different paths through a forrest to reach the same destination. Alice and Bob take different paths to arrive at the same key but neither path needs to be reversible for the system to work.</div><div class=""><br class=""></div><div class=""><br class=""></div><div class="">So what is to be done?</div><div class=""><br class=""></div><div class="">One option we do not have is to deploy a new Quantum resistant algorithm. There are proposals out there. But it will take us a considerable time to get comfortable with any of them. And that is not the only criteria either. We would have to have clear intellectual property rights before we could use them. And even if such algorithms exist, they may not be anywhere near as fast as RSA, let alone match the Elliptic Curve systems we are currently getting excited about.</div><div class=""><br class=""></div><div class="">Breaking down the problem into stages, I see two separate problems. One is developing a new QCR PKI (Quantum Cryptanalysis Resistant) and the second is how to deploy it using the assets we already have in place.</div><div class=""><br class=""></div><div class="">So right now, for purposes of contingency planning, I would like to focus on the second. In particular I would like to ask what we can do now to deploy QCR roots of trust that we can use as anchors for the eventual QCR-PKI.</div><div class=""><br class=""></div><div class=""><br class=""></div><span class="">It seems to me that the obvious approach is to make use of Lamport's hash signatures in combination with various efficiency improvements proposed by Diffie, Merkle and Winternitz. CFRG is already working on a draft.<br class=""></span><span class=""><br class=""></span><div class=""><a href="https://datatracker.ietf.org/doc/draft-mcgrew-hash-sigs/" class="">https://datatracker.ietf.org/doc/draft-mcgrew-hash-sigs/</a> </div><div class=""><br class=""></div><div class="">The principle of hash signatures is fairly straightforward. If I start with two random numbers X and NX, I can take a hash of them to produce H(X) and H(NX) and then calculate V = H(H(X) +H(NX)). The value V is my ‘public key’. To assert the value 1, I release the value X, to release the value 0, I release NX. </div><div class=""><br class=""></div><div class="">This approach can be quickly shown to be secure provided that (1) the hash function is secure and (2) only one of the values is ever released.</div><div class=""><br class=""></div><div class="">The efficiency improvements allow the work factor of the signature to be increased to reasonable strength (i.e. 128, 256 bits) without creating unreasonably long signatures. Even so, using hash signatures has two important disadvantages over RSA or ECDH:</div><div class=""><br class=""></div><div class="">1) The signatures are relatively large (1Kb - 8Kb depending on strength and precalculation)</div><div class="">2) Each public key can only be used to sign a single document.</div><div class=""><br class=""></div><div class=""><br class=""></div><div class="">There are in fact ways that it is possible to construct a WebPKI type infrastructure using hash signatures and we may even end up having to resort to using some of them, particularly for low power devices. In particular:</div><div class=""><br class=""></div><div class="">* Distribute Merkle trees of public key values. </div><div class="">* Adopt a ‘use one, make one’ approach to distribution.</div><div class="">* Engage hash chain logs to provide reference truth.</div><div class="">* Use GPU farms and/or bitcoin mining equipment to construct large Merkle trees, the hardware using the trees can be more modest.</div><div class=""><br class=""></div><div class="">Note that even if some smart person comes up with a perfect QCR algorithm tomorrow that is obviously secure and a drop in replacement for RSA, I still want a hash signature alternative so that they don’t have unlimited bargaining power.</div><div class=""><br class=""></div><div class=""><br class=""></div><div class="">So what I think should be done now is for CAs, assisted by the technical community to come to a mechanism for deploying QCR contingency trust roots that can be validated under the current PKI. These would consist of the head of a Merkle tree containing 'some number’ (hundreds? thousands? millions?) of public key commitments for ‘just in case’ use.</div><div class=""><br class=""></div><div class="">As far as distribution goes, the simplest approach would probably be to add them to traditional certs as an extension. This might be in the root itself or an intermediary that has been checked into CT.</div><div class=""><br class=""></div><div class=""><br class=""></div><div class=""><br class=""></div></body></html>