Mathur

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

The Mathur et al. 2008 quantizer is easy to understand and implement, but hard to configure right. The problem lies in the right values for the parameters $\displaystyle q_+, q_-$ and $\displaystyle m$ . Before that, let us begin at getting data recorded.

Let us assume that two parties, Alice and Bob, can establish a connection to each other. Let us further assume, that both can send a standard probe signal to each other and that both can process the received signals. Now Alice and Bob are repeatedly sending probe signals to each other. Through channel characteristics, like reciprocity or randomness, they both get sequences of received data which both Alice and Bob are using from now on to establish a shared key. The sequences might not be the same because of bit-errors.

The quantizer uses the parameters $\displaystyle q_+$ , $\displaystyle q_-$ and m, where $\displaystyle q_+$ is the upper boundary, $\displaystyle q_-$ the lower boundary. The parameter m is the minimum duration for a set of data in the received sequence which is $\displaystyle >q_+$ or $\displaystyle . This allows us to catch sudden short peaks that would normally deteriorate our quantizer. Now we can easily quantize the sequences, while sets of data, with the minimum duration m, >q+ are mapped to 1 and sets of data <q- are mapped to 0. We define now that an error has arises, if Alice/Bob maps a set of data in the other boundary than Bob/Alice. It can be easily seen that increasing the value m or the boundaries $\displaystyle q_+$ , $\displaystyle q_-$ results in lower bit rate, but also in lower probability of error. So, there is a tradeoff between bit rate and probability of error.

In most practical cases the parameters are set or computed as following: m=3 or m=4 and $\displaystyle q_{+/-} = mean(sequence) +/- α · σ(sequence)$ while σ represents the standard deviation and α a factor which can be selected to differentiate between quantizer levels.

Now that the general idea of the quantizer is established we can take a closer look to the level crossing algorithm. The algorithm has five steps:

1. Alice searches in the received sequence sets where m or more successive data lie above $\displaystyle q_+$ or below $\displaystyle q_-$ .
2. A random subset of all the found sets is selected, so an attacker does not get any information on the received sequence. The center of each set is taken and the underlying index is selected as a list L. This list L is sent to Bob.
3. For each element of L Bob checks if around the index there is a set of $\displaystyle m-1$ data above $\displaystyle q_+$ or below $\displaystyle q_-$ .
4. Sometimes through the initial bit-errors some indexes in L will not result in appropriate sets of data. So Bob makes a list L' of all matches and sends L' to Alice.
5. Now both Alice and Bob can quantize their sequences at the indexes of L' to bit-strings. The result is $\displaystyle K_a$ and $\displaystyle K_b$ while $\displaystyle K_a = K_b$ .

With this an attacker does not get any information about the received sequences because Alice and Bob only exchange indexes of the sequences. Like so an attacker can only guess, if one specific is quantize to 0 or 1 which results to an probability of 1/2, the worst case.