Demystifying the information reconciliation protocol cascade

S. J. Wiesner (1983), Conjugate Coding, SIGACT News, Vol. 15, No. 1, pp. 78-88.

C. H. Bennett and G. Brassard (1984), Quantum Cryptography: Public Key Distribution and Coin Tossing, in IEEE Intl. Conf. on Computers, Systems, and Signal Processing, pp. 175-179.

C. H. Bennett, G. Brassard and J.-M. Roberts (1988), Privacy Amplification by Public Discussion, SIAM J. Comput., Vol. 17, No. 2, pp. 210-229.

C. H. Bennett, F. Bessette, G. Brassard, L. Salvail and J. Smolin (1992), Experimental Quantum Cryptography, J. Cryptology, Vol. 5, No. 1, pp. 3-28.

C. H. Bennett, G. Brassard, C. Crépeau and U. M. Maurer (1995), Generalized Privacy Amplification, IEEE Trans. Inf. Theory, Vol. 41, No. 6, pp. 1915-1923.

G. Brassard and L. Salvail (1994), Secret-Key Reconciliation by Public Discussion, in Advances in Cryptology -- EUROCRYPT '93, Workshop on the Theory and Application of Cryptographic Techniques, Vol. 765 of Lecture Notes in Computer Science, pp. 410-423. Springer Berlin Heidelberg.

M. Van Dijk (1997), Secret Key Sharing and Secret Key Generation, PhD thesis, Technische Universiteit Eindhoven.

M. Van Dijk and A. Koppelaar (1997), High Rate Reconciliation, in ISIT 1997, IEEE Intl. Symposium on Information Theory, p. 92.

K. Yamazaki, M. Osaki and O. Hirota (1998), On Reconciliation of Discrepant Sequences Shared Through Quantum Mechanical Channels, in Information Security, Vol. 1396 of Lecture Notes in Computer Science, pp. 345-356. Springer Berlin Heidelberg.

T. Sugimoto and K. Yamazaki (2000), A Study on Secret Key Reconciliation Protocol "Cascade", IEICE Trans. Fundam. Electron. Commun. Comput. Sci., Vol. E83-A, No. 10, pp. 1987-1991.

K. Chen (2000), Improvement of Reconciliation for Quantum Key Distribution, Master's thesis, Department of Computer Science, Rochester Institute of Technology, available online at https://ritdml.rit.edu/handle/1850/14810; last accessed July 7, 2014.

E. Furukawa and K. Yamazaki (2001), Application of existing perfect code to secret key reconciliation, in ISCIT 2001, Intl. Symposium on Communications and Information Technologies, pp 397-400.

A. Yamamura and H. Ishizuka (2001), Error Detection and Authentication in Quantum Key Distribution, in ACISP 2001, Information Security and Privacy, 6th Australasian Conf., Vol. 2119 of Lecture Notes in Computer Science, pp. 260-273. Springer Berlin Heidelberg.

K. Chen (2001), Reconciliation by Public Discussion: Throughput and Residue Error Rate, unpublished draft.

K.-C. Nguyen (2002), Extension des protocoles de réconciliation en cryptographie quantique, Master's thesis, Faculté des Sciences Appliquées, Université Libre de Bruxelles.

S. Liu (2002), Information-Theoretic Secret Key Agreement, PhD thesis, Technische Universiteit Eindhoven.

S. Liu, H. C. Van Tilborg and M. Van Dijk (2003), A Practical Protocol for Advantage Distillation and Information Reconciliation, Designs Codes Cryptogr., Vol. 30, No. 1, pp. 39-62.

W. T. Buttler, S. K. Lamoreaux, J. R. Torgerson, G. H. Nickel, C. H. Donahue and C. G. Peterson (2003), Fast, efficient error reconciliation for quantum cryptography, Phys. Rev. A, Vol. 67, No. 5, p. 052303.

H. Yan, T. Ren, X. Peng, X. Lin, W. Jiang, T. Liu and H. Guo (2008), Information Reconciliation Protocol in Quantum Key Distribution System, in ICNC 2008, 4th Intl. Conf. on Natural Computation, Vol. 3, pp. 637-641.

J. Han and X. Qian (2009), Auto-adaptive interval selection for quantum key distribution, Quantum Inform. Comput., Vol. 9, No. 7&8, pp. 693-700.

R. Ii-Yung (2013), A probabilistic analysis of Binary and Cascade, unpublished manuscript, available online at http://math.uchicago.edu/~may/REU2013/REUPapers/Ng.pdf; last accessed July 7, 2014.

R. W. Hamming (1950), Error Detecting and Error Correcting Codes, Bell Labs Tech. J., Vol. 29, No. 2, pp. 147-160.

N. Bonello, S. Chen and L. Hanzo (2011), Design of Low-Density Parity-Check Codes: An overview, IEEE Veh. Technol. Mag., Vol. 6, No. 4, pp. 16-23.

S. Seet, R. Ii-Yung and K. Khoo (2013), An Accurate Analysis of the BINARY Information Reconciliation Protocol by Generating Functions, QCrypt 2013, 3rd Intl. Conf. on Quantum Cryptography.

T. B. Pedersen and M. Toyran (2014), High Performance Information Reconciliation for QKD with CASCADE, Quantum Inform. Comput., to appear, arXiv:1307.7829 [quant-ph].

D. S. Slepian and J. K. Wolf (1973), Noiseless Coding of Correlated Information Sources, IEEE Trans. Inf. Theory, 19 (4), pp. 471-480.

C. Crépeau (1995), Réconciliation et Distillation Publiques de Secret, unpublished manuscript, available online at http://www.cs.mcgill.ca/~crepeau/; last accessed July 7, 2014.

This is a crucial issue for the application of Cascade in QKD. Information leakage, e.g., see Eq. (7), is a quantity to be subtracted from the raw key in the privacy amplification step of the post-processing protocol. Information leakage in turn depends on the ratio of the transmitted information and hence on the information efficiency f_EC (cf. Eq. (2); the theoretically optimal value of the latter being equal to 1). The main question then is how to estimate the information leakage of Cascade. Our approach here is that if a parity of a subblock of one of the parties (Alice) is sent to the other (Bob) and he responds with the parity of the same subblock, then the overall leakage is 1 bit. This is by no means self-evident as in fact two bits are leaked and in principle the eavesdropper could make use of both of them. If so, the leakage would double and the usage of Cascade and any two-way protocol in general would be highly penalized during privacy ampli_cation. Fortunately this is not the case, at least for BB84. In [32] it is shown that the information leakage in the discussed case is indeed 1 bit for arbitrary eavesdropper attacks. The author puts forward the approach of encrypting the reconciliation communication exchange by one time pad, a procedure that consumes key and is thus, from an overall key generation balance point of view, equivalent to reducing an equal amount of key during privacy amplification. One of the results in [32] is that for BB84 one can encrypt BOTH parities discussed above by the same bit. This implies that in this case the information leakage due to Bob's answer does not need to be taken into account during privacy amplification and it is the leakage of information, due to Alice's communication alone that is relevant for Cascade performance for BB84.

G. Van Assche (2005), Information-Theoretic Aspects of Quantum Key Distribution, PhD thesis, Faculté des Sciences Appliquées, Université Libre de Bruxelles.

G. Van Assche (2006), Quantum Cryptography and Secret-Key Distillation, Cambridge University Press.

A. R. Conn, K. Scheinberg and L. N. Vicente (2009), Introduction to Derivative-Free Optimization, Society for Industrial and Applied Mathematics, Philadelphia.

H.-K. Lo (2003), Method for decoupling error correction from privacy amplification, New J. Phys., Vol. 5, pp. 36.1-36.24.