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 make search queries on an untrusted cloud server securely. Findex is concurrent and database-independent, allowing large database indexes to be outsourced securely without compromising usability.

Scientific paper: https://eprint.iacr.org/2024/1541

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$.

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	Block1		...	BlockB
		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):

$$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.

Avg locations	#records			size (in KB)			ratio
	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 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