Updated to v1.2 on 1/3/2023.
Although it’s widely agreed that field-level data encryption provides the best protection against data breaches, it also limits an application’s ability to perform ranged searches, where an inequality comparison is performed against search terms.
Although there are existing strategies which use search trees, these depend on complex key management schemes, or trees with fixed intervals.
Another common approach is to assign artificial search keys, but the general problem with this approach is that it can result in information disclosure as well as key collisions. If the keys are regularly-spaced, this can lead to an inference about the underlying data values, and if the spacing is too narrow, this can lead to insufficient search keys when presented with a large quantity of data values for given key interval.
In the scheme proposed herein, a binary tree is used to generate integer search keys, called comparators, that are non-sequential but maintain the same ordinal relationship as the underlying data. Because comparators have no fixed relationship to each other, they don’t leak any information, but because they maintain an ordinal relationship, they can be searched with a ranged query.
Click here to view or download: