IP Library › Granted Patent US 12,572,684
Granted Patent B2
US 12,572,684 · App. 17/357,096 · Granted Mar 10, 2026

Secure multi-party computation of differentially private heavy hitters

Inventor: Jonas Boehler (Karlsruhe, DE)
Assignee: SAP SE
G06F21/6227G06F7/08G06F16/2282
View Patent ↗
Loading inventors, assignments & file history…
Monitor This Case
Get email alerts when status or documents change.
Order Certified Copies
Most orders are placed with the USPTO same day — all within 24 business hours.
Order via The Patent Place →
Pre-filled with this patent's details
Quick Facts
Patent No.
US 12,572,684
App. No.
17/357,096
Granted
Mar 10, 2026
Kind
B2
Abstract

According to an aspect, a method may include receiving a candidate value; in response to a received candidate value matching one of the entries in the table, incrementing a corresponding count; in response to the received candidate value not matching one of the entries in the table and the table not exceeding a threshold size, adding an entry to the table; in response to the received candidate value not matching one of the entries in the table and the table exceeding the threshold size, decrementing the counts in the table and deleting entries having a count of zero; adding noise to the corresponding counts in the entries of the table and deleting any noisy corresponding counts less than a threshold value; and outputting at least a portion of the table as the top-k value result set.

Claims (35)

1 . A system, comprising:

at least one data processor; and

at least one memory storing instructions which, when executed by the at least one data processor, result in operations comprising:

generating, for a top-k value determination across a plurality of clients, a table including entries to map candidate values to corresponding counts;

receiving, from each of the plurality of clients, a candidate value;

in response to a received candidate value matching one of the entries in the table, incrementing, for the matching candidate value, a corresponding count;

in response to the received candidate value not matching one of the entries in the table and the table not exceeding a threshold size, adding an entry to the table by adding the received candidate value with a count value of 1;

in response to the received candidate value not matching one of the entries in the table and the table exceeding the threshold size, decrementing all of the counts in the table by 1 and deleting from the table any entries having a count of zero;

adding one of Laplace noise, exponential noise, or Gumbel noise to the corresponding counts in the entries of the table;

in response to a noisy corresponding count being less than a threshold value, deleting the corresponding entry in the table for the noisy corresponding count;

determining, based on a multi-party computation using a domain of data across the plurality of clients and over the domain of data, a top-k value result set, wherein the multi-party computation comprises a plurality of compute nodes across one or more of the plurality of clients and the top-k value result set being split into multiple shares distributed across the compute nodes, each of the compute nodes exchanging secure input messages with other compute nodes, each of the secure input messages containing one or more of the shares, and the exchanged secure input messages being used to jointly compute the top-k value result set by combining the shares contained in the secure input messages to reconstruct the top-k value result set, while keeping private data secret from the other compute nodes; and

outputting at least a portion of the table as the top-k value result set.

2 . The system of claim 1 , wherein the table is sorted based on the noisy corresponding count before the outputting.

3 . The system of claim 1 , wherein the system comprises or is comprised in a trusted server.

4 . The system of claim 1 , wherein the receiving, from each of the plurality of clients, the candidate value comprises, receiving the candidate value in a secured message, the secured message further including a partial noise value.

5 . The system of claim 4 , wherein the adding noise to the corresponding counts in the entries of the table further comprises adding the noise based on the partial noise value from each of the plurality of clients.

6 . The system of claim 1 , wherein the outputting at least a portion of the table as the top-k value result set further comprises outputting the at least a portion of the table in a secured message.

7 . The system of claim 1 , wherein the top-k value result set is output in accordance with differential privacy.

8 . A computer-implemented method comprising:

generating, for a top-k value determination across a plurality of clients, a table including entries to map candidate values to corresponding counts;

receiving, from each of the plurality of clients, a candidate value;

in response to a received candidate value matching one of the entries in the table, incrementing, for the matching candidate value, a corresponding count;

in response to the received candidate value not matching one of the entries in the table and the table not exceeding a threshold size, adding an entry to the table by adding the received candidate value with a count value of 1;

in response to the received candidate value not matching one of the entries in the table and the table exceeding the threshold size, decrementing all of the counts in the table by 1 and deleting from the table any entries having a count of zero;

adding one of Laplace noise, exponential noise, or Gumbel noise to the corresponding counts in the entries of the table;

in response to a noisy corresponding count being less than a threshold value, deleting the corresponding entry in the table for the noisy corresponding count;

determining, based on a multi-party computation using a domain of data across the plurality of clients and over the domain of data, a top-k value result set, wherein the multi-party computation comprises a plurality of compute nodes across one or more of the plurality of clients and the top-k value result set being split into multiple shares distributed across the compute nodes, each of the compute nodes exchanging secure input messages with other compute nodes, each of the secure input messages containing one or more of the shares, and the exchanged secure input messages being used to jointly compute the top-k value result set by combining the shares contained in the secure input messages to reconstruct the top-k value result set, while keeping private data secret from the other compute nodes; and

outputting at least a portion of the table as the top-k value result set on an output device.

9 . The method of claim 8 , wherein the table is sorted based on the noisy corresponding count before the outputting.

10 . The method of claim 8 , wherein the method is implemented by a trusted server, wherein the trusted server comprises at least one data processor and at least one memory.

11 . The method of claim 10 , wherein the trusted server performs the multi-party computation.

12 . The method of claim 8 , wherein the receiving, from each of the plurality of clients, the candidate value comprises, receiving the candidate value in a secured message, the secured message further including a partial noise value.

13 . The method of claim 12 , wherein the adding noise to the corresponding counts in the entries of the table further comprises adding the noise based on the partial noise value from each of the plurality of clients.

14 . The method of claim 8 , wherein the outputting at least a portion of the table as the top-k value result set further comprises outputting the at least a portion of the table in a secured message.

15 . The method of claim 8 , wherein the top-k value result set is output in accordance with differential privacy.

Assignments (1)
ASSIGNMENT OF ASSIGNOR'S INTEREST Recorded Jun 24, 2021
From: BOEHLER, JONAS
To: SAP SE
Reel/Frame 056657/0539 →
Continuity (1)
Related Publication 20230017374A1 · Jan 19, 2023
References Cited (43)
US 11170131B1 · Rogers · 2021 [cited by examiner]
US 20180114028A1 · Kafai · 2018 [cited by examiner]
US 20180336357A1 · Nissim Kobliner · 2018 [cited by examiner]
US 20190095487A1 · Le · 2019 [cited by examiner]
US 20190272388A1 · Tsou · 2019 [cited by examiner]
Anderson et al, “A High-Performance Algorithm for Identifying Frequent Items in Data Streams”, May 2017, pp. 1-22, downloaded from https://arxiv.org/pdf/1705.07001 (Year: 2017). [cited by examiner]
Chan et al, “Differentially Private Continual Monitoring of Heavy Hitters from Distributed Streams”, 2012, pp. 1-30, downloaded from https://link.springer.com/chapter/10.1007/978-3-642-31680-7_8 (Year: 2012). [cited by examiner]
Dai et al, “A Multibranch Search Tree-Based Multi-Keyword Ranked Search Scheme over Encrypted Cloud Data”, Jan. 2020, pp. 1-15, downloaded from https://www.hindawi.com/journals/scn/2020/7307315/ (Year: 2020). [cited by examiner]
Apple's Differential Privacy Team. Learning with privacy at scale, (available at https://machinelearning.apple.com/research/learning-with-privacy-at-scale) 2017. [cited by applicant]
Balcer, V. et al., “Separating local & shuffled differential privacy via histograms,” arXiv:1911.06879v1, 2019. [cited by applicant]
Bittau, A. et al., “Prochlo: Strong privacy for analytics in the crowd,” In Proceedings of the Symposium on Operating Systems Principles, SOSP, 2017. [cited by applicant]
Boehler, J. et al., Secure multiparty computation of differentially private median. In 29th USENIX Security Symposium. [cited by applicant]
Boehler, J. et al., “Secure sublinear time differentially private median computation,” In Network and Distributed Systems Security Symposium, NDSS, 2020. [cited by applicant]
Cheu, A. et al., “Distributed differential privacy via shuffling,” In Annual International Conference on the Theory and Applications of Cryptographic Techniques, Eurocrypt, 2019. [cited by applicant]
Cormode, G. et al., “Methods for finding frequent items in data streams,” The VLDB Journal (2010) 19:3-20. [cited by applicant]
Ding, B. et al., “Collecting telemetry data privately,” In Advances in Neural Information Processing Systems, NeurIPS, 2017. [cited by applicant]
Durfee, D. et al., “Practical differentially private top-k selection with pay-what-you-get composition,” In Advances in Neural Information Processing Systems, pp. 3532-3542, 2019. [cited by applicant]
Dwork, C. et al., “Calibrating noise to sensitivity in private data analysis,” In Theory of Cryptography Conference, TCC, 2006. [cited by applicant]
Dwork, C. “Differential privacy,” In International Colloquium on Automata, Languages, and Programming, ICALP, 2006. [cited by applicant]
Dwork, C. et al., “Our data, ourselves: Privacy via distributed noise generation,” In Annual International Conference on the Theory and Applications of Cryptographic Techniques, Eurocrypt, 2006. [cited by applicant]
Dwork, C. et al., “The algorithmic foundations of differential privacy,” Foundations and Trends in Theoretical Computer Science, 2014. [cited by applicant]
Eigner, F. et al., “Differentially private data aggregation with optimal utility,” In Proceedings of the Annual Computer Security Applications Conference, ACSAC, 2014. [cited by applicant]
Erlingsson, U. et al., “RAPPOR: Randomized aggregatable privacy-preserving ordinal response,” In Proceedings of the annual ACM conference on computer and communications security, CCS, 2014. [cited by applicant]
Fanti, G. et al., “Building a RAPPOR with the unknown: Privacy-preserving learning of associations and data dictionaries,” Proceedings on Privacy Enhancing Technologies, 2016. [cited by applicant]
Goldreich, O. “Foundations of Cryptography: vol. 2, Basic Applications,” 2009. [cited by applicant]
Goryczka, S. et al., “A comprehensive comparison of multiparty secure additions with differential privacy,” IEEE transactions on Dependable and Secure Computing, 2017. [cited by applicant]
Guevara, M., Google Developers Blog. “Enabling developers and organizations to use differential privacy,” 2019. [cited by applicant]
Hsu, J. et al., “Distributed private heavy hitters,” In International Colloquium on Automata, Languages, and Programming, ICALP, 2012. [cited by applicant]
Kasiviswanathan, S.P. et al., What can we learn privately? SIAM Journal on Computing, 2011. [cited by applicant]
McGregor, A. et al., “The limits of two-party differential privacy,” In Annual IEEE Symposium on Foundations of Computer Science, FOCS, 2010. [cited by applicant]
McSherry, F. et al., “Mechanism design via differential privacy,” In Annual IEEE Symposium on Foundations of Computer Science, FOCS, 2007. [cited by applicant]
Neel, S. et al., “Differentially private objective perturbation: Beyond smoothness and convexity,” arXiv:1909.01783, 2019. [cited by applicant]
Pettai, M. et al., “Combining differential privacy and secure multiparty computation,” In Proceedings of the Annual Computer Security Applications Conference, ACSAC, 2015. [cited by applicant]
Rastogi, V. et al., “Differentially private aggregation of distributed time-series with transformation and encryption,” In Proceedings of the annual ACM SIGMOD International Conference on Management of data, SIGMOD, 201… [cited by applicant]
Rogers, R. “A differentially private data analytics {API} at scale,” Conference Presentation, In USENIX Conference on Privacy Engineering Practice and Respect, PEPR, 2020. [cited by applicant]
Rogers, R. et al., “Linkedin's audience engagements api: A privacy preserving data analytics system at scale,” arXiv:2022.05839, 2021. [cited by applicant]
Takabi, H. et al., “Differentially private distributed data analysis,” In IEEE International Conference on Collaboration and Internet Computing, CIC, 2016. [cited by applicant]
Wang, T. et al., “Locally differentially private heavy hitter identification,” IEEE transactions on Dependable and Secure Computing, arXiv:1708.06674, 2017. [cited by applicant]
Wilson, R.J. et al., “Differentially private SQL with bounded user contribution,” In International Symposium on Privacy Enhancing Technologies Symposium, PETS, 2020. [cited by applicant]
WWDC 2016. “Engineering privacy for your users,” Transcript. 2016 (Available at https://wwdctogether.com/wwdc2016/709). [cited by applicant]
Bhaskar, R. et al., “Discovering Frequent Patterns in Sensitive Data,” Proceedings of the 19th International Conference on Information & Knowledge Management and Co-Located Workshops, (CIKM '10), Jul. 25, 2010, pp. 503-… [cited by applicant]
Bhattacharyya, A. et al., “An Optimal Algorithm for -Heavy Hitters in Insertion Streams and Related Problems,” ACM Transactions on Algorithms, vol. 15, No. 1, Oct. 22, 2018, pp. 1-27. [cited by applicant]
Extended European Search Report issued in European Application No. 21211207.2-1218, mailed May 3, 2022, 16 pages. [cited by applicant]