Quantum cryptography

from Wikipedia, the free encyclopedia

Quantum cryptography is the use of quantum mechanical effects (especially in quantum communication and quantum computers ) as part of cryptographic processes or for cryptanalysis .

The best known examples of quantum cryptography are the quantum key exchange and the (not yet practicable) Shor algorithm for factoring large numbers. Quantum cryptography allows the development of methods that are classically impossible (i.e. without the use of quantum effects). For example, an eavesdropper can be discovered in a quantum channel because its measurement influences the data sent.

Quantum key exchange

The best known and commercially available application of quantum cryptography is quantum key exchange. Stephen Wiesner proposed information transfer based on quantum effects in the 1970s, but was only able to publish this proposal in 1983. Charles H. Bennett and Gilles Brassard introduced the first quantum key exchange protocol in 1984 (BB84). The aim of a key exchange protocol is that two parties (usually called Alice and Bob ) agree on a shared secret key without a third party (Eve) receiving information about the key, even if it is listening to the communication channel. In the case of quantum key exchange, this is achieved through the use of a quantum channel, as Eve cannot listen to messages passing through this channel without changing them. Artur Ekert introduced a key exchange with quantum entanglement in 1991.

The security of a quantum key exchange protocol can also be proven against unrestricted attackers, which is impossible with a classic key exchange protocol. The only assumptions needed are the validity of the laws of quantum mechanics and a way for Alice and Bob to authenticate each other to rule out a man-in-the-middle attack . In addition, it is assumed in the security evidence that the communication partners are not bugged or secretly observed and that the devices used (e.g. photodetectors , photon sources, random number generators ) function as specified. The second of these assumptions is not necessary when using methods called " device-independent " ( device-independent quantum cryptography ).

What the security proofs ultimately provide is a guarantee of the form: "If the prerequisites for this proof apply, there is a (very small) probability that the opponent will know more than about the agreed key." The sizes depend on sizes that can be determined within the framework of the protocol and before the key is used.

Quantum Commitment Process

The discovery of the quantum key exchange raised hopes that other cryptographic methods could also be made secure against unrestricted attackers. A fundamental primitive are commitment procedures that allow one party to commit to a value in relation to another party in such a way that it cannot change the value, but the other party learns nothing about the value until it is revealed . Together with a quantum channel, a quantum commitment procedure can be used to construct a primitive called Oblivious Transfer (OT) that is secure against unrestricted attackers. Oblivious Transfer is a complete primitive as it allows the safe implementation of any distributed computation ( secure multi-party computation ). (The results of Crépeau and Kilian and Kilian alone are not yet sufficient to construct general protocols for reliable multi-party computation from a quantum commitment and a quantum channel, since the "composability" is not given, so it is not guaranteed that the simultaneous use of two secure primitives did not create any security holes. However, composability was demonstrated later.)

First attempts to construct quantum commitment procedures were flawed. It could be shown that it is impossible to construct quantum commitment procedures that are secure against unrestricted attackers. However, the use of quantum channels makes it possible to construct commitment procedures under much weaker assumptions than are traditionally necessary.

Bounded and noisy quantum storage model

One way of obtaining quantum commitment and quantum OT that are secure against attackers without any runtime restrictions is to limit the attacker's storage space. In Bounded quantum storage model (BQSM) the attacker may store any amount of information classic Although, its quantum memory is, however, by a constant Q limited.

Secure commitment and OT protocols can be constructed in the BQSM. The underlying idea is that the communicating parties exchange more than Q qubits . Since the attacker can store a maximum of Q of it, he must measure or discard the rest. This allows the above-mentioned impossibility result to be circumvented. The honest protocol participants do not have to store any quantum information, similar to the quantum key exchange; In principle, the protocols can therefore already be implemented with the existing technology. The case transferred amount of data is a constant multiple of the barrier Q .

The advantage of the BQSM is that the limited quantum memory assumption is quite realistic. With today's technology, storing a single qubit for a long enough time is a challenge. The exact meaning of “sufficiently long” depends on the protocol, but the period can be extended as required by inserting a pause.

A generalization of the BQSM is the noisy storage model by Wehner, Schaffner and Terhal. In this model, the quantum memory of the attacker is not limited, but it will (as noisy channel English noisy channel ) models, d. that is, it is assumed that bit errors occur when storing. The strength of the noise is a parameter; for sufficiently strong noise, the same primitives can be implemented as in the BQSM, which can be viewed as a special case.

Under classical conditions, results similar to those in BQSM can be achieved if the size of the classical memory is assumed to be limited. The honest protocol participants must, however, save data on the order of the square root of the limit. Since the barrier for the attacker must be set correspondingly high with today's storage prices, these protocols are not practical.

Position-based quantum cryptography

Location-based cryptography allows a party's whereabouts to be used as a credential . For example, a message can be encrypted so that it can only be read when the recipient is in a certain location. In position verification, a party wants to prove that they are in a specific location. This is impossible with classic protocols when all verifying parties are dishonest and work together. So there can only be procedures that are secure against attackers who are restricted in any way.

The first position-based quantum methods were investigated in 2002 under the name Quantum Tagging , but were not published until 2010. After further protocols were presented in 2010, a general impossibility result could be shown: If the attackers share an entangled quantum state of any size , they can always pretend to be in a certain position. However, this does not preclude the existence of protocols in a bounded or noisy quantum storage model.

Post-quantum cryptography

At present, only extremely limited quantum computers can be constructed. Since it is conceivable that quantum computers that can be used in practice can be built in the future, it is important to investigate cryptographic methods that are also secure against attackers with a quantum computer. This area of ​​research is called post-quantum cryptography.

Web links

Wiktionary: Quantum Cryptography  - explanations of meanings, word origins, synonyms, translations

Individual evidence

  1. 5 Quantum Cryptography and Quantum Encryption Companies. nanalyze.com, accessed on February 16, 2018 (English).
  2. Stephen Wiesner: Conjugate coding . In: ACM (Ed.): SIGACT News . 15, No. 1, New York, NY, USA, 1983, ISSN 0163-5700 , pp. 78-88. doi : 10.1145 / 1008908.1008920 . Manuscript written around ~ 1970  
  3. ^ Charles H. Bennett, Gilles Brassard: Quantum cryptography: Public-key distribution and coin tossing . In: Proceedings of IEEE International Conference on Computers, Systems and Signal Processing 1984 . IEEE Computer Society, 1984, pp. 175-179. (reprinted in: Quantum cryptography: Public-key distribution and coin tossing . In: Theoretical Computer Science . 560, No. P1, 2014, pp. 7–11. doi : 10.1016 / j.tcs.2014.05.025 . )
  4. Umesh Vazirani, Thomas Vidick: Fully Device-Independent Quantum Key Distribution . In: Phys. Rev. Lett. tape 113 , 2014, pp. 140501 , doi : 10.1103 / PhysRevLett.113.140501 , arxiv : 1210.1810 .
  5. Valerio Scarani, Helle Bechmann-Pasquinucci, Nicolas J. Cerf, Miloslav Dusek, Norbert Lutkenhaus, Momtchil Peev: The Security of Practical Quantum Key Distribution . In: Rev. Mod. Phys. tape 81 , 2009, p. 1301 , doi : 10.1103 / RevModPhys.81.1301 , arxiv : 0802.4155 .
  6. ^ A b Claude Crépeau, Kilian Joe: Achieving Oblivious Transfer Using Weakened Security Assumptions (Extended Abstract) . In: FOCS 1988. IEEE, 1988, pp. 42-52.
  7. ^ A b Kilian Joe: Founding cryptography on oblivious transfer . In: STOC 1988. ACM, 1988, pp. 20-31. doi : 10.1145 / 62212.62215
  8. Brassard Gilles, Claude Crépeau, Jozsa Richard, Denis Langlois: A Quantum Bit Commitment Scheme Provably Unbreakable by both Parties . In: FOCS 1993. IEEE, 1993, pp. 362-371.
  9. a b Dominic Mayers: Unconditionally Secure Quantum Bit Commitment is Impossible . In: APS (Ed.): Physical Review Letters . 78, No. 17, 1997, pp. 3414-3417. arxiv : quant-ph / 9605044 . bibcode : 1997PhRvL..78.3414M . doi : 10.1103 / PhysRevLett.78.3414 .
  10. Ivan Damgård, Serge Fehr, Louis Salvail, Christian Schaffner: Cryptography In the Bounded Quantum-Storage Model . In: FOCS 2005. IEEE, 2005, pp. 449-458. arxiv : quant-ph / 0508222 .
  11. ^ Stephanie Wehner, Christian Schaffner, Barbara M. Terhal: Cryptography from Noisy Storage . In: APS (Ed.): Physical Review Letters . 100, No. 22, 2008, p. 220502. arxiv : 0711.2895 . bibcode : 2008PhRvL.100v0502W . doi : 10.1103 / PhysRevLett.100.220502 . PMID 18643410 .
  12. ^ Robert Koenig, Stephanie Wehner, Juerg Wullschleger: Unconditional security from noisy quantum storage . In: .. IEEE Trans Inf Th. . 58, No. 3, September, pp. 1962-1984. arxiv : 0906.1030 .
  13. ^ Christian Cachin, Claude Crépeau, Julien Marcil: Oblivious Transfer with a Memory-Bounded Receiver . In: FOCS 1998. IEEE, 1998, pp. 493-502.
  14. ^ Stefan Dziembowski, Maurer Ueli: On Generating the Initial Key in the Bounded-Storage Model . In: Eurocrypt 2004. Springer, 2004, pp. 126-137.
  15. Nishanth Chandran, Moriarty, Ryan; Goyal, Vipul; Ostrovsky, Rafail: Position-Based Cryptography 2009. A full version is available at IACR eprint: 2009/364 .
  16. ^ Adrian Kent, Bill Munro, Tim Spiller: Quantum Tagging with Cryptographically Secure Tags . In: Phys. Rev. A . 84, 2011, p. 012326. arxiv : 1008.2147 .
  17. Hoi-Kwan Lau, Hoi-Kwong Lo: Insecurity of position-based quantum-cryptography protocols against entanglement attacks . In: APS (ed.): Physical Review A . 83, 2010, p. 012322. arxiv : 1009.2256 . doi : 10.1103 / PhysRevA.83.012322 .
  18. Robert A. Malaney: Location-dependent communications using quantum entanglement . In: Physical Review A . 81, 2010, p. 042319. doi : 10.1103 / PhysRevA.81.042319 .
  19. Harry Buhrman, Chandran, Nishanth; Fehr, Serge; Gelles, Ran; Goyal, Vipul; Ostrovsky, Rafail; Schaffner, Christian: Position-Based Quantum Cryptography: Impossibility and Constructions . In: SIAM J. Comput. . 43, No. 1, September, pp. 150-178. arxiv : 1009.2490 . doi : 10.1137 / 130913687 .