Paper 2024/870

Computationally Secure Aggregation and Private Information Retrieval in the Shuffle Model

Adrià Gascón, Google (United States)
Yuval Ishai, Technion – Israel Institute of Technology
Mahimna Kelkar, Cornell University
Baiyu Li, Google (United States)
Yiping Ma, University of Pennsylvania
Mariana Raykova, Google (United States)

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 $9\times$-$25\times$ 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.

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. Minor revision. ACM CCS 2024
shuffle modelprivate information retrievalsecure aggregationsparse LPNsyndrome decodingvariable-size records
Contact author(s)
adriag @ google com
yuval ishai @ gmail com
mahimna @ cs cornell edu
baiyuli @ google com
yipingma @ seas upenn edu
marianar @ google com
2024-06-05: approved
2024-06-01: received
See all versions
Short URL
Creative Commons Attribution


      author = {Adrià Gascón and Yuval Ishai and Mahimna Kelkar and Baiyu Li and Yiping Ma and Mariana Raykova},
      title = {Computationally Secure Aggregation and Private Information Retrieval in the Shuffle Model},
      howpublished = {Cryptology ePrint Archive, Paper 2024/870},
      year = {2024},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.