Apparatus and method with intersection operation
A processor-implemented method includes receiving, from a first device, ciphertext corresponding to elements of a first data set of the first device, performing, based on a match function defined for elements of a second data set of a second device, an intersection operation between the ciphertext and the elements of the second data set, and transmitting a result of the intersection operation to the first device, wherein the ciphertext is generated based on an elementary symmetric polynomial corresponding to the elements of the first data set.
1 . A processor-implemented method comprising:
receiving, from a first device, ciphertext generated by encrypting a precomputation formula defined based on an elementary symmetric polynomial corresponding to elements of a first data set of the first device;
performing, based on a match function defined for elements of a second data set of a second device, an intersection operation between the ciphertext and the elements of the second data set; and
transmitting a result of the intersection operation to the first device.
2 . The method of claim 1 , wherein the performing of the intersection operation comprises performing a linear combination operation of the ciphertext and a power of the elements of the second data set.
3 . The method of claim 2 , wherein the performing of the intersection operation further comprises performing an additional operation to obtain elements of the intersection based on a result of the linear combination operation and the elements of the second data set.
4 . The method of claim 3 , wherein the transmitting of the intersection operation result comprises transmitting the linear combination operation result and a result of the additional operation to the first device.
5 . The method of claim 1 , wherein a number of the elements of the first data set is less than a number of the elements of the second data set.
6 . The method of claim 1 , wherein an accumulated number of homomorphic multiplication operations in the intersection operation is “1”.
7 . The method of claim 1 , wherein the ciphertext is ciphertext based on ring learning with errors (RLWE).
8 . A non-transitory computer-readable storage medium storing instructions that, when executed by one or more processors, configure the one or more processors to perform the method of claim 1 .
9 . A processor-implemented method comprising:
obtaining an elementary symmetric polynomial corresponding to elements of a first data set of a first device;
defining a precomputation formula based on the elementary symmetric polynomial;
generating ciphertext by encrypting the precomputation formula; and
transmitting the ciphertext to a second device.
10 . The method of claim 9 , further comprising:
receiving, from the second device, a result of an intersection operation of the ciphertext and a second data set of the second device; and
decrypting the intersection operation result.
11 . The method of claim 10 , wherein a number of the elements of the first data set is less than a number of the elements of the second data set.
12 . An apparatus comprising:
one or more processors configured to:
receive, from a first device, ciphertext generated by encrypting a precomputation formula defined based on an elementary symmetric polynomial corresponding to elements of a first data set of the first device;
perform, based on a match function defined for elements of a second data set of a second device, an intersection operation between the ciphertext and the elements of the second data set; and
transmit a result of the intersection operation to the first device.
13 . The apparatus of claim 12 , wherein, for the performing of the intersection operation, the one or more processors are further configured to perform a linear combination operation of the ciphertext and a power of the elements of the second data set.
14 . The apparatus of claim 13 , wherein, for the performing of the intersection operation, the one or more processors are further configured to perform an additional operation to obtain elements of the intersection based on a result of the linear combination operation and the elements of the second data set.
15 . The apparatus of claim 14 , wherein, for the transmitting of the intersection operation result, the one or more processors are further configured to transmit the linear combination operation result and a result of the additional operation to the first device.
16 . The apparatus of claim 12 , wherein a number of the elements of the first data set is less than a number of the elements of the second data set.
17 . The apparatus of claim 12 , wherein an accumulated number of homomorphic multiplication operations in the intersection operation is “1”.
18 . The apparatus of claim 12 , wherein the ciphertext is ciphertext based on ring learning with errors (RLWE).
19 . A device comprising:
one or more processors configured to:
obtain an elementary symmetric polynomial corresponding to elements of a first data set of a first device;
define a precomputation formula based on the elementary symmetric polynomial;
generate ciphertext by encrypting the precomputation formula; and
transmit the ciphertext to a second device.
20 . The encryption device of claim 19 , wherein the one or more processors are further configured to:
receive, from the second device, a result of an intersection operation of the ciphertext and a second data set of the second device; and
decrypt the intersection operation result.