Paper 2024/547

Efficient Permutation Correlations and Batched Random Access for Two-Party Computation

Stanislav Peceny, Georgia Institute of Technology
Srinivasan Raghuraman, Visa Research & Massachusetts Institute of Technology
Peter Rindal, Visa Research
Harshal Shah, Visa Research
Abstract

In this work we formalize the notion of a two-party permutation correlation (A,B),(C,π) s.t. π(A)=B+C for a random permutation π of n elements and vectors A,B,CFn. This correlation can be viewed as an abstraction and generalization of the Chase et al. (Asiacrypt 2020) share translation protocol. We give a systematization of knowledge for how such a permutation correlation can be derandomized to allow the parties to perform a wide range of oblivious permutations of secret-shared data. This systematization immediately enables the translation of various popular honest-majority protocols to be efficiently instantiated in the two-party setting, e.g. collaborative filtering, sorting, database joins, graph algorithms, and many more. We give two novel protocols for efficiently generating a random permutation correlation. The first uses MPC-friendly PRFs to generate a correlation of elements, each of size bits, with bit-OTs, time, communication, and only three rounds. Similar asymptotics previously required relatively expensive public-key cryptography, e.g. Paillier or LWE. Our protocol implementation for requires just 7 seconds & bits of communication, a respective 40 & improvement on the LWE solution of Juvekar at al. (CCS 2018). The second protocol is based on pseudo-random correlation generators and achieves an overhead that is sublinear in the string length , i.e. the communication and number of OTs is . The overhead of the latter protocol has larger hidden constants, and therefore is more efficient only when long strings are permuted, e.g. in graph algorithms. Finally, we present a suite of highly efficient protocols based on permutations for performing various batched random access operations. These include the ability to extract a hidden subset of a secret-shared list. More generally, we give ORAM-like protocols for obliviously reading and writing from a list in a batched manner. We argue that this suite of batched random access protocols should be a first class primitive in the MPC practitioner's toolbox.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
A minor revision of an IACR publication in PKC 2025
Keywords
PermutationShuffleMPC
Contact author(s)
StanislavPeceny @ gmail com
srini131293 @ gmail com
peterrindal @ gmail com
History
2025-02-10: last of 3 revisions
2024-04-08: received
See all versions
Short URL
https://ia.cr/2024/547
License
Creative Commons Attribution-NonCommercial
CC BY-NC

BibTeX

@misc{cryptoeprint:2024/547,
      author = {Stanislav Peceny and Srinivasan Raghuraman and Peter Rindal and Harshal Shah},
      title = {Efficient Permutation Correlations and Batched Random Access for Two-Party Computation},
      howpublished = {Cryptology {ePrint} Archive, Paper 2024/547},
      year = {2024},
      url = {https://eprint.iacr.org/2024/547}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.