Secure join protocol in encrypted databases

Abstract

Computer systems and associated methods are disclosed to implement a table join protocol for two encrypted database tables using two different servers. In embodiments, responsive to a query that specifies a join of two tables, a first server performs a join operation on encrypted representations of the join attributes of two rows from the two tables to determine an encrypted join indicator. The join attributes are encrypted in a scheme that is homomorphic with respect to the join operation. The first server sends the join indicator to a second server to be decrypted, and then uses the decrypted join indicator to determine whether the two rows satisfies the join. In embodiments, the first server does not possess the decryption key for the encrypted representations, and the second server does not have access to the encrypted representations. The division of labor thus reduces the vulnerability of both individual servers.