Patent ID: 12231563

DETAILED DESCRIPTION

In the following detailed description, particular embodiments of the present disclosure are described herein with reference to the accompanying drawings, which form a part of the description. In this description, as well as in the drawings, like-referenced numbers represent elements that may perform the same, similar, or equivalent functions, unless context dictates otherwise. Furthermore, unless otherwise noted, the description of each successive drawing may reference features from one or more of the previous drawings to provide clearer context and a more substantive explanation of the current example embodiment. Still, the example embodiments described in the detailed description, drawings, and claims are not intended to be limiting. Other embodiments may be utilized, and other changes may be made, without departing from the spirit or scope of the subject matter presented herein. It will be readily understood that the aspects of the present disclosure, as generally described herein and illustrated in the drawings, may be arranged, substituted, combined, separated, and designed in a wide variety of different configurations, all of which are explicitly contemplated herein.

It is to be understood that the disclosed embodiments are merely examples of the disclosure, which may be embodied in various forms. Well-known functions or constructions are not described in detail to avoid obscuring the present disclosure in unnecessary detail. Therefore, specific structural and functional details disclosed herein are not to be interpreted as limiting, but merely as a basis for the claims and as a representative basis for teaching one skilled in the art to variously employ the present disclosure in virtually any appropriately detailed structure.

Additionally, the present disclosure may be described herein in terms of functional block components and various processing steps. It should be appreciated that such functional blocks may be realized by any number of hardware and/or software components configured to perform the specified functions.

The scope of the disclosure should be determined by the appended claims and their legal equivalents, rather than by the examples given herein. For example, the steps recited in any method claims may be executed in any order and are not limited to the order presented in the claims. Moreover, no element is essential to the practice of the disclosure unless specifically described herein as “critical” or “essential”.

As referenced herein, a “data set” or “dataset” is a term of art and may refer to an organized collection of data stored and accessed electronically. In an example embodiment, a dataset may refer to a database, a data table, a portion of a database or data table, etc. It is to be understood that a dataset may correspond to one or more database tables, of which every column of a database table represents a particular variable or field, and each row of the database table corresponds to a given record of the dataset. The dataset may list values for each of the variables, and/or for each record of the dataset. It is also to be understood that a dataset may also or alternatively refer to a set of related data and the way the related data is organized. In an example embodiment, each record of a dataset may include field(s) or element(s) such as one or more predefined or predetermined identifications (e.g., membership identifications, user identifications, etc., such as user's name, e-mail address, phone numbers, etc.), and/or one or more attributes or features or values associated with the one or more identifications. It is to be understood that any user's identification(s) and/or user's data described in this document are allowed, permitted, and/or otherwise authorized by the user for use in the embodiments described herein and in their proper legal equivalents as understood by those of skill in the art.

As referenced herein, “inner join” or “inner-join” is a term of art and may refer to an operation or function that includes combining records from datasets, particularly when there are matching values in a field common to the datasets. For example, an inner join may be performed with a “Departments” dataset and an “Employees” dataset to determine all the employees in each department. It is to be understood that in the resulting dataset (i.e., the “intersection”) of the inner join operation, the inner join may contain the information from both datasets that is related to each other. An outer join, on the other hand, may also contain information that is not related to the other dataset in its resulting dataset. A private inner join may refer to an inner join operation of datasets of two or more parties that does not reveal the data in the intersection of datasets of the two or more parties.

As referenced herein, “hashing” may refer to an operation or function that transforms or converts an input (a key such as a numerical value, a string of characters, etc.) into an output (e.g., another numerical value, another string of characters, etc.). It is to be understood that hashing is a term of art and may be used in cyber security application(s) to access data in a small and nearly constant time per retrieval.

As referenced herein, “federated”, “distributed”, or “collaborative” learning or training is a term of art and may refer to a machine learning techniques that train an algorithm across multiple decentralized edge devices or servers that store local data samples, without exchanging the data samples among the devices or servers. It is to be understood that “federated” learning or training may stand in contrast to traditional centralized machine learning techniques by which all the local datasets are uploaded to one server, as well as to more classical decentralized approaches which often assume that local data samples are identically distributed. Federated learning or training may enable multiple actors to build a common, robust machine learning model without sharing data among the actors, thus addressing critical issues such as data privacy, data security, data access rights and access to heterogenous data.

As referenced herein, “MPC” or “multi-party computation” is a term of art and may refer to a field of cryptography with the goal of creating schemes for parties to jointly compute a function over the joint input of the parties while keeping respective input private. It is to be understood that, unlike traditional cryptographic tasks where cryptography may assure security and integrity of communication or storage when an adversary is outside the system of participants (e.g., an eavesdropper on the sender and/or the receiver), the cryptography in MPC may protect participants' privacy relative to each other.

As referenced herein, “ECC” or “elliptic-curve cryptography” is a term of art and may refer to a public-key cryptography based on the algebraic structure of elliptic curves over finite fields. It is to be understood that the ECC may allow smaller keys compared to non-EC cryptography to provide equivalent security. It is also to be understood that “EC” or “elliptic curve” may be applicable for key agreement, digital signatures, pseudo-random generators, and/or other tasks. Elliptic curves may be indirectly used for encryption by combining a key agreement between/among the parties with a symmetric encryption scheme. Elliptic curves may also be used in integer factorization algorithms based on elliptic curves that have applications in cryptography.

As referenced herein, “decisional Diffie-Hellman assumption” or “DDH assumption” is a term of art and may refer to a computational complexity assumption about a certain problem involving discrete logarithms in cyclic groups. It is to be understood that the DDH assumption may be used as a basis to prove the security of many cryptographic protocols.

As referenced herein, “elliptic-curve Diffie-Hellman” or “ECDH” is a term of art and may refer to a key agreement protocol or a corresponding algorithm that allows two or more parties, each having an elliptic-curve public-private key pair, to establish a shared secret over an unsecured channel. It is to be understood that the shared secret may be directly used as a key or to derive another key. It is also to be understood that the key, or the derived key, may then be used to encrypt or encode subsequent communications using a symmetric-key cipher. It is further to be understood that ECDH may refer to a variant of the Diffie-Hellman protocol using elliptic-curve cryptography.

As referenced herein, “homomorphic” encryption is a term of art and may refer to a form of encryption that permits users to perform computations on encrypted data without first decrypting it. It is to be understood that the resulting computations of homomorphic encryption are left in an encrypted form which, when decrypted, result in an identical output to that produced had the operations been performed on the unencrypted data. It is also to be understood that the homomorphic encryption can be used for privacy-preserving outsourced storage and computation, which may allow data to be encrypted and out-sourced to commercial cloud environments for processing, all while encrypted. It is further to be understood that an additively homomorphic encryption or cryptosystem may refer to a form of encryption or cryptosystem that, given only the public key and the encryption of message m1 and message m2, one can compute the encryption of m1+m2. For example, the Paillier cryptosystem, which is a probabilistic asymmetric algorithm for public key cryptography, is an additively homomorphic cryptosystem.

As referenced herein, “secret sharing” or “secret splitting” is a term of art and may refer to cryptographic actions or algorithms for generating a secret, breaking the secret into multiple shares, and distributing the shares among multiple parties, so that only when the parties bring together their respective shares can the secret be reconstructed. It is to be understood that secret sharing may refer to actions or algorithms for distributing a secret among a group, in such a way that no individual holds any intelligible information about the secret, but when a sufficient number of individuals combine their “shares”, the secret may be reconstructed. It is also to be understood that whereas insecure secret sharing may allow an attacker to gain more information with each share, secure secret sharing may be “all or nothing”, where “all” may mean the necessary number of shares.

As referenced herein, “shuffle”, “shuffling”, “permute”, or “permuting” is a term of art and may refer to an action or algorithm for rearranging and/or randomly rearranging the order of the records (elements, rows, etc.) of e.g., an array, a dataset, a database, a data table, etc.

As referenced herein, a “semi-honest” adversary is a term of art and may refer to a party who may try corrupting parties but follow the protocol as specified. It is to be understood that the “semi-honest” party may be a corrupt party that runs a present protocol honestly but may try learning messages received from another party and/or parties for purposes e.g., beyond those intended by the protocol.

FIG.1is a schematic view of an example secure computation and communication system100, arranged in accordance with at least some embodiments described herein.

The system100may include terminal devices110,120,130, and140, a network160, and a server150. It is to be understood thatFIG.1only shows illustrative numbers of the terminal devices, the network, and the server. The embodiments described herein are not limited to the number of the terminal devices, the network, and/or the server described. That is, the number of terminal devices, networks, and/or servers described herein are provided for descriptive purposes only and are not intended to be limiting.

In accordance with at least some example embodiments, the terminal devices110,120,130, and140may be various electronic devices. The various electronic devices may include but not be limited to a mobile device such as a smartphone, a tablet computer, an e-book reader, a laptop computer, a desktop computer, and/or any other suitable electronic devices.

In accordance with at least some example embodiments, the network160may be a medium used to provide a communications link between the terminal devices110,120,130,140and the server150. The network160may be the Internet, a local area network (LAN), a wide area network (WAN), a local interconnect network (LIN), a cloud, etc. The network160may be implemented by various types of connections, such as a wired communications link, a wireless communications link, an optical fiber cable, etc.

In accordance with at least some example embodiments, the server150may be a server for providing various services to users using one or more of the terminal devices110,120,130, and140. The server150may be implemented by a distributed server cluster including multiple servers or may be implemented by a single server.

A user may use one or more of the terminal devices110,120,130, and140to interact with the server150via the network160. Various applications or localized interfaces thereof, such as social media applications, online shopping services, or the like, may be installed on the terminal devices110,120,130, and140.

It is to be understood that software applications or services according to the embodiments described herein and/or according to the services provided by the service providers may be performed by the server150and/or the terminal devices110,120,130, and140(which may be referred to herein as user devices). Accordingly, the apparatus for the software applications and/or services may be arranged in the server150and/or in the terminal devices110,120,130, and140.

It is also to be understood that when a service is not performed remotely, the system100may not include the network160, but include only the terminal device110,120,130, and140and/or the server150.

It is further to be understood that the terminal device110,120,130, and140and/or the server150may each include one or more processors, a memory, and a storage device storing one or more programs. The terminal device110,120,130, and140and/or the server150may also each include an Ethernet connector, a wireless fidelity receptor, etc. The one or more programs, when being executed by the one or more processors, may cause the one or more processors to perform the method(s) described in any embodiments described herein. Also, it is to be understood that a computer readable non-volatile medium may be provided according to the embodiments described herein. The computer readable medium stores computer programs. The computer programs are used to, when being executed by a processor, perform the method(s) described in any embodiments described herein.

FIG.2is a flow chart illustrating an example inner join processing flow200for private and secure computations and communication, in accordance with at least some embodiments described herein.FIG.5Ashows a first portion500of a schematic diagram illustrating an example of the processing flow200ofFIG.2, in accordance with at least some embodiments described herein.FIG.5Bshows a second portion501of a schematic diagram illustrating an example of the processing flow200ofFIG.2, in accordance with at least some embodiments described herein.

It is to be understood that the processing flow200disclosed herein can be conducted by one or more processors (e.g., the processor of one or more of the terminal device110,120,130, and140ofFIG.1, the processor of the server150ofFIG.1, the central processor unit605ofFIG.6, and/or any other suitable processor), unless otherwise specified.

It is also to be understood that the processing flow200can include one or more operations, actions, or functions as illustrated by one or more of blocks210,220,230, and240. These various operations, functions, or actions may, for example, correspond to software, program code, or program instructions executable by a processor that causes the functions to be performed. Although illustrated as discrete blocks, obvious modifications may be made, e.g., two or more of the blocks may be re-ordered; further blocks may be added; and various blocks may be divided into additional blocks, combined into fewer blocks, or eliminated, depending on the desired implementation. It is to be understood that before the processing flow200, operations including initializations or the like may be performed. For example, system parameters and/or application parameters may be initialized. Processing flow200may begin at block210.

At block210(Shuffle and transform dataset), the processor may provide a dataset (e.g.,505A ofFIG.5A) for Party A, and/or provide a dataset (e.g.,505B ofFIG.5A) for Party B. In an example embodiment, the size of the dataset505A or505B may include tens or hundreds of thousands elements (or records, rows, etc.). It is to be understood that a size of a dataset may refer to the number of elements (or records, rows, etc.) of the dataset. It is to be understood that the size of the dataset505A may be significantly larger than the size of the dataset505B.

In an example embodiment, the dataset505A includes multiple records (rows), each record including a member or membership or user identification (ID) and a time (T1) indicating e.g., the time (e.g., the starting time or timestamp) when the user clicks on e.g., a link or the like on Party A's platform. The dataset505B includes multiple records (rows), each record including a member or membership or user identification (ID), a time (T2) indicating e.g., the time (e.g., the starting time or timestamp) when the user goes to Party B's website, and a value (Value) indicating the value of the user for Party B. In an example embodiment, the time (or timestamp) is listed in units of “minutes”. It is to be understood that the format, content, and/or arrangement of the dataset505A and/or505B are for descriptive purposes only and are not intended to be limiting. For example, each dataset505A or505B may have one or more IDs (columns) and/or one or more features or attributes (columns) associated with the ID or IDs.

In an example embodiment, Party A and/or Party B may want to find out e.g., (1) how many users who clicked on e.g., a link or the like on Party A's platform and went to Party B's website and made valuable interaction, (2) how many users who clicked on e.g., a link or the like on Party A's platform and went to Party B's website within a certain period of time (e.g., within 70 minutes) after the user clicked on e.g., a link or the like on Party A's platform, and made valuable interaction, and/or (3) the total value of all users who clicked on e.g., a link or the like on Party A's platform and went to Party B's website within a certain period of time (e.g., within 70 minutes) after the users clicked on e.g., a link or the like on Party A's platform and made valuable interaction.

It is to be understood that Party A and/or Party B may not want to reveal to the other party the data in the dataset505A and/or the dataset505B, and/or in the intersection of the dataset505A and the dataset505B.

At block210, the processor of the respective device may also shuffle (e.g., randomly permute, etc.) the dataset505A to obtain or generate the dataset510A for Party A, and/or shuffle the dataset505B to obtain or generate the dataset510B for Party B.

The processor may also transform the ID (column) of the dataset510A using a transforming scheme for Party A. It is to be understood that the function or operation to “transform” or of “transforming” a dataset or a portion thereof, e.g., one or more columns (or rows) of a dataset such as one or more identification fields/columns (or records/rows), etc., may refer to processing (e.g., encrypting, decrypting, encoding, decoding, manipulating, compressing, decompressing, converting, etc.) the dataset or a portion thereof. It is also to be understood that the “transforming scheme” may refer to an algorithm, protocol, or function of performing the processing (e.g., encrypting, decrypting, encoding, decoding, manipulating, compressing, decompressing, converting, etc.) of the dataset or a portion thereof. In an example embodiment, the processor may encrypt (or decrypt, encode, decode, manipulate, compress, decompress, convert, etc.) the ID of the dataset510A using e.g., a key of Party A based on an ECDH algorithm or protocol (represented by the function D0(⋅)).

The processor may also transform the ID of the dataset510B using a transforming scheme for Party B. In an example embodiment, the processor may encrypt (or decrypt, encode, decode, manipulate, compress, decompress, convert, etc.) the ID of the dataset510B using e.g., a key of Party B based on the ECDH algorithm or protocol (represented by the function D1(⋅)).

The processor may further transform T1 (column) of the dataset510A using a transforming scheme for Party A. In an example embodiment, the processor may encrypt (or decrypt, encode, decode, manipulate, compress, decompress, convert, etc.) T1 of the dataset510A using e.g., a key of Party A based on an additively homomorphic encryption algorithm or protocol (represented by the function H0(⋅)).

The processor may also transform T2 (column) and Value (column) of the dataset510B using a transforming scheme for Party B. In an example embodiment, the processor may encrypt (or decrypt, encode, decode, manipulate, compress, decompress, convert, etc.) the T2 and Value of the dataset510B using e.g., a key of Party B based on the additively homomorphic encryption algorithm or protocol (represented by the function H1(⋅)).

It is to be understood that at block210, for Party A and/or Party B, a sequence of the transforming of the dataset and the shuffling of the dataset may be switched or changed, without impacting the purpose of the resultant dataset. For example, the processor may transform the dataset505A to obtain or generate the dataset510A for Party A, and then shuffle the dataset510A. The processor may also transform the dataset505B to obtain or generate the dataset510B for Party B, and then shuffle the dataset510B. Processing may proceed from block210to block220.

At block220(Exchange, shuffle, and transform dataset), the processor of the respective device may exchange the dataset510A with the dataset510B between Party A and Party B. For Party A, the processor may dispatch or send the dataset510A to Party B, and receive or obtain the dataset510B from Party B as dataset515A (SeeFIG.5A). For Party B, the processor may dispatch or send the dataset510B to Party A, and receive or obtain the dataset510A from Party A as dataset515B (SeeFIG.5A). It is to be understood that since the dataset510A and the dataset510B have been transformed (e.g., encoded, etc.), the corresponding receiving party may not know the data in the received dataset.

The processor may also shuffle the dataset515A for Party A to obtain or generate the dataset520A, and/or shuffle the dataset515B for Party B to obtain or generate the dataset520B.

The processor may further transform the ID of the dataset520A using a transforming scheme for Party A. In an example embodiment, the processor may encrypt (or decrypt, encode, decode, manipulate, compress, decompress, convert, etc.) the ID of the dataset520A using a key of Party A based on the ECDH algorithm or protocol (represented by the function D0(⋅)). The processor may further transform the ID of the dataset520B using a transforming scheme for Party B. In an example embodiment, the processor may encrypt (or decrypt, encode, decode, manipulate, compress, decompress, convert, etc.) the ID of the dataset520B using a key of Party B based on the ECDH algorithm or protocol (represented by the function D1(⋅)). It is to be understood that the results of the functions D1(D2(p)) and D2(D1(p)) may be the same for a same parameter “p”.

It is to be understood that at block220, for Party A and/or Party B, a sequence of the transforming of the ID of the dataset and the shuffling of the dataset may be switched or changed, without impacting the purpose of the resultant dataset. For example, the processor may transform the dataset515A to obtain or generate the dataset520A for Party A, and then shuffle the dataset520A. The processor may also transform the dataset515B to obtain or generate the dataset520B for Party B, and then shuffle the dataset520B. Processing may proceed from block220to block230.

At block230(Exchange and match), the processor of the respective device may extract the ID of the dataset520A to obtain or generate the dataset525A for Party A, and/or extract the ID of the dataset520B to obtain or generate the dataset525B for Party B. The processor of the respective device may also exchange the dataset525A with the dataset525B between Party A and Party B. For Party A, the processor may dispatch or send the dataset525A to Party B, and receive or obtain the dataset525B from Party B. For Party B, the processor may dispatch or send the dataset525B to Party A, and receive or obtain the dataset525A from Party A.

The processor may also perform search for a match (or an inner join operation, etc.) between the dataset520A and the dataset525B to obtain or generate an intersection (dataset530A ofFIG.5B) for Party A. It is to be understood that the above operation incudes for each identification in the dataset525B that matches the identification in the dataset520A, adding or appending the record (or row) of the dataset520A that contains the matched identification to the dataset530A.

The processor may also perform search for a match (or an inner join operation, etc.) between the dataset520B and the dataset525A to obtain or generate an intersection (dataset530B ofFIG.5B) for Party B. It is to be understood that the above operation incudes for each identification in the dataset525A that matches the identification in the dataset520B, adding or appending the record (or row) of the dataset520B that contains the matched identification to the dataset530B.

It is to be understood that for Party A, data in the intersection530A are also transformed (e.g., encoded, etc.) by Party B (via D1(⋅) and H1(⋅)), and thus Party A may not know the real data in the intersection530A. For Party B, data in the intersection530B are also transformed (e.g., encoded, etc.) by Party A (via D0(⋅) and H0(⋅)), and thus Party B may not know the real data in the intersection530B. That is, the matching or inner join operation conducted, as described above, is a private matching or inner join operation. The processor performs a private identity matching without revealing the intersection of datasets of the two parties. Processing may proceed from block230to block240.

At block240(Generate shares), for each attribute or feature (e.g., those elements that are not identifications of the ID field/column) in the dataset530A for Party A, the processor may generate a corresponding mask (see description ofFIG.4for details), and may mask (see description ofFIG.4for details) each attribute or feature in the dataset530A with its corresponding mask using a masking scheme, to obtain or generate a dataset535A. In an example embodiment, each mask is a random number or random plaintext. In an example embodiment, the masking scheme is a homomorphic operation or computation (e.g., addition, subtraction, etc.) in an additively homomorphic encryption algorithm or protocol. For example, as shown inFIG.5B, the processor may mask the T2 data H1(50) in the dataset530A with a mask “share0_of_50”, and homomorphically compute the T2 data H1(50−share0_of_50) in the dataset535A by subtracting the mask “share0_of_50” from H1(50), where the mask “share0_of_50” is generated for and corresponds to the T2 time “50”.

The processor may also extract the ID column from the dataset530A, along with all the masks generated for all the attributes or features (i.e., those elements that are not IDs), to obtain the dataset540A (seeFIG.5C) for Party A.

Similarly, for each attribute or feature (e.g., those elements that are not identifications of the ID field/column) in the dataset530B for Party B, the processor may generate a corresponding mask, and may mask each attribute or feature in the dataset530B with its corresponding mask using a masking scheme, to obtain or generate a dataset535B. In an example embodiment, each mask is a random number or random plaintext. In an example embodiment, the masking scheme is a homomorphic operation or computation (e.g., addition, subtraction, etc.) in an additively homomorphic encryption algorithm or protocol. For example, as shown inFIG.5B, the processor may mask the T1 data H0(30) in the dataset530B with a mask “share1_of_30”, and homomorphically compute the T1 data H0(30−share1_of_30) in the dataset535B by subtracting the mask “share1_of_30” from H0(30), where the mask “share1_of_30” is generated for and corresponds to the T1 time “30”.

The processor may also extract the ID column from the dataset530B, along with all the masks generated for all the attributes or features (i.e., those elements that are not IDs), to obtain the dataset540B (seeFIG.5C) for Party B.

FIG.3is a flow chart illustrating an example secret sharing processing flow300for private and secure computation and communication, in accordance with at least some embodiments described herein.FIG.5Cshows a third portion502of a schematic diagram illustrating an example of the processing flow300ofFIG.3, in accordance with at least some embodiments described herein.FIG.5Dshows a fourth portion503of a schematic diagram illustrating an example of the processing flow300ofFIG.3, in accordance with at least some embodiments described herein.

It is to be understood that the processing flow300disclosed herein can be conducted by one or more processors (e.g., the processor of one or more of the terminal device110,120,130, and140ofFIG.1, the processor of the server150ofFIG.1, the central processor unit605ofFIG.6, and/or any other suitable processor), unless otherwise specified.

It is also to be understood that the processing flow300can include one or more operations, actions, or functions as illustrated by one or more of blocks310,320,330, and340. These various operations, functions, or actions may, for example, correspond to software, program code, or program instructions executable by a processor that causes the functions to be performed. Although illustrated as discrete blocks, obvious modifications may be made, e.g., two or more of the blocks may be re-ordered; further blocks may be added; and various blocks may be divided into additional blocks, combined into fewer blocks, or eliminated, depending on the desired implementation. It is to be understood that before the processing flow300, operations including initializations or the like may be performed. For example, system parameters and/or application parameters may be initialized from the results at block240ofFIG.2. Processing flow300may begin at block310.

At block310(Exchange shares), the processor of the respective device may exchange the dataset535A with the dataset535B between Party A and Party B. For Party A, the processor may dispatch or send the dataset535A to Party B, and receive or obtain the dataset535B from Party B as dataset545A (SeeFIG.5C). For Party B, the processor may dispatch or send the dataset535B to Party A, and receive or obtain the dataset535A from Party A as dataset545B (SeeFIG.5C). Processing may proceed from block310to block320.

At block320(Construct shares), the processor may transform the attributes or features (e.g., T1—those elements that are not IDs) of the dataset545A using a transfer scheme for Party A, and construct the secret shares (dataset550A) for Party A by combining (e.g., performing a union operation, etc.) the dataset540A and the transformed attributes or features (e.g., T1—those elements that are not IDs) of the dataset545A. In an example embodiment, the processor may decrypt (or encrypt, encode, decode, manipulate, compress, decompress, convert, etc.) the attributes or features (e.g., T1—those elements that are not IDs) of the dataset545A using a key of Party A based on the additively homomorphic encryption algorithm or protocol.

The processor may transform the attributes or features (e.g., T2 and Value—those elements that are not IDs) of the dataset545B using a transfer scheme for Party B, and construct the secret shares (dataset550B) for Party B by combining (e.g., performing a union operation, etc.) the dataset540B and the transformed attributes or features (e.g., T2 and Value—those elements that are not IDs) of the dataset545B. In an example embodiment, the processor may decrypt (or encrypt, encode, decode, manipulate, compress, decompress, convert, etc.) the attributes or features (e.g., T2 and Value—those elements that are not IDs) of the dataset545B using a key of Party B based on the additively homomorphic encryption algorithm or protocol. Processing may proceed from block320to block330.

At block330(Perform secure MPC), the processor of the respective device may perform secure multi-party computation (see descriptions below) on the secret shares of Party A and/or perform secure multi-party computation (see descriptions below) on the secret shares of Party B.

In an example embodiment, the processor may subtract T1 from T2 for the dataset550A to obtain or generate the dataset555A for Party A, and/or subtract T1 from T2 for the dataset550B to obtain or generate the dataset555B for Party B.

In an example embodiment, the processor may determine whether T2 is greater than 0 and less than a predetermined value for the dataset555A to obtain or generate the dataset560A for Party A. If T2 is greater than 0 and less than a predetermined value, the processor may set the T2 value in the dataset560A to the secret share of 1 (to represent “True”), which is a random number for Party A. If T2 is not greater than 0 or not less than the predetermined value, the processor may set the T2 value in the dataset560A to the secret share of 0 (to represent “False”), which is a random number for Party A.

In an example embodiment, the processor may determine whether T2 is greater than 0 and less than a predetermined value for the dataset555B to obtain or generate the dataset560B for Party B. If T2 is greater than 0 and less than a predetermined value, the processor may set the T2 value in the dataset560B to the secret share of 1 (to represent “True”), which is a random number for Party B. If T2 is not greater than 0 or not less than the predetermined value, the processor may set the T2 value in the dataset560B to the secret share of 0 (to represent “False”), which is a random number for Party B.

In an example embodiment, the processor may also multiply the corresponding T2 and Value of the dataset560A, and store or save the results in the Value field of the dataset565A, to generate the dataset565A for Party A. The processor may also multiply the corresponding T2 and Value of the dataset560B, and store or save the results in the Value field of the dataset565B, to generate the dataset565B for Party B. It is to be understood that the secret share of 1 multiplies any value V may result in the same value V. The secret share of 0 multiplies any value V may result in the secret share of 0.

In an example embodiment, the processor may further sum the Value of the dataset565A, and store or save the results in the Value field of the dataset570A, to generate the dataset570A for Party A. The processor may further sum the Value of the dataset565B, and store or save the results in the Value field of the dataset570B, to generate the dataset570B for Party B. It is to be understood that the secret share of 0 adds any value V may result in the same value V.

It is to be understood that Party A now has the dataset570A (a secret share) indicating the total value of all users who clicked on e.g., a link or the like on Party A's platform and went to Party B's website, within a certain period of time (e.g., within 70 minutes) after the users clicked on e.g., a link or the like on Party A's platform and made valuable interaction. It is also to be understood that Party A does not know the data in the dataset570A because the secret share is a random value.

It is to be understood that Party B now has the dataset570B (a secret share) indicating the total value of all users who clicked on e.g., a link or the like on Party A's platform and went to Party B's website, within a certain period of time (e.g., within 70 minutes) after the users clicked on e.g., a link or the like on Party A's platform and made valuable interaction. It is also to be understood that Party B does not know the data in the dataset570B because the secret share is a random value. Processing may proceed from block330to block340.

At block340(Construct results), the processor of the respective device may exchange the dataset570A with the dataset570B between Party A and Party B. For Party A, the processor may dispatch or send the dataset570A to Party B, and receive or obtain the dataset570B from Party B. The processor may also construct the results (“121”) by e.g., adding data in the dataset570A and data in the received dataset570B. That is, the total value of all users who clicked on e.g., a link or the like on Party A's platform and went to Party B's website, within a certain period of time (e.g., within 70 minutes) after the users clicked on e.g., a link or the like on Party A's platform and made valuable interaction, is “121”.

For Party B, the processor may dispatch or send the dataset570B to Party A, and receive or obtain the dataset570A from Party A. The processor may also construct the results (“121”) by e.g., adding data in the dataset570B and data in the received dataset570A. That is, the total value of all users who clicked on e.g., a link or the like on Party A's platform and went to Party B's website, within a certain period of time (e.g., within 70 minutes) after the users clicked on e.g., a link or the like on Party A's platform and made valuable interaction, is “121”, which is the same as the result determined by Party A.

It is to be understood that other results may also be constructed or determined by combining the secret shares (550A and550B), the secret shares (555A and555B), the secret shares (560A and560B), the secret shares (565A and565B), etc. For example, the value in T2 column of datasets555A and/or555B may be constructed or determined by combining T2 of the secret shares555A and555B, and the constructed or determined results may be used to determine the corresponding T2 values in the datasets560A and/or560B. It is also to be understood that other results may further be constructed or determined by conducting other MPC computations on the secret shares to get secret shares of the Party A and Party B, and by combining the secret shares of both Party A and Party B.

FIG.4is a schematic view of an example packing optimization scheme400for private and secure computation and communication, in accordance with at least some embodiments described herein.

As discussed above, at block240(Generate shares) ofFIG.2, for each attribute or feature (those elements that are not IDs) in the dataset530A or540B (seeFIG.5B), the processor may generate a corresponding mask, and may mask each attribute or feature in the dataset530A or530B with its corresponding mask using a masking scheme, to obtain or generate a dataset535A or535B. In an example embodiment, each mask is a random number or random plaintext. The processor may also extract the ID column from the dataset530A or530B, along with all the masks generated for all the attributes or features, to obtain the dataset540A or540B.

In an example embodiment without the packing optimization, given an attribute or feature A0 in a record, the processor may generate its corresponding mask R0. The mask R0 may be a random number or random plaintext. Masking A0 with R0 may refer to adding (or subtracting, etc.) R0 to (or from) A0 such that the result may be a random number or random plaintext (since a value adding or subtracting a random number may result in a random number). In an example embodiment, for T2 value (A0=“50”) inFIGS.5B and5C, its corresponding mask (R0) is represented as share0_of_50. For a ciphertext having a size of 6144 bits with a plaintext space having a size of 3072 bits, without the packing optimization, each value A0 (e.g., having a size of 64 bits, etc.) may occupy a space of 3072 bits during the process.

InFIG.4, the record410(e.g., in the dataset530A or530B ofFIG.5B) includes one or more IDs, and one or more attributes or features (i.e., those elements that are not IDs) A0, A1 . . . AN. In an example embodiment, a value of each attribute or feature has a size of L. In an example embodiment, L is 64 bits (i.e., the value ranges from 0 to 264). For each attribute or feature A0, A1 . . . . AN, the processor may generate a corresponding mask R0, R1 . . . . RN. Each mask R0, R1 . . . . RN may be a random number or random plaintext (e.g., that is greater than 2L) and has a size of L+D bits, where L is the size of A0, A1 . . . . AN, and D is a statistical security parameter (e.g., 40 bits, etc.).

Each attribute or feature A0, A1 . . . . AN may be expanded from L bits to 1+L+D bits (e.g., by adding leading 0s) and be stored in slot420_1,420_2, . . .420_N, respectively. Each slot has a size of 1+L+D bits, with the additional 1 bit (compared with the size of the mask R0, R1 . . . RN) to accommodate overflow when adding or subtracting the corresponding mask R0, R1 . . . RN to or from A0, A1 . . . . AN, respectively.

In an example embodiment, the processor may pack (or combine, concatenate, etc.) two or more attributes or features A0, A1 . . . . AN in the corresponding two or more slots420_1,420_2, . . .420_N, as long as the total size is less than the size of the plaintext space. For example, packing two attributes or features A0 and A1 in the corresponding slots420_1and420_2may result in a packed attribute or packed feature having a size of 1+L+D+1+L+D bits, where the left/first 1+L+D bits is for A0 in slot420_1and the right/second 1+L+D bits is for A1 in slot420_2.

In an example embodiment, the processor may also expand each mask R0, R1 . . . . RN from L+D bits to 1+L+D bits (e.g., by adding leading 0s) and pack two or more masks R0, R1 . . . RN, as long as the total size is less than the size of the plaintext space. For example, packing two masks R0 and R1 may result in a packed mask having a size of 1+L+D+1+L+D bits, where the left/first 1+L+D bits is for mask R0 and the right/second 1+L+D bits is for mask R1.

With the packing optimization, the result from the packing of the two or more masks R0, R1 . . . . RN may be used as the packed mask for the packed attributes or packed features A0, A1 . . . AN (i.e., the result from the packing of the two or more attributes or features A0, A1 . . . . AN). The processor may mask each packed attribute or packed feature with its corresponding packed mask using a masking scheme (e.g., adding, subtracting, etc.).

It is to be understood that the packing optimization described above may help packing together multiple messages (e.g., multiple attributes or features associated with each user or member identifier) into a single ciphertext and reducing the number of transforms such as encryptions, decryptions, etc. The packing optimization described above may also help reducing the communication complexity.

FIG.6is a schematic structural diagram of an example computer system600applicable to implementing an electronic device (for example, the server or one of the terminal devices shown inFIG.1), arranged in accordance with at least some embodiments described herein. It is to be understood that the computer system shown inFIG.6is provided for illustration only instead of limiting the functions and applications of the embodiments described herein.

As depicted, the computer system600may include a central processing unit (CPU)605. The CPU605may perform various operations and processing based on programs stored in a read-only memory (ROM)610or programs loaded from a storage device640to a random-access memory (RAM)615. The RAM615may also store various data and programs required for operations of the system600. The CPU605, the ROM610, and the RAM615may be connected to each other via a bus620. An input/output (I/O) interface625may also be connected to the bus620.

The components connected to the I/O interface625may further include an input device630including a keyboard, a mouse, a digital pen, a drawing pad, or the like; an output device635including a display such as a liquid crystal display (LCD), a speaker, or the like; a storage device640including a hard disk or the like; and a communication device645including a network interface card such as a LAN card, a modem, or the like. The communication device645may perform communication processing via a network such as the Internet, a WAN, a LAN, a LIN, a cloud, etc. In an embodiment, a driver650may also be connected to the I/O interface625. A removable medium655such as a magnetic disk, an optical disk, a magneto-optical disk, a semiconductor memory, or the like may be mounted on the driver650as desired, such that a computer program read from the removable medium655may be installed in the storage device640.

It is to be understood that the processes described with reference to the flowcharts ofFIGS.2and3and/or the processes described in other figures may be implemented as computer software programs or in hardware. The computer program product may include a computer program stored in a computer readable non-volatile medium. The computer program includes program codes for performing the method shown in the flowcharts and/or GUIs. In this embodiment, the computer program may be downloaded and installed from the network via the communication device645, and/or may be installed from the removable medium655. The computer program, when being executed by the central processing unit (CPU)605, can implement the above functions specified in the method in the embodiments disclosed herein.

Compared with the existing algorithms, protocols, or systems, testing and/or analysis indicate that with the features in the embodiments disclosed herein, efficiency may be improved, the number of transforming actions or steps (e.g., homomorphic encryptions, decryptions, additions, etc.) may be reduced, and the communication complexity and the computational complexity may be reduced.

It is to be understood that the disclosed and other solutions, examples, embodiments, modules and the functional operations described in this document can be implemented in digital electronic circuitry, or in computer software, firmware, or hardware, including the structures disclosed in this document and their structural equivalents, or in combinations of one or more of them. The disclosed and other embodiments can be implemented as one or more computer program products, i.e., one or more modules of computer program instructions encoded on a computer readable medium for execution by, or to control the operation of, data processing apparatus. The computer readable medium can be a machine-readable storage device, a machine-readable storage substrate, a memory device, a composition of matter effecting a machine-readable propagated signal, or a combination of one or more them. The term “data processing apparatus” encompasses all apparatus, devices, and machines for processing data, including by way of example a programmable processor, a computer, or multiple processors or computers. The apparatus can include, in addition to hardware, code that creates an execution environment for the computer program in question, e.g., code that constitutes processor firmware, a protocol stack, a database management system, an operating system, or a combination of one or more of them.

A computer program (also known as a program, software, software application, script, or code) can be written in any form of programming language, including compiled or interpreted languages, and it can be deployed in any form, including as a stand-alone program or as a module, component, subroutine, or other unit suitable for use in a computing environment. A computer program does not necessarily correspond to a file in a file system. A program can be stored in a portion of a file that holds other programs or data (e.g., one or more scripts stored in a markup language document), in a single file dedicated to the program in question, or in multiple coordinated files (e.g., files that store one or more modules, sub programs, or portions of code). A computer program can be deployed to be executed on one computer or on multiple computers that are located at one site or distributed across multiple sites and interconnected by a communication network.

The processes and logic flows described in this document can be performed by one or more programmable processors executing one or more computer programs to perform functions by operating on input data and generating output. The processes and logic flows can also be performed by, and apparatus can also be implemented as, special purpose logic circuitry, e.g., a field programmable gate array, an application specific integrated circuit, or the like.

Processors suitable for the execution of a computer program include, by way of example, both general and special purpose microprocessors, and any one or more processors of any kind of digital computer. Generally, a processor will receive instructions and data from a read only memory or a random-access memory or both. The essential elements of a computer are a processor for performing instructions and one or more memory devices for storing instructions and data. Generally, a computer will also include, or be operatively coupled to receive data from or transfer data to, or both, one or more mass storage devices for storing data, e.g., magnetic, magneto optical disks, or optical disks. However, a computer need not have such devices. Computer readable media suitable for storing computer program instructions and data include all forms of non-volatile memory, media and memory devices, including by way of example semiconductor memory devices, e.g., erasable programmable read-only memory, electrically erasable programmable read-only memory, and flash memory devices; magnetic disks, e.g., internal hard disks or removable disks; magneto optical disks; and compact disc read-only memory and digital video disc read-only memory disks. The processor and the memory can be supplemented by, or incorporated in, special purpose logic circuitry.

It is to be understood that different features, variations and multiple different embodiments have been shown and described with various details. What has been described in this application at times in terms of specific embodiments is done for illustrative purposes only and without the intent to limit or suggest that what has been conceived is only one particular embodiment or specific embodiments. It is to be understood that this disclosure is not limited to any single specific embodiments or enumerated variations. Many modifications, variations and other embodiments will come to mind of those skilled in the art, and which are intended to be and are in fact covered by both this disclosure. It is indeed intended that the scope of this disclosure should be determined by a proper legal interpretation and construction of the disclosure, including equivalents, as understood by those of skill in the art relying upon the complete disclosure present at the time of filing.

Aspects:

It is appreciated that any one of aspects can be combined with each other.

Aspect 1. A method for secure computation and communication, the method comprising: transforming identifications of a first dataset using a first transforming scheme; transforming attributes of the first dataset using a second transforming scheme; dispatching the transformed first dataset; receiving a second dataset; transforming identifications of the received second dataset; dispatching the identifications of the transformed received second dataset; receiving a set of identifications; generating a first intersection of the received set of identifications and the transformed received second dataset; generating a first share based on the first intersection; receiving a second share; and constructing a first result based on the first share and the second share.

Aspect 2. The method of aspect 1, further comprising: before dispatching the transformed first dataset, shuffling the transformed first dataset; and before dispatching the identifications of the transformed second dataset, shuffling the transformed second dataset.

Aspect 3. The method of aspect 1 or aspect 2, further comprising: before constructing the first result, manipulating the first share.

Aspect 4. The method of any one of aspects 1-3, wherein the generating of the first share based on the first intersection includes: masking attributes of the first intersection using a masking scheme; dispatching the masked attributes of the first intersection; generating a first portion of the first share using the masking scheme; receiving a second portion of the first share; transforming the second portion of the first share using the second transforming scheme; and generating the first share based on the first portion of the first share and the second portion of the first share.

Aspect 5. The method of aspect 4, wherein a record of the first intersection includes an identification and two or more attribute fields, the method further comprising: expanding each of the two or more attribute fields to a predetermined size; concatenating the expanded two or more attribute fields; and masking the concatenated two or more attribute fields using the masking scheme.

Aspect 6. The method of aspect 5, wherein the masking of the concatenated two or more attribute fields includes adding random values to the expanded two or more attribute fields, respectively.

Aspect 7. The method of any one of aspects 1-6, further comprising: determining a random exponent for the first transforming scheme.

Aspect 8. The method of aspect 7, wherein the transforming of the identifications of the first dataset using the first transforming scheme includes: mapping the identifications of the first dataset to an elliptic curve, and applying exponentiation on the mapped identifications using the random exponent.

Aspect 9. The method of any one of aspects 1-8, further comprising: generating a public key for the second transforming scheme.

Aspect 10. The method of aspect 9, wherein the transforming of the attributes of the first dataset using the second transforming scheme includes: transforming the attributes of the first dataset using the public key.

Aspect 11. The method of any one of aspects 1-10, further comprising: transforming identifications of the second dataset using the first transforming scheme; transforming attributes of the second dataset using the second transforming scheme; dispatching the transformed second dataset; receiving the dispatched first dataset; transforming identifications of the received first dataset; dispatching the identifications of the transformed received first dataset; receiving the dispatched identifications of the transformed received second dataset; generating a second intersection of the received dispatched identifications and the transformed received first dataset; generating the second share based on the second intersection; receiving the first share; and constructing a second result based on the first share and the second share.

Aspect 12. The method of aspect 11, wherein the first result is the same as the second result.

Aspect 13. The method of aspect 11 or aspect 12, wherein identifications of the first intersection match identifications of the second intersection.

Aspect 14. The method of any one of aspects 11-13, further comprising: before dispatching the transformed second dataset, shuffling the transformed second dataset; and before dispatching the identifications of the transformed received first dataset, shuffling the transformed received first dataset.

Aspect 15. A secure computation and communication system, the system comprising: a memory to store a first dataset; a processor to: transform identifications of a first dataset using a first transforming scheme; transform attributes of the first dataset using a second transforming scheme; dispatch the transformed first dataset; receive a second dataset; transform identifications of the received second dataset; dispatch the identifications of the transformed received second dataset; receive a set of identifications; generate a first intersection of the received set of identifications and the transformed received second dataset; generate a first share based on the first intersection; receive a second share; and construct a first result based on the first share and the second share.

Aspect 16. The system of aspect 15, wherein the processor is to further: before dispatching the transformed first dataset, shuffle the transformed first dataset; and before dispatching the identifications of the transformed received second dataset, shuffle the transformed received second dataset.

Aspect 17. The system of aspect 16, wherein the processor is to further: before constructing the first result, manipulate the first share.

Aspect 18. A non-transitory computer-readable medium having computer-executable instructions stored thereon that, upon execution, cause one or more processors to perform operations comprising: transforming identifications of a first dataset; transforming attributes of the first dataset; dispatching the transformed first dataset; receiving a second dataset; transforming identifications of the received second dataset; dispatching the identifications of the transformed received second dataset; receiving a set of identifications; generating a first intersection of the received set of identifications and the transformed received second dataset; generating a first share based on the first intersection; receiving a second share; and constructing a first result based on the first share and the second share.

Aspect 19. The computer-readable medium of aspect 18, wherein the operations further comprise: before dispatching the transformed first dataset, shuffling the transformed first dataset; and before dispatching the identifications of the transformed received second dataset, shuffling the transformed received second dataset.

Aspect 20. The computer-readable medium of aspect 19, wherein the operations further comprise: before constructing the first result, manipulating the first share.

The terminology used in this specification is intended to describe particular embodiments and is not intended to be limiting. The terms “a,” “an,” and “the” include the plural forms as well, unless clearly indicated otherwise. The terms “comprises” and/or “comprising,” when used in this specification, specify the presence of the stated features, integers, steps, operations, elements, and/or components, but do not preclude the presence or addition of one or more other features, integers, steps, operations, elements, and/or components.

With regard to the preceding description, it is to be understood that changes may be made in detail, especially in matters of the construction materials employed and the shape, size, and arrangement of parts without departing from the scope of the present disclosure. This specification and the embodiments described are exemplary only, with the true scope and spirit of the disclosure being indicated by the claims that follow.