Optimal re-encryption strategy for joins in encrypted databases

A non-transitory computer-readable storage medium coupled to one or more processors and having instructions stored thereon which, when executed by the one or more processors, cause the one or more processors to perform operations for selecting columns for re-encryption in join operations, the operations comprising:

• determining a first column and a second column to be joined;
• receiving a first key corresponding to the first column and a second key corresponding to the second column;
• receiving a first rank associated with the first key and a second rank associated with the second key;
• selecting the second column for re-encryption based on the first rank and the second rank;
• updating data associated with the first column and the second column based on selecting the second column for re-encryption and based on a cost associated with the second column, updating data comprising:
• adding the cost to the first rank, and
• subtracting the cost from the second rank;
• and
• providing the first column, the second column, and the first key for performing a join operation, the second column being re-encrypted based on the first key.

A system, comprising:

• a computing device;
• and
• a computer-readable storage device coupled to the computing device and having instructions stored thereon which, when executed by the computing device, cause the computing device to perform operations for selecting columns for re-encryption in join operations, the operations comprising:
• determining a first column and a second column to be joined;
• receiving a first key corresponding to the first column and a second key corresponding to the second column;
• receiving a first rank associated with the first key and a second rank associated with the second key;
• selecting the second column for re-encryption based on the first rank and the second rank;
• updating data associated with the first column and the second column based on selecting the second column for re-encryption and based on a cost associated with the second column, updating data comprising:
• adding the cost to the first rank, and
• subtracting the cost from the second rank;
• and
• providing the first column, the second column, and the first key for performing a join operation, the second column being re-encrypted based on the first key.