# Encrypting the relationship between two database tables

I'm not a cryptography expert myself, and know enough to know that I shouldn't design my own crypto schemes, so I thought I'd seek advice here.

In an application, let's say we have two database tables: Lawyers and Clients. There exists a many-to-many relationship between these two models, so a Lawyer can have many Clients and a Client can have many Lawyers. As is typical in relational databases, there is a Join Table containing pointers to rows in each table in order to define the relationships between them.

The columns for the Join Table might look like this:

id | client_id | lawyer_id

Now let's say that in our security model, information about lawyers and information about clients are not considered privileged information on their own, so there's no need to encrypt them in any way. However, information about the relationship between Lawyers and Clients is privileged information that we would like to protect in the event an attacker gains access to the database.

Does there exist a common encryption scheme that securely encrypts client_id and lawyer_id without rendering the Join Table useless?

Provided that any user, who is supposed to have access to any relationship, may be granted access to all relationships, one solution would be to use a SQL engine that supports table level access control through table encryption, and encrypt the Join Table. In such case a decently implemented symmetric encryption scheme would be sufficient.

An attacker who gains physical access to the database files, will need the key for the Join table to be able to extract information from it. Conversely, if the attacker gains guest access to the database through the SQL interface, privilege elevation would be required to gain Join Table access.

However, such solutions are not sufficient e.g. in scenarios where any client is supposed to be able to run a query for his or her own lawyers, or conversely, where some lawyers are not allowed to run queries for any clients but their own. In such case, a trivial solution would be to encrypt each record separately, using a symmetric encryption scheme under a randomly generated content encryption key that, in turn, is encrypted using e.g. RSA-OAEP and the public RSA key of each user that is supposed to have access to the record, with the RSA cipher texts being stored in a fourth table. Such schemes would require the join process to be implemented to run locally (since the process would need access to the RSA private key).

Another alternative altogether would be to use Predicate Encryption, but such schemes are arguably very far from "common"-

• Thanks for the thoughtful response! I should have clarified in the question, but I think the threat scenario I'm trying to defend against is one where I assume the attacker has (somehow) acquired complete access to the database and application servers. I'm wondering if there's a way to accomplish the Join Table encryption in a manner similar to how we hash passwords so they aren't (theoretically) crack-able in the event they're all exposed. Aug 24 '18 at 9:28
• Sounds like the table-level encryption protects against physically stealing the drive. If I understand correctly, privileged access to certain tables is also moot if an attacker has also achieved privileged access to the app server (which presumably includes credentials to make a privileged connection to the DB). I think Public Key encryption fits the constraints, but gets complicated and requires a lot of decryption on the front-end as you note. It also makes it impossible for the server to do any kind of processing on the Join Table (e.g. for aggregate analysis). Aug 24 '18 at 9:34
• Seems like it's the case that, if I'm worried about an attacker stealing privileged DB credentials from the app server, it's actually impossible to have a purely cryptographic scheme (not just access controls) that both allows the application server to process the data in the Join Table and keeps that data encrypted such that an attacker with total access cannot decrypt the information. Would you agree? Aug 24 '18 at 9:36
• This depends on the db engine, but some, such as www.nexusdb.com supports table encryption in such manner that there is no single privileged state that will give the user access to all protected tables at once. As long as the hacker is not able to extract information from the running db engine process, there is no practical difference between letting your app or the db engine do the encryption, except in the latter case you will have seamless access to SQL functionality. Aug 24 '18 at 9:48
• That makes sense if I were to go the symmetrically encrypted tables route, but I'm working with the assumption the attacker has privileged database access. In that case, the data and relationships are exposed unless they are encrypted with a user's RSA public key (as you had suggested above), which is not known to the app. Since that key isn't known to the app, the app can't actually do anything with the data, no? In other words, in this threat model I think it's the case that the attacker always has as much data access as the app server does. Aug 24 '18 at 9:54