-
公开(公告)号:US12199956B2
公开(公告)日:2025-01-14
申请号:US18403339
申请日:2024-01-03
Applicant: Google LLC
Inventor: Badih Ghazi , Noah Zeger Golowich , Shanmugasundaram Ravikumar , Pasin Manurangsi , Ameya Avinash Velingker , Rasmus Pagh
Abstract: An encoding method for enabling privacy-preserving aggregation of private data can include obtaining private data including a private value, determining a probabilistic status defining one of a first condition and a second condition, producing a multiset including a plurality of multiset values, and providing the multiset for aggregation with a plurality of additional multisets respectively generated for a plurality of additional private values. In response to the probabilistic status having the first condition, the plurality of multiset values is based at least in part on the private value, and in response to the probabilistic status having the second condition, the plurality of multiset values is a noise message. The noise message is produced based at least in part on a noise distribution that comprises a discretization of a continuous unimodal distribution supported on a range from zero to a number of multiset values included in the plurality of multiset values.
-
公开(公告)号:US20250005179A1
公开(公告)日:2025-01-02
申请号:US18502816
申请日:2023-11-06
Applicant: Google LLC
Inventor: Jiayu Peng , Michael James Wurm , Chenwei Wang , Pasin Manurangsi , Adam Benjamin Gelernter Sealfon , Jakub Tetek , Matthew Tran Clegg
IPC: G06F21/62
Abstract: Systems and methods for generating and maintaining differential privacy while providing accurate values can include obtaining a plurality of noise-added values, processing the plurality of noise-added values to determine a predicted value. The plurality of noise-added value may be utilized to determine one or more accuracy values that can be compared to a threshold to determine if more data is to be obtained and processed before providing a predicted value.
-
公开(公告)号:US20230032705A1
公开(公告)日:2023-02-02
申请号:US17863186
申请日:2022-07-12
Applicant: Google LLC
Inventor: Vidhya Navalpakkam , Pasin Manurangsi , Nachiappan Valliappan , Kai Kohlhoff , Junfeng He , Badih Ghazi , Shanmugasundaram Ravikumar
IPC: G06F21/62
Abstract: Improved methods are provided for generating heatmaps or other summary map data from multiple users' data (e.g., probability distributions) in a manner that preserves the privacy of the users' data while also generating heatmaps that are visually similar to the ‘true’ heatmap. These methods include decomposing the average of the users' data (the ‘true’ heatmap) into multiple different spatial scales, injecting random noise into the data at the multiple different spatial scales, and then reconstructing the privacy-preserving heatmap based on the noisy multi-scale representations. The magnitude of the noise injected at each spatial scale is selected to ensure preservation of privacy while also resulting in heatmaps that are visually similar to the ‘true’ heatmap.
-
公开(公告)号:US20210243171A1
公开(公告)日:2021-08-05
申请号:US17122638
申请日:2020-12-15
Applicant: Google LLC
Inventor: Badih Ghazi , Noah Zeger Golowich , Shanmugasundaram Ravikumar , Pasin Manurangsi , Ameya Avinash Velingker , Rasmus Pagh
Abstract: An encoding method for enabling privacy-preserving aggregation of private data can include obtaining private data including a private value, determining a probabilistic status defining one of a first condition and a second condition, producing a multiset including a plurality of multiset values, and providing the multiset for aggregation with a plurality of additional multisets respectively generated for a plurality of additional private values. In response to the probabilistic status having the first condition, the plurality of multiset values is based at least in part on the private value, and in response to the probabilistic status having the second condition, the plurality of multiset values is a noise message. The noise message is produced based at least in part on a noise distribution that comprises a discretization of a continuous unimodal distribution supported on a range from zero to a number of multiset values included in the plurality of multiset values.
-
公开(公告)号:US20240320271A1
公开(公告)日:2024-09-26
申请号:US18434260
申请日:2024-02-06
Applicant: Google LLC
Inventor: Shanmugasundaram Ravikumar , Pasin Manurangsi , Badih Ghazi
IPC: G06F16/906 , G06F18/21 , G06F18/214 , G06F18/23213 , G06F18/2413
CPC classification number: G06F16/906 , G06F18/214 , G06F18/2193 , G06F18/23213 , G06F18/24137
Abstract: Example techniques are provided for the task of differentially private clustering. For several basic clustering problems, including Euclidean DensestBall, 1-Cluster, k-means, and k-median, the present disclosure provides efficient differentially private algorithms that achieve essentially the same approximation ratios as those that can be obtained by any non-private algorithm, while incurring only small additive errors. This improves upon existing efficient algorithms that only achieve some large constant approximation factors.
-
公开(公告)号:US20240265294A1
公开(公告)日:2024-08-08
申请号:US18156915
申请日:2023-01-19
Applicant: Google LLC
Inventor: Badih Ghazi , Pritish Kamath , Shanmugasundaram Ravikumar , Ethan Jacob Leeman , Pasin Manurangsi , Avinash Vaidyanathan Varadarajan , Chiyuan Zhang
IPC: G06N20/00
CPC classification number: G06N20/00
Abstract: An example method is provided for conducting differentially private communication of training data for training a machine-learned model. Initial label data can be obtained that corresponds to feature data. A plurality of label bins can be determined to respectively provide representative values for initial label values assigned to the plurality of label bins. Noised label data can be generated, based on a probability distribution over the plurality of label bins, to correspond to the initial label data, the probability distribution characterized by, for a respective noised label corresponding to a respective initial label of the initial label data, a first probability for returning a representative value of a label bin to which the respective initial label is assigned, and a second probability for returning another value. The noised label data can be communicated for training the machine-learned model.
-
公开(公告)号:US20240236052A1
公开(公告)日:2024-07-11
申请号:US18403339
申请日:2024-01-03
Applicant: Google LLC
Inventor: Badih Ghazi , Noah Zeger Golowich , Shanmugasundaram Ravikumar , Pasin Manurangsi , Ameya Avinash Velingker , Rasmus Pagh
CPC classification number: H04L63/0428 , G06N5/04 , G06N20/00
Abstract: An encoding method for enabling privacy-preserving aggregation of private data can include obtaining private data including a private value, determining a probabilistic status defining one of a first condition and a second condition, producing a multiset including a plurality of multiset values, and providing the multiset for aggregation with a plurality of additional multisets respectively generated for a plurality of additional private values. In response to the probabilistic status having the first condition, the plurality of multiset values is based at least in part on the private value, and in response to the probabilistic status having the second condition, the plurality of multiset values is a noise message. The noise message is produced based at least in part on a noise distribution that comprises a discretization of a continuous unimodal distribution supported on a range from zero to a number of multiset values included in the plurality of multiset values.
-
公开(公告)号:US20230327850A1
公开(公告)日:2023-10-12
申请号:US18297084
申请日:2023-04-07
Applicant: Google LLC
Inventor: Badih Ghazi , Shanmugasundaram Ravikumar , Pasin Manurangsi , Mariana Petrova Raykova , Adrian Gascon , James Henry Bell , Phillipp Schoppmann
CPC classification number: H04L9/008 , H04L9/14 , H04L9/0643 , H04L2209/46
Abstract: Provided are systems and methods for the computation of sparse, (ε, δ)-differentially private (DP) histograms in the two-server model of secure multi-party computation (MPC). Example protocols enable two semi-honest non-colluding servers to compute histograms over the data held by multiple users, while only learning a private view of the data.
-
公开(公告)号:US20230308422A1
公开(公告)日:2023-09-28
申请号:US18011995
申请日:2021-12-20
Applicant: Google LLC
Inventor: Badih Ghazi , Shanmugasundaram Ravikumar , Alisa Chang , Pasin Manurangsi
CPC classification number: H04L63/0428 , G06F21/604
Abstract: A computer-implemented method for encoding data for communications with improved privacy includes obtaining, by a computing system comprising one or more computing devices, input data including one or more input data points. The method can include constructing, by the computing system, a net tree including potential representatives of the one or more input data points, the potential representatives arranged in a plurality of levels, the net tree including a hierarchical data structure including a plurality of hierarchically organized nodes. The method can include determining, by the computing system, a representative of each of the one or more input data points from the potential representatives of the net tree, the representative including one of the plurality of hierarchically organized nodes. The method can include encoding, by the computing system, the representative of each of the one or more input data points for communication.
-
公开(公告)号:US20250139282A1
公开(公告)日:2025-05-01
申请号:US17926281
申请日:2022-08-23
Applicant: Google LLC
Inventor: Pasin Manurangsi , Shanmugasundaram Ravikumar , Badih Ghazi , Matthew Tran Clegg , Joseph Sean Cahill Goodknight Knightbrook
IPC: G06F21/62
Abstract: Methods, systems, and apparatus, including medium-encoded computer program products, for adaptive privacy-preserving information retrieval. An information server can accept from a user a request for privacy sensitive information accessible to the information server. The information server can determine a remaining privacy allocation for the user of the information server and can determine a noise parameter for a response to the request, where application of the noise parameter to the response can decrease a privacy loss associated with the response. The information server can determine a privacy modifier for the response. In response to the information server determining that the remaining privacy allocation satisfies the privacy modifier, the information server can: (i) determining the response to the request; (ii) apply the noise parameter to the response to produce a noised response; (iii) provide the noised response to the user; and (iv) adjust the remaining privacy allocation according to the privacy modifier.
-
-
-
-
-
-
-
-
-