Secret shared database joins using sorting

Patent metadata

Field	Value
Publication number	US-2025200048-A1
Application number	US-202318846214-A
Country	US
Kind code	A1
Filing date	Mar 17, 2023
Priority date	Apr 25, 2022
Publication date	Jun 19, 2025
Grant date	—

Abstract

Embodiments can perform a database join that allows secret shared database join between a database table with a unique matching column and a database table with a non-unique matching column (i.e., contains unbounded repeats of values).

First claim

1 . A method of performing a secret-shared join of a first database table and a second database table stored respectively on a first computer and a second computer, the method comprising performing, by the first computer, a multi-party computation in conjunction with the second computer:
storing the first database table having a first column and a second column, the first column used to join the first database table and the second database table, wherein the second database table includes the first column and a third column, wherein the first column is a matching column between the first database table and the second database table; distributing shares of the first database table to the second computer, wherein the second computer distributes shares of the second database table to the first computer; modifying first values of the of the matching column of the first database table by appending a first identifier that indicates the first values correspond to the first database table, thereby generating first modified values, wherein a first modified value includes a first value and the first identifier; modifying second values of the matching column of the second database table by appending a second identifier that indicates the second values correspond to the second database table, thereby generating second modified values, wherein a second modified value includes second value and the second identifier; generating an unsorted list that includes the first modified values and the second modified values; sorting the first modified values and the second modified values of the unsorted list to create a sorted list; determining a bit vector by comparing a current modified value of the sorted list to a previous modified value to determine whether the current modified value is a matching value, wherein a bit value in the bit vector specifies whether a row having the matching value of the first database table and a row having the matching value of the second database table are to be combined in a combined row of a combined database table; and generating the combined database table using the bit vector, values of the second column of the first database table, and values of the third column of the second database table.

2 . The method of claim 1 , wherein the row having the matching value in the first database table matches with multiple rows having the matching value in the second database table.

3 . The method of claim 1 , wherein the sorted list comprises one of the first modified values followed by one or more second modified values that match the one of the first modified values.

4 . The method of claim 1 , wherein the values of the matching column of the first database table are unique to each other.

5 . The method of claim 4 , wherein the secret-shared join is a one-to-many database join, wherein the matching column of the second database table is unbounded.

6 . The method of claim 1 , wherein the bit vector has a length equal to a sum of a number of rows in the first database table and a number of rows of the second database table.

7 . The method of claim 1 , wherein nodes of a tree are used to combine the row having the matching value in the first database table with one or more rows of the matching value of the second database table.

8 . The method of claim 7 , wherein the tree has an upstream phase for updating parent nodes starting from leaf nodes to a root node using a first set of functions, and a downstream phase for updating item values (v) of child nodes starting from the root node to the leaf nodes using a second set of functions after the upstream phase.

9 . The method of claim 8 , wherein the first set of functions is used to update each node of the tree in the upstream phase with an array of three values: node's current item (v), node's product bit (p), and node's left-most bit (l), wherein the array of three values is used during the downstream phase to update child nodes.

10 . The method of claim 8 , wherein the second set of functions specifies whether a row of an updated item value of a leaf node is to be combined with a row of an original item value before updating of the leaf node.

11 . The method of claim 1 , wherein a share of the first database table is generated by selecting a random number and then taking an XOR of the random number and a value of the first database table.

12 . A first computer comprising:
a processor; a network interface; and a non-transitory computer-readable medium comprising code for instructing the processor to implement a method of performing a secret-shared join of a first database table and a second database table stored respectively on the first computer and a second computer, the method comprising performing, by the first computer, a multi-party computation in conjunction with the second computer, the method comprising:
storing the first database table having a first column and a second column, the first column used to join the first database table and the second database table, wherein the second database table includes the first column and a third column, wherein the first column is a matching column between the first database table and the second database table;
distributing shares of the first database table to the second computer, wherein the second computer distributes shares of the second database table to the first computer;
modifying first values of the of the matching column of the first database table by appending a first identifier that indicates the first values correspond to the first database table, thereby generating first modified values, wherein a first modified value includes a first value and the first identifier;
modifying second values of the matching column of the second database table by appending a second identifier that indicates the second values correspond to the second database table, thereby generating second modified values, wherein a second modified value includes second value and the second identifier;
generating an unsorted list that includes the first modified values and the second modified values;
sorting the first modified values and the second modified values of the unsorted list to create a sorted list;
determining a bit vector by comparing a current modified value of the sorted list to a previous modified value to determine whether the current modified value is a matching value, wherein a bit value in the bit vector specifies whether a row having the matching value of the first database table and a row having the matching value of the second database table are to be combined in a combined row of a combined database table; and
generating the combined database table using the bit vector, values of the second column of the first database table, and values of the third column of the second database table.

13 . The first computer of claim 12 , wherein the row having the matching value in the first database table matches with multiple rows having the matching value in the second database table.

14 . The first computer of claim 12 , wherein the sorted list comprises one of the first modified values followed by one or more second modified values that match the one of the first modified values.

15 . The first computer of claim 12 , wherein the values of the matching column of the first database table are unique to each other.

16 . The first computer of claim 15 , wherein the secret-shared join is a one-to-many database join, wherein the matching column of the second database table is unbounded.

17 . The first computer of claim 12 , wherein the bit vector has a length equa

Assignees

• Visa Int Service Ass

Inventors

• Rindal Peter
• Badrinarayanan Saikrishna
• Raghuraman Srinivasan
• Garimella Gayathri Annapurna

Classifications

• G06F16/2282

  Tablespace storage structures; Management thereof · CPC title

• H04L2209/46

  Secure multiparty computation, e.g. millionaire problem · CPC title

• H04L9/0894

  Escrow, recovery or storing of secret information, e.g. secret key escrow or cryptographic key storage · CPC title

• H04L9/085

  Secret sharing or secret splitting, e.g. threshold schemes · CPC title

• G06F16/2456 Primary

  Join operations · CPC title