The descriptions of the BICONF information reconciliation protocol in the literature appear to be inconsistent.
All descriptions agree that in each iteration Alice and Bob should select a random subset of bits of the key, that Alice should tell Bob what the correct parity of the chosen subset is, and that Bob should run BINARY on the selected subset if the correct parity differs from the current parity.
However, some descriptions (e.g. [2], [3]) explicitly say that Bob should also run BINARY on the complementary bits subset if the parity differs on the chosen bits subset.
Other descriptions (e.g. [4], [5]) only mention running BINARY on the chosen bits subset and never mention running BINARY on the complementary bits subset.
My questions are:
Should I or should I not also run BINARY on the complementary bits subset? In other words, which of the two conflicting descriptions is correct?
If yes, it appears necessary that Alice must also reveal the correct parity of the complementary bits subset (*). The fact that the chosen bits subset contains an odd number of errors says nothing about the number of errors in the complementary bits subset. The number of errors in the complementary bits subset could very well be zero, in which case it is not correct for Bob to run BINARY on the complementary bits subset. Is my understanding correct that more parities will need to be revealed?
I would like to consult the original paper where BICONF was introduced, which is apparently [1], to see what it says. Is there an online PDF version for this available (I could not find any)?
(*) = Or alternatively, we can infer the correct parity of the complementary subset from the correct parity of the entire key, which in turn can be inferred from the correct parities of all the top-level blocks in the earlier Cascade iterations.
References:
[1] Tomohiro Sugimoto and Kouichi Yamazaki. A study on secret key reconciliation protocol "cascade". IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, E83-A(10), 2000.
[2] JesusMartinez-Mateo,ChristophPacher,MomtchilPeev,AlexCiurana,andVicenteMartin. Demystifying the Information Reconciliation Protocol Cascade. arXiv:1407.3257 [quant-ph], Jul 2014. https://arxiv.org/pdf/1407.3257.pdf Section 3.2 page 8: Then, they compute and exchange the parity value of this subset, and perform two dichotomic searches if their parities differ, one for the chosen subset and the other for the complementary subset (i.e., the subset of bits that were not selected).
[3] André Reis. Quantum Key Distribution Post Processing - A study on the Information Reconciliation Cascade Protocol, July 2019. https://repositorio-aberto.up.pt/bitstream/10216/121965/2/347567.pdf Section 3.1.2 page 16: If the parity of Bob’s subset is different, they execute BINARY once for the chosen subset and another for the complementary subset.
[4] Gilles Brassard and Louis Salvail. Secret-Key Reconciliation by Public Discussion. In Advances in Cryptology — EUROCRYPT ’93, pages 410–423. Springer Berlin Heidelberg, Berlin, Heidelberg, 1993. https://link.springer.com/content/pdf/10.1007%2F3-540-48285-7_35.pdf Section 6.2 page 418: Each time CONFIRM shows a subset for which Alice’s and Bob’s string have different parities they run BINARY on this subset and thus correct an error.
[5] Shengli Liu. Information-Theoretic Secret Key Agreement, Feb 2002. https://pure.tue.nl/ws/files/1977072/200210541.pdf. Section 2.3.1 page 22: Then Alice tells Bob the parity of her subset, and Bob checks whether his subset has the same parity. The primitive ends in case of identical parity, otherwise a binary search is performed to locate an error.
