Cryptology ePrint Archive: Report 2019/1340

Secret Shared Shuffle

Melissa Chase and Esha Ghosh and 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.

Category / Keywords: cryptographic protocols / secure shuffle, secure function evaluation, puncturable PRF

Date: received 20 Nov 2019, last revised 20 Nov 2019

Contact author: Esha Ghosh at microsoft com,melissac@microsoft com,oxanapob@bu edu

Available format(s): PDF | BibTeX Citation

Version: 20191122:182511 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]