Trying to implement the algorithm in Wikipedia regarding key exchange

Question

I am trying to understand the reconciliation technique mentioned in Wikipedia page for Ring-LWE key exchange. Basically, if we intentionally choose x, y (or the coefficients of calculated shared key of Alice and Bob) to be different in terms of range or one in range (-floor(q/4), round(q/4)) and another not in that range, then w should be 1 for at least one of them. Then that party sends w which would be 1 to the other part and then we do the reconciliation technique of $Mod_2$:

$Mod_{2}(v,w)={(}v+w.{\frac {q-1}{2}}{ )}{\text{ mod }}q{\text{ mod 2}}$

Which essentially would do the following (and the bits are supposed to match):

k1 = ((x + (q-1) / 2) % q) % 2
k2 = ((y + (q-1) / 2) % q) % 2

So what I have done (in SageMath) is that I randomly choose 2 values one in the range and one not in that range and then followed the reconciliation and it does not workout, half of the time bits don't match. Obviously, I am not understanding something here. Any help would be appreciated.

What I assume is that the difference between x and y in a real world implementation should be small (errors are supposed to be small) and that is why reconciliation does not work

arr = {
        "correct" : 0,
        "incorrect" : 0
        }

q = 40961

for i in range(0, 10000):
    x = ZZ.random_element(-floor(q/4), round(q/4))
    y = ZZ.random_element(round(q/4) + 1, q)

    if x not in range(-floor(q/4), round(q/4)) or y in range(-floor(q/4), round(q/4)):
        print "critical error! (range does not match)"

    k1 = ((x + (q-1) / 2) % q) % 2
    k2 = ((y + (q-1) / 2) % q) % 2

    if k1 != k2:
        # print "error!"
        # print k1
        # print k2

        arr["correct"] = arr["correct"] + 1
    else:
        arr["incorrect"] = arr["incorrect"] + 1        

print arr


output >> {'incorrect': 4980, 'correct': 5020}

Answer 1

There have been several rLWE key exchange protocols proposed; what you're looking at is the protocol proposed by Professor Ding here.

In this protocol, the errors are assumed to be small even values; on the Wikipedia page, you can see that they always add the error vector in the form of $2e_i$. Your test fixture is generating relatively large errors without any regard to whether they're even or odd. Unless you fix that up, yes, the reconcilliation process will generate random values. It still won't work great unless you make sure that the errors are actually small (you appear to be trying it with large errors); but you appear to be testing that deliberately.