Original Article Journal Section ABC, a black cat; DEF, doesn’t ever fret;
GHI, goes home immediately. [1]Equally contributing authors. Jaydeep Howlader,
Department, Computer Science and Technology Durgapur, West Bengal, 713209,
India<EMAIL_ADDRESS>No Funding is available

# Multiparty Protocol that Usually Shuffles

Dhaneshwar Mardi  Surbhi Tanwar  Jaydeep Howlader

###### Abstract

Multiparty computation is raising importance because it’s primary objective is
to replace any trusted third party in the distributed computation. This work
presents two multiparty shuffling protocols where each party, possesses a
private input, agrees on a random permutation while keeping the permutation
secret. The proposed shuffling protocols are based on permutation network,
thereby data-oblivious. The first proposal is $n\text{-}permute$ that permutes
$n$ inputs in all $n!$ possible ways. $n$-permute network consists of
$2\log{n}-1$ layers, and in each layer there are $n/2$ gates. Our second
protocol is $n_{\pi}$-permute shuffling that defines a permutation set
$\Pi=\\{\pi_{1},\dots,\pi_{N}\\}$ where $|\Pi|<n!$, and the resultant
shuffling is a random permutation $\pi_{i}\in\Pi$. The $n_{\pi}$-permute
network contains leases number of layers compare to $n$-permute network. Let
$n=n_{1}n_{2}$, the $n_{\pi}$-permute network would define
$2\log{n_{1}}-1+\log{n_{2}}$ layers.

The proposed shuffling protocols are unconditionally secure against malicious
adversary who can corrupt at most $t<n/3$ parties. The probability that
adversary can learn the outcome of $n$-permute is upper bound by
$((n-t)!)^{-1}$. Whereas, the probability that adversary can learn the outcome
of $n_{\pi}$-permute is upper bounded by
$\big{(}f_{\Pi}(n_{1}-\theta_{1})^{n_{2}}2^{\theta_{2}}\big{)}^{-1}$, for some
positive integer $\theta_{1},\theta_{2}$, and a recursive definition of
$f_{\Pi}$. The protocols allow the parties to build quorums, and distribute
the load among the quorums.

###### keywords:

Anonymity, Privacy, Multiparty Computation, Data Oblivious Operation,
Permutation Network

##  1 Introduction

Shuffling is a process that produces a random permutation of an
indistinguishable input sequence. Shuffling is secure if the underlying
permutation remains secret. A multiparty shuffling (MPS) is a protocol where
parties collaboratively execute the shuffling protocol, but no subset of
colluded parties (up to certain threshold) is unable to learn the underlying
permutation. There are generally two variations of MPC. Firstly, each party
possesses a secret input. Secondly, each party possesses the shares of other
secrets. The first setting can easily be plugged into the second setting -
where parties make a secret sharing of their secrets among the other parties.
MPS is one of the primitive operation for many privacy-preserving
applications, like anonymous communication [1, 2], personalized browsing [3],
e-voting and e-auction [4, 5], online gaming [6, 7, 8, 9], private data
outsourcing [10], and oblivious RAM designing [11].

MPS was primarily studied in anonymous communication, known as Mixnet. Chaum
[1] introduced the Mixnet as a network consisting of a chain of servers,
called mixing nodes. Each mixing node receives a batch of encrypted messages
then decrypts (or re-encrypts) individual message, performs a random
permutation, and forwards the batch to the next mixing node. The final output
is unlinkable to the input when at least one of the mixing node’s permutation
remains secret. Shuffling is the composition of permutations along the chain
of the mixing nodes. Shuffling is verifiable [12, 13] if there is a mechanism
to prove the correctness of the output sequence. Mixnet relies on the
cryptographic-primitives, e.g., factorization or computational discrete
logarithm problem. Therefore verifiable Mixnets [14, 15, 16] incur the
additional cost of communication and computation. Moreover, there are some
attacks like - traffic analysis [17, 18], insertion/deletion attack [19],
which have shown some weakness in the unlinkability property.

Chaum [20] also proposed the DCnet111A multiparty protocol based on the Dining
Cryptographers Problem. for anonymous communication. DCnet is free from
cryptographic-primitives and eliminates the problem of traffic analysis. DCnet
is primarily designed with honest parties. DCnet with adversary was addressed
in [21]. Unfortunately, DCnet suffers from collision and jamming attacks [21].

Mixnet and DCnet are asynchronous in nature. This is an advantage as well as
disadvantage of the system. The advantageous part is that - nodes operate
independently. Every mixing node performs three operations: receives,
processes, and forwards. Mixing nodes do not require any communicate with
others during their execution. The mixing node only interacts with its
predecessor and successor. The disadvantage is - failure of any node may
result in the total failure of the system. To withstand the mixing node
failure, Mixnet implements threshold cryptography [22, 23] that generates a
public key for encryption where the corresponding private key is shared among
the parties in a t-n (read t-out of-n) threshold sharing scheme. Any subset of
$t$ parties can perform the Mixnet decryption. Bayer and Diaconis [24]
reported that $\frac{3}{2}\log{n}$ shuffles were sufficient to mix up a deck
of $n$ arranged cards. Bayer-Diaconis’s result intuitively amortizes the upper
bound of the number of mixing nodes in the Mixnet.

MPS is designed as a data-oblivious algorithm where the operations are
independent of the input data. Data-oblivious algorithms are classified into
two categories:

  * •

Network Model: A network model is a fixed wired network of oblivious switches
(alternatively called gates) that transfers the input to the output. Examples
of network models are sorting network [25, 26], permutation networks [29],
etc.

  * •

Randomization Model: Randomization model, on the other hand, hides the data
access pattern of an algorithm by distributing every access instruction (e.g.,
read and write) over the whole memory block. Examples of randomization based
models are ORAM [11], oblivious looked-up table [27], etc.

Most of the MPS protocols are based on the network model [28, 12].

###  1.1 Multiparty Shuffling and Data-Oblivious Algorithm

Let $I=\\{i_{1},\dots,i_{n}\\}$ be the set of inputs taken randomly from a
uniform distribution. For example, cipher-text of any IND-CCA or information-
theoretic encryption. Sorting of $I$ produces a random permutation of the
input. Thus shuffling can be realized by oblivious sorting. Movahedi et al.
[28] proposed an MPS protocol based sorting network [30].

Alternative approach is to route through a permutation network. A network with
$n$-inputs $n$-output is rearrangeable if for all permutation $\pi$ of
$\\{1,\dots,n\\}$, there exist edge disjoint paths to connect any input $i$ to
the output $\pi(i)$. A rearrangeable network consists of configurable switches
of two inputs, called swap-gate. The swap-gate randomly swaps the inputs. A
Beneš network with $n$ inputs is an well-known $(2\log{n}-1)$ layers
rearrangeable network, and able to permute the inputs in all possible $n!$
ways [31, 32]. Some similar types of $2\log{n}$ layers rearrangeable networks
are baseline-baseline-1, omega-omega-1 [33].

###  1.2 Related work

Despite of several applications of MPS, to the best of our knowledge, MPS has
not been explored to a great extent. Laur et al. [34] studied MPS in the
context of database privacy. In [34], three shuffling mechanisms were
proposed:

  1. 1.

For $n$ ordered element $\langle x_{1},\dots,x_{n}\rangle$, parties define a
permutation matrix $M$ such that the sum of the elements along every rows and
column is $1$. Shuffling is computed as $\langle
x_{1},\dots,x_{n}\rangle\times M$

  2. 2.

Sorting $n$ elements obliviously.

  3. 3.

Share the elements to a trusted third party who shuffles and delivers the
elements privately.

The above mechanisms were primarily designed with honest participants. Non-
interactive zero-knowledge proofs [35, 36] were applied to ensure
verifiability and correctness of shuffling.

Movahedi et al. [28] proposed a scalable protocol for MPS. In their protocol,
parties generate random shared-seeds and pair the elements with the shared-
seeds. Let $(r,i)$ be a pair, where $r$ and $i$ are the random-seen and
parties’ input, respectively. The protocol obliviously sorts the pairs
according to the random shared-seeds and thereby obtains a random shuffling.

###  1.3 Our Contribution

In this paper, we propose two MPS protocols based on the rearrangeable
network. We assume that the malicious adversary can corrupt up to $t<n/3$
parties. Our first protocol has $\frac{n}{2}(\log{n}-1)$ layers, and in every
layer, there are $n/2$ swap-gates. In the presence of $t$ corrupted parties,
the adversary can guess the permutation with probability $\frac{1}{(n-t)!}$.
When the number of inputs is large (e.g., $n\geq 2^{8}$), MPS becomes
inefficient. The cost of shuffling is proportional to the number of swap-gates
in the network.

In our second protocol, we reduce the number of layers at the cost of the
number of permutations. Let the number of inputs be $n=n_{1}n_{2}$. We design
$n_{2}$ rearrangeable networks, each with $n_{1}$ inputs, followed by a
Riffle222Riffle is a well-known technique for card shuffling network. In this
design, a malicious adversary who corrupts at most $t$ parties can guess the
permutation with probability
$((n_{1}-\theta_{1})!)^{n_{2}}2^{\theta_{2}})^{-1}$ for some positive
$\theta_{2}$.

We analyze the existing MPS by sorting network [28]. We find that sorting
gates are costlier than the swap-gates used in the rearrangeable network.

Finally, we show that our proposed MPS protocols are unconditionally secure
against $t<n/3$ corrupted parties. The protocols are universally-composable
and scalable with the number of inputs.

##  2 Preliminaries

In the rest of this paper, we use the symbols which are summarized in Table 1.
Furthermore, we define round that comprises all the communications where every
party sends one message to all other parties and performs some local
computation. We assume that parties are synchronous, that is messages do not
have an arbitrary delay.Every party has an identifier (index) which is known
to all. We assume an authenticated-private channel between every pair of
parties.

$\mathbb{F}_{p}$ | Finite field of order $p$, where $p$ is prime.
---|---
$\mathcal{P}=\\{P_{1},\dots,P_{n}\\}$ | A set of $n$ mutually distrustful parties.
$x_{i}\in\mathbb{F}_{p}$ |  $P_{i}$’s secret.
$[x]$ | Secret sharing of $x\in\mathbb{F}_{p}$.
$x_{ij}\in[x_{i}]$ | The $j^{th}$ share of $P_{i}$’s secret. $P_{i}$ privately communicates the share to party $P_{j}$.
Table 1: Notations and their definitions.

###  2.1 Secret sharing

Let $\mathcal{P}$ be a finite set of parties. Let $D\not\in\mathcal{P}$ be a
distinguished party, called dealer, who possesses a secret $x\in X$. A
distribution scheme
$\mathcal{S}=\langle\mathcal{S}_{S},\mathcal{S}_{R}\rangle$ is called $t$-$n$
threshold secret sharing if:

  1. 1.

$\mathcal{S}_{S}:X\times R\rightarrow\mathbb{F}^{n}$ be the sharing function,
where $R$ is a uniform distribution of randomness over some finite field
extension $\mathbb{F}^{t-1}$. The dealer samples ${\bf r}\in R$ uniformly at
random, and shares the secret $x$ according to $\mathcal{S}_{S}(x,{\bf
r})\rightarrow\langle x_{1},\dots,x_{n}\rangle$, where every
$x_{i}\in\mathbb{F}$. Dealer privately communicates the share $x_{i}$ to
player $P_{i}$.

  2. 2.

A set of the authorized party can reconstruct the secret $x$. The size of the
authorized set is parameterized by $t$. Any subset of lesser than $t$ parties
is unable to reconstruct the secret.
$\mathcal{S}_{R}:\mathbb{F}^{t}\rightarrow X$ is the reconstruction function.
The probability of correct reconstruction with the authorized set is
$Pr[\mathcal{S}_{R}(\cdot)=x_{i}]=1$.

###  2.2 Shamir’s Secret Sharing (SSS)

Shamir [37] introduced a $t$-$n$ threshold secret sharing scheme over the
finite field $\mathbb{F}_{p}$. Let $\mathcal{P}$ be the set of parties, and
the dealer possesses a secret $x\in\mathbb{F}_{p}$. Dealer chooses
$a_{0},\dots a_{t-1}\in\mathbb{F}_{p}$ randomly, sets a polynomial
$f(z)=x+\sum_{i=1}^{t-1}a_{i}z^{i}$, and computes the shares as $\langle
f(1),\dots,f(n)\rangle$. Dealer communicates $f(i)$ to party $P_{i}$
privately. The sharing is represented as
$\mathcal{S}_{S}(x,a_{i},\dots,a_{t-1})\rightarrow[x]$, where $x_{i}\in[x]$ is
the $i^{th}$ share and computed as $x_{i}=f(i)$.

As $n$ points on a polynomial of degree $t-1$ have been shared among the
parties, any $t$ points can redefine the polynomial $f(x)$, thereby $x=f(0)$.
The reconstruction function is the interpolation of any $t$ points on the
polynomial, and defines as $x=\sum_{i=1}^{t}\lambda_{i}f(i)$. Here $\lambda$
is the Lagrange Interpolation of $t$ distinct points.

###  2.3 Verifiable secret sharing

In presence of the faulty party, where either the dealer or some party may not
behave honestly, SSS fails to meet the correct output. The notion of
Verifiable Secret Sharing (VSS) was introduced in [38], where the parties can
verify the correctness of their shares that they have received from the
dealer. A secret sharing protocol is verifiable if parties can verify the
following without learning any additional information about the secret.

  * •

The dealer distributes the valid shares.

  * •

During reconstruction, reconstructor receives the correct shares from the
respective parties.

Ben-Or et al. [39] and Chaum et al. [42] proposed the interactive VSS
mechanism for unconditionally secure protocols with at most $t<n/2$ passive
corruption and at most $t<n/3$ active corruption. Further, Rabin and Ben-Or
[41] showed that in the presence of a broadcast channel, the upper bound of
corrupted parties could be $t<n/2$, irrespective of the mode of corruption.

Our construction is based on Ben-Or et al. VSS mechanism [39]. We index the
parties as $P_{1},\dots,P_{n}$. The $i^{th}$ party receives the share as
$f(\omega^{i})$, where $\omega\in\mathbb{F}_{p}$ is the $p^{th}$ root of unity
(i.e., $\omega^{p}=1$), and $n<p$.

###  2.4 Secure multiparty computation

Now we consider $n$ parties $\\{P_{1},\dots,P_{n}\\}$, each of them possesses
a secret $x_{i}$, wants to compute a publicly known function
$F(x_{1},\dots,x_{n})$ on their private inputs in such a way that no party
learns anything about others’ input, and the output is either known to all or
none.

####  2.4.1 Adversary models

The adversary is an entity that corrupts some of the parties to learn private
information. The adversary may be either semi honest or malicious. In a semi-
honest setting, the corrupted parties follow the protocol correctly. However,
the adversary obtains all the internal states and the messages that are
received by the corrupt parties. Semi-honest adversary is often called honest-
but-curious or passive adversary.

On the other hand, malicious adversary controls the corrupted parties. The
adversary determines the inputs of the corrupted parties. Moreover, the
corrupted parties may deviate from the protocol arbitrarily. The only
restriction in both the cases is - adversary cannot learns the randomness of
the corrupted parties, which implies that parties can toss coins
independently, and the outcome of the tosses are private.

An adversary structure is a subset of possible corrupted parties. The
adversary is static if the subset of corrupted parties is chosen prior to the
start of the protocol. On the other hand, the adversary structure is adaptive
when the subset of corrupted parties is dynamic, i.e., the adversary corrupts
the parties during the execution of the protocol.

Depending on the computational capacity, multiparty protocols are classified
into two categories.

  * •

Computationally Bounded or Conditional: Adversary runs in polynomial time, and
is unable to solve certain hardness of the problem (e.g., factorization,
computational DLP problems, etc.)

  * •

Computationally Unbounded or Unconditional: Adversary may not be limited to
polynomial running time. The adversary has unlimited computational power. For
example, given two random elements, $x$ and $y$ form a set, the adversary’s
ability to distinguish the elements is negligible.

SSS is unconditionally secure. Given any $t-1$ shares $\langle
x_{1},\dots,x_{t-1}\rangle\in\mathbb{F}_{p}$ and any random polynomial
function $G(\cdot)$ to compute the secret with, probability that adversary can
compute the secret is $Pr[G(\langle
x_{1},\dots,x_{t-1}\rangle)=x]=\frac{1}{|\mathbb{F}_{p}|}$.

####  2.4.2 Security Definition

A multiparty computation $F(x_{1},\dots,x_{n})=y$ with $n$ parties is a random
mapping of $n$-private inputs $(x_{1},\dots,x_{n})$ to $n$-private outputs
$(y_{1},\dots,y_{n})$, one for each party, such that a reconstruction function
$\mathcal{S}_{R}(y_{1},\dots,y_{n})$ remaps the output to $y$. We refer such a
process as functionality in the $Ideal$ sense. The mapping is defined as
$F:(\\{0,1\\}^{*})^{n}\rightarrow(\\{0,1\\}^{*})^{n}$ where
$F=(f_{1},\dots,f_{n})$ and every $f_{i}$ realizes the functionality of party
$P_{i}$. For every input $X=(x_{1},\dots,x_{n})$, the output is a random
mapping $(f_{1}(x_{1}),\dots,f_{n}(x_{n}))$. Here $x_{i}$ is the private input
of party $P_{i}$.

Let $\Phi$ be a multiparty protocol that realizes functionality $F$. The
$view$ of a party $P_{i}$ during the execution of $\Phi$ on input $X=\langle
x_{1},\dots,x_{n}\rangle$ and security parameter $t$ is denoted as
$view_{i}^{\Phi}(X,t)=(x_{i},r_{i},m^{i}_{1},\dots,m^{i}_{n})$, where $r_{i}$
is the local randomness for party $P_{i}$ and $m^{i}_{j}$ is the message
received by party $P_{i}$ from party $P_{j}$. The output of party $P_{i}$ is
denoted as $output^{\Phi}_{i}(X,t)$. The joint output of all parties is
$output^{\Phi}(X,t)$. All $view$s and their subsequent $output$s are random
variables.

In the MPC, all $output$s are indistinguishable. That is, one cannot
distinguish the $output_{i}$ from the others. We represent the
indistinguishably as

$output^{\Phi}_{1}(X,t)\overset{d}{\equiv}\dots\overset{d}{\equiv}output^{\Phi}_{n}(X,t)\overset{d}{\equiv}output^{\Phi}(X,t)$

######  Definition 2.1.

Security in semi-honest adversary: Let $F=(f_{1},\dots,f_{n})$ be a
functionality and $t$ be the security parameter. The protocol $\Phi$ securely
computes $F$ in the presence of static semi-honest adversary if there exist
Probabilistic Polynomial Time (PPT) simulators $S_{1},\dots S_{n}$ for the
$P_{1},\dots,P_{n}$, respectively such that simulators do not learn any
additional information than the $view$s of the corresponding parties, and the
output of the functionality $F$. We formally denote:

$\\{S_{i}(1^{t},x_{i},f_{i}(x_{i})),F(X)\\}\overset{d}{\equiv}\\{view^{\Phi}_{i}(X,t),output^{\Phi}(X,t)\\}$
(1)

Let $F$ be the functionality, and $A$ be a PPT adversary. An $Ideal$ execution
of the functionality refers to the process where every party handovers his
input to a trusted party, the trusted party computes the functionality $F$,
and returns the $output$ to the corresponding party privately. An $Ideal$
execution of party $P_{i}$ is denoted as $Ideal_{f_{i},A(z)}(X,t)$ where $z$
is the input of the adversary.

A $Real$ execution of the protocol $\Phi$ refers to the process where parties
execute the protocol $\Phi$ by exchanging messages over private channels [39,
42]. A $Real$ execution of party $P_{i}$ is denoted as $Real_{\Phi,A(z)}(X,t)$

######  Definition 2.2.

Security in malicious adversary: Let $F$ be the functionality, $t$ be the
security parameter, and $\Phi$ be the multiparty protocol. The protocol $\Phi$
is securely evaluating the functionality $F$ in the presence of malicious
adversary if, for every $Real$ execution, there exists a PPT simulator $S_{A}$
corresponds to the adversary such that the $Ideal$ process with the simulator
$S_{A}$ is equivalent to any $Real$ execution with the adversary $A$ with the
local randomness $z$.

$\\{Ideal_{f_{i},S_{A}}(X,t)\\}\overset{d}{\equiv}\\{Real_{\Phi,A(z)}(X,t)\\}$
(2)

The simulation models in Equation 1 and 2 provide the security definitions in
the stand-alone paradigm.

####  2.4.3 Universal Composability of Cryptographic protocol

Universal composability (UC) is a general framework to describe and analyze
the security properties of any cryptographic protocol. Protocols are modeled
as a computation to be executed by some computational entities, called parties
who communicate among themselves. Parties run the protocol on their local
inputs and randomness. There is an additional computational entity, called
adversary, who may control a subset of parties their respective communication
channels. However, the adversary can not control the local randomness of
individual parties.

Under the composition paradigm, UC defines the adversary as the Environment,
denoted as $Z$. The Environment generates all the inputs, reads all outputs,
and interacts with the real adversary in an arbitrary way.

######  Definition 2.3.

UC-securely computation: Let $F$ be the functionality, $t$ be the security
parameter, and $\Phi$ be the multiparty protocol. The protocol $\Phi$ is UC-
securely computable if, there does not exist any Environment $Z$ who can
distinguish whether the execution is the $Ideal$ functionality $F$ with the
simulator $S$ or the $Real$ in the presence of adversary $A$.

$Ideal_{F,S_{A}(z)}(X,t)\overset{d}{\equiv}Real_{\Phi,A(z)}(X,t)$ (3)

In the definition, $view$ of the Environment includes all inputs and outputs
of every party, except their randomnesses. The notation $S_{A}(z)$ denotes
whatever the input of the simulator $S$ is known to Environment $Z$ or not.

######  Definition 2.4.

Straight-line Black-box simulator: The simulator is black-box if it only
allows oracle access to the adversary. Such a simulator is straight-line if it
interacts with the adversary in a state-full manner. That is, the simulator
sends all the simulated messages of a round to the adversary and then proceeds
to the next round.

######  Theorem 2.5.

(Kushilevitz et. al [43]) If a protocol is securely computable in the stand-
alone model and has a straight-line black-box simulator, then the protocol is
also UC-securely computable.

####  2.4.4 UC Hybrid model

Now, consider a protocol $\Phi$ that has $\eta$ sub-protocol invocations where
each of the sub-protocol is already proven to be UC-securely computable. The
modular composition theorem [44] allows to analyze the UC-security of the
protocol $\Phi$ from the composability of the sub-protocols. Let
$\\{\Phi_{1},\dots,\Phi_{\eta}\\}$ be the sub-protocols and
$\\{F_{i},\dots,F_{\eta}\\}$ be the functionalities of the sub-protocols,
respectively. The $(\Phi_{1},\dots,\Phi_{\eta})$ hybrid model is defined as
below:

######  Definition 2.6.

Hybrid model: Let $F=\\{F_{1},\dots,F_{\eta}\\}$ be the functionality
corresponds to the protocol $\Phi$ having invocation to
$\\{\Phi_{1},\dots,\Phi_{\eta}\\}$ sub-protocols, $t$ be the security
parameter. Protocol $\Phi$ securely evaluates $F$ if for every $Real$
execution, there exist a PPT simulator $S_{A}$ corresponds to the adversary
such that no Environment $Z$ can distinguish whether the execution is the
$Ideal$ process with the simulator $S_{A}$ or the $Real$ execution of the
adversary $A$. Here $Z$ learns the inputs of all parties and the outputs of
the corrupted parties and interacts with the adversary arbitrarily. We
formally define:

$Ideal_{\Phi,S_{A}(z)}^{F_{1},\dots,F_{\eta}}(X,t)\overset{d}{\equiv}Real_{\Phi,A(z)}(X,t)$
(4)

###  2.5 Multiparty computation on SSS

Let $\mathcal{P}$ be the set of $n$ parties, and $[x],[y]$ be two shared
secrets over the field $\mathbb{F}_{p}$:

  * •

Addition: Parties can compute $[x+y]\leftarrow Add([x],[y])$ locally.

  * •

Multiplication: Parties can compute $[xy]\leftarrow Mul([x],[y])$ with one
round of communication 333Multiplication operation requires at least $2t-1$
parties..

  * •

Constant Multiplication: For a publicly known constant $c\in\mathbb{F}_{p}$,
parties can compute $[cy]\leftarrow Mul(c,[y])$ locally.

Damgård et al. [45] further enhanced the multiparty functionalities as below:

  * •

Random Number Generation: Parties generate a random share as $[r]\leftarrow
Rand()$ with one round of communication.

  * •

Random Bit Generation: Parties generate a random shared bit as $[b]\leftarrow
Rand_{2}()$ where $b\in\\{[0],[1]\\}\subset\mathbb{F}_{p}$ with two rounds of
communication.

  * •

Inverse: Let $[x]$ be a shared secret. Parties compute the inverse
$[x^{-1}]\leftarrow Inv([x])$ with two rounds of communication.

$BITS$ Protocol | Rounds | Invocations of $Mul$
---|---|---
Damgård et al. [45] | $38$ | $O(l)$
Nishide et al. [46] | $25$ | $O(l)$
Veugen [47] | $l+8$ | $O(l)$
$7$† | $O(l)$
Table 2: The round complexity of $BITS$ operation. †Veugen [47] proposed an
efficient $BITS$ operation with pre-computed randomness to reduce the round
complexity.

  * •

Bit Decomposition: Bit decomposition function is a random mapping
$BITS:\mathbb{F}_{p}\rightarrow(\mathbb{F}_{p})^{l}$ where $l=\log{p}$. Let
$[x]$ be a shared secret, then $([b_{l-1}],\dots,[b_{0}])\leftarrow BITS([x])$
such that $x=\sum_{i=0}^{l-1}2^{i}b_{i}$, and $b_{i}\in\\{0,1\\}$. $BITS$ is
the primitive functionality that is used to map any arithmetic circuit to
Boolean circuity. Bit decomposition is a constant round operation. However, it
invokes $O(l)$ $Mul$ operations. Table 2 presents the round complexity of
different bit decomposition protocols.

  * •

Random-swap: Let $([x],[y])$ be an ordered pair of two shared secrets. The
Random-swap function swaps the pair with probability $1/2$. The parties toss a
secret coin, and depending on the output the elements are swapped. Algorithm 1
describes the Random-swap operation.

$Rand_{2}()\rightarrow[b]$;

$Add([x],[y])\rightarrow[z]$;

$Add((Mul([b],[y]),Mul(Add(1-[b]),[x])))\rightarrow[\alpha]$ ;

/* One round */

$Add([z],[-\alpha])\rightarrow[\beta]$ ;

returns $([\alpha],[\beta])$ ;

Algorithm 1 $Random\text{-}swap(\langle[x],[y]\rangle)$

The $Muls$ in algorithm 1 are performed in parallel which incurs one round
operation. Therefore, the complexity of Random-swap is three rounds of
communication - two for $Rand_{2}()$, and one for $Mul$.

  * •

Comparison: Parties compare two shared secrets as $[b]\leftarrow Com([x],[y])$
(if $x>y$ then $b=1$ otherwise $b=0$). Comparison invokes $BITS$ as a sub-
protocol followed by a Boolean circuit of $O(l)$ depth. Therefore, $Com$ is
constant round, but $O(l)$ rounds of $Mul$ operation.

  * •

Reshare: Let $\mathcal{P}_{1}=\\{P_{1},\dots,P_{n1}\\}$ and
$\mathcal{P}_{2}=\\{\bar{P}_{1},\dots,\bar{P}_{n2}\\}$ be two different sets
of parties. Let $[x]$ has been shared among the parties of $\mathcal{P}_{1}$.
Resharing refers to the functionality where parties in $\mathcal{P}_{1}$
construct another distribution $[\bar{x}]$ and privately communicates to the
parties of $\mathcal{P}_{2}$ such that the reconstruction of $[x]$ and
$[\bar{x}]$ by $\mathcal{P}_{1}$ and $\mathcal{P}_{2}$ respectively, are
equal.

/* Let $x_{i}\in[x]$ be the share of $x$ possessed by
$P_{i}\in\mathcal{P}_{1}$ */

$\forall{i}$, $P_{i}\in\mathcal{P}_{1}$ chooses a random polynomial $f_{i}(z)$
of degree $t-1$, such that $f_{i}(0)=x_{i}$, and invokes VSS-shares with
respect to $\mathcal{P}_{2}$; ;

/* let $P_{i}\in\mathcal{P}_{2}$ receives the shares from
$P_{i_{1}},P_{i_{2}},\dots\in\mathcal{P}_{2}$ */

On receiving the shares from $\mathcal{P}_{1}$, each party
$\bar{P}_{j}\in\mathcal{P}_{2}$ computes
$\bar{x}_{j}=\sum_{i=1}^{n}\lambda_{i}f_{i}(x_{j})$

Algorithm 2 $Reshare([x],\mathcal{P}_{1},\mathcal{P}_{2})$

###  2.6 Shuffling by Sorting

In this section we briefly discuss MPS based on sorting network proposed in
[6]. Let $I=(x_{1},\dots,x_{n})$ be the secret inputs of $n$ parties. For
every input $x_{i}\in I$, parties generates a random element $r_{i}\leftarrow
Rand()$ and form the tuple $(r_{i},x_{i})$. Parties then jointly execute a
data-oblivious sorting network on the randomness $r_{1},\dots,r_{n}$, which
intuitively shuffles the sequence.

####  2.6.1 Assumptions and Limitations

Sorting network is comprised of compare and swap gates. Multiparty comparison
is costly, it invokes $BITS$ followed by a Boolean circuit of logarithmic
depth. Therefore, every compare gate incurs $O(\log{p})$ round of complexity
where $\mathbb{F}_{p}$ be the underlying field. As data-oblivious sorting
network typically contains $O(n(\log{n})^{2})$ compare gates, the overall
complexity of a shuffle network is $O(n(\log{n})^{3})$.

In contrast, a permutation network is comprised of Random-swap and does not
require any comparison. The Random-swap gate is computationally efficient that
comparison. In our construction, we define the Random-swap gate with three
rounds of complexity. A permutation network typically contains of
$O(n\log{n})$ Random-swap gates. Therefore, the complexity of permutation is
$O(n\log{n})$.

> For any $16$ ($=\frac{1}{0.0625}$) independent runs of the shuffling
> algorithm [28] with $32$ inputs, there is an overwhelming chance that one
> (or more) run would have at least one repetition in the randomness.

Number of Elements ($n$) | Size of $n$ (bits) | $q=\frac{3}{2}n^{2}\log{n}$ | Size of $q$ (bits) | $P(n,q)$
---|---|---|---|---
$32$ | $5$ | $7680$ | $13$ | $0.0625$
$64$ | $6$ | $36864$ | $16$ | $0.0548$
$128$ | $7$ | $172032$ | $18$ | $0.0461$
$256$ | $8$ | $786432$ | $20$ | $0.0406$
Table 3: Birthday Attack in MPS by sorting protocol [28]

The protocol [28] operates on Compare-swap gates. In the design of the
protocol, comparisons are performed over the field $\mathbb{F}_{q}$, whereas
swapping are performed over another field $\mathbb{F}_{p}$, where $q<p$.
Therefore, the output of every comparison i.e. $[b]\in\mathbb{F}_{q}$ has to
be mapped to an equivalent $[b]\in\mathbb{F}_{p}$, where $b\in\\{0,1\\}$. This
share conversion from one domain to another incurs additional rounds of
communication. As the sorting network is comprised of $O(n(\log{n}^{2})$
Compare-swap gates, and for every gate invokes a share conversion, the overall
round complexity of [28] is higher.

###  2.7 Byzantine agreement and quorum in a large network

In a large network with many parties, the computation often becomes
inefficient due to a large number of inter-party message passing. We often
form quorums and distribute the computation among the quorums. Forming quorums
with the faulty party is not trivial. We refer to the problem of Byzantine
Agreement is presence of malicious adversary. Malicious party can view all the
messages in a round before sending its own message of that round, and is
state-full in the sense that party can remember all previous rounds. In a
nutshell, Byzantine Agreement is a protocol that allows the honest parties to
agree on a common binary string [40]. Byzantine Agreement protocol is used to
form quorums. King et al. [48] and Dani et al. [49] protocols are used to
generate $n$ number of good quorums among $n$ parties.

######  Definition 2.7.

Good Quorum [48, 49]: A $n$ party protocol, called Quorum-Gen, with at most
$t<n/8$ malicious parties forms $n$ quorums each of them having $O(\log{n})$
parties. The quorums are called good if no more than $(t/n+\delta)$ parties in
each quorum are faulty, where $\delta$ is small. Moreover, the quorums are
load-balanced in the sense that no party is mapped to more than $O(\log{n})$
quorums.

###  2.8 Permutation Network

A permutation network (or rearrangeable network) is a non-blocking network of
switches that permutes $n$ inputs to all possible $n!$ ways. The building
block of a permutation network is Random-swap gates. Every Random-swap gate
has two inputs and two outputs. The gate randomly maps the input lines to the
output lines, one to each output. Let $\mathcal{S}$ be a permutation network
with $n$ inputs, and $\pi$ be a random permutation, then there exists some
configuration $\mathcal{C}$ such that the network outputs the permutation
$\pi$. If $(i,j)^{th}$ entry of $\mathcal{C}$ is $1$, then the corresponding
gate swaps the input, otherwise passes the inputs.

######  Definition 2.8.

$n$-permute: A $n$-permute network with $n$-inputs is capable of permuting the
input sequence in all $n!$ possible ways.

No. of Permutations | No. of Occurrences
---|---
8192 | 8
14336 | 16
12288 | 32
2048 | 40
2816 | 64
512 | 128
128 | 256
Table 4: the occurrences of different permutations in a $8$-input Beneš
network. One can read first row as - $8192$ different permutations each occurs
$8$ times.

####  2.8.1 Beneš Network

Beneš network is a $n$-permute network [50]. The dimension $d$ characterizes
the Beneš network. A $d$-dimension Beneš network has $n=2^{d}$ input and
output terminals. The network consists of $K=\frac{n}{2}(2d-1)$ gates arranged
in $2d-1$ layers. Every gate in the network behaves as a Random-swap gate. The
gates are assigned with a random bit $b\in\\{0,1\\}$. The gate swaps the
inputs when the random bit is $1$; otherwise, it passed the inputs. It is easy
to observe that, every gate routes its outputs to the alternate halves of the
network. For example, the first layer virtually divides the network into two
horizontal halves and routes accordingly. The partitioning and routing are
applied recursively on each half. Let $X=(x_{1},\dots,x_{n})$ be the input
sequence. After $d$ layers of routing, an input element $x_{i}\in X$ is
permuted to any position, provided that the adjacent element $x_{i+1}$ (in the
input sequence) is always in the other half of the permuted sequence. To
overrule this constraint, the network performs another $d-1$ layers of
routing. The configuration of the network is captured in a matrix called a
configuration matrix. Figure 1 shows a Beneš network with $8$ input. The
corresponding configuration of the network is shown in Equation 5. It is easy
to observe that for any permutation $\pi$ there exist multiple configurations.
For example, Equation 5 presents two configurations, $\mathcal{C}$ and
$\bar{\mathcal{C}}$, correspond to the $8$ input Beneš network shown in Figure
1.

$\begin{array}[]{ccccccccccccc}&1&1&1&0&0&&&1&1&1&0&0\\\
\mathcal{C}_{\mathcal{S}}=&0&1&0&1&1&&\bar{\mathcal{C}}_{\mathcal{S}}=&0&1&0&1&0\\\
&1&0&1&1&0&&&1&0&0&0&0\\\ &1&1&0&0&0&&&1&1&1&1&1\\\ \end{array}$ (5)

Every gate in Beneš network takes two inputs and swaps the inputs with
probability $1/2$. This implies that the network is able to produce $2^{K}$
possible outputs. Whereas, the total number of permutations with $n$ inputs is
$n!<2^{K}$, for $n>2$. Therefore, the mapping from the set of all possible
configurations $\mathbb{C}=\\{\mathcal{C}_{1},\dots,\mathcal{C}_{2^{K}}\\}$ to
the set of all possible permutation $\Pi=\\{\pi_{1},\dots,\pi_{n!}\\}$ is many
to one. We find that the distribution of occurring the permutations are not
uniform. Table 4 shows the distribution of occurring of different permutations
of an $8$-input Beneš network. The first column of Table 4 represents the
number of permutations that occur by the number depicted in the second column.

####  2.8.2 Arbitrary Size Beneš Network

Beneš network has a limitation. The number of inputs is always a power of $2$.
An arbitrary size Beneš network was introduced by Chang and Melhel [51] and
further optimized in [52]. They proposed a $3$-input swap gate as shown in
Figure 2 (Left). The arbitrary size $n$-permute network is recursively
constructed by forming a $\lceil\frac{n}{2}\rceil$-permute and another
$\lfloor\frac{n}{2}\rfloor$-permute networks. If $n$ is even, then the two
networks are of equal size, otherwise one of the network contains odd number
of inputs. An odd input permute network includes one $3$-input swap gate.
Figure 2 (Right) shows the construction of a $(n+1)$-permute network, where
$n$ is even.

$x_{5}$$x_{7}$$x_{3}$$x_{2}$$x_{4}$$x_{6}$$x_{8}$$x_{1}$$Q_{1}$$Q_{5}$$x_{1}$$x_{2}$$x_{3}$$x_{4}$$x_{5}$$x_{6}$$x_{8}$$x_{7}$$Q_{2}$$Q_{3}$$Q_{4}$$Q_{8}$$Q_{7}$$Q_{6}$$Q_{1}$$Q_{2}$$Q_{3}$$Q_{4}$$Q_{8}$$Q_{7}$$Q_{6}$$Q_{5}$$Q_{1}$$Q_{2}$$Q_{3}$$Q_{4}$

Figure 1: An $8$-input Beneš network and its routing corresponds to the
configuration $\mathcal{C}_{S}$ in Equation 5

$3$-input gate

$m_{\pi}$-permute$x_{1}$$x_{2}$$x_{m}$$x_{m+1}$$x_{m-1}$$d^{th}$layer$3$-input
gate

Figure 2: Left: The construction of a $3$-input swap gate with three $2$-input
swap gates in a cycle. Right: The construction of a $(n+1)$-permute network
with one $3$-input swap gate.

###  2.9 $n_{\pi}$-permute Network

There are two reasons that motivate us to define $n_{\pi}$-permute network.
Firstly, The structure of an arbitrary size Beneš network is asymmetric. A
$3$-permute swap gate is constructed with three $2$-permute swap gates in a
cycle. The design of an asymmetric network using crossbar-switches is
inefficient. Therefore, we propose a $n_{\pi}$-permute network which is almost
symmetric in structure. Secondly, the cost of a permutation network mainly
depends on the size of the network, which is determined by the number of gates
in the network. If the number of inputs is $n$, then there are at most
$\frac{n}{2}(2\log n-1)$ gates in the network. When $n$ is large (say $64\geq
n$), then the cost of permutation is relatively high. In our second
construction, we propose another $n_{\pi}$-permute network that reduces the
cost of the permutation.

The proposed $n_{\pi}$-permute network is a blocking network. That means,
there are some permutations for which no configuration is defined in the
network. Our design goal is not to design all possible permutations, but to
maximize the number of permutations. Furthermore, $n_{\pi}$-permute network is
primarily used for multiparty shuffling and may not be prescribed for
permuting the inputs.

######  Definition 2.9.

$n_{\pi}$-permute: Let $\bar{\Pi}=\\{\pi_{1},\dots,\pi_{k}\\}$ be a subset of
all permutations of $n$ inputs. A $n_{\pi}$-permute network produces the
permutation $\pi_{i}\in\bar{\Pi}$. The number of distinct permutations
generated by $n_{\pi}$-permute network is upper bounded by $k$.

We present two constructions of $n_{\pi}$-permute network. The first
construction is based on arbitrary size Beneš network [51]. We call this
network as symmetric $n_{\pi}$-permute. The second construction reduces the
size of the network. Let $n=n_{1}n_{2}$, then we construct $n_{2}$ number of
$n_{1}$-permute (or $n_{1_{\pi}}$-permute) networks followed by a Riffle
structure that mixes the individual permutations.

####  2.9.1 Symmetric $n_{\pi}$-permute Network

Symmetric $n_{\pi}$-permute network is of even size (i.e. $n$ is even) and
appears to be almost symmetric in structure. We propose a cross-connector that
binds two $n$-permute (or $n_{\pi}$-permute) networks and forms a
$(2n+2)_{\pi}$-permute network. Figure 3 shows the binding technique of two
networks. The green lines randomly draw one element from each upper and lowed
$n$-permute networks and push the elements to gate $G_{2}$. On the other hand,
gate $G_{1}$ pushes two random elements $\alpha$ and $\beta$, where
$\alpha\in\\{x_{1},x_{2}\\}$ and $\beta\in\\{y_{n-1},y_{n}\\}$, to the upper
and lower permute network, respectively. This drawing and pushing operations
occur at the middle of the permute network. The following layers mixes the
elements in such a way that $\alpha$ and $\beta$ always appear at the upper
and lower half of the respective $n$-permute networks. In Figure 3, the blue
gates are used to show all the possible mixing scenarios of $\alpha$ and
$\beta$.

The proposed symmetric $n_{\pi}$-permute network cannot produce all possible
permutations. Consider the Figure 3, it is easy to observe that $\alpha$ and
$\beta$ never reach at gate $\bar{G}_{1}$. Therefore, the final permutation
never contains $\alpha$ and $\beta$ in the middle of the permuted string. re
We estimate the upper bound of the number of permutations produced by the
symmetric $n_{\pi}$-permute network. We consider two equal sized $n$-permute
(or $n_{\pi}$-permute) networks which are connected by a cross-connector. The
total number of inputs becomes $2n+2$. Let $N=2n+2$, we find that all but two
elements, one from $\\{x_{1},x_{2}\\}$ and other from $\\{y_{n-1},y_{n}\\}$,
may permute at the middle of the output string of size $N$. We recursively
define the upper bound as $f_{\Pi}(N)$ as

$\begin{split}f_{\Pi}(N)&=\begin{cases}N!\text{~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}when
$N$ is a power of $2$}\\\
N(N-1)\dots(\frac{N}{2}+1)f_{\Pi}(N/2)\text{~{}~{}~{}~{}when $N=2n$ and $n$ is
even}\\\ 2(N-2)\dots(\frac{N}{2}+1)f_{\Pi}(N/2)\text{~{}~{}~{}~{}~{}when
$N=2n$ and $n$ is odd}\\\ \end{cases}\end{split}$

$x_{2}$$x_{1}$$x_{n}$$x_{n-1}$n-permute networkn-permute
network$\bar{G}$$y_{n-1}$$a_{2}$$y_{2}$$y_{1}$$y_{n}$$a_{1}$$d^{th}$layer$2d-1$layers

$\frac{n}{4}$gates

$\frac{n}{4}$gates

$G$

Figure 3: Two $n$-permute networks are bound using a cross-connector.

####  2.9.2 Reduced $n_{\pi}$-permute Network

In our second construction of $n_{\pi}$-permute network, we represent
$n=n_{1}n_{2}$. We construct $n_{2}$ number of $n$-permute (or
$n_{1_{\pi}}$-permute) networks and Mix the outputs of all
$n_{1_{\pi}}$-permute networks using a Riffle structure. We call this
permutation as reduced $n_{\pi}$-permute network.

$mid\leftarrow\frac{i+j}{2}+1$;

if  _ $d_{2}>1$_ then

$BinaryRiffle(i,mid-1,([x_{i}],\dots,[x_{mid-1}]),d_{2}/2)$;

$BinaryRiffle(mid,j,([x_{mid}],\dots,[x_{j}]),d_{2}/2)$;

for  _$k=0\text{ to }mid-1$_ do

$Random\text{-}swap(([x_{i+k}],[x_{mid+k}]))$;

else

return;

Algorithm 3 $BinaryRiffle(i,j,([x_{i}],\dots,[x_{j}]),d_{2})$

##### Riffle:

This is one of the common technique for card shuffling. The deck of the card
is divided into two halves. The halves are held in each hand and released so
that the cards fall almost interleavely.

We emulate BinaryRiffle to realize the Riffle operation. BinaryRiffle divides
the input sequence into two equal halves. A pair is formed by taking one
element from each half. Subsequently, the elements are swapped randomly. This
operation is recursively applied on each half. Algorithm 3 describes the
process of BinaryRiffle. In general, there would be $\log{n}$ recursions.
However, we tailor the BinaryRiffle and run for $\log{n_{2}}$ recursions.

Figure 4 presents a reduced $n_{\pi}$-permute network with $n=265$ inputs. We
represent $n_{1}=2^{6}$ and $n_{2}=2^{2}$. There are $4$ Beneš structures,
each of having $64$ inputs followed by a BinaryRiffle of having two
recursions.

64-inputBeneš2
layerRiffle$x_{64}$$x_{65}$$x_{128}$$x_{129}$$x_{1}$$x_{192}$$x_{193}$$x_{256}$BenešBenešBenešBenešRandom-
swap

Figure 4: A $256_{\pi}$-permute network. We construct the network with four
$64$-permute structures followed by a BinaryRiffle of depth $2$.

##  3 Multiparty Shuffling Algorithm

Let $\pi:\\{1,\dots,n\\}\rightarrow\\{1,\dots,n\\}$ denotes a permutation, and
$\Pi$ be the subset of all $n!$ permutations. Let $X=(x_{1},\dots,x_{n})$ be
an ordered sequence. Shuffling is a random bijection that maps the sequence
$X$ to another sequence $X_{\pi}=\\{x_{\pi(1)},\dots,x_{\pi(n)}\\}$ where
$\pi\in\Pi$. We denote shuffling as a mapping
$\mathcal{S}:\\{X\\}\overset{\pi}{\rightarrow}\\{X\\}$.

In MPS protocol, there are $n$ parties. Each party $P_{i}$ contains a secret
input $x_{i}$. Parties agree on a random permutation $\pi\in\Pi$ and shuffle
the sequence $X=(x_{1},\dots,x_{n})$ to
$X_{\pi}=(x_{\pi(1)},\dots,x_{\pi(n)})$ in such a way that no party learns the
permutation $\pi$ and the inputs of other parties.

We present two MPS protocols. The first protocol, Shuffle-I, is a $n$-permute
(or symmetric $n_{\pi}$-permute) network. The second protocol, Shuffle-II, is
a reduced $n_{\pi}$-permute network. We apply either Beneš or arbitrary size
Beneš structure to realize the $n$-permute network.

######  Definition 3.1.

$\zeta$-bit Unlinkability: The permutation network ($n$-permute or
$n_{\pi}$-permute), in the presence of an adversary, is $\zeta$-bit unlinkable
if the probability of an adversary to guess the permutation $\pi$ is less than
$\frac{1}{2^{\zeta}}$, where $\zeta$ is the largest positive integer.

Input : Sequence of $n$ elements, $X=(x_{1},\dots,x_{n})$

Output : A random permutation, $X_{\pi}$

begin

Preprocessing:

Parties agree on a $n$-input or symmetric $n_{\pi}$-permute network. Let the
network be $\mathcal{S}$ and public to all;

Parties execute Quorum-Gen, and form $n$ quorums
$\mathbb{Q}=\\{Q_{1},\dots,Q_{n}\\}$. Each gate $G_{i}\in\mathcal{S}$ is
assigned some quorum $Q_{i}$, where $i\equiv j\mod{n}$. Thus $G_{1}$ is
assigned to $Q_{1}$, $G_{2}$ is assigned to $Q_{2}$, etc. As there are more
gates than the number of quorums, some quorums are associated with multiple
gates. Figure 1 shows the assignment of the quorums of an $8$-permute Beneš
network;

Every $Q_{i=1,\dots,n/2}$ receives two shared-secrets: $[x_{i}]$ from party
$P_{2i-1}$ and $[y_{i}]$ from parties $P_{2i}$, respectively;

Gate Operation:

At layer-1, the quorums invoke  $([\alpha_{i}],[\beta_{i}])\leftarrow
Random\text{-}swap([x_{i}],[y_{i}])\text{~{}~{}~{}~{}for $i=1,\dots,n/2$}$

Thus, the output-lines of gate $G_{i}$, (for $i=1,\dots,n/2$), contains the
ordered pair $([\alpha_{i}],[\beta_{i}])$;

Resharing:

The output-lines of layer-1 are now forwarded to layer-2. Quorums at layer-1
reshare the outputs to the quorums at layer-2;

If $Q_{i}$ forwards the outputs to $Q_{k}^{1}$ and $Q_{k}^{2}$, respectively,
then the parties in $Q_{i}$ reshares $[\alpha_{i}]$ to $Q_{k}^{1}$, and
$[\beta_{i}]$ to $Q_{k}^{2}$. For example $Q_{1}$ reshares $[\alpha_{1}]$ to
$Q_{\frac{n}{2}+1}$ and $[\beta_{i}]$ to $Q_{\frac{n}{2}+\frac{n}{4}+1}$;

Routing:

Routing is performed layer by layer. In each layer, the quorums operate
synchronously and forward the outputs to the next layer. On receiving the
inputs from the preceding layer, quorums perform the gate operations and
forward to the next layer;

Algorithm 4 Shuffle-I

A MPS protocol, with adversary who can corrupt at most $t$ parties, should
satisfy the following properties:

  * •

$\zeta$-bit unlinkability: For a security parameter $t$, the protocol must
satisfy $\zeta$-bit unlinkability.

  * •

Uniformly Knowing: The corrupted party cannot stop the honest party to learn
the output. We call this all-or-nothing where every party learns the
permutation, or no party learns anything.

######  Definition 3.2.

A MPS protocol with $t<n/3$ corrupted parties is $t$-resistant, if the
protocol guaranteed $\zeta$-bit unlinkability, and uniformly knowing
properties.

###  3.1 Shuffle-I

Our first protocol is a $n$-permute (or symmetric $n_{\pi}$-permute)
shuffling. General, a rearrangeable non-blocking permutation network can be
used for shuffling. In our design, we use either a Beneš or an arbitrary size
Beneš or a symmetric $n_{\pi}$-permute network. The gates are replaced by
Random-swap gates. algorithm 4 describes the MPS protocol.

####  3.1.1 Shuffle-I with passive adversary

Following we present the properties of Shuffle-I protocol.

$\zeta$-bit Unlinkability: Shuffle-I generates all $n!$ permutations. We
consider a passive adversary who can corrupt $t$ parties and learns their
inputs. Therefore, the adversary can link those $t$ elements at the output,
where the remaining $n-t$ elements are permuted in $f_{\Pi}(n-t)$ possible
ways. Therefore, the probability that the adversary can guess the permutation
correctly is $\frac{1}{f_{\Pi}(n-t)}$. Consequently, Shuffle-I defines the
security parameter $\zeta=\lfloor\log{(f_{\Pi}(n-t))}\rfloor$.

Uniformly Knowing: Shuffle-I basically runs on the $n$-permute or symmetric
$n_{\pi}$-permute structure. The permutation $\pi$ progresses as the inputs
progress layer by layer. The gates of the structure are assigned to some
quorum. In a particular layer, the quorums operate synchronously. Thus, if any
quorum fails to deliver to the next layer, then the permutation is aborted.
The final output is obtained when the inputs pass through all the layers of
the network, otherwise aborts. Therefore, Shuffle-I guarantees all-or-nothing.

###  3.2 Shuffle-II

The second protocol is based on reduced $n_{\pi}$-permute shuffling. The
protocol is shown in algorithm 5. When the number of inputs is large (say
$2^{8}\geq n$), shuffling often becomes inefficient. In that case, we propose
a reduction in the number of layers of the network. Let the number of inputs
be $n$. We represent $n$ as a product of two numbers, say $n=n_{1}n_{2}$. We
form $n_{2}$ independent Shuffle-I structures, each with $n_{1}$ inputs.
Finally, the outputs of all the Shuffle-I are mixed using BinaryRiffle.

Input : A sequence of $n$ elements $X=(x_{1},\dots,x_{n})$

Output : A random permutation $X_{\pi}$

begin

Preprocessing:

Parties invoke Quorum-Gen, and form $n$ quorums
$\mathbb{Q}=\\{Q_{1},\dots,Q_{n}\\}$;

Parties agree on $n=n_{1}n_{2}$ and defines $n_{2}$ Shuffle-I networks, each
of having $n_{1}$ inputs. Parties further agree on a BinaryRiffle of
$\log{n_{2}}$ layers. Let the network be $\mathcal{S}^{\Pi}$, and is public;

Every gate $G\in\mathcal{S}^{\pi}$ is assigned to some quorum $Q_{i}$;

Shuffling in Two Phases:

/* Shuffling is performed in two phases */

Phase-I

For every subsequence of $n_{1}$, say $(x_{1},\dots,x_{n_{1}})$
$(x_{n_{1}+1},\dots,x_{2n_{1}})$ $\dots$, $(x_{(n_{2}-1)n_{1}}\dots
n_{n_{1}n_{2}})$, parties invoke Shuffle-I independently on each subsequence.
Thus Phase-I produces $n_{2}$ independent shuffles each with $n_{1}$ distinct
elements;

Phase-II:

Phase-II is a BinaryRiffle with $\log{n_{2}}$ layers. The outputs of Shuffle-I
are mixed using the Riffle;

Routing:

Routing is performed layer by layer. In each layer, the quorums operate
synchronously, and forward the output to the next layer. On receiving the
inputs from the preceding layer, quorums performs the gate operation;

Algorithm 5 Shuffle-II

####  3.2.1 Shuffle-II with the passive adversary

Following, we present the properties of shuffle-II protocol.

$\zeta$-bit Unlinkability: A Shuffle-II structure is consisting of two blocks.
The first block is Shuffle-I structure and the second block is the
BinaryRiffle. Let there are $n_{2}$ Shuffle-I structures, each of them having
$n_{1}$ inputs. We also assume that adversary knows $t$ inputs, and those $t$
elements are uniformly distributed over the input sequence. Without loss of
generality, we consider that every sub-sequence of $n_{1}$ elements at input
there are $t/n_{2}$ elements whose values are known to the adversary.
Therefore, in every Shuffle-I there are $t/n_{2}$ elements at the output which
are linkable, and the remaining $(n_{1}-t/n_{2})$ elements are permuted in
$f_{\Pi}(n_{1}-t/n_{2})$ possible ways. As there are $n_{2}$ Shuffle-I
structures and all the Shuffle-I structure operates concurrently on different
inputs set, the unknown elements are permuted in
$(f_{\Pi}(n_{1}-t/n_{2})^{n_{2}}$ possible ways.

The second block is the BinaryRiffle. A $n$-input Riffle is constructed with
$n/2$ Random-swap gates and is capable to produce $2^{\frac{n}{2}}$
permutations. In our construction the output of the first block is fed to the
BinaryRiffle structure. Figure 1 shows a reduced $256_{\pi}$-permute network
with $4$ numbers of $64$-permute networks in the first block and a
BinaryRiffle of depth $2$ at the second block.

Now the input to a BinaryRiffle is a sequence of $n$ elements where $t$
elements are linkable. Let the structure has $d_{2}=\log{n_{2}}$ layers. All
the layers, except the last, independently permutes the sequence in
$2^{\frac{n}{2}}$ possible ways. As $t$ elements are linkable, the last layer
permutes the sequence in $2^{\frac{n-t}{2}}$ possible ways. Therefore, a
BinaryRiffle with $d_{2}$ layers permutes the input in $2^{(d_{2}n-t)/2}$
possible ways.

Finally, a reduced $n_{\pi}$-permute with $t$ linkable inputs, is capable of
permuting the input sequence in
$(f_{\Pi}(n_{1}-t/n_{2}))^{n_{2}}2^{(d_{2}n-t)/2}$ possible ways. Thus the
probability of an adversary to guess the permutation is
$\frac{1}{(f_{\Pi}(n_{1}-t/n_{2})^{n_{2}}2^{(d_{2}n-t)/2}}$. Consequently,
Shuffle-II defines the security parameter
$\zeta=\lfloor\log{(f_{Pi}(n_{1}-t/n_{2})^{n_{2}}2^{(d_{2}n-t)/2}}\rfloor$.

(number of inputs, number of corruptions) | Shuffle-I | Shuffle-II
---|---|---
| $\zeta$ |  $\zeta$ (when $n_{1}=64$, $n_{2}=2$)
$n=128$, $t=42$ | $433$ | $413$
| $\zeta$ |  $\zeta$ (when $n_{1}=64$, $n_{2}=4$)
$n=256$, $t=85$ | $1026$ | $908$
|  |  $\zeta$ (when $n_{1}=128$, $n_{2}=2$)
|  | $944$
| $\zeta$ |  $\zeta$ (when $n_{1}=64$, $n_{2}=8$)
$n=512$, $t=170$ | $2319$ | $2074$
|  |  $\zeta$ (when $n_{1}=128$, $n_{2}=4$)
|  | $2146$
|  |  $\zeta$ (when $n_{1}=256$, $n_{2}=2$)
|  | $2224$
Table 5: Caption

Table 5 shows the estimation of $\zeta$ for both Shuffle-I and Shuffle-II. We
consider that $\lfloor n/3\rfloor$ players are corrupted. We measure the
$\zeta$-bit unlinkability for $n=128,256$, and $512$. In each of the cases, we
design the reduced $n_{\pi}$-permute with $n_{2}=2,4$, and $8$ input Beneš
networks where each Beneš network consists of $n_{1}=64,128,255$ inputs,
respectively. It is easy to observe that $\zeta$-bit unlinkability property of
Shuffle-I does not vary significantly from Shuffle-II.

Uniformly Knowing: This property of Shuffle-II directly follows from the
protocol Shuffle-I.

##  4 UC-securely Computability

In this section we present the UC-security proofs of the two protocols:
Shuffle-I and Shuffle-II. Before proceed, we consider the following:

  1. 1.

The adversary structure is static. However, adversary may be semi-honest or
malicious.

  2. 2.

The adversary is computationally unbounded. However, the simulator that
corresponds to the adversary is probabilistic polynomially bounded.

  3. 3.

Environment $Z$ acts as an interactive Turing machine. The interactive Turing
machine has additional tapes which receive inputs during the execution of the
Turing machine. This model basically simulates the real-life operation of the
protocol, where the inputs are not known during the instantiation of the
simulation. The interactive Turing machine models the straight-line black-box
behavior of the simulator (see Theorem 2.5).

  4. 4.

Let $\mathcal{P}_{C}\subset\mathcal{P}$ be a static subset of corrupted
parties. Adversary is $\mathcal{P}_{C}$-limited if he can only corrupt the
parties from the set $\mathcal{P}_{C}$. As the adversary structure is static,
$\mathcal{P}_{C}$ is fixed and defined before the execution of the protocol.
We set the cardinality of $\mathcal{P}_{C}$ equal to the security parameter of
the protocol, i.e. $|\mathcal{P}_{C}|=t$.

  5. 5.

Finally, we assume that Quorum-Gen has already formed $n$ quorums. For every
gate $G_{j}$, let $Q_{i}$ be the associated quorum, where $i\equiv j\mod{n}$.
We also assume that $Q_{C_{i}}\subset Q_{i}$ be the set of corrupted parties
in quorum $Q_{i}$.

###  4.1 UC modeling of Shuffle-I and Shuffle-II

We model the protocols using modular composability model and prove the UC-
security of the protocols. Here we define the $Ideal$ functionality correspond
to the sub-protocols used in Shuffle-I and Shuffle-II. Table 6 presents the
list of sub-protocols, their dependencies, and the $Ideal$ functionalities.

Protocol | Ideal Functionality
---|---
VSS-share [39] | $\quad F_{VSS\text{-}share}$
VSS-recons[39] | $\quad F_{VSS\text{-}recons}$
Reshare [53] | $\quad F_{Reshare}$
Mul [39, 45] | $\quad F_{Mul}$
$Rand_{2}$ [45] | $\quad F_{Rand_{2}}$
Random-swap | $\quad F_{RS}$

Shuffle-IMul$Rand_{2}$Random-swapBinaryRiffleShuffle-IIVSS-reconsVSS-share

Table 6: The sub-protocols and their $Ideal$ functionalities. The dependencies
of the sub-protocols are depicted depicts the invocation of sub-protocols.

The security proofs of VSS-share, VSS-recons, Mul, $Rand_{2}$, and Reshare
protocols (using straight-line black-box simulator) were presented in [54, 45,
53]. We apply UC-hybrid model to prove the security of Random-swap and
BinaryRiffle. Subsequently, we show that Shuffle-I and Shuffle-II are also UC-
secure.

begin

/* Let $Q_{i}$ be the quorum associated with the gate $G_{j}$. */

Trusted party receives input
$(a_{1},b_{1}),\dots(a_{n},b_{n})\in(\mathbb{F}_{p})^{2}$ from
$P_{1},\dots,P_{n}\in Q_{i}$ respectively;

if  _$P_{i}$ does not send the input_ then

set $(a_{i},b_{i})\leftarrow(0,0)$;

Trusted party tosses an unbiased coin and generates the randomness. Let
$r\in\\{0,1\\}$ be the tossed value;

Trusted party computes  $a\leftarrow
F_{VSS\text{-}recon}(a_{1},\dots,a_{n})\text{ and }b\leftarrow
F_{VSS\text{-}recon}(b_{1},\dots,b_{n})$

if  _$(r==1)$_ then

Trusted party invokes $(F_{VSS\text{-}share}(b),~{}F_{VSS\text{-}share}(a))$;

else

Trusted party invokes $(F_{VSS\text{-}share}(a),~{}F_{VSS\text{-}share}(b))$;

Algorithm 6 Functionality $F_{RS}$

####  4.1.1 Protocol Random-swap:

The $Ideal$ functionality of Random-swap is given in algorithm 6. The $Ideal$
function receives inputs from the parties, tosses a coin, swaps the inputs
based on the toss, and invokes VSS-shares. Since VSS-share generates uniform
and random shares of the input, the $view$s of the parties are independent and
random.

begin

/* Let $Q_{i}$ be the quorum associated with the gate $G_{j}$. */

/* $\mathcal{P}_{C_{i}}\subset Q_{i}$ be the set of corrupted parties. */

/* $I_{i}=Q_{i}-\mathcal{P}_{C_{i}}$ be the set of honest parties. */

Simulation

for  _every party $P_{i}\in I_{i}$_ do

$S_{RS}$ selects random $(x_{i},y_{i})$;

$S_{RS}$ writes $(P_{i},(x_{i},y_{i}))$ on the tape of $Z$;

for  _every party $P_{i}\in\mathcal{P}_{C_{i}}$_ do

$S_{RS}$ obtains the input $(x_{i},y_{i})$ of party $P_{i}$, and passes the
input to $A$;

if  _$A$ corrupts $P_{i}$_ then

$S_{RS}$ receives $(\bar{x}_{i},\bar{y}_{i})$ from $A$;

$S_{RS}$ writes $(P_{i},(\bar{x}_{i},\bar{y}_{i}))$ on the tape of $Z$;

else

$S_{RS}$ writes $(P_{i},(x_{i},y_{i}))$ on the tape of $Z$;

for  _all $Q_{i}$, i$=1,\dots,n/2$_ do

$S_{RS}$ invokes $[r]\leftarrow F^{i}_{Rand_{2}}()$ with respect to $Q_{i}$;

for  _all $Q_{i}$, $i=1\dots,n/2$_ do

$S_{RS}$ computes:

$\qquad[z_{i}]\leftarrow Add([x],[y])$; // Addition is a local computation

$\qquad[\bar{a}]\leftarrow
Add((F^{i}_{Mul}([x],[r]),F^{i}_{Mul}(Add(1-[r]),[y])))$;

$\qquad[\bar{b}]\leftarrow Add([z],[-\bar{a}])$;

$S_{RS}$ adds $(\bar{a}_{i},\bar{b}_{i})$ to the $output_{i}$ of party $P_{i}$
and writes $(P_{i},(\bar{a}_{i},\bar{b}_{i}))$ on the tape of $Z$;

Algorithm 7 Environment $Z$, with Adversary $A$ and Simulator $S_{RS}$

The composability of Random-swap in the $F_{Mul}$ and $F_{Rand_{2}}$-hybrid
model is similar to the protocol in algorithm 1, except that every call to the
real protocol Mul or $Rand_{2}$ is replaced by the call to the $Ideal$
functionalities $F_{Mul}$ or $F_{Rand_{2}}$, respectively. The simulation is
given in algorithm 7. Let $A$ be the adversary for protocol Random-swap. $A$
interacts with $n$ parties and accesses to $n/2$ copies of the $Ideal$
functionalities $F_{Rand_{2}}$ and $F_{Mul}$. Given $A$, the simulator
$S_{RS}$ simulates the real execution of the protocol Random-swap for $A$ as
follows:

  1. 1.

Let $Q_{i}$ be the quorum. Let $\mathcal{P}_{C_{i}}\subset Q_{i}$ be the set
of corrupted parties.

  2. 2.

For every gate $G_{i}$, $i=1,\dots,n/2$, there are $n/2$ copies of $Ideal$
functionalities $F^{i}_{Rand_{2}}$, and $F^{i}_{Mul}$ corresponds to the
parties $P_{i}$.

If $A$ corrupts a party $P_{j}\in\mathcal{P}_{C_{i}}$ in some quorum $Q_{i}$,
then $S_{RS}$ obtains the input $(x_{i},y_{i})$ from $P_{j}$ and passes the
inputs to $A$. If $A$ instructs to corrupt the inputs, then $S_{RS}$ receives
$(\bar{x}_{i},\bar{y}_{i})$ from $A$ manipulates the input of $P_{j}$. On the
other hand, if $A$ does not corrupt $P_{j}$, then $S_{RS}$ randomly sets the
input of $P_{j}$. Simulator $S_{RS}$ writes all inputs on the tape of $Z$.

For every quorum, $S_{RS}$ simulates the copy of the $Ideal$ functionalities
$F^{i}_{Rand_{2}}$ and $F^{i}_{Mul}$ with their inputs. The output of the
$Ideal$ functionalities are written on the tape of $Z$.

Simulation of Mul and $Rand_{2}$ in the $F_{VSS\text{-}share}$-hybrid modeling
are secure [54, 45]. Both the protocols have calls to the $Ideal$
functionality of $F_{VSS\text{-}share}$, which generates uniform and random
shares over $\mathbb{F}_{p}$. Simulator writes every inputs and output on the
tape of $Z$. As the outputs are random variables over the field
$\mathbb{F}_{p}$, $Z$ is unable to distinguish - who writes on the tape? Is it
the $Ideal$ functionality or the simulator?

begin

/* Let the network has $n=2^{d}$ inputs. Then there are $\frac{n}{2}(2d-1)$
Random-swap gates in the network. The input lines of the network are assigned
to the gates labeled as $G_{1},G_{2},\dots,G_{n/2}$. */

Network setup:

for  _$i=1,\dots,n/2$_ do

Parties $P_{2i-1}$ and $P_{2i}$ VSS-share their secret to quorum $Q_{i}$;

if  _Party $P_{2i-1}$ (or $P_{2i}$) does not shares the secret_ then

Set the secret as $0$

Routing:

for  _every layers_ do

for  _every quorum $Q_{i}$_ do

Trusted party receives $([x_{i}],[y_{i}])$ from $Q_{i}$;

Trusted party invokes $F_{RS}$;

For first output line, trusted party invokes $F_{VSS\text{-}share}$ to quorum
$Q_{k}^{1}$;

For second output line, trusted party invokes $F_{VSS\text{-}share}$ to quorum
$Q_{k}^{2}$;

Algorithm 8 Functionality $F_{S\text{-}I}$

####  4.1.2 Protocol Shuffle-I:

There are $n$ parties. The parties already form $n$ quorums where no party is
in more than $O(\log{n})$ quorums [48]. There exists a $n$-permute (or
symmetric $n$-permute) structure with $n$ inputs. The structure contains at
most $\frac{n}{2}(2\log{n}-1)$ gates which are arranged in $(2\log{n}-1)$
layers. Each gate $G_{j}$ is assigned to some quorum $Q_{i}$, where $i\equiv
j\mod{n}$. The first layer contains $n/2$ gates, and are indexed as
$G_{1},\dots,G_{n/2}$. The corresponding quorums are $Q_{1},\dots,Q_{n/2}$,
respectively. The gate $G_{i}$ (for $i=1,\dots,n/2$) receives the inputs from
$P_{2i-1}$ (first input line) and $P_{2i}$ (second input line). Thus,
$P_{2i-1}$ and $P_{2i}$ VSS-share their secrets to the parties $P_{j}\in
Q_{i}$. In the subsequent layers, the gates receive inputs from the preceding
layer. Let gate $G_{i}$ delivers its first output line to the gate $G_{k}$ and
second output line to $G_{\frac{n}{2}+k}$. Also, let for $Q_{\bar{k}}$ and
$Q_{\bar{\frac{n}{2}+k}}$ be the corresponding quorums associate to $G_{k}$
and $G_{\frac{n}{2}+k}$, respectively. Every party $P_{j}\in Q_{i}$ VSS-shares
the outputs to quorums $Q_{\bar{k}}$ (first output line) and
$G_{\frac{n}{2}+k}$ (second output line), respectively.

The $Ideal$ functionality of Shuffle-I is shown in algorithm 8. The
functionality is defined in two phases: the network setup phase and the
routing phase. The network setup phase receives the input from the parties,
and the routing phase shuffles the input by traveling thorough the network. In
every layer, the output of the gates are VSS-shared to the next layer. Since
VSS-share produces random shares of the secret, all the outputs are random and
uniformly distributed over $\mathbb{F}_{p}$.

Let $A$ be the adversary who can corrupts $t<n/2$ parties. We assume that
Quorum-Gen produces good quorums where the majority of the parties in each
quorum are honest. $A$ interacts with $n$ parties which are executing the
protocol Shuffle-I with access to multiple copies of the $Ideal$ functionality
$F_{RS}$. Given $A$, simulator $S_{S\text{-}I}$ simulates the real execution
of protocol Shuffle-I for the adversary $A$ as follows:

  1. 1.

Simulator $S_{S\text{-}I}$ executes the structure layer-by-layer. In each
layer, the quorums operate synchronously. If some quorum fails to deliver
within a fixed time, the protocol is aborted.

  2. 2.

Let $Q_{i}$ be a quorum. The quorum may contain some corrupt parties. Let
$\mathcal{P}_{i}\subset Q_{i}$ be the subset of corrupted parties in $Q_{i}$.
We consider that $|\mathcal{P}_{i}|<\frac{|Q_{i}|}{2}$.

  3. 3.

For $i=1,\dots,n/2$, there are $n/2$ copies of $Ideal$ functionalities
$F^{i}_{RS}$ correspond to quorum $Q_{i}$ in each layer.

For every gate of the first layer, simulator $S_{S\text{-}I}$ obtains the
input from party $P_{2i-1}$ and $P_{2i}$. Since $G_{i}$ is assigned to quorum
$Q_{i}$, the parties do the following:

  * •

If $P_{i}\in Q_{i}$ is a corrupted player, then the simulator obtains the
input $(x_{i},y_{i})$ from $P_{i}$ and passes the input $(x_{i}.y_{i})$ to
$A$. If $A$ instructs to corrupt the input to $(\bar{x}_{i},\bar{y}_{i})$,
then simulator sets the input as $(x_{i},y_{i})=(\bar{x}_{i},\bar{y})$.

  * •

Simulator writes $(P_{i},(x_{i},y_{i}))$ on the tape of $Z$.

  * •

If $P_{i}\in Q_{i}$ is not corrupted, then the simulator randomly sets the
input as $(x_{i},y_{i})$, and writes $(P_{i},(x_{i},y_{i}))$ on the tape of
$Z$.

The composability of Shuffle-I in $F_{S\text{-}I}$-hybrid model is similar to
the protocol in algorithm 4, except that every call to the real protocol
Random-swap is replaced with the call to the Ideal functionalities $F_{RS}$.
The simulation is given in algorithm 9. Simulator $S_{S\text{-}I}$ writes
every $views$ of the parties on the tape of the environment. Since $F_{RS}$
outputs random variables over the field $\mathbb{F}_{p}$, the environment is
unable to distinguish - who writes on the tape? Is it the Ideal functionality
or the simulator?

begin

Network setup:

for  _Party $P_{j}\in\mathcal{P}$_ do

if  _$P_{j}\in\mathcal{P}_{C}$_ then

$S_{S\text{-}I}$ obtains the secret $x_{j}$ of $P_{j}$ and passes to $A$;

if  _$A$ corrupts $P_{j}$_ then

$A$ corrupts the secret of $P_{j}$ as $\bar{x}_{j}$ and $S_{S\text{-}I}$
resets $x_{j}=\bar{x}_{j}$.

else

$S_{S\text{-}I}$ randomly sets the input $x_{j}$ for party $P_{j}$;

for  _all $i=1,\dots,n/2$_ do

$S_{S\text{-}I}$ calls $F_{VSS\text{-}share}^{i}$ with respect to the quorum
$Q_{i}$;

Simulation:

for  _every layer_ do

for  _every $P_{j}\in Q_{i}$_ do

if  _$P_{j}\in\mathcal{P}_{C}$_ then

$S_{S\text{-}I}$ obtains the input $(x_{j},y_{j})$ from $P_{j}$ and passes the
input to $A$.

if  _$A$ corrupts $P_{j}$_ then

$A$ corrupts the input as $(\bar{x}_{j},\bar{y}_{j})$ and $S_{S\text{-}I}$
resets $P_{j}$’s secret as $(x_{j},y_{j})=(\bar{x}_{j},\bar{y}_{j})$.

$S_{S\text{-}I}$ writes $(P_{j},(x_{j},y_{j}))$ on the tape of $Z$.

$S_{S\text{-}I}$ randomly sets the input as $(x_{j},y_{j})$ for $P_{j}$ and
writes $(P_{j},(x_{j},y_{j}))$ on the tape of $Z$.

for  _all $i=1,\dots,n/2$_ do

$S_{S\text{-}I}$ calls $F_{RS}^{j}$ /* This is a concurrent operation. */

if  _not the last layer_ then

if  _$P_{j}\in\mathcal{P}_{C}$ and $A$ corrupts $P_{j}$_ then

$S_{S\text{-}I}$ obtains the $output_{j}$ of $P_{j}$ from $A$.

$Q_{k}^{1}$ and $Q_{k}^{2}$, respectively /* This is a concurrent operation.
*/

Algorithm 9 Environment $Z$, with Adversary $A$ and Simulator $S_{S\text{-}I}$

####  4.1.3 Protocol BinaryRiffle and Shuffle-II:

The two protocols BinaryRiffle and Shuffle-II are similar to Shuffle-I except
the underlying structure.

######  Lemma 4.1.

BinaryRiffle and Shuffle-II are UC-securely computable.

######  Proof 4.2.

Shuffle-I is UC-secure under the straight-line black-box simulation. The
simulator $S_{S\text{-}I}$ is independent of the underline structure
(network). If the underline structure is replaced by BinaryRiffle then it
provides the UC-security of the simulator $S_{BR}$. Similarly, the UC-security
of Shuffle-II is obtained.

###  4.2 Why Permutation Network?

The prior MPS protocols ( e.g. [28, 12, 34]) are based on sorting network. The
commonly used sorting networks are having $O((\log{n})^{2})$ layers [26].
Ajtai et al. proposed an $O(\log{n})$ layer sorting network for large number
of inputs [55]. However, their protocol requires large number of inputs.
Donald E. Knuth commented in [56] that -

> The networks they constructed are not for practical interest, since many
> components were introduced just to save a factor of $\log{n}$; Batcher’s
> method is much better, unless $n$ exceeds the total memory capacity of all
> computers on earth!

Later on Leighton et al. proposed an $O(\log{n})$ layers network that usually
sorted the input sequence with high probability. Their protocol [30] is based
on the butterfly tournament protocol. Nevertheless, the protocol [30] defines
a sorting network with $7.44\log{n}$ layers.

A $n$-permute network produces a random permutation of the input sequence.
$n$-permute networks (e.g. [50, 31, 29]) are having $O(\log{n})$ layers. Our
implementation is based on Beneš network that has $2\log{n}-1$ layers.
Therefore, $n$-permute networks are more suitable than the sorting networks.
However, $n$-permute network does not produce uniform distribution of
permutations. That is, some of the permutations are more likely that the
others. For example, Table 4 shows the distribution of $8$-permute network. We
find that, for all possible configurations the mean of occurring a permutation
is $26.0063$ and the standard deviation is $1.622$.

##  5 Conclusion

In this paper, we have presented two MPS protocols. The protocols are based on
permutation networks. The first MPS protocol emulates the Beneš network. We
generalize the Beneš structure for any even number of inputs and design a
multiparty protocol to shuffle the inputs. We find that when the number of
inputs is large, say greater than $2^{8}$, shuffling becomes inefficient. Our
second MPS protocol is designed for large number of inputs. We propose a
$n_{\pi}$-permute network to reduce the number of layers of the network.
However, $n_{\pi}$-permute network produces less than $n!$ permutations.

The building block of the shuffling protocol is Random-swap gate. We design a
multipaty Random-swap gate that swaps the inputs with probability
$\frac{1}{2}$, without learning the inputs. Moreover, an observer can not
distinguish whether the inputs are swapped or passed through. Each gate is
operated by a quorum of parties. We consider that at most $1/3$ of the parties
may be corrupted.

Instead of sorting network, we use permutation network for shuffling. Unlike
the Compare-swap gate in sorting network, the permutation network uses Random-
swap gates. We find that Random-swap gate is more efficient than Compare-swap.
There are three rounds of communication in the Random-swap gate, whereas
Compare-swap incurs $O(\log{p})$ rounds of communications where $p$ is the
size of the underlying field.

## References

  * [1] Chaum D: Untraceable Electronic Mail, Return Addresses, and Digital Pseudonyms, Commun. ACM, Volume 24, 84–90, 1981
  * [2] Smith L., Umbanhowar P., Ottino J. and Lueptow, R.: Optimized Mixing by Cutting-and-Shuffling, SIAM Journal on Applied Dynamical Systems, Volume 17(4), 2544–2573, 2018
  * [3] Gabber E., Gibbons P. B., Matias Y, Mayer A. J.: How to Make Personalized Web Browising Simple, Secure, and Anonymous, Financial Cryptography, FC’97, 1997, LNCS 1318,17–32, Springer
  * [4] Neff, C. A. : A Verifiable Secret Shuffle and Its Application to e-Voting, 8th ACM Conference on Computer and Communications Security, 2001, CCS’01, 116–125, ACM
  * [5] Juang W-S, Liaw H-T, Lin P-C, Lin C-K: The Design of a Secure and Fair Sealed-bid Auction Service, Math. Comput. Model., 2005, Volume 41(8-9), 973–985
  * [6] Goodrich M. T., Mitzenmacher M: Anonymous Card Shuffling and its Applications to Parallel Mixnets, CoRR, 2012, Volume abs/1205.1579, 1–14, http://arxiv.org/abs/1205.1579
  * [7] Goldwasser S., and Micali S: Probabilistic Encryption & Amp; How to Play Mental Poker Keeping Secret All Partial Information, 14th Annual ACM Symposium on Theory of Computing, 1982, STOC ’82, 365–377, ACM,
  * [8] Shamr A, Rivest R. L., Adleman L. M. : Chapter: Mental Poker, The Mathematical Gardner, 37–43, 1981, Springer
  * [9] Zuylen A., Schalekamp F. : The Achilles’ hell of the GSR-shuffle: A note on new age solitaire, Probability in the Engineering and Information Science, 2004, Volume 18(3), 315–328
  * [10] Zhang Z., Wang K., Lin W., Fu A. W-C, Wong R. C-W : Repeatable Oblivious Shuffling of Large Outsourced Data Blocks, Cryptology ePrint Archive, Report 2019/071, 2019, https://eprint.iacr.org/2019/071
  * [11] Damgård I., Meldgaard S., Nielsen J. B. : Perfectly Secure Oblivious RAM Without Random Oracles, 8th Conference on Theory of Cryptography, TCC’11, 2011, LNCS 6597, 144–163, Springer
  * [12] Adida B. Wikström D. :How to Shuffle in Public, 4th Conference on Theory of Cryptography, TCC ’07, 2007, LNCS 4393, 555–574, Springer
  * [13] Abe M. : Universally verifiable mix-net with verification work independent of the number of mix-servers, Advances in Cryptology - EUROCRYPT’98, 1998, LNCS 1403, 437-447, Springer
  * [14] Jacobsson M. : A Practical Mix, Advances in Cryptology - EUROCRYPT’98, 1998, LNCS 1403, 448–461, Springer
  * [15] Jacobsson M., Juels A., Revesr R. L. : Making Mix Nets Robust for Electronic Voting by Randomized Partial Checking, 11th USENIX Security Symposium, 2002, 339–353, USENIX Association
  * [16] Golle P., Jakobsson M, Juels A. Syverson P. : Universal Re-encryption for Mixnets, Topics in Cryptology - CT-RSA ’04, 2004, LNCS 2964, 163-178, Springer
  * [17] Shirazi F. Simeonovski M, Asghar M. R., Backes M., Diaz C. : A Survey on Routing in Anonymous Communication Protocols, ACM Comput. Surv., 2018, Volume 51, 51:1–51:39
  * [18] Raymond J-F : Traffic Analysis: Protocols, Attacks, Design Issues, and Open Problems, International Workshop on Designing Privacy Enhancing Technologies: Design Issues in Anonymity and Unobservability, 2001, LNCS 2009, 10–29, Springer
  * [19] Dingledine R., Freedman J. M., Hopwood D., Molnar D. :A Reputation System to Increase MIX-Net Reliability, Information Hiding, IH’01, 2001, LNCS 2137, 126–141, Springer
  * [20] Chaum D. : The Dining Cryptographers Problem: Unconditional Sender and Recipient Untraceability, Journal of Cryptology, 1988, Volume 1(1), 65–75, 1988, Springer
  * [21] Golle P., Juels A. : Dining Cryptographers Revisited, Advances in Cryptology - EUROCRYPT ’04, 2004, LNCS 3027, 456–473, Springer
  * [22] Katz J., Yung M. : Threshold Cryptosystems Based on Factoring, Advances in Cryptology - ASIACRYPT ’02, 2002, LNCS 2501, 192–205,Springer
  * [23] Gennaro R., Jarecki S., Krawczyk H. Rabin T. : Secure Distributed Key Generation for Discrete-log Based Cryptosystems, EUROCRYPT’99, 1999, LNCS 1592, 295–310, Springer
  * [24] Bayer D., Diaconis P. : Trailing the Dovetail Shuffle to its Lair, The Annals of Applied Probability, 1992, Volume 2(2), 294–313,The Institute of Mathematical Statistics
  * [25] Batcher K. E. : Means for merging data, 1969, US Patent 3,428,946
  * [26] Batcher K. E. : Sorting Networks and Their Applications, Spring Joint Computer Conference, AFIPS ’68, 1968, 307–314, ACM
  * [27] Launchbury J., Diatchki I. S., DuBuisson T. Adams-Moran A. : Efficient Lookup-table Protocol in Secure Multiparty Computation, ACM SIGPLAN Notice, Volume 47(9), 2012, ACM
  * [28] Movahedi M., Saia J., Zamani M. : Secure Multi-party Shuffling, 22nd International Colloquium on Structural Information and Communication Complexity, SIROCCO’15, 2015, LNCS 9439, 459–473, Springer
  * [29] Clos C. : A study of non-blocking switching networks, The Bell System Technical Journal, Volume 32(2), 406–424, 1952
  * [30] Leighton F. T., Plaxton C. G. : A (fairly) Simple Circuit that (usually) Sorts, 31st Annual Symposium on Foundations of Computer Science, 264–274, IEEE Computer Society, 1990
  * [31] Waksman A. : A Permutation Network, Journal of the ACM, Volume 15(1), 1968, 159–163, ACM
  * [32] Lee K. Y. : A New Benes Network Control Algorithm, IEEE Trans. Comput., Volume 36(6), 1987, IEEE Computer Society
  * [33] Yeh Y-M, Feng T-y: On a Class of Rearrangeable Networks, IEEE Trans. Comput., Volume 41(11), 1992, 1361–1379,IEEE Computer Society
  * [34] Laur S., Willemson J., Zhang B. : Round-efficient Oblivious Database Manipulation, 14th International Conference on Information Security, ISC’11, 2011, LNCS 7001, 262–277, Springer
  * [35] Pedersen T. P. : Non-Interactive and Information-Theoretic Secure Verifiable Secret Sharing, 11th Annual International Cryptology Conference on Advances in Cryptology, CRYPTO ’91, 1992, LNCS 576, 129–140, Springer
  * [36] Feldman P. : A Practical Scheme for Non-interactive Verifiable Secret Sharing, 28th Annual Symposium on Foundations of Computer Science, 1987, SFCS ’87, 427–438, IEEE Computer Society
  * [37] Shamir A. : How to Share a Secret, Commun. ACM, 1979, Volume 22(11), ACM
  * [38] Chor B., Goldwasser S., Micali S., Awerbuch B. : Verifiable Secret Sharing and Achieving Simultaneity in the Presence of Faults, 26th Annual Symposium on Foundations of Computer Science, SFCS ’85, 1985, 383–395, IEEE Computer Society
  * [39] Ben-Or M., Goldwasser S., Wigderson A. : Completeness Theorems for Non-cryptographic Fault-tolerant Distributed Computation, 20th Annual ACM Symposium on Theory of Computing, 1988, STOC ’88, 1–10, ACM
  * [40] Ben-Or M., Pavlov E., Vaikuntanathan V. : Byzantine Agreement in the Full-information Model in O(Log N) Rounds, 38th Annual ACM Symposium on Theory of Computing, 2006, STOC ’06, 179–186, ACM
  * [41] Rabin T., Ben-Or M. : Verifiable Secret Sharing and Multiparty Protocols with Honest Majority, 21st Annual ACM Symposium on Theory of Computing, STOC ’89, 1989, 73–85, ACM
  * [42] Chaum D., Crépeau C., Damgård I. : Multiparty Unconditionally Secure Protocols, 20th Annual ACM Symposium on Theory of Computing, STOC ’88, 1988, 11–19, ACM
  * [43] Eyal K., Yehuda L., Tal R. : Information-Theoretically Secure Protocols and Security under Composition, SIAM J. Comput., Volume 39(5), 2090–2112, 2010
  * [44] Ran C. : Security and Composition of Multiparty Cryptographic Protocols, J. Cryptology, Volume 13(1), 143–202, 2000
  * [45] Damgård I., Fitzi M., Kiltz E., Nielsen J. B., Toft T. : Unconditionally Secure Constant-rounds Multi-party Computation for Equality, Comparison, Bits and Exponentiation, 3rd Conference on Theory of Cryptography - TCC’06, 2006, LNCS 3876, 285–304, Springer
  * [46] Nishide T., Ohta K. : Multiparty Computation for Interval, Equality, and Comparison Without Bit-decomposition Protocol, 10th International Conference on Practice and Theory in Public-key Cryptography, PKC’07, 2007, LNCS 4450, 343–360, Springer
  * [47] Veugen T., Blom F., Hoog S. J. A. de, Erkin Z. : Secure Comparison Protocols in the Semi-Honest Model, IEEE Journal of Selected Topics in Signal Processing, 2015, Volume 9(7), 1217-1228 bitembday1 William K., D. M. Bloom : The American Mathematical Monthly, (10), 1141–1142, Mathematical Association of America, E2386, Volume 80(10), 1973
  * [48] King V., Lonargan S., Saia J., Trehan A. : Load Balanced Scalable Byzantine Agreement Through Quorum Building, with Full Information, 12th International Conference on Distributed Computing and Networking, ICDCN’11, 2011, 203–214, Springer
  * [49] Dani V., Kin g V., Movahedi M., Saia J. : Quorums Quicken Queries: Efficient Asynchronous Secure Multiparty Computation, 15th International Conference on Distributed Computing and Networking, ICDCN’14, 242–256, Springer
  * [50] Beneš V. E. : Optimal Rearrangeable Multistage Connecting Networks, Bell System Technical Journal, Volume 43(4), 1641–1656, 1964
  * [51] Chang C., Melhem G. R. : Arbitrary Size Benes Networks, Parallel Processing Letters, Volume 7(3),279–284, 1997
  * [52] Soo W. H., Samsudin A., Goh A. : Efficient Mental Card Shuffling via Optimised Arbitrary-Sized Benes Permutation Network, 5th International Conference Information Security, 446–458, 2002, LNCS 2433, Springer
  * [53] Mahnush M., Jared S., Mahdi Z : Secure Multi-Party Shuffling, IACR Cryptology ePrint Archive, Volume 2015, 664,http://eprint.iacr.org/2015/664
  * [54] Gilad A., Yehuda L. : A Full Proof of the BGW Protocol for Perfectly Secure Multiparty Computation, J. Cryptology, Volume 30(1), 58–151, 2017, Springer
  * [55] Ajtai M., Komlós J., Szemerédi E. : An $O(NLogN)$ Sorting Network, 15th Annual ACM Symposium on Theory of Computing, 1983, STOC ’83, 1–9, ACM
  * [56] Knuth D. E. : The Art of Computer Programming, Volume 3: (2Nd Ed.) Sorting and Searching, Addison Wesley Longman Publishing Co., Inc., 1998