ABSTRACT
Abstract
The present disclosure involves systems, software, and computer implemented methods for a verifiable communication-efficient secret shuffle protocol for encrypted data based on homomorphic encryption. A service provider and multiple clients participate in a secret shuffle protocol of randomly shuffling encrypted client-specific secret input values. The protocol includes generation and exchange of random numbers, random permutations, different blinding values, and use of random secret-shares. A protocol step includes homomorphic operations to shuffle encrypted secret input values so that resulting encrypted secret input values are rerandomized and in a shuffled sequence that is unmapped to an order of receipt by the service provider of the encrypted secret input values.
Description
TECHNICAL FIELD
The present disclosure relates to computer-implemented methods, software, and systems for secret shuffle protocols using homomorphic encryption.
BACKGROUND
An organization may gather data related to the organization and use the data to generate one or more KPIs (Key Performance Indicators). KPIs can be used as performance measurements to measure success or progress of various activities of an organization. For example, for an accounting organization, a KPI can be a percentage of overdue invoices. As another example, for a manufacturing organization, a KPI can be an availability metric that measure production run time divided by total available time.
SUMMARY
The present disclosure involves systems, software, and computer implemented methods for secret shuffle protocols using homomorphic encryption. An example method includes: receiving, from each of a plurality of clients, an encrypted client-specific secret input value; receiving, from each client, an encrypted client-specific random value; generating a client-specific random secret-share for each combination of client and encrypted secret input value, wherein the client-specific secret-shares for one encrypted secret input value add up to zero; for each client, blinding each encrypted secret input value for the client with the random secret-share for the combination of client and encrypted secret input value; sending a list of encrypted blinded secret input values to each client; randomly-permuting, using a first random permutation, the encrypted client-specific random values received from the clients to generate a randomly-permuted list of encrypted random values; sending the randomly-permuted list of encrypted random values to each client; receiving a client-specific list of randomly-permuted rerandomized encrypted blinded secret input values from each client; and homomorphically adding, for each position of multiple list positions in the lists of randomly-permuted rerandomized encrypted blinded secret input values, position-specific encrypted blinded secret values at the position, to generate, by homomorphically removing the random secret-shares, and by homomorphically dividing the resulting encrypted sum by the number of clients, an encrypted secret input value corresponding to the position, wherein resulting encrypted secret input values at all positions are rerandomized and in a shuffled sequence that is unmapped to an order of receipt by the service provider of the encrypted secret input values.
While generally described as computer-implemented software embodied on tangible media that processes and transforms the respective data, some or all of the aspects may be computer-implemented methods or further included in respective systems or other devices for performing this described functionality. The details of these and other aspects and embodiments of the present disclosure are set forth in the accompanying drawings and the description below. Other features, objects, and advantages of the disclosure will be apparent from the description and drawings, and from the claims.
DESCRIPTION OF DRAWINGS
FIG. 1 is a block diagram illustrating an example system for using secret shuffle protocols using homomorphic encryption.
FIG. 2 is an overview table that includes details regarding secret-shuffle protocols.
FIG. 3 illustrates mathematical constructs for homomorphic encryption and rerandomization.
FIG. 4 illustrates an example of a system for oblivious transfer of messages between protocol participants.
FIG. 5A is a table that provides information describing a communication-efficient secret shuffle protocol based on homomorphic encryption and oblivious transfer.
FIG. 5B illustrates a communication scenario for a communication-efficient secret shuffle protocol based on homomorphic encryption and oblivious transfer.
FIG. 6 illustrates a protocol specification for a communication-efficient secret shuffle protocol for encrypted data based on homomorphic encryption and oblivious transfer.
FIG. 7 illustrates a swim lane diagram for a communication-efficient secret shuffle protocol for encrypted data based on homomorphic encryption and oblivious transfer.
FIGS. 8A-8B illustrate a flowchart of a participant method for a communication-efficient secret shuffle protocol for encrypted data based on homomorphic encryption and oblivious transfer.
FIGS. 9A-9B illustrate a flowchart of a service provider method for a communication-efficient secret shuffle protocol for encrypted data based on homomorphic encryption and oblivious transfer.
FIG. 10A is a table that provides information describing a verifiable secret shuffle protocol for encrypted data based on homomorphic encryption and secret sharing.
FIG. 10B illustrates a communication scenario for a verifiable secret shuffle protocol for encrypted data based on homomorphic encryption and secret sharing.
FIG. 11 is a protocol specification for a verifiable secret shuffle protocol for encrypted data based on homomorphic encryption and secret sharing.
FIGS. 12A-B are swims lane diagrams for a verifiable secret shuffle protocol for encrypted data based on homomorphic encryption and secret sharing.
FIG. 13A-B illustrate a flowchart of a participant method for a verifiable secret shuffle protocol for encrypted data based on homomorphic encryption and secret sharing.
FIG. 14A-B illustrate a flowchart of a service provider method for a verifiable secret shuffle protocol for encrypted data based on homomorphic encryption and secret sharing.
FIG. 15A is a table that provides information describing a communication-efficient secret shuffle protocol based on homomorphic encryption.
FIG. 15B illustrates a communication scenario for a communication-efficient secret shuffle protocol based on homomorphic encryption.
FIG. 16 illustrates a protocol specification for a communication-efficient secret shuffle protocol for encrypted data based on homomorphic encryption.
FIG. 17 illustrates a swim lane diagram for a communication-efficient secret shuffle protocol for encrypted data based on homomorphic encryption.
FIGS. 18A-B illustrate a flowchart of a participant method for a communication-efficient secret shuffle protocol for encrypted data based on homomorphic encryption.
FIGS. 19A-B illustrate a flowchart of a service provider method for a communication-efficient secret shuffle protocol for encrypted data based on homomorphic encryption.
FIG. 20A is a table that provides information describing an efficient distributed secret shuffle protocol for encrypted database entries using dependent shufflers.
FIG. 20B illustrates a communication scenario for an efficient distributed secret shuffle protocol for encrypted database entries using dependent shufflers.
FIG. 21 illustrates a protocol specification for an efficient distributed secret shuffle protocol for encrypted database entries using dependent shufflers.
FIG. 22 illustrates a swim lane diagram for an efficient distributed secret shuffle protocol for encrypted database entries using dependent shufflers.
FIGS. 23A-B illustrate a flowchart of a shuffler method for an efficient distributed secret shuffle protocol for encrypted database entries using dependent shufflers.
FIGS. 24A-B illustrates a flowchart of a service provider method for an efficient distributed secret shuffle protocol for encrypted database entries using dependent shufflers.
FIG. 25A is a table that provides information describing an efficient distributed secret shuffle protocol for encrypted database entries using independent shufflers.
FIG. 25B illustrates a communication scenario for an efficient distributed secret shuffle protocol for encrypted database entries using independent shufflers.
FIG. 26 illustrates a protocol specification for an efficient distributed secret shuffle protocol for encrypted database entries using independent shufflers.
FIG. 27 illustrates a swim lane diagram for an efficient distributed secret shuffle protocol for encrypted database entries using independent shufflers.
FIGS. 28A-B illustrate a flowchart of a shuffler method for an efficient distributed secret shuffle protocol for encrypted database entries using independent shufflers.
FIG. 29 illustrates a flowchart of a service provider method for an efficient distributed secret shuffle protocol for encrypted database entries using independent shufflers.
DETAILED DESCRIPTION
In an industrial context, security against dishonest or semi-honest adversaries can be important for companies, since companies typically have a financial and legal interest in the correct execution of processes. Proactive misbehavior or negligent data handling can lead to a loss of reputation or legal consequences, for example. When working with joint collections of confidential data from multiple sources, e.g., in cloud-based multi-party computation scenarios, ownership relation between data providers and their inputs can be considered to be confidential information.
One widely-used measure for companies to determine their performance relatively to their peer group is cross-company benchmarking. In cross-company benchmarking, companies compare their KPI, e.g., return on investment, to those of other companies of the same industry. As benchmark results, companies can obtain statistical measures, such as quartiles and mean. To compute rank-based statistical measures like quartiles, sorting KPIs typically is an important aspect of benchmarking. However, as the companies' performances are confidential, no company should learn another company's KPIs. Instead, benchmark results should only help them determine how they perform relatively to their overall peer group.
Computations could be performed by a trusted third party. However, finding such a trusted third party that every single one of (potentially) mutually distrusting participants trusts might not be possible. As another solution, computations can be performed using secure multi-party communication (MPC). MPC scenarios can include parties each contributing confidential inputs and jointly evaluate the target function with a service provider.
With, for example, a centralized privacy-preserving benchmarking protocol, encrypted KPIs may be sorted according to their underlying plaintexts. However, sorting may enable the service provider to learn the order of the confidential KPIs, that is, how a particular company performs relatively to another particular company. Even if the service provider is assumed to not misuse this information proactively, a data breach could leak this confidential performance information.
To reduce the risk of benchmarks leaking confidential data and relative performance information, efficient privacy-preserving secret shuffle protocols based on MPC can ensure anonymity in the sense that no observer can infer ownership relations between companies and their encrypted KPIs. A secret shuffle can be defined as a function that randomizes the order of a sequence of encrypted inputs such that no observer can map elements in the original sequence to their corresponding elements in the shuffled sequence with probability better than guessing. Preventing such a mapping also implies a need, met by the secret shuffle protocols, for changing the ciphertexts without affecting the underlying plaintexts.
Besides privacy-preserving benchmarking, secret shuffle protocols can be applied to any scenario where participants (e.g., called players) send encrypted inputs to a central service provider, e.g., a cloud service, and want to shuffle the resulting data collection in order to ensure anonymity. Other applications include use cases such as anonymous surveys, polls, and voting, for example.
FIG. 1 is a block diagram illustrating an example system 100 for using secret shuffle protocols using homomorphic encryption. Specifically, the illustrated system 100 includes or is communicably coupled with a server 102 , various data provider and shuffler computing devices as described below, and a network 106 . Although shown separately, in some implementations, functionality of two or more systems or servers may be provided by a single system or server. In some implementations, the functionality of one illustrated system, server, or component may be provided by multiple systems, servers, or components, respectively.
As mentioned, when a service provider (e.g., the server 102 ) works with collections of confidential data from multiple data owners, e.g., in cloud-based multi-party computation scenarios, the position of an entry can leak confidential information such as ownership. When sorting a list of encrypted inputs according to their underlying plaintexts, for instance, the position of an entry in the sorted list of ciphertexts leaks the rank of a data owner's input. Secret shuffling can be performed to eliminate such leakage. Secret shuffling protocols can be, for example, secure multi-party computation protocols for shuffling encrypted data items in a privacy-preserving manner based on an (e.g., additively) homomorphic cryptosystem. Multiple protocols are described.
Each of the protocols can be particularly tailed for particular use case(s) or specific setup(s) that introduce particular requirements. The protocols can be used separately and independently and for different applications. Different prot
TECHNICAL FIELD
The present disclosure relates to computer-implemented methods, software, and systems for secret shuffle protocols using homomorphic encryption.
BACKGROUND
An organization may gather data related to the organization and use the data to generate one or more KPIs (Key Performance Indicators). KPIs can be used as performance measurements to measure success or progress of various activities of an organization. For example, for an accounting organization, a KPI can be a percentage of overdue invoices. As another example, for a manufacturing organization, a KPI can be an availability metric that measure production run time divided by total available time.
SUMMARY
The present disclosure involves systems, software, and computer implemented methods for secret shuffle protocols using homomorphic encryption. An example method includes: receiving, from each of a plurality of clients, an encrypted client-specific secret input value; receiving, from each client, an encrypted client-specific random value; generating a client-specific random secret-share for each combination of client and encrypted secret input value, wherein the client-specific secret-shares for one encrypted secret input value add up to zero; for each client, blinding each encrypted secret input value for the client with the random secret-share for the combination of client and encrypted secret input value; sending a list of encrypted blinded secret input values to each client; randomly-permuting, using a first random permutation, the encrypted client-specific random values received from the clients to generate a randomly-permuted list of encrypted random values; sending the randomly-permuted list of encrypted random values to each client; receiving a client-specific list of randomly-permuted rerandomized encrypted blinded secret input values from each client; and homomorphically adding, for each position of multiple list positions in the lists of randomly-permuted rerandomized encrypted blinded secret input values, position-specific encrypted blinded secret values at the position, to generate, by homomorphically removing the random secret-shares, and by homomorphically dividing the resulting encrypted sum by the number of clients, an encrypted secret input value corresponding to the position, wherein resulting encrypted secret input values at all positions are rerandomized and in a shuffled sequence that is unmapped to an order of receipt by the service provider of the encrypted secret input values.
While generally described as computer-implemented software embodied on tangible media that processes and transforms the respective data, some or all of the aspects may be computer-implemented methods or further included in respective systems or other devices for performing this described functionality. The details of these and other aspects and embodiments of the present disclosure are set forth in the accompanying drawings and the description below. Other features, objects, and advantages of the disclosure will be apparent from the description and drawings, and from the claims.
DESCRIPTION OF DRAWINGS
FIG. 1 is a block diagram illustrating an example system for using secret shuffle protocols using homomorphic encryption.
FIG. 2 is an overview table that includes details regarding secret-shuffle protocols.
FIG. 3 illustrates mathematical constructs for homomorphic encryption and rerandomization.
FIG. 4 illustrates an example of a system for oblivious transfer of messages between protocol participants.
FIG. 5A is a table that provides information describing a communication-efficient secret shuffle protocol based on homomorphic encryption and oblivious transfer.
FIG. 5B illustrates a communication scenario for a communication-efficient secret shuffle protocol based on homomorphic encryption and oblivious transfer.
FIG. 6 illustrates a protocol specification for a communication-efficient secret shuffle protocol for encrypted data based on homomorphic encryption and oblivious transfer.
FIG. 7 illustrates a swim lane diagram for a communication-efficient secret shuffle protocol for encrypted data based on homomorphic encryption and oblivious transfer.
FIGS. 8A-8B illustrate a flowchart of a participant method for a communication-efficient secret shuffle protocol for encrypted data based on homomorphic encryption and oblivious transfer.
FIGS. 9A-9B illustrate a flowchart of a service provider method for a communication-efficient secret shuffle protocol for encrypted data based on homomorphic encryption and oblivious transfer.
FIG. 10A is a table that provides information describing a verifiable secret shuffle protocol for encrypted data based on homomorphic encryption and secret sharing.
FIG. 10B illustrates a communication scenario for a verifiable secret shuffle protocol for encrypted data based on homomorphic encryption and secret sharing.
FIG. 11 is a protocol specification for a verifiable secret shuffle protocol for encrypted data based on homomorphic encryption and secret sharing.
FIGS. 12A-B are swims lane diagrams for a verifiable secret shuffle protocol for encrypted data based on homomorphic encryption and secret sharing.
FIG. 13A-B illustrate a flowchart of a participant method for a verifiable secret shuffle protocol for encrypted data based on homomorphic encryption and secret sharing.
FIG. 14A-B illustrate a flowchart of a service provider method for a verifiable secret shuffle protocol for encrypted data based on homomorphic encryption and secret sharing.
FIG. 15A is a table that provides information describing a communication-efficient secret shuffle protocol based on homomorphic encryption.
FIG. 15B illustrates a communication scenario for a communication-efficient secret shuffle protocol based on homomorphic encryption.
FIG. 16 illustrates a protocol specification for a communication-efficient secret shuffle protocol for encrypted data based on homomorphic encryption.
FIG. 17 illustrates a swim lane diagram for a communication-efficient secret shuffle protocol for encrypted data based on homomorphic encryption.
FIGS. 18A-B illustrate a flowchart of a participant method for a communication-efficient secret shuffle protocol for encrypted data based on homomorphic encryption.
FIGS. 19A-B illustrate a flowchart of a service provider method for a communication-efficient secret shuffle protocol for encrypted data based on homomorphic encryption.
FIG. 20A is a table that provides information describing an efficient distributed secret shuffle protocol for encrypted database entries using dependent shufflers.
FIG. 20B illustrates a communication scenario for an efficient distributed secret shuffle protocol for encrypted database entries using dependent shufflers.
FIG. 21 illustrates a protocol specification for an efficient distributed secret shuffle protocol for encrypted database entries using dependent shufflers.
FIG. 22 illustrates a swim lane diagram for an efficient distributed secret shuffle protocol for encrypted database entries using dependent shufflers.
FIGS. 23A-B illustrate a flowchart of a shuffler method for an efficient distributed secret shuffle protocol for encrypted database entries using dependent shufflers.
FIGS. 24A-B illustrates a flowchart of a service provider method for an efficient distributed secret shuffle protocol for encrypted database entries using dependent shufflers.
FIG. 25A is a table that provides information describing an efficient distributed secret shuffle protocol for encrypted database entries using independent shufflers.
FIG. 25B illustrates a communication scenario for an efficient distributed secret shuffle protocol for encrypted database entries using independent shufflers.
FIG. 26 illustrates a protocol specification for an efficient distributed secret shuffle protocol for encrypted database entries using independent shufflers.
FIG. 27 illustrates a swim lane diagram for an efficient distributed secret shuffle protocol for encrypted database entries using independent shufflers.
FIGS. 28A-B illustrate a flowchart of a shuffler method for an efficient distributed secret shuffle protocol for encrypted database entries using independent shufflers.
FIG. 29 illustrates a flowchart of a service provider method for an efficient distributed secret shuffle protocol for encrypted database entries using independent shufflers.
DETAILED DESCRIPTION
In an industrial context, security against dishonest or semi-honest adversaries can be important for companies, since companies typically have a financial and legal interest in the correct execution of processes. Proactive misbehavior or negligent data handling can lead to a loss of reputation or legal consequences, for example. When working with joint collections of confidential data from multiple sources, e.g., in cloud-based multi-party computation scenarios, ownership relation between data providers and their inputs can be considered to be confidential information.
One widely-used measure for companies to determine their performance relatively to their peer group is cross-company benchmarking. In cross-company benchmarking, companies compare their KPI, e.g., return on investment, to those of other companies of the same industry. As benchmark results, companies can obtain statistical measures, such as quartiles and mean. To compute rank-based statistical measures like quartiles, sorting KPIs typically is an important aspect of benchmarking. However, as the companies' performances are confidential, no company should learn another company's KPIs. Instead, benchmark results should only help them determine how they perform relatively to their overall peer group.
Computations could be performed by a trusted third party. However, finding such a trusted third party that every single one of (potentially) mutually distrusting participants trusts might not be possible. As another solution, computations can be performed using secure multi-party communication (MPC). MPC scenarios can include parties each contributing confidential inputs and jointly evaluate the target function with a service provider.
With, for example, a centralized privacy-preserving benchmarking protocol, encrypted KPIs may be sorted according to their underlying plaintexts. However, sorting may enable the service provider to learn the order of the confidential KPIs, that is, how a particular company performs relatively to another particular company. Even if the service provider is assumed to not misuse this information proactively, a data breach could leak this confidential performance information.
To reduce the risk of benchmarks leaking confidential data and relative performance information, efficient privacy-preserving secret shuffle protocols based on MPC can ensure anonymity in the sense that no observer can infer ownership relations between companies and their encrypted KPIs. A secret shuffle can be defined as a function that randomizes the order of a sequence of encrypted inputs such that no observer can map elements in the original sequence to their corresponding elements in the shuffled sequence with probability better than guessing. Preventing such a mapping also implies a need, met by the secret shuffle protocols, for changing the ciphertexts without affecting the underlying plaintexts.
Besides privacy-preserving benchmarking, secret shuffle protocols can be applied to any scenario where participants (e.g., called players) send encrypted inputs to a central service provider, e.g., a cloud service, and want to shuffle the resulting data collection in order to ensure anonymity. Other applications include use cases such as anonymous surveys, polls, and voting, for example.
FIG. 1 is a block diagram illustrating an example system 100 for using secret shuffle protocols using homomorphic encryption. Specifically, the illustrated system 100 includes or is communicably coupled with a server 102 , various data provider and shuffler computing devices as described below, and a network 106 . Although shown separately, in some implementations, functionality of two or more systems or servers may be provided by a single system or server. In some implementations, the functionality of one illustrated system, server, or component may be provided by multiple systems, servers, or components, respectively.
As mentioned, when a service provider (e.g., the server 102 ) works with collections of confidential data from multiple data owners, e.g., in cloud-based multi-party computation scenarios, the position of an entry can leak confidential information such as ownership. When sorting a list of encrypted inputs according to their underlying plaintexts, for instance, the position of an entry in the sorted list of ciphertexts leaks the rank of a data owner's input. Secret shuffling can be performed to eliminate such leakage. Secret shuffling protocols can be, for example, secure multi-party computation protocols for shuffling encrypted data items in a privacy-preserving manner based on an (e.g., additively) homomorphic cryptosystem. Multiple protocols are described.
Each of the protocols can be particularly tailed for particular use case(s) or specific setup(s) that introduce particular requirements. The protocols can be used separately and independently and for different applications. Different protocol settings and mechanisms have different advantages and disadvantages and make different assumptions (e.g., independent shufflers are available or are not available, computational power of the shufflers is very limited or not, data provider is known or is not, data provider is a single instance or multiple providers).
Protocols can involve data providers, which may or may not be involved in shuffling operations. For instance, some protocol(s) may involve data providers
108 a , 108 b , and 108 c that provide encrypted input data (e.g., an input data value 109 ) and also participate in shuffling (e.g., in combination with the server 102 ). As another example, for some protocol(s), the data providers
108 a , 108 b , 108 c provide data to be stored as encrypted input data 110 , but do not participate in shuffling. Rather, shufflers 112 a , 112 b , and 112 c , for example, can participate in shuffling, with the server 102 , using the encrypted input data 110 provided by the data providers
108 a , 108 b , and 108 c . As yet another example, for some protocol(s) and for a set of data providers, some but not all of the data providers participate in shuffling. For example, data providers 114 a and 114 b may provide data (e.g., an input data value 116 ) but may not perform shuffling, whereas data provider/shufflers 114 c and 114 d may both provide data and perform shuffling.
As described below, the server 102 (and in some cases, a shuffling client or data provider) can include various components for performing shuffling operations. For instance, the server 102 includes one or more homomorphic cryptosystems 122 , with corresponding keys 124 . The server 102 can also include a random number generator 126 , an oblivious transfer mechanism 128 , and a secret-sharing mechanism 130 . Other components can be included.
Each data provider or shuffler can include an application (e.g., an
application
132 a , 132 b , or 132 c ) that can be used for performing shuffling operations and/or for viewing computation results 120 (e.g., aggregate metrics). Shuffling participants can include different cryptosystems and keys (or other components). Data providers and shufflers (or participants that are both data providers and shufflers) can be collectively referred to as clients.
As used in the present disclosure, the term âcomputerâ is intended to encompass any suitable processing device. For example, although FIG. 1 illustrates a single server 102 , and example data providers and shufflers, the system 100 can include two or more servers 102 , or various numbers of data providers or shufflers. Indeed, the server 102 and the shuffler and data provider devices may be any computer or processing device such as, for example, a blade server, general-purpose personal computer (PC), Mac®, workstation, UNIX-based workstation, or any other suitable device. In other words, the present disclosure contemplates computers other than general purpose computers, as well as computers without conventional operating systems. Further, the server 102 and the client devices may be adapted to execute any operating system, including Linux, UNIX, Windows, Mac OS®, Javaâ¢, Androidâ¢, iOS or any other suitable operating system. According to one implementation, the server 102 may also include or be communicably coupled with an e-mail server, a Web server, a caching server, a streaming data server, and/or other suitable server.
Interfaces
150 , 152 , 153 , and 154 are used by the server 102 , and exemplarily, by the data provider 114 a , the shuffler 112 a , and the data provider 108 a , respectively, for communicating with other systems in a distributed environmentâincluding within the system 100 âconnected to the network 106 . Generally, the
interfaces
150 , 152 , 153 , and 154 (and other interfaces) each comprise logic encoded in software and/or hardware in a suitable combination and operable to communicate with the network 106 . More specifically, the
interfaces
150 , 152 , 153 , and 154 (and other interfaces) may each comprise software supporting one or more communication protocols associated with communications such that the network 106 or interface's hardware is operable to communicate physical signals within and outside of the illustrated system 100 .
The server 102 includes one or more processors 156 . Each processor 156 may be a central processing unit (CPU), a blade, an application specific integrated circuit (ASIC), a field-programmable gate array (FPGA), or another suitable component. Generally, each processor 156 executes instructions and manipulates data to perform the operations of the server 102 . Specifically, each processor 156 executes the functionality required to receive and respond to requests from the end-user client device 104 , for example.
Regardless of the particular implementation, âsoftwareâ may include computer-readable instructions, firmware, wired and/or programmed hardware, or any combination thereof on a tangible medium (transitory or non-transitory, as appropriate) operable when executed to perform at least the processes and operations described herein. Indeed, each software component may be fully or partially written or described in any appropriate computer language including C, C++, Javaâ¢, JavaScript®, Visual Basic, assembler, Perl®, any suitable version of 4GL, as well as others. While portions of the software illustrated in FIG. 1 are shown as individual modules that implement the various features and functionality through various objects, methods, or other processes, the software may instead include a number of sub-modules, third-party services, components, libraries, and such, as appropriate. Conversely, the features and functionality of various components can be combined into single components as appropriate.
The server 102 includes memory 158 . In some implementations, the server 102 includes multiple memories. The memory 158 may include any type of memory or database module and may take the form of volatile and/or non-volatile memory including, without limitation, magnetic media, optical media, random access memory (RAM), read-only memory (ROM), removable media, or any other suitable local or remote memory component. The memory 158 may store various objects or data, including caches, classes, frameworks, applications, backup data, business objects, jobs, web pages, web page templates, database tables, database queries, repositories storing business and/or dynamic information, and any other appropriate information including any parameters, variables, algorithms, instructions, rules, constraints, or references thereto associated with the purposes of the server 102 .
The illustrated shufflers and data providers may each generally be any computing device operable to connect to or communicate with the server 102 via the network 106 using a wireline or wireless connection. In general, the shufflers and data providers each comprise an electronic computer device operable to receive, transmit, process, and store any appropriate data associated with the system 100 of FIG. 1 . The shufflers and data providers can each include one or more applications, including the
application
132 a , 132 b , or 132 c , respectively. In some implementations, an application on a shuffler or data provider can use parameters, metadata, and other information received at launch to access a particular set of data from the server 102 . In some instances, an application may be a client application that is an agent or client-side version of the one or more enterprise applications running on an enterprise server (not shown).
Each shuffler or data provider can include one or more processors. For example, the data provider 118 a , the shuffler 112 , and the data provider 114 a include processor(s) 160 , 161 , 162 , respectively. Each
processor
160 , 161 , or 162 may be a central processing unit (CPU), an application specific integrated circuit (ASIC), a field-programmable gate array (FPGA), or another suitable component. Generally, each
processor
160 , 161 , or 162 executes instructions and manipulates data to perform the operations of the respective device. Specifically, each
processor
160 , 161 , or 162 included executes the functionality required to send requests to the server 102 and to receive and process responses from the server 102 .
Each shuffler or data provider is generally intended to encompass any computing device such as a laptop/notebook computer, wireless data port, smart phone, server computing device, personal data assistant (PDA), tablet computing device, one or more processors within these devices, or any other suitable processing device. For example, a client may comprise a computer that includes an input device, such as a keypad, touch screen, or other device that can accept user information, and an output device that conveys information associated with the operation of the server 102 , or the respective device itself, including digital data, visual information, or a
GUI
164 , 165 , or 166 , respectively.
The
GUIs
164 , 165 , and 166 interface with at least a portion of the system 100 for any suitable purpose, including generating a visual representation of the
application
132 a , 132 b , or 132 c , respectively. In particular, the
GUI
164 , 165 or 166 may be used to view and navigate various Web pages. Generally, the
GUI
164 , 165 , and 166 provide a respective user with an efficient and user-friendly presentation of business data provided by or communicated within the system. The
GUI
164 , 165 , and 166 may each comprise a plurality of customizable frames or views having interactive fields, pull-down lists, and buttons operated by the user. The
GUI
164 , 165 , and 166 each contemplate any suitable graphical user interface, such as a combination of a generic web browser, intelligent engine, and command line interface (CLI) that processes information and efficiently presents the results to the user visually.
Memory
168 , 169 , and 170 exemplarily included in the data provider 108 a , the shuffler 112 a , or the data provider 114 a , respectively, may each include any memory or database module and may take the form of volatile or non-volatile memory including, without limitation, magnetic media, optical media, random access memory (RAM), read-only memory (ROM), removable media, or any other suitable local or remote memory component. The
memory
168 , 169 , 170 may each store various objects or data, including user selections, caches, classes, frameworks, applications, backup data, business objects, jobs, web pages, web page templates, database tables, repositories storing business and/or dynamic information, and any other appropriate information including any parameters, variables, algorithms, instructions, rules, constraints, or references thereto associated with the purposes of the associated client device.
There may be any number of data providers and/or shufflers associated with, or external to, the system 100 . Additionally, there may also be one or more additional client or other types of devices external to the illustrated portion of system 100 that are capable of interacting with the system 100 via the network 106 . Further, the term âclientâ, âclient deviceâ and âuserâ may be used interchangeably as appropriate without departing from the scope of this disclosure. Moreover, while devices may be described in terms of being used by a single user, this disclosure contemplates that many users may use one computer, or that one user may use multiple computers.
FIG. 2 is an overview table 200 that includes details regarding secret-
shuffle protocols
202 , 204 , 206 , 208 , and 210 . The protocol 202 is a communication-efficient secret shuffle protocol for encrypted data, based on homomorphic encryption, with oblivious transfer. The protocol 204 is a verifiable secret shuffle protocol for encrypted data, based on homomorphic encryption and secret sharing. The protocol 206 is a computation-efficient secret shuffle for encrypted data, based on homomorphic encryption. The protocol 208 is an efficient, distributed secret shuffle protocol for encrypted database entries using dependent shufflers. The protocol 210 is an efficient, distributed secret shuffle protocol for encrypted database entries using independent shufflers.
The overview table 200 includes information on technologies 212 used by the
protocols
202 , 204 , 206 , 208 , and 210 . As described below with respect to detailed descriptions of particular protocols, each protocol can have different or unique technologies, characteristics, mechanisms, or requirements from other protocols. Some characteristics, requirements or mechanisms may be inconsistent or incompatible with other requirements, characteristics, or mechanisms and may therefore not be combined in a given single protocol. Accordingly, different and separate mechanisms and protocols can be provided and used for different and separate applications. Some protocols may be suited for strong client computation, strong server computation, or a strong network, for example. Specific examples are discussed below.
In further detail, each of the described protocols can be tailored for a specific type of application. To enable different applications, different protocols and mechanisms are provided that use different technologies (e.g., Homomorphic Encryption, Homomorphic Encryption+Secret Sharing, Homomorphic Encryption+Oblivious Transfer). The different protocols and mechanisms have different complexities (steps, communication, computation) and generally make different assumptions (e.g., about mobile scenarios, computational resources, data ownership, etc.). None of the protocols requires one of the other protocols to exist.
Regarding examples of particular technologies, the protocol 202 uses homomorphic encryption 214 and oblivious transfer 216 . As another example, the protocol 204 uses homomorphic encryption 218 and secret sharing 220 .
The overview table 200 also includes information on inputs 222 received or used by the
protocols
202 , 204 , 206 , 208 , and 210 . For instance, the protocol 206 uses inputs 224 provided by clients. As another example, the protocol 208 uses inputs 226 that are included in a service provider's database that were previously provided by a set of clients of which shufflers are a subset.
The overview table 200 includes an indication of how many steps and rounds 228 each
protocol
202 , 204 , 206 , 208 , and 210 includes. For example, the protocol 210 includes ten steps in two rounds 230 . As another example, the protocol 204 includes nine steps in three rounds 232 .
A verifiability indication 234 is included for each
protocol
202 , 204 , 206 , 208 , and 210 . For instance, the protocol 204 is marked as verifiable 236 . Other protocols are not marked as verifiable.
Each
protocol
202 , 204 , 206 , 208 , and 210 has an indication of communication complexity 238 (e.g., between participants). For example, the pro
CLAIMS
Claims ( 20 )
What is claimed is:
1. A system for executing a secret shuffle protocol, the system comprising a plurality of clients and a service provider, wherein each client comprises at least one computing device and the service provider comprises at least one server computing device, and wherein:
each client is configured to:
identify a client-specific secret input value;
encrypt the client-specific secret input value; and
send the encrypted client-specific secret input value to the service provider; and
the service provider is configured to receive, from each client, the encrypted client-specific secret input value; and
each client is further configured to:
generate a client-specific random value;
encrypt the client-specific random value; and
send the encrypted client-specific random value to the service provider; and
the service provider is further configured to:
receive the encrypted client-specific random value from each of the clients; and
the service provider is further configured to:
generate a client-specific random secret-share for each combination of client and encrypted secret input value, wherein the client-specific secret-shares for one encrypted secret input value add up to zero;
for each client, blind each encrypted secret input value for the client with the random secret-share for the combination of client and encrypted secret input value; and
send a list of encrypted blinded secret input values to each client;
each client is further configured to receive, from the service provider, the list of encrypted blinded secret input values;
the service provider is further configured to:
randomly-permute, using a first random permutation, the encrypted client-specific random values received from the clients to generate a randomly-permuted list of encrypted random values; and
send the randomly-permuted list of encrypted random values to each client;
wherein the client is further configured to:
receive the randomly-permuted list of encrypted random values from the service provider;
decrypt each encrypted random value in the randomly-permuted list of encrypted random values to generate a list of random values;
obtain a second random permutation that is based on the list of random values, wherein a same second random permutation is obtained by each client;
rerandomize each encrypted blinded secret input value in the list of encrypted blinded secret input values to generate a rerandomized list of encrypted blinded secret input values;
randomly-permute, using the second permutation, the rerandomized list of encrypted blinded secret input values to generate a client-specific list of randomly-permuted rerandomized encrypted blinded secret input values; and
send the client-specific list of randomly-permuted rerandomized encrypted blinded secret input values to the service provider;
wherein the service provider is further configured to:
receive the client-specific list of randomly-permuted rerandomized encrypted blinded secret input values from each client;
homomorphically adding, for each position of multiple list positions in the lists of randomly-permuted rerandomized encrypted blinded secret input values, position-specific encrypted blinded secret values at the position, to generate, by homomorphically removing the random secret-shares, and by homomorphically dividing the resulting encrypted sum by the number of clients, an encrypted secret input value corresponding to the position, wherein resulting encrypted secret input values at all positions are rerandomized and in a shuffled sequence that is unmapped to an order of receipt by the service provider of the encrypted secret input values.
2. The system of claim 1 , wherein the service provider is further configured to verify the shuffled sequence of encrypted secret input values.
3. The system of claim 1 , wherein verifying the shuffled sequence of encrypted secret input values comprises:
homomorphically computing a first sum of the encrypted secret input values;
homomorphically computing a second sum of the shuffled sequence of encrypted input values;
generating first and second random numbers;
homomorphically computing a difference between the first sum and the second sum; and
using homomorphism to generate an encrypted blinded difference.
4. The system of claim 3 , wherein using homomorphism to generate the encrypted blinded difference comprises homomorphically blinding the difference between the first sum and the second sum multiplicatively with the first random number using exponentiation and additively with the second random number using multiplication.
5. The system of claim 3 , wherein verifying the shuffled sequence of encrypted secret input values comprises:
providing the encrypted blinded difference to each of the shuffling clients;
receiving a blinded difference from each shuffling client;
determining whether all received blinded differences match the second random number;
in response to determining that all of the received blinded differences match the second random number, determining that the shuffled sequence of encrypted secret input values is valid; and
in response to determining that not all of the received blinded differences match the second random number, determining that the shuffled sequence of encrypted secret input values is invalid.
6. The system of claim 1 , wherein the service provider comprises a cloud-based service executed on one or more servers.
7. The system of claim 1 , wherein clients rerandomize encrypted blinded secret input values by multiplication with an encrypted zero value.
8. The system of claim 1 , wherein obtaining the second permutation comprises:
providing the list of random values to a pseudo-random permutation generator; and
receiving the second random permutation from the pseudo-random permutation generator.
9. A computer-implemented method for executing a secret shuffle protocol comprising:
receiving, from each of a plurality of clients, an encrypted client-specific secret input value;
receiving, from each client, an encrypted client-specific random value;
generating a client-specific random secret-share for each combination of client and encrypted secret input value, wherein the client-specific secret-shares for one encrypted secret input value add up to zero;
for each client, blinding each encrypted secret input value for the client with the random secret-share for the combination of client and encrypted secret input value;
sending a list of encrypted blinded secret input values to each client;
randomly-permuting, using a first random permutation, the encrypted client-specific random values received from the clients to generate a randomly-permuted list of encrypted random values;
sending the randomly-permuted list of encrypted random values to each client;
receiving a client-specific list of randomly-permuted rerandomized encrypted blinded secret input values from each client; and
homomorphically adding, for each position of multiple list positions in the lists of randomly-permuted rerandomized encrypted blinded secret input values, position-specific encrypted blinded secret values at the position, to generate, by homomorphically removing the random secret-shares, and by homomorphically dividing the resulting encrypted sum by the number of clients, an encrypted secret input value corresponding to the position, wherein resulting encrypted secret input values at all positions are rerandomized and in a shuffled sequence that is unmapped to an order of receipt by the service provider of the encrypted secret input values.
10. The method of claim 9 , further comprising verifying the shuffled sequence of encrypted secret input values.
11. The method of claim 10 , wherein verifying the shuffled sequence of encrypted secret input values comprises:
homomorphically computing a first sum of the encrypted secret input values;
homomorphically computing a second sum of the shuffled sequence of encrypted input values;
generating first and second random numbers;
homomorphically computing a difference between the first sum and the second sum; and
using homomorphism to generate an encrypted blinded difference.
12. The method of claim 11 , wherein using homomorphism to generate the encrypted blinded difference comprises homomorphically blinding the difference between the first sum and the second sum multiplicatively with the first random number using exponentiation and additively with the second random number using multiplication.
13. The method of claim 11 , wherein verifying the shuffled sequence of encrypted secret input values comprises:
providing the encrypted blinded difference to each of the shuffling clients;
receiving a blinded difference from each shuffling client;
determining whether all received blinded differences match the second random number;
in response to determining that all of the received blinded differences match the second random number, determining that the shuffled sequence of encrypted secret input values is valid; and
in response to determining that not all of the received blinded differences match the second random number, determining that the shuffled sequence of encrypted secret input values is invalid.
14. The method of claim 9 , wherein the rerandomized encrypted blinded secret input values are encrypted by multiplication with an encrypted zero value.
15. A computer program product encoded on a non-transitory storage medium, the product comprising non-transitory, computer readable instructions for causing one or more processors to perform operations comprising:
receiving, from each of a plurality of clients, an encrypted client-specific secret input value;
receiving, from each client, an encrypted client-specific random value;
generating a client-specific random secret-share for each combination of client and encrypted secret input value, wherein the client-specific secret-shares for one encrypted secret input value add up to zero;
for each client, blinding each encrypted secret input value for the client with the random secret-share for the combination of client and encrypted secret input value;
sending a list of encrypted blinded secret input values to each client;
randomly-permuting, using a first random permutation, the encrypted client-specific random values received from the clients to generate a randomly-permuted list of encrypted random values;
sending the randomly-permuted list of encrypted random values to each client;
receiving a client-specific list of randomly-permuted rerandomized encrypted blinded secret input values from each client; and
homomorphically adding, for each position of multiple list positions in the lists of randomly-permuted rerandomized encrypted blinded secret input values, position-specific encrypted blinded secret values at the position, to generate, by homomorphically removing the random secret-shares, and by homomorphically dividing the resulting encrypted sum by the number of clients, an encrypted secret input value corresponding to the position, wherein resulting encrypted secret input values at all positions are rerandomized and in a shuffled sequence that is unmapped to an order of receipt by the service provider of the encrypted secret input values.
16. The computer program product of claim 15 , wherein the operations further comprise verifying the shuffled sequence of encrypted secret input values.
17. The computer program product of claim 16 , wherein verifying the shuffled sequence of encrypted secret input values comprises:
homomorphically computing a first sum of the encrypted secret input values;
homomorphically computing a second sum of the shuffled sequence of encrypted input values;
generating first and second random numbers;
homomorphically computing a difference between the first sum and the second sum; and
using homomorphism to generate an encrypted blinded difference.
18. The computer program product of claim 17 , wherein using homomorphism to generate the encrypted blinded difference comprises homomorphically blinding the difference between the first sum and the second sum multiplicatively with the first random number using exponentiation and additively with the second random number using multiplication.
19. The computer program product of claim 17 , wherein verifying the shuffled sequence of encrypted secret input values comprises:
providing the encrypted blinded difference to each of the shuffling clients;
receiving a blinded difference from each shuffling client;
determining whether all received blinded differences match the second random number;
in response to determining that all of the received blinded differences match the second random number, determining that the shuffled sequence of encrypted secret input values is valid; and
in response to determining that not all of the received blinded differences match the second random number, determining that the shuffled sequence of encrypted secret input values is invalid.
20. The computer program product of claim 15 , wherein the rerandomized encrypted blinded secret input values are encrypted by multiplication with an encrypted zero value.
US16/848,966
2020-04-15
2020-04-15
Verifiable secret shuffle protocol for encrypted data based on homomorphic encryption and secret sharing
Active
2040-06-25
US11356241B2
( en )
Priority Applications (1)
Application Number
Priority Date
Filing Date
Title
US16/848,966
US11356241B2
( en )
2020-04-15
2020-04-15
Verifiable secret shuffle protocol for encrypted data based on homomorphic encryption and secret sharing
Applications Claiming Priority (1)
Application Number
Priority Date
Filing Date
Title
US16/848,966
US11356241B2
( en )
2020-04-15
2020-04-15
Verifiable secret shuffle protocol for encrypted data based on homomorphic encryption and secret sharing
Publications (2)
Publication Number
Publication Date
US20210328762A1
US20210328762A1 ( en )
2021-10-21
US11356241B2
true
US11356241B2 ( en )
2022-06-07
Family
ID=78082777
Family Applications (1)
Application Number
Title
Priority Date
Filing Date
US16/848,966
Active
2040-06-25
US11356241B2
( en )
2020-04-15
2020-04-15
Verifiable secret shuffle protocol for encrypted data based on homomorphic encryption and secret sharing
Country Status (1)
Country
Link
US
( 1 )
US11356241B2
( en )
Cited By (1)
* Cited by examiner, â Cited by third party
Publication number
Priority date
Publication date
Assignee
Title
US12401493B2
( en )
2022-11-28
2025-08-26
Sap Se
Performance benchmarking with cascaded decryption
Families Citing this family (14)
* Cited by examiner, â Cited by third party
Publication number
Priority date
Publication date
Assignee
Title
US11368281B2
( en )
2020-04-15
2022-06-21
Sap Se
Efficient distributed secret shuffle protocol for encrypted database entries using dependent shufflers
US11265153B2
( en )
2020-04-15
2022-03-01
Sap Se
Verifying a result using encrypted data provider data on a public storage medium
US11368296B2
( en )
2020-04-15
2022-06-21
Sap Se
Communication-efficient secret shuffle protocol for encrypted data based on homomorphic encryption and oblivious transfer
US11411725B2
( en )
2020-04-15
2022-08-09
Sap Se
Efficient distributed secret shuffle protocol for encrypted database entries using independent shufflers
US11799643B2
( en )
*
2021-01-19
2023-10-24
Bank Of America Corporation
Collaborative architecture for secure data sharing
CN114282256B
( en )
*
2022-03-04
2022-06-07
æ¯ä»å®(æå·)ä¿¡æ¯ææ¯æéå ¬å¸
Secret sharing-based sorting scrambling method and recovery method
CN114760367B
( en )
*
2022-04-24
2024-05-31
åæ§æ¸ 交信æ¯ç§æ(å京)æéå ¬å¸
Encryption protocol conversion method, first node and second node
KR20230161779A
( en )
*
2022-05-19
2023-11-28
ìì¸ëíêµì°ííë ¥ë¨
Device and Method for Homomorphic Permutation
CN115378725B
( en )
*
2022-08-25
2024-10-29
æ°å¥¥æ°æºç§ææéå ¬å¸
Privacy protection method and device based on multiparty security calculation
CN116388967B
( en )
*
2022-12-30
2025-08-22
ä¸å½å°è´¨å¤§å¦ï¼æ¦æ±ï¼
A secure aggregation method based on random exchange and key homomorphic pseudorandom function
US12259827B2
( en )
*
2023-01-31
2025-03-25
Avago Technologies International Sales Pte. Limited
Systems and methods for address scrambling
CN116471051B
( en )
*
2023-03-22
2024-04-02
çµåç§æ大å¦
A secure multi-party data sorting method based on oblivious transfer protocol
US12231563B2
( en )
2023-04-07
2025-02-18
Lemon Inc.
Secure computation and communication
CN117171779B
( en )
*
2023-11-02
2024-02-27
éªæ·ä¿¡æ¯ç§ææéå ¬å¸
Data processing device based on intersection protection
Citations (32)
* Cited by examiner, â Cited by third party
Publication number
Priority date
Publication date
Assignee
Title
US20080144832A1
( en )
2006-12-18
2008-06-19
Sap Ag
Secure computation of private values
US20130216044A1
( en )
2012-02-17
2013-08-22
International Business Machines Corporation
Homomorphic evaluation including key switching, modulus switching, and dynamic noise management
US20140007250A1
( en )
2012-06-15
2014-01-02
The Regents Of The University Of California
Concealing access patterns to electronic data storage for privacy
US9003204B2
( en )
2013-07-10
2015-04-07
Sap Se
Optimal re-encryption strategy for joins in encrypted databases
US9009089B1
( en )
2011-06-27
2015-04-14
Hrl Laboratories, Llc
Secure pattern matching
US20150341174A1
( en )
2014-05-25
2015-11-26
Fujitsu Limited
Relational Encryption
US9342707B1
( en )
2014-11-06
2016-05-17
Sap Se
Searchable encryption for infrequent queries in adjustable encrypted databases
US20160359617A1
( en )
2015-01-06
2016-12-08
Google Inc.
Systems and methods for a multiple value packing scheme for homomorphic encryption
US9537838B2
( en )
2014-12-22
2017-01-03
Sap Se
Adjustable proxy re-encryption
US20170012970A1
( en )
2014-05-25
2017-01-12
Fujitsu Limited
Relational encryption
US9547720B2
( en )
2014-12-24
2017-01-17
Sap Se
Access control for encrypted query processing
US20170085382A1
( en )
2014-05-25
2017-03-23
Fujitsu Limited
Relational encryption
US20170142109A1
( en )
2014-05-25
2017-05-18
Fujitsu Limited
Relational encryption
US20180205707A1
( en )
2017-01-19
2018-07-19
Hewlett Packard Enterprise Development Lp
Computing a global sum that preserves privacy of parties in a multi-party environment
US10162858B2
( en )
2013-07-31
2018-12-25
Sap Se
Local versus remote optimization in encrypted query processing
US20190297064A1
( en )
*
2018-03-20
2019-09-26
International Business Machines Corporation
Key identifiers in an obliviousness pseudorandom function (oprf)-based key management service (kms)
US20190296897A1
( en )
*
2018-03-20
2019-09-26
International Business Machines Corporation
Virtualizing a key hierarchy using a partially-oblivious pseudorandom function (p-oprf)
US20190296896A1
( en )
*
2018-03-20
2019-09-26
International Business Machines Corporation
Oblivious pseudorandom function in a key management system
US20190356475A1
( en )
*
2018-05-15
2019-11-21
International Business Machines Corporation
Threshold oblivious pseudorandom function in a key management system
US20200021568A1
( en )
2018-07-16
2020-01-16
Sap Se
Private Benchmarking Cloud Service with Enhanced Statistics
US20200067699A1
( en )
*
2018-08-24
2020-02-27
International Business Machines Corporation
Validating keys derived from an oblivious pseudorandom function
US20200067707A1
( en )
*
2018-08-23
2020-02-27
International Business Machines Corporation
Assymetric structured key recovering using oblivious pseudorandom function
US20200092094A1
( en )
*
2018-04-02
2020-03-19
International Business Machines Corporation
Efficient computation of a threshold partially-oblivious pseudorandom function
US10630468B1
( en )
2019-01-11
2020-04-21
Alibaba Group Holding Limited
Distributed multi-party security model training framework for privacy protection
US20200151356A1
( en )
2017-08-11
2020-05-14
Duality Technologies, Inc.
System and method for fast and efficient searching of encrypted ciphertexts
US20200177364A1
( en )
2019-08-09
2020-06-04
Alibaba Group Holding Limited
Determining data processing model parameters through multiparty cooperation
US20200401726A1
( en )
2017-11-20
2020-12-24
Singapore Telecommunications Limited
System and method for private integration of datasets
US11133922B1
( en )
2020-04-15
2021-09-28
Sap Se
Computation-efficient secret shuffle protocol for encrypted data based on homomorphic encryption
US20210328778A1
( en )
2020-04-15
2021-10-21
Sap Se
Verifying a result using encrypted data provider data on a public storage medium
US20210336764A1
( en )
2020-04-15
2021-10-28
Sap Se
Efficient distributed secret shuffle protocol for encrypted database entries using dependent shufflers
US20210336778A1
( en )
2020-04-15
2021-10-28
Sap Se
Efficient distributed secret shuffle protocol for encrypted database entries using independent shufflers
US20210344489A1
( en )
2020-04-15
2021-11-04
Sap Se
Communication-efficient secret shuffle protocol for encrypted data based on homomorphic encryption and oblivious transfer
2020
2020-04-15
US
US16/848,966
patent/US11356241B2/en
active
Active
Patent Citations (33)
* Cited by examiner, â Cited by third party
Publication number
Priority date
Publication date
Assignee
Title
US20080144832A1
( en )
2006-12-18
2008-06-19
Sap Ag
Secure computation of private values
US9009089B1
( en )
2011-06-27
2015-04-14
Hrl Laboratories, Llc
Secure pattern matching
US20130216044A1
( en )
2012-02-17
2013-08-22
International Business Machines Corporation
Homomorphic evaluation including key switching, modulus switching, and dynamic noise management
US20140007250A1
( en )
2012-06-15
2014-01-02
The Regents Of The University Of California
Concealing access patterns to electronic data storage for privacy
US9607161B2
( en )
2013-07-10
2017-03-28
Sap Se
Optimal re-encryption strategy for joins in encrypted databases
US9003204B2
( en )
2013-07-10
2015-04-07
Sap Se
Optimal re-encryption strategy for joins in encrypted databases
US10162858B2
( en )
2013-07-31
2018-12-25
Sap Se
Local versus remote optimization in encrypted query processing
US20170142109A1
( en )
2014-05-25
2017-05-18
Fujitsu Limited
Relational encryption
US20150341174A1
( en )
2014-05-25
2015-11-26
Fujitsu Limited
Relational Encryption
US20170012970A1
( en )
2014-05-25
2017-01-12
Fujitsu Limited
Relational encryption
US20170085382A1
( en )
2014-05-25
2017-03-23
Fujitsu Limited
Relational encryption
US9342707B1
( en )
2014-11-06
2016-05-17
Sap Se
Searchable encryption for infrequent queries in adjustable encrypted databases
US9537838B2
( en )
2014-12-22
2017-01-03
Sap Se
Adjustable proxy re-encryption
US9547720B2
( en )
2014-12-24
2017-01-17
Sap Se
Access control for encrypted query processing
US20160359617A1
( en )
2015-01-06
2016-12-08
Google Inc.
Systems and methods for a multiple value packing scheme for homomorphic encryption
US20180205707A1
( en )
2017-01-19
2018-07-19
Hewlett Packard Enterprise Development Lp
Computing a global sum that preserves privacy of parties in a multi-party environment
US20200151356A1
( en )
2017-08-11
2020-05-14
Duality Technologies, Inc.
System and method for fast and efficient searching of encrypted ciphertexts
US20200401726A1
( en )
2017-11-20
2020-12-24
Singapore Telecommunications Limited
System and method for private integration of datasets
US20190297064A1
( en )
*
2018-03-20
2019-09-26
International Business Machines Corporation
Key identifiers in an obliviousness pseudorandom function (oprf)-based key management service (kms)
US20190296896A1
( en )
*
2018-03-20
2019-09-26
International Business Machines Corporation
Oblivious pseudorandom function in a key management system
US20190296897A1
( en )
*
2018-03-20
2019-09-26
International Business Machines Corporation
Virtualizing a key hierarchy using a partially-oblivious pseudorandom function (p-oprf)
US20200092094A1
( en )
*
2018-04-02
2020-03-19
International Business Machines Corporation
Efficient computation of a threshold partially-oblivious pseudorandom function
US20190356475A1
( en )
*
2018-05-15
2019-11-21
International Business Machines Corporation
Threshold oblivious pseudorandom function in a key management system
US20200021568A1
( en )
2018-07-16
2020-01-16
Sap Se
Private Benchmarking Cloud Service with Enhanced Statistics
US20200067707A1
( en )
*
2018-08-23
2020-02-27
International Business Machines Corporation
Assymetric structured key recovering using oblivious pseudorandom function
US20200067699A1
( en )
*
2018-08-24
2020-02-27
International Business Machines Corporation
Validating keys derived from an oblivious pseudorandom function
US10630468B1
( en )
2019-01-11
2020-04-21
Alibaba Group Holding Limited
Distributed multi-party security model training framework for privacy protection
US20200177364A1
( en )
2019-08-09
2020-06-04
Alibaba Group Holding Limited
Determining data processing model parameters through multiparty cooperation
US11133922B1
( en )
2020-04-15
2021-09-28
Sap Se
Computation-efficient secret shuffle protocol for encrypted data based on homomorphic encryption
US20210328778A1
( en )
2020-04-15
2021-10-21
Sap Se
Verifying a result using encrypted data provider data on a public storage medium
US20210336764A1
( en )
2020-04-15
2021-10-28
Sap Se
Efficient distributed secret shuffle protocol for encrypted database entries using dependent shufflers
US20210336778A1
( en )
2020-04-15
2021-10-28
Sap Se
Efficient distributed secret shuffle protocol for encrypted database entries using independent shufflers
US20210344489A1
( en )
2020-04-15
2021-11-04
Sap Se
Communication-efficient secret shuffle protocol for encrypted data based on homomorphic encryption and oblivious transfer
Non-Patent Citations (4)
* Cited by examiner, â Cited by third party
Title
Becher et al., " An Enhanced Approach to Cloud-based Privacy-preserving Benchmarking (Long Version), " arXiv preprint arXiv: 1810.04971, Oct. 2018, 12 pages.
Becher et al., " Efficient Cloud-based Secret Shuffling via Homomorphic Encryption. " arXiv preprint arXiv:2002.05231, Feb. 12, 2020, 11 pages.
Non-Final Office Action issued in United States U.S. Appl. No. 16/848,963 dated Oct. 13, 2021, 15 pages.
Non-Final Office Action issued in United States U.S. Appl. No. 16/848,982 dated Sep. 14, 2021, 26 pages.
Cited By (1)
* Cited by examiner, â Cited by third party
Publication number
Priority date
Publication date
Assignee
Title
US12401493B2
( en )
2022-11-28
2025-08-26
Sap Se
Performance benchmarking with cascaded decryption
Also Published As
Publication number
Publication date
US20210328762A1
( en )
2021-10-21
Similar Documents
Publication
Publication Date
Title
US11368296B2
( en )
2022-06-21
Communication-efficient secret shuffle protocol for encrypted data based on homomorphic encryption and oblivious transfer
US20210328762A1
( en )
2021-10-21
Verifiable secret shuffle protocol for encrypted data based on homomorphic encryption and secret sharing
US11133922B1
( en )
2021-09-28
Computation-efficient secret shuffle protocol for encrypted data based on homomorphic encryption
US11368281B2
( en )
2022-06-21
Efficient distributed secret shuffle protocol for encrypted database entries using dependent shufflers
US10333696B2
( en )
2019-06-25
Systems and methods for implementing an efficient, scalable homomorphic transformation of encrypted data with minimal data expansion and improved processing efficiency
US11341269B2
( en )
2022-05-24
Providing security against user collusion in data analytics using random group selection
US11050725B2
( en )
2021-06-29
Private benchmarking cloud service with enhanced statistics
US12067129B2
( en )
2024-08-20
Privacy preserving computation protocol for data analytics
US20190386814A1
( en )
2019-12-19
Systems and Methods for Implementing an Efficient, Scalable Homomorphic Transformation of Encrypted Data with Minimal Data Expansion and Improved Processing Efficiency
Wang et al.
2010
Privacy-preserving public auditing for data storage security in cloud computing
Abadi et al.
2015
O-PSI: delegated private set intersection on outsourced datasets
US11411725B2
( en )
2022-08-09
Efficient distributed secret shuffle protocol for encrypted database entries using independent shufflers
US11250140B2
( en )
2022-02-15
Cloud-based secure computation of the median
CN115037477A
( en )
2022-09-09
Block chain-based federated learning privacy protection method
US11190336B2
( en )
2021-11-30
Privacy-preserving benchmarking with interval statistics reducing leakage
Yi et al.
2019
Privacy-preserving user profile matching in social networks
WO2019094303A1
( en )
2019-05-16
Systems and methods for implementing an efficient, scalable homomorphic transformation of encrypted data with minimal data expansion and improved processing efficiency
Salvakkam et al.
2023
An improved lattice based certificateless data integrity verification techniques for cloud computing
US11750380B2
( en )
2023-09-05
Storing and retrieving user data using joint, non-correlative, irreversible and private indexical expressions
Hadian Dehkordi et al.
2024
Changeable essential threshold secret image sharing scheme with verifiability using bloom filter
Dou et al.
2016
Efficient private subset computation
US11907392B2
( en )
2024-02-20
System and method utilizing function secret sharing with conditional disclosure of secrets
Liu et al.
2015
Proofs of encrypted data retrievability with probabilistic and homomorphic message authenticators
Qiang
2018
Faster fog-aided private set intersection with integrity preserving
Zhou et al.
2017
Efficient secure multiparty subset computation
Legal Events
Date
Code
Title
Description
2020-04-15
AS
Assignment
Owner name : SAP SE, GERMANY
Free format text : ASSIGNMENT OF ASSIGNORS INTEREST;ASSIGNORS:BECHER, KILIAN;SCHROEPFER, AXEL;SCHAEFER, MIRKO;REEL/FRAME:052406/0815
<p itemprop="attributes" itemsc