25
$\begingroup$

This is my current understanding of how Quantum Cryptography works: (The first bit is Quantum Key Distribution)

Alice sends a beam of photons to Bob through a quantum channel such as an optical fiber. Each of these photons represent a bit of information (0 or 1), and have been polarised in some way (rectilinear or diagonal). Bob uses a set of polarising filters (are these called bases?) combined with photon detectors to pick up these photons. If the polarised photon from Alice passes through its corresponding filter on Bob's end, he will receive the associated bit of the photon (0 or 1). If the photon passes through a wrong filter, it has a 50% probability of getting a 0 or 1. All the photons from Alice are passed through Bob's filters, and Bob obtains a string of 0s and 1s. He then communicates over the public channel to Alice what polarisers (the filters) he used, and Alice tells him which filters are correct. As a result, both parties have a sifted key.

[This is the "BB84" protocol of C. H. Bennett and G. Brassard: Quantum cryptography: Public key distribution and coin tossing, originally in proceedings of IEEE ICCSSP; 1984]
BB84 protocol
Image source: UNS Nice (France), Department of Physics

This next part I am not too sure about. It is my understanding that this new string of 0s and 1s (the sifted key) becomes a new parameter for the encryption and decryption algorithms, allowing communication between Alice and Bob. It is my understanding that in classical cryptography, Eve intercepts the encrypted message and using their computational power, tries to figure out the key.

So in this quantum version, what makes it more secure than the classical version? As in, why can't Eve intercept this encrypted message and as usual try to figure out the key (which is a string of 0s and 1s) like in classical cryptography?

If there is a problem in my understanding, or the question is ambiguously written, please notify me. I am looking for an answer as soon as possible.

$\endgroup$
  • $\begingroup$ "He then communicates over the public channel to Alice what polarisers (the filters) he used, and Alice tells him which filters are correct." Could be clarified more. I unfortunately just hear white noise after the word quantum gets used on this site. $\endgroup$ – Q-Club Sep 5 '17 at 2:20
  • $\begingroup$ @back_seat_driver So what that bit means is that if Bob used DRRDRRD in this order for instance as his filters, where D means diagonal and R means rectilinear, he tells Alice this string. Then Alice confirms which filters were used correctly. $\endgroup$ – lal lal Sep 5 '17 at 3:17
  • $\begingroup$ Great, now we have any idea of what is being transferred! But how does your d/r string get transferred? $\endgroup$ – Q-Club Sep 5 '17 at 3:38
  • $\begingroup$ @back_seat_driver it is communicated through the public (unsecured) channel. Also, do you know anyone who can answer my question? $\endgroup$ – lal lal Sep 5 '17 at 3:57
  • $\begingroup$ There are tons of people who can answer this question! Whether that answer is correct, or even rooted in reality is an even better question! I'll be of no help I stopped listening after the uncertainty principle. $\endgroup$ – Q-Club Sep 5 '17 at 4:08
33
$\begingroup$

TL;DR     The answer is classical cryptography.

Besides a quantum link, secure data communication with Quantum Cryptography uses classical links, a lot of mathematically provable classical cryptography, and a setup procedure using initially trusted material just as in classical cryptography.

To perform the same other than by the One Time Pad, classical cryptography assumes a bound of the adversary's computing power, and some unproven mathematical hypothesis; either assumption may turn out wrong, and risk exists that future progress allows decryption of archived intercepts. Pure Quantum Cryptography relies only on physics when it comes to unproven assumptions, and avoids that particular risk.


This answer (and the question) uses Quantum Cryptography (QC) as meaning use of quantum physics as the basis of data communication with confidentiality and integrity; this is not to be confused with

  • Quantum Cryptanalysis, examining how Quantum Computing could be applied to breaking classical cryptography (Quantum Cryptanalysis could also refer to breaking Quantum Cryptography, perhaps Quantum Random Number Generation, without Quantum Computer or theoretically).
  • Post-Quantum Cryptography, exploring which classical cryptography methods usable now will resist Quantum Cryptanalysis should it start to materialize (though sometime Post-Quantum Cryptography is taken to include some Quantum Cryptanalysis).
  • Quantum Random Number Generation, which aims at producing a demonstrably secure source of near-perfect random secret non-shared bits demonstrably rooted in some identified quantum physics phenomena; these are often used as RNGs in Quantum Cryptography, and that's consistent.

The thought experiment in the seminal BB84 article quoted in the question can lead to practical QC. I explain how and give links, but no math. That's out of ignorance on the quantum side, laziness on the information-theoretic side, and 30000 characters limit as an excuse.


A. Issues prevent direct use of sifted bits

The question summarized only a subset of the article, and stops at obtaining sifted bits. These are squarely unsuitable for direct use, and do not achieve Quantum Key Distribution (QKD), for three main reasons:

  1. Errors creep in the sifted bits

    The many imperfections of the model (heavily simplified compared to the actual hardware and the known laws of quantum physics, even at the time the article was written) are such that, without Eve messing, sizably many sifted bits differ at Alice's and Bob's end. Sifted bits are thus unusable as key to a cipher, for decryption would likely fail.

  2. The sifted bits are not nearly secret enough

    An eavesdropper can gain sizable knowledge about the sifted bits. That makes them unacceptable for direct use as a keystream, for Eve's partial knowledge puts confidentiality in jeopardy. Quoting the article, the best insurance given by the quantum model of the adversary is only:

    it can be shown that no measurement on a photon in transit, by an eavesdropper who is informed of the photon's original basis only after he has performed his measurement, can yield more than 1/2 expected bits of information about the key bit encoded by that photon

  3. Who are these sifted bits shared with?

    The first part of the article, and the question, assume the classical channels are

    susceptible to eavesdropping but not to the injection or alteration of messages

    Without such insurance, Alice and Bob would be unsure about who their sifted bits are really shared with! It could be that Eve rather than Bob is who receives Alice's photons and "communicates over the public channel to Alice", thus that Alice shares sifted bits with Eve. Bob faces a similar issues if Eve really is who sent him photons and "tells him which filters are correct". This allows a Man-in-the-Middle attack when data transmission time comes.


B. Classical cryptography rooted in information theory fixes them all

  1. Secret-Key Reconciliation protocol remove errors, and more

    Coding theory and error detection and correction are used to build a secure Secret-Key Reconciliation protocol additional to sifting, also running over the classical channels. Its objectives are to

    • remove or fix errors in the sifted bits, with bounded low odds of the contrary;
    • obtain an upper bound on the actual error rate, which is attributed to Eve spying the quantum channel;
    • obtain and minimize an upper bound on the information leaked by running the protocol over the classical channels, that Eve is assumed to scrutinize;
    • deduce a lower bound of what entropy (if any) remains in the rest; if there is less than some headroom, QKD failed.

    Such reconciliation protocol can loose little-enough entropy as to be usable in practice, and be information-theoretically provable; but no simple such one is known. A most scrutinized milestone is the cascade protocol in: Gilles Brassard and Louis Salvail's Secret-Key Reconciliation by Public Discussion, in proceedings of Eurocrypt 1993.

  2. Privacy Amplification distillates a shared key

    The entropy demonstrably remaining after reconciliation (if any) is distilled into bits with close to perfect entropy. A classical cryptographer would use a hash, but provable information theory has nothing to offer in that category. ID Quantique's whitepaper gives a rudimentary Privacy Amplification Protocol, but that's only for illustration.

    Further, for use as an ever-flowing source of near-perfect random secret shared bits, it must be removed from the outcome enough bits to renew the setup key (see 3 below). Articles scrutinizing this circularity go under variations of the name Universally Composable Quantum Privacy Amplification.

  3. Classical setup key and cryptography make the classical channels secure

    The method proposed by the article is the most common:

    Alice and Bob have agreed beforehand on a small secret key, which they use to create Wegman–Carter authentication tags

    That's similar to the low-tech key ceremony of classical cryptography: Bob physically meets Alice, each throws an hex dice 20 times, and writes the outcomes as 20 characters, forming two lines on paper. Chemical carbon copy insures Alice and Bob keep identical notes. Their are sealed in two opaque tamper-evident envelopes to insure secrecy until use. Bob protects his envelope while he gets back. Alternatively, Alice does the whole job and a trusted courier hands Bob the envelope against signature.

    For each of the two classic communication channels, the half of the setup key generated by the sender on that channel is used as key to an information-theoretic Message Authentication Code (like Universal hashing of Mark N. Wegman, J. Lawrence Carter; New hash functions and their use in authentication and set equality, in Journal of Computer and System Sciences, 1981), computed over all the data sent on the channel for sieving and reconciliation. That MAC (one of the two "tags" in the article) is sent on the conventional channel it protects. The receiver can recompute and check it, and this gives demonstrably bounded odds of forgery. Our example's 80-bit half key demonstrably gives 40-bit security: better than one in a million millions odds of undetected forgery, which satisfies any rational person.

    Setup key transfer must insure integrity, but can be differed to a moment when secrecy is no longer required, like in classical asymmetric cryptography. However setup key halves must then be conveyed separately in each direction, after reconciliation, but before the key established by QKD can be trusted. That's inconvenient, and common practice is to keep the setup key secret: ID Quantique's whitepaper states that it is made

    use of a preestablished secret key in the emitter and the receiver, which is used to authenticate the communications on the conventional channel. This initial secret key serves only to authenticate the first quantum cryptography session. After each session, part of the key produced is used to replace the previous authentication key.


Note: This did not cover a number of things needed for a working QKD, and possible pitfalls:

  • How does Bob conclude that a photon did not pass thru a polarizing beam splitter, which is an absence of event? If that's by timing, how do Alice and Bob get a common timing reference precise enough? At a coarser level, how do Bob and Alice agree on a common indexing of expected photon events?
  • How much exploitable information leaks thru classical side-channels not accounted for in the reconciliation's estimate of remaining entropy, e.g. due to timing variations in the sifting or reconciliation protocol, varying light intensity, electromagnetic leakage..
  • How much other headroom is necessary in the test at end of reconciliation to robustly cover the imperfections of the quantum model, including those sneakily introduced by a creative adversary? How can it be safely arranged a retry should that test fail?
  • How is the setup key stored secretly in the QKD devices? How is it kept in synchronization under down-to-earth constraints like power failure?
  • Uncaught design errors or runtime faults (accidental or deliberate) in the implementation, which relies on conventional electronics, processors, and software.

C. Quantum Cryptography from Quantum Key Distribution

Just like conventional cryptography, Quantum Cryptography aims at transmission of arbitrary data with confidentiality and integrity (understood to include assurance of origin and destination). Each of these two goals can be reached in two ways, both using classical cryptography over classical channels, using the outcome of Quantum Key Distribution as key:

  1. Provably secure conventional cryptography rooted in information theory

    • The One Time Pad (or an essentially equivalent variant) for confidentiality, using the random bits of QKD as keystream.
      Security relies heavily on the quality of the Privacy Amplification of B.2, and on the soundness of the insurance given by the Secret-Key Reconciliation protocol of B.1. Throughput is bounded by the sift rate diminished by what's eaten by the tasks in B.
    • An information-theoretic Message Authentication Code for integrity and origin, keyed from the QKD flow, as in B.3 above. That tolerates small imperfections in Privacy Amplification.
  2. Conventional symmetric cryptography without mathematical proof

    • Some symmetric cipher for confidentiality, regularly re-keyed using the key stream of QKD. That's the only method to boost an otherwise insufficient rate of QKD. Also, it adequately mitigates small imperfections after Privacy Amplification.
      A typical choice is the block cipher AES-256, perhaps with an operating mode like CTR. That's pragmatic and makes a lot of sense: AES-256 is rubber-stamped by civilians and miliary, is largely conjectured adequately secure from brute force attack for decades including using Quantum Computers, and against side channel attack assuming regular key change with classical key derivation, which QKD can supplement or replace.

    • Some standard Message Authentication Code for integrity, e.g. HMAC-SHA-512, probably regularly keyed from the QKD; giving up on using an information-theoretic MAC could make sense when reusing a commercial classical cryptography device without modification.

    • Authenticated encryption (perhaps AES-GCM), which is a modern way to integrate a symmetric cipher and a standard MAC.

The above techniques are believed secure, or even mathematically provable for those of C.1. The technically difficult points are the prior QKD, and correct implementation as for conventional applied cryptography: Random Number Generator, side channels and fault attacks, integration in a protocol..


D. Operational constraints of Quantum Cryptography

There are severe limitations to QC, at least as widely available:

  1. Incompatibility with network gear along the fiber (standard optical amplifiers or other standard repeaters as used in long fiber cables, switches and routers directing data to the right user). Solutions exist only at the laboratory level. Commercial offers are restricted to point-to-point communication, or/and use conventional cryptography beyond that.
  2. Small range, and (when not assisted by conventional cryptography not mathematically proven) low bandwidth, with a compromise between the two. This ID Quantique Cerberis QKD blade is specified for 20000 AES-256 keys per hour over 50 km (<2 kbit/s QKD), and 10 times less for 100 km. For direct line-of-sight ground-satellite by night, a 2017 paper reports ~12 kbit/s at 645 km to ~1 kbit/s at 1200 km. In lab conditions with supercooled photon detector it is reported
    speed
  3. If we want pure QC, it is lost the convenience of Public-Key Infrastructure based on digital certificates issued by certification authoritie(s).
  4. No interoperability between vendors (closest I could find is Toshiba's call for arms towards that, in a Feb. 2017 newsletter).
  5. No extensive data on operational availability of QC links is available, especially under varying temperature; it is reasonable to fear low Mean Time Between Failure for some parts, e.g. photon detectors after temperature cycling.
  6. To my knowledge, no device employing QKD has obtained so far (Aug 2017) a public security certification covering QKD. Fact-checking this datasheet for a "Certified Common Criteria & FIPS 140-2 Level 3" product with "Support for QKD" available as an upgrade, I conclude the only quantum-related feature covered by certificates is a RNG, and the FIPS 140-2 security policy's only mention of QKD is:

    The Quantum Key Channel serial port connects to a separately available ID Quantiqe (sic) Cerberus quantum key distribution server (not a supported FIPS140-2 Level 3 mode of operation under this certification).


E. Security of Quantum and conventional cryptography

  1. How Quantum Key Distribution implementations fail

    The security of QC is rooted into parts of cryptography that are mathematically proven secure; and a physical model of how photons (possibly other quantum physics objects) behave per modern physical theory, which exquisitely matches experimental results, and allows theoretical proofs.

    However, a large fraction of particles physics and electromagnetism, and all of gravity/relativity, is typically brushed aside from the analysis; and the hypothesis of proofs do not fully model the equipment used, which has allowed some credible attacks, like phase-remapping.

    Worst, adversaries think outside of the box and actively modify the quantum experiment so that the model is no longer a close fit. Like Eve blinds the photon detector! Quoting Lars Lydersen, Carlos Wiechers, Christoffer Wittmann, Dominique Elser, Johannes Skaar and Vadim Makarov: Hacking commercial quantum cryptography systems by tailored bright illumination, in Nature Photonics Letter 2010:

    we demonstrate how two commercial QKD systems id3110 Clavis2 and QPN 5505, from the commercial vendors ID Quantique and MagiQ Technologies, can be fully cracked. We show experimentally that Eve can blind the gated detectors in the QKD systems using bright illumination, thereby converting them into classical, linear detectors. The detectors are then fully controlled by classical laser pulses superimposed over the bright continuous-wave (c.w.) illumination. Remarkably, the detectors exactly measure what is dictated by Eve.

    A joint 2010 press release with the company which QKD device was hacked mentions that it was

    developed and tested a countermeasure. [..] “Testing is a necessary step to validate a new security technology and the fact that this process is applied today to quantum cryptography is a sign of maturity for this technology,” explains [..] CEO of [..company..]

    That's an arms race, similar to what has been ongoing for 40 years in Smart Cards, often used nowadays for convenient cryptographic key distribution. Eve has blueprints for other attacks:

    • inducing Alice to make errors by blinding her side rather than Bob's;
    • probe the (assumed random and secret) orientation of Alice and/or Bob polarizers by remotely sending photons (perhaps entangled, and with whatever characteristic best fits the job) in-between the individual photons sent (typically regularly) by Alice;
    • predicting Alice's or Bob's RNG from earlier output (to reach the record rates reported in D.2, several gigabit/second of assumed perfect randomness are consumed by Alice; that's hundreds times more than common quantum sources);
    • classical TEMPEST information leaks or induced-faults targeting the state of the quantum gear, the current setup key, or the QKD outcome.
  2. Quantum and Classical assumptions compared

    Conventional cryptography achieves the equivalent of QDK only by relying on some mathematically unproven hypothesis. For symmetric (secret-key) cryptography, that can be broadly described as hardness of solving some combinatorial problem. Further, asymmetric (public-key) cryptography is required for turning a channel with integrity into one with confidentiality (something QC can do), and that relies on the hardness of solving some other problem; examples include integer factorization, discrete logarithm, or RLWE.

    There is wide consensus, but no mathematical proof, that (ignoring implementation issues) current conventional cryptography is currently secure; and that symmetric cryptography needs at most a doubling of the key size to become secure against future quantum computers hypothetically usable for problems of cryptographic interest. Which key size is required for which of the various problems used in asymmetric cryptography is an active research topic.

    The security of QC relies on physical hypothesis, where the security of conventional cryptography relies on mathematical hypothesis. Both kinds of hypothesis are not mathematically proven. But both are firmly established (at least when we restrict conventional cryptography to its symmetric branch). Any insecurity (beyond, inevitably, the humans involved) is likely to lie elsewhere: oversimplified theoretical model, undetected mistakes or backdoors in the implementation. The complexity of QC/QKD makes these mishaps more likely.

  3. Quantum Key Distribution's strongest point

    QC gives an insurance that classical cryptography does not. Arguably, if a data transfer protected by QC is secure when it takes place, and uses only mathematically proven cryptography, then no future progress will decipher that data. The argument is that even if the photons sent on the quantum channel could be stored (a trick that has been pulled) at time of the communication in hope of decryption in the future, the photons would not reach the quantum receptor, QKD would fail (with high insurance), actual data encryption would not occur, and the data would be safe.

    By contrast, the channels of classical cryptography can be passively eavesdropped and stored for hypothetical future decryption using superior technology. That's reasonable: even perfect forward secrecy won't resit a break of the symmetric cipher. Intercepts kept from the past that used a well-documented cipher with less than about 100-bit key are decipherable today with enough resources, 3DES (64-bit block, 111-bit key) will likely succumb, AES-128 can assuming mere stability of technical progress, AES-192 too if further assuming quantum computers usable for cryptanalysis, AES-256 also if we stop wondering about how and when.


F. Use cases for commercial Quantum Cryptography

The justified scientific recognition and the press coverage of QKD/QC helps sales, and is enough for targeting some markets:

  1. Experimental study of QKD/QC, which is of high scientific and educational value from both experimental quantum physics and applied cryptography/cryptanalysis/auditing/hacking perspectives. ID Quantique reports targeting this market, exclusively so for its most recent and fastest QKD device Clavis3.
  2. A segment of the computer security market: purchase-decision-makers in quest of prestige, reassurance, or theatrical effect. Quantum can be to crypto what gold is to audio, and silver to bullet.
  3. The funneling out of money for plausible cause. Expensive security equipment is good at that, usefulness is secondary, unconventionality no obstacle: see ADE 651.
  4. Cover for backdoor. QKD equipment is sold to supply keys for encryption of sensitive data. Knowing an easily exploitable vulnerability in the QKD/QC implementation (e.g. leak of shared key on classical channels, perhaps subtly by timing variation in sifting or reconciliation, accidentally or deliberately) can break an otherwise secure encrypted link.
  5. Cover for trojan. QKD/QC equipment has reasons to be in secure perimeter. It's cabinet is thus ideal to physically sneak-in a microphone, camera, spy gadget, or side-channel attack device (being physically connected to the targeted security equipment helps immensely).

It is harder to find a security problem that today's QC can solve (and penetrate the bulk of the market); many conditions must be met:

  • The confidentiality of some data to be transferred from point to point is of vital importance (at time of transfer, or later).
  • And the One Time Pad (which has successfully been used in that situation) is not an option; perhaps the means that must transport the shared key of QC with at least integrity won't transfer a 1TB memory stick full of randomness with integrity and confidentiality, or the data of vital importance is larger than 1TB; see Johny Mnemonic.
  • And QC is left usable despite D.1, D.2 (excluding the bandwidth issue which is adequately taken care by C.2), D.4, D.5 and D.6.

Assuming the above, then it is rational to think about using commercial QC as a supplement to classical cryptography; fortunately, we are not bound to choose between the two, and can get the best of both worlds on security, when it is acceptable to get the worst on availability.

Classical cryptography featuring perfect forward secrecy and robust cipher with large block and key is widely available. On the communication link it uses, it can be inserted an independently sourced commercial QC equipment, of course with independently managed setup keys for each of the two encryption means as in any sound use of multiple encryption. An auditor can ensure confidentiality is at least as good as without QC by merely ruling out trojan (see F.5), for a fee. Perhaps the reduction in simplicity and assurance of working on D-day is worth the price and added confidence in long term confidentiality, however tarnished it is by the use of classical cryptography without mathematical proof to reach acceptable throughput.

But it would be entirely irrational to rely solely on QC/QKD, given its immaturity, unconvincing security argument against adversaries not bound by the narrow physical hypothesis made, deep complexity when we account for the arsenal of classical cryptography necessary to make it work at all, tainted security track record for these reasons, poor auditability and recognition by practitioners, and requirement for the same inconvenient setup key management as classical cryptography.


Operational summary

Quantum Cryptography in principle performs the same tasks, and uses the same operational procedures as conventional cryptography, with no operational simplification whatsoever. In particular, the need for initially trusted material established by inconvenient human means remains.

QC relies on physics rather than mathematics when it comes to unproven hypothesis. That's a remarkable achievement and paradigm shift. But if that's a benefit, it is intangible, and did not help QC get a clean security track record, much less be widely recognized as useful by practitioners.

Integration of QC in current networks is utterly impractical: QC currently requires a dedicated fiber with practical range limit ≪500 km, or direct line of sight with no sunlight. That can only be extended with trusted facilities at each intermediary endpoint. Practical throughput is low, except when supplemented by conventional cryptography (then loosing some of the aforementioned intangible benefit).

Commercial QC equipment is complex, in part because it relies heavily on many classical mathematically provable cryptographic techniques. It is expensive, big, power-hungry, in low demand and stock, of unproven field reliability, seldom used in practice, and not recognized by security certification authorities.

QC removes the risk that future technological progress allows compromise of intercepts made earlier. It is worth consideration in complement (not replacement) of carefully vetted classical cryptography with independent secure setup procedure, for data which confidentiality is of utmost importance (especially if that's for decades), if we trust couriers for setup keys but not for the One Time Pads traditionally used for perfect secrecy in that situation.

$\endgroup$
  • 1
    $\begingroup$ @Paul Uszak: you should be convinced by the string ".. attack is prevented thanks to the use of a preestablished secret key in the emitter and the receiver" on page 9 of the ID Quantique marketing brochure linked in the answer. See also Is quantum key distribution safe against MITM attacks too?. About credibility of Swiss companies/government on security of crypto gear, it can't go much lower than it is after Cryto AG selling rigged cipher machines for years. $\endgroup$ – fgrieu Sep 5 '17 at 14:11
  • 1
    $\begingroup$ FYI, the one-time authenticator was invented by Edgar N. Gilbert, F. Jessie MacWilliams, and Neal J.A. Sloane, ‘Codes which detect deception’, Bell System Technical Journal 53(3), March 1974, pp. 405–424 (non-paywalled scan), several years before Carter and Wegman's research program on universal hashing. $\endgroup$ – Squeamish Ossifrage Sep 5 '17 at 15:26
  • 2
    $\begingroup$ But is this going to be easy to implement? Are we going to be switching to one-time pads sometime in the future or will this only be used in a limited number of scenarios? If the former, then cryptography will become very boring. $\endgroup$ – Melab Sep 8 '17 at 13:57
  • 2
    $\begingroup$ @PaulUszak That leaves infrastructure disruption as a way of defeating this. $\endgroup$ – Melab Sep 8 '17 at 14:29
  • 1
    $\begingroup$ @Paul Uszak: I explain, with sources, why QKD requires the same key ceremony as classical key distribution (B.3); and give reasons why it is impractical (D). Do you remain unconvinced ? I give use cases for QC/QKD: F.1 is serious and legitimate, and F.2 is a good fit for the Swiss referendum system. The one thing close to "blowing up the infrastructure" in my answer is D.1, but that's for using QKD, not "defeating" it. I give reasons why QKD can be defeated, and example that it has been: see e.g. "blinds the photon detector" in E, and the quotes there [updated]. $\endgroup$ – fgrieu Sep 18 '17 at 9:07
8
$\begingroup$

@fgrieu already wrote a little book, so I'll restrict my answer to a minimum to avoid repetitions. Think of this as an extended comment (which indeed wouldn't have fit the comment size limits).

What makes Quantum Cryptography secure?

… what makes it more secure than the classical version?

In classical crypto, things like three party key distribution protocols utilize challenge/response mechanisms, or time stamps, to prevent replay attacks. However challenge mechanisms require at least two communication rounds between the “trusted center” and participants, and the timestamp approach relies on the assumption of clock synchronization, which isn't very practical in distributed systems due to the unpredictable nature of network delays and potential hostile attacks.

Also, classical crypto cannot detect the existence of passive attacks such as eavesdropping. This fact can be used in Quantum Cryptography solutions to reduce the number of rounds of – for example – protocols based on challenge/response mechanisms to a trusted center.

On the other side of the Quantum Cryptography coin: public data exchanges require additional communication rounds between a sender and receiver and cost precious qubits, while classical cryptography provides convenient techniques that enable efficient key verification and user authentication. This explains why (at the time of writing this) most end-solutions tend to end up mixing both quantum crypto and classic cryptography to achieve their goal(s) in an optimal way.

$\endgroup$
5
$\begingroup$

My turn!

  • In classical cryptography between two peers over a channel such as the internet, an eavesdropper on the channel learns a transcript of information from which secrets could theoretically be derived.

    For example, the eavesdropper learns Diffie–Hellman public keys $g^a$ and $g^b$, which with unbounded computation could be used to recover the peer's conversation secret key $k = \operatorname{SHA-256}(g^a, g^b, g^{ab})$, which the peers use to encrypt their conversation with the cipher $\operatorname{AES}_k$. This conversation is probably about how to smash the state, because it's cheap and affordable by everyday crypto-anarchist cypherpunks.

    (Note: An adversary with unbounded computation could also figure out $k$ from $\operatorname{AES}_k(0)$, but we pretend the adversary only uses their magic unbounded computation for approved purposes like Diffie–Hellman.)

  • In quantum cryptography, the peers use a special channel over a dedicated fiber optic link that they assiduously guard with guns and lawyers and other forms of state violence. Over this channel they perform a joint quantum random number generation ceremony which is designed to have the property that anyone eavesdropping on the channel will make the ceremony fail, and so there's no transcript to attack with magic unbounded computation later on.

    On success, they get a key $k$, which the peers use to encrypt their conversation with the cipher $\operatorname{AES}_k$. This conversation is probably about how much money they have, because only Swiss banks can afford toys like these.

    (Note: An adversary who can get past all the guns and lawyers and other forms of state violence to eavesdrop on the fiber link can probably break into computers too, but we pretend the adversary uses ninjas only for approved purposes like carefully bending fiber optic cables past their index of refraction.)

I left out a couple parts: authenticating $k$, which is needed in both regimes and always done with other forms of classical cryptography;* and hypothetical breakthroughs of cryptanalysis, such as with a quantum computer, which is why classical cryptographers are busy having academic fights over whose post-quantum crypto has the coolest-sounding hard problem reduction before anyone standardizes it.


* A reader has alerted me to certain forms of quantum authentication, such as Christopher Portmann, ‘Quantum Authentication with Key Recycling’, IACR Cryptology ePrint Archive: Report 2017/119. This is curious because the one form of classical cryptography with a short key that can be unconditionally secure even against an adversary of unbounded computational power is the one-time authenticator, which is exactly what one would use here, as @fgrieu noted. I guess the advantage of quantum authentication is that it allows you to recycle the key, in contradistinction to the protocols advocated by wasteful antienvironmentalist consumerist classical cryptographers. But it still doesn't work over the internet. Pooh.

$\endgroup$
  • 1
    $\begingroup$ Fully OK on the first bullet, including limitation of use of magic (AES-256 might be safer from quantum computers than ECDH-P-521). I'm not sure about the second bullet, and the degree of pun. Isn't guarding the link squarely off-topic in crypto? And if we remove the guards, Eve cuts the fiber in the middle, installs two boxes obtained from ID Quantique there, and the ceremony of both peers succeeds (assuming the same setup key in the 4 boxes). I agree with: the quantum channel in QC can't be passively eavesdropped, making passive transcripts of other channels useless. $\endgroup$ – fgrieu Sep 8 '17 at 16:49
  • $\begingroup$ I hope there aren't any bullets involved, even though I mentioned guns! In both regimes the peers need to use classical cryptography to authenticate one another. Guns and lawyers do indeed usually fall outside the domain of cryptography, but as you observed, they are an essential part of the security of QKD against NITM attacks, and I see our old friend Mallory the NITM (nonbinary in the middle) has taken the additional step of disguising themself as a mere passive eavesdropper Eve! $\endgroup$ – Squeamish Ossifrage Sep 8 '17 at 17:00
  • $\begingroup$ @fgrieu I agree that "guarding the link" is off-topic in crypto...BUT it's a good reality check. Can the most advanced crypto in the world not be foiled by a key logger physically attached to your keyboard? Squeamish Ossifrage, You should adjust your perspective, because it's not malevolent nijas that you should be worried about, but rather the true rulers of the world...the janitors :) $\endgroup$ – Q-Club Sep 8 '17 at 23:12
4
$\begingroup$

There is some confusion regarding QKD. The confusion revolves around the underlying principle and it's nuts & bolts implementation in the physical world. The two are conflated, which I believe is unfair as QKD is an emerging technology so shouldn't be so harshly compared with centuries year old cipher principles.

So in this quantum version, what makes it more secure than the classical version?

QKD per se is unlike sending an electrical signal through a network cable. If the following is a QKDN like so

qkdn

Eve cannot avoid being noticed. This is the crux and often missed. She cannot eavesdrop without affecting the photon stream between Alice and Bob. This is fundamental to life, the universe and quantum mechanics and is called the Observer Effect.

...why can't Eve intercept this encrypted message and as usual try to figure out the key (which is a string of 0s and 1s) like in classical cryptography?

Eve doesn't have to figure out the message. She can just read it directly from the photon beam. But Alice and Bob will notice. They then either retry the transmission, or send out a ruthless search & destroy team to obliterate Eve. The point here is that no key exchange completes if Eve is listening. There is no such effect in an Ethernet cable. This is why the NSA can secretly tap all our phones, but not the photon stream within a QKDN.

Of course the whole QKD hardware has to operate in the physical world. That makes it susceptible to traditional attacks and compromises. It's important that people do not conflate the Observer Effect underpinning QKD with a server's resistance to a thermite grenade or a computer hacker.

$\endgroup$
  • $\begingroup$ Is a wireless quantum connection possible, or are we bounded by the usage of light? $\endgroup$ – Q-Club Sep 7 '17 at 1:32
  • $\begingroup$ @back_seat_driver Wireless (fibreless) yes, but not with radio. You need to send polarised photons for the Observer Effect to have effect. But you can therefore do it thru the air - see crypto.stackexchange.com/questions/50767/… $\endgroup$ – Paul Uszak Sep 7 '17 at 2:00
  • $\begingroup$ My understanding of how the observer effect ties in here is that when Eve tries to measure the polarization states, about half the time she'll use the wrong filter therefore destroying the original state of the photon. But this doesn't imply that Eve absolutely must get noticed right? Since she might by sheer luck use the correct polarization filter for every photon $\endgroup$ – lal lal Sep 7 '17 at 15:21
  • 1
    $\begingroup$ @lal lal: The drawing shows the path of the photons in QKD per BB84. The full BB84 (and the question) also has a classical channel in each direction. The security requires integrity of these channels. Even though, Eve can have some knowledge of the key. In secure applications, complex but provable crypto uses a pre-established secret key to make the distributed key arbitrarily close to perfect, and possibly produced continuously. BB84's great achievement is going from integrity to confidentiality, as DH does, but using physics rather than math as the only hypothesis without mathematical proof. $\endgroup$ – fgrieu Sep 8 '17 at 10:26
  • 2
    $\begingroup$ Paul, your are correct with "(Eve) cannot eavesdrop without affecting the photon stream between Alice and Bob. This is fundamental". Thinking this over again, and also the answer of @Squeamish Ossifrage , I (now) see that it prevents making an intercept now and keeping it for future decryption with better technology. I have changed my answer accordingly. $\endgroup$ – fgrieu Sep 9 '17 at 5:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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