Efficient protocol to give out N known items randomly to k>=3 parties without independent bodies

Question

There are $N$ items which are to be uniformly randomly distributed (every possibility has equal probability) to $k\geq 3$ parties, such that no individual party can change the probability of getting certain items.

Party $0\leq i<k$ would receive $N_i$ items, such that the sum of all $N_i$ is $N$.

No party would want any other party to know any more things than their own $N_i$ items.

The only form of communication possible is a broadcast to all other parties.

You can assume an upper limit on the amount of computation possible during the protocol.

Question: Is there a method to give the $N$ items to the $k$ parties such that:

1. The probability of any party finding out another party's information is less than any chosen positive amount.
2. The method terminates in finitely many steps with probability 1.

I am particularly interested in alternative solutions which requires less computation (time) on average than my answer presented below.

Answer 1

Consider the following protocol to find the sum of secret integers among $k$ parties:

Pairs of parties use RSA or any other communication protocol to set up a secure channel of information. In the exchange, they declare a number $x$ such that the first party subtracts $x$ from their secret integer, and the second party adds $x$ to their secret integer.

When the following is satisfied:

1. Each party has communicated with at least 2 parties.
2. The graph formed by vertices being parties and edges being communications is biconnected. It is sufficient to make a cycle graph.

If every pair of parties communicated, then any communication between any pair of parties would not get any more information than them sharing which cards they have.

The parties announce their modified numbers, and the sum can be calculated by summing the modified numbers. This step takes $O(k)$ (or $O(k^2)$ for the other version) time.

---

Consider the following protocol to generate random numbers:

Each party generates a random bitstring of a certain and commits to it (by salting and hashing). All parties reveal their bitstring and the xor of all the bitstring is taken to be used for random numbers. This takes $O(k|bitstring|)$ time.

---

The main protocol is:

1. Each party $i$ chooses $N_i$ random integers in the range $(0, N^2)$ and commits to them. The parties would try to find the order of their random integers (number of other random integers chosen by all the parties which are less than it). We also have to detect when two parties choose the same integer.
2. For each integer $x$ from $0$ to $N^2$, each party is supposed to find the number of integers they have less than $x$, summing all the secret integers would give the order of $x$. If the order of $x$ and $x+1$ differs by more than $1$, rinse and repeat. As there are $O(N^2)$ numbers, this step takes finitely many steps with probability 1. This takes $O(N^2k)$ time.
3. Now, each party knows the order of their random integers, and the set of orders of the random integers is from $[0, N)$. We map the orders to the $N$ items by selecting an order and using the random number protocol to to generate enough bits to select a random item from the remaining items. This step takes finitely many steps with probability 1, and is expected to take $O(N \log N)$ bits, hence taking $O(kN \log N)$ time.
4. To prove that a party owns the item, the party has to reveal the random integer used for that item, and since it was committed in advance, other parties can check it.

---

Example: With $N=k=3$, the $N$ items being $A, B, C$, $N_0=N_1=N_2=1$, parties $0, 1, 2$ select the numbers $5, 2, 7$ respectively among $(0, 9)$.

Using the secret summing method, they get the orders (which we denote as $\text{ord}$) of the integers:

$\text{ord}(0) = 0$

$\text{ord}(1) = 0$

$\text{ord}(2) = 0$

$\text{ord}(3) = 1$

$\text{ord}(4) = 1$

$\text{ord}(5) = 1$

$\text{ord}(6) = 2$

$\text{ord}(7) = 2$

$\text{ord}(8) = 3$

$\text{ord}(9) = 3$

It is easy to check that there are no two randomly selected numbers that are the same.

Using the random number generator, the parties decide that the order of $0$ maps to $C$, $1$ maps to $A$ and $2$ maps to $B$.

Hence, party $0$ gets $A$ as $1=\text{ord}(5)$ maps to it.

Party $1$ gets $C$ as $0=\text{ord}(2)$ maps to it.

Party $2$ gets $B$ as $2=\text{ord}(7)$ maps to it.