# Reconciliation (permutation, parity)

1. May 30, 2004

### Chen

I am reading through this paper and one stage has got me stumbled:
http://www.cs.umbc.edu/~lomonaco/lecturenotes/9811056.pdf [Broken]
The part I don't understand is 4.2.3 Phase 3 of Stage 2. Extraction of reconciled key on page 17.

I'm pretty sure this is purely mathematical stuff, so you don't need any knowledge of the quantum mess that surrounds it. I simply don't understand things like reconciliation, permutation, parity checks, etc. If someone could explain these ideas and that paragraph in general, or even just point to some place that does, I would be very grateful.

Thanks,

Last edited by a moderator: May 1, 2017
2. May 30, 2004

### Chen

Also here:
http://www.ai.sri.com/~goldwate/quantum.html
It says "Actual photon emitters can generate pulses of light with a given average number, m, of photons per pulse, but not necessarily exactly that number each time. ... If m is significantly less than 1". How can a photon emitter emit "significantly less than 1" photon per pulse?!

3. May 30, 2004

### Chen

I am trying to make sense of that first PDF myself, I still don't quite understand what a random permutation is but I'm trying to understand the whole thing step by step.

"Next Alice and Bob partition the remnant raw key into blocks of length l, where the length l is chosen so that blocks of this length are unlikely to contain more than one error."
Alice and Bob found the error rate R earlier. Let's say the error rate is 10%, they want to choose blocks of no more than 10 bits, because then they arey are more likely to contain more than one error? Am I on track here?

"For each of these blocks, Alice and Bob publicly compare parity checks, making sure each time to discard the last bit of the compared block."
Ok, so here they basically add up all bits in each block and compare the last bit. I.e if they had a block of 101101, they add the bits together for a parity of 0 and then compare it with each other. After that, they remove the last bit of the block so it becomes just 10110 (or maybe 01101? Or does it matter?). I'm guessing this is done to prevent an eavesdropper from making up the data, but I'm not sure how (help).

"Each time a overall parity check does not agree, Alice and Bob initate a binary search for the error, i.e., bisecting the block into two subblocks, publicly comparing the parities for each of these subblocks, discarding the right most bit of each subblock."
Ok, so let's say Alice has a block of 10110101 but Bob has a block of 10110001. The parities don't match so they divide the block into two smaller ones - Alice has 1011 and 0101 and Bob has 1011 and 0001. They compare the parities of the first subblock and see that it matches, so the error must be with the second subblock... and so on and so forth until they find the bad bit.

And this is where I get lost again.

4. May 31, 2004

### Chen

Does the random permutation step basically mean I need to shuffle the bits? For example if I have this: 10011010 I make a random permutation of {1,8,2,6,3,5,7,4} and map the bits to that: 10000111. Is that correct?