Searchable encryption

Searchable encryption enables you to search encrypted records without decrypting the entire database. This is accomplished using beacons, which create a map between the plaintext value written to a field and the encrypted value that is actually stored in your database. The AWS Database Encryption SDK stores the beacon in a new field that it adds to the record. Depending on the type of beacon you use, you can perform exact match searches or more customized complex queries on your encrypted data.

A beacon is a truncated Hash-Based Message Authentication Code (HMAC) tag that creates a map between the plaintext and encrypted values of a field. When you write a new value to an encrypted field that's configured for searchable encryption, the AWS Database Encryption SDK calculates an HMAC over the plaintext value. This HMAC output is a one‐to‐one (1:1) match for the plaintext value of that field. The HMAC output is truncated so that multiple, distinct plaintext values map to the same truncated HMAC tag. These false positives limit an unauthorized user's ability to identify distinguishing information about the plaintext value. When you query a beacon, the AWS Database Encryption SDK automatically filters out these false positives and returns the plaintext result of your query.

The average number of false positives generated for each beacon is determined by the beacon length remaining after truncation. For help determining the appropriate beacon length for your implementation, see Determining beacon length.

Are beacons right for my dataset?

Using beacons to perform queries on encrypted data reduces the performance costs associated with client-side encrypted databases. When you use beacons, there is an inherent tradeoff between how efficient your queries are and how much information is revealed about the distribution of your data. The beacon does not alter the encrypted state of the field. When you encrypt and sign a field with the AWS Database Encryption SDK, the plaintext value of the field is never exposed to the database. The database stores the randomized, encrypted value of the field.

Beacons are stored alongside the encrypted fields they are calculated from. This means that even if an unauthorized user cannot view the plaintext values of an encrypted field, they might be able to perform statistical analysis on the beacons to learn more about the distribution of your dataset, and, in extreme cases, identify the plaintext values that a beacon maps to. The way you configure your beacons can mitigate these risks. In particular, choosing the right beacon length can help you preserve the confidentiality of your dataset.

Searchable encryption might not be able to provide the desired levels of both performance and security for all datasets. Review your threat model, security requirements, and performance needs before configuring any beacons.

Consider the following dataset uniqueness requirements as you determine whether searchable encryption is right for your dataset.

Even if your dataset contains correlated fields or has an uneven distribution, you might be able to construct beacons that preserve the confidentiality of your dataset by using shorter beacon lengths. However, beacon length does not guarantee that every unique value in your dataset will produce a number of false positives that effectively minimizes the amount of distinguishing information revealed about your dataset. Beacon length only estimates the average number of false positives produced. The more unevenly distributed your dataset, the less effective beacon length is at determining the average number of false positives produced.

Carefully consider the distribution of the fields you construct beacons from and consider how much you will need to truncate the beacon length to meet your security requirements. The following topics in this chapter assume that your beacons are uniformly distributed and do not contain correlated data.

Searchable encryption scenario

The following example demonstrates a simple searchable encryption solution. In application, the example fields used in this example might not meet the distribution and correlation uniqueness recommendations for beacons. You can use this example for reference as you read about the searchable encryption concepts in this chapter.

Consider a database named Employees that tracks employee data for a company. Each record in the database contains fields called EmployeeID, LastName, FirstName, and Address. Each field in the Employees database is identified by the primary key EmployeeID.

The following is an example plaintext record in the database.

{
    "EmployeeID": 101,
    "LastName": "Jones",
    "FirstName": "Mary",
    "Address": {
                "Street": "123 Main",
                "City": "Anytown",
                "State": "OH",
                "ZIPCode": 12345
    }
}

If you marked the LastName and FirstName fields as ENCRYPT_AND_SIGN in your cryptographic actions, the values in these fields are encrypted locally before they're uploaded to the database. The encrypted data that is uploaded is fully randomized, the database doesn't recognize this data as being protected. It just detects typical data entries. This means that the record that is actually stored in the database might look like the following.

{
    "PersonID": 101,
    "LastName": "1d76e94a2063578637d51371b363c9682bad926cbd",
    "FirstName": "21d6d54b0aaabc411e9f9b34b6d53aa4ef3b0a35",
    "Address": {
                "Street": "123 Main",
                "City": "Anytown",
                "State": "OH",
                "ZIPCode": 12345
    }
}

If you need to query the database for exact matches in the LastName field, configure a standard beacon named LastName to map the plaintext values written to the LastName field to the encrypted values stored in the database.

This beacon calculates HMACs from the plaintext values in the LastName field. Each HMAC output is truncated so that it is no longer an exact match for the plaintext value. For example, the complete hash and the truncated hash for Jones might look like the following.

Complete hash

2aa4e9b404c68182562b6ec761fcca5306de527826a69468885e59dc36d0c3f824bdd44cab45526f70a2a18322000264f5451acf75f9f817e2b35099d408c833

Truncated hash

b35099d408c833

After the standard beacon is configured, you can perform equality searches on the LastName field. For example, if you want to search for Jones, use the LastName beacon to perform the following query.

LastName = Jones

The AWS Database Encryption SDK automatically filters out the false positives and returns the plaintext result of your query.