1
$\begingroup$

Please note, I am in no way questioning the future usefulness of quantum key distribution (QKD) in certain applications. I have no doubt it will prove useful for large banks, and in certain military research applications.

However, I cannot ever see it becoming common at the consumer level, or even enterprise level, even if the cost of sensitive quantum hardware decreases drastically.

http://users.telenet.be/d.rijmenants/en/onetimepad.htm

One-time pad encryption nevertheless has a bright future. It is in fact the only crypto algorithm that has any future. Once that computational power and codebreaking technology has surpassed the capabilities of cryptologists and the limitations of mathematics to make strong encryption, there will no longer be any crypto algorithm that survives the evolution of cryptology, unless it meets the standards of information-theoretical perfect security.

The above article claims that all other encryption algorithms will be made obsolete by computing advances, and therefore, we must at some point move to a combination of One Time Pad (OTP) and QKD. I find this claim to be dubious, but as a non-cryptography expert, I am trying to keep an open mind.

Although this article is mostly about OTP, QKD would need to be used along side OTP to be of much practical value for all but a few select applications.

My doubts stem from QKD not seeming compatible with the principals and implementation of the world wide web. The WWW requires decentralized routing; that is to say, the electrons you receive, will never be the actual electrons I sent you, and that is okay, as long their frequency pattern matches.

To my knowledge, there is no way to duplicate a photon's properties without collapsing its wave function; perhaps this assumption is incorrect? That means, my server would have to find a way to redirect the same photon to its intended target, which seems error prone and unpractical.

Even if we can find a way to duplicate a photon (or electron) without collapsing its wave function in an efficient manner, how do I now transmit that wave function over wifi, which is how most people use the internet?

Am I misunderstanding something here that would allow widespread QKD and OTP to become practical for a large distributed consumer network? Or is the conclusion this article came to questionable as I suspected?

$\endgroup$
15
  • $\begingroup$ For me this sounds like asking if training monkeys to do programming would be possible without explaining why you want to do this in the first place. Could you instead start with explaining what actual problem you are trying to solve and why QKD sound like a better solution to deal with this problem than anything else and only then explain why do you think it would not be possible? If there is no better solution to the problem then QKD then one probably has to design the internet protocols around this solution. $\endgroup$ Commented Apr 13, 2017 at 15:50
  • $\begingroup$ Steffan, I am not personally trying to solve a problem, I am just talking theory $\endgroup$ Commented Apr 13, 2017 at 16:44
  • 1
    $\begingroup$ I was reading an article on the topic (linked by another question on this site); it claimed that QKD was the future, and the current encryption techniques used were broken because they are not perfect. I have my doubts about both of these claims, which is why I asked this question. $\endgroup$ Commented Apr 13, 2017 at 17:07
  • 2
    $\begingroup$ In this case it might be a good idea to structure the question around the claim you've read, i.e. that there is no way around QKD. And then you can add your doubts. This way an answer would be possible which refutes the claim or shows that the article did not mean to use QKD in the way you envision. But for this you also need to reference the article so that one can see what was actually written. $\endgroup$ Commented Apr 13, 2017 at 17:49
  • 1
    $\begingroup$ Much better. Although I doubt the initial claim they make in the article, i.e. the OTP will be the only thing left because all other algorithms will be eventually broken (and no better developed). $\endgroup$ Commented Apr 13, 2017 at 19:10

2 Answers 2

7
$\begingroup$

There are many questions here; I am not answering the question in the title, but rather addressing the final questions in the body.

One-time pad encryption nevertheless has a bright future. It is in fact the only crypto algorithm that has any future. Once that computational power and codebreaking technology has surpassed the capabilities of cryptologists and the limitations of mathematics to make strong encryption, there will no longer be any crypto algorithm that survives the evolution of cryptology, unless it meets the standards of information-theoretical perfect security. Just as classical pencil-and-paper ciphers were rendered useless with the advent of the computer, so will current computer based crypto algorithms become victim to the evolution of technology, and that moment might creep on us much faster than we expect. Only one-time pad encryption, the only information theoretically secure encryption, will survive that evolution.

The linked article describes OTPs at great length. It goes on to quickly make casual claims about how doomed all other cryptographic algorithms are, without providing any kind of citation or real argument for why this will be the case. There is no reference to even a weak argument such as "but maybe P=NP". They make vague references to increasing computational power and improved cryptanalytic techniques, so I guess that is what we will have to cover.

Computational Power

This demonstrates a lack of understanding of how the cost of cracking a key actually scales. Claiming that advances in computational power alone will ever threaten the security of, for example, AES-256, is evidence in support of this. No amount of computing power will ever brute force an AES-256 key. It is not a possibility even from a theoretical point of view, let alone a practical one.

Additional misunderstandings are present in the paragraph immediately preceding that one:

Another disadvantage is that one-time encryption doesn't provide message authentication and integrity.

Ok good, this is true and at least the author recognizes this much.

Of course, you know that the sender is authentic, because he has the appropriate key and only he can produce a decipherable ciphertext ...

This is silly. Anyone can simply craft any set of bits they want and submit it as a "ciphertext", and the receiving party has no way of verifying that the message actually came from anyone in particular (indeed, they could not accurately tell the difference between a ciphertext intended for them and a pile of random bits)

Continuing further into that same paragraph, we see the author advocate MAC-then-encrypt (edit: Actually, it's arguably not even MAC-then-encrypt as the hash is not even keyed), which runs contrary to standard best practices

A solution is to use a hash algorithm on the plaintext and send the hash output value, encrypted along with the message, to the recipient (a hash value is a unique fixed-length value, derived from a message). Only the person who has the proper one-time pad is able to correctly encrypt the message and corresponding hash. An adversary cannot predict the effect of his manipulations on the plaintext, nor on the hash value. Upon reception, the message is deciphered and its content checked by comparing the received hash value with a hash that is created from the received message. Unfortunately, a computer is required to calculate the hash value, making this method of authentication impossible for a purely manual encryption.

Interestingly enough, regular old hash functions appear to be good enough for our information-theoretic security lover, despite the fact that information-theoretically secure MACs exist.

But what about cryptanalysis?

Cryptanalytic attacks may exist that can recover a key in less time then brute force. This does not imply that:

  • The space requirements of such attacks is practical
  • The time requirements of such attacks is practical (> 2 ** 100 == impractical)
  • The conditions required for the attack to function may not be realistic
    • For example/before anyone comments with "But related key attacks on AES-256!", consider the context and costs of that attack:
      • There is a key owner; the key is KA and the attackers tries to guess it.
      • The key owner can somehow be persuaded to compute three other keys KB , KC and KD, from KA, using a specific derivation algorithm (KB is equal to KA XORed with a constant that the attacker chooses; KC and KD use a more complex but equally deterministic derivation algorithm).
      • Then, the attacker can make the key owner encrypt and decrypt arbitrary blocks -- that the attacker chooses -- with the keys KA , KB, KC and KD.
      • The key owner will accept to process up to $2^{99.5}$ blocks (that's 16-byte blocks, hence a grand total of about 14 thousands of billions of billions of gigabytes).
      • Finally, the attacker has access to some storage space of about one million of billions of gigabytes.

Did you see the part where the adversary can encrypt and decrypt 14 thousands of billions of billions of gigabytes under four different keys of their choosing? What exactly is your cipher protecting, in this scenario? Why does the adversary even need your key if they have access to a decryption oracle? Is this really a reasonable and practical scenario to be in? Would you really base your decision on which algorithm to use based off of an attack with these kind of requirements?

The point is that just using "the bottom line" where the author(s) consolidate all of their attack into a single measurement of time as the only gauge for security is too narrow of a perspective. Is an algorithm that is broken in time 2 ** 115 really less secure then an algorithm that requires time 2 ** 128 to break? Obviously in theory the correct answer to the question is "yes", but in practice both such attacks would take too long to execute and hence both would offer equivalent security as neither attack would ever be performed (we will ignore the argument that the hypothetical attacks could be improved).

Am I misunderstanding something here that would allow widespread QKD and OTP to become practical for a large distributed consumer network? Or is the conclusion this article came to questionable as I suspected?

There are reasons to believe that the conclusion of the article is questionable. The author of the article basically claims that widespread QKD+OTP is needed, but does not appear to offer any constructive advice as to how to build such a future, nor any supporting evidence for why all of the rest of cryptography is apparently doomed.

Amidst all of the praise of the OTP, they completely neglect to mention how the algorithms that are used in practice (i.e. AES/ChaCha) succeed at providing security to the entire world on a regular basis, while the OTP in all of it's theoretically perfect glory has been broken in practice on multiple occasions.

The OTP and quantum cryptography are basically the opposite of practical cryptography. The more complicated the communication system is, the more vulnerable it will be to attack.

Adversaries will not target the strongest parts of the equation; Supposing you really did utilize QKD and OTP to secure your messages, they will simply wait for you to receive the messages then extract the information from you personally.

Either that or they will target/exploit some aspect of the implementation, because there is a difference between a theoretically secure algorithm and a secure implementation of that algorithm.

$\endgroup$
7
  • $\begingroup$ I see some value in your answer, but at the end you seem to throw up your hands and say, "other vulnerabilities exist, so why add another layer of security?" I'm also not sure you understand how QKD works. Any interference destroys the information, given entanglement. What exactly is being recovered? $\endgroup$
    – floor cat
    Commented Apr 17, 2017 at 4:59
  • 2
    $\begingroup$ @floorcat Your quotation is inaccurate; I did not say that. Considering I did not really discuss QKD in my answer, I see no reason for you to doubt my understanding of it. If the combination of QKD + OTP is provably, unconditionally secure, then attacking it is not an option, which means that weaker links such as the implementation will be targeted instead. "What exactly is being recovered" - Did you read the link behind "extract the information from you personally"? In case you did not, it means someone will simply visit you after you receive your messages and force you to tell them... $\endgroup$
    – Ella Rose
    Commented Apr 17, 2017 at 5:15
  • 2
    $\begingroup$ ... And there is nothing cryptography can do to prevent them from doing so, regardless of whether or not it's in the form of QKD and OTPs. $\endgroup$
    – Ella Rose
    Commented Apr 17, 2017 at 5:16
  • 2
    $\begingroup$ @floorcat I included that statement because many may naively think "I'm using QKD + OTP, it's literally impossible for anyone to breach my confidentiality" - this is not true in practice, they simply will target some other part besides the QKD + OTP. My argument is that your adversary will wait for you to receive your messages successfully via QKD + OTP, then physically coerce you into surrendering the information. This situation applies regardless of whether or not "regular" public key encryption techniques are used or QKD... $\endgroup$
    – Ella Rose
    Commented Apr 17, 2017 at 19:44
  • 3
    $\begingroup$ ... Acknowledging the possibile realities is not equivalent to saying "Oh well, don't bother encrypting anything ever.". I did not say that in my answer, and if you interpreted my answer as saying that, I am explicitly informing you that such an interpretation is inaccurate. I do not feel this is unclear from my answer, and am not entirely sure what we're not understanding here. $\endgroup$
    – Ella Rose
    Commented Apr 17, 2017 at 19:45
3
$\begingroup$

This answer addresses the questions you posed specifically concerning QKD.

The above article claims that all other encryption algorithms will be made obsolete by computing advances, and therefore, we must at some point move to a combination of One Time Pad (OTP) and QKD.

I highly doubt all other encryption algorithms will become obsolete. To begin, the complexity class of quantum computing isn't fully understood yet but we are able to say that there are certain problem classes a quantum computer cannot solve any better than a classical device. In terms of classical devices, Moore's law is a strong enough reason to trust that computational advances have limits.

To my knowledge, there is no way to duplicate a photon's properties without collapsing its wave function; perhaps this assumption is incorrect? That means, my server would have to find a way to redirect the same photon to its intended target, which seems error prone and unpractical.

It is possible to encode and transmit data without losing the information during measurement. This component of QKD is termed error correction, and it was recently shown that classical entanglement can be used to prevent loss of information.

Quoting from phys org:

"Previously, to fix an error in the quantum state used for secure communication would mean measuring the photon sent, which in turn would mean losing the information that one was trying to send. ...all the measurements needed to fix the errors in the quantum state can be done in real-time without destroying the quantum information."

However, I cannot ever see it becoming common at the consumer level, or even enterprise level, even if the cost of sensitive quantum hardware decreases drastically.

There has been active research deploying QKD in already existing telecommunications infrastructure. Toshiba and Cambridge have been spending years deploying QKD over "dark" fibers and have also succeeded in using "lit" fibers alongside classical transmissions of 100Gbps (source).

Even if we can find a way to duplicate a photon (or electron) without collapsing its wave function in an efficient manner, how do I now transmit that wave function over wifi, which is how most people use the internet?

This is probably the more difficult aspect of commercial accessibility of QKD. A QKD protocol enabling a mobile device or wifi connection to negotiate the keys would require the capability of sharing and transmitting quantum properties. A further issue comes in the form of maintaining the entanglement. I think it's safe to say that the initial uses of QKD in a commercial setting would focus on client and server key negotiations, while potentially relying on a third-party in the handshake. This would rely on recent discoveries which demonstrate you can work around the no-cloning theorem to map quantum properties onto an intermediary particle.

Essentially Alice sends classical information to Bob containing unknown quantum properties. A server can then share additional components of the quantum state, serving as the "quantum channel."

Alice then performs some function that effects her entangled particle, and again sends the information to Bob using classical information. Alice's actions change Bob's particle and after measurement, Bob is able to recreate the unknown quantum state.

If Alice is interacting with her entangled particle as a component of some QKD protocol deployed in telecom fibers, it might address some of the difficulty of providing QKD security for end-users on wifi connections.

Am I misunderstanding something here that would allow widespread QKD and OTP to become practical for a large distributed consumer network? Or is the conclusion this article came to questionable as I suspected?

There are a few misunderstandings in your question, but they mostly arise from the quick pace of new discoveries in the field.

QKD has been deployed successfully over currently existing channels, transmitted in parallel with classical data. There are also methods to bypass potential loss of information once the wave function collapses. Additional relevant discoveries are the new phase of matter called "time crystals" which may help maintain equilibrium in quantum communications.

All things considered though, yes, the conclusion is dubious at best. There are several other forms of encryption that in all likelihood won't be at risk for the foreseeable future.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.