# Secure and Scalable Circuit-based Protocol for Multi-Party Private Set
Intersection

Jiuheng Su  East China Normal University
Shanghai, China
<EMAIL_ADDRESS>Zhili Chen  East China Normal University
Shanghai, China
<EMAIL_ADDRESS>
###### Abstract

We propose a novel protocol for computing a circuit which implements the
multi-party private set intersection functionality (PSI). Circuit-based
approach has advantages over using custom protocols to achieve this task,
since many applications of PSI do not require the computation of the
intersection itself, but rather specific functional computations over the
items in the intersection.

Our protocol represents the pioneering circuit-based multi-party PSI protocol,
which builds upon and optimizes the two-party SCS [9] protocol. By using
secure computation between two parties, our protocol sidesteps the
complexities associated with multi-party interactions and demonstrates good
scalability.

In order to mitigate the high overhead associated with circuit-based
constructions, we have further enhanced our protocol by utilizing simple
hashing scheme and permutation-based hash functions. These tricks have enabled
us to minimize circuit size by employing bucketing techniques while
simultaneously attaining noteworthy reductions in both computation and
communication expenses.

††publicationid: pubid:  Network and Distributed System Security (NDSS)
Symposium 2024 26 February - 1 March 2024, San Diego, CA, USA ISBN
1-891562-93-2 https://dx.doi.org/10.14722/ndss.2024.23xxx www.ndss-
symposium.org

##  I Introduction

Two-party Private Set Intersection (PSI) enables two parties, denoted as
$P_{1}$ and $P_{2}$ with respective input sets $X$ and $Y$, to compute the
intersection $I=X\cap Y$ without revealing any other information about the
items outside the intersection. Currently, there are numerous constructions of
protocols for computing two-party PSI with concretely efficient and secure
implementations. The problem of multi-party PSI (mPSI) naturally extends the
concept of two-party PSI, i.e. $n$ parties collaborate to securely compute the
intersection of their private input sets $S_{1},S_{2},...,S_{n}$ while
ensuring the confidentiality of all other information.

Secure protocols for computing PSI, applicable to both two-party and multi-
party scenarios, can be broadly categorized into two classes. The first
category encompasses constructions specifically designed to address the PSI
problem, yielding highly efficient protocols tailored to this particular task.
On the other hand, the second category involves the utilization of generic
secure multi-party computation (MPC) techniques, employing circuit
representations of the desired functionality. This allows for the integration
of PSI protocols into larger, composite secure computations. In this study,
our focus is primarily directed towards the latter category of protocol
constructions. These constructions offer the advantage of maintaining the
secrecy of the intersection itself from the participating parties, while
securely evaluating a symmetric function $f(S_{1}\cap S_{2}\cap...\cap
S_{n})$, which could include operations such as set intersection sum or
cardinality computation. For clarity, the functionality $F_{mPSI,f}$ is
formally depicted in Figure 1.

|  Parameters $P_{1}$ and $P_{2}$ are the two sides for computing the boolean
---
circuit $C$. $f$ is any symmetric function.
Input: $P_{i}$ inputs set $S_{i}$, $i\in\\{1,...,n\\}$.
Output: The functionality computes the circuit C on the parties’ input
sets and returns the output $f(S_{1}\cap S_{2}\cap...\cap S_{n})$ to the
parties.

Figure 1: Functionality $F_{mPSI,f}$

In the context of two-party circuit-based PSI, we suppose that each party
possesses an input set containing $n$ items. A most naive circuit requires
$O(n^{2})$ pairwise comparisons between the items. However, optimizations have
been proposed by leveraging local computation capabilities of the parties. For
instance, in the work of [9], several two-party circuit-based PSI protocols
were introduced. For small universes, the parties can represent their input
sets as bit-vectors and compute the intersection using bit-wise AND operations
(referred to as the Bit-Wise And (BWA) protocol). On the other hand, for
larger universes, [9] presented the Sort-Compare-Shuffle (SCS) design. This
design involves local sorting of the respective sets by each party, followed
by the computation of the sorted list of the union of the two sets using the
bitonic sorting network. Consequently, items in the intersection will appear
twice adjacently in the sorted list, allowing for the identification of the
intersection by comparing adjacent items. To preserve privacy, the sorted
result of the intersection is then shuffled using a Waksman permutation
network, effectively concealing the positional information of the items. The
overall circuit computation requires only $O(n\log n)$ comparisons, primarily
stemming from the initial stage of merge sort. The two-party circuit-based PSI
protocols proposed by [9] serve as the foundation for our research. In fact,
the two-party circuit-based PSI protocols proposed by [9] is the starting
point of our work.

###  I-A Overview of our Protocol

Our protocols are built upon the foundation of the two-party circuit-based PSI
protocols proposed by [9]. One notable difference is that, in order to
overcome the challenges of complex interactions and scalability in the multi-
party setting, our protocol adopts a generic two-party secure computation
protocol. As a result, prior to conducting circuit computations, the private
inputs of the parties need to be securely distributed between the two parties
engaged in the secure computation process. These two parties then reconstruct
the items and perform secure computation of multi-party PSI (mPSI) within the
circuit. The construction of our protocols uses generic secure multi-party
computation (MPC) protocols, such as Yao’s garbled-circuit protocol and the
GMW protocol, to evaluate boolean circuits that compute the desired
functionality. By relying on these established MPC protocols, which possess
proven security properties, we can focus on designing circuits that
effectively implement the desired functionality. In our study, we consider the
multi-party setting involving $m$ parties denoted as $P_{1},...,P_{m}$. Each
party possesses an input set consisting of $n$ items, which are represented
using $\sigma$ bits.

In our first protocol, namely multi-party Bitwise-AND (mBWA), the input sets
are represented as bit-vectors of length $2^{\sigma}$. The protocol
incorporates a secret sharing scheme, where each party securely distributes
their respective bit-vectors to two designated parties, denoted as $P_{1}$ and
$P_{2}$. Subsequently, $P_{1}$ and $P_{2}$ reconstruct the bit-vectors within
the circuit, enabling the computation of the intersection by performing bit-
wise AND operations on the corresponding bit-vectors.

It is important to highlight that the practical applicability of this protocol
is limited to scenarios involving smaller universes. The exponential growth of
AND gates within the circuit imposes constraints on its scalability when
dealing with larger datasets.

Our second protocol, multi-party Sort-Compare-Shuffle (mSCS), follows the
Sort-Compare-Shuffle (SCS) paradigm while extending it to the multi-party
setting. In this protocol, each party independently performs a local sorting
operation on their respective input sets. The sorted sets are then distributed
among the designated parties, $P_{1}$ and $P_{2}$, ensuring that the order of
the secret shares aligns with the order of the items in the sorted sets.

Upon distribution, $P_{1}$ and $P_{2}$ reconstruct the sets within the circuit
and merge them securely using a $k$-bitonic sorting network based on the
$k$-Bitonic sort algorithm [7]. The intersection of the sets can be
subsequently determined by identifying the elements that occur $m$ times
consecutively in the merged list. This identification process involves
comparing adjacent elements. Finally, before revealing the sorted
intersection, a shuffling procedure is applied to conceal the positional
information of the items, thus preserving privacy and confidentiality.

Our research is also motivated by the work presented in [13], which introduced
a method for comparing items mapped to each bin. In light of this, we propose
a novel approach that employs simple hashing scheme for each party to
distribute their elements into distinct bins. This approach aims to reduce
communication overhead by utilizing multi-party circuit-based PSI protocols to
compare the elements within each bin. Through our exploration, we have
discovered substantial advantages in employing individual instances of the
aforementioned protocol within each bin, as opposed to directly utilizing a
single, large circuit for computation. These advantages extend beyond the
realm of communication overhead and also encompass the facilitation of
parallel computation. By leveraging this approach, our protocols exhibit
improved efficiency and scalability, making them well-suited for practical
deployment in multi-party settings.

###  I-B Motivation for multi-party Circuit PSI

####  I-B1 Circuit

Currently, the predominant focus of research efforts lies in addressing the
PSI problem itself, which aims to reveal the intersection to the involved
parties. These protocols have demonstrated high levels of efficiency, even
achieving linear communication costs. However, in many practical applications,
PSI functions as a module, and it is crucial to maintain the privacy of the
intersection. In fact, these PSI applications often require the ability to
compute any function based on the intersection.

Moreover, modifying or altering a custom MPC protocol has been shown to be
prohibitively expensive and sometimes even infeasible. In contrast, generic
MPC protocols offer greater flexibility in supporting additional computations
through circuit expansion. They can leverage existing code bases and software
packages, allowing users to focus on circuit design rather than developing an
entirely new protocol. Clearly, the latter option is more challenging.

####  I-B2 Multi-party

The multi-party PSI problem constitutes a more general case of the two-party
PSI problem and presents greater potential in the context of massive data
sharing. The multi-party scenario is better suited for various applications,
such as identifying a target audience for an advertising campaign that
involves several companies sharing data on their common users. It should be
noted that generic Multi-Party Computation (MPC) protocols tend to be
computationally expensive in the multi-party setting. Consequently, there
exists a research gap in the context of multi-party circuit-based PSI.
Nevertheless, as discussed earlier, there is significant motivation to address
this gap and develop efficient solutions in this context.

###  I-C Related Work

The problem of PSI has always been a hot issue in the field of MPC. We focus
on the discussion of the state-of-the-art of semi-honest PSI protocols and
simply classify previous works into two-party PSI and multi-party PSI.

####  I-C1 Two-party PSI

The earliest Private Set Intersection protocols were built upon public-key
cryptography, specifically relying on the Diffie-Hellman assumptions, which
can be traced back to the 1980s [19]. Subsequently, more efficient PSI
protocols were developed based on oblivious transfer (OT) extension, which
require minimal public-key cryptography computation and can be efficiently
instantiated with symmetric key cryptography. Circuit-based PSI protocols use
generic MPC protocols to perform the necessary computations.

A basic PSI circuit computes $O(n^{2})$ element comparisons, resulting in
$O(\sigma n^{2})$ gates, where $\sigma$ represents the bit-length of the
elements. The number of comparisons performed by the circuit is a crucial
factor that impacts the overhead, as it directly affects the communication
volume in the protocol. The Sort-Compare-Shuffle (SCS) PSI circuit introduced
by [9] reduces the number of element comparisons to $O(n\log n)$. The Circuit-
Phasing PSI protocol proposed by [13] hashes input items into $O(n)$ bins
using Cuckoo hashing and simple hashing, enabling independent operations on
each bin. Each bin typically contains at most $O(\log n/\log\log n)$ elements.
Consequently, the Circuit-Phasing PSI circuit computes $O(n\log n/\log\log n)$
comparisons.

The first circuit-based PSI protocol to achieve linear communication
complexity is presented in [14]. This protocol relies on the use of oblivious
programmable pseudo-random functions (OPPRF). Parties need to evaluate a
circuit per bin to compare the programmed value with the output of the OPRF.
As a result, this circuit only needs to compute one single comparison per bin.

####  I-C2 Multi-party PSI

The first multi-party PSI protocol was introduced by [6], which utilized
oblivious polynomial evaluation (OPE) techniques like additively homomorphic
encryption. Subsequent works by [10, 17, 4] focused on optimizing the
computation and communication overhead of these protocols. The mPSI protocol
proposed in [11] was the first implementation of multi-party PSI and
introduced a novel primitive called Oblivious Programmable Pseudo-Random
Functions (OPPRF). This protocol successfully avoids computationally expensive
public-key operations.

To the best of our knowledge, the exploration of multi-party circuit-based PSI
remains largely unexplored in the existing literature.

###  I-D Our Contributions

In summary, in this paper we present the following contributions:

  * •

We provide the first multi-party circuit-based PSI achieving
$O(mnlog^{2}(mn))$ asymptotic communication overhead. Our protocol is a
natural generalization of the two-party circuit-based PSI protocol, which
simplifies the complexity of multi-party interactions and can be easily
expanded.

  * •

We integrate simple hashing scheme into our multi-party circuit-based
protocols. By using the permutation-based hashing function, the elements can
be represented in the form of shorter bits in the bins. Grouping data into
bins results in a reduction in circuit size and enables parallel computation.
This approach achieves the goal of simultaneously decreasing both
communication and time overheads.

##  II Preliminaries

###  II-A Setting

There are $m$ parties, which we denote as $P_{1}$, …, $P_{m}$, where $P_{1}$
and $P_{2}$ are typically the two parties for security computation. Each of
these parties is in possession of respective input sets,
$S_{1},S_{2},\dots,S_{m}$, each of which contains $n$ items represented by
$\sigma$ bits. It is assumed that $P_{1}$ and $P_{2}$ agree on a circuit $C$
that receives the secret shares of input sets and computes the intersection of
$\hat{n}$ elements. They also agree on a symmetric function $f$ and can
compute $f(S_{1}\cap S_{2}\cap...\cap S_{m})$ securely. We denote the
computational and statistical security parameters by $\kappa$ and $\lambda$.
We use $\gamma$ to denote a parameter that determines the probability of
hashing failure, which is employed in optimization schemes. We use $S_{i}[j]$
to denote the $j$-th item in the set $S_{i}$. We also denote the set
$\\{1,...,c\\}$ as $[c]$.

###  II-B Security Model

In this work, similar to most protocols for private set intersection, we focus
on the semi-honest model, also known as the honest-but-curious model, which
assumes that all parties will follow the protocol, but adversaries may attempt
to extract as much information as possible from the protocol execution. This
is different from malicious adversary model, where adversaries can deviate
from the protocol steps arbitrarily. While protocols designed for malicious
adversaries offer more security, they tend to be less efficient than those
designed for the semi-honest setting. In most scenarios, semi-honest security
is sufficient, as it is currently difficult for adversaries to modify software
with attestation or business restrictions. However, for most recent
optimization of circuit-based PSI protocols that rely on Cuckoo hashing, it is
still difficult to ensure that such operation of hashing is secure and
correct.

The SCS protocol of [9] is a unique circuit-based PSI protocol that can be
easily modified to provide security against malicious adversaries by expanding
the circuit to verify that the elements are sorted, while maintaining an
overall complexity of $O(nlogn)$. It is worth noting that this advantage is
also present in our protocol.

###  II-C Secure Two-Party Computation

In contemporary MPC research, there exist two primary methods for the secure
computation of boolean circuits: Yao’s garbled circuit (GC) protocol [20] and
the GMW protocol [8].

Yao’s garbled circuit protocol presents a constant round complexity and
implements the free XOR gates technique [12]. Through the optimization
techniques developed in [21], the protocol requires at least two ciphertext
transmissions to evaluate an AND gate. Similarly, the GMW protocol also
implements the free XOR technique and necessitates two ciphertext
transmissions to evaluate each AND gate using OT extension [2]. However, the
GMW protocol offers an additional benefit in the form of its ability to
perform symmetric cryptographic computations in advance during the pre-
computation phase, thereby improving the efficiency of the online phase.

The main advantage of generic protocols is that it can easily extend the
functionality of the protocol without having to change the security of the
protocol. As such, we use generic secure two-party computation protocol to
implement our protocols.

###  II-D Secret Sharing

In cryptography, an $(n,t)$-secret sharing scheme has been proposed for
distributing a secret $s$ among $n$ parties in such a way that any $t+1$
parties can collectively reconstruct the secret $s$ from their shares, while
preventing any collusion of $t$ parties from learning any information about
$s$ [18, 3]. This scheme provides a secure and efficient way to distribute
secret information among multiple parties without compromising its
confidentiality.

In this context, our protocols employ an additive $(n,n-1)$-secret sharing
scheme. In our protocols, all parties have to distribute their input sets
among two designated parties, $P_{1}$ and $P_{2}$. This distribution ensures
that neither $P_{1}$ nor $P_{2}$ can obtain any information about the input
sets of other parties except their own data. During the computation phase of
the circuit, $P_{1}$ and $P_{2}$ reconstruct the inputs of the parties in the
circuit and calculate the intersection of the input sets.

The use of the additive secret sharing scheme in our protocols provides an
additional layer of security to the distribution of secret information among
multiple parties. The data pre-processing phase ensures that the input sets of
parties are kept confidential, and the computation phase guarantees that the
secret information is reconstructed securely without revealing any information
to unauthorized parties. This approach is beneficial for applications that
require the distribution of confidential information among multiple parties,
such as secure multi-party computation, privacy-preserving data analysis, and
secure cloud computing.

###  II-E Simple Hashing

We have incorporated a hashing scheme in our protocols to optimize them. The
literature on hashing schemes is extensive and covers a range of methods for
handling collisions, complexities associated with insertion, deletion, and
look-up operations, as well as utilization of storage space. Previous works
such as [15, 13, 5] have used hashing to improve the number of comparisons
performed in Private Set Intersection (PSI) protocols. Similarly, our
protocols allow the use of simple hashing schemes to split the computation by
mapping input items to bins.

The simple hashing scheme typically utilizes a table $T$ containing $\beta$
bins. We make the assumption that the number of bins $\beta$ is a power of 2.
In cases where $\beta$ is not a power of 2, [1] proposes a method to handle
this situation. Using a hash function $H$ which maps an element $e$ to an
address $a=H(e)$ within the range $[0,\beta-1]$, the element $e$ is then
placed into the corresponding bin $T[a]$. The simple hashing approach allows
for multiple elements to be stored in each bin, with the maximum number of
elements that can be stored in each bin depending on the total number of
elements and the number of bins. This problem has been analyzed in detail in
[16], which showed that when randomly mapping $n$ items to $n$ bins using $H$,
the most populated bin would have at most $\frac{lnn}{lnlnn}(1+o(1))$ items
with high probability.

In summary, by adopting simple hashing scheme, our protocols allow for
efficient computation by reducing the number of comparisons while enabling
parallel computation.

###  II-F Permutation-based Hashing

When dividing elements into bins, it is possible to reduce the bit-length of
stored items through permutation-based hashing, a technique introduced in
prior literature [1, 13]. In this work, we apply permutation-based hashing to
improve the memory usage of our simple hashing scheme. Specifically, by
utilizing permutation-based hashing, the elements stored in bins can be
represented using fewer bits, resulting in a reduction of the number of gates
required during the circuit computation stage. This reduction can lead to
significant efficiency improvements in terms of communication costs and
computation time. Notably, the permutation-based hashing technique can be
applied in all hashing-based privacy-preserving set intersection (PSI)
protocols, including the one proposed in this study.

In general, a traditional hash function
$h:\\{0,1\\}^{\sigma}\rightarrow\\{0,1\\}^{log\beta}$ maps an element $x$ to
bin $h(x)$, where $|x|$ represents the bit-length of $x$. We notice that the
bin index $h(x)$ is able to carry $log\beta$ bits of information. So, it is
possible to reduce the information stored in the bins from $\sigma$ to
$\sigma-log\beta$, which means that secure computations are done on elements
with smaller representations. If we choose the hash function carefully, we can
realize that if two items have the same representation stored in the bin and
are in the same bin, they must be equal. Permutation-based hashing provides
uses a Feistel-style trick to implement this purpose.

In details, we split the bit representation of an input item $x$ into
$x_{L}||x_{R}$, where $x_{L}$ has $log\beta$ bit-length, which is equal to the
big-length of the bin index in the hash table, and $|x_{R}|$ has $\sigma-
log\beta$ bit-length. Then we define $f()$ be a random function whose range is
$[0,\beta-1]$, represented by $log\beta$ bits. We define $h(x)=x_{L}\oplus
f(x_{R})$. Then the input item $x$ is stored in the bin $x_{L}\oplus
f(x_{R})$, and the value stored in the bin is $x_{R}$, which is reduced to
$\sigma-log\beta$ bit-length. We observe that if two elements $x$ and $y$ are
stored in the same bin, and the stored values $x_{R}$ and $y_{R}$ are also the
same, then that means $f(x_{R})=f(y_{R})$. Since the bin $h(x)=h(y)$, then
$x_{L}=y_{L}$. So, we can conclude that $x=y$. Note that if $|x|$ is not much
longer than $log\beta$, the overhead will have a great improvement.

|  $P_{1}$ and $P_{2}$ are the two sides for computing the boolean circuit
$C$.
---
Input to $P_{i}$: Input set $S_{i}$, $i\in[m]$.
Output: The intersection $I$ of the input sets.
Preparation:
— $P_{i}$ represents the input set $S_{i}$ as bit-vector $v_{i}$ of length
$2^{\sigma}$ locally.
— $P_{i}$ randomly selects $r_{i}$ and $r_{i}^{\prime}$ so that
$r_{i}+r_{i}^{\prime}=v_{i}$.
Execution:
1\. $P_{i}$ sends $r_{i}$ to $P_{1}$ and $r_{i}^{\prime}$ to $P_{2}$, for all
$i$, we have $r_{i}+r_{i}^{\prime}=v_{i}$.
2\. $P_{1}$ and $P_{2}$ input the received secret share,
$\\{r_{i}\\}_{i\in[m]}$ and $\\{r_{i}^{\prime}\\}_{i\in[m]}$, into the boolean
circuit $C$ and perform secure two-party computation:
— Reconstruct the bit-vectors $\\{v_{i}\\}_{i\in[m]}$ using $m2^{\sigma}$ XOR
gates.
— By performing AND operations on bit vectors $\\{v_{i}\\}_{i\in[m]}$ in turn,
the circuit C outputs the ciphertext of the bit-vector representation of the
intersection.
3\. $P_{1}$ and $P_{2}$ send the result (the bit-vector of the intersection)
to all the other parties.
4\. All participants infer the elements of the intersection according to the
representation of the bit-vector of the intersection.

Figure 2: Multi-party Bitwise-AND Protocol

###  II-G Circuit PSI based on Hashing

The first circuit-based PSI protocol was introduced in [9]. Prior to
performing computations in the circuit, the parties are required to sort their
input sets and input them to the circuit. In the protocol proposed in [13],
the parties must also utilize hash schemes, such as Cuckoo hashing and simple
hashing, to map their input items into bins. Generally, these circuit-based
PSI protocols necessitate that the parties conduct operations (e.g.,
reordering and hashing) on their input sets beforehand.

It was shown in [6] that if the parties map their input items into bins, then
they only need to compare the items that stored in the same bins.
Nevertheless, the number of items mapped into each bin may reveal information
about their input sets. Thus, to ensure that this information is concealed
from other parties, it is necessary to pad all bins with random dummy values,
without revealing the number of items in each bin. It is assumed that the
parties agree on the maximum number of items that can be mapped into a bin,
denoted as $B$. Following the mapping of all items into bins, the parties must
pad each bin with dummy values until it contains $B$ items. If the two parties
compare the items in the bins using pairwise comparisons, the total number of
the comparisons will reduce from $O(n^{2})$ to $O(\beta\cdot B^{2})$, where
$n$ is the number of items in each input set and $\beta$ is the number of the
bins.

In our proposed protocols, we combine simple hashing scheme with the Sort-
Compare-Shuffle protocol to compare items in each bin. By carefully selecting
the number of bins $\beta$ and the upper bound $B$ for the maximum number of
items that can be mapped to a bin, this approach can offer computational and
communicational advantages over previous schemes. In this scenario, the
parties need to map their input items into bins using a hash function and
locally sort the items in each bin for subsequent merge sorting.

##  III Multi-party Bitwise-AND Protocol

As illustrated in Figure 2, the mBWA protocol is exclusively viable for small-
scale universes. In such circumstances, the input sets can be succinctly
represented as bit-vectors of length $2\sigma$. In a two-party context, the
intersection can be computed by applying a simple bit-wise AND operation
between the bit-vectors of the two parties. When it comes to multi-party
situation, each party must first distribute their respective input sets among
two designated parties (typically denoted as $P_{1}$ and $P_{2}$) through the
use of a secret-sharing scheme prior to the computation phase. Subsequently,
$P_{1}$ and $P_{2}$ must reconstruct the respective bit-vectors of each party.
The intersection can then be computed by performing a bit-wise AND operation
between the bit-vectors.

The whole computation process of the circuit is relatively clear and the
circuit can be obtained by instantiating a binary XOR gate $m2^{\sigma}$ times
and a binary AND gate $(m-1)2^{\sigma}$ times. The utilization of the free XOR
gates technique permits the XOR gates in the circuit to be evaluated without
incurring any communication or cryptographic operations, resulting in a bit-
vectors reconstruction stage that is free of such operations. Despite the
exponential number of AND gates, the small constant factor leads to favorable
performance, particularly after integrating the optimization of the hash
scheme. Detailed information about the experimental results can be found in
the ”Experimental Results” section.

##  IV Multi-party Sort-Compare-Shuffle Protocol

It is worth noting that while the cost of a multi-party protocol increases
exponentially with sigma, the constant factor is relatively small, leading to
satisfactory performance in small universes. However, for larger universes, it
is necessary to further reduce the protocol overhead. To this end, we propose
the mSCS protocol, following the SCS paradigm. The protocol leverages the
local computing capabilities of each party to minimize overhead.

Figure 3: Example of multiparty Sort-Compare-Shuffle protocol where $m=3$ (any
stage labeled as ”Oblivious” in the figure indicates the parts that require
two-party secure computation).

The mSCS protocol comprises three parts as shown in Figure 3. Firstly, each
participant, including $P_{1}$ and $P_{2}$, performs local sorting on the
input set and then distributes the sorted set to $P_{1}$ and $P_{2}$ via a
additive secret sharing scheme. Secondly, $P_{1}$ and $P_{2}$ utilize generic
secure two-party computation to reconstruct the input sets and sort the union
of the two sets with an oblivious merging network. As the sequence is already
sorted, it is not necessary to compare every adjacent element, as was done in
the scenario involving two parties. Rather, comparison of elements at
specified positions in the sorted sequence suffices for finding the
intersection elements. For example, in a scenario with three participating
parties, if the first and third elements are equal, then the element must be
one of the elements in the intersection. Nonetheless, direct output of the
intersection elements is not viable, as this may reveal positional
information. Further details can be found in [9]. Therefore, it is imperative
to shuffle the matched elements to conceal any positional information from the
resulting order.

###  IV-A Sort

Referring to the first protocol for distributing and reconstructing the input
sets, we assume that the input set of each participant has already been
reconstructed in the circuit. Following this, participants $P_{1}$ and $P_{2}$
are required to implement an oblivious merging network to sort the union of
the input sets, making use of the fact that the input sets are already sorted.
The term ”oblivious” implies that regardless of the order of the input
elements, the circuit remains fixed, i.e., the sequence of comparison between
elements is predetermined. In order to merge the $m$ sorted lists into a fully
sorted sequence, a merge-sort network is designed based on the $k$-Bitonic
sort algorithm [7]. The resulting number of comparisons is $O(mnlog^{2}(mn))$.

(a) 2-Sorter

(b) 1-bit Comparator

(c) 1-bit CondSwap

Figure 4: Basic modules of a sorting network.

The concatenation of a sequence sorted in ascending order with a sequence
sorted in descending order yields a bitonic sequence, which can be obtained
after local sorting. In the context of sorting networks, the 2-Sorter module
serves as a fundamental component. As shown in Figure 4, a design for 2-Sorter
is presented in [9], which comprises a $\sigma$-bits Comparator and a
$\sigma$-bits CondSwap, resulting in a requirement of only $2\sigma$ non-free
gates to compare two $\sigma$-bits elements. We can recursively utilize the
Batcher’s bitonic sorting network, as described [9], in a tree-like manner.
However, the resulting high complexity caused by excessive redundant
computations is not acceptable.

In our work, we introduce a $k$-Bitonic sort algorithm, denoted as Algorithm
1, which is a generalized version of the bitonic sort introduced by Batcher in
1968. We assume that $k=\lceil\frac{m}{2}\rceil$ to indicate that there are
$k$ bitonic sequences in total in the case of $m$ parties. It is important to
note that $k$-Bitonic sort reduces to Batcher’s bitonic sort when $k$ is equal
to 1. Specifically, the code executed until the 10th line of the algorithm is
identical to Batcher’s bitonic sorting algorithm.

We assume that the input $V=V[0:N-1]$ is a $k$-bitonic sequence, where $N=mn$
is the length of the sequence, and the ouput $U[0:N-1]$ is an incremental
sequence. By performing odd-even splitting on a sequence, the resulting sub-
sequences can still exhibit the characteristic of $k$-bitonic sequence. Thus,
the $k$-bitonic sort algorithm KBS($V,N,U$) is a recursive procedure. We
denote $Q({a_{0},a_{1},...,a_{n-1}})$ is the permutation of the sequence
$A=\\{a_{0},a_{1},...,a_{n-1}\\}$ ordered in an ascending fashion. The
fundamental operation in the execution process of the KBS algorithm is to
compare and exchange two elements.

Algorithm 1 $k$-Bitonic Sort KBS($V,N,U$)

1: if N == 1 then

2: RETURN;

3: end if

4: $Y[0:\frac{N}{2}-1,0:1]=V[0:N-1]$; ($Y[i,j]=V[2i+j]$)

5: for $j=0$ to $1$ do

6: KBS($Y[*,j],\frac{N}{2},B[*,j]$);

7: end for

8: for $i=0$ to $\frac{N}{2}-1$ do

9: $C_{0}[i,*]=Q(B[i,*])$;

10: end for

11: $d=\lceil log_{2}(N)\rceil$

12: if $N\leq 2k$ then

13: $d=d-1$;

14: end if

15: for $t=1$ to $d$ do

16: $\delta=2^{d-t}$;

17: for $i=0$ to $\frac{N}{2}-1-\delta$ do

18: $(C_{t}[i,1],C_{t}[i+\delta,0])=Q(C_{t-1}[i,1],C_{t-1}[i+\delta,0])$;

19: end for

20: end for

21: $U=C=C_{d}$; ($U[2i+j]=C[i,j]$)

Based on the complexity analysis of the recursive function, we deduce that the
time complexity of the KBS algorithm is $O(mnlog^{2}(mn))$. To provide a more
detailed analysis, we use the recurrence formula to work out the number of
comparisons performed by the merge sort circuit. The resulting expression is
$\frac{mn}{4}log(mn)log(\frac{mn}{2})+mn-1$. Thus, we can construct a circuit
that merges $m$ sequences of $n$ elements, each consisting of $\sigma$ bits,
into a single sorted sequence of $mn$ elements. The circuit requires
$2\sigma(\frac{mn}{4}log(mn)log(\frac{mn}{2})+mn-1)$ non-free gates.

###  IV-B Compare

After sorting the $mn$ elements in a list, the next step in the secure set
intersection protocol involves comparing adjacent $m$ elements to identify the
elements in the intersection.

In this phase, we employ a duplicate-selection circuit to identify all
elements in the intersection. Specifically, the circuit filters out the
elements in the intersection by computing whether a consecutive set of $m$
elements are all equal. If they are equal, it outputs the value of the
element; otherwise, it outputs a dummy value. Our investigation focused on
exploring the properties of sorted lists and their relevance to the protocol
at hand. We aimed to gain a deeper understanding of the characteristics that
could be leveraged to optimize the execution of the protocol. After thorough
analysis, we identified two key properties that are particularly significant:

####  IV-B1 Non-adjacent element comparison

By exploiting the inherent order of the sorted list, we discovered that it is
unnecessary to compare adjacent elements during the computation. Instead, we
can employ a larger stride when comparing elements. In a scenario involving
three parties, we denote the the sorted list as $l$. So we can compare
elements $(l_{i},l_{i+2})$ rather than evaluating pairs $(l_{i},l_{i+1})$ and
$(l_{i+1},l_{i+2})$. This strategic adjustment effectively reduces the
computational complexity of the circuit, leading to improved efficiency.

Figure 5: Example of comparing three consecutive elements.

####  IV-B2 Obliviousness of matched elements

Through our investigation, we observed an intriguing pattern within the sorted
sequence. In any consecutive group of $2m-1$ elements, there can be at most
one matched element, and it will always be positioned in the middle of the
group. This critical characteristic aligns with the requirement of the
circuit’s obliviousness, ensuring that only relevant and meaningful elements
are considered in the intersection computation.

Based on these two properties, we are able to streamline the circuit design
and enhance its overall performance. To implement and leverage the two
important properties we have discovered, as shown in Figure 6, we design a
$5$-duplicate-selection circuit to acquire the matched elements in the
intersection, if any. Specifically, the circuit takes as input $5$ consecutive
elements and outputs the matched element or a dummy value $0^{\sigma}$. In
fact, the combination of the $5$-duplicate-selection circuits ensures that
every continuous $5$ elements of the sequence in the circuit will be compared.

(a) 5-duplicate-selection circuit

(b) Combination of 5-duplicate-selction circuits

Figure 6: Design and use of 5-duplicate-selection circuits.

The $5$-duplicate-selection circuit is constructed using $4\sigma-1$ non-free
gates. The combination of duplicate-selection circuits employs $n-1$
$5$-duplication-selection circuits and one $3$-duplication-selection circuit
which can be constructed using $2\sigma-1$ non-free gates. Consequently, the
total number of non-free gates required for this phase is $(4n-2)\sigma-n$. By
leveraging the property of non-adjacent element comparison, in a scenario
involving three participants, we can achieve a reduction in the circuit’s size
by approximately 25% for this particular stage. Furthermore, the effectiveness
of this optimization becomes more pronounced when $m$ is a relatively large
value (more than 10). Moreover, this particular circuit design is capable of
producing $n$ elements rather than $3n-2$ which would be produced using
adjacent element comparison. Therefore, this optimization also results in a
reduction of approximately 60% in the size of the circuit for the next stage
(Shuffle).

This design can be generalized to $m$ participants, where the total number of
non-free gates required for the comparison phase is
$[(m+1)\sigma-1](n-1)+2\sigma-1$. Therefore, we have devised and employed a
combination of duplicate-selection circuits, which compare each of the $m$
consecutive elements in the sorted sequence, in order to figure out the
elements in the intersection. This process involves the use of $O(mn)$ non-
free binary gates.

###  IV-C Shuffle

Upon figuring out the intersection, the matched $n$ elements (and dummy
values) are arranged in a specific positional order in the circuit. This
ordering has the potential to compromise the confidentiality of parties’ input
sets. However, if we only need to perform subsequent computations based on the
elements in the intersection, this step can be omitted. Therefore, to preserve
privacy, it is essential to shuffle the elements before their disclosure. The
shuffling process is crucial to ensuring privacy in secure multi-party
computation, especially when dealing with sensitive data. In the absence of a
proper shuffling algorithm, the positional information of the elements in the
circuit may allow an adversary to deduce the corresponding parties’ input
sets. Specific examples can be obtained in [9]. In line with [9], we also
utilize an oblivious shuffling network, which is constructed using
$O(mnlog(mn))$ non-free gates, to implement the random permutation needed to
obliterate the positional information.

An oblivious shuffling network employs a set of gates that do not reveal any
information about the input values while transforming the input sequence into
an output sequence. The network achieves this by iteratively swapping pairs of
elements in the sequence according to a predetermined permutation. Since the
permutation is randomly generated, the resulting sequence is uniformly
distributed over all possible permutations. Consequently, the positional order
of the elements in the circuit is destroyed, and parties’ input sets remain
private.

The computational complexity of the shuffling process is a critical
consideration, as it determines the scalability of the multi-party computation
protocol. The $O(mnlog(mn))$ complexity of the oblivious shuffling network
used in this protocol can be expensive for large inputs. Nonetheless, it
remains a practical solution for most use cases, and ongoing research aims to
develop more efficient shuffling algorithms.

##  V Hashing to Bins

In this section, we present an enhanced iteration of the previously proposed
protocol. Our approach combines the simple hashing scheme with circuit-based
multi-party private set intersection to minimize communication overhead and
enable parallel computing. We consider the earlier proposed protocol as a sub-
protocol within our optimization framework. Specifically, we employ the simple
hashing scheme to partition the data into multiple bins, and subsequently
employ the circuit-based sub-protocol within each bin to compute the set
intersection efficiently. This optimized approach aims to improve the overall
performance and scalability of the protocol while maintaining the privacy
guarantees provided by the original scheme.

To further improve the efficiency of the protocol, we also use the
permutation-based hashing function. These hash functions allow for a more
compact representation of the elements stored in each bin, which can further
reduce communication costs, as the communication cost mainly depends on the
number of non-free gates in the circuit.

We provide a detailed description of the main ideas behind our optimization
approach and the overall protocol flow. To prove the effectiveness of our
optimization approach, we also conduct extensive calculations and analyses on
both the efficiency and security of our protocol after incorporating the
hashing scheme.

###  V-A Construction

As shown in Figure 7, each participant follows simple hashing scheme, where
each bin can store more than one element, using a public permutation-based
hash function $h$ to hash elements from the input set to their respective
bins. We assume that each participant possesses $\beta$ bins, with each bin
having a capacity of $B$, including both dummy values and actual elements.

Once the elements are hashed into the bins, the generic circuit-based multi-
party protocol is executed in each corresponding bin to perform the set
intersection operation. The circuits in each bin are independent of each
other, allowing for simple and efficient parallel computation.

|  $P_{1}$ and $P_{2}$ are the two sides for computing the boolean circuit
$C$.
---
Input to $P_{i}$: Input set $S_{i}$, $i\in[m]$.
Output: The intersection $I$ of the input sets.
Preparation:
— Let $h:\\{0,1\\}^{\sigma}\rightarrow\\{0,1\\}^{log\beta}$ be a public hash
function.
Execution:
1\. $P_{i}$ applies the hash function $h$ to hash all of their elements into
respective $\beta$ bins. If the number of elements in any bin exceeds the
capacity $B$,
the protocol is terminated.
2\. For each bin, $P_{1}$ and $P_{2}$ perform secure computation on each bin
to implement circuit-based multi-party private set intersection protocol (mBWA
and mSCS).

Figure 7: Combining simple hashing and circuit-based multi-party private set
intersection protocol

###  V-B Security

In our proposed scheme, each party employs simple hash scheme to map their
respective input set into multiple bins. In simple hash scheme, if the number
of items mapped to a bin exceeds its capacity, the use of bins with a constant
size may result in hashing failures.

When hashing fails, the party responsible for the hashing operation has two
possible options. The first option is to ignore the unmapped element and
remove it from its input set, which may result in an incorrect final computed
result, albeit rare. The second option is to attempt to use an alternative
hash function to remap the unmapped element. However, this approach requires
informing the other parties involved of the use of the new hash function,
which introduces a potential privacy leak. For instance, the other party could
infer whether the input set $S$ of the first party could be equal to a set
$S^{\prime}$ by checking if $S^{\prime}$ did not encounter hash failure,
indicating that $S^{\prime}$ and $S$ are not identical. Thus, it is essential
to carefully set the capacity of each bin to minimize the probability of
hashing failures to be negligibly small. However, a large bin capacity may
inevitably result in an excessive number of dummy values in each bucket,
leading to a reduction in the overall efficiency of the protocol.

The most desirable scenario is when all elements are uniformly mapped to bins
and each bin is fully occupied. In this case, we denote the ideal capacity of
each bin is $b=\frac{n}{\beta}$, where $n$ is the total number of elements and
$\beta$ is the number of bins. Next, the actual capacity $B$ should be as
close as possible to $b$ while maintaining a negligible probability of hashing
failures. We assume that $h$ is a random uniform hash function, and
$X_{i},i\in[n]$ are independent random variables. From the perspective of a
fixed party, observing a fixed bin, $X_{i}=1$ means that the $i$-th element is
mapped to the bin by $h$, otherwise $X_{i}=0$. Then, $X=\sum_{i=1}^{n}X_{i}$
represents the number of the participant’s elements mapped to that bin. Thus,
we can obtain $E(X)=b$.

In probability theory, Chernoff Bound is a statistical concept that helps us
understand the probability of the sum of independent random variables
deviating from its expected value. Thus, according to Chernoff Bound, we can
obtain that for any $\delta\in[0,1]$, it holds that:

$Pr[X\geq(1+\delta)b]\leq e^{-\frac{\delta^{2}b}{3}}$

We define the event $A_{i}$ as $X\geq(1+\delta)b$, which represents the
occurrence of hashing failure in a particular bin. Using the Boolean
inequality $P(\bigcup_{i}A_{i})\leq\sum_{i}P(A_{i})$, given that there are $m$
parties and each party has $\beta$ bins, the probability of the whole protocol
experiencing hashing failure satisfies:

$\displaystyle\begin{aligned} Pr[Failure]&\leq m\beta
e^{-\frac{\delta^{2}b}{3}}\\\ &=m\frac{n}{b}e^{-\frac{\delta^{2}b}{3}}\\\
&=2^{log_{2}e^{-\frac{\delta^{2}b}{3}}+log_{2}\frac{mn}{b}}\\\
&<2^{-\frac{\delta^{2}b}{3}+logn}\end{aligned}$

Therefore, if $B$ is set to $(1+\delta)b$ and the right-hand side of the
inequality is a negligible function, it suffices to prove that the proposed
scheme will result in negligible probability of hashing failures. So, if we
want to keep the overall failure probability less than $2^{-\gamma}$:

$\displaystyle\begin{aligned}
2^{-\frac{\delta^{2}b}{3}+logn}&<2^{-\gamma}\end{aligned}$

We can get:

$b>\frac{3(logn+\gamma)}{\delta^{2}}$

and

$\beta=\frac{n}{b}<\frac{n\delta^{2}}{3(logn+\gamma)}$

m | 3 | 5 | 7 | 9
---|---|---|---|---
n | $2^{8}$ | $2^{12}$ | $2^{16}$ | $2^{8}$ | $2^{12}$ | $2^{16}$ | $2^{8}$ | $2^{12}$ | $2^{16}$ | $2^{8}$ | $2^{12}$ | $2^{16}$
Time | 0.37 | 7.07 | 160.39 | 0.52 | 12.30 | 272.80 | 0.73 | 19.78 | 357.26 | 0.97 | 32.90 | 593.54
Comm. | 13.68 | 430.46 | 11457.65 | 48.97 | 1539.40 | 41018.387 | 100.14 | 3151.91 | 83869.97 | 165.53 | 5208.56 | 138637.57
TABLE I: Total runtime (in seconds) and communication (in MB) of Plain mSC
protocol. All the parties have n 32-bit elements as input.

###  V-C Complexity Analysis

In fact, we can set $\delta=1$ and $b=\log^{2}n$ to make the probability of
overall hashing failure a negligible function of the input set size $n$. If we
consider the mSCS protocol and use it to handle the elements in each bin, we
need to perform $O(mb\log^{2}(mb))$ comparisons between elements. Thus, the
total number of comparisons for $\beta$ bins is $O(\beta mb\log^{2}(mb))$,
which can be simplified as $O(mnlog^{2}(mlogn))$.

We assume that all the elements can be represented using $\sigma$ bits. By
using permutation-based hashing function to map elements to corresponding
bins, the elements stored in the bin can be represented with shorter bits.
Specifically, with $\beta$ bins, the corresponding element can be stored using
$l=\sigma-log\beta$ bits, and it can be guaranteed that if two elements have
the same value stored in the same bin, then these two elements must be equal.
Therefore, the asymptotic communication complexity of our final protocol
reduces from $O(\sigma mnlog^{2}(mn))$ to $O(lmnlog^{2}(mlogn))$. By summing
up, simplifying, and scaling down the number of non-free gates across the
three stages, we obtain an upper bound on the number of non-free gates
required for computations within each bin:

$\displaystyle\quad\sigma[\frac{mn}{2}log^{2}(mn)+\frac{8mn}{3}+n]$

In our proposed optimization scheme, each bin stores $B=(1+\delta)b$ elements,
and each element has a length of $\sigma-\log\beta$ bits. Therefore, we can
obtain an upper bound on the number of non-free gates for each bin required
after incorporating the hashing scheme using the above equation (with
$n=(1+\delta)b$ and $\sigma$ is set to $\sigma-\log\beta$). That is, for given
$m$, $n$, $\sigma$, and $\gamma$, we can minimize the number of non-free gates
required by setting the value of $\delta$ and $b$.

##  VI Experimental Results

In this section, we provide a comprehensive evaluation of the performance and
costs associated with our protocols, considering specific values for the
security parameters. Specifically, we set the computational security parameter
to $\kappa=128$, and the statistical security parameter to $\lambda=80$. As
the work of [9] has demonstrated, we find that the BWA protocol is the optimal
choice when the size of the element space is small (up to approximately
$\sigma$ = 20), as verified through experimental validation. Therefore, to
accommodate more general scenarios, we have exclusively implemented mSCS
protocol, and measured its performance on a range of inputs.

To carry out our experiments, we utilized two standard desktop computers
equipped with high-performance 12th Gen Intel(R) Core(TM) i5-12400 2.50GHz
processors and 16GB RAM. These computers were connected via a local area
network (LAN) with a bandwidth capacity of 100 Mbps. All the experiments were
done using two standard desktop computers equipped with 12th Gen Intel(R)
Core(TM) i5-12400 2.50GHz processors and 16GB RAM. These computers were
connected via a local area network (LAN) with a bandwidth capacity of 100
Mbps. In our experiments, all the elements were randomly generated from some
fixed universe, and each party’s input set was guaranteed to have no duplicate
elements. The time taken by the protocol includes both the execution of
oblivious transfer (OT) and the execution phase of garbled circuit.

###  VI-A Plain mSCS

Table 1 presents the results of a experimental evaluation conducted to assess
the performance of the plain mSCS protocol in computing the intersection of
large-scale input sets. Our findings reveal that the plain mSCS protocol
incurs a significantly higher communication overhead compared to a custom
multi-party private set intersection protocol, such as the one proposed by
[11]. Specifically, the plain mSCS protocol necessitates between 100 and 1000
times more communication than [11], which discloses the intersection in
plaintext to the participating parties. Despite the increased communication
overhead, the results obtained highlight the feasibility of employing the
plain mSCS protocol for privacy-preserving set intersection in large-scale
scenarios. Furthermore, the protocol demonstrates potential utility in non-
real-time applications where private set intersection serves as a submodule.

###  VI-B Hashing-mSCS

Table 2 presents a comprehensive analysis of the minimum numbers of non-free
gates required for each element in the Hashing-mSCS protocol, with $\delta$
and $b$ values set at $m=3$ and $\gamma=40$. The number of non-free gates
serves as a crucial metric for evaluating the protocol’s complexity, as it
significantly influences the performance of circuit-based Multi-Party
Computation protocols. Notably, the number of non-free gates remains
independent of the specific implementation details of the MPC framework,
distinguishing it from other benchmarks such as communication overhead or
runtime.

By conducting a meticulous analysis and comparing the theoretical
computational results of our proposed Hashing-mSCS protocol with the empirical
findings from the naive mSCS protocol, we have discovered a substantial
reduction of approximately 20% in communication overhead when employing the
Hashing-mSCS protocol. This reduction can be attributed to the utilization of
hashing techniques, which partition the elements into distinct bins.
Importantly, each bin operates independently, and the intersection of
computation results within each bin forms a subset of the final intersection.
As a consequence, the Hashing-mSCS protocol facilitates parallel computation,
effectively mitigating the challenge of excessive memory consumption
associated with large-scale circuits.

This improvement in communication overhead underscores the advantages offered
by the Hashing-mSCS protocol in terms of efficiency and scalability. The
parallel computation capability, achieved through bin-based partitioning and
independent processing, enables more efficient resource utilization. By
avoiding the need for storing and processing the entire intersection in a
single circuit, the protocol alleviates the burden on memory resources, making
it particularly well-suited for scenarios involving large circuit scales.
These findings contribute to the growing body of knowledge in the field of
secure multi-party computation, paving the way for enhanced privacy-preserving
protocols in large-scale settings.

$logn$ | $\sigma$ | $b$ | $\delta$ | non-free gates
---|---|---|---|---
8 | 12 | 292 | 0.82 | 1470
8 | 16 | 292 | 0.72 | 1932
8 | 20 | 292 | 0.67 | 2387
12 | 16 | 316 | 0.81 | 1514
12 | 20 | 316 | 0.71 | 1983
12 | 24 | 316 | 0.66 | 2447
16 | 20 | 341 | 0.80 | 1554
16 | 24 | 341 | 0.71 | 2032
16 | 28 | 341 | 0.65 | 2503
24 | 28 | 389 | 0.78 | 1629
24 | 32 | 389 | 0.69 | 2121
32 | 36 | 438 | 0.77 | 1697
32 | 40 | 438 | 0.68 | 2201
TABLE II: Minimum numbers of non-free gates required for each element in the
hashing-mSCS protocol

## References

  * [1] Y. Arbitman, M. Naor, and G. Segev, “Backyard cuckoo hashing: Constant worst-case operations with a succinct representation,” in _2010 IEEE 51st Annual symposium on foundations of computer science_. IEEE, 2010, pp. 787–796.
  * [2] G. Asharov, Y. Lindell, T. Schneider, and M. Zohner, “More efficient oblivious transfer and extensions for faster secure computation,” in _Proceedings of the 2013 ACM SIGSAC conference on Computer & communications security_, 2013, pp. 535–548.
  * [3] G. R. Blakley, “Safeguarding cryptographic keys,” in _Managing Requirements Knowledge, International Workshop on_. IEEE Computer Society, 1979, pp. 313–313.
  * [4] J. H. Cheon, S. Jarecki, and J. H. Seo, “Multi-party privacy-preserving set intersection with quasi-linear complexity,” _IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences_ , vol. 95, no. 8, pp. 1366–1378, 2012.
  * [5] M. J. Freedman, C. Hazay, K. Nissim, and B. Pinkas, “Efficient set intersection with simulation-based security,” _Journal of Cryptology_ , vol. 29, no. 1, pp. 115–155, 2016.
  * [6] M. J. Freedman, K. Nissim, and B. Pinkas, “Efficient private matching and set intersection,” in _Advances in Cryptology-EUROCRYPT 2004: International Conference on the Theory and Applications of Cryptographic Techniques, Interlaken, Switzerland, May 2-6, 2004. Proceedings 23_. Springer, 2004, pp. 1–19.
  * [7] Q. Gao, Y. Hu, and Z. Liu, “K-bitonic sort,” _Science in China Series E: Technological Sciences_ , vol. 42, no. 2, pp. 157–164, 1999.
  * [8] S. Goldwasser, “How to play any mental game, or a completeness theorem for protocols with an honest majority,” _Proc. the Nineteenth Annual ACM STOC’87_ , pp. 218–229, 1987.
  * [9] Y. Huang, D. Evans, and J. Katz, “Private set intersection: Are garbled circuits better than custom protocols?” in _NDSS_ , 2012.
  * [10] L. Kissner and D. Song, “Privacy-preserving set operations,” in _Advances in Cryptology–CRYPTO 2005: 25th Annual International Cryptology Conference, Santa Barbara, California, USA, August 14-18, 2005. Proceedings 25_. Springer, 2005, pp. 241–257.
  * [11] V. Kolesnikov, N. Matania, B. Pinkas, M. Rosulek, and N. Trieu, “Practical multi-party private set intersection from symmetric-key techniques,” in _Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security_ , 2017, pp. 1257–1272.
  * [12] V. Kolesnikov and T. Schneider, “Improved garbled circuit: Free xor gates and applications,” in _Automata, Languages and Programming: 35th International Colloquium, ICALP 2008, Reykjavik, Iceland, July 7-11, 2008, Proceedings, Part II 35_. Springer, 2008, pp. 486–498.
  * [13] B. Pinkas, T. Schneider, G. Segev, and M. Zohner, “Phasing: Private set intersection using permutation-based hashing,” in _24th $\\{$USENIX$\\}$ Security Symposium ($\\{$USENIX$\\}$ Security 15)_, 2015, pp. 515–530.
  * [14] B. Pinkas, T. Schneider, O. Tkachenko, and A. Yanai, “Efficient circuit-based psi with linear communication,” in _Advances in Cryptology–EUROCRYPT 2019: 38th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Darmstadt, Germany, May 19–23, 2019, Proceedings, Part III 38_. Springer, 2019, pp. 122–153.
  * [15] B. Pinkas, T. Schneider, and M. Zohner, “Faster private set intersection based on $\\{$OT$\\}$ extension,” in _23rd $\\{$USENIX$\\}$ Security Symposium ($\\{$USENIX$\\}$ Security 14)_, 2014, pp. 797–812.
  * [16] M. Raab and A. Steger, “Balls into bins-a simple and tight analysis,” _Randomization and Approximation Techniques in Computer Science_ , vol. 1518, pp. 159–170, 1998.
  * [17] Y. Sang and H. Shen, “Privacy preserving set intersection based on bilinear groups,” in _Proceedings of the thirty-first Australasian conference on Computer science-Volume 74_. Citeseer, 2008, pp. 47–54.
  * [18] A. Shamir, “How to share a secret,” _Communications of the ACM_ , vol. 22, no. 11, pp. 612–613, 1979.
  * [19] ——, “On the power of commutativity in cryptography,” in _Automata, Languages and Programming: Seventh Colloquium Noordwijkerhout, the Netherlands July 14–18, 1980 7_. Springer, 1980, pp. 582–595.
  * [20] A. C.-C. Yao, “How to generate and exchange secrets,” in _27th annual symposium on foundations of computer science (Sfcs 1986)_. IEEE, 1986, pp. 162–167.
  * [21] S. Zahur, M. Rosulek, and D. Evans, “Two halves make a whole: Reducing data transfer in garbled circuits using half gates,” in _Advances in Cryptology-EUROCRYPT 2015: 34th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Sofia, Bulgaria, April 26-30, 2015, Proceedings, Part II 34_. Springer, 2015, pp. 220–250.

[9] [7] [19] [13] [14] [6] [10] [17] [4] [11] [20] [8] [12] [21] [2] [18] [3]
[15] [5] [1] [16]


11footnotetext<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>
# The Brownian Motion in an Ideal Quantum Qas

Chi-Chun Zhou  Ping Zhang  and Wu-Sheng Dai

###### Abstract

A Brownian particle in an ideal quantum gas is considered. The mean square
displacement (MSD) is derived. The Bose-Einstein or Fermi-Dirac distribution,
other than the Maxwell-Boltzmann distribution, provides a different stochastic
force compared with the classical Brownian motion. The MSD, which depends on
the thermal wavelength and the density of medium particles, reflects the
quantum effect on the Brownian particle explicitly. The result shows that the
MSD in an ideal Bose gas is shorter than that in a Fermi gas. The behavior of
the quantum Brownian particle recovers the classical Brownian particle as the
temperature raises. At low temperatures, the quantum effect becomes obvious.
For example, there is a random motion of the Brownian particle due to the
fermionic exchange interaction even the temperature is near the absolute zero.

##  1 Introduction

The Brownian motion is first observed by Robert Brown in 1827 and then
explained by Einstein (1905), Smoluchowski (1905), and Langevin (1908) in the
early 20th century [1]. The early theory of the Brownian motion not only
provides an evidence for the atomistic hypothesis of matter [2], but also
builds a bridge between the microscopic dynamics and the macroscopic
observable phenomena [2].

The classical understanding of the Brownian motion is quite well established.
However, there is an assumption in the early theory of the Brownian motion
that the medium particle obeys the Maxwell-Boltzmann distribution.

The behavior of a Brownian particle in an ideal quantum gas draws some
attentions because to study the motion of a Brownian particle in an quantum
system is now within reach of experimental tests. For example, an electron in
a black body radiation [3]. In such systems, the quantum exchange interaction,
which always leads to real difficulty in mechanics and statistical mechanics
[4, 5, 6, 7], exists and causes the medium particle obeying the Bose-Einstein
or Fermi-Dirac distribution. It is difficult to make exact or even detailed
dynamical calculations [8, 1], since a different stochastic force is provided
by the Bose-Einstein or Fermi-Dirac distribution. At high-temperature and low-
density, the classical theory serves as good approximation.

In this paper, we give an explicit expression of the mean square displacement
(MSD) of a Brownian particle in an ideal quantum gas using, e.g., the virial
expansion. Comparison with the classical Brownian motion, a correction for the
MSD, which depends on the thermal wavelength and the density of medium
particles, is deduced. The result shows that the MSD in an ideal Bose gas is
shorter than that in a Fermi gas. The behavior of the quantum Brownian
particle recovers the classical Brownian particle as the temperature raises.
At low temperature, the quantum effect becomes obvious. For example, there is
a random motion of the Brownian particle due to the fermionic exchange
interaction even the temperature is near the absolute zero.

The early studies of the Brownian motion inspired many prominent developments
in various areas such as physics, mathematics, financial markets, and biology.
In physics, exact solutions of Brownian particles in different cases, such as
in a constant field of force [1] and in a harmonically potential field [1],
are given. The Brownian motion with a time dependent diffusion coefficient is
studied in Ref. [9]. The boundary problem of Brownian motions is studied in
Refs. [10, 11]. The anomalous diffusion process, frequently described by the
scaled Brownian motion, is studied in Refs. [12, 13]. The Kramers-Klein
equation considers the Brownian particle that is in an general field of force
[1]. The generalized Langevin equations and the master equation for the
quantum Brownian motion are studied in Refs. [14, 15]. In mathematics, the
rigorous interpretation of Brownian motions based on concepts of random walks,
martingales, and stochastic processes is given [16, 8, 1]. In financial
markets, the theory of the Brownian motion is used to describe the movement of
the price of stocks and options [8, 1, 17, 18, 19, 20]. The application of the
fractional Brownian motion, which is a generalized Brownian motion, in
financial markets is studied in Refs. [21, 22, 23]. Moreover, the Brownian
motion plays a central and fundamental role in studies of soft matter and
biophysics [8], e.g., active Brownian motions, which can be used to describe
the motion of swarms of animals in fluid, are studied in Refs. [24, 25, 26,
27, 28, 8].

Among many quantities, the MSD, which is measurable, describes the Brownian
motion intuitively. There are studies focus on the MSD related problems. For
examples, the relation between the MSD and the time interval can be generally
written as $\left\langle x_{t}^{2}\right\rangle\sim t^{\alpha}$ [9]. One
distinguishes the subdiffusion with $0<\alpha<1$ and the superdiffusion with
$\alpha>1$ [29, 30, 31]. The relation between the MSD and the time interval of
the so called ultraslow Brownian motions is $\left\langle
x_{t}^{2}\right\rangle\sim\left(\ln t\right)^{\gamma}$ [32].

There are different approaches to build a quantum analog of the Brownian
motion [33, 34, 35, 36]. For examples, the method of the path integral is used
to study the quantum Brownian motion [35]. The approach of a quantum analog or
quantum generalization of the Langevin equation and the master equation, e.g.,
the quantum master equation [3] and the quantum Langevin equation [37] is used
to build a quantum Brownian motion. Among them, the method of quantum
dynamical semigroups [38] is prominent. They point it out that the quantum
equation should be casted into the Lindblad form [38, 39]. A completely
positive master equation describing quantum dissipation for a Brownian
particle is derived in Ref. [39].

This paper is organized as follows. In Sec. 2, for the sake of completeness,
we derive the brownian motion from the perspective of the particle
distribution in an ideal Boltzmann gas. In Sec. 3, we derive the MSD of a
Brownian particle in an ideal quantum gas. High-temperature and low-
temperature expansions are given. The $d$-dimensional case is considered. The
conclusion and outlook are given in Sec. 4. Some details of the calculation is
given in the Appendix.

##  2 A Brownian particle in an ideal classical gas: the Brownian motion

In this section, we consider a Brownian particle in an ideal classical gas.
For the sake of completeness, we derive, in detail, the Brownian motion from
the perspective of the particle distribution.

A brief review on the Langevin equation. For a Brownian particle with mass
$M$, the dynamic equation is given by Paul Langevin [40]

$\displaystyle dv$ $\displaystyle=-\frac{\gamma}{M}vdt+\frac{1}{M}F_{t}dt,$
(2.1) $\displaystyle dx$ $\displaystyle=vdt,$ (2.2)

where $\gamma=6\pi\eta r$ with $\eta$ the viscous coefficient and $r$ the
radius of the medium particles. $F_{t}$ is the stochastic force generated by
numerous collisions of the medium particle. It is reasonable to make the
assumption that $F_{t}$ is isotropic, i.e.,

$\left\langle F_{t}\right\rangle=0.$ (2.3)

If the collision of the medium particle is uncorrelated; that is, for $t\neq
s$, $F_{t}$ is independent of $F_{s}$:

$\left\langle F_{s}F_{t}\right\rangle\propto\delta\left(s-t\right),$ (2.4)

then, the solution of Eqs. (2.1) and (2.2) is [40]

$\displaystyle v_{t}$
$\displaystyle=v_{0}\exp\left(-\frac{\gamma}{M}t\right)+\frac{1}{M}\int_{0}^{t}\exp\left[-\frac{\gamma}{M}\left(t-s\right)\right]F_{s}ds,$
(2.5) $\displaystyle x_{t}$
$\displaystyle=x_{0}+\frac{M}{\gamma}v_{0}\left[1-\exp\left(-\frac{\gamma}{M}t\right)\right]+\frac{1}{\gamma}\int_{0}^{t}\left\\{1-\exp\left[-\frac{\gamma}{M}\left(t-s\right)\right]\right\\}F_{s}ds,$
(2.6)

where $x_{0}$ and $v_{0}$ are the initial position and velocity.

The stochastic force determined by the Maxwell-Boltzmann distribution and the
MSD. In an ideal classical gas, the gas particle obeys the Maxwell-Boltzmann
distribution [41]. The number of particles possessing energy within
$\varepsilon$ to $\varepsilon+d\varepsilon$, denoted by
$\tilde{a}_{\varepsilon}$, is proportional to $e^{-\beta\varepsilon}$ [41],
i.e.,

$\tilde{a}_{\varepsilon}=\omega_{\varepsilon}e^{-\beta\varepsilon}d\varepsilon,$
(2.7)

where $\omega_{\varepsilon}$ is the degeneracy of the energy $\varepsilon$ and
$\beta=\left(kT\right)^{-1}$ with $k$ the Boltzmann constant $T$ the
temperature [41]. A collision of the medium particle with energy $\varepsilon$
gives a force of magnitude proportional to $\sqrt{2m\varepsilon}$, which is
the momentum of the particle. We have

$F=\rho\sqrt{2m\varepsilon},$ (2.8)

where $\rho$ is a coefficient and $m$ is the mass of the medium particle.
Thus, the probability of the Brownian particle subjected to a stochastic force
with magnitude within $F$ to $F+dF$ is

$P\left(F\right)dF=\sqrt{\frac{\beta}{2\pi
m\rho^{2}}}\exp\left(-\frac{F^{2}\beta}{2m\rho^{2}}\right)dF.$ (2.9)

In an ideal classical gas, there is no inter-particle interactions among
medium particles, thus, for $t\neq s$, the force $F_{s}$ and $F_{t}$ are
independent. Substituting Eq. (2.9) into Eq. (2.4) gives

$\left\langle
F_{s}F_{t}\right\rangle=\frac{m\rho^{2}}{\beta}\delta\left(s-t\right).$ (2.10)

By using Eqs (2.6), (2.9), and (2.10), a direct calculation of the MSD gives

$\displaystyle\left\langle\left(x_{t}-x_{0}\right)^{2}\right\rangle$
$\displaystyle=\frac{M^{2}}{\gamma^{2}}\left(v_{0}^{2}-\frac{1}{2m\gamma}\frac{m\rho^{2}}{\beta}\right)\left[1-\exp\left(-\frac{\gamma}{M}t\right)\right]^{2}$
$\displaystyle+\frac{1}{\gamma^{2}}\frac{m\rho^{2}}{\beta}\left\\{t-\frac{M}{\gamma}\left[1-\exp\left(-\frac{\gamma}{M}t\right)\right]\right\\}.$
(2.11)

For a large-scale time, $t\gg 1$, Eq. (2.11) recovers

$\left\langle x_{t}^{2}\right\rangle=\frac{kT}{3\pi\eta r}t,$ (2.12)

where $\rho=\sqrt{12\pi\eta r/m}$ and $x_{0}$ is chosen to be $0$ without lose
of generality. Eq. (2.12) is the famous Einstein’s long-time result of the
MSD. The motion of a brownian particle in an ideal classical gas is the
Brownian motion.

##  3 The MSD of a Brownian particle in an ideal quantum gas

In this section, we give the MSD of a Brownian particle in an ideal quantum
gas. High-temperature and low-temperature expansions explain the quantum
effect intuitively.

###  3.1 The stochastic force determined by the Bose-Einstein or Fermi-Dirac
distribution

In an ideal quantum gas, the gas particle obeys Bose-Einstein or Fermi-Dirac
distribution other than the Maxwell-Boltzmann distribution. The stochastic
force is different from that in an ideal classical gas. In this section, we
discuss the properties of the stochastic force in an ideal quantum gas.

In an ideal quantum gas, the number of particles possessing energy within
$\varepsilon$ to $\varepsilon+d\varepsilon$, denoted by $a_{\varepsilon}$, is

$a_{\varepsilon}=\frac{\omega_{\varepsilon}}{\exp\left(\beta\varepsilon+\alpha\right)+g}d\varepsilon,$
(3.1)

where $\alpha$ is defined by $z=e^{-\alpha}$ with $z$ the fugacity [41]. For
Bose cases, $g=-1$, and for Fermi cases, $g=1$. Thus, the probability of the
Brownian particle subjected to a stochastic force with magnitude within $F$ to
$F+dF$ is

$p\left(F\right)dF=\sqrt{\frac{\beta}{2\rho^{2}m\pi}}\frac{1}{h_{1/2}\left(z\right)}\frac{1}{\exp\left[\beta
F^{2}/\left(2\rho^{2}m\right)+\alpha\right]+g}dF,$ (3.2)

where we $h_{\nu}\left(x\right)$ equals Bose-Einstein integral
$g_{\nu}\left(x\right)$ in Bose cases [41] and Fermi-Dirac integral
$f_{\nu}\left(x\right)$ [41] in Fermi cases.

In an ideal quantum gas, the stochastic force is also isotropic, that is, Eq.
(2.3) holds. However, the collision, due to the overlapping of the wave
package, can be correlated; that is, $\left\langle F_{s}F_{t}\right\rangle$ is
no longer a delta function but a function of $s-t$ with a peak at $s=t$.
However, as the ratio of the thermal wavelength and the average distance
between the medium particles decreases, $\left\langle
F_{s}F_{t}\right\rangle$, can be well approximated by a delta function:

$\left\langle
F_{s}F_{t}\right\rangle\sim\frac{m\rho^{2}}{\beta}\frac{h_{3/2}\left(z\right)}{h_{1/2}\left(z\right)}\delta\left(s-t\right),$
(3.3)

for $n\lambda\ll 1$, where $\lambda=h/\sqrt{2\pi mkT}$ is the thermal
wavelength and $n$ is the density of the medium particle.

In this paper, we consider the case that the ratio of the thermal wavelength
and the average distance between the medium particles is small.

###  3.2 The MSD

For $n\lambda\ll 1$, by using Eqs. (3.2), (2.3), and (2.6), a direct
calculation of MSD gives

$\displaystyle\left\langle x_{t}^{2}\right\rangle$
$\displaystyle=\frac{M^{2}}{\gamma^{2}}\left\\{v_{0}^{2}-\frac{1}{2m\gamma}\frac{m\rho^{2}}{\beta}\frac{h_{3/2}\left(z\right)}{h_{1/2}\left(z\right)}\right\\}\left[1-\exp\left(-\frac{\gamma}{M}t\right)\right]^{2}$
$\displaystyle+\frac{1}{\gamma^{2}}\frac{m\rho^{2}}{\beta}\frac{h_{3/2}\left(z\right)}{h_{1/2}\left(z\right)}\left\\{t-\frac{M}{\gamma}\left[1-\exp\left(-\frac{\gamma}{M}t\right)\right]\right\\}.$
(3.4)

For a large-scale time, $t\gg 1$, Eq. (3.4) recovers

$\left\langle x_{t}^{2}\right\rangle=\frac{kT}{3\pi\eta
r}t\frac{h_{3/2}\left(z\right)}{h_{1/2}\left(z\right)},$ (3.5)

where $h_{3/2}\left(z\right)/h_{1/2}\left(z\right)$ is a correction for the
MSD due to the Bose-Einstein or Fermi-Dirac distribution, a result of the
quantum exchange interaction among gases particles.

###  3.3 High-temperature and low-temperature expansions

In order to compare with Eq. (2.12) intuitively, we give high-temperature and
low-temperature expansions of Eq. (3.5) by using the state equation of ideal
Bose or Fermi gases [40, 41]

$\displaystyle p$ $\displaystyle=\frac{kT}{\lambda}h_{3/2}\left(z\right),$
(3.6) $\displaystyle\frac{N}{V}$
$\displaystyle=\frac{1}{\lambda}h_{1/2}\left(z\right).$ (3.7)

The high-temperature expansion. At high temperatures, the virial expansion of
Eqs. (3.6) and (3.7) directly gives [40, 41]

$\frac{pV}{N}\sim kT\left[1+ga_{1}\left(T\right)n\lambda+...\right],$ (3.8)

where $a_{1}\left(T\right)$ is the first virial coefficient [40]. For a
$1$-dimensional ideal Bose or Fermi gas, $a_{1}\left(T\right)=0.353553$ [41].
Substituting Eqs. (3.6) and (3.7) into Eq. (3.8) gives

$\frac{h_{3/2}\left(z\right)}{h_{1/2}\left(z\right)}\sim\left[1+ga_{1}\left(T\right)n\lambda+...\right].$
(3.9)

Substituting Eq. (3.9) into Eq. (3.5) gives the MSD at high temperatures:

$\left\langle x_{t}^{2}\right\rangle=\frac{kT}{3\pi\eta
r}t\left[1+ga_{1}\left(T\right)n\lambda+\ldots\right].$ (3.10)

The result, Eq. (3.10), shows that the MSD in an ideal Bose gas is shorter
than that in a Fermi gas. Since $\lambda$ decreases as $T$ raises, the
behavior of the quantum Brownian particle returns the classical Brownian
particle as the temperature raises.

The low-temperature expansion for Fermi cases. At low temperatures, for Fermi
cases, $g=-1$,

$\frac{h_{3/2}\left(z\right)}{h_{1/2}\left(z\right)}=\frac{f_{3/2}\left(z\right)}{f_{1/2}\left(z\right)}.$
(3.11)

The expansion of the Fermi-Dirac integral at large $z$ gives [41]

$f_{\nu}\left(e^{\xi}\right)=\frac{\xi^{\nu}}{\Gamma\left(1+\nu\right)}\left\\{1+2\nu\sum_{j=1,3,5,...}\left[\left(\nu-1\right)....\left(\nu-j\right)\left(1-2^{-j}\right)\frac{\zeta\left(j+1\right)}{\xi^{j+1}}\right]\right\\}.$
(3.12)

Keeping only the first two terms in Eq. (3.12) gives

$f_{\nu}\left(z\right)=\frac{\left(\ln
z\right)^{\nu}}{\Gamma\left(1+\nu\right)}+2\nu\left(\nu-1\right)\frac{1}{2}\frac{\zeta\left(2\right)}{\left(\ln
z\right)^{2}}.$ (3.13)

Substituting Eq. (3.13) into Eqs. (3.6) and (3.7) gives

$\displaystyle p$ $\displaystyle=\frac{kT}{\lambda}\frac{\left(\ln
z\right)^{3/2}}{\Gamma\left(5/2\right)}\left[1+\frac{3}{4}\frac{\zeta\left(2\right)}{\left(\ln
z\right)^{2}}\right],$ (3.14) $\displaystyle\frac{N}{V}$
$\displaystyle=\frac{1}{\lambda}\frac{\left(\ln
z\right)^{1/2}}{\Gamma\left(5/2\right)}\left[1-\frac{1}{4}\frac{\zeta\left(2\right)}{\left(\ln
z\right)^{2}}\right].$ (3.15)

The fugacity $z$ can be solved from Eq. (3.15):

$\ln
z\sim\frac{\epsilon_{f}}{kT}\left[1+\frac{1}{2}\zeta\left(2\right)\left(\frac{kT}{\epsilon_{f}}\right)^{2}\right],$
(3.16)

where
$\epsilon_{f}=\lambda^{2}kT\left[\frac{1}{2}\Gamma\left(\frac{3}{2}\right)n\right]^{2}$
is the Fermi energy [41]. By substituting Eq. (3.13) into Eq. (3.11) with
fugacity $z$ given by Eq. (3.16), we have

$\frac{f_{3/2}\left(z\right)}{f_{1/2}\left(z\right)}=\frac{\Gamma\left(3/2\right)}{\Gamma\left(5/2\right)}\frac{\epsilon_{f}}{kT}\left\\{1+\left[\frac{\zeta\left(2\right)}{2}+\zeta\left(2\right)\right]\left(\frac{kT}{\epsilon_{f}}\right)^{2}\right\\}.$
(3.17)

Substituting Eq. (3.17) into Eq. (3.5) gives the MSD of Fermi cases at low
temperatures:

$\left\langle x_{t}^{2}\right\rangle\sim\frac{1}{3\pi\eta
r}t\frac{\Gamma\left(3/2\right)}{\Gamma\left(5/2\right)}\epsilon_{f}\left[1+\frac{3}{2}\zeta\left(2\right)\left(\frac{kT}{\epsilon_{f}}\right)^{2}\right].$
(3.18)

The first term of Eq. (3.18) is independent of the temperature $T$, which
means that there is a random motion of the Brownian particle due to the
fermionic exchange interaction even the temperature is near the absolute zero.
It is a result of Pauli exclusion principle [41].

The low-temperature expansion for Bose cases. At low temperatures, for Bose
cases, $g=1$,

$\frac{h_{1+d/2}\left(z\right)}{h_{d/2}\left(z\right)}=\frac{g_{1+d/2}\left(z\right)}{g_{d/2}\left(z\right)}.$
(3.19)

Expanding $g_{\nu}\left(z\right)$ around $z=1$ gives [41]

$g_{\nu}\left(z\right)=\frac{\Gamma\left(1-\nu\right)}{\left(-\ln
z\right)^{1-\nu}}+\sum_{j=0}^{\infty}\frac{\left(-1\right)^{j}}{j!}\zeta\left(\nu-j\right)\left(-\ln
z\right)^{j}.$ (3.20)

Substituting Eq. (3.20) into Eqs. (3.6) and (3.7) gives

$\displaystyle p$
$\displaystyle=\frac{1}{\lambda^{d}}\Gamma\left(-\frac{1}{2}\right)\left(-\ln
z\right)^{1/2}+\zeta\left(\frac{3}{2}\right)-\zeta\left(\frac{1}{2}\right)\left(-\ln
z\right),$ (3.21) $\displaystyle\frac{N}{V}$
$\displaystyle=\frac{1}{\lambda^{d}}\frac{\Gamma\left(1/2\right)}{\left(-\ln
z\right)^{1/2}}+\zeta\left(\frac{1}{2}\right)-\zeta\left(-\frac{1}{2}\right)\left(-\ln
z\right).$ (3.22)

The fugacity can be solved from Eq. (3.22):

$\ln z=-\frac{\pi}{n^{2}\lambda^{2}}.$ (3.23)

By substituting Eq. (3.20) into Eq. (3.19) with fugacity $z$ given by Eq.
(3.23), we have

$\frac{g_{3/2}\left(z\right)}{g_{1/2}\left(z\right)}=\frac{\zeta\left(3/2\right)}{\sqrt{n^{2}\lambda^{2}}}-\left(2+\frac{\zeta\left(3/2\right)\zeta\left(1/2\right)}{\pi}\right)\frac{\pi}{n^{2}\lambda^{2}}.$
(3.24)

Substituting Eq. (3.24) into Eq. (3.5) gives the MSD of Bose cases at low
temperatures:

$\displaystyle\left\langle x_{t}^{2}\right\rangle$
$\displaystyle\sim\frac{kT}{3\pi\eta
r}t\left[\zeta\left(\frac{3}{2}\right)\frac{1}{n\lambda}-\left(2\pi+\zeta\left(\frac{3}{2}\right)\zeta\left(\frac{1}{2}\right)\right)\frac{1}{n^{2}\lambda^{2}}\right]$
(3.25) $\displaystyle\sim\frac{1}{3\pi\eta
r}\zeta\left(\frac{3}{2}\right)\frac{\sqrt{2\pi
m}}{h}\frac{1}{n}\left(kT\right)^{3/2}t.$ (3.26)

The MSD is proportional to $T^{3/2}$ and is reversely proportional to the
density of particle, which is also different from that of the Brownian motion.

###  3.4 The $d$-dimensional case

In this section, a similar procedure gives the MSD of a Brownian particle in a
$d$-dimensional space. For the sake of clarity, we list the result. The detail
of the calculation can be found in the Appendix.

The MSD. The MSD for a Brownian particle in an ideal quantum gas in a
$d$-dimensional space is

$\left\langle\mathbf{x}_{t}^{2}\right\rangle=\frac{kTd}{3\pi\eta
r}t\frac{h_{1+d/2}\left(z\right)}{h_{d/2}\left(z\right)}.$ (3.27)

The high-temperature expansion. At high temperatures, the MSD, Eq.(3.27),
becomes

$\left\langle\mathbf{x}_{t}^{2}\right\rangle=\frac{kTd}{3\pi\eta
r}t\left[1+ga_{1}\left(T\right)n\lambda^{d}+\ldots\right],$ (3.28)

where $a_{1}\left(T\right)=\frac{1}{2^{1+d/2}}$ and is the first virial
coefficient of ideal Bose or Fermi gases in a $d$-dimensional space [40, 41].

The low-temperature expansion for Fermi cases. At low temperatures, for Fermi
cases, the MSD, Eq. (3.27), becomes

$\left\langle\mathbf{x}_{t}^{2}\right\rangle\sim\frac{d}{3\pi\eta
r}\frac{\Gamma\left(1+d/2\right)}{\Gamma\left(2+d/2\right)}t\epsilon_{f}\left[1+\left(\frac{d}{2}+1\right)\zeta\left(2\right)\left(\frac{kT}{\epsilon_{f}}\right)^{2}\right],$
(3.29)

where $\epsilon_{f}$ is the Fermi energy in a $d$-dimensional space and
$\epsilon_{f}=\lambda^{2}kT\left[\frac{1}{2}\Gamma\left(1+\frac{d}{2}\right)n\right]^{2/d}$
[40, 41].

The low-temperature expansion for Bose cases with $d=2$. The low-temperature
expansion for a Bose gas at any dimension higher than $2$ is not given in this
section, because the Bose-Einstein condensation (BEC) occurs. Here, we only
consider the $2$-dimensional case. At low temperatures, for Bose cases, the
MSD, Eq. (3.27), becomes

$\left\langle\mathbf{x}_{t}^{2}\right\rangle=\frac{2kT}{3\pi\eta
r}t\left[-\exp\left(-n\lambda^{2}\right)-\frac{\exp\left(-n\lambda^{2}\right)}{n\lambda^{2}}+\frac{\pi^{2}}{6n\lambda^{2}}\right].$
(3.30)

##  4 Conclusions and outlooks

The difficulty in the calculation of the behavior of a Brownian particle in an
ideal quantum gas directly comes from the stochastic force caused by the Bose-
Einstein and Fermi-Dirac distribution other than the Maxwell-Boltzmann
distribution. Comparison with the classical Brownian motion, on one hand, the
distribution of the stochastic force is different; on the other hand, the
collision, due to the overlapping of the wave package, could be correlated,
that is, $\left\langle F_{s}F_{t}\right\rangle$ is no longer a delta function
but a function of $s-t$ with a peak at $s=t$. Thus, it is difficult to make
exact or even detailed dynamical calculations [8, 1].

In this paper, we consider the motion of a Brownian particle in an ideal
quantum gas. We give an explicit expression of the MSD, which depends on the
thermal wavelength and the density of medium particles. High-temperature and
low-temperature expansions explain the quantum effect intuitively. For
examples, the MSD in an ideal Bose gas is shorter than that in a Ferm gas.
There is a random motion of the Brownian particle due to the fermionic
exchange interaction even the temperature is near the absolute zero.

The result in this work can be verified by experiment test.

##  5 Acknowledgments

We are very indebted to Dr G Zeitrauman for his encouragement. This work is
supported in part by NSF of China under Grant No. 11575125 and No. 11675119.

##  6 Appendix

In the appendix, we give the detail of the calculation of Eqs (3.27), (3.28),
(3.29), and (3.30).

The detail of the calculate for the MSD, Eq. (3.27), of a Brownian particle in
a $d$-dimensional space. The Langevin equation in $d$-dimensional is

$\displaystyle M\frac{d\mathbf{v}}{dt}$
$\displaystyle=-\gamma\mathbf{v}+\mathbf{F}_{t},$ (6.1)
$\displaystyle\frac{d\mathbf{x}}{dt}$ $\displaystyle=\mathbf{v.}$ (6.2)

In a $d$-dimensional space, the stochastic force $\mathbf{F}_{t}$ is
isotropic:

$\left\langle\mathbf{F}\right\rangle=0.$ (6.3)

For different time $t$ and $s$, $\mathbf{F}_{s}$ and $\mathbf{F}_{t}$ are
almost independent when the ratio of the thermal wavelength and the average
distance between the medium particles is small, that is,

$\left\langle\mathbf{F}_{s}\cdot\mathbf{F}_{t}\right\rangle\sim\delta\left(s-t\right)$
(6.4)

holds for $n\lambda^{d}\ll 1$. The solution of Eqs. (6.1) and (6.2) is

$\displaystyle\mathbf{v}_{t}$
$\displaystyle=\mathbf{v}_{0}e^{-\frac{\gamma}{M}t}+\frac{1}{M}\int_{0}^{t}\exp\left[-\frac{\gamma}{M}\left(t-s\right)\right]\mathbf{F}_{s}ds,$
(6.5) $\displaystyle\mathbf{x}_{t}$
$\displaystyle=\mathbf{x}_{0}+\frac{M}{\gamma}v_{0}\left[1-\exp\left(-\frac{\gamma}{M}t\right)\right]+\frac{1}{\gamma}\int_{0}^{t}\left\\{1-\exp\left[-\frac{\gamma}{M}\left(t-s\right)\right]\right\\}\mathbf{F}_{s}ds.$
(6.6)

In the $d$-dimensional case, the number of particle possessing momentum within
$\mathbf{P}$ to $\mathbf{P+}d\mathbf{P}$, denoted by
$a\left(\mathbf{P}\right)$, is [40, 41]

$a\left(\mathbf{P}\right)=\frac{1}{\exp\left[\beta\left(p_{x^{1}}^{2}+p_{x^{2}}^{2}+...p_{x^{d}}^{2}\right)/\left(2m\right)+\alpha\right]+g}.$
(6.7)

The force given by a collision of a particle with momentum $\mathbf{P}$ is
proportional to $\mathbf{P}$, $\mathbf{F=}\rho\mathbf{P}$. Thus the
probability of the stochastic force with magnitude within
$\left|\mathbf{F}\right|$ to $\left|\mathbf{F+}d\mathbf{F}\right|$ is

$P\left(\mathbf{F}\right)d\mathbf{F}=\left(\sqrt{\frac{\beta}{2\pi
m\rho^{2}}}\right)^{d}\frac{1}{h_{d/2}\left(z\right)}\frac{1}{\exp\left[\beta\left|\mathbf{F}\right|^{2}/\left(2m\rho^{2}\right)+\alpha\right]+g}.$
(6.8)

Substituting Eq. (6.8) into Eq. (6.4) gives

$\left\langle\mathbf{F}_{s}\cdot\mathbf{F}_{t}\right\rangle\sim\frac{dm\rho^{2}}{\beta}\frac{h_{1+d/2}\left(z\right)}{h_{d/2}\left(z\right)}\delta\left(s-t\right).$
(6.9)

By using Eqs. (6.6), (6.8), and (6.9), a direct calculation of MSD gives

$\displaystyle\left\langle\mathbf{x}_{t}^{2}\right\rangle$
$\displaystyle=\frac{M^{2}}{\gamma^{2}}\left[\mathbf{v}_{0}^{2}-\frac{d}{2m\gamma}\frac{m\rho^{2}}{\beta}\frac{h_{1+d/2}\left(z\right)}{h_{d/2}\left(z\right)}\right]\left[1-\exp\left(-\frac{\gamma}{M}t\right)\right]^{2}$
$\displaystyle+\frac{1}{\gamma^{2}}\frac{dm\rho^{2}}{\beta}\frac{h_{1+d/2}\left(z\right)}{h_{d/2}\left(z\right)}\left[t-\frac{M}{\gamma}\left[1-\exp\left(-\frac{\gamma}{M}t\right)\right]\right].$
(6.10)

where $\mathbf{x}_{0}$ is chosen to be the origin.

For a large-scale time, $t\gg 1$, Eq. (6.10) recovers Eq. (3.27).

The high-temperature expansion. For the $d$-dimensional case, the state
equation of an ideal quantum gas is [40, 41]

$\displaystyle p$
$\displaystyle=\frac{kT}{\lambda^{d}}h_{1+d/2}\left(z\right),$ (6.11)
$\displaystyle\frac{N}{V}$
$\displaystyle=\frac{1}{\lambda^{d}}h_{d/2}\left(z\right).$ (6.12)

The virial expansion [40, 41] directly gives

$\frac{pV}{N}\sim kT\left[1+ga_{1}\left(T\right)n\lambda^{d}+...\right]$
(6.13)

Substituting Eqs. (6.11) and (6.12) into Eq. (6.13) gives

$\frac{h_{1+d/2}\left(z\right)}{h_{d/2}\left(z\right)}\sim\left[1+ga_{1}\left(T\right)n\lambda^{d}+...\right].$
(6.14)

Substituting Eq. (6.14) into Eq. (3.27) gives Eq. (3.28).

The low-temperature expansion for Fermi cases. For Fermi cases, $g=-1$,

$\frac{h_{1+d/2}\left(z\right)}{h_{d/2}\left(z\right)}=\frac{f_{1+d/2}\left(z\right)}{f_{d/2}\left(z\right)}.$
(6.15)

By the expansion of the Fermi-Dirac integral at large $z$, we have [41]

$f_{\nu}\left(e^{\xi}\right)=\frac{\xi^{\nu}}{\Gamma\left(1+\nu\right)}\left\\{1+2\nu\sum_{j=1,3,5,...}\left[\left(\nu-1\right)....\left(\nu-j\right)\left(1-2^{-j}\right)\frac{\zeta\left(j+1\right)}{\xi^{j+1}}\right]\right\\}.$
(6.16)

Keeping only the first two terms gives

$f_{\nu}\left(z\right)=\frac{\left(\ln
z\right)^{\nu}}{\Gamma\left(1+\nu\right)}+2\nu\left(\nu-1\right)\frac{1}{2}\frac{\zeta\left(2\right)}{\left(\ln
z\right)^{2}}.$ (6.17)

Substituting Eq. (6.17) into Eqs. (6.11) and (6.12) gives

$\displaystyle\frac{p}{kT}$
$\displaystyle=\frac{1}{\lambda^{d}}\frac{\left(\ln
z\right)^{1+d/2}}{\Gamma\left(2+d/2\right)}\left[1+\frac{d}{2}\left(1+\frac{d}{2}\right)\frac{\zeta\left(2\right)}{\left(\ln
z\right)^{2}}\right],$ (6.18) $\displaystyle N$
$\displaystyle=\frac{\Omega}{\lambda^{d}}\frac{\left(\ln
z\right)^{d/2}}{\Gamma\left(1+d/2\right)}\left[1+\frac{d}{2}\left(\frac{d}{2}-1\right)\frac{\zeta\left(2\right)}{\left(\ln
z\right)^{2}}\right],$ (6.19)

where $\Omega$ is the volume. The fugacity can be solved from Eq (6.19):

$\ln
z\sim\frac{\epsilon_{f}}{kT}\left[1-\zeta\left(2\right)\left(\frac{d}{2}-1\right)\left(\frac{kT}{\epsilon_{f}}\right)^{2}\right],$
(6.20)

where
$\epsilon_{f}=\lambda^{2}kT\left[\frac{1}{2}\Gamma\left(1+\frac{d}{2}\right)n\right]^{2/d}$
is the Fermi energy. By substituting Eq. (6.17) into Eq. (6.15) with fugacity
$z$ given by Eq. (6.20), we have

$\frac{f_{1+d/2}\left(z\right)}{f_{d/2}\left(z\right)}=\frac{\Gamma\left(1+\frac{d}{2}\right)}{\Gamma\left(2+\frac{d}{2}\right)}\frac{\epsilon_{f}}{kT}\left\\{1+\left[\frac{d\zeta\left(2\right)}{2}+\zeta\left(2\right)\right]\left(\frac{kT}{\epsilon_{f}}\right)^{2}\right\\}.$
(6.21)

Substituting Eq. (6.21) into Eq. (3.27) gives Eq. (3.29).

The low-temperature expansion for Bose cases in the $2$-dimensional space. For
Bose cases, $g=1$,

$\frac{h_{2}\left(z\right)}{h_{1}\left(z\right)}=\frac{g_{2}\left(z\right)}{g_{1}\left(z\right)},$
(6.22)

where $d=2$. For $d=2$,

$g_{1}\left(z\right)=-\ln\left(1-z\right).$ (6.23)

Substituting Eq. (6.23) into Eq. (6.12) gives

$\frac{N}{V}=-\frac{1}{\lambda^{2}}\ln\left(1-z\right).$ (6.24)

Then, the fugacity can be solved from Eq (6.24):

$z=1-\exp\left(-n\lambda^{2}\right).$ (6.25)

Expanding $g_{2}\left(z\right)$ around $z=1$ gives

$\displaystyle g_{2}\left(z\right)$
$\displaystyle=\frac{\pi^{2}}{6}-\left(1-z\right)-\frac{\left(1-z\right)^{2}}{2^{2}}-\frac{\left(1-z\right)^{3}}{3^{2}}-\ldots$
$\displaystyle+\left(1-z\right)\ln\left(1-z\right)+\frac{\left(1-z\right)^{2}}{2}\ln\left(1-z\right)+\frac{\left(1-z\right)^{3}}{3}\ln\left(1-z\right)+\ldots$
(6.26)

Substituting Eqs. (6.26) and (6.23) with fugacity given in Eq. (6.25) into Eq.
(6.22) gives

$\frac{g_{2}\left(z\right)}{g_{1}\left(z\right)}=-\exp\left(-n\lambda^{2}\right)-\frac{\exp\left(-n\lambda^{2}\right)}{n\lambda^{2}}+\frac{\pi^{2}}{6n\lambda^{2}},$
(6.27)

Substituting Eq. (6.27) into Eq. (3.27) gives Eq. (3.30).

## Acknowledgments

We are very indebted to Dr G. Zeitrauman for his encouragement. This work is
supported in part by NSF of China under Grant No. 11575125 and No. 11675119.

## References

  * [1] R. M. Mazo, Brownian motion: fluctuations, dynamics, and applications, vol. 112.  Oxford University Press on Demand, 2002.
  * [2] P. Hänggi and F. Marchesoni, Introduction: 100 years of brownian motion, 2005.
  * [3] L. Diosi, Quantum master equation of a particle in a gas environment, EPL (Europhysics Letters) 30 (1995), no. 2 63.
  * [4] W.-S. Dai and M. Xie, The explicit expression of the fugacity for weakly interacting bose and fermi gases, Journal of Mathematical Physics 58 (2017), no. 11 113502.
  * [5] W.-S. Dai and M. Xie, Interacting quantum gases in confined space: Two-and three-dimensional equations of state, Journal of Mathematical Physics 48 (2007), no. 12 123302.
  * [6] W. Dai and M. Xie, Hard-sphere gases as ideal gases with multi-core boundaries: An approach to two- and three-dimensional interacting gases, EPL (Europhysics Letters) 72 (2005), no. 6 887.
  * [7] C.-C. Zhou and W.-S. Dai, Canonical partition functions: ideal quantum gases, interacting classical gases, and interacting quantum gases, Journal of Statistical Mechanics: Theory and Experiment 2018 (2018), no. 2 023105.
  * [8] X. Bian, C. Kim, and G. E. Karniadakis, 111 years of brownian motion, Soft Matter 12 (2016), no. 30 6331–6346.
  * [9] A. S. Bodrova, A. V. Chechkin, A. G. Cherstvy, and R. Metzler, Ultraslow scaled brownian motion, New Journal of Physics 17 (2015), no. 6 063038\.
  * [10] K. Huang and I. Szlufarska, Effect of interfaces on the nearby brownian motion, Nature communications 6 (2015) 8558.
  * [11] S. Gür and K. Pötzelberger, Sensitivity of boundary crossing probabilities of the brownian motion, Monte Carlo Methods and Applications 25 (2019), no. 1 75–83.
  * [12] H. Safdari, A. G. Cherstvy, A. V. Chechkin, F. Thiel, I. M. Sokolov, and R. Metzler, Quantifying the non-ergodicity of scaled brownian motion, Journal of Physics A: Mathematical and Theoretical 48 (2015), no. 37 375002.
  * [13] J.-H. Jeon, A. V. Chechkin, and R. Metzler, Scaled brownian motion: a paradoxical process with a time dependent diffusivity for the description of anomalous diffusion, Physical Chemistry Chemical Physics 16 (2014), no. 30 15811–15817.
  * [14] M. Carlesso and A. Bassi, Adjoint master equation for quantum brownian motion, Physical Review A 95 (2017), no. 5 052119.
  * [15] U. Weiss, Quantum dissipative systems, vol. 13.  World scientific, 2012.
  * [16] J.-F. Le Gall, Brownian motion, martingales, and stochastic calculus, vol. 274.  Springer, 2016.
  * [17] K. Kanazawa, T. Sueshige, H. Takayasu, and M. Takayasu, Derivation of the boltzmann equation for financial brownian motion: Direct observation of the collective motion of high-frequency traders, Physical review letters 120 (2018), no. 13 138301.
  * [18] A. Gairat and V. Shcherbakov, Density of skew brownian motion and its functionals with application in finance, Mathematical Finance 27 (2017), no. 4 1069–1088.
  * [19] M. Kijima, Stochastic processes with applications to finance.  Chapman and Hall/CRC, 2016.
  * [20] Z. Yang and D. ALDOUS, Geometric brownian motion model in financial market, University of California, Berkeley (2015).
  * [21] C. Czichowsky, R. Peyre, W. Schachermayer, and J. Yang, Shadow prices, fractional brownian motion, and portfolio optimisation under transaction costs, Finance and Stochastics 22 (2018), no. 1 161–180.
  * [22] B. P. Rao, Pricing geometric asian power options under mixed fractional brownian motion environment, Physica A: Statistical Mechanics and its Applications 446 (2016) 92–99.
  * [23] E. Neuman, M. Rosenbaum, et al., Fractional brownian motion with zero hurst parameter: a rough volatility viewpoint, Electronic Communications in Probability 23 (2018).
  * [24] P. Romanczuk, M. Bär, W. Ebeling, B. Lindner, and L. Schimansky-Geier, Active brownian particles, The European Physical Journal Special Topics 202 (2012), no. 1 1–162.
  * [25] X. Ao, P. K. Ghosh, Y. Li, G. Schmid, P. Hänggi, and F. Marchesoni, Active brownian motion in a narrow channel, The European Physical Journal Special Topics 223 (2014), no. 14 3227–3242.
  * [26] B. Lindner and E. Nicola, Diffusion in different models of active brownian motion, The European Physical Journal Special Topics 157 (2008), no. 1 43–52.
  * [27] W. Ebeling and L. Schimansky-Geier, Swarm dynamics, attractors and bifurcations of active brownian motion, The European Physical Journal Special Topics 157 (2008), no. 1 17–31.
  * [28] P. Pietzonka, K. Kleinbeck, and U. Seifert, Extreme fluctuations of active brownian motion, New Journal of Physics 18 (2016), no. 5 052001\.
  * [29] J.-P. Bouchaud and A. Georges, Anomalous diffusion in disordered media: statistical mechanisms, models and physical applications, Physics reports 195 (1990), no. 4-5 127–293.
  * [30] R. Metzler and J. Klafter, The random walk’s guide to anomalous diffusion: a fractional dynamics approach, Physics reports 339 (2000), no. 1 1–77.
  * [31] G. Sikora, K. Burnecki, and A. Wyłomańska, Mean-squared-displacement statistical test for fractional brownian motion, Physical Review E 95 (2017), no. 3 032110.
  * [32] R. Metzler, J.-H. Jeon, A. G. Cherstvy, and E. Barkai, Anomalous diffusion models and their properties: non-stationarity, non-ergodicity, and ageing at the centenary of single particle tracking, Physical Chemistry Chemical Physics 16 (2014), no. 44 24128–24164.
  * [33] A. Lampo, M. Á. G. March, and M. Lewenstein, Quantum brownian motion, in Quantum Brownian Motion Revisited, pp. 19–39.  Springer, 2019.
  * [34] H. Grabert, P. Schramm, and G.-L. Ingold, Quantum brownian motion: The functional integral approach, Physics reports 168 (1988), no. 3 115–207.
  * [35] A. O. Caldeira and A. J. Leggett, Path integral approach to quantum brownian motion, Physica A: Statistical mechanics and its Applications 121 (1983), no. 3 587–616.
  * [36] V. Ambegaokar, Quantum brownian motion and its classical limit, Berichte der Bunsengesellschaft für physikalische Chemie 95 (1991), no. 3 400–404.
  * [37] G. Ford and M. Kac, On the quantum langevin equation, Journal of statistical physics 46 (1987), no. 5-6 803–810.
  * [38] G. Lindblad, On the generators of quantum dynamical semigroups, Communications in Mathematical Physics 48 (1976), no. 2 119–130.
  * [39] B. Vacchini, Completely positive quantum dissipation, Physical review letters 84 (2000), no. 7 1374.
  * [40] L. Reichl, A Modern Course in Statistical Physics.  Physics textbook. Wiley, 2009.
  * [41] R. Pathria, Statistical Mechanics.  Elsevier Science, 2011.