Sharded Shuffle Protocol

[eriktaubeneck]

We have currently implemented the following sharded shuffle, performed by 2 out 3 helper parties. It is then repeated by the other two pairwise configuration of the 3 helper parties, so that all 3 are oblivious to one of the shuffles.

Let there be S shards.

1. For each row, select a uniform random value s in [0, S) and send that row to the sth shard.
2. After completing step 1 for all rows, shuffle each shard using an uniform random permutation (e.g., Fisher Yates.)

We need to confirm that this still results a uniform random permutation. Moreover, the size of each shard at each stage is revealed to all helper parties (including the "hidden" 3rd helper party), and we need to confirm that that knowledge doesn't add bias either.

I've attached a draft proof of this, and am seeking feedback on it's validity.

Sharded_Shuffle.pdf

(pdf updated on 2024/3/12)

[eriktaubeneck]

It seems that there is an error with the PDF upload right now on Github, but there is an upload currently available in the W3C slack, in the #patcg-ipa channel.