Intuitively, IND-CDBA means an attacker cannot tell which of two databases contains a record he picked.
In other words even if you know the passwords in a database. And even if there are only two possible databases to pick from. An attacker still cannot figure out which one is the right one.
This is the formal definition from the paper:
Indistinguishability of databases game $\text{IND-CDBA}_{\text{Adv}_r, \mathcal{PM}}(\kappa)$:
A challenger $\text{Ch}$ running $\mathcal{PM}$ interacts with
$\text{Adv}_r$ as follows:
- $\text{Ch}$ runs $\text{mp} \leftarrow \text{Setup}(1^\kappa)$
- $\text{Adv}_r$ outputs two record-sets $\text{RS}_0, \text{RS}_1$
- $\text{Ch}$ selects a bit $b$ uniformly at random and returns the database $\text{DB}_b \leftarrow \text{Create}(mp, \text{RS}_b)$ to
$\text{Adv}_r$
- $\text{Adv}_r$ eventually outputs bit $b'$ and wins if $b = b'$
This is similar to the familiar IND-CPA definition where you pick two messages and then you get an encryption of one of them and you have to guess which one it was.
Of course what this tells you in the end, is that you cannot learn any information about the passwords in a password file if this game is hard to win.