You are looking at a specific version 20191122:182511 of this paper. See the latest version.

Paper 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.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Preprint. MINOR revision.
Keywords
secure shufflesecure function evaluationpuncturable PRF
Contact author(s)
Esha Ghosh @ microsoft com,melissac @ microsoft com,oxanapob @ bu edu
History
2020-10-01: revised
2019-11-22: received
See all versions
Short URL
https://ia.cr/2019/1340
License
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.