Editing Quantum key distribution (section)

== Information reconciliation and privacy amplification ==
The quantum key distribution protocols described above provide Alice and Bob with nearly identical shared keys, and also with an estimate of the discrepancy between the keys. These differences can be caused by eavesdropping, but also by imperfections in the transmission line and detectors. As it is impossible to distinguish between these two types of errors, guaranteed security requires the assumption that all errors are due to eavesdropping. Provided the error rate between the keys is lower than a certain threshold (27.6% as of 2002<ref>{{cite journal | last1 = Chau | first1 = H.F. | year = 2002 | title = Practical scheme to share a secret key through a quantum channel with a 27.6% bit error rate | url = https://journals.aps.org/pra/pdf/10.1103/PhysRevA.66.060302| journal = Physical Review A | volume = 66 | issue = 6 | page = 60302 | doi = 10.1103/PhysRevA.66.060302 | bibcode = 2002PhRvA..66f0302C | access-date = 4 September 2020| hdl = 10722/43370 | hdl-access = free }}</ref>), two steps can be performed to first remove the erroneous bits and then reduce Eve's knowledge of the key to an arbitrary small value. These two steps are known as '''information reconciliation''' and '''privacy amplification''' respectively, and were first described in 1988.<ref>{{cite journal | last1 = Bennett | first1 = C. H. | last2 = Brassard | last3 = Robert | first2 = J. M. | year = 1988 | title = Privacy Amplification by Public Discussion | url = https://citeseerx.ist.psu.edu/document?repid=rep1&type=pdf&doi=594dfbdf3e3ba9df94a31ab9cb1e23912773b98a| journal = SIAM J. Comput. | volume = 17 | issue = 2| pages = 210–229 | doi = 10.1137/0217014}}</ref>

'''Information reconciliation''' is a form of error correction carried out between Alice and Bob's keys, in order to ensure both keys are identical. It is conducted over the public channel and as such it is vital to minimise the information sent about each key, as this can be read by Eve. A common protocol used for information reconciliation is the '''cascade protocol''', proposed in 1994.<ref>{{cite book |last1=Brassard |first1=G. |last2=Salvail |first2=L. |chapter=Secret-key reconciliation by public discussion |chapter-url=https://link.springer.com/chapter/10.1007/3-540-48285-7_35 |doi=10.1007/3-540-48285-7_35 |title=Workshop on the Theory and Application of Cryptographic Techniques |publisher=Springer |date=1993 |isbn=3-540-48285-7 |pages=410–423 }}</ref> This operates in several rounds, with both keys divided into blocks in each round and the [[parity (telecommunication)|parity]] of those blocks compared. If a difference in parity is found then a [[binary search]] is performed to find and correct the error. If an error is found in a block from a previous round that had correct parity then another error must be contained in that block; this error is found and corrected as before. This process is repeated recursively, which is the source of the cascade name. After all blocks have been compared, Alice and Bob both reorder their keys in the same random way, and a new round begins. At the end of multiple rounds Alice and Bob have identical keys with high probability; however, Eve has additional information about the key from the parity information exchanged. However, from a [[coding theory]] point of view information reconciliation is essentially source coding with side information. In consequence any coding scheme that works for this problem can be used for information reconciliation. Lately turbocodes,<ref>{{cite arXiv |first1= Kim-Chi |last1=Nguyen |first2= Gilles |last2=Van Assche |first3= Nicolas J. |last3= Cerf |title= Side-Information Coding with Turbo Codes and its Application to Quantum Key Distribution |date= 10–13 October 2004 |eprint= cs/0406001}} Parma, Italy.</ref> LDPC codes<ref>{{cite journal | last1 = Elkouss | first1 = D. | last2 = Martinez-Mateo | first2 = J. | last3 = Martin | first3 = V. | year = 2010 | title = Information reconciliation for quantum key distribution | url = http://www.dma.fi.upm.es/jmartinez/doc/qic-11-34_0226-0238.pdf| journal = Quantum Information & Computation | volume = 11 | pages = 226–238 | doi = 10.26421/QIC11.3-4-3 | archive-url = https://web.archive.org/web/20131215041349/http://www.dma.fi.upm.es/jmartinez/doc/qic-11-34_0226-0238.pdf | archive-date = 15 December 2013 | access-date = 4 September 2020}}</ref> and polar codes<ref>{{Cite arXiv |eprint = 1204.5882v3|last1 = Nguyen|first1 = Kim-Chi|title = High Performance Error Correction for Quantum Key Distribution using Polar Codes|author2 = Gilles Van Assche|last3 = Cerf|first3 = Nicolas J.|class = quant-ph|year = 2012}}</ref> have been used for this purpose improving the efficiency of the cascade protocol.

'''Privacy amplification''' is a method for reducing (and effectively eliminating) Eve's partial information about Alice and Bob's key. This partial information could have been gained both by eavesdropping on the quantum channel during key transmission (thus introducing detectable errors), and on the public channel during information reconciliation (where it is assumed Eve gains all possible parity information). Privacy amplification uses Alice and Bob's key to produce a new, shorter key, in such a way that Eve has only negligible information about the new key. This is performed using a [[randomness extractor]], for example, by applying a [[universal hashing|universal hash function]], chosen at random from a publicly known set of such functions, which takes as its input a binary string of length equal to the key and outputs a binary string of a chosen shorter length. The amount by which this new key is shortened is calculated, based on how much information Eve could have gained about the old key (which is known due to the errors this would introduce), in order to reduce the probability of Eve having any knowledge of the new key to a very low value.