Findex

latest version

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 to index values by keywords. These values can be locations (UIDs of an encrypted database, URLs, paths, etc.).

Using Findex API one can:

index or desindex 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 FindexCallbacks trait. See callbacks.md for details on the implementation of the callbacks.

See in_memory_example.rs for a example of implementation.

Building and testing

To build Findex simply run:

bash cargo build --release

To test, run:

bash cargo test --release --all-features

To launch the benchmarks, run:

bash 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 which structure is given in the following tables, with $K{wi}$ the ephemeral key associated to a keyword $wi$, $H{wi}$ the hash of $wi$ and $UID{last}$ the last UID of the chain of indexed values associated to $wi$.

Entry Table
key	value
UID	$K_{w_i}$	$H_{w_i}$	$UID_{last}$

Chain Table
key	value
UID	$\textnormal{block}_1$	...	$\textnormal{block}_B$

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

	flag	Block₁		...	Block_B
	flag	prefix	data	...	prefix	data
Size (in bytes)	1	1	16	...	1	16

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):

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

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

math 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{wi} = 16~\textnormal{bytes}$
the length of the hash of the keyword: $H{wi} = 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.

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

Avg locations	#records			size (in KB)			ratio
Avg locations	naive	mixed	graph	naive	mixed	graph	mixed / naive	graph / naive
1	49016	53058	49316	6988	7564	7031	1.08	1.01
2	58253	57347	53526	8305	8176	7631	0.98	0.92
3	71455	61817	57949	10187	8813	8262	0.87	0.81
4	80692	66671	62785	11504	9505	8951	0.83	0.78
5	86048	72676	69014	12268	10362	9839	0.84	0.80

Benchmarks

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

Findex in memory (no database)

Documentation

Findex supporting paper can be found Findex.pdf. Documentation on callback implementation details can be found in callbacks.md.

The developer documentation can be found on doc.rs