format: text

text:
# Fast, efficient error reconciliation for quantum cryptography

## I Introduction

Quantum cryptography  presents special problems in regard to error correction of noisy quantum communications. Under the constraint that the public channel can be authenticated, and the assumption that all public communications can be eavesdropped, classical information on the exchanged qubits must be revealed through a series of public discussions to test the quantum key integrity and to remove the errors. Discrepancies within the qubits, observed as errors, must be treated as having been introduced by a hostile eavesdropper; the eavesdropper is generally referred to as Eve and labeled E in this work.

In a classical environment all errors can always be removed with the condition that to remove all errors one may have to reveal all information. However, within the secrecy framework imposed by quantum key distribution (QKD), revealed information reduces privacy and the effective channel capacity. Because of this great care must be taken to reveal a minimal amount of information to remove errors from quantum key while accounting for the leaked information to ensure key integrity after errors are removed.

Within this context of QKD, the two parties that exchange qubits over a quantum channel (Alice (A) and Bob (B) is the notation typically used within the quantum cryptography community) must have a fast and efficient method to mend the quantum key; in addition, they must also reduce E’s knowledge gained during public discussions to a vanishingly small amount. These constraints require that any error reconciliation protocol will also need supporting protocols to provide a complete framework for quantum cryptographic security. That is, a useable QKD system will comprise a quantum-key transmitter (A) and receiver (B), and a series of protocols to remove errors and account for and mitigate the information leakage attributable to E. The series of protocols includes , but is not necessarily limited to the following: error-reconciliation , privacy amplification  and signature authentication .

In addition to these protocols, we acknowledge a protocol generally formulated in  that we refer to as privacy maintenance. We also note that the predecessor to CASCADE  — the best known and probably the most widely used error reconciliation protocol — is also generally formulated in  and is characterized by a binary search; here we refer to the binary search, which is a major element of CASCADE, as BINARY. A fundamental difference between BINARY and CASCADE is that CASCADE neglects privacy maintenance: all data are retained until the necessary privacy amplification is performed on the error-free data. We observe that the reconciliation process is more efficient if privacy maintenance is implemented during reconciliation as will become obvious in the following discussion.

Finally, this work introduces a new error reconciliation protocol that uses a Hamming code  to remove errors. We refer to this protocol as Winnow. Winnow is characterized by the application of a parity test, a conditional Hamming hash, and privacy maintenance.

## II Hamming Error Detection and Correction

The application of the Hamming hash function for error correction  is illustrated as follows:

First, after A and B exchange qubits on the quantum channel, A and B then divide their random bits into blocks of length $`N_h=2^m1`$. (Due to the 1:1 correlation of these data, we henceforth refer to these blocks as a single data- or bit-block.) The $`m`$bit ($`m3`$) syndromes $`S_a`$ and $`S_b`$ are then calculated, where $`S_a`$ and $`S_b`$ respectively depend only on A’s or B’s bits in a particular block.

Next, B transmits his syndrome to A and errors are only discovered if the syndrome difference $`S_d`$ (exclusive or of $`S_a`$ with $`S_b`$) is non-zero:

$$S_d=S_aS_b\{0\}^m\text{.}$$
(1)
Finally, $`m`$ bits are deleted from each bit block to eliminate the potential loss of privacy to E due to the (classical) communication of B’s syndromes: $`m`$ bits of information are revealed on each block for which $`S_b`$ is revealed reducing the channel capacity per symbol by $`m/N_h`$.

Specifically, data privacy is maintained by removal of $`m`$ bits from each block at the $`\{2^j\}`$ positions where $`j\{0,\mathrm{},m1\}`$. These bits are independent in the syndrome calculations as seen below in the matrix $`h^{(m)}`$:

$$h^{(3)}=\left[\begin{array}{ccccccc}1& 0& 1& 0& 1& 0& 1\\ 0& 1& 1& 0& 0& 1& 1\\ 0& 0& 0& 1& 1& 1& 1\end{array}\right]\text{,}$$
(2)
where for this particular matrix, $`m3`$. We refer to the operation of discarding bits in this manner  as privacy maintenance.

As a final comment on Eq. 2, note that the transpose of $`h^{(3)}\left[h^{(3)}\right]^T`$ are the binary equivalent numbers $`1`$ to $`7`$, and is generalized such that $`[h^{(m)})]^T\{1,\mathrm{},(2^m1)\}`$, $`N_h`$ binary numbers.

The matrix $`h^{(m)}`$ is a special form of hash function  and is represented by:

$$h_{i,j}^{(m)}=\frac{j}{2^{i1}}\left(\mathrm{mod}\mathrm{\hspace{0.33em}2}\right)\text{,}$$
(3)
where $`i\{1,\mathrm{},m\}`$, and $`j\{1,\mathrm{},N_h\}`$; arithmetic is modulo 2.

The Hamming algorithm always corrects any single error within any $`N_h`$-bit block, but the effect of the Hamming algorithm, which is related to the syndromes and privacy maintenance, is less clear in the event that more than one error exists in a bit block. Such considerations are now discussed in detail in terms of the syndromes.

The syndromes $`S_a`$ and $`S_b`$ are formed by contraction of the $`N_h`$bit blocks with the matrix $`h^{(m)}`$:

$$S_i=\left(\underset{j=1}{\overset{N_h}{}}X_jh_{i,j}^{(m)}\right)\left(\mathrm{mod}\mathrm{\hspace{0.33em}2}\right)\{0,1\}^m\text{,}$$
(4)
where subscript $`i`$ represents syndrome bit $`i`$ in the $`m`$-bit binary syndrome, $`X_j`$ represents bit j $``$ A’s or B’s block, and $`S=\{S_i\}`$ is the binary syndrome value of either B’s or A’s block. Understanding the effect of the syndromes in locating and correcting errors is crucial to assessing the performance of Hamming, and thus Winnow.

The syndrome difference (Eq. 1) defines a binary number that gives the location of a single bit in A’s or B’s code word that when toggled from $`01`$ or from $`10`$ affects the syndrome difference $`S_d`$ such that when the syndrome difference is recalculated it gives the binary number $`S_d^{}\{0\}^m`$. For example, if $`S_d\{0\}^m`$, then $`S_d`$ is an $`m`$-bit binary number whose value gives the location of a single bit in either A’s or B’s code-word to add exclusive or with the orignal bit value. After that bit value is changed, then the new syndrome for that code word is then calculated (e.g. $`S_A^{}`$) and added (again, exclusive or) to the original syndrome for the other code word ($`S_B`$ in this example). The result is that the changing of the single bit indicated by the non-zero syndrome difference in the one code-word either corrects an error, or introduces another, in that code word. This is no great mystery but rather reflects the fact that Hamming codes are n-k codes. In this case, $`n=2^m1`$ relates the number of bits in each code word ($`N_h`$), and $`k=nm`$ relates the channel capacity (the channel capacity is $`k/nk/N_h`$ per bit) given the code (a Hamming code in this discussion).

In an n-k Hamming code, there are $`2^{(2^m)}`$ unique code words characterized by $`2^m`$ unique syndromes; further, there are $`2^k`$ code words with the same syndrome. Because this code can correct $`1`$ error, it has a minimum Hamming distance of $`d=3`$. This also means it can detect at least $`2`$ errors. In fact the Hamming distance $`d`$ for the Hamming code is $`d3`$.

By definition, a code word with a single error will have $`S_d\{0\}^m`$ (can obviously detect a single error if it can correct a single error). In addition, if a code word has exactly $`2`$ errors then by definition $`S_d\{0\}^m`$ (can detect at least $`2`$ errors if it can correct a single error). Therefore, if a code word has exactly $`2`$ errors, then after applying the Hamming algorithm, and after changing the bit value indicated by $`S_d`$, the code word will finish with exactly $`3`$ errors. The proof is by contradiction: If a code word with $`2`$ errors finished with $`1`$ error (an error was corrected), then the new syndrome difference would be non-zero! Contradiction also proves that $`1`$-error is corrected if there is exactly $`1`$ error: If an error was introduced the syndrome difference would again be non-zero. Thus, in examining Hamming codes we observe that a code word with $`1`$ error will finish with $`0`$ errors, but a code word with exactly $`2`$ errors finishes with exactly $`3`$ errors. In each case the new syndrome difference changes such that $`S_d^{}=\{0\}^m`$.

By symmetry, if an $`N_h`$-bit code word contains exactly $`N_h1`$-errors (all the bits except one are in error), then after application of Hamming all the bits in the code word will be in error. Further, a code word that contains $`N_h2`$ errors will finish with $`N_h3`$ errors, i.e one of the errors is corrected.

The above arguments imply that a Hamming code only works well if the probability of $`2`$ or more errors is low relative to the liklihood of a single, or no, errors. In either case the Hamming code is inefficient as $`m`$-bits are revealed in the syndrome (this fact is discussed in detail later).

The difficult question to answer in analyzing the performance of a Hamming code is how does Hamming affect code words with more than $`2`$, but less than $`2^{m1}`$, errors?

It is not obvious but the number of code words with $`3`$-errors and $`S_d\{0\}^m`$ is related to the number of ways $`2`$-error code words map to a code word with $`3`$ errors (and $`S_d=\{0\}^m`$). In other words, there must be a way to arrange $`3`$ errors in a code word and still maintain $`S_d=\{0\}^m`$. Lacking this would mean that the code could always detect more than $`2`$ errors with a Hamming distance of $`d=3`$.

To complete the Hamming efficiency analysis, how code words with $`3`$ or more errors are affected after application of Hamming must be analyzed. For $`3`$ errors it is now obvious: there must be at least $`2^m1`$ ways to start with $`3`$ errors in an $`N_h`$-bit code word and still finish with $`3`$ errors. In the case that there exist $`3`$ errors in a code word, and $`S_d\{0\}^m`$, then an error will be introduced into the $`N_h`$-bit code word because if the code word finished with $`2`$ errors then $`S_d\{0\}^m`$—a contradiction.

As a special case (example), consider $`m=3`$. There are $`\left(\genfrac{}{}{0pt}{}{7}{3}\right)=35`$ ways to arrange $`3`$ errors in $`7`$ bits. Because there are exactly $`7`$ non-zero syndrome differences for $`m=3`$ and $`n_i=2`$, there must be at least $`7`$ ways to arrange $`3`$ errors in $`7`$-bits and have $`S_d\{0\}^m`$. In fact for this special case this is the result. What this means is that, statistically, $`7`$ in $`35`$ code words with $`3`$-errors will finish with $`3`$-errors, and $`28`$ in $`35`$ words with $`3`$ errors will finish with $`4`$ errors. Thus, code words that start with $`3`$ errors will finish with $`19/5`$ errors per $`7`$-bit block, in the limit of an infinite number of $`7`$-bit blocks with exactly $`3`$ errors. By symmetry, it is obvious that given an infinite number of $`7`$-bit blocks with exactly $`4`$ errors, the final error rate per block would be $`16/5`$—a lower final error rate.

Thus, what is needed is a way to calculate, for any number $`m`$ of parity checks, in Hamming, a way to calculate the number of ways to arrange the initial number of errors per block and finish with $`S_d=\{0\}^m`$, or with $`S_d\{0\}^m`$. Eq. 7 permits that calculation for any initial number of errors per block, $`n_i`$, given any initial block size, $`N_h`$:

$`N_{S_d0}+N_{S_d=0}`$ $`=`$ $`\left({\displaystyle \genfrac{}{}{0pt}{}{N_h}{n_i}}\right)`$ (5)
$`N_{S_d0}+N_hN_{S_d=0}`$ $`=`$ $`(1)^qN_h\left({\displaystyle \genfrac{}{}{0pt}{}{\frac{N_h1}{2}}{p}}\right)`$ (6)
$`\left[\begin{array}{c}N_{S_d0}\\ N_{S_d=0}\end{array}\right]`$ $`=`$ $`\left[\begin{array}{cc}N_h& 1\\ 1& 1\end{array}\right]^1\left[\begin{array}{c}\left(\genfrac{}{}{0pt}{}{N_h}{n_i}\right)\\ (1)^q\left(\genfrac{}{}{0pt}{}{\frac{N_h1}{2}}{p}\right)\end{array}\right]\text{,}`$ (7)
where $`q=n_i/2`$, $`p=n_i/2`$, $`n_i`$ is the initial number of errors per Hamming block of $`N_h=2^m1`$ bits per block; in this situation, $`N_{S_d=0}`$ gives the number of syndrome differences with $`S_d=\{0\}^m`$, and $`N_{S_d0}`$ gives the number of syndrome differences with $`S_d\{0\}^m`$. Eq. 7 is generalized by dividing both sides by the total number of ways to arrange $`n_i`$ errors in the $`N_h`$ bits. In this situation we find a more useful quantity:

$`\mathrm{\Pi }_{S_d=0}`$ $`=`$ $`{\displaystyle \frac{N_{S_d=0}}{\left(\genfrac{}{}{0pt}{}{N_h}{n_i}\right)}}\text{, and}`$ (8)
$`\mathrm{\Pi }_{S_d0}`$ $`=`$ $`{\displaystyle \frac{N_{S_d0}}{\left(\genfrac{}{}{0pt}{}{N_h}{n_i}\right)}}\text{.}`$ (9)
This result is required later.

These arguments are not obviously general for the case of $`m>3`$, but they give insight into the general problem. The difficulty with the special case of $`m=3`$ and $`n_i=3`$ is that the next case of $`n_i=4`$ is symmetric and complementary with $`n_i=3`$, as mentioned previously. Further, as was noted, there is no path to map $`3`$ errors to $`2`$ errors as $`S_d\{0\}^m`$ when there are exactly $`2`$ errors. However, Eq. 7 is the general technique to calculate the quantities specified, i.e. the number of ways to map $`n_i`$ errors to $`S_d=\{0\}^m`$ or not, given $`N_h=2^m1`$ bits in a block.

Given these facts, how the errors change for $`m4`$ and $`4n_i<2^{(m1)}`$ is the general result of interest.

Let $`n_i^{(+)}`$ be the number of ways to increase the number of errors from $`n_i`$ to $`n_i+1`$, in a bit-block, and $`n_i^{()}`$ the number of ways to decrease the number of errors from $`n_i`$ to $`n_i1`$; of course, the considerations relate to $`m4`$. The results are as follows:

$`n_i^{(+)}`$ $`=`$ $`N_{S_d=0}(N_h|n_i)+(n_i+1)N_{S_d=0}(N_h|n_i+1)`$ (10)
$`n_i^{()}`$ $`=`$ $`\left({\displaystyle \genfrac{}{}{0pt}{}{N_h}{n_i}}\right)n_i^{(+)}\text{,}`$ (11)
where $`N_{S_d=0}(N_h|n_i+1)`$ is the number of ways to arrange $`n_i+1`$ errors in $`N_h`$ bits and obtain $`S_d=\{0\}^m`$ (the reader will recall that earlier it was stated that the number of ways to get $`S_d=\{0\}^m`$ for $`n_i+1`$ errors is directly related to the number of ways to map $`n_in_i+1`$ errors); of course, $`N_{S_d=0}(N_h|n_i)`$ is the number of ways to arrange $`n_i`$ errors in $`N_h`$ bits and get $`S_d=\{0\}^m`$. Thus, the generalized probability for the number of errors $`n_i`$ to increase, or decrease is:

$`\mathrm{\Pi }^{(+)}`$ $`=`$ $`{\displaystyle \frac{n_i^{(+)}}{n_i^{(+)}+n_i^{()}}}\text{, and}`$ (12)
$`\mathrm{\Pi }^{()}`$ $`=`$ $`1\mathrm{\Pi }^{(+)}\text{.}`$ (13)
## III Winnow

As a general rule, the ideal error correcting protocol would correct all bit errors in each bit block, introduce no additional bit errors, and reveal a minimal amount of information on the key bits to an eavesdropper through public communication. The outlined Hamming protocol has a number of shortcomings regarding this ideal. First, the difference syndrome $`S_d`$ does not distinguish between single- and multiple-bit errors. Therefore, additional errors may be introduced if instances of $`S_d\{0\}^m`$ are treated as due to single errors. Second, up to $`m`$ bits of information are exchanged for each data block reducing channel capacity per symbol with each exchange: information which can be compromised by eavesdropping.

One solution is to eliminate all bits within data blocks for which $`S_d\{0\}^m`$. This certainly removes the possibility of introducing additional bit errors into the key, but, unfortunately, the efficiency of such a method is low as every block loses either $`m`$-bits to privacy maintenance, or all bits because $`S_d\{0\}^m`$. The efficiency of this approach is not optimal as most of the discarded bits/blocks for which $`S_d\{0\}^m`$ are probably not in error.

Another, more powerful solution is to introduce a preliminary parity comparison on a block of $`N=2^m`$ bits and to make a comparison of the syndromes $`S_a`$ and $`S_b`$ conditional upon the result of the parity comparison.***Hamming discusses the addition of a parity check on the $`N_h=2^m1`$ bit block  (pp. 47-48; pp. 213-214). His conclusion is that A and B are more likely to introduce additional errors than correct errors by changing a bit if $`S_d\{0\}^m`$ and the block-parities agree. In this situation A and B could either remove the $`m+1`$ bits required to ensure privacy on the remaining bits (which may remove errors), or they could eliminate all of the bits in question, as $`n_i\{2,4,\mathrm{},2^m2\}>1`$. The expanded protocol described in this effort allows the detection of an even or odd number of errors and prevents a correction attempt on those data blocks with even numbers of errors. This is important since the Hamming algorithm will increase the number of errors in blocks which have $`2n_iN_h/2`$.

If the block parities do not agree an odd number of errors exists in the $`N`$-bit block. Moreover, if the bit errors are distributed randomly throughout the data, and if the number of errors is sufficiently small, then an odd number of errors in a block probably indicates a single error which can be corrected by the additional application of the Hamming algorithm. For example, in the situation that a block contains one bit error, if $`S_d=\{0\}^m`$ then the first bit is in error. (By symmetry it is clear that if there are exactly $`N1`$ errors in the block the first bit would not be in error.) Thus, this approach always allows the correction of a single error in the $`N`$ bits, i.e. if the bits are to be retained. However, in the protocol outlined here the one bit is regularly discarded for privacy maintenance (for the exchanged parity bit) and the Hamming algorithm is applied to the remaining $`N_h`$ bits, as previously discussed, and then $`\mathrm{log}_2(N_h)`$ additional bits are discarded to complete the privacy maintenance giving a channel capacity of $`(2^mm1)/N`$ per symbol on blocks that contain an initial parity error. This appears to be an additional loss of channel capacity, but because the syndromes are not exchanged and compared when the block parities agree the channel capacity actually increases over the basic Hamming algorithm; one bit is still discarded from the blocks that do not exhibit a parity error for privacy maintenance. We refer to this error reconciliation protocol as Winnow.

Winnow reveals $`\mathrm{log}_2(N)+1`$ bits in $`2`$ classical communications when the parities on the $`N`$ bits do not agree: $`m`$ bits for the syndrome and $`1`$ bit for parity; conversely, Winnow reveals $`1`$ bit of information in $`1`$ classical communication when the parities agree.Exchanging the parity on $`N=2^m`$ bits instead of $`N_h=2^m1`$ bits results in slightly higher channel capacity. That is: more information is revealed when the syndrome information is combined with the parity information on a $`N_h`$ bit block than is revealed when the parity and syndrome are revealed on $`N`$ bits in Winnow.

Therefore, the amount of key data discarded is

$$N_{dis.}^{odd}=\mathrm{log}_2(N)+1=m+1$$
(14)
bits for blocks with odd numbers of errors such that the fraction of the bits remaining after privacy maintenance is

$$\mu _{pm}^{odd}=1\frac{N_{dis.}^{odd}}{N}\text{.}$$
(15)
For $`N\{8,16,32,64,128\}`$, $`\mu _{pm}^{odd}\{0.5,0.69,0.88,0.89,0.94\}`$, respectively. Also,

$$\mu _{pm}^{even}=1\frac{1}{N}\text{,}$$
(16)
and $`\mu _{pm}^{even}\{0.88,0.94,0.97,0.98,0.99\}`$ for the same values of $`N`$. In either case, the appropriate overhead for the classical communications is also removed immediately from the data so that the privacy of the bits is at least maintained if not improved.

All single bit errors in an $`N`$-block are guaranteed to be either eliminated or corrected after a single pass of Winnow (a Winnowing). What remains to be considered is how blocks with multiple errors affect the overall efficiency of Winnow.

## IV Winnow Efficiency

Define the change in number of errors in a given block and for a given initial number of errors as $`\mathrm{\Delta }n=n_fn_i`$, where $`n_i`$ and $`n_fn_f(n_i|N)`$ are the initial and final numbers of bit errors in a block prior to and after Winnowing, respectively. The average change in the number of errors, for a given number of initial errors, after a Winnowing (this step includes elimination of the parity bit but not the final $`m`$-bits required for completion of the privacy maintenance step) can be expressed as

$$\overline{\mathrm{\Delta }n}\mathrm{\Delta }n(n_i)=\underset{\mathrm{\Delta }n=2}{\overset{1}{}}\mathrm{\Delta }np(\mathrm{\Delta }n|n_i)\text{,}$$
(17)
where

$$\underset{\mathrm{\Delta }n=2}{\overset{1}{}}p(\mathrm{\Delta }n|n_i)=1\text{,}$$
(18)
and $`p(\mathrm{\Delta }n|n_i)`$ is the probability that the number of errors will change by $`\mathrm{\Delta }n\{2,1,0,1\}`$ given an initial condition of $`n_i`$ errors in an $`N`$bit data block. The $`p(\mathrm{\Delta }n|n_i)`$ of interest can be written more instructively as

$`p(+1|n_i)`$ $`=`$ $`\pi ^{(n)}\mathrm{\Pi }_{S_d0}(n_i)\mathrm{\Pi }^{(+)}(n_i)`$ (19)
$`p(\pm 0|n_i)`$ $`=`$ $`\pi ^{(n)}\mathrm{\Pi }_{S_d=0}(n_i)+\pi ^{(y)}\mathrm{\Pi }_{S_d0}(\delta n_i)\mathrm{\Pi }^{(+)}(\delta n_i)`$ (20)
$`p(1|n_i)`$ $`=`$ $`\pi ^{(n)}\mathrm{\Pi }_{S_d0}(n_i)\mathrm{\Pi }^{()}(n_i)+\pi ^{(y)}\mathrm{\Pi }_{S_d=0}(\delta n_i)`$ (21)
$`p(2|n_i)`$ $`=`$ $`\pi ^{(y)}\mathrm{\Pi }_{S_d0}(\delta n_i)\mathrm{\Pi }^{()}(\delta n_i)\text{,}`$ (22)
where, $`n_i`$ is as previously defined, $`\delta n_in_i1`$, $`\pi ^{(yn)}`$ depends only on the initial number of errors ($`n_i`$) in the $`N`$-bit block and is the probability the bit discarded for privacy maintenance following the parity check was (y), or () was not (n) in error; $`\mathrm{\Pi }_{S_d=0}(n_i^{}\delta n_i)`$ and $`\mathrm{\Pi }_{S_d0}(n_i^{}\delta n_i)`$ are the probabilities that $`S_a=S_b`$ or $`S_aS_b`$ for $`n_i`$ or $`\delta n_i`$ errors in $`N_h`$ bits and are concretely defined in Eq. 9, and $`\mathrm{\Pi }^{(\pm )}(n_i^{}\delta n_i)`$ is defined in Eq. 13.

Eq. 17 can be expressed in terms of $`\pi ^{(yn)}`$, $`\mathrm{\Pi }_{S_d}`$ and $`\mathrm{\Pi }^{(\pm )}`$ as

$`\overline{\mathrm{\Delta }n}`$ $``$ $`\mathrm{\Delta }n^{(n)}(n_i)+\mathrm{\Delta }n^{(y)}(n_i)\text{,}`$ (23)
$`=`$ $`\overline{\mathrm{\Delta }n}^{(n)}+\overline{\mathrm{\Delta }n}^{(y)}\text{,}`$ (24)
where the arguments which depend on $`n_i`$ have been suppressed, and

$`\overline{\mathrm{\Delta }n}^{(n)}`$ $`=`$ $`\pi ^{(n)}\mathrm{\Pi }_{S_d0}(n_i)\left[12\mathrm{\Pi }^{()}(n_i)\right]\text{,}`$ (25)
$`\overline{\mathrm{\Delta }n}^{(y)}`$ $`=`$ $`\pi ^{(y)}\mathrm{\Pi }_{S_d0}(\delta n_i)\left[12\mathrm{\Pi }^{()}(\delta n_i)\right]\pi ^{(y)}\text{.}`$ (26)
The final quantity needed to calculate the efficiency of Winnow is $`\pi ^{(yn)}`$:

$`\pi ^{(y)}`$ $`=`$ $`{\displaystyle \frac{n_i}{N}}\text{, where}`$ (27)
$`\pi ^{(y)}+\pi ^{(n)}`$ $`=`$ $`1\text{.}`$ (28)
Table I and Table II provide a concrete example for the special case of $`m=3`$ of the effects of Winnow on blocks with exactly $`n_i\{0,\mathrm{},8\}`$ errors. Table I, introduces a new quantity

$$\overline{n}_fn_f=n_i+\overline{\mathrm{\Delta }n}\text{,}$$
(29)
and in Table II a new parameter

$$p_f=\frac{\overline{n}_f}{N_f}$$
(30)
is defined.

The parameter $`p_f`$ defines the probability for each bit in a given block to be in error. The number $`N_f\{N1,Nm1\}`$ and its value depends on the action required by Winnow for a given number of initial errors. For example, $`N_f=N1`$ or $`Nm1`$ for $`p_f`$ and $`n_i`$ even or odd, respectively.

These two tables illustrate the effect of Winnow on data which are divided into 8-bit blocks. The values marked with superscript $`p`$ reflect the effect of discarding one bit following the parity comparison. The values marked with superscript $`ph`$ refer to the data after the Hamming algorithm is also applied, but before the requisite $`\mathrm{log}_2(N)=3`$ bits of data are discarded for privacy maintenance. The final values denoted by subscript $`f`$ reveal the effect of Winnow (including the effect of all discarded data required for privacy maintenance).

The parameter $`p_f`$ clearly shows a reduction in errors for $`n_i=1`$ and an increase in errors for $`n_i=3`$. It also shows that discarding data to maintain privacy of the remaining key has no effect on the error probability.

The fraction of key remaining after a Winnowing is given by

$$\mu _N\frac{N_f}{N}=\frac{_{n_i=0}^NN_fP(n_i|N)}{N}\text{,}$$
(31)
and the probability for any key bit to be in error following a Winnowing is

$`p_N={\displaystyle \frac{\overline{n}_f}{N_f}}={\displaystyle \frac{_{n_i=0}^N\overline{n}_f(n_i)P(n_i|N)}{N\mu _N}}\text{,}`$ (32)
where $`P(n_i|N)`$ is the probability for an $`N`$-bit block to contain $`n_i`$ errors before a Winnowing.

Obviously, the efficiency with which Winnow removes errors depends upon the distribution of errors within the data. Without intimate knowledge of a specific QKD apparatus, a reasonable assumption is that the errors are random and normally distributed throughout the data. Given this assumption, $`P(n_i|N)`$ in Eq. 32 is given by the binomial distribution

$$P(n_iN,p_0)=\left(\genfrac{}{}{0pt}{}{N}{n_i}\right)p_{0}^{}{}_{}{}^{n_i}(1p_0)^{Nn_i}$$
(33)
where $`p_0`$ is the probability that any given bit is in (relative) error.

With this assumption, Eqs. 31 and 32 can be expressed as

$`\mu _N={\displaystyle \frac{N1m_{n_i^{odd}}\left(\genfrac{}{}{0pt}{}{N}{n_i}\right)p_{0}^{}{}_{}{}^{n_i}(1p_0)^{Nn_i}}{N}}\text{,}`$ (34)
where $`m=\mathrm{log}_2(N)`$, and

$`p_N={\displaystyle \frac{_{n_i=0}^N\overline{n}_f(n_i)\left(\genfrac{}{}{0pt}{}{N}{n_i}\right)p_{0}^{}{}_{}{}^{n_i}(1p_0)^{Nn_i}}{N\mu _N}}\text{.}`$ (35)
The efficiency with which Winnow reduces errors in the key is of great interest. Two related issues which concern the efficiency are: 1) the number of iterations of Winnow necessary to achieve a sufficiently low probability of error in the remaining key data, and 2) the amount of key data that is discarded through privacy maintenance.

The number of iterations is of concern because each iteration reveals information and consumes time with each communication between A and B. Moreover, each communication requires the use of some private key for signature authentication . Most importantly, though, is that each iteration requires a significant amount of data to be discarded through privacy maintenance.

Smaller $`N`$ require more data to be discarded than larger $`N`$ as can be seen from Eq. 34. However, an effect which tends to mollify this undesirable condition is that smaller $`N`$ are more efficient at removing errors for larger values of initial error probability. This effect is illustrated in Fig. 1 where we have plotted $`p_N/p_0`$ for several values of $`N`$. For all values of $`N`$ and $`p_0`$ sufficiently small, $`p_N/p_0<1`$ and the protocol can remove errors from the key data. However, as $`p_0`$ increases from $`p_0=0`$, each of the curves passes through $`p_N/p_0=1`$ indicating that additional errors are being introduced into the key. Moreover, the value of $`p_0`$ for which $`p_N/p_0=1`$ is smaller for larger N and the curves do not intersect between $`p_0=0`$ and $`p_N/p_0=1`$.

As a primary requirement of Winnowing real data in an iterative application, a random shuffling of the data between iterations is essential to randomly redistribute missed or introduced errors. Without this random shuffle multiple errors remain clumped together and, in essence, are impossible to completely remove from the data. Under this constraint it is obvious that the final error probability, and the amount of data remaining after a number of Winnowings, depends on the way in which $`N`$ is varied throughout the successive Winnowings. An intuitive result which we have verified empirically is that less data are discarded for the same initial and final error probabilities if $`N`$ is chosen well for the first iteration and is either held constant or increased for all subsequent iterations; there is no advantage to decreasing $`N`$ in subsequent iterations if Winnow is applied as outlined here.

Define

$$p(p_0;\{j_N\})$$
(36)
and

$$\mu (p_0;\{j_N\})$$
(37)
as the final error rate and fraction of data remaining after a sequence $`\{j_N\}=\{j_8,j_{16},j_{32},j_{64},j_{128}\}`$ where $`j_N`$ iterations of Winnow are applied with a block size $`N\{8,16,32,64,128\}`$ beginning with $`N=8`$ and increasing monotonically in $`N`$ by factors of $`2`$.In this work $`N`$ is constrained such that $`N128`$ only for the sake of brevity. We have found that this constraint does not impose a serious limit on the ability of Winnow to correct errors. The ideas discussed below can be extended to include $`N>128`$ in a straightforward manner.

Because $`(p_8<p_0)(p_0<0.5)`$, it may appear that errors can be corrected in the data for this entire range of initial error probability. However, there is another criterion that must be met which significantly reduces the maximum correctable error probability: There must remain a finite amount of error-free data after the potential information possessed by E is reduced through privacy amplification.

The maximum amount of potential information possessed by E can be determined by the initial error probability $`p_0`$ and depends on the QKD protocol and the type of attacks being employed. For example, if the BB84 protocol is used and E employs a complete intercept/resend attack on the quantum channel in the same bases used by B, she will introduce an error probability of $`p_0=1/4`$. She will also potentially know $`1/2`$ of the data before error reconciliation and up to $`2/3`$ of the data which remains after error reconciliation.

If E uses a more clever intercept/resend strategy of detecting and resending in the Breidbart basis (second paper in ), she would introduce the same number of errors ($`p_0=1/4`$) and could know up to a fraction of $`0.59`$ of the data before error reconciliation and $`0.78`$ of the data remaining after error reconciliation.

It should also be noted that certain states of light are more susceptible to attack than others. For example, consider weak coherent states which are commonly used in QKD systems. If E also employs a beamsplitter attack  against one of these systems, an additional amount of data is compromised which is not greater than the mean number of photons in the state. However, this value can be made arbitrarily small so it is neglected in the following calculations. Moreover, other states of light can be used in QKD schemes which are not vulnerable to this type of attack .

Thus, the fraction of data remaining after error reconciliation and privacy amplifications can be

$$\nu ^{bb84}=\mu (0.59)4p_0$$
(38)
for BB84, where $`\nu `$ describes the remaining fraction of key.

From the above considerations, $`p`$ and $`\nu `$ can be investigated as a function of $`p_0`$. Of particular interest is the maximum $`p_0`$ for which some secure data remains while achieving a sufficiently low final error probability to make the data useful. We have chosen, somewhat arbitrarily, $`p10^6`$ as a reasonable target for the final error probability.

With this target and the remaining fraction of private data described by Eq. 38, we find the largest initial error probability for which some private data remains is

$$p_0=0.1322\text{,}$$
(39)
after Winnowing and privacy amplification.

To achieve $`p10^6`$ from this large initial error probability, Winnow must be applied in the sequence $`\{j_N\}=\{3,1,0,1,3\}`$. That is, $`3`$ Winnowings with $`N=8`$ must be followed by $`1`$ Winnowing with $`N=16`$, etc. If this prescription is followed,

$$\nu ^{bb84}=0.0017$$
(40)
of the original data remain and are secure following privacy amplification.

Some QKD schemes require a larger estimate of E’s knowledge. If Eq. 38 is replaced with

$$\nu =\mu 2\sqrt{2}p_0\text{,}$$
(41)
we find

$$p_0=0.1222$$
(42)
for $`\{j_N\}=\{3,0,1,0,4\}`$. This leaves a fraction $`\nu =0.0017`$ of the original data as secure data with a single-bit error probability $`10^6`$.

Finally, if we estimate that E knows every bit of data by causing $`p_0=1/4`$, then

$$\nu =\mu 4p_0\text{.}$$
(43)
We then find that the largest reconcilable $`p_0`$ is

$$p_0=0.1037$$
(44)
for $`\{j_N\}=\{2,1,1,0,3\}`$ and $`\nu =0.0020`$.

The most efficient iteration sequence ($`\{j_N\}`$) for any QKD scheme can be determined by first applying Winnow with $`N=8`$ to estimate $`p_0`$. Once the number of blocks with odd and even (even includes zero) errors, $`M_e^{odd}`$ and $`M_e^{even}`$ respectively, are known, the fraction

$$\frac{\mathrm{\#}\text{ of Parity Errors}}{\mathrm{\#}\text{ of Blocks}}=\frac{_{n_i^{odd}}\left(\genfrac{}{}{0pt}{}{N}{n_i}\right)p_{0}^{}{}_{}{}^{n_i}(1p_0)^{Nn_i}}{N}$$
(45)
can be used to estimate $`p_0`$. Knowledge of $`p_0`$ is sufficient to determine the $`\{j_N\}`$ which maximizes $`\nu `$.

For small $`p_0`$, the most efficient $`\{j_N\}`$ may start with $`N>8`$. However, working systems that have been reported in the literature  have large enough error probabilities so that the most key is left if $`N=8`$ for at least the first iteration.

A detailed analysis of the advantages of Winnow over other protocols is beyond the scope of this work. However, it is instructive to note the advantages over at least the best-known protocol CASCADE.

The most notable difference between Winnow or BINARY and CASCADE is that CASCADE does not employ privacy maintenance. The disadvantage of such a protocol is that super-redundant information must be exchanged with each successive iteration. This is to be compared with BINARY and Winnow which reduce the size of the data set with each communication. With the reasonable requirement that a bit revealed through these communications requires at least a bit to be eliminated through some channel, either before or during privacy amplification, then the inefficiency of keeping all bits until all errors are removed becomes obvious: retaining and repetitively exchanging information on the same bits is an additional expense to the protocol.

For the purpose of comparison, we have computed the maximum $`p_0`$ which BINARY (less privacy maintenance) can successfully reconcile errors and preserve a small amount of secure data after privacy amplification and the removal of the super-redundant information. We find

$$p_0=0.114$$
(46)
for $`\{j_N\}=\{2,1,0,2,1\}`$ and $`\nu ^{bb84}=0.01`$ when $`(0.59)4p_0`$ describes the additional amount of key that must be discarded through privacy amplification. This is to be compared with $`p_0=0.1322`$ for the same considerations with Winnow. This application of BINARY is a reasonable approximation to CASCADE which may include a higher order correction giving a slightly higher overall error reduction than BINARY without privacy maintenance.

This comparison (or any of the previous discussion) does not take into account bits used to authenticate messages sent between A and B. Both CASCADE and BINARY requires significantly more two-way communication than Winnow, and each packet of $`n`$ bits sent may require $`\mathrm{log}_2(n)`$ for authentication . We calculate that the most efficient application of CASCADE requires a minimum of $`1+\mathrm{log}_2(N)`$ communications per iteration while Winnow requires only $`2`$ communications for any block size $`N`$ that exhibits a parity error; the additional communications required imposes a tight limitation on practical efficiency. In addition, because CASCADE does not maintain privacy, subsequent iterations requires more bits to be exchanged in the initial parity phase with each iteration. The additional bit exchanges may require additional signature authentication bits.

We acknowledge that because CASCADE and BINARY always removes a single error and never introduces additional errors to multiple error blocks, both BINARY and CASCADE perform infinitesimally better than Winnow in an environment where signature authentication is not required and privacy maintenance is removed from the Winnow and BINARY protocols. However, Winnow’s $`2`$ communications is a great advantage where time is of the essence with regard to production of secure key bits over inefficient noisy quantum channels.

## V Conclusion

We have identified a new, fast, efficient, error reconciliation protocol for quantum key distribution which requires only $`2`$ communications between the two parties attempting to reconcile private, quantum key material. We refer to this protocol as Winnow.

Winnow incorporates a preliminary parity comparison on blocks whose size is $`N=2^m`$ where $`m\{3,4,5,6,\mathrm{}\}`$. Subsequently, one bit is discarded from these blocks to maintain the privacy of the remaining bits. A Hamming hash function, which can be used to correct single errors, is applied to the remaining $`N1`$ bits on the blocks whose parities did not agree. Finally, $`m`$ bits are discarded from the blocks on which the Hamming algorithm was applied to maintain the privacy of those bits.

We find this protocol capable of correcting an initial error probability of up to $`13.22\%`$ in privacy amplified BB84-like quantum key distribution schemes.

Acknowledgments: The authors extend their thanks and appreciation to R. J. Hughes, E. Twyffort, D. P. Simpson and J. S. Reeve for many helpful discussions regarding this effort.


text:
# Minority Opinion Spreading in Random Geometry

((galam@ccr.jussieu.fr))

## Abstract

The dynamics of spreading of the minority opinion in public debates (a reform proposal, a behavior change, a military retaliation) is studied using a diffusion reaction model. People move by discrete step on a landscape of random geometry shaped by social life (offices, houses, bars, and restaurants). A perfect world is considered with no advantage to the minority. A one person-one argument principle is applied to determine locally individual mind changes. In case of equality, a collective doubt is evoked which in turn favors the Status Quo. Starting from a large in favor of the proposal initial majority, repeated random size local discussions are found to drive the majority reversal along the minority hostile view. Total opinion refusal is completed within few days. Recent national collective issues are revisited. The model may apply to rumor and fear propagation.

PACS numbers: 89.75Hc, 05.50+q, 87.23.G

All over the world and more specifically in democratic countries public opinion seems to be rather conservative while facing a nationwide issue open to a public debate like for instance a reform proposal or a behavior change . Even when the changes at stake are known to be desperately needed (medical evidences, danger of death, administrative inefficiencies) an initial hostile minority appears to be almost always able to turn the majority along its refusal position.

A symptomatic illustration of such a paradoxical social refusal was the year 2000 generalized failure of the French government to reform the academic system, the taxes collect and the agriculture system of economical help . Another example is the Irish No to the Nice European treaty that came as a surprise to the Irish people itself . Along with this reality some people could be tempted to consider reforms possible only using social violence or authoritarian top leadership decisions. It thus arises he fundamental question whether or not a reform can be decided democratically at least in principle.

To understand the reason of such a social inertia, most research has concentrated on analyzing the complicated psycho-sociological mechanisms involved in the process of opinion forming. In particular focusing on those by which a huge majority of people gives up to an initial minority view . The main feature being that the prospect to loose definite advantages is much more energizing than the hypothetical gain of a reform. Such an approach is certainly realistic in view of the very active nature of minorities involved in a large spectrum of situations.

However in this letter we claim that in addition to the more aggressiveness and persuasive power of a threatened or very motivated minority there exists some basic and natural mechanism inherent to free public debate which makes the initial hostile minority to a full spreading over.

To ground our claim we present an extremely simple model to opinion forming using some concepts and techniques from the physics of disorder . A diffusion reaction model is implemented on a landscape of random geometry. It does not aimed at an exact description of reality. But rather, by doing some crude approximations, it focuses on enlightening an essential feature of an otherwise very complex and multiple phenomena. In particular the holding of free public debate is shown to lead almost systematically to the total spreading of an initial hostile minority view within the initial proposal in favor huge majority. The associated dynamics of extreme public polarization at the advantage of the initial minority is found to result from the existence of asymmetric unstable thresholds  that are produced by the random occurrence of temporary local doubts. Some recent nation wide issues with respect to European construction are thus revisited . The application to the phenomena of rumor and fear propagation is discussed .

We start from a population with $`N`$ individuals, which have to decide whether or not to accept a reform proposal. At time $`t`$ prior to the discussion the proposal has a support by $`N_+(t)`$ individuals leaving $`N_{}(t)`$ persons against it. Each person is supposed to have an opinion making $`N_+(t)+N_{}(t)=N`$. Associated individual probabilities to be in favor or against the proposal are thus,

$$P_\pm (t)\frac{N_\pm (t)}{N},$$
(1)
with,

$$P_+(t)+P_{}(t)=1.$$
(2)
From this initial configuration, people start discussing the project. However they don’t meet all the time and all together at once. Gatherings are shaped by the geometry of social life within physical spaces like offices, houses, bars and restaurants. This geometry determines the number of people, which meet at a given place. Usually it is of the order of just a few. Groups may be larger but it is much rare. Accordingly a given social life yields a random local geometry landscape characterized by a probability distribution for gathering sizes $`\{a_i\}`$ which satisfy the constraint,

$$\underset{i=1}{\overset{L}{}}a_i=1,$$
(3)
where $`i=1,2,\mathrm{},L`$ stands for respective sizes $`1,\mathrm{},L`$ with $`L`$ being the larger group. While discussions can occur by chance, most are monitored through regular time break meetings like lunch, dinner, happy hour and late drink. At each encounter people meet with different people (friends, colleagues and acquaintances) at different areas of their social space. It extends from a building, a neighborhood, a town or another state. Thus, people gatherings occur in sequences in time, each one allowing a new local discussion. There, people may change their mind with respect to the reform proposal. During these meetings all individuals are assumed to be involved in one group gathering. It means a given person is, on average, taking part to a group of size $`i`$ with probability $`a_i`$. The existence of one-person groups makes this assumption realistic. Each new cycle of multi-size discussions is marked by a time increment $`+1`$.

To emphasize the bare mechanism at work into the refusal dynamics which arises from local interactions we consider a perfect world. No advantage is given to the minority with neither lobbying nor organized strategy. Moreover an identical individual persuasive power is assumed for both sides. A one person - one argument principle is used to implement the psychological process of collective mind update. On this basis a local majority argument determines the outcome of the discussion. People align along the local initial majority view.

For instance a group of five persons with at start three in favor of the reform and two against it ends up with five people in favor of the reform. On the reverse two initial reform supporters leads to five persons against it. However in case of an even group this rule of one person - one argument leaves the local possibility of a temporary absence of a collective majority. The group is then at a tie within a non-decisional state. It doubts.

There we evoke a physical principle called the “inertia principle” which states that to put on motion a system, it is necessary to apply on it a force at least infinitesimally larger than the friction which holds on it to keep the system at rest. This principle can be put in parallel to the fundamental psychological asymmetry that exists between what is known and what is hypothetical. Therefore, to go along what is unknown, even if this unknown is supposed to be better, a local majority of at least one voice is necessary.

In terms of our model, at a tie the group does not move and thus decides not to move, i. e., the full group turns against the reform proposal to preserve the existing situation. For instance a group of six persons with initially three in favor of the reform and three against it yields six persons against the reform. It is worth to stress that this is not an advantage given to the minority in terms of being more convincing. It is a collective outcome that results from a state of doubt. For instance dealing with a military retaliation people will avoid action unless there exist clear evidences for it. Accordingly having $`P_\pm (t)`$ at time $`t`$ yields,

$$P_+(t+1)=\underset{k=1}{\overset{L}{}}a_k\underset{j=N[\frac{k}{2}+1]}{\overset{k}{}}C_j^kP_+(t)^jP_{}(t)^{(kj)},$$
(4)
at time $`(t+1)`$ where $`C_j^k\frac{k!}{(kj)!j!}`$ and $`N[\frac{k}{2}+1]IntegerPartof(\frac{k}{2}+1)`$. Simultaneously,

$$P_{}(t+1)=\underset{k=1}{\overset{L}{}}a_k\underset{j=N[\frac{k}{2}]}{\overset{k}{}}C_j^kP_{}(t)^jP_+(t)^{(kj)}.$$
(5)
In the course of time, the same people will meet again and again randomly in the same cluster configuration. At each new encounter they discuss locally the issue at stake and change their mind according to above majority rule. To follow the time evolution of the reform support Eq. (4) is iterated until a stable value is reached. A monotonic flow is obtained towards either one of two stable fixed points $`P_{+N}=0`$ and $`P_{+Y}=1`$. The flow and its direction are produced by an unstable fixed point $`P_{+F}`$ located in between $`P_{+N}`$ and $`P_{+Y}`$. Its value depends on both the $`\{a_i\}`$ and $`L`$. We denote it the Faith point. For $`P_+(t)<P_{+F}`$ it exists a number $`n`$ such that $`P_+(t+n)=P_{+N}=0`$ while for $`P_+(t)>P_{+F}`$ it is another number $`m`$ which yields $`P_+(t+m)=P_{+Y}=0`$. Both $`n`$ and $`m`$ measure the required time at reaching a stable and final opinion. It is either a “Big Yes” to the reform at $`P_{+Y}=1`$ or a “Big No” at $`P_{+N}=0`$. Their respective values depend on the $`\{a_i\}`$, $`L`$ and the initial value $`P_+(t)`$ .

Repeated successive local discussions thus drive the whole population to a full polarization with a “Big Yes” to the reform project at $`P_{+Y}=1`$, or a “Big No” at $`P_{+N}=0`$. Accordingly, public opinion is not volatile. It stabilizes rather quickly ($`n`$ and $`m`$ are usually small numbers) to a clear stand.

Figure 1 shows the variation of $`P_+(t+1)`$ as function of $`P_+(t)`$ for two particular sets of the $`\{a_i\}`$. First one is $`a_1=a_2=a_3=a_4=0.2`$ and $`a_5=a_6=0.1`$ where $`L=6`$. There $`P_{+F}=0.74`$ which puts the required initial support to the reform success at a very high value of more than $`74\%`$. Simultaneously an initial minority above $`26\%`$ is enough to produce a final total refusal. The second set is $`a_1=0`$, $`a_2=0.1`$ and $`a_3=0.9`$ with $`L=3`$ and $`P_{+F}=0.56`$. There the situation is much milder but also unrealistic since always pair discussions are much more numerous than just $`10\%`$.

To make a quantitative illustration of the dynamics refusal let us consider above first setting with an initial $`P_+(t)=0.70`$ at time $`t`$. The associated series in time is $`P_+(t+1)=0.68`$, $`P_+(t+2)=0.66`$, $`P_+(t+3)=0.63`$, $`P_+(t+4)=0.58`$, $`P_+(t+5)=0.51`$, $`P_+(t+6)=0.41`$, $`P_+(t+7)=0.27`$, $`P_+(t+8)=0.14`$, $`P_+(t+9)=0.05`$, $`P_+(t+10)=0.01`$ and eventually $`P_+(t+11)=0.00`$. Eleven cycles of discussion make all $`70\%`$ of reform supporters to turn against it by merging with the initial $`30\%`$ of reform opponents. On a basis of one discussion a day on average, less than two weeks is enough to a total crystallization of the No against the reform proposal. Moreover a majority against the reform is obtained already within six days (see Fig. (2)).

Changing a bit the parameters with $`a_1=0.2`$, $`a_2=0.3`$, $`a_3=0.2`$, $`a_4=0.2`$, $`a_5=0.1`$ and $`a_6=0`$ gives $`P_{+F}=0.85`$, a higher value, which makes any reform proposal quite impossible. How a realistic reform project could start with already more than $`85\%`$ support in the population? Starting still from $`P_+(t)=0.70`$ yields successively $`P_+(t+1)=0.66`$, $`P_+(t+2)=0.60`$, $`P_+(t+3)=0.52`$, $`P_+(t+4)=0.41`$, $`P_+(t+5)=0.28`$, $`P_+(t+6)=0.15`$, $`P_+(t+7)=0.05`$, $`P_+(t+8)=0.01`$ before $`P_+(t+9)=0.00`$. The number of local meetings has shrieked from $`11`$ to $`9`$. Within ten days the whole population stands against the reform proposal. The initial $`30\%`$ of opponents grow to more than fifty percent in less than four days (see Fig. (2)).

It is the existence of an unstable fixed point between the two stable ones which produces the whole polarization dynamics. The stable ones are constant and independent of the $`a_i`$ but the unstable one varies with both, sizes and the $`a_i`$ distribution. To single out the specific contribution of each gathering size to the aggregation effect we now determine the associated unstable fixed point for groups from two to six. Values are shown in Table 1. The flow landscape is identical for all odd sizes with an unstable fixed point at $`\frac{1}{2}`$. On the opposite for even sizes the unstable fixed point starts at one for size two and decreases to $`0.65`$ at size six, via $`0.77`$ at size four.

To illustrate the interplay dynamics between even and odd sizes, let us look at more details in the hypothetical case of discussion groups restricted to only two and three persons. Putting $`a_1=a_4=..=a_L=0`$, Eq. (4) reduces to,

$`P_+(t+1)`$ $`=`$ $`a_2P_+(t)^2`$
$`+(1a_2)\{P_+(t)^3+3P_+(t)^2(1P_+(t))\},`$
whose stable fixed points are still $`0`$ and $`1`$ with the unstable one lacated at,

$$P_{+F}=\frac{1}{2(1a_2)}.$$
(7)
For $`a_2=0`$ (only three size groups) we recover $`P_{+F}=\frac{1}{2}`$ while it gets to $`P_{+F}=1`$ already at $`a_2=\frac{1}{2}`$. It shows the existence of pair discussion has a drastic effect on creating doubt that in turn produces a massive refusal spreading. Few days are now enough to get a total reform rejection.

Keeping an initial $`P_+(t)=0.70`$ the time series become $`P_+(t+1)=0.64`$, $`P_+(t+2)=0.55`$, $`P_+(t+3)=0.44`$, $`P_+(t+4)=0.30`$, $`P_+(t+5)=0.16`$, $`P_+(t+6)=0.05`$ before $`P_+(t+7)=0.00`$. The reform supporters falling down is extremely sharp as shown in Fig. (2). Within a bit more than two days a majority of the people is already standing against the reform that yet started with a seventy- percent support. Seven days latter the proposal is completely out of any reach with not one single supporter. Considering instead only thirty percent of pair discussion groups, the falling is weakened but yet within sixteen days we have $`P_+(t+16)=P_N0.00`$ (see Fig. 2).

Clearly an infinite number of combinations of the $`\{a_i\}`$ is possible. However the existence of these temporary local doubts which ultimately produces a strong polarization towards social refusal is always preserved. At this stage it is worth to stress that in real life situations not every person is open to a mind change. Some fractions of the population will keep on their opinion whatever happens. Including this effect in the model will not change qualitatively the results. It will make the polarization process not total with the two stable fixed points shifted towards respectively larger and smaller values than zero and one.

To give some real life illustrations of our model, we can cite events related to the European Union which all came as a surprise. From the beginning of its construction there have been never a large public debate in most of the involved countries. The whole process came trough government decisions tough most people always have seemed to agree on this construction. At the same time European opponents have been systematically urging for public debates. Such a demand sounds like absurd knowing a majority of people favor the European union. But anyhow most European governments have been reluctant to held referendum on the issue.

At odd, several years ago French president Mitterand decides to run a referendum to accept the Maastricht agreement . While a large success of the Yes was given for granted it indeed made it just a bit beyond the required fifty percent. The more people were discussing, the less support there was for the proposal. It is even possible to conjuncture that an additional two weeks extension of the public debate would have make the No to win. The very recent Irish No  which came as a blow to all analysts may obey the same logic. The difference with the French case was certainly the weaker initial support. Of course addition political reasons to the No were also active.

To conclude, even tough our model is clearly very crude it does demonstrate the inherent polarization effect associated to the holding of democratic debates towards social immobility. Moreover this process was shown to be de facto anti-democratic since even in a perfect world it makes an initial minority refusal to almost systematically spread over in convincing very quickly the whole population. The existence of natural random local temporary doubts is instrumental in this phenomenon driven by the geometry of social life. As on how to remedy this reversal phenomenon, the first hint is to avoid the diffusion of the No via these localized temporary doubts. Direct and immediate votes would address this task preserving the democratic expression of an unbiased initial majority. But more thoughts and studies should be performed before getting to a clear proposal scheme. The model may generalize to a large spectrum of social, economical and political phenomena that involve propagation effects. In particular it could shed a new light on both processes of fear propagation and rumors spreading.