# US 10,769,295 B2 · Join operations on encrypted database tables > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 10,769,295 B2 - Document ID: US10769295B2 - Status: Granted - Kind: B2 - Application number: 15/874,698 - Filed: 2018-01-18 - Published: 2019-07-18 - Granted: 2020-09-08 - Earliest claimed: 2018-01-18 - Assignees: Sap SE - Applicants: Sap SE - Inventors: Nicolas Loza; Florian Hahn; Florian Kerschbaum - Web page: https://patentgrep.com/patent/US10769295B2 ## CPC - G06F 21/6227: {where protection concerns the structure of data, e.g. records, types, queries} - G06F 16/2456: {Join operations} - G06F 21/602: {Providing cryptographic facilities or services} - H04L 9/14: using a plurality of keys or algorithms - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) - H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M) ## Abstract Embodiments allow join operations to be performed upon encrypted database tables stored on an unsecure server (e.g., as part of a DBaaS offering), with reduced information leakage. Such secure join operations may be implemented through the combination of two cryptographic techniques: non-deterministic (randomized) searchable encryption; and attribute based encryption. The searchable encryption (e.g., Symmetric Searchable Encryption: SSE) allows join values to be revealed only for rows fulfilling additional predicate attributes that the client has filtered for, thereby offering fine granular security. The attribute based encryption (e.g., Key-Policy Attribute-Based Encryption: KP-ABE) avoids the unmanageable consumption of memory that would otherwise result from the creation of intermediate constructions on the server. Embodiments offer a solution reducing information leakage of join values not contained in the result of the actual database query. This results in fine granular security because join values of data rows not involved in the join computation, remain semantically secure. ## Claims ### Claim 1 A computer-implemented method comprising: a server storing in a database, a first encrypted table and a second encrypted table encrypted according to a non-deterministic and searchable first encryption scheme; the server receiving from a client, a join token based upon a query including a join operation and a predicate attribute constraint; an engine of the server, prior to joining the first encrypted table and the second encrypted table, separately searching the first encrypted table according to the predicate attribute constraint to reveal only rows of the first encrypted table fulfilling the predicate attribute constraint and searching the second encrypted table according to the predicate attribute constraint to reveal only rows of the second encrypted table fulfilling the predicate attribute constraint, the engine generating an intermediate construction including only rows of the first encrypted table and the second encrypted table fulfilling the predicate attribute constraint, the intermediate construction encrypted according to a different encryption scheme; and the server communicating to the client, the rows of the first encrypted table and the second encrypted table fulfilling the predicate attribute constraint. ### Claim 2 (depends on 1) A method as in claim 1 wherein the non-deterministic and searchable encryption scheme is randomized. ### Claim 3 (depends on 2) A method as in claim 2 wherein the non-deterministic and searchable encryption scheme comprises Symmetric Searchable Encryption (SSE). ### Claim 4 (depends on 1) A method as in claim 1 wherein the join token reflects the constraint expressed in a WHERE clause of the query. ### Claim 5 (depends on 1) A method as in claim 1 wherein the another encryption scheme comprises attribute based encryption. ### Claim 6 (depends on 5) A method as in claim 5 wherein the attribute based encryption comprises Key-Policy Attribute-Based Encryption (KP-ABE). ### Claim 7 (depends on 1) A method as in claim 1 wherein the first encrypted table and the second encrypted table are outsourced to the server from the client. ### Claim 8 (depends on 1) A method as in claim 1 wherein the first encrypted table and the second encrypted table are outsourced to the server from other than the client. ### Claim 9 (depends on 1) A method as in claim 1 wherein database comprises an in-memory database, and the engine comprises an in-memory database engine. ### Claim 10 A non-transitory computer readable storage medium embodying a computer program for performing a method, said method comprising: a server storing in an in-memory database, a first encrypted table and a second encrypted table encrypted according to a non-deterministic and searchable first encryption scheme; the server receiving from a client, a join token based upon a query including a join operation and a predicate attribute constraint; an in-memory database engine of the server, prior to joining the first encrypted table and the second encrypted table, separately searching the first encrypted table according to the predicate attribute constraint to reveal only rows of the first encrypted table fulfilling the predicate attribute constraint and searching the second encrypted table according to the predicate attribute constraint to reveal only rows of the second encrypted table fulfilling the predicate attribute constraint, the engine generating an intermediate construction including only rows of the first encrypted table and the second encrypted table fulfilling the predicate attribute constraint, the intermediate construction encrypted according to a different encryption scheme; and the server communicating to the client, the rows of the first encrypted table and the second encrypted table fulfilling the predicate attribute constraint. ### Claim 11 (depends on 10) A non-transitory computer readable storage medium as in claim 10 wherein the non-deterministic and searchable encryption scheme comprises Symmetric Searchable Encryption (SSE). ### Claim 12 (depends on 10) A non-transitory computer readable storage medium as in claim 10 wherein the another encryption scheme comprises attribute based encryption. ### Claim 13 (depends on 12) A non-transitory computer readable storage medium as in claim 12 wherein the attribute based encryption comprises Key-Policy Attribute-Based Encryption (KP-ABE). ### Claim 14 (depends on 10) A non-transitory computer readable storage medium as in claim 10 wherein the first encrypted table and the second encrypted table are outsourced to the server from other than the client. ### Claim 15 (depends on 10) A non-transitory computer readable storage medium as in claim 10 wherein join token reflects the constraint expressed in a WHERE clause of the query. ### Claim 16 A computer system comprising: one or more processors; a software program, stored in memory, executed on said computer system, the software program configured to cause an in-memory database engine to: store in an in-memory database, a first encrypted table and a second encrypted table encrypted according to a non-deterministic and searchable first encryption scheme; receive from a client, a join token based upon a query including a join operation and a predicate attribute constraint; search, prior to joining the first encrypted table and the second encrypted table, the first encrypted table according to the predicate attribute constraint to reveal only rows of the first encrypted table fulfilling the predicate attribute constraint, and separately search the second encrypted table according to the predicate attribute to reveal only rows of the second encrypted table fulfilling the predicate attribute constraint, and generate an intermediate construction including only rows of the first encrypted table and the second encrypted table fulfilling the predicate attribute constraint, the intermediate construction encrypted according to a different encryption scheme; and communicate to the client, the rows of the first encrypted table and the second encrypted table fulfilling the predicate attribute constraint. ### Claim 17 (depends on 16) A computer system as in claim 16 wherein the non-deterministic and searchable encryption scheme comprises Symmetric Searchable Encryption (SSE). ### Claim 18 (depends on 16) A computer system as in claim 16 wherein the another encryption scheme comprises Key-Policy Attribute-Based Encryption (KP-ABE). ### Claim 19 (depends on 16) A computer system as in claim 16 wherein the join token reflects the constraint expressed in a WHERE clause of the query. ### Claim 20 (depends on 16) A computer system as in claim 16 wherein the first encrypted table and the second encrypted table are received from other than the client.