Computationally Secure Aggregation and Private Information Retrieval in the Shuffle Model
Pages 4122 - 4136
Abstract
The shuffle model has recently emerged as a popular setting for differential privacy, where clients can communicate with a central server using anonymous channels or an intermediate message shuffler. This model was also explored in the context of cryptographic tasks such as secure aggregation and private information retrieval (PIR). However, this study was almost entirely restricted to the stringent notion of information-theoretic security.
In this work, we study computationally secure aggregation protocols and PIR in the shuffle model. Our starting point is the insight that the previous technique of shuffling additive shares can be improved in the computational setting. We show that this indeed holds under the standard learning parity with noise (LPN) assumption, but even better efficiency follows from plausible conjectures about the multi-disjoint syndrome decoding (MDSD) problem that we introduce and study in this work.
We leverage the above towards improving the efficiency of secure aggregation and PIR in the shuffle model. For secure aggregation of long vectors, our protocols require 9x--25x less communication than the previous information-theoretic solutions. Our PIR protocols enjoy the simplicity and concrete efficiency benefits of multi-server PIR while only requiring a single server to store the database. Under the MDSD assumption, they improve over recent single-server PIR constructions by up to two orders of magnitude.
References
[1]
Surya Addanki, Kevin Garbe, Eli Jaffe, Rafail Ostrovsky, and Antigoni Polychroniadou. 2022. Prio: Privacy Preserving Aggregate Statistics via Boolean Shares. In SCN. 516--539.
[2]
Apple. 2021. iCloud Private Relay Overview. https://www.apple.com/icloud/docs/iCloud_Private_Relay_Overview_Dec2021.pdf.
[3]
Benny Applebaum, Yuval Ishai, and Eyal Kushilevitz. 2007. Cryptography with Constant Input Locality. In Advances in Cryptology -- CRYPTO 2007 (Lecture Notes in Computer Science, Vol. 4622), Alfred Menezes (Ed.). Springer, Heidelberg, Germany, Santa Barbara, CA, USA, 92--110. https://doi.org/10.1007/978--3--540--74143--5_6
[4]
Daniel Augot, Matthieu Finiasz, and Nicolas Sendrier. 2003. A Fast Provably Secure Cryptographic Hash Function. Cryptology ePrint Archive, Paper 2003/230. https://eprint.iacr.org/2003/230 https://eprint.iacr.org/2003/230.
[5]
Borja Balle, James Bell, Adrià Gascón, and Kobbi Nissim. 2019. The Privacy Blanket of the Shuffle Model. In Advances in Cryptology -- CRYPTO 2019, Part II (Lecture Notes in Computer Science, Vol. 11693), Alexandra Boldyreva and Daniele Micciancio (Eds.). Springer, Heidelberg, Germany, Santa Barbara, CA, USA, 638--667. https://doi.org/10.1007/978--3-030--26951--7_22
[6]
Borja Balle, James Bell, Adrià Gascón, and Kobbi Nissim. 2020. Private Summation in the Multi-Message Shuffle Model. In ACM CCS 2020: 27th Conference on Computer and Communications Security, Jay Ligatti, Xinming Ou, Jonathan Katz, and Giovanni Vigna (Eds.). ACM Press, Virtual Event, USA, 657--676. https://doi.org/10.1145/3372297.3417242
[7]
Amos Beimel, Yuval Ishai, and Tal Malkin. 2000. Reducing the Servers Computation in Private Information Retrieval: PIR with Preprocessing. In Advances in Cryptology -- CRYPTO 2000 (Lecture Notes in Computer Science, Vol. 1880), Mihir Bellare (Ed.). Springer, Heidelberg, Germany, Santa Barbara, CA, USA, 55--73. https://doi.org/10.1007/3--540--44598--6_4
[8]
James Bell, Adrià Gascón, Tancrède Lepoint, Baiyu Li, Sarah Meiklejohn, Mariana Raykova, and Cathie Yun. 2023. ACORN: Input Validation for Secure Aggregation. In 32nd USENIX Security Symposium (USENIX Security 23).
[9]
James Henry Bell, Kallista A. Bonawitz, Adrià Gascón, Tancrède Lepoint, and Mariana Raykova. 2020. Secure Single-Server Aggregation with (Poly)Logarithmic Overhead. In CCS. ACM, 1253--1269.
[10]
Elwyn R. Berlekamp, Robert J. McEliece, and Henk C. A. van Tilborg. 1978. On the inherent intractability of certain coding problems (Corresp.). IEEE Trans. Inf. Theory, Vol. 24, 3 (1978), 384--386. https://doi.org/10.1109/TIT.1978.1055873
[11]
Andrea Bittau, Úlfar Erlingsson, Petros Maniatis, Ilya Mironov, Ananth Raghunathan, David Lie, Mitch Rudominer, Ushasree Kode, Julien Tinnes, and Bernhard Seefeld. 2017. Prochlo: Strong Privacy for Analytics in the Crowd. In Proceedings of the 26th Symposium on Operating Systems Principles (SOSP '17).
[12]
Avrim Blum, Merrick L. Furst, Michael J. Kearns, and Richard J. Lipton. 1994. Cryptographic Primitives Based on Hard Learning Problems. In Advances in Cryptology -- CRYPTO'93 (Lecture Notes in Computer Science, Vol. 773), Douglas R. Stinson (Ed.). Springer, Heidelberg, Germany, Santa Barbara, CA, USA, 278--291. https://doi.org/10.1007/3--540--48329--2_24
[13]
Kallista A. Bonawitz, Vladimir Ivanov, Ben Kreuter, Antonio Marcedone, H. Brendan McMahan, Sarvar Patel, Daniel Ramage, Aaron Segal, and Karn Seth. 2017. Practical Secure Aggregation for Privacy-Preserving Machine Learning. In CCS. ACM, 1175--1191.
[14]
Dan Boneh, Elette Boyle, Henry Corrigan-Gibbs, Niv Gilboa, and Yuval Ishai. 2021. Lightweight Techniques for Private Heavy Hitters. In 2021 IEEE Symposium on Security and Privacy (SP).
[15]
Elette Boyle, Geoffroy Couteau, Niv Gilboa, Yuval Ishai, Lisa Kohl, and Peter Scholl. 2020. Correlated Pseudorandom Functions from Variable-Density LPN. In 61st Annual Symposium on Foundations of Computer Science. IEEE Computer Society Press, Durham, NC, USA, 1069--1080. https://doi.org/10.1109/FOCS46700.2020.00103
[16]
Pierre Briaud and Morten Øygarden. 2023. A New Algebraic Approach to the Regular Syndrome Decoding Problem and Implications for PCG Constructions. In Advances in Cryptology -- EUROCRYPT 2023, Part V (Lecture Notes in Computer Science, Vol. 14008), Carmit Hazay and Martijn Stam (Eds.). Springer, Heidelberg, Germany, Lyon, France, 391--422. https://doi.org/10.1007/978--3-031--30589--4_14
[17]
Jan Camenisch and Anna Lysyanskaya. 2005. A Formal Treatment of Onion Routing. In Advances in Cryptology -- CRYPTO 2005 (Lecture Notes in Computer Science, Vol. 3621), Victor Shoup (Ed.). Springer, Heidelberg, Germany, Santa Barbara, CA, USA, 169--187. https://doi.org/10.1007/11535218_11
[18]
David Chaum. 1981. Untraceable Electronic Mail, Return Addresses, and Digital Pseudonyms. Commun. ACM, Vol. 24, 2 (1981), 84--88. https://doi.org/10.1145/358549.358563
[19]
David Chaum. 1988. The Dining Cryptographers Problem: Unconditional Sender and Recipient Untraceability. J. Cryptol., Vol. 1, 1 (1988), 65--75. https://doi.org/10.1007/BF00206326
[20]
Albert Cheu. 2021. Differential Privacy in the Shuffle Model: A Survey of Separations. CoRR, Vol. abs/2107.11839 (2021). showeprint[arXiv]2107.11839 https://arxiv.org/abs/2107.11839
[21]
Albert Cheu, Adam D. Smith, Jonathan Ullman, David Zeber, and Maxim Zhilyaev. 2019. Distributed Differential Privacy via Shuffling. In Advances in Cryptology -- EUROCRYPT 2019, Part I (Lecture Notes in Computer Science, Vol. 11476), Yuval Ishai and Vincent Rijmen (Eds.). Springer, Heidelberg, Germany, Darmstadt, Germany, 375--403. https://doi.org/10.1007/978--3-030--17653--2_13
[22]
Albert Cheu and Maxim Zhilyaev. 2022. Differentially Private Histograms in the Shuffle Model from Fake Users. In 43rd IEEE Symposium on Security and Privacy, SP 2022, San Francisco, CA, USA, May 22--26, 2022. IEEE, 440--457. https://doi.org/10.1109/SP46214.2022.9833614
[23]
Benny Chor, Eyal Kushilevitz, Oded Goldreich, and Madhu Sudan. 1998. Private Information Retrieval. J. ACM, Vol. 45, 6 (1998), 965--981. https://doi.org/10.1145/293347.293350
[24]
Google Chrome. 2023. IP Protection. https://github.com/GoogleChrome/ip-protection.
[25]
Cloudflare. 2022. Privacy Gateway. https://blog.cloudflare.com/building-privacy-into-internet-standards-and-how-to-make-your-app-more-private-today.
[26]
Henry Corrigan-Gibbs and Dan Boneh. 2017. Prio: private, robust, and scalable computation of aggregate statistics. In Proceedings of the 14th USENIX Conference on Networked Systems Design and Implementation (NSDI'17).
[27]
Alex Davidson, Gonccalo Pestana, and Sofía Celi. 2023. FrodoPIR: Simple, Scalable, Single-Server Private Information Retrieval. Proc. Priv. Enhancing Technol., Vol. 2023, 1 (2023), 365--383. https://doi.org/10.56553/POPETS-2023-0022
[28]
Roger Dingledine, Nick Mathewson, and Paul Syverson. 2004. Tor: the second-generation onion router. In Proceedings of the 13th Conference on USENIX Security Symposium - Volume 13 (SSYM'04). USENIX Association.
[29]
Ilya Dumer. 1991. On minimum distance decoding of linear codes. In Proc. 5th Joint Soviet-Swedish Int. Workshop Inform. Theory. Moscow, 50--52.
[30]
Úlfar Erlingsson, Vitaly Feldman, Ilya Mironov, Ananth Raghunathan, Kunal Talwar, and Abhradeep Thakurta. 2019. Amplification by shuffling: from local to central differential privacy via anonymity. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '19).
[31]
Andre Esser and Emanuele Bellini. 2022. Syndrome Decoding Estimator. In Public-Key Cryptography - PKC 2022 - 25th IACR International Conference on Practice and Theory of Public-Key Cryptography, Virtual Event, March 8--11, 2022, Proceedings, Part I (Lecture Notes in Computer Science, Vol. 13177), Goichiro Hanaoka, Junji Shikata, and Yohei Watanabe (Eds.). Springer, 112--141. https://doi.org/10.1007/978--3-030--97121--2_5
[32]
Andre Esser, Javier Verbel, Floyd Zweydinger, and Emanuele Bellini. 2023. textttCryptographicEstimators: a Software Library for Cryptographic Hardness Estimation. Cryptology ePrint Archive, Paper 2023/589. https://eprint.iacr.org/2023/589 https://eprint.iacr.org/2023/589.
[33]
Michael J. Freedman and Robert Morris. 2002. Tarzan: a peer-to-peer anonymizing network layer. In Proceedings of the 9th ACM Conference on Computer and Communications Security (CCS '02).
[34]
Adrià Gascón, Yuval Ishai, Mahimna Kelkar, Baiyu Li, Yiping Ma, and Mariana Raykova. 2024. Computationally Secure Aggregation and Private Information Retrieval in the Shuffle Model. Cryptology ePrint Archive, Paper 2024/870. https://eprint.iacr.org/2024/870 https://eprint.iacr.org/2024/870.
[35]
Badih Ghazi, Pasin Manurangsi, Rasmus Pagh, and Ameya Velingker. 2020. Private Aggregation from Fewer Anonymous Messages. In Advances in Cryptology -- EUROCRYPT 2020, Part II (Lecture Notes in Computer Science, Vol. 12106), Anne Canteaut and Yuval Ishai (Eds.). Springer, Heidelberg, Germany, Zagreb, Croatia, 798--827. https://doi.org/10.1007/978--3-030--45724--2_27
[36]
David Goldschlag, Michael Reed, and Paul Syverson. 1999. Onion routing. Commun. ACM, Vol. 42, 2 (1999).
[37]
Philippe Golle and Ari Juels. 2004. Dining Cryptographers Revisited. In Advances in Cryptology -- EUROCRYPT 2004 (Lecture Notes in Computer Science, Vol. 3027), Christian Cachin and Jan Camenisch (Eds.). Springer, Heidelberg, Germany, Interlaken, Switzerland, 456--473. https://doi.org/10.1007/978--3--540--24676--3_27
[38]
Ceki Gulcu and Gene Tsudik. 1996. Mixing Email with Babel. In Proceedings of the 1996 Symposium on Network and Distributed System Security (SNDSS '96) (SNDSS '96).
[39]
Shai Halevi, Yuval Ishai, Eyal Kushilevitz, and Tal Rabin. 2023. Additive Randomized Encodings and Their Applications. In Advances in Cryptology - CRYPTO 2023 - 43rd Annual International Cryptology Conference, CRYPTO 2023, Santa Barbara, CA, USA, August 20--24, 2023, Proceedings, Part I (Lecture Notes in Computer Science, Vol. 14081), Helena Handschuh and Anna Lysyanskaya (Eds.). Springer, 203--235. https://doi.org/10.1007/978--3-031--38557--5_7
[40]
Carmit Hazay, Emmanuela Orsini, Peter Scholl, and Eduardo Soria-Vazquez. 2022. TinyKeys: A New Approach to Efficient Multi-Party Computation. Journal of Cryptology, Vol. 35, 2 (April 2022), 13. https://doi.org/10.1007/s00145-022-09423--5
[41]
Alexandra Henzinger, Matthew M. Hong, Henry Corrigan-Gibbs, Sarah Meiklejohn, and Vinod Vaikuntanathan. 2023. One Server for the Price of Two: Simple and Fast Single-Server Private Information Retrieval. In 32nd USENIX Security Symposium, USENIX Security 2023, Anaheim, CA, USA, August 9--11, 2023, Joseph A. Calandrino and Carmela Troncoso (Eds.).
[42]
Yuval Ishai, Mahimna Kelkar, Daniel Lee, and Yiping Ma. 2024. Information-Theoretic Single-Server PIR in the Shuffle Model. In ITC 2024. https://eprint.iacr.org/2024/930.
[43]
Yuval Ishai, Eyal Kushilevitz, Rafail Ostrovsky, and Amit Sahai. 2006. Cryptography from Anonymity. In 47th Annual Symposium on Foundations of Computer Science. IEEE Computer Society Press, Berkeley, CA, USA, 239--248. https://doi.org/10.1109/FOCS.2006.25
[44]
Jonathan Katz, Ji Sun Shin, and Adam Smith. 2010. Parallel and Concurrent Security of the HB and HB Protocols. Journal of Cryptology, Vol. 23, 3 (July 2010), 402--421. https://doi.org/10.1007/s00145-010--9061--2
[45]
Eyal Kushilevitz and Rafail Ostrovsky. 1997. Replication is NOT Needed: SINGLE Database, Computationally-Private Information Retrieval. In 38th Annual Symposium on Foundations of Computer Science. IEEE Computer Society Press, Miami Beach, Florida, 364--373. https://doi.org/10.1109/SFCS.1997.646125
[46]
Pil Joong Lee and Ernest F. Brickell. 1988. An Observation on the Security of McEliece's Public-Key Cryptosystem. In Advances in Cryptology - EUROCRYPT '88, Workshop on the Theory and Application of of Cryptographic Techniques, Davos, Switzerland, May 25--27, 1988, Proceedings (Lecture Notes in Computer Science, Vol. 330). Springer, 275--280. https://doi.org/10.1007/3--540--45961--8_25
[47]
Baiyu Li, Daniele Micciancio, Mariana Raykova, and Mark Schultz-Wu. 2024. Hintless Single-Server Private Information Retrieval. In CRYPTO 2024. https://eprint.iacr.org/2023/1733.
[48]
Hanjun Li, Huijia Lin, Antigoni Polychroniadou, and Stefano Tessaro. 2023. LERNA: Secure Single-Server Aggregation via Key-Homomorphic Masking. In ASIACRYPT (1) (Lecture Notes in Computer Science, Vol. 14438). Springer, 302--334.
[49]
Hanlin Liu, Xiao Wang, Kang Yang, and Yu Yu. 2022. The Hardness of LPN over Any Integer Ring and Field for PCG Applications. IACR Cryptol. ePrint Arch. (2022), 712.
[50]
Yiping Ma, Jess Woods, Sebastian Angel, Antigoni Polychroniadou, and Tal Rabin. 2023. Flamingo: Multi-Round Single-Server Secure Aggregation with Applications to Private Federated Learning. In 44th IEEE Symposium on Security and Privacy, SP 2023, San Francisco, CA, USA, May 21--25, 2023. IEEE, 477--496.
[51]
Robert J. McEliece. 1978. A public key cryptosystem based on algebraic coding theory. In The Deep Space Network Progress Report. https://api.semanticscholar.org/CorpusID:56502909
[52]
Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Agüera y Arcas. 2017. Communication-Efficient Learning of Deep Networks from Decentralized Data. In Proceedings of the 20th International Conference on Artificial Intelligence and Statistics, AISTATS 2017, 20--22 April 2017, Fort Lauderdale, FL, USA, Aarti Singh and Xiaojin (Jerry) Zhu (Eds.).
[53]
Samir Jordan Menon and David J. Wu. 2022. SPIRAL: Fast, High-Rate Single-Server PIR via FHE Composition. In 2022 IEEE Symposium on Security and Privacy (SP).
[54]
Daniele Micciancio and Petros Mol. 2011. Pseudorandom Knapsacks and the Sample Complexity of LWE Search-to-Decision Reductions. In Advances in Cryptology -- CRYPTO 2011 (Lecture Notes in Computer Science, Vol. 6841), Phillip Rogaway (Ed.). Springer, Heidelberg, Germany, Santa Barbara, CA, USA, 465--484. https://doi.org/10.1007/978--3--642--22792--9_26
[55]
Daniele Micciancio and Michael Walter. 2018. On the Bit Security of Cryptographic Primitives. In Advances in Cryptology -- EUROCRYPT 2018, Part I (Lecture Notes in Computer Science, Vol. 10820), Jesper Buus Nielsen and Vincent Rijmen (Eds.). Springer, Heidelberg, Germany, Tel Aviv, Israel, 3--28. https://doi.org/10.1007/978--3--319--78381--9_1
[56]
C. Andrew Neff. 2001. A verifiable secret shuffle and its application to e-voting. In Proceedings of the 8th ACM Conference on Computer and Communications Security (CCS '01).
[57]
Sarvar Patel, Giuseppe Persiano, and Kevin Yeo. 2018. Private Stateful Information Retrieval. In ACM CCS 2018: 25th Conference on Computer and Communications Security, David Lie, Mohammad Mannan, Michael Backes, and XiaoFeng Wang (Eds.). ACM Press, Toronto, ON, Canada, 1002--1019. https://doi.org/10.1145/3243734.3243821
[58]
Krzysztof Pietrzak. 2012. Cryptography from Learning Parity with Noise. In SOFSEM (Lecture Notes in Computer Science, Vol. 7147). Springer, 99--114.
[59]
Eugene Prange. 1962. The use of information sets in decoding cyclic codes. IRE Trans. Inf. Theory, Vol. 8, 5 (1962), 5--9. https://doi.org/10.1109/TIT.1962.1057777
[60]
Oded Regev. 2005. On lattices, learning with errors, random linear codes, and cryptography. In 37th Annual ACM Symposium on Theory of Computing, Harold N. Gabow and Ronald Fagin (Eds.). ACM Press, Baltimore, MA, USA, 84--93. https://doi.org/10.1145/1060590.1060603
[61]
Nicolas Sendrier. 2011. Decoding One Out of Many. In PQCrypto (Lecture Notes in Computer Science, Vol. 7071). Springer, 51--67.
[62]
Jacques Stern. 1988. A method for finding codewords of small weight. In Coding Theory and Applications (Lecture Notes in Computer Science, Vol. 388). Springer, 106--113.
[63]
Rodolfo Canto Torres and Nicolas Sendrier. 2016. Analysis of Information Set Decoding for a Sub-linear Error Weight. In PQCrypto (Lecture Notes in Computer Science, Vol. 9606). Springer, 144--161.
[64]
Ke Zhong, Yiping Ma, and Sebastian Angel. 2022. Ibex: Privacy-preserving Ad Conversion Tracking and Bidding. In ACM CCS 2022: 29th Conference on Computer and Communications Security, Heng Yin, Angelos Stavrou, Cas Cremers, and Elaine Shi (Eds.). ACM Press, Los Angeles, CA, USA, 3223--3237. https://doi.org/10.1145/3548606.3560651
[65]
Mingxun Zhou, Andrew Park, Elaine Shi, and Wenting Zheng. 2024. PIANO: Extremely Simple, Single-Server PIR with Sublinear Server Computation. In 2024 IEEE Symposium on Security and Privacy (SP). IEEE Computer Society, Los Alamitos, CA, USA, 55--55. https://doi.org/10.1109/SP54263.2024.00055
Index Terms
- Computationally Secure Aggregation and Private Information Retrieval in the Shuffle Model
Recommendations
General constructions for information-theoretic private information retrieval
A Private Information Retrieval (PIR) protocol enables a user to retrieve a data item from a database while hiding the identity of the item being retrieved; specifically, in a t-private k-server PIR protocol the database is replicated among k servers, ...
On the Round Complexity of the Shuffle Model
Theory of CryptographyAbstractThe shuffle model of differential privacy [Bittau et al. SOSP 2017; Erlingsson et al. SODA 2019; Cheu et al. EUROCRYPT 2019] was proposed as a viable model for performing distributed differentially private computations. Informally, the model ...
Secure coprocessor-based private information retrieval without periodical preprocessing
AISC '10: Proceedings of the Eighth Australasian Conference on Information Security - Volume 105Early works on Private Information Retrieval (PIR) focused on minimizing the necessary communication overhead. They seemed to achieve this goal but at the expense of query response time. To mitigate this weakness, protocols with secure coprocessors were ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
December 2024
5188 pages
ISBN:9798400706363
DOI:10.1145/3658644
- General Chairs:
- Bo Luo,
- Xiaojing Liao,
- Jun Xu,
- Program Chairs:
- Engin Kirda,
- David Lie
Copyright © 2024 Owner/Author.
Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for third-party components of this work must be honored. For all other uses, contact the Owner/Author.
Sponsors
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 09 December 2024
Check for updates
Author Tags
Qualifiers
- Research-article
Funding Sources
Conference
CCS '24
Sponsor:
CCS '24: ACM SIGSAC Conference on Computer and Communications Security
October 14 - 18, 2024
UT, Salt Lake City, USA
Acceptance Rates
Overall Acceptance Rate 1,261 of 6,999 submissions, 18%
Upcoming Conference
CCS '25
- Sponsor:
- sigsac
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 4Total Downloads
- Downloads (Last 12 months)4
- Downloads (Last 6 weeks)8
Reflects downloads up to 09 Dec 2024
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in