Patent Issued for Differential privacy for encrypted data (USPTO 11328082): Ketch Kloud Inc.

2022 MAY 31 (NewsRx) -- By a News Reporter-Staff News Editor at Insurance Daily News -- From Alexandria, Virginia, NewsRx journalists report that a patent by the inventors Alexander, Samuel (San Francisco, CA, US), Anderson, Maxwell (San Francisco, CA, US), Chavez, Tom (San Francisco, CA, US), Salomon, Yacov (Danville, CA, US), Vaidya, Vivek (San Francisco, CA, US), Winter, Anton (San Mateo, CA, US), Yates, Seth (Danville, CA, US), filed on April 13, 2020, was published online on May 10, 2022.

The patent’s assignee for patent number 11328082 is Ketch Kloud Inc. (San Francisco, California, United States).

News editors obtained the following quote from the background information supplied by the inventors: “Some database systems may store information related to a number of users. In some cases, this user data may include personally identifiable information (PII) or other data protected under one or more data privacy regulations. Some examples of such regulations may include the European Union’s General Data Protection Regulation (GDPR), the Health Insurance Portability and Accountability Act (HIPAA) for health-related data privacy, and the Federal Trade Commission’s (FTC’s) data and privacy regulations for financial institutions, among other such regulations. However, despite the regulations, such user data may be extremely valuable for statistical analysis (e.g., to determine marketing campaigns, track user trends, etc.). As such, some systems or users may desire to use this user data for statistical analysis within the bounds of the privacy regulations. Further complicating such analysis, database systems may encrypt the user data at rest for data securitization. Some encryption techniques may not support statistical analysis. However, decrypting user data for statistical analysis may involve the system storing PII or other protected information as unencrypted, noise-free data (e.g., temporarily while performing one or more statistical methods). While in this unencrypted, noise-free state, a malicious user may access the data, resulting in data leakage of private user data from the database system.”

As a supplement to the background information on this patent, NewsRx correspondents also obtained the inventors’ summary information for this patent: “A database system may store information for a number of users, including personally identifiable information (PII) or other data protected under one or more data privacy regulations. Such user data may be extremely valuable for data analytics, including statistical analysis. For example, although specific data values may be protected under the data regulations, general trends, average values, or similar statistical properties may be informative to a system or user analyzing the data (e.g., for targeting groups of users, making generalized determinations about groups of users, etc.). However, to run a statistical query on the user data in the database system, the data regulations may enforce maintaining a balance between providing accurate insights and respecting the privacy of the individual users. To support such a balance, a system may implement differential privacy as a statistical method for providing guarantees to users for bounded privacy. Differential privacy techniques may involve adding noise or sampling of user data to obfuscate any specific personal information for the users.

“In some cases, the database system may secure the user information by storing the user data as encrypted at rest in a database. For example, the user data may be encrypted to ensure that the data is accessed by specific users or systems with the proper credentials and is used for specific purposes supported by legitimizing reasons (e.g., user consent or other regulations). The database may restrict other users or systems from accessing the data and may restrict requests for unauthorized usages of the data by withholding an encryption key corresponding to the encrypted data. While statistical queries on the data may be supported by the database system, temporarily decrypting the data for statistical analysis may, correspondingly, temporarily expose private user data (e.g., for potential security breaches by malicious users). For example, this data may not include noise (e.g., from one or more differential privacy techniques) upon decryption. If this data is directly accessed in any way (e.g., prior to applying differential privacy), the database system may fail to uphold one or more data regulations associated with user privacy.

“To perform statistical analysis on user data while maintaining data security and supporting data regulations, a system may implement homomorphic differentially private statistical queries. The system may store user data in a database using homomorphic encryption. In some cases, a single value may be stored multiple times using multiple different homomorphic encryption techniques to support different functionality. When the system receives a statistical query for the user data, the system may identify a differential privacy mechanism applicable to the query, queried data, or both. Based on this identified differential privacy mechanism, the system may transform the query. The transformation may involve rewriting the query to target specific encrypted data in the database and to inject noise into the query results (e.g., without decrypting the data) by leveraging particular homomorphic encryption mechanisms. The system may execute the transformed query at the database to add noise into the queried data and retrieve a noisified query result including encrypted user data (e.g., ciphertext). The system may decrypt the encrypted user data to perform statistical analysis on the user data. By injecting noise into the data at query time (e.g., while the data is encrypted), the decrypted user data may already be differentially private. As such, the decryption may not expose any specific user data to potentially malicious users. Instead, by applying differential privacy on the encrypted data in the database (e.g., by leveraging specific homomorphic encryption properties), the system may support statistical analysis of user data while following data privacy regulations.

“Aspects of the disclosure are initially described in the context of systems supporting differential privacy for encrypted data. Additional aspects of the disclosure are described with reference to a database configuration and a process flow. Aspects of the disclosure are further illustrated by and described with reference to apparatus diagrams, system diagrams, and flowcharts that relate to differential privacy for encrypted data.”

The claims supplied by the inventors are:

“1. A method for data processing, comprising: receiving, from an application, a query comprising a request for data stored as ciphertext at a database; identifying a differential privacy mechanism applicable to the query, the data, or both; transforming the query to comprise a noisification function based at least in part on the differential privacy mechanism; executing the transformed query at the database, wherein the executing comprises adding noise to a query result at the database prior to decrypting the ciphertext to obtain a noisified query result according to the noisification function; and receiving, from the database and in response to the transformed query, the noisified query result comprising the ciphertext based at least in part on executing the transformed query.

“2. The method of claim 1, further comprising: decrypting the ciphertext for the noisified query result; and transmitting, to the application and in response to the query, the noisified query result comprising the decrypted ciphertext.

“3. The method of claim 2, wherein the query comprises a statistical query, the method further comprising: performing one or more statistical operations on the noisified query result based at least in part on the decrypted ciphertext and the statistical query.

“4. The method of claim 2, wherein the ciphertext for the noisified query result is decrypted external to the database.

“5. The method of claim 1, wherein transforming the query further comprises: performing one or more calls to one or more user-defined functions based at least in part on the query, the differential privacy mechanism, or both.

“6. The method of claim 1, further comprising: encrypting the data to obtain the ciphertext; and storing the ciphertext at the database, wherein the stored ciphertext is noise-free.

“7. The method of claim 6, wherein: the query is associated with an analytics operation; and the differential privacy mechanism is identified based at least in part on the analytics operation, the method further comprising: receiving, from a second application, a second query comprising a second request for at least a portion of the data, wherein the second query is associated with a permissioned user request; executing the second query at the database to obtain a query result comprising second ciphertext associated with the portion of the data; receiving, from the database and in response to the second query, the query result comprising the second ciphertext based at least in part on executing the second query; decrypting the second ciphertext for the query result to obtain the portion of the data, wherein the portion of the data is noise-free based at least in part on the storing and the second query being associated with the permissioned user request; and transmitting, to the second application and in response to the second query, the portion of the data.

“8. The method of claim 1, wherein the noisification function is associated with a level of noise, the method further comprising: determining the level of noise for the noisification function based at least in part on a preference of an owner of the data, a user identifier associated with the query, an analytics operation associated with the query, or a combination thereof.

“9. The method of claim 1, wherein the query comprises a count operation and adding the noise to the query result at the database further comprises: calculating one or more aggregate values based at least in part on the ciphertext and the count operation, wherein each aggregate value of the one or more aggregate values is associated with a corresponding ciphertext label; determining one or more noise values; and adding the one or more noise values to at least one of the one or more aggregate values to obtain one or more noisified aggregate values, wherein the noisified query result comprises the one or more noisified aggregate values and wherein each noisified aggregate value of the one or more noisified aggregate values is associated with the corresponding ciphertext label.

“10. The method of claim 1, wherein the query comprises a field-level operation and adding the noise to the query result at the database further comprises: identifying a plurality of encrypted fields in the database comprising the ciphertext, wherein the ciphertext is encrypted according to a homomorphic encryption key; determining a plurality of noise values, wherein each noise value of the plurality of noise values corresponds to a respective field of the plurality of fields; encrypting the plurality of noise values using the homomorphic encryption key; and adding the plurality of encrypted noise values to the plurality of encrypted fields based at least in part on the field-level operation to obtain a plurality of noisified encrypted field values, wherein the noisified query result comprises the plurality of noisified encrypted field values.

“11. The method of claim 10, wherein: the database comprises a relational database; the field-level operation comprises a row-level operation, a join operation, or a combination thereof in the relational database; and the plurality of encrypted fields comprises a column in the relational database.

“12. The method of claim 1, wherein: the database comprises a relational database; and the data is stored as first ciphertext in a first column of the relational database and as second ciphertext in a second column of the relational database, wherein the first ciphertext is encrypted according to a first homomorphic encryption method and the second ciphertext is encrypted according to a second homomorphic encryption method different from the first homomorphic encryption method.

“13. The method of claim 12, wherein the ciphertext comprises the first ciphertext and executing the transformed query at the database further comprises: determining to use the first column for executing the transformed query based at least in part on the first homomorphic encryption method supporting the differential privacy mechanism.

“14. The method of claim 1, further comprising: refraining from handling a plaintext version of the data in the database based at least in part on adding the noise to the query result at the database prior to decrypting the ciphertext.

“15. An apparatus for data processing, comprising: a processor; memory coupled with the processor; and instructions stored in the memory and executable by the processor to cause the apparatus to: receive, from an application, a query comprising a request for data stored as ciphertext at a database; identify a differential privacy mechanism applicable to the query, the data, or both; transform the query to comprise a noisification function based at least in part on the differential privacy mechanism; execute the transformed query at the database, wherein the executing comprises adding noise to a query result at the database prior to decrypting the ciphertext to obtain a noisified query result according to the noisification function; and receive, from the database and in response to the transformed query, the noisified query result comprising the ciphertext based at least in part on executing the transformed query.

“16. The apparatus of claim 15, wherein the instructions are further executable by the processor to cause the apparatus to: decrypt the ciphertext for the noisified query result; and transmit, to the application and in response to the query, the noisified query result comprising the decrypted ciphertext.

“17. The apparatus of claim 15, wherein the instructions to transform the query further are executable by the processor to cause the apparatus to: perform one or more calls to one or more user-defined functions based at least in part on the query, the differential privacy mechanism, or both.

“18. The apparatus of claim 15, wherein the instructions are further executable by the processor to cause the apparatus to: encrypt the data to obtain the ciphertext; and store the ciphertext at the database, wherein the stored ciphertext is noise-free.

“19. The apparatus of claim 15, wherein the noisification function is associated with a level of noise, and the instructions are further executable by the processor to cause the apparatus to: determine the level of noise for the noisification function based at least in part on a preference of an owner of the data, a user identifier associated with the query, an analytics operation associated with the query, or a combination thereof.

“20. A non-transitory computer-readable medium storing code for data processing, the code comprising instructions executable by a processor to: receive, from an application, a query comprising a request for data stored as ciphertext at a database; identify a differential privacy mechanism applicable to the query, the data, or both; transform the query to comprise a noisification function based at least in part on the differential privacy mechanism; execute the transformed query at the database, wherein the executing comprises adding noise to a query result at the database prior to decrypting the ciphertext to obtain a noisified query result according to the noisification function; and receive, from the database and in response to the transformed query, the noisified query result comprising the ciphertext based at least in part on executing the transformed query.”

For additional information on this patent, see: Alexander, Samuel. Differential privacy for encrypted data. U.S. Patent Number 11328082, filed April 13, 2020, and published online on May 10, 2022. Patent URL: http://patft.uspto.gov/netacgi/nph-Parser?Sect1=PTO1&Sect2=HITOFF&d=PALL&p=1&u=%2Fnetahtml%2FPTO%2Fsrchnum.htm&r=1&f=G&l=50&s1=11328082.PN.&OS=PN/11328082RS=PN/11328082

(Our reports deliver fact-based news of research and discoveries from around the world.)