Scholarlink

In this work we formalize the notion of a two-party permutation correlation \((A, B), (C, \pi )\) s.t. \(\pi (A)=B+C\) for a random permutation \(\pi \) of n elements and vectors \(A,B,C\in \mathbb {F}^n\) . 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 n elements, each of size \(\ell =\log |\mathbb {F}|\) bits, with \(O(n\ell )\) bit-OTs, time, communication, and only 3 rounds including setup. Similar asymptotics previously required relatively expensive public-key cryptography, e.g. Paillier or LWE. Our protocol implementation for \(n=2^{20},\ell =128\) requires just 7 s & \(\sim 2\ell n\) bits of communication, a respective 40 & \(1.1\times \) 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 \(\ell \) , i.e. the communication and number of OTs is \(O(n\log \ell )\) . 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.(The authors grant IACR a non-exclusive and irrevocable license to distribute the article under the https://creativecommons.org/licenses/by-nc/3.0/ .)

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

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

  • 会议论文

  • 发表日期：

    2025年

查看全文
  • Stanislav Peceny,
  • Srinivasan Raghuraman,
  • Peter Rindal,
  • Harshal Shah

摘要

In this work we formalize the notion of a two-party permutation correlation \((A, B), (C, \pi )\) s.t. \(\pi (A)=B+C\) for a random permutation \(\pi \) of n elements and vectors \(A,B,C\in \mathbb {F}^n\) . 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 n elements, each of size \(\ell =\log |\mathbb {F}|\) bits, with \(O(n\ell )\) bit-OTs, time, communication, and only 3 rounds including setup. Similar asymptotics previously required relatively expensive public-key cryptography, e.g. Paillier or LWE. Our protocol implementation for \(n=2^{20},\ell =128\) requires just 7 s & \(\sim 2\ell n\) bits of communication, a respective 40 & \(1.1\times \) 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 \(\ell \) , i.e. the communication and number of OTs is \(O(n\log \ell )\) . 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.(The authors grant IACR a non-exclusive and irrevocable license to distribute the article under the https://creativecommons.org/licenses/by-nc/3.0/ .)