Blind Index Planning

CipherSweet includes a planner to assist developers in determining the safe sizes for an additional blind index on an encrypted field.

Using the planner is straightforward:

<?php
use ParagonIE\CipherSweet\Planner\FieldIndexPlanner;

# First, instantiate the planner for a given field
$planner = new FieldIndexPlanner();

# How many rows do you anticipate?
$planner->setEstimatedPopulation(50000);

# Next, add some information about existing fields
$planner->addExistingIndex('name_goes_here', 4, 16);
// ... etc.

$recommended = $planner->recommend();
var_dump($recommended);

This code snippet should yield the following:

array(2) {
  ["min"]=>
  int(4)
  ["max"]=>
  int(11)
}

In the above example, the existing index ("name_goes_here") has an output size of 4 bits and an input domain of 2^16 possible inputs (16 bits). That is where the 4 and 16 come from, respectively.

Input domain is the set of all possible distinct inputs.

For example: Calendar years consisting of 4-digit integers (2019) have an input domain of 10,000 possible values. The log (base 2) of 10,000 is 13.2877; you would want to always round up (so 14).

Output size is the number of bits (not bytes) of a blind index.

How to interpret this data:

If you make the additional index larger than 11, you introduce the risk of leaking data.
If you make it lower than 4, you'll have a lot of false positives and it really would not be worth creating this blind index.
If your additional index has a limited keyspace, you can pass the number of bits to the recommend() method to include this in the calculation.

Furthermore, you can use recommendLow() to only get the lower number, and recommendHigh() to only get the higher number.

Note: If there is no safe value for an additional index, the recommend methods will throw a PlannerException.

I Don't Know What Any Of That Means

Let's walk through using the planner one step at a time.

Let's say you're building an encrypted database for a local government that will service between 45,000 and 50,000 people in the next 10 years. Your Population can be assumed to be 50,000.

$planner = new FieldIndexPlanner();
$planner->setEstimatedPopulation(50000);

Starting from scratch, you won't have any existing indexes. The previous example included some, but we'll skip that for now.

So let's say you want to add an index just based on the population.

$recommended = $planner->recommend();
var_dump($recommended);
/*
array(2) {
  ["min"]=>
  int(8)
  ["max"]=>
  int(15)
}
*/

This means if you create your first index with an output size between 8 and 15, you're safe.

But let's say this first index is based on a smaller input domain (e.g. calendar year, as explained above) than your total population.

If we specify an input domain of 14 bits (smallest power of 2, where 2^n is larger than 10,000), we get a lower max recommendation than 15.

<?php
use ParagonIE\CipherSweet\Planner\FieldIndexPlanner;
$planner = new FieldIndexPlanner();
$planner->setEstimatedPopulation(50000);
$recommended = $planner->recommend(14);
var_dump($recommended);
/*
array(2) {
  ["min"]=>
  int(8)
  ["max"]=>
  int(14)
}
*/

Let's add a blind index with an output size of 8 and move on.

$field->addBlindIndex(
    new BlindIndex('birth_year_idx', [], 8, true)
);

And update our planner accordingly...

// 8 is the output size (in bits) we decided previously
// 14 because log_2(10000) is larger than 13 but smaller than 14
$planner->addExistingIndex('birth_year_idx', 8, 14);

Next, we want to know what the safe bounds are for an additional index on birth year (e.g. a compound index combining birth year with gender).

Since we used addExistingIndex(), we can simply run recommend() again to see what the safe range is.

<?php
use ParagonIE\CipherSweet\Planner\FieldIndexPlanner;
$planner = new FieldIndexPlanner();
$planner->setEstimatedPopulation(50000);
$planner->addExistingIndex('birth_year_idx', 8, 14);
$recommended = $planner->recommend();
/* 
array(2) {
  ["min"]=>
  int(1)
  ["max"]=>
  int(7)
}
*/

So if we want to create a second blind index on the same field, the only safe values are between 1 and 7 bits. Anything else will be useful for attackers.

That's all you need to know to use the planner safely. The jargon isn't super important.

Next: Key/Backend Rotation