Findex

Findex aims to solve the following problem:

How to securely recover the location of an encrypted data matching a given keyword?

It is a cryptographic protocol designed to securely make search queries on an untrusted cloud server. Thanks to its encrypted indexes, large databases can securely be outsourced without compromising usability.

Findex is part of Cosmian Cloudproof Encryption.

• Getting started
• Building and testing
• Findex indexes
  • Two indexing strategies
• Benchmarks
• Documentation

Getting started

Findex allows indexing values by keywords. These values can be locations (UIDs of an encrypted database, URLs, paths, etc.).

Using Findex API one can:

• index or deindex values by keywords via the FindexUpsert trait;
• search for keywords via the FindexSearch trait;
• compact the indexes via the FindexCompact trait.

These traits can be automatically implemented and a macro is provided to help with the syntax. The default parameters (the ones used by the macro) are defined in parameters.rs.

Findex delegates to the user the implementation of callbacks to manipulate the indexes. This makes Findex compatible with any database technology since no database-specific code is part of it. Implementation is done via the

See in_memory_example.rs for an example of implementation.

Building and testing

To build Findex simply run:

cargo build --release

To test, run:

cargo test --release --all-features

To launch the benchmarks, run:

cargo bench --all-features

Findex indexes

Findex relies on two server-side indexes:

• Entry Table: provides the values needed to fetch the correct locations from the Chain Table. Each indexing keyword matches a line in the Entry Table.
• Chain Table: securely stores the indexed values. These indexed values may be locations or pointers to other keywords. Locations usually are database UIDs, but Findex can be used to index any kind of location (URL, path...). In order to make lines indistinguishable, the variable length indexed values are stored by blocks of fixed length and the same number of blocks is stored in each line (padding is added where necessary).

Findex indexes are key-value stores whose structure is given in the following tables, with $K_{w_i}$ the ephemeral key associated with a keyword $w_i$, $H_{w_i}$ the hash of $w_i$ and $UID_{last}$ the last UID of the chain of indexed values associated to $w_i$.

The Chain Table values are serialized as follows (sizes are given in bytes):

When stored, the values of the indexes are symmetrically encrypted with an AEAD. Our implementation uses a 16-bytes MAC tag and a 12-bytes nonce.

The flag is used to mark the blocks as being addition or deletions. Each bit corresponds to a block, which limits the possible number of blocks inside a single Chain Table value to 8. The prefix is used to write the actual length of the data stored inside a block.

Therefore:

• given $N$ the number of keywords used, the size of the Entry Table is given by (in bytes):

L_{entry~table} = (L_{uid} + C_e + L_{K_{w_i}} + L_{H_{w_i}} + L_{uid}) \cdot N
                = 140 \cdot N

• given $V(w_i)$ the volume of the keyword $w_i$ (i.e. the number of values indexed by this keyword) the size of the Chain Table is given by (in bytes):

L_{chain~table} = \left(L_{uid} + C_e + 1 + B * (1 + L_{block})\right) \sum\limits_{i~\in~[1,N]}\left\lceil \frac{V(w_i)}{B}\right\rceil
                = 146 \sum\limits_{i~\in~[1;N]}\left\lceil \frac{V(w_i)}{5}\right\rceil

where:

• the length of an UID: $L_{uid} = 32~\textnormal{bytes}$
• the length of the ephemeral key: $K_{w_i} = 16~\textnormal{bytes}$
• the length of the hash of the keyword: $H_{w_i} = 32~\textnormal{bytes}$
• the Chain Table width: $B = 5$
• the block length: $L_{block} = 16~\textnormal{bytes}$
• the encryption overhead: $C_e = 28~\textnormal{bytes}$

Two indexing strategies

Naive (locations are indexed for all possible slices):

• mar -> {locations}
• mart -> {locations}
• marti -> {locations}
• martin -> {locations}
• martine -> {locations}

Mixed:

• mar -> martine
• mart -> martine
• marti -> martine
• martin -> martine
• martine -> {locations}

Graph:

• mar -> mart
• mart -> marti
• marti -> martin
• martin -> martine
• martine -> {locations}

More client/server interactions are needed for the graph solution: the depth of the graph (4 in this example) compared to 1 for the naive solution and 2 for the mixed solution.

On the other hand, the graph solution optimizes the size of the Chain Table.

Benchmarks

The benchmarks presented in this section are run on an Intel(R) Xeon(R) Platinum 8171M CPU @ 2.60GHz.

• Findex in memory (no database)

Documentation

Findex supporting paper can be found the Findex whitepaper.

The developer documentation can be found on doc.rs