On the Use of Deltas in Linux Entropy Estimators

Question

Recently, I've become interested in applied cryptography and stumbled upon a link explaining how Linux estimates entropy.

At some point, we're told that entropy estimation is based on first, second and third differences of the timestamps of certain system events. Fair enough. What I didn't understand was the intuition behind this, explained in the link as follows:

This use of deltas is approximately the same as attempting to fit an n degree polynomial to the previous n+1 points, then looking to see how far the new point is from the best prediction based on the previous n points. The minimum of the deltas is used, which has the effect of taking the best fit of a 0th, 1st or 2nd degree polynomial, and using that one.

To clarify, here's what (I think) I've understood. Taking the example of mouse events in the link:

Mouse event times       1004   1012    1024    1025    1030    1041

1st differences              8      12       1       5      11

2nd differences                  4       11      4       6

3rd differences                      7       7       2

Fit an n degree polynomial to the previous n+1 points: I guess that would be taking the (i+1)-th diff, which are the 1st diffs of the i-th diffs. These could be used to predict the next values of the i-th diff, hence the 'fitting'. E.g. the 1st diff explains how consecutive values of the mouse event line (0th diff) change.

How far the new point is from the best prediction based on the previous n points: I guess this is given by the (i+2)-th diff? E.g. after the last mouse event time, 1041, the 2nd diff is 6, which is how far 1041 (the new point) is from 1035 (the best prediction). The prediction is obtained by taking the previous 0th diff value, 1030, added to the previous 1st diff value, 5.

Use of minimum delta: My best guess is that the entropy estimator chooses minimum value, because it is the best fit for the (i-1)-th diff (or (i-1)-th degree polynomial). I think I understand how this method picks the best fit, but I really didn't get the 'why' though.

My doubts/questions are:

• I may be overlooking something obvious, but I still don't see the relation between my idea of n degree polynomial fitting (e.g. polynomial regression using a least squares method).
• What's the actual rationale behind choosing the minimum delta? Why does it provide a good measure of how unexpected the next data point is? Is it because the minimum delta is the most conservative?

Answer 1

The estimator uses minimum third delta because the degree of the fitted polynomial of it is the entropy of the dataset. In the first example, the minimum delta was 2, its base 2 log is 1, therefore the data overall added 1 bit of entropy. Why the minimum delta? It is because using it allows to represent the entropy (in other words, unpredictability) of the entire dataset as a one-digit number. If you look at the entropy measurements in the first two examples (1 and 2 bits), you can see that they translate to 1st delta values of about 10 and 100, respectively. Accordingly, entropy of 3 would mean 1st deltas of about 1,000, 4 - 10,000, and so forth. In summary, in our delta representation we went from multiple to single digits by using the polynomial degree of the minimum third delta.