Welcome to the resource topic for 2019/1340
Title:
Secret Shared Shuffle
Authors: Melissa Chase, Esha Ghosh, Oxana Poburinnaya
Abstract:Generating secret shares of a shuffled dataset - such that neither party knows the order in which it is permuted - is a fundamental building block in many protocols, such as secure collaborative filtering, oblivious sorting, and secure function evaluation on set intersection. Traditional approaches to this problem either involve expensive public-key based crypto or using symmetric crypto on permutation networks. While public-key based solutions are bandwidth efficient, they are computation-bound. On the other hand, permutation network based constructions are communication-bound, especially when the elements are long, for example feature vectors in an ML context. We design a new 2-party protocol for this task of computing secret shares of shuffled data, which we refer to as secret-shared shuffle. Our protocol is secure against static semi-honest adversary. At the heart of our approach is a new method of obtaining two sets of pseudorandom shares which are ``correlated via the permutation’', which can be implemented with low communication using GGM puncturable PRFs. This gives a new protocol for secure shuffle which is concretely more efficient than the existing techniques in the literature. In particular, we are three orders of magnitude faster than public key based approach and one order of magnitude faster compared to the best known symmetric-key cryptography approach based on permutation network when the elements are moderately large.
ePrint: https://eprint.iacr.org/2019/1340
Talk: https://www.youtube.com/watch?v=TiHFU_sRfow
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .