Suppose we have a DB with n records on it, one of the fields is numeric and considered sensitive (e.g. ID number). If we use tokenization for said field, could we query all records between x and y?
So far the only option I have seen depicted was preserving head and tail as it is and just tokenizing the middle part. I am not so convinced by that approach since it feels like too much leakage might be going on.
As I understand it then, should we limit its usage to searching(since it is a 1:1 map)?

P.S: I got this question while reading the white paper The Cloud Encryption Handbook. Where it reads:

Data tokenization involves creating tokens for each plaintext, . . . searching for keywords and SORTING DATA on the server are possible.

The user @pg1989 has co-authored it, so maybe he has interesting inputs about it as well.


1 Answer 1


Since I was specifically mentioned in the question, I'll take a stab at answering it.

First, note that the whitepaper was ghostwritten by a couple of marketing people. These (talented and lovely) marketing folks changed and simplified some terminology to match what is used in other marketing materials the company uses. This is pretty standard in industry, but it does sometimes result in things getting confused.

Here, the confusion is that two different kinds of tokenization are both being called "data tokenization". Regular old tokenization can support search because it is deterministic, but to preserve sort order you need to use a different tokenization algorithm. If you're curious you can read the details in this patent. The algorithm is more or less an embellishment on the BCLO order-preserving encryption scheme, but uses some clever tricks (which exploit the fact that you have all plaintext/ciphertext mappings available in the token database) to make token generation very fast. Otherwise, it has all the properties of the BCLO OPE scheme, which means that you actually can perform range queries on tokens.

Note, though, that the BCLO scheme has some very serious security drawbacks. Following a lower bound in a follow-up paper written by some of the same authors, a couple of recent works have found that the attack implied by this lower bound is devastating for security in basically any practical setting people actually care about. Perhaps more worryingly, these papers found that all OPE schemes (not just BCLO) that are efficient enough to deploy are vulnerable to serious attacks in practical settings.

If all you want to do is range queries, "more secure" approaches exist. The phrase "more secure" is in quotes because the extent to which they actually resist determined attacks is an open question right now. We know they resist existing attacks on OPE, but we don't know much else.

For example, last year a paper was published which showed that given enough queries, an attacker that only observes the amount of communication between a client and server (and no other leakage whatsoever) can fully recover plaintexts from any system which enables range queries on encrypted data. This attack requires a huge number of queries and is therefore not very practical, but there is some (not yet published) follow-up work which extends the attack to work with a very small number of queries. In systems with high query volume, this improved attack could completely recover the data in a matter of hours.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.