METHOD AND APPARATUS FOR NEARLY OPTIMAL PRIVATE CONVOLUTION
First Claim
1. A method for computing a private convolution comprising:
- receiving private data, x, the private data x being stored in a database;
receiving public data, h, the public data h being received from a querier;
transforming, by a controller, the private and public data to obtain transformed private data {circumflex over (x)} and transformed public data Ĥ
;
adding, by a privacy processor, noise to the transformed private data {circumflex over (x)} to obtain a noisy transformed private data {tilde over (x)};
multiplying, by the privacy processor, the noisy transformed private data with the transformed public data to obtain a product data y=Ĥ
{tilde over (x)}; and
inverse transforming, by the privacy processor, the product data to obtain privacy preserving output {tilde over (y)}releasing {tilde over (y)} to the querier.
0 Assignments
0 Petitions
Accused Products
Abstract
A method and apparatus for ensuring a level of privacy for answering a convolution query on data stored in a database is provided. The method and apparatus includes the activities of determining (402) the level of privacy associated with at least a portion of the data stored in the database and receiving (404) query data, from a querier, for use in performing a convolution over the data stored in the database. The database is searched (406) for data related to the received query data and the data that corresponds to the received query data is retrieved (408) from the database. An amount of noise based on the determined privacy level is generated (410) and added (412) to the retrieved data to create noisy data which is then communicated (414) to the querier.
50 Citations
24 Claims
-
1. A method for computing a private convolution comprising:
-
receiving private data, x, the private data x being stored in a database; receiving public data, h, the public data h being received from a querier; transforming, by a controller, the private and public data to obtain transformed private data {circumflex over (x)} and transformed public data Ĥ
;adding, by a privacy processor, noise to the transformed private data {circumflex over (x)} to obtain a noisy transformed private data {tilde over (x)}; multiplying, by the privacy processor, the noisy transformed private data with the transformed public data to obtain a product data y =Ĥ
{tilde over (x)}; andinverse transforming, by the privacy processor, the product data to obtain privacy preserving output {tilde over (y)} releasing {tilde over (y)} to the querier. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8)
-
-
9. An apparatus for computing a private convolution comprising:
-
a database having private data, x, stored therein a controller that receives public data, h, from a querier and transforms the private and public data to obtain transformed private data {circumflex over (x)} and transformed public data Ĥ
; anda privacy processor that adds noise to the transformed private data {circumflex over (x)} to obtain a noisy transformed private data {tilde over (x)}; multiplies the noisy transformed private data with the transformed public data to obtain a product data y =Ĥ
{tilde over (x)}; andinverse transforms the product data to obtain privacy preserving output {tilde over (y)} for release to the querier. - View Dependent Claims (10, 11, 12, 13, 14, 15, 16, 23)
(a) z0=Lap(η
) and zi=Lap (η
2−
k/2) for i in [N/2k, N/2k-1−
1], where
-
-
14. The apparatus of claim 9, wherein
the apparatus performs linear filtering of data. -
15. The apparatus of claim 14, wherein
the linear filtering is performed during financial analysis, the financial analysis including one of volatility estimation and business cycle analysis. -
16. The apparatus of claim 9, wherein
the apparatus executes generalized marginal queries. -
23. The apparatus of claim 14, wherein
the linear filtering is performed during financial analysis, the financial analysis including one of volatility estimation and business cycle analysis.
-
17. An apparatus for computing a private convolution comprising:
-
means for storing private data, x means for receiving public data, h, from a querier; means for transforming the private and public data to obtain transformed private data {circumflex over (x)} and transformed public data Ĥ
;means for adding noise to the transformed private data {circumflex over (x)} to obtain a noisy transformed private data {tilde over (x)}; means for multiplying the noisy transformed private data with the transformed public data to obtain a product data y =Ĥ
{tilde over (x)}; andmeans for inverse transforms the product data to obtain privacy preserving output {tilde over (y)} for release to the querier. - View Dependent Claims (18, 19, 20, 21, 22, 24)
-
Specification