The BICONF Primitive Sample Clauses

The BICONF Primitive. The BICONF primitive was first introduced in [2] (it is a combination of two prim- itives named BINARY and CONFIRM, see [7] for more details). It was used as a primitive in [7, 76, 73, 77]. It deals with the case when there are only a small number of errors or no errors left in Bob’s string (Xxxxx and Xxx xxx not know that they are in this case). Xxxxx and Xxx begin by choosing the same randomly generated subset of bits from their strings. Then Xxxxx 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. If Xxxxx’s string is different from Bob’s, the BICONF primitive will detect this with probability 1/2; if the two strings are identical, the primitive says so with probability 1. Therefore, if the primitive is executed sufficiently many times, say l times, with the same parities for Xxxxx and Xxx, Xxxxx and Xxx will be rightly convinced that their strings are identical with probability at least 1 − 2—l.

The BICONF Primitive. In our protocol, after Pass t + 1, the average bit error rate p(t+1) (according to simulation) is so small that BICONF passes are enough to eliminate the remaining errors. The difference between BICONF pass and BICONF primitives is that if an error is found in some BICONF pass, other errors may be located by looking back to the parity check vectors of previous passes.