Queries on Encrypted Data Library

This section includes a deeper explanation of certain aspects of the library.

Security Parameter for Prime Sizes:

The Queries on Encrypted Data algorithms compute over a composite order elliptic curve group. This composite order elliptic curve group is generated in the setup algorithm, by randomly selecting two primes p and q, and then generating an elliptic curve group of order n=p*q.

We provide three choices for these prime sizes:

Message Key:

During the encrypt and query algorithms, a Message Key file is generated.

The msgkey_file can be deserialized* to a QED_MessageKey_t type. The QED_MessageKey_t contains an element_t key_elem**. We hash this key_elem and store the hash in an uint8_t *key_blob, with length size_t key_blob_len. (The structure declaration can be found in key.h in the types directory of the QED library.) This structure can be used by encrypt and query as described below, but is outside of the scope of this library:

*See Import/Export in the QED Library Manual for information on how to deserialize the msgkey_file.
**element_t is a PBC type for elements on the elliptic curve group.

Bloom filters and Epsilon Values:

For subset queries, we needed to find a way to map of raw data (i.e. the strings "foo" or "bar") to a bit vector. We use Bloom filter hashing to do this. (For more information on Bloom filters, refer to this wikipedia page.)

When using the Bloom filter, there is a probabilty of a false positive, causing the query algorithm to wrongly return true when a string not in the subset is used in encrypt. The prob parameter in the hveformat_file for subset (see setup) is the probability of this false positive.

We provide three choices for this probabilty parameter: