Skip to content

Encrypted Search API

Cosmian Findex is a Searchable Encryption scheme that allows the building of encrypted indexes. One can efficiently search these encrypted indexes using encrypted queries and receive encrypted responses.

Benefits

Since the environment cannot learn anything about the content of the index, the queries, or the responses, one can use Zero-Trust environments, such as the public cloud, to store the indexes.

sse

User workflow

  1. Using a client library (java, python, js, ios, android, etc.), the user supplies a searched keyword and encrypts it using a secret key.

  2. The client library issues two encrypted requests to the key-value store storing the index (the key-value store can be any store of your choice - see below)

  3. The client library decrypts the response, typically the locations in the main DB where the keyword is found.

The user will then query the main DB for the given records, encrypted with attributes encryption, and decrypt what their private key allows.

Implementing the Index DB tables callbacks

The Findex library abstracts the calls to the tables hosting the indexes.

The developer is expected to provide the database’s backend, typically a fast key/value store, and implement the necessary code in the callbacks used by Findex.

Findex uses two tables: the Entry table and the Chain table. Both have two columns: uid and value.

The type UidsAnValues represents a (uid, value) tuple, i.e., a line, in the Entry or Chain table. Its definition is

type UidsAndValues = Array<{ uid: Uint8Array, value: Uint8Array }>

With regards to the Findex callbacks, the developer should provide instantiations of the following function types

/**
 * Fetch a uid in the Entry table and return the (uid, value) column
 */
type FetchEntries = (uids: Uint8Array[]) => Promise<UidsAndValues>

/**
 * Fetch a uid in the Chain table and return the (uid, value) column
 */
type FetchChains = (uids: Uint8Array[]) => Promise<UidsAndValues>

/**
 * Insert, or update an existing (uid, value) line in the Entry table
 */
type UpsertEntries = (uidsAndValues: UidsAndValues) => Promise<void>

/**
 * Insert, or update an existing (uid, value) line in the Chain table
 */
type UpsertChains = (uidsAndValues: UidsAndValues) => Promise<void>

For instance, the implementation for an in-memory store could be

const entryTable: { [uid: string]: Uint8Array } = {}
const chainTable: { [uid: string]: Uint8Array } = {}

const fetchEntries: FetchEntries = async (
    uids: Uint8Array[]
): Promise<UidsAndValues> => {
    const results: UidsAndValues = []
    for (const uid of uids) {
        const value = entryTable[hexEncode(uid)]
        if (typeof value !== "undefined") {
            results.push({ uid, value })
        }
    }
    return await Promise.resolve(results)
}

const fetchChains: FetchChains = async (
    uids: Uint8Array[]
): Promise<UidsAndValues> => {
    const results: UidsAndValues = []
    for (const uid of uids) {
        const value = chainTable[hexEncode(uid)]
        if (typeof value !== "undefined") {
            results.push({ uid, value })
        }
    }
    return await Promise.resolve(results)
}

const upsertEntries: UpsertEntries = async (
    uidsAndValues: UidsAndValues
): Promise<void> => {
    for (const { uid, value } of uidsAndValues) {
        entryTable[hexEncode(uid)] = value
    }
    return await Promise.resolve()
}

const upsertChains: UpsertChains = async (
    uidsAndValues: UidsAndValues
): Promise<void> => {
    for (const { uid, value } of uidsAndValues) {
        chainTable[hexEncode(uid)] = value
    }
    return await Promise.resolve()
}

The developer should provide the implementation of a series of callback declared in the interface FfiWrapper. A sample implementation of these callbacks for Sqlite is available in the class SqLite

public FetchEntry fetchEntry = new FetchEntry(new com.cosmian.jna.findex.FfiWrapper.FetchEntryInterface() {
    @Override
    public HashMap<byte[], byte[]> fetch(List<byte[]> keys) throws FfiException {
        try {
            //TODO Fetch Entry table items using keys, return a map key->value
        } catch (SQLException e) {
            throw new FfiException("Failed fetch entry: " + e.toString());
        }
    }
});
public FetchAllEntry fetchAllEntry =
    new FetchAllEntry(new com.cosmian.jna.findex.FfiWrapper.FetchAllEntryInterface() {
        @Override
        public HashMap<byte[], byte[]> fetch() throws FfiException {
            try {
                //TODO Fetch all Entry table items, return a map key->value
            } catch (SQLException e) {
                throw new FfiException("Failed fetch all entry: " + e.toString());
            }
        }
    });
public UpsertEntry upsertEntry = new UpsertEntry(new com.cosmian.jna.findex.FfiWrapper.UpsertEntryInterface() {
    @Override
    public void upsert(HashMap<byte[], byte[]> keysAndValues) throws FfiException {
        try {
            //TODO upsert all the tuples key->value of keysAndValues in the Entry table
        } catch (SQLException e) {
            throw new FfiException("Failed entry upsert: " + e.toString());
        }
    }
});
public FetchChain fetchChain = new FetchChain(new com.cosmian.jna.findex.FfiWrapper.FetchChainInterface() {
    @Override
    public HashMap<byte[], byte[]> fetch(List<byte[]> keys) throws FfiException {
        try {
            //TODO Fetch Chain table items using keys, return a map key->value
        } catch (SQLException e) {
            throw new FfiException("Failed fetch chain: " + e.toString());
        }
    }
});
public UpsertChain upsertChain = new UpsertChain(new com.cosmian.jna.findex.FfiWrapper.UpsertChainInterface() {
    @Override
    public void upsert(HashMap<byte[], byte[]> keysAndValues) throws FfiException {
        try {
            //TODO upsert all the tuples key->value of keysAndValues in the Chain table
        } catch (SQLException e) {
            throw new FfiException("Failed chain upsert: " + e.toString());
        }
    }
});
public UpdateLines updateLines = new UpdateLines(new com.cosmian.jna.findex.FfiWrapper.UpdateLinesInterface() {
    @Override
    public void update(List<byte[]> removedChains, HashMap<byte[], byte[]> newEntries,
        HashMap<byte[], byte[]> newChains) throws FfiException {
        try {
            // Note: used by the compact algorithm
            //TODO 1- truncate the Entry table
            //TODO 2- upsert all the tuples key->value of newEntries in the Entry table
            //TODO 3- upsert all the tuples key->value of newChains in the Chain tables
            //TODO 4- remove all the tuples key->value of removedChains in the Chain tables
        } catch (SQLException e) {
            throw new FfiException("Failed update lines: " + e.toString());
        }
    }
});
public ListRemovedLocations listRemovedLocations =
    new ListRemovedLocations(new com.cosmian.jna.findex.FfiWrapper.ListRemovedLocationsInterface() {
        @Override
        public List<Location> list(List<Location> locations) throws FfiException {
            //TODO return the sub list of all the locations in the main DB that do
            // not exist anymore within this list
        }
    });
public Progress progress = new Progress(new com.cosmian.jna.findex.FfiWrapper.ProgressInterface() {
    @Override
    public boolean list(List<byte[]> indexedValues) throws FfiException {

        //TODO implement feedback (to the final user). This method is called
        // by the search function when it progresses along the graph of a searched
        // keyword. If you return false, the search stops progressing along the graph
    }
});

Generating the Findex keys

Findex uses two keys, k and k* (k star):

  • k, also called the search key used by all users: those making updates and those making queries,
  • k*, also called the update key used by users making updates only

To generate symmetric keys in a Cosmian KMS server, find the server address and - unless you run in dev mode - an API Key to authenticate to the server.

// instantiate a KMS KMIP client
const client: KmipClient = new KmipClient(
    new URL("http://localhost:9998/kmip/2_1")
)

// create two 256bit symmetric keys meant for AES
// k
const searchKeyId = await client.createSymmetricKey(
    SymmetricKeyAlgorithm.AES,
    256
)
const searchKey = await client.retrieveSymmetricKey(searchKeyId)
// k*
const updateKeyId = await client.createSymmetricKey(
    SymmetricKeyAlgorithm.AES,
    256
)
const updateKey = await client.retrieveSymmetricKey(updateKeyId)

The k and k* keys are 256bit keys used with AES 256 GCM. To generate 32 random bytes locally, use the randomBytes generator from 'crypto'

import { randomBytes } from 'crypto'

const searchKey = new FindexKey(randomBytes(32))
const updateKey = new FindexKey(randomBytes(32))

The k and k* keys are 256bit keys used with AES 256 GCM. To generate 32 random bytes use the SecureRandom cryptographically secure random number generator (CSRNG)

SecureRandom random = new SecureRandom();
byte[] key = new byte[32];
random.nextBytes(key);
(soon)

Indexing: inserting and updating keywords

keywords and their indexed values

Findex maintains a key -> value relationship Keyword -> IndexedValue The IndexedValue may be:

  • a Location (such as a DB record uid, file name, …)
  • or another Keyword (for instance, “Bob” may point to “Robert”, so querying “Bob” will also return the Locations for “Robert”).

To perform insertions or updates (a.k.a upserts), supply an array of IndexedEntry. This structure maps an IndexedValue to a list of Keywords. Its definition is

/**
* A new value to index for a given set of keywords:
* IndexedValue -> Set<KeyWord>
*/
export interface IndexedEntry {
    indexedValue: IndexedValue
    keywords: Set<Keyword>
}

There are two helper classes to build IndexEntry:

For indexing Locations, LocationIndexEntry takes in its constructor

  • a location as a string or a Uint8Array,
  • an array of keywords as a string[] or a Uint8Array[].

 const entry = new LocationIndexEntry(
    "file://docs/project42.doc",
    ["Robert", "Project 42"]
)
For indexing a Keyword pointing to another Keyword use KeywordIndexEntry:

// Bob points to Robert
const entryKeyword_ = new KeywordIndexEntry("Bob", "Robert")

labeling: salting the encryption

When indexing, encryption uses an arbitrary label; this label may represent anything, such as a period, e.g., “Q1 2022”, as long as it changes when the index is compacted or recreated. Changing it regularly significantly increases the difficulty of performing statistical attacks.

const label = new Label("Week 13")

upserting the entries

Now that:

call the upsert function :

/**
 * Insert or update existing (a.k.a upsert) entries in the index
 *
 * @param {IndexedEntry[]} newIndexedEntries new entries to upsert in indexes
 * @param {FindexKey | SymmetricKey} searchKey Findex's read key
 * @param {FindexKey | SymmetricKey} updateKey Findex's write key
 * @param {Label} label public label for the index
 * @param {FetchEntries} fetchEntries callback to fetch the entries table
 * @param {UpsertEntries} upsertEntries callback to upsert inside entries table
 * @param {UpsertChains} upsertChains callback to upsert inside chains table
 */
export async function upsert(
    newIndexedEntries: IndexedEntry[],
    searchKey: FindexKey | SymmetricKey,
    updateKey: FindexKey | SymmetricKey,
    label: Label,
    fetchEntries: FetchEntries,
    upsertEntries: UpsertEntries,
    upsertChains: UpsertChains
): Promise<void> {
    ...
}
const { upsert } = await Findex();

await upsert(
    [
        {
            indexedValue: IndexedValue.fromLocation(new Location(Uint8Array.from([0, 0, 1]))),
            keywords: new Set([
                Keyword.fromUtf8String("John"),
                Keyword.fromUtf8String("Doe"),
            ]),
        },
        {
            indexedValue: IndexedValue.fromLocation(new Location(Uint8Array.from([0, 0, 2]))),
            keywords: new Set([
                Keyword.fromUtf8String("Jane"),
                Keyword.fromUtf8String("Doe"),
            ]),
        },
    ],
    searchKey,
    updateKey,
    label,
    async (uids) => {
        // Return the entry table
    },
    async (uidsAndValues) => {
        // Save the new uidsAndValues inside the entry table
    },
    async (uidsAndValues) => {
        // Save the new uidsAndvalues inside the chain table
    },
);

keywords and their indexed values

Findex maintains a key -> value relationship Keyword -> IndexedValue The IndexedValue may be:

  • a Location (such as a DB record uid, file name, …)
  • or another Word (for instance, “Bob” may point to “Robert”, so querying “Bob” will also return the Locations for “Robert”).

The class IndexedValue can be constructed using either a Location or a Word as appropriate.

master keys: create the MasterKeys instance

To perform updates, first create the MasterKeys instance by injecting the 2 keys k and k*

 MasterKeys masterKeys = new MasterKeys(k, k_star);

labeling: salting the encryption

When indexing, encryption uses an arbitrary label; this label may represent anything, such as a period, e.g., “Q1 2022”, as long as it changes when the index is compacted or recreated. Changing it regularly significantly increases the difficulty of performing statistical attacks.

byte[] label = new byte[] {1,2,3,4};

upserting entries

To upsert locations, create a map

HashMap<IndexedValue, Word[]> indexedValuesAndWords = new HashMap<>();
// fill the map of Indexed Values and the corresponding keywords

Ffi.graph_upsert(
    masterKeys, 
    label, 
    indexedValuesAndWords, 
    fetchEntry,   // -> FetchEntry callback
    upsertEntry,  // -> UpsertEntry callback
    upsertChain   // -> UpsertChain callback
);

Querying the index

Querying the index is performed using the search function.

The progress callback sends back the IndexedValues found as the search algorithm walks the index graph. It is a callback function with a signature

    (indexedValues: IndexedValue[]) => Promise<boolean>

Assuming the keywords graph car -> care -> caret, and a search for anything starting with car, the progress callback will be called 3 times, returning locations found for car, then care, and finally caret.

Returning false in the callback will immediately stop the algorithm from further walking the graph.

/**
 * Search indexed keywords and return the corresponding IndexedValues
 *
 * @param {Set<string>} keywords keywords to search inside the indexes
 * @param {FindexKey | SymmetricKey} searchKey Findex's read key
 * @param {Label} label public label for the index
 * @param {FetchEntries} fetchEntries callback to fetch the entries table
 * @param {FetchChains} fetchChains callback to fetch the chains table
 * @param {Progress} progress the optional callback of found values as the search graph is walked.
 *    Returning false stops the walk
 * @returns {Promise<IndexedValue[]>} a list of `IndexedValue`
*/
export async function search(
    keywords: Set<string>,
    searchKey: FindexKey | SymmetricKey,
    label: Label,
    fetchEntries: FetchEntries,
    fetchChains: FetchChains,
    progress?: Progress
): Promise<IndexedValue[]> {
    ...
}
const { search } = await Findex();

const indexedValues = await search(
    new Set(["Doe"]),
    searchKey,
    label,
    async (uids) => {
        // Fetch entry table
    },
    async (uids) => {
        // Fetch chain table
    },
);

// IndexedValues will contain 0,0,1 and 0,0,2

The progress callback sends back the IndexedValues found as the search algorithm walks the index graph. It is a callback function with a signature

    public boolean list(List<byte[]> indexedValues) throws FfiException;

Assuming the keywords graph car -> care -> caret, and a search for anything starting with car, the progress callback will be called 3 times, returning locations found for car, then care, and finally caret.

Returning false in the callback will immediately stop the algorithm from further walking the graph.

    Ffi.search(
        key_k, 
        label, 
        new Word[] {new Word("TheWord")}, 
        0,
        -1, 
        db.progress, 
        db.fetchEntry, 
        db.fetchChain
    )

© Copyright 2018-2022 Cosmian. All rights reserved