\section{Modeling Encrypted Ping Pong}

To understand the individual contribution of Chopping and Multi-threading Encryption,
we model the performance of encrypted Ping Pong when (i) only Chopping is used, and (ii) only Multi-threading Encryption is used.
We then model the interaction of Chopping and Multi-threading Encryption in  CryptMPI's Ping Pong.
In our models, we assume that a sender can concurrently transmit the ciphertext of a message via a non-blocking send
and encrypt the next message. A receiver likewise can decrypt the current ciphertext while getting the next ciphertext via a non-blocking receive.

\heading{The Hockney model.}

\heading{Modeling Encryption-Decryption.}

\subsection{Ping Pong with Chopping}

\noskipheading{Model description.}
Suppose that we chop a message of~$m$ bytes into $s$-byte segments.
For simplicity, assume that $m$ is a multiple of $s$.
As the ciphertext segments are sent successively, the latency term $\alpha_{\mathrm{comm}}$ is only
manifest in the transmission of the last ciphertext segment.
Since the encryption of each $i$-th segment can overlap with the transmission of the
ciphertext of the $(i - 1)$-th  segment  for every $i \in \{ 2, \ldots, m / s\}$,
the time to encrypt and transmit the entire message is
\[
\frac{T_{\mathrm{enc}}(s)}{2} + \Bigl( \frac{m}{s} - 1\Bigr) \max\Bigl\{ \frac{T_{\mathrm{enc}}(s)}{2} , \beta_{\mathrm{comm}} \cdot s \Bigr\} + T_{\mathrm{comm}}(s) \enspace.
\]
During this time, the receiver can decrypt all but the last ciphertext,
 and thus it will need $\frac{T_{\mathrm{enc}}(s)}{2}$ additional time units to decrypt the last ciphertext.
Hence the total time is
\[
T_{\mathrm{enc}}(s) + \Bigl( \frac{m}{s} - 1\Bigr) \max\Bigl\{ \frac{T_{\mathrm{enc}}(s)}{2} , \beta_{\mathrm{comm}} \cdot s \Bigr\} + T_{\mathrm{comm}}(s) \enspace.
\]

\noskipheading{Discussion.}

\heading{Model validation.}

\subsection{Ping Pong with Multi-threading Encryption}

\noskipheading{Model description.}
Suppose that we use $t$ threads to encrypt a message of~$m$ bytes.
Assume that $m$ is a multiple of $t$.
Then the total time to encrypt~$t$ segments, transmit them, and then decrypt them is about
\[
T_{\mathrm{enc}}(t, m / t) + T_{\mathrm{comm}}(m) \enspace.
\]
If $t = 1$ then we get back the model of Naser et al.~\cite{Cluster:Naser19} for their vanilla implementation of encrypted Ping Pong.

\heading{Model validation.}

\subsection{Ping Pong under CryptMPI}

\noskipheading{Model description.} Suppose that we chop a message into $s$-byte segments,
and use $t$ threads to encrypt each segment. Assume that $m$ is a multiple of $s$, and $s$ is a multiple of $t$.
We model the latency of encrypted Ping Pong as
\[
T_{\mathrm{enc}}(t, s / t) + \Bigl( \frac{m}{s} - 1\Bigr) \max\Bigl\{ \frac{T_{\mathrm{enc}}(t, s/t)}{2} , \beta_{\mathrm{comm}} \cdot s \Bigr\} + T_{\mathrm{comm}}(s).
\]
This is essentially the model of Chopping's Ping Pong, where each $T_{\mathrm{enc}}(s)$ is replaced by $T_{\mathrm{enc}}(t, s/t)$.

\heading{Discussion.}

\heading{Model validation.}

\iffalse

\subsection{Privacy Analysis}

In our privacy threat model, an adversary passively collects network packets sent
from the MPI nodes and tries to infer partial information about the MPI program and input.\footnote{We assume that the MPI program does not have MPI\_Reduce or MPI\_Allreduce,
since $\textrm{CryptMPI}$ currently does not support these two routines.}
The adversary, however, does not have physical access to the machines.
This restriction eliminates side-channel attacks such as the rowhammer attack~\cite{rowhammer}.
Thanks to the semantic security of encryption~\cite{GM84,BDJR97},
the adversary cannot distinguish a ciphertext segment and a uniformly random string of the same length.
Despite encryption, the adversary still gets some \emph{metadata}
of the program and input: the message length,  the routine type
(Send, Broadcast, Scatter, or AlltoAll), and the execution timings.
$\textrm{CryptMPI}$ guarantees that the adversary does not learn anything beyond
what can be inferred from the metadata and the adversary's prior knowledge of the MPI program and input.

\subsection{Authenticity Analysis}

In our authenticity threat model, an adversary first requests the execution of an adversarial MPI program and input,
and then actively tries to modify the ciphertext segments
in the network packets without detection.
The adversary is, however, not allowed to launch a \emph{replay attack},
that is, it is forbidden from replacing the entire vector of ciphertext segments
$(C_1, \ldots, C_m)$ of $\bm{M} = (M_1, \ldots, M_m)$
by the entire vector of ciphertext segments of a prior message.\footnote{
This restriction is due to the fact that GCM is deterministic:
under the same key and nonce, encrypting the same message via GCM multiple times
will always result in the same ciphertext.}
The authenticity of $\textrm{CryptMPI}$ (assuming that Chopping GCM is used) follows directly from the authenticity of Chopping GCM.
We stress that $\textrm{CryptMPI}$ with $\textrm{FastCTR}$ offers no authenticity.

\fi
\section{Background}
\label{sec:backg}

\iffalse
\subsection{MPI}
Message Passing Interface (MPI) \cite{Forum:2012:MPI} is the de facto
standard for developing portable message passing programs and has been used
in developing a large number of parallel applications. MPI is standardized
in several versions. MPI-1 \cite{Forum:1994:MPI}
provides over 115 routines of point-to-point
communication, collective communication, communicator, process topologies,
environment management and profiling interface. MPI-2
\cite{Forum:2008:MPI} includes new
functionalities such as dynamic processes, one-sided communications, extended
collective operations, external interfaces, additional language bindings and
parallel I/O. MPI-3 \cite{Forum:2012:MPI}
further introduces new features for better supporting
applications including nonblocking collectives, neighborhood
collectives, and improved one-sided communication interface.

MPI point-to-point communication is the basic mechanism
for processors to communicate. It includes two main classes of operations:
sending and receiving. The communication can be either blocking or
nonblocking. In the blocking mode, the operations do not return until the
send buffer can be reused. In the nonblocking mode, the operations
return without waiting for the communication to complete.
The nonblocking mode provides an opportunity to hide communication latency and
overlap communication with computation.

MPI collective communication involves a group of processes.
Based on the sending members and receiving members in the group, it can
be categorized into one-to-all, all-to-one, all-to-all, and synchronization
operations. Broadcast and scatter belongs to one-to-all;
gather and reduce are all-to-one operations; alltoall, allgather and
allreduce are categorized as all-to-all operations; barrier synchronizes
across all processes in the group.

Two MPI libraries, MPICH2 \cite{Gropp:2002:MPICH2}
and Open MPI \cite{Graham:2005:openMPI} are in the public domain and
have been widely used. Our work is built upon MPICH2. We modify the source code
to add efficient support for security mechanisms for commonly used
point-to-point
and collective routines, including MPI\_Send, MPI\_Isend, MPI\_Recv,
MPI\_Irecv, MPI\_Wait, MPI\_Waitall, MPI\_Test, MPI\_Alltoall, MPI\_Allgather,
MPI\_Bcast, and MPI\_Init. We have also modified the MPI progress engine to
support the functionality.

\fi

\noskipheading{Blockciphers.} A blockcipher on message space ${\mathcal M}$ and \allowbreak
keyspace~$\mathcal{K}$ is a function
$E: \mathcal{K} \times {\mathcal M} \to {\mathcal M}$ such that for every key $K \in \mathcal{K}$, the function $E_K(\cdot) = E(K, \cdot)$ is
a permutation on~${\mathcal M}$.
A typical blockcipher is AES.

\heading{Symmetric Encryption.}  Syntactically, a (symmetric) encryption scheme is a triple of algorithms
$(\texttt{Gen}, \texttt{Enc}, \texttt{Dec})$. Initially, the sender and receiver need to share a secret key~$K$
that is generated by~$\texttt{Gen}$.
Each time the sender wants to encrypt a message $M$, she creates a ciphertext $C$ via
$C \gets \texttt{Enc}(K, M)$.
Upon receiving~$C$, the receiver decrypts via $M \gets \texttt{Dec}(K, C)$.
An encryption scheme is often built upon a blockcipher such as~AES.

Traditionally, an encryption scheme's only goal is to deliver \emph{privacy},
meaning that an adversary cannot distinguish the ciphertexts of its chosen messages
with those of uniformly random strings of the same length.
Several standard encryption methods, such as
the Cipher Block Chaining (CBC) mode or Counter (CTR) mode~\cite{NIST:38A}
fail to provide  \emph{integrity} (meaning that the adversary cannot modify ciphertexts without being detected).\footnote{Actually,
an adversary may still replace a ciphertext by an old one; this is known as a \emph{replay attack}.
We do not consider replay attacks in this work.
}
In this work, we focus on the Galois Counter Mode (GCM)~\cite{NIST:38D}.
GCM is the fastest standard encryption method that \emph{provably} provides both privacy and integrity~\cite{McGrew:2004:SPG:2158177.2158215}.

\smallskip

\noskipheading{GCM overview.} GCM is a \emph{nonce-based} encryption scheme.
Each time the sender encrypts, she needs to provide a 12-byte \emph{nonce}~$N$, a string that should never repeat,
to produce a ciphertext $C \gets \texttt{Enc}(K, N, M)$.
Conventionally, a GCM nonce is implemented as a counter or a uniformly random string.
Each ciphertext $C$ is 16-byte longer than the corresponding message $M$
as it includes a 16-byte tag for integrity checking.
The sender then needs to transmit both the ciphertext $C$ and the nonce $N$ to the receiver.
The latter then decrypts via $M \gets \texttt{Dec}(K, N, C)$.
Thanks to its speed and provable security, GCM is widely used in network protocols,
such as SSH, IPSec, and TLS.

According to NIST standard SP 800-38D~\cite{NIST:38D},
the blockcipher of GCM must be AES; we  often write AES-GCM
to refer to an instantiation of GCM with AES as the blockcipher.
There are three corresponding key sizes for AES: 128, 192, or 256 bits.
Longer key length means better security against brute-force attacks,
at the cost of slower execution time.
In this work we only consider 128-bit keys to achieve the best possible performance.

\heading{Public-key Encryption.} Public-key encryption (PKE) is analogous to symmetric-key encryption,
but the (public) encryption key is different from the (secret) decryption key.
Standard PKE scheme (such as RSA~\cite{RSA}) are more expensive than standard symmetric-encryption schemes (such as GCM)
by several orders of magnitude.
One therefore often just uses PKE to distribute, say a shared GCM key,
and then switches to GCM encryption.
In this work, we use the OAEP method of RSA~\cite{OAEP},
which is \emph{provably} secure.

\iffalse
RSA~\cite{RSA} is  the most well-known PKE scheme,
but there are a few RSA variants and some of them are terribly insecure.
Textbook RSA, for example, is subject to a number of attacks~\cite[Chapter 11.5.1]{Book:KL14}.
The most widely-used version of RSA, known as PKCS\#1 v1.5,
is the default choice  of RSA in the popular cryptographic library OpenSSL~\cite{openssl}.
But this scheme is vulnerable to the notorious padding-oracle attack~\cite{padding}
that which still plagues the Internet today~\cite{9CAT}.
\fi

\section{Conclusion}
\label{sec:conclu}

Achieving high performance for encrypted MPI communication is challenging
since the encryption and decryption operations are the bottlenecks of
encrypted communication in modern platforms. In this work, we present
$\textrm{CryptMPI}$, a fast encrypted MPI library. By incorporating
various optimization techniques for large messages,
$\textrm{CryptMPI}$ significantly improves
the performance of the naive approach to support MPI communication
with privacy and integrity. The evaluation on two platforms indicates
that the proposed techniques are more effective when the
network speed is significantly higher than single-core encryption
performance, a likely scenario in the future.

A limitation of this work is to consider only one-to-one communication.
We are currently developing techniques to deal with collective operations
in $\textrm{CryptMPI}$.

\section{Introduction}

\iffalse
High performance computing (HPC) applications that process
sensitive data, such as medical, financial, and engineering documents have
to meet stringent security requirements. In order for such applications to execute in
the public cloud environment, it is imperative that the cloud infrastructure
supports both privacy and integrity. Many HPC applications utilize the Message
Passing Interface (MPI) library, the de facto library for message
passing applications. For MPI applications to run with security
guarantees in the public cloud environment, mechanisms must be
incorporated to support privacy and integrity in MPI communication.

Existing efforts to retrofit MPI libraries with encryption, however,
have introduced severe security flaws. For example,
ES-MPICH2~\cite{Ruan:2012:EMP:2197079.2197242}, the first such MPI library,
uses the weak ECB (Electronic Codebook) mode of operation that has known
vulnerabilities~\cite[page 89]{Book:KL14}.
In addition, no existing encrypted MPI libraries provide meaningful data
integrity, meaning that data could potentially be modified without being
detected. Consequently, it is urgent to revisit the problem by applying
the state-of-the-art theory and practice to properly
encrypt MPI communications.

The advances in the networking technology for data centers
have shifted the communication
bottleneck from network links to network end points.
Even with the
state-of-the-art processor hardware support for cryptographic operations
(e.g., Intel AES-NI instructions to accelerate the AES algorithm,
or the x86 CLMUL instruction set to improve the speed of finite-field
multiplications), the computationally intensive encryption and decryption
operations can still introduce very high overheads and limit the
performance of secure MPI communication.
\fi

High Performance Computing (HPC) applications are often used to process
sensitive data, such as medical, financial, or scientific documents.
In the past, HPC jobs were run in trusted local clusters of no external access,
and security was taken for granted.
But the current trend of moving everything to the cloud has upended this assumption,
introducing unprecedented security challenges to HPC.
This paper aims to partially address this problem
in the context of Message Passing Interface (MPI) environment, which is the de facto library for
message-passing applications.

To ensure privacy and integrity of sensitive data,
an obvious solution is to encrypt MPI communication.
The easiest way to do that is to rely on existing encryption mechanisms at lower levels,
such as IPSec.
This approach allows one to encrypt MPI communication without modifying the MPI library.
The second option is to naively incorporate  encryption to the MPI library
by encrypting the whole message at the sender side, transmitting
the entire ciphertext, and decrypting the ciphertext at the
receiving side~\cite{Cluster:Naser19}.

\figref{fig:ipsec} illustrates the performance of the unencrypted baseline,
IPSec, and our library CryptMPI on a 10 Gbps Ethernet network.
Although IPSec and CryptMPI rely on the same underlying encryption scheme,
the performance of the former is far worse.
In particular, the throughput that can be achieved by IPSec is only a small
fraction of the raw network throughput. In
our system, IPSec only achieves about one-third of the network throughput
for 1MB messages. Moreover, IPSec sequentializes encrypted communication
when there are multiple concurrent flows in the system. As shown
in \figref{fig:ipsec}, the aggregate throughput remains the same
when the number of concurrent flows increases from one to~four.

\begin{figure}[t]
    \centering

      \includegraphics[width=0.4\textwidth]{graphs/ipsec-1MB.eps}%
    \vspace{-1.5ex}
    \captionsetup{singlelinecheck=false}
    \caption{Motivating example: IPSec throughput on 10Gbps Ethernet
      with multiple concurrent flows and 1MB messages.}
    \label{fig:ipsec}
    \vspace{-1.5ex}

    \end{figure}

Several prior works~\cite{Cluster:Naser19,Ruan:2012:EMP:2197079.2197242,Maffina2013,RTSJ16,Shivaramakrishnan2014}
instead opt for naively adding encryption to the MPI library.
But except for the recent work of Naser et al.~\cite{Cluster:Naser19},
all other prior systems contain severe security flaws.
For example, ES-MPICH2~\cite{Ruan:2012:EMP:2197079.2197242}, the first encrypted MPI library,
uses the weak ECB (Electronic Codebook) mode of operation that has known
vulnerabilities~\cite[page 89]{Book:KL14}.

Even if one correctly implements the naive approach of adding encryption to the MPI library
as in~\cite{Cluster:Naser19}, this route is doomed to give very unsatisfactory performance,
due to recent advances in the networking technology for data centers.
\figref{fig:motivate} compares the communication performance of
unencrypted MPI library (MVAPICH) with the naive method
using the AES-GCM encryption scheme with a 128-bit key on a cluster with 40Gbps InfiniBand
in the Ping-Pong setting.
As shown in \figref{fig:motivate},  naively adding encryption can incur very high overheads.
For example, when the message size is 1MB, the throughput
drops from 3.0 GBps for unencrypted communication
to 1.2GBps for encrypted one.

\begin{figure}[t]
\centering
\vspace{-2.5ex}
\includegraphics[width=0.4\textwidth]{graphs/motivation.eps}
\vspace{-1.5ex}
\caption{Motivating example: the one-way throughput by naively incorporating
AES-GCM with a 128-bit key into MVAPICH.}
\label{fig:motivate}
\vspace{-3.0ex}
\end{figure}

The results above show that in today's data centers, even with the
state-of-the-art processor hardware support for cryptographic operations
(e.g., Intel AES-NI instructions to accelerate the AES algorithm,
or the x86 CLMUL instruction set to improve the speed of finite-field
multiplications), the overheads of encryption
can easily dominate the encrypted communication time. This calls
for a careful design of an encrypted MPI library so as to exploit the
computing power at end-nodes and to minimize
the encryption  overheads. Compute nodes in modern systems
usually have lots of CPU cores with Hyper-Threading
Technology (HTT).
For instance, each node of the world's fastest supercomputer Summit
supports 176 hyper-threads~\cite{summit},
meanwhile a single processor~\cite{amdryzen} of AMD has
128 hyper-threads. These imply that in the very near future compute nodes will
be equipped with more hyper-threads than what applications can use.
$\textrm{CryptMPI}$ targets this type of systems by leveraging hyper-threads to deliver
higher performance.

In this work, we introduce $\textrm{CryptMPI}$, a
high-performance encrypted MPI library. $\textrm{CryptMPI}$ encrypts MPI communication under AES-GCM,
providing both integrity and privacy. Since encryption overheads are relatively small for small messages~\cite{Cluster:Naser19},
this work focuses on optimizing the point-to-point communication performance for large messages.
$\textrm{CryptMPI}$ employs a technique to maintain the required security properties while allowing the
communication and encryption to be pipelined and be performed by multiple threads. Moreover,
by using an accurate performance model for Ping Pong experiments,
$\textrm{CryptMPI}$ automatically derives the parameters used at runtime for each communication, such
as the number of threads
and the size of each chunk of data in
pipelined encrypted communication.
We will describe the techniques in $\textrm{CryptMPI}$ and report our benchmarking
results, which demonstrates that our methods are effective in achieving fast encrypted
MPI communication.

The rest of the paper is structured as follows. Section~\ref{sec:related}
discusses the related work. Section~\ref{sec:backg}
introduces the background of this work.
Section~\ref{sec:oursystem} presents our system. Section~\ref{sec:perf}
reports
the results of our performance study. Finally, Section~\ref{sec:conclu}
concludes the paper.

\iffalse

As a motivation to the techniques that we introduce in our high-performance
secure MPI library, $\textrm{CryptMPI}$, let us first examine two simpler options for
supporting secure MPI communication. The first option is to rely on
the existing
security mechanism such as IPSec at the lower level. Using IPSec, secure
MPI communication can be achieved without modifying the MPI library.
The second option is to naively incorporate the security mechanism in the MPI
library by encrypting the whole message at the sender side, transmitting
the whole message, and decrypting the message at the
receiving side \cite{Cluster:Naser19}.

Figure~\ref{fig:ipsec} shows the comparison between unencrypted baseline,
IPSec, and CryptMPI on 10 Gb/s Ethernet network. This figure highlights
the performance issues with IPSec. First, the throughput that can be
achieved by IPSec is only a small
fraction of the raw network throughput. In
our system, IPSec only achieves about one-third of the network throughput
for 1MB messages. Second, IPSec sequentializes secure communication
when there are multiple concurrent flows in the system. As shown
in Figure~\ref{fig:ipsec}, the aggregate throughput remains the same
when the number of concurrent flow increases from 1 to 4.
These limitations call for developing techniques
that can take advantage of the increasing computing power
at the end points to support secure communication.

\begin{figure}[b]
    \centering
    \vspace{-2.5ex}
      \includegraphics[width=0.35\textwidth]{graphs/ipsec-1MB.eps}%
    \captionsetup{singlelinecheck=false}
    \caption{Motivating example: IPSec throughput on 10G Ethernet
      with multiple concurrent flows and 1MB message size}
    \label{fig:ipsec}
    \vspace{-1.5ex}

    \end{figure}

Figure~\ref{fig:motivate} compares the communication performance of
unencrypted MPI library (MVAPICH) with the naive method
using AES GCM with a 128-bit key on a cluster with 40Gbps InfiniBand.
The one-way throughput is measured using the ping-pong program.
As can be seen from the figure, naively introducing the security
mechanism can incur very high overheads. For example,
when the message size is 1MB, the throughput
drops from 3.0GBps for unencrypted communication
to 1.2GBps for encrypted communication. These results show that in
today's data centers, the overheads of encryption and decryption
can easily dominate the secure communication time. This calls
for a careful design of the secure MPI library so as to exploit the
computing power at end-nodes and to minimize
the encryption and decryption overheads.

\begin{figure}[t]
\centering
\vspace{-2.5ex}
\includegraphics[width=0.4\textwidth]{graphs/motivation.eps}
\caption{Motivating example: the one-way throughput by naively incorporating
AES GCM with a 128-bit key into MVAPICH}
\label{fig:motivate}
\vspace{-2.5ex}
\end{figure}

Both of the two simpler methods have performance issues.
In particular, there are situations when the secure communication
time will be dominated by the encryption and decryption time, which means that
any further improvement of the network speed will not help in the
performance of secure communication in those situations. To overcome
these limitations, we introduce $\textrm{CryptMPI}$, a
high-performance secure MPI library. $\textrm{CryptMPI}$ uses AES GCM to support
communication with integrity and privacy. Since the encryption and
decryption overhead is relatively small for small messages
\cite{Cluster:Naser19}, this work focuses on optimizing the
point-to-point communication performance for large messages.
$\textrm{CryptMPI}$ incorporates
various optimization techniques including overlapping communication
with computation, pipelined communication, and dynamic multi-threading.
We will describe the techniques used in $\textrm{CryptMPI}$ and report our benchmarking
results, which demonstrate that the techniques are effective in achieving high
secure MPI communication performance.

The rest of the paper is structured as follows. Section~\ref{sec:related}
discusses the related work. Section~\ref{sec:backg}
introduces the background of this work.
Section~\ref{sec:oursystem} presents our system. Section~\ref{sec:perf}
reports
the results of our performance study. Finally, Section~\ref{sec:conclu}
concludes the paper.

\fi

\section{\textrm{CryptMPI}: A Fast Encrypted MPI Library}
\label{sec:oursystem}

$\textrm{CryptMPI}$ supports encrypted MPI communication via AES-GCM from the BoringSSL library~\cite{boringssl}.
It is implemented on top of MVAPICH2-2.3.2 for systems with
InfiniBand and Omni-path-based interconnects.

Our starting point is the vanilla implementation of Naser et al.~\cite{Cluster:Naser19}.
Since encryption overheads are relatively low
for point-to-point communication of small messages \cite{Cluster:Naser19},
this work focuses on optimizing point-to-point communication of
large messages (meaning 64KB and beyond).
The following MPI routines are modified: $\texttt{MPI\_Send} $, $\texttt{MPI\_Recv} $, $\texttt{MPI\_ISend} $, $\texttt{MPI\_IRecv} $, $\texttt{MPI\_Wait} $, and $\texttt{MPI\_Waitall} $.

To achieve high performance,
$\textrm{CryptMPI}$ incorporates two optimization techniques:
pipelining and multi-threading.
Integrating those with encryption without compromising security is challenging.
We resolved that by using theory from streaming encryption~\cite{C:HRRV15} and Google's Tink library~\cite{tink}.
It is also nontrivial to decide the values of the parameters of those optimizations---for example, the number of threads in multi-threading---for
maximizing the performance.
To find the best choice of the parameters, we developed a
performance model for
the parameterized version of CryptMPI in the ping-pong setting.
CryptMPI then uses that model to derive the values for the parameters that
maximize the ping-pong performance for each communication.
Empirical results confirm that these are also good choices in
other settings.

\iffalse
and trained it with experiment results from common benchmarks
(in particular, ping pong benchmark for unencrypted MPI communication,
and throughput benchmarks for multi-threading encryption).
\fi

Below, we will first describe our threat model,
and then discuss the details of the optimization techniques.
For the convenience of discussion,
we will adopt the following notation.
Let $\{0,1\}^n$ be the set of $n$-bit binary strings,
and let $x {\,\|\,} y$
denote the concatenation of the two strings $x$ and~$y$.
For an integer $r$, we write $[x]_r$ to denote a $r$-byte encoding
of a string~$x$.

\iffalse
Integrating all of these techniques and AES-GCM in one system
results in complications in maintaining the AES-GCM's security features as well
as challenges in deciding important parameters for communications
(e.g. the segment size for pipelining and the number of threads
in multi-threading). $\textrm{CryptMPI}$ uses performance benchmarking results from
common benchmarks to set important parameters for communication.
In the following, we will first describe the $\textrm{CryptMPI}$'s thread model,
and then present the details of the techniques.
\fi

\heading{Threat model.}
Under our model, we consider an external
adversary that can observe and tamper with network packets.
We however assume that compute nodes are secure.
As a result, $\textrm{CryptMPI}$ only encrypts inter-node communication.

\heading{Pipelining.}
A reason for the high encryption overhead in the vanilla
implementation of Naser et al.~\cite{Cluster:Naser19}
is that the receiver has to wait for the sender to
encrypt the \emph{entire} message. A simple solution is to chop the
message into multiple segments, and encrypt and transmit them individually, which
results in pipelining the tasks in  the sender and receiver.
Under this approach, the receiver can start decrypting as soon as the
first ciphertext segment arrives. Hence, with pipelining, message transmission,
encryption, and decryption can all be overlapped.

The pipelining method above however breaks the authenticity of GCM:
the adversary can reorder the ciphertext segments of a message,
or even drop some of them without detection. This is a known issue for
streaming authenticated encryption~\cite{C:HRRV15}.
The treatment, suggested by~\cite{C:HRRV15},  is to embed the following
information in the nonce:
(i) a flag to indicate whether the segment is the last one
for the given message, and (ii) a counter to specify the position of the current segment within the given message.
Typically one uses one byte to encode the flag, and four bytes for the counter.
This approach is, however, problematic in our context.
In particular, if we pick the seven-byte remainder of a GCM nonce as a random string,
then we will be likely to have nonce repetition after encrypting just $2^{28}$ messages,
due to the well-known Birthday Problem.\footnote{
The Birthday Theorem (see, for example, \cite[Appendix A.4]{Book:KL14}) states that if we sample $q$ elements $x_1, \ldots, x_q$ uniformly and independently from a set of size $N$,
for $q \leq \sqrt{2N}$,
then the chance that there are some $i \ne j$ such that $x_i = x_j$ is at least $q(q - 1) / 4N$.}

To resolve the issue above, we adopt the approach in Google's
library Tink~\cite{tink} to use a different \emph{subkey} for each message, but our key derivation method is simpler.
Specifically, to encrypt a message $\bm{M}$ under a master key~$K$,
we first pick a 128-bit random seed $V$, and derive a subkey $L \gets \mathrm{AES}_K(V)$.
We then use GCM with key $L$ to encrypt the segments of~$\bm{M}$,
with the nonces following the suggestion in~\cite{C:HRRV15}.
The seed $V$ and the message length $|\bm{M}|$ will be sent together with the first ciphertext segment.
\iffalse
In many-to-many setting, senders will pick their seeds independently,
but for efficiency, each sender will use the same seed for all receivers.
To ensure that nonces for the same subkey are distinct,
we include a  unique \emph{ranking}~$R$ of the receiver in the nonce.
In one-to-one setting, one can set $R \gets 0$,
but in one-to-many or many-to-many setting,
we will pick $R$ as the MPI rank of the corresponding receiver.
\fi

The pseudocode of our encryption method  is given in Algorithm~\ref{algo:chop}.
In addition to the ciphertext segments, the ciphertext~$\boldsymbol{C}$ consists of a header
that provides the seed $V$, the length of the message $\bm{M}$, and the size of a message segment.
In implementation, the computation of $\boldsymbol{C} = (\textsl{Header}, C_1, \ldots, C_t)$
will be interleaved with non-blocking communication
so that the receiver can start decrypting $C_i$ while the sender is still encrypting or sending~$C_{i + 1}$.

\iffalse
\footnote{
In the context of streaming encryption, one does not need to include the message length in the header,
as the flag in nonces can inform the receiver whether it receives the last segment.
However, MPI environment requires the receiver to know the message length at the beginning.
While the header is not authenticated, the receiver will eventually learn the correct length of the message.
}
\fi

\iffalse
Note that putting the message size in the $\textsl{Header}$ also
resolves the issue with the mis-match sender message size and receiver message
size.

Tung: No, the header is not authenticated. The length is there because MPI requires it at the beginning,
but if you want to verify it, you have to wait at the very end.

\fi

\RestyleAlgo{boxed}
\IncMargin{1em}
\begin{algorithm}[h]

  \DontPrintSemicolon

  \SetKwFunction{alltoall}{MPI\_Alltoall}\SetKwFunction{nonce}{RAND\_bytes}

  \BlankLine
	\textbf{Input:} A message $\bm{M}$ of $m$ bytes. \;
	\textbf{Parameter:} A key $K$, and an integer $t$  \;

Pick a 16-byte random seed $V$ \;
\tcc{Derive a subkey $L$}
$L \gets \mathrm{AES}_K(V)$ \\
$s \gets \lceil m / t \rceil$;~ $\textsl{Header} \gets (V, m, s)$ \;
\tcc{Chop $\bm{M}$ into $t$ segments}
  $(M_1, \ldots, M_t) \gets \bm{M}$ \;
\tcc{Encrypt each segment}
\For{$i\gets 1$ \KwTo $t$}{
\textbf{if } $i = m$ \textbf{then } $\textsl{last} \gets 1$ \textbf{else } $\textsl{last} \gets 0$   \;
$N_i \gets [0]_7 {\,\|\,} [\textsl{last}]_1 {\,\|\,} [i]_4$;~ $C_i \gets \texttt{Enc}(L, N_i, M_i)$ \;
}
\Return $(\textsl{Header}, C_1, C_2\ldots, C_t)$
\caption{How to chop and encrypt a message~$\bm{M}$ under master key $K$.
Here
$\texttt{Enc}(L, N, M)$ denotes the use of GCM to encrypt a message $M$ under nonce $N$ and key $L$.
 }\label{algo:chop}

\end{algorithm}\DecMargin{1em}

When the receiver gets the header, it
derives the number of segments $t$ that it needs to decrypt from the segment size~$s$
and the message size $m$.
\iffalse
Then for each ciphertext segment $C_i$, it decrypts via GCM with key $L$ and the
nonce $N_i \gets [0]_7 {\,\|\,} [\textsl{last}]_1 {\,\|\,} [i]_4$, where the bit $\textsl{last}$ is $1$
if $C_i$ is supposed to be the last segment, and $\textsl{last} = 0$ otherwise.
\fi
Later, if GCM decryption flags some ciphertext segment as invalid,
or if the receiver does not get the correct number of ciphertext segments,
it will report a decryption failure.
In particular, if an adversary tampers with the header then thanks to the integrity property of GCM,
this will result in a decryption failure.

A very recent paper by Hoang and Shen~\cite{CCS:HS20}
gives a proof for the security of  a generalized version of the encryption in Google's library Tink
that also covers our approach.
Under the analysis in~\cite{CCS:HS20}, our encryption scheme provides both privacy and integrity as long as
the 128-bit seeds are distinct,
which is very likely according to the following result.

\begin{proposition}
Suppose that we sample $q$ seeds $V_1, \ldots, V_q$ uniformly at random from $\{0,1\}^{128}$.
Then the chance that they are distinct is at least $1 - q^2 / 2^{129}$.
\end{proposition}
\begin{proof}
Since the seeds are sampled independently and uniformly random,
for every $i \ne j$, the chance that $V_i = V_j$ is at most $2^{-128}$.
Since there are ${q \choose 2} \leq q^2 /2$ pairs of seeds,
by the Union Bound, the chance that two seeds in some pair are the same is at most $q^2 / 2^{129}$.
\end{proof}

\iffalse
To justify the security of our method to derive subkeys,
we say that seeds $V_i$ and $V_j$ \emph{collide} if  $V_i = V_j$.
If there is no seed collision
and
AES is modeled as a \emph{pseudorandom function} (PRF)~\cite{GGM86}
then the derived subkeys are indistinguishable from independent, uniformly random keys.\footnote{
Informally, a (keyed) function $F: \mathrm{Keys} \times \mathrm{Dom} \to \{0,1\}^n$
is a PRF if for any efficient adversary and a uniformly random key $K \in \mathrm{Keys}$,
the outputs of $F(K, \cdot)$, even on adversarial inputs,
are indistinguishable from truly $n$-bit random strings.
AES is widely believed to be a PRF~\cite[page 225]{Book:KL14}.
}
The following result shows that the chance of seed collision is small.

\begin{proposition}
Suppose that we sample $q$ seeds $V_1, \ldots, V_q$ uniformly at random from $\{0,1\}^{128}$.
Then the chance of seed collision is at most $q^2 / 2^{129}$.
\end{proposition}
\begin{proof}
Since the seeds are sampled independently and uniformly random,
for every $i \ne j$, the chance that $V_i$ and $V_j$ collide is at most $2^{-128}$.
Since there are ${q \choose 2} \leq q^2 /2$ pairs of seeds,
by the Union Bound, the chance that there is some seed collision is at most $q^2 / 2^{129}$.
\end{proof}
\fi

\heading{Multi-threading encryption/decryption.} As shown
in \figref{fig:motivate},
there is a huge gap between single-core encryption speed and
MPI bandwidth.
Data in \figref{fig:motivate} are for a 40Gbps interconnect;
the situation is much worse for current generation HPC systems with 100Gbps interconnects.
On the other hand, modern machines may have many cores that MPI applications
do not fully utilize. A natural way to fill the gap is to
chop a message into $t$ segments,
and use $t$ threads to encrypt them simultaneously via Algorithm~\ref{algo:chop},
where $t$ is a parameter.
The header will be computed and sent first.
Then, each thread $i$ will compute the corresponding ciphertext segment~$C_i$,
and the entire $(C_1, \ldots, C_t)$ will be sent as a whole.

\heading{Putting things together: $(k, t)$-chopping algorithm.}  To combine pipelining and multi-threading,
we chop a message into $kt$ segments and encrypt them via Algorithm~\ref{algo:chop},
where $k$ and $t$ are parameters,
but the interleaving of encryption and communication is as follows.
\iffalse
In other words, each large message is chopped
into $k$ segments; each segment is communicated as a unit; the encryption
and decryption of a segment is performed by $t$ threads.
\fi
Again, the header will be computed and sent first.
Then, we will use $t$ threads to compute the first $t$-segment chunk $(C_1, \ldots, C_t)$ and send it as a whole,
and then compute  and send the next chunk $(C_{t + 1}, \ldots, C_{2t})$, and so on.
For convenience, we refer to this algorithm as \emph{$(k, t)$-chopping}.
Note that when $k = 1$ then the
$(k, t)$-chopping algorithm falls back to basic multi-threading encryption (namely using
$t$ threads to encrypt the message),
and when $t = 1$, it corresponds to the special case where only pipelining is used.

Still, GCM encryption is somewhat slow for tiny messages.
The encryption speed, however, gathers momentum quickly and gets saturated at around 32 KB.
CryptMPI, therefore,
uses the $(k, t)$-chopping algorithm only if the message size is at least 64KB.
For small messages, we will directly encrypt via GCM so that we do not waste time in deriving subkeys.
To simplify the decryption process, we will still create a header when encrypting a small message;
here a 12-byte nonce will be included instead of a 16-byte random seed.
Headers will additionally contain an opcode to inform receivers of the encryption algorithm.

We stress that one needs to maintain \emph{two} separate keys, one for Algorithm~\ref{algo:chop} to encrypt large messages,
and another for direct GCM encryption of small messages.
Violating this key separation will break security.
To see why, suppose that we use a single key $K$ for encrypting messages of all sizes,
and suppose that at some point we encrypt a known 16-byte message $X$ directly via GCM under a random nonce~$N$.
The resulting ciphertext consists of $\mathrm{AES}_K(V) {\oplus} X$ and a tag~$T$,
where ${\oplus}$ denotes the xor of two equal-length strings, and $V = N {\,\|\,} [1]_{4}$.
Since $X$ is known, an adversary can extract $L \gets \mathrm{AES}_K(V)$ from the ciphertext.
It then can create a valid ciphertext for \emph{any} large message $\bm{M}$ as follows.
Instead of picking a 16-byte random seed and deriving the corresponding subkey,
it uses the string $V$ above as the seed and the string~$L$ above as the subkey.
It then runs lines 5--11 of Algorithm~\ref{algo:chop} to encrypt $\bm{M}$.

\iffalse

While the two techniques above seem orthogonal, unfortunately when we combine them, we will have a diminishing return in performance gain.

\fi

\section{Experiments} \label{sec:perf}

\iffalse
\begin{itemize}
\item Describe the machine environments for the experiments (OS, compiler, flags, etc)
\item Ping-pong and other OSU benchmark results
\item Application results
\end{itemize}
\fi

In this section, we empirically evaluate the performance of $\textrm{CryptMPI}$ on
two platforms and compare $\textrm{CryptMPI}$ with
conventional unencrypted MPI, which will be called {\emph{Unencrypted}},
and the naive approach of
Naser et al.~\cite{Cluster:Naser19}, which will be called {{\emph{Naive}}}.
We begin with a description of our experiment setup
and our benchmark methodology.
We then report the experiment results.

\heading{System setup.}
The experiments are performed on two systems. One is a local {\em Noleland}
cluster with InfiniBand connectivity. Machines in our cluster are
Intel Xeon Gold 6130 with 2.10 GHz base frequency. Each node
has 16 cores, 32 threads, and 187GB DDR4-2666 RAM, and runs CentOS~7.5.
It is equipped with a 100 Gigabit InfiniBand one (Mellanox MT28908 Family, ConnectX-6).
Allocated nodes were chosen manually. Each experiment used the same
node allocation for all measurements.  All ping-pong results used two
processes on different nodes.

The other system is an Xsede resource, PSC Bridges with Regular Memory
partition~\cite{XSEDE}. The CPUs
are Intel Haswell E5-2695 v3, with 2.3--3.3 GHz base frequency. Each
node has 14 cores, 28 threads, and 128GB DDR4-2133 RAM, and runs CentOS~7.6.
It is equipped with a 100 Gigabit Intel Omni-path interconnect.

We implemented our prototypes on top of
MVAPICH2-2.3.2  for both InfiniBand and Omni-path. The underlying
encryption library is BoringSSL (using AES-GCM-128 in all experiments).
All MPI code was compiled
with the standard set of MVAPICH compilation
flags and optimization level O2,
together with the \texttt{-fopenmp} flag to enable OpenMP.
We compiled BoringSSL
separately under default settings,
and linked it with MPI libraries during the linking phase of
MVAPICH.

Multi-threading is handled via OpenMP-3.1.
In MVAPICH, we set the following environment variables
\begin{eqnarray*}
\texttt{MV2\_ENABLE\_AFFINITY=1}  \\
\texttt{MV2\_CPU\_BINDING\_POLICY=hybrid}  \\
\texttt{MV2\_HYBRID\_BINDING\_POLICY=spread}
\end{eqnarray*}
to distribute resources evenly among MPI ranks.

\heading{Benchmarks.} We consider the following suites of benchmarks:

\begin{itemize}

\item Ping-pong: This benchmark measures the uni-directional throughput when
two processes send back and forth via blocking send and receive.
In each  measurement,
the two processes send messages of the given size back and forth  for 10,000 times
for messages under 1MB, and 1,000 times otherwise.

\item OSU micro-benchmark 5.6.2~\cite{OSUBM}: We used the Multiple Pair Bandwidth Test
benchmark in OSU suite to measure aggregate uni-directional throughput of multiple one-to-one
flows between two nodes.
Each measurement consists of a 100-round loop.
In each loop the sender sends 64 non-blocking messages of the given size
to the receiver, and waits for the replies.

\item 2D, 3D, and 4D stencil kernels: We will describe the 2D kernel;
3D and 4D kernels are similar.
The five-point 2D stencil kernel is as follows.
In a loop of 1250 rounds, each process in a $\sqrt{N} \times \sqrt{N}$ grid (here $N$ is number of processes)
performs some matrix multiplications and then sends messages of  $m$~KB
to its four neighbors via non-blocking sends, and
finishes the communication via $\texttt{MPI\_Waitall} $.
The kernels allow the computation load to be tuned to achieve a given
ratio between computation and communication. In the experiments,
we set the computation load so that for the unencrypted conventional MPI,
the average computational time is about $p\%$ of the average total time.
where $p \in \{25, 50, 75\}$ on the Noleland cluster and
$p \in \{30, 60, 80\}$ on the PSC Bridges.

\item NAS parallel benchmarks~\cite{Bailey:1991:NPB:2748645.2748648}:
To measure performance of CryptMPI in applications,
we used the CG, LU, BT, and SP tests in the NAS parallel benchmarks,
all under class D size.
Collective functions in the NAS benchmarks are unencrypted for both CryptMPI and ${\emph{Naive}}$.

\end{itemize}

\iffalse

Stencil codes are very common in scientific
computing research. We choose 2D, 3D and 4D stencil programs to show how the amount
of computation could impact the encrypted communication performance.
We configured our code in such so that computation and communication
could run for a certain amount of time. In each iteration, we did some
amount of computation and then communication. All the communication
is done by non-blocking point to point routines and finally used
waitall. Stencil programs were run for 1250 iterations, on
112 nodes and 784 ranks in the InfiniBand network of PSC Bridges~\cite{XSEDE}
\fi

\noskipheading{Benchmark methodology.}
For each experiment, we ran it at
least 10 times, up to 100 times,
until the standard deviation was within 5\% of the arithmetic mean.
If after 100 measurements, the standard deviation was still big then
we kept running
 until the 99\% confidence interval
was within 1\% of the  mean.

\heading{Multi-thread encryption throughput.}
Before we get into the details
of the benchmark results, it is instructive to
evaluate multi-threading performance of AES-GCM on a single node,
as it will give us a better understanding of the performance of CryptMPI.
For each size, we measured the time for performing 500,000 times
the encryption
of messages of the given size under different numbers of threads.
The measurements were stable, as they involved only local computation.
We therefore ran this experiment at least~5 times until the standard
deviation was within 5\% of the arithmetic mean.

The average encryption throughput of AES-GCM-128 on the local Noleland
is shown in \figref{fig:enc_dec_gcc_throughput},
for various message sizes and numbers of threads.
AES-GCM has about the same the encryption and decryption speed,
thus the reported throughput here is also the decryption throughput.
For convenience, in the analysis,
we use the term \emph{encryption-decryption} throughput for the speed of  encrypting and then decrypting a message;
this is about half of the encryption throughput.

The encryption throughput on PSC Bridges is shown
in \figref{fig:xsede-enc}, for
various message sizes and numbers of threads.
The encryption throughput in Bridges is much lower than that
in Noleland, because machines in the latter are newer.

\begin{figure}[t]
	\centering

		\includegraphics[width=0.45\textwidth]{graphs/encryption.eps}

		\vspace{-1.5ex}
	        \caption{Encryption throughput of AES-GCM (128-bit key) on a Noleland node.}

	\label{fig:enc_dec_gcc_throughput}
	\vspace{-2ex}
\end{figure}

\begin{figure}[t]
	\centering
		\includegraphics[width=0.45\textwidth]{graphs/xsede-encryption.eps}

		\vspace{-1.5ex}
	        \caption{Encryption throughput of AES-GCM (128-bit key) on a PSC Bridges node.

	\label{fig:xsede-enc}
	\vspace{-2ex}
\end{figure}

\subsection{Results for the Noleland cluster} \label{sec:infiniband}

\iffalse

From the figure, we could see that with the increase of the
threads, 4MB throughputs increased approximately as a factor of 2.
For instance, with 2 threads and 4 threads, its throughput is 1.98
times and 3.78 times of the single thread respectively.
There are two ways to interpret the results
here. First, one can view this as the convergence of the ping-pong performance
when the network speed becomes much faster than encryption and decryption.
Also, since for AES-GCM, the encryption and decryption speed
is roughly the same, the reported performance here is a half of the
encryption throughput (that is also decryption throughput).

\fi

\noskipheading{Ping-pong.} The ping-pong performance of the
unencrypted conventional MPI ({\emph{Unencrypted}}), the naive approach ({\emph{Naive}}),
and CryptMPI is shown in  \figref{fig:pingpong_infiniband}.
Both {{\emph{Naive}}} and CryptMPI start well below the performance of the
unencrypted baseline.
For example, for 64KB messages, the overhead of the naive approach,
compared to the baseline, is  $202.1\%$,
whereas CryptMPI uses $\min\{T_0-T_1, t\} = 2$ threads
and $k = 1$ chunk,
ending up with $187.4\%$ overhead.

As the message size becomes larger,
the performance of ${\emph{Naive}}$ becomes saturated very quickly,
widening its gap with the baseline.
In contrast, the performance of CryptMPI increases sharply,
catching up with the baseline.
For example, for 4MB messages, the overhead of the ${\emph{Naive}}$ approach is $412.4\%$,
whereas CryptMPI uses $\min\{T_0-T_1, t\} = 8$ threads and $k = 8$ chunks,
resulting in just $13.3\%$ overhead.
The phenomenon above can be explained as follows.

\begin{figure}[!tbp]
	\centering

		\includegraphics[width=0.45\textwidth]{graphs/infini-pingpong.eps}
		\vspace{-1.5ex}
	\caption{Average
	ping-pong throughput on Noleland.}
	\label{fig:pingpong_infiniband}
	\vspace{-1ex}
\end{figure}

\begin{itemize}
	\item The running time of the naive approach consists of (i)~the (one-thread) encryption-decryption time,
	and (ii) the underlying MPI communication time,
	which is approximately the same as the time of the unencrypted baseline.
	For 4MB messages, the single-thread encryption-decryption throughput (2,759.27 MB/s,  \allowbreak roughly half of the encryption throughput shown
        in \figref{fig:enc_dec_gcc_throughput}) is about
	24\% of the unencrypted ping-pong throughput (11,235.13 MB/s).
	The ping-pong performance of ${\emph{Naive}}$
	can be estimated as
        $\frac{1 + 0.24}{0.24} \approx 5.16$ times slower than
        that of the unencrypted baseline,
	which is consistent with the reported $412.4\%$ overhead above.

      \item For messages under 1MB, CryptMPI's running time consists
        of (i) the time of multi-threading
	encryption-decryption, with $t \in \{2, 4, 8\}$ threads,
	and (ii) the underlying MPI communication time.
	For $64$KB messages, $\min\{T_0-T_1, t\} = 2$
	and thus the encryption-decryption throughput (3,151.68 MB/s) is about 62\% of the unencrypted ping-pong throughput  (5,023.81 MB/s).
	The ping-pong performance with CryptMPI can be estimated as
	$\frac{1 + 0.62}{0.62} \approx 2.61$ times slower than
        that of the unencrypted baseline,
	which is close to the reported $187.4\%$ overhead above.

      \item For messages of at least 1MB,  the model
        in \secref{sec:oursystem} suggests that
	the total timing of CryptMPI is roughly  the time of unencrypted Ping Pong
	plus the encryption-decryption time (under 8 threads) of a \emph{single} 512KB chunk.
  The 8-thread  encryption-decryption throughput for 512KB (10,736.98 MB/s) is 0.96 times is the unencrypted ping-pong throughput for 4MB (11,235.13 MB/s).
	As a 512KB chunk is only $1/8$ the size of a 4MB message,
	estimatedly, the ping-pong performance under CryptMPI
	is $\frac{1 + 0.96 \cdot 8}{0.96 \cdot 8} \approx 1.13$ times slower than that of the unencrypted baseline,
	which is consistent with the reported $13.3\%$ overhead above.
\end{itemize}

\iffalse

\fi

\iffalse

\fi

\iffalse
\begin{figure*}[t]
\centering
\subfloat[$64$KB-messages]{
  \includegraphics[width=0.4\textwidth]{graphs/infini-multi-pair-64KB.eps}%
}
\subfloat[$256$KB-messages]{
  \includegraphics[width=0.4\textwidth]{graphs/infini-multi-pair-256KB.eps}%
}

\subfloat[$1$MB-messages]{
  \includegraphics[width=0.4\textwidth]{graphs/infini-multi-pair-1MB.eps}%
}
\subfloat[$4$MB-messages]{
  \includegraphics[width=0.4\textwidth]{graphs/infini-multi-pair-4MB.eps}%
}
\captionsetup{singlelinecheck=false}
\caption{OSU Multiple-Pair average throughput on InfiniBand. }
\label{fig:multipair_infiniband_64KB}
\vspace{-1.5ex}
\end{figure*}

\fi

\noskipheading{OSU Multiple-Pair Bandwidth.}
OSU Multiple-Pair benchmark measures the throughput between two nodes where there are multiple
concurrent flows.
\figref{fig:multipair_infiniband_64KB} shows the Multiple-Pair
performance of ${\emph{Unencrypted}}$, CryptMPI, and ${\emph{Naive}}$ with 1, 2, 4, 8, and 16 pairs of
communication, and two message sizes, 64KB and 4MB.

When there is only a single pair, we have a similar phenomenon as in
the ping-pong experiment.
If we keep adding more and more pairs, the performance of both CryptMPI and ${\emph{Naive}}$ will increase,
until the aggregate throughput of all pairs exceeds the bandwidth of the link between the two nodes.
In that case, the bottleneck is the link,
  and  encryption overhead in this situation is effectively
  hidden.

In particular, when there are two pairs, $\textrm{CryptMPI}$ can match the performance of the baseline,
but ${\emph{Naive}}$ still falls far behind.
For example, for 4MB message,
compared to the baseline, $\textrm{CryptMPI}$ has $0.31\%$ overhead,
whereas ${\emph{Naive}}$ has $34.87\%$ overhead.
For four or more pairs, even the naive approach
has about the same performance as the baseline.
This concurs with the observation of Naser et al. that in practical
scenarios where there are multiple
concurrent flows, the overhead of encrypted MPI may be
negligible \cite{Cluster:Naser19}.
Notice that ${\emph{Naive}}$ cannot fully utilize the network bandwidth when
there is one or two pairs regardless of the message size;
in contrast CryptMPI achieves similar performance as ${\emph{Unencrypted}}$ even with
just a single pair of communication when the message size is sufficiently large.

\iffalse

  Note that the OSU multi-pair benchmark is a bandwidth benchmark, measuring the
  throughput when multiple pairs of MPI ranks communicate simultaneously.
  When there is only one pair,  the encryption overhead directly results in
  a lower throughput. When there are many pairs (more than 4 in our experiments),
  the aggregate throughput for all of the pairs exceeds the link
  bandwidth between the two nodes. In this case, the bottleneck is the link,
  which limits the total bandwidth that can be achieved by all pairs:
  encryption overhead in this situation is effectively
  hidden (overlapping with the communication).
	\fi

\iffalse
\textcolor{blue}{
	$\textrm{CryptMPI}'s$  similar performance with the baseline suggests $\textrm{CryptMPI}$ effectively
    the encryption and decryption cost by overlapping
    computation and communication. For example, suppose, a sender sends $n$ chunks of data. After sending
    the first two chunks sender will start encrypting $3rd$ chunk data. At the same time, $2nd$ chunk will
    in transmission, and the receiver will do the decryption of already received $1st$ chunk
    data. In osu-multipair benchmark that exactly happens as it sends each message 64 times
    in a single iteration. When multiple pairs doing communication as above mentioned procedure, it
    utilizes the entire bandwidth and provides similar performance as baseline.}
\fi

\begin{figure}[!htbp]
\centering
\subfloat[$64$KB-messages]{
  \includegraphics[width=0.4\textwidth]{graphs/infini-multi-pair-64KB.eps}%
}
\\
\subfloat[$4$MB-messages]{
  \includegraphics[width=0.4\textwidth]{graphs/infini-multi-pair-4MB.eps}%
}
\vspace{-1.5ex}
\captionsetup{singlelinecheck=false}
\caption{OSU Multiple-Pair throughput on Noleland. }
\label{fig:multipair_infiniband_64KB}
\vspace{-1.5ex}
\end{figure}

CryptMPI is carefully designed to avoid performance degradation.
For example, consider the setting of two pairs of communication for 4MB messages,
namely $t = 8$.
Recall that in the OSU Multiple-Pair Bandwidth test, in each iteration,
a sender will send 64 messages.
Initially, CryptMPI  picks $\min\{T_0 - T_1, t\} = 8$ threads and $k = 8$ chunks for each message.
However, after the 8th messages, there are already $64$ pending send requests,
and CryptMPI will reset $k = 1$ for subsequent messages.
When there are many pairs, CryptMPI automatically adjusts the thread number to avoid an over-subscription of cores.
For example, if there are $8$ pairs, since there are $32$ hyper-threads in a Noleland node,
$T_0 = 32 / 8 = 4$, and thus CryptMPI will use $\min\{T_0 - T_1, t\} = 2$ threads.

\iffalse
\fi

\iffalse

\begin{figure}[t]
	\centering
		\includegraphics[width=0.5\textwidth]{graphs/infini-multi-pair-64KB.eps}
	\caption{OSU Multiple-Pair average throughput for 64KB-messages on InfiniBand.}
	\label{fig:multipair_infiniband_64KB}
	\vspace{-2ex}
\end{figure}

\begin{figure}[t]
	\centering
		\includegraphics[width=0.5\textwidth]{graphs/infini-multi-pair-256KB.eps}
	\caption{OSU Multiple-Pair average throughput for 256KB-messages on InfiniBand.}
	\label{fig:multipair_infiniband_256KB}
	\vspace{-1ex}
\end{figure}

\begin{figure}[t]
	\centering
		\includegraphics[width=0.5\textwidth]{graphs/infini-multi-pair-1MB.eps}
	\caption{OSU Multiple-Pair average throughput for 1MB-messages on InfiniBand.}
	\label{fig:multipair_infiniband_1MB}
	\vspace{-2ex}
\end{figure}

\begin{figure}[t]
	\centering
		\includegraphics[width=0.5\textwidth]{graphs/infini-multi-pair-4MB.eps}
	\caption{OSU Multiple-Pair average throughput for 4MB-messages on InfiniBand.}
	\label{fig:multipair_infiniband_4MB}

\end{figure}

\fi

\iffalse

\heading{Stencil kernels.}
Stencil kernels are used in many HPC applications. The results for
2D, 3D, and 4D stencil kernels have the similar trend. Here,
we will only show the results for the 2D stencil kernel (64-rank, 8-node)
in \figref{fig:2d_stencil_noleland} with three different computation loads.
For 25\%, 50\%, and 75\% computational loads and the two message sizes
256KB and 2MB, $\textrm{CryptMPI}$ improves over ${\emph{Naive}}$ significantly.
For instance, on 2MB for 75\% computation naive approach
overhead is $95.18\%$ and CryptMPI overhead is $44.38\%$.
This improvement is achieved by $\textrm{CryptMPI}$ during runtime
by dynamically deciding $\min\{T_0-T_1, t\} = 2$ threads, and 4 pipeline chunks for
the 2MB messages. Meanwhile, 256KB uses the same number of threads and 1 pipeline chunk.
This suggests, $\textrm{CryptMPI}$ will reduce the overhead further in the systems which enabled with many hyper-threads.

\begin{figure}[t]
	\centering
	\vspace{-2ex}
	\subfloat[$256$KB-messages]{
	  \includegraphics[width=0.32\textwidth]{graphs/2d-256KB-noleland-1k.eps}%
	}
	\vspace{-2.75ex}
	\,

	\subfloat[$2$MB-messages]{
	  \includegraphics[width=0.32\textwidth]{graphs/2d-2MB-noleland-1k.eps}%
	}
	\vspace{-1.5ex}
	\captionsetup{singlelinecheck=false}
	\caption{2D Stencil communication time, for 64-rank and 8-node on InfiniBand.}
	\label{fig:2d_stencil_noleland}
	\vspace{-1.5ex}

	\end{figure}

\begin{table*}[!t]

		\centering

		\caption{Average Inter-node Communication ($t$\textsubscript{$icom$}), Total Communication ($t$\textsubscript{$tcom$}) and Total Execution ($t$\textsubscript{$exe$}) Time (seconds) of NAS Parallel Benchmarks, Class D, 64-rank and 8-node, on InfiniBand.}
		\begin{tabular}{p{0.10\linewidth}*{12}{p{0.045\linewidth}}}
		\toprule[1.25pt]
		& \multicolumn{3}{|c|}{\textbf{CG}} & \multicolumn{3}{c|}{\textbf{LU}} & \multicolumn{3}{c|}{\textbf{SP}} & \multicolumn{3}{c|}{\textbf{BT}}\\
		& $t$\textsubscript{$icom$} & $t$\textsubscript{$tcom$} & $t$\textsubscript{$exe$} & $t$\textsubscript{$icom$} & $t$\textsubscript{$tcom$} & $t$\textsubscript{$exe$} & $t$\textsubscript{$icom$} & $t$\textsubscript{$tcom$} & $t$\textsubscript{$exe$} & $t$\textsubscript{$icom$} & $t$\textsubscript{$tcom$} & $t$\textsubscript{$exe$} \\ \midrule
		\textbf{Unencrypted} & 2.57 &  10.36 & 125.84 & 2.61  & 9.66 & 172.86 & 6.39 & 9.84 & 233.25 & 9.49 & 12.94 & 292.85 \\
		\textbf{CryptMPI}    & 3.39 &  11.79 & 128.26 & 4.19  & 11.99 & 175.96 & 9.59 & 12.33 & 237.44 & 9.96 & 12.65 & 296.11 \\
		\textbf{Naive}       & 4.14 &  12.13 & 128.40 & 6.56  & 17.29 & 181.25 & 10.02 & 12.60 & 236.37 & 10.97 & 13.94 & 294.30 \\
		\bottomrule[1.25pt]
		\end{tabular}

		\label{tab:NAS_IB_INTER_NODE}

\end{table*}

\heading{NAS benchmarks.}
    For NAS benchmarks (64-rank, 8-node),
    the total execution time is dominated mostly
    by computation thus the total execution times of all three libraries are similar.
    As a consequence, reduced encrypted communication time by $\textrm{CryptMPI}$ does not reflect properly
    in the total execution time as shown in Table~\ref{tab:NAS_IB_INTER_NODE}.
    For instance, in LU the $\textrm{CryptMPI}$ execution time overhead is $1.79\%$ and the ${\emph{Naive}}$
    approach overhead is 4.85\% compared with the unencrypted total execution time.
    However, if we take into account only the inter-node communication time
    then $\textrm{CryptMPI}$ reduced encrypted communication time by $63.87\%$ than that of the
    ${\emph{Naive}}$ approach. The total execution time for SP and BT in the ${\emph{Naive}}$
    approach is a little lower than the $\textrm{CryptMPI}$ and it is less than $0.7\%$:
    this is likely due to the noise. That also suggests that in cases when
    $\textrm{CryptMPI}$ does not improve the overall execution time, it does not degrade
    the performance either. Since $\textrm{CryptMPI}$ only optimizes the inter-node communication,
    we compare the inter-node communication time as follows

For inter-node communications,
CryptMPI's improvement over ${\emph{Naive}}$ varies from one benchmark to another.
In CG, for example, CryptMPI's overhead, compared to the unencrypted baseline,
is $31.90\%$, which is much lower than the $61.08\%$ overhead of ${\emph{Naive}}$.
In BT, both $\textrm{CryptMPI}$ and ${\emph{Naive}}$ have relatively low overhead: $4.95\%$
for CryptMPI and $15.59\%$ for ${\emph{Naive}}$. In the more practical situations like
the NAS benchmarks, there are factors that can affect the effectiveness
of $\textrm{CryptMPI}$, including the following.

\begin{itemize}
\item Recall that CryptMPI only improves the naive approach
  for messages of at least 64KB, and thus there might be no noticeable
  difference between the two libraries
  for applications that have largely small messages.

\item CryptMPI's approach of using multi-thread encryption is only
  beneficial if there are still some idle computational resources to
  exploit, which may not hold for some computationally intensive situations.

\item Finally, CryptMPI's pipelining will give a diminishing return if
  there is already a significant overlapping between computation and
  communication in the application. Such a  situation basically hides
  the communication overheads; and both ${\emph{Naive}}$ and CryptMPI should have
  a low overhead. This happens in the BT benchmark.
\end{itemize}

\iffalse
\fi

\iffalse
\fi

\iffalse
\begin{table*}[!t]

		\centering
		\captionsetup{justification=centering, labelsep=newline}

		\caption{\textcolor{blue}{Average Inter-node Communication ($t$\textsubscript{$icom$}), Total Communication ($t$\textsubscript{$tcom$}) and Total Execution ($t$\textsubscript{$exe$}) Time (seconds) of NAS Parallel Benchmarks, Class D, 64-rank and 8-node, on InfiniBand.}}
		{\color{blue}\begin{tabular}{p{0.10\linewidth}*{12}{p{0.045\linewidth}}}
		\toprule[1.25pt]
		& \multicolumn{3}{|c|}{\textbf{CG}} & \multicolumn{3}{c|}{\textbf{LU}} & \multicolumn{3}{c|}{\textbf{SP}} & \multicolumn{3}{c|}{\textbf{BT}}\\
		& $t$\textsubscript{$icom$} & $t$\textsubscript{$tcom$} & $t$\textsubscript{$exe$} & $t$\textsubscript{$icom$} & $t$\textsubscript{$tcom$} & $t$\textsubscript{$exe$} & $t$\textsubscript{$icom$} & $t$\textsubscript{$tcom$} & $t$\textsubscript{$exe$} & $t$\textsubscript{$icom$} & $t$\textsubscript{$tcom$} & $t$\textsubscript{$exe$} \\ \midrule
		\textbf{Unencrypted} & 2.57 &  10.36 & 125.84 & 2.61  & 9.66 & 172.86 & 6.39 & 9.84 & 233.25 & 9.49 & 12.94 & 292.85 \\
		\textbf{CryptMPI}    & 3.39 &  11.79 & 128.26 & 4.19  & 11.99 & 175.96 & 9.59 & 12.33 & 237.44 & 9.96 & 12.65 & 296.11 \\
		\textbf{Naive}       & 4.14 &  12.13 & 128.40 & 6.56  & 17.29 & 181.25 & 10.02 & 12.60 & 236.37 & 10.97 & 13.94 & 294.30 \\
		\bottomrule[1.25pt]
		\end{tabular}}

		\label{tab:NAS_IB_INTER_NODE}

\end{table*}
\fi

\fi

\iffalse

\subsection{Results for the Noleland cluster with Ethernet} \label{sec:ethernet}

\noskipheading{Ping-pong.} The ping-pong results on Ethernet
are shown in \figref{fig:pingpong_ethernet}. For 64KB-messages,
the naive approach appears to slightly outperform CryptMPI,
but recall that we are reporting the mean values with 5\% deviation,
so this only means that the performance of these two libraries are very close.

In this setting, the gap between network speed and encryption power
is much narrower than that of InfiniBand.
Expectedly, the trend here is similar to that of InfiniBand,
but the encryption overhead is lower, for both the naive approach and CryptMPI.
For example, for 4MB-messages,
the overhead of the naive approach is $46.35\%$,
whereas CryptMPI's ($\min\{T_0-T_1, t\} = 8$, and 8 pipeline chunks) overhead is just $7.83\%$.
These statistics can be explained using the similar analysis
of ping-pong performance on InfiniBand.

\iffalse

Ethernet results exhibit a similar trend as InfiniBand. However, the overhead is
low on Ethernet. Because the network latency increased but encryption speed remains the same.
At 64KB the naive approach (501.24 MB/s) is performing a little better than CrypMPI (482.65 MB/s).
Here we are reporting the mean values with the $5\%$ deviation. So we can say at that point
both approach performance is the same. As message size increased we could notice the performance gain of CrypMPI.
At 4MB, the naive approach overhead is $46.35\%$ (750.76 MB/s) compared to the unencrypted base (1,098.77 MB/s),
 meanwhile for the same size, CryptMPI overhead is $7.83\%$ (1,019.01 MB/s). We could explain this as follows.
\begin{itemize}
    \item On 4MB message encryption-decryption throughput (2,759.27 MB/s) is 2.51 times of
    the unencrypted base. Estimatedly, the naive approach would be
    $\frac{1 + 2.51}{2.51} \approx 1.40$ times slower than that of the unencrypted baseline,
    which is consistent with the reported $46.35\%$ overhead.

    \item For 4MB, the encryption throughput (21,473.96  MB/s) is
    32.88 times of the unencrypted base. Estimatedly, CryptMPI would be
     $\frac{1 + 32.88}{32.88} \approx 1.03$ times slower than that of the unencrypted baseline,
    which is consistent with the reported $7.63\%$ overhead.

\end{itemize}

\fi

	\begin{figure}[!tbp]
			\centering
				\includegraphics[width=0.35\textwidth]{graphs/eth-pingpong.eps}
					\captionsetup{singlelinecheck=false}
			\caption{Average
			ping-pong throughput on Ethernet.}
			\label{fig:pingpong_ethernet}
			\vspace{-2ex}
		\end{figure}

\iffalse

	\begin{figure*}[!b]
	\centering
	\subfloat[$64$KB-messages]{
	  \includegraphics[width=0.45\textwidth]{graphs/eth-multi-pair-64KB.eps}%
	}
	\subfloat[$256$KB-messages]{
	  \includegraphics[width=0.45\textwidth]{graphs/eth-multi-pair-256KB.eps}%
	}

	\subfloat[$1$MB-messages]{
	  \includegraphics[width=0.45\textwidth]{graphs/eth-multi-pair-1MB.eps}%
	}
	\subfloat[$4$MB-messages]{
	  \includegraphics[width=0.45\textwidth]{graphs/eth-multi-pair-4MB.eps}%
	}
	\captionsetup{singlelinecheck=false}
	\caption{OSU Multiple-Pair average throughput on Ethernet. }
	\label{fig:multipair_ethernet}
	\vspace{-1.5ex}

	\end{figure*}

	\fi

\heading{OSU Multiple-Pair Bandwidth.}
The Multiple-Pair performance is shown in
\figref{fig:multipair_ethernet}.
The phenomenon here is similar to that of InfiniBand,
but since Ethernet speed is much slower,
even for two pairs, the performance of ${\emph{Naive}}$ is
already close to that of the unencrypted baseline.
For one pair, CryptMPI has low overhead for different message sizes while
${\emph{Naive}}$ has larger overheads, especially for large messages.
For example, for 4MB messages,
the overhead of the naive approach is $24.73\%$ of the baseline,
whereas that of CryptMPI ($\min\{T_0-T_1, t\} = 8$, and pipeline chunks are decided similar as InfiniBand) is only $5.13\%$.

\iffalse

The reason behind multiple-pair good performance
in Ethernet also the same as InfiniBand. In 1 pair, 64KB message performs similarly as the unencrypted baseline compared
to the other message size. Because MPICH uses the eager protocol to send data at that size.
Large messages from 2 pairs, both naive and CrypMPI perform close to the unencrypted baseline.
However, in 1 pair naive approach has large overhead. For instance, 4MB message overhead for the naive
approach is $24.73\%$ (942.67 MB/s) compared to the unencrypted base (1,175.87 MB/s) and CrypMPI
overhead is $5.13\%$ (1,118.4 MB/s).

\fi

\begin{figure}[!tp]
	\centering
	\subfloat[$64$KB-messages]{
	  \includegraphics[width=0.4\textwidth]{graphs/eth-multi-pair-64KB.eps}%
	}
	\\
	\subfloat[$4$MB-messages]{
	  \includegraphics[width=0.4\textwidth]{graphs/eth-multi-pair-4MB.eps}%
	}
	\captionsetup{singlelinecheck=false}
	\caption{OSU Multiple-Pair average throughput on Ethernet. }
	\label{fig:multipair_ethernet}
	\vspace{-1.5ex}

	\end{figure}

\heading{NAS benchmarks.} The stencil kernel results have a similar trend
as those with InfiniBand, and are omitted in the interests of space.
The average inter-node communication times of the NAS benchmarks on
Ethernet are shown in the  Table~\ref{tab:NAS_ETHERNET_INTER_NODE}.
The 10 Gigabit Ethernet is 10 times slower than the 100 Gigabit InfiniBand,
with the same encryption speed, the overhead introduced by encryption is
less, and the optimization techniques in $\textrm{CryptMPI}$ is less effective
relatively. Nonetheless, $\textrm{CryptMPI}$ consistently improves over ${\emph{Naive}}$. For
example, for LU, the overhead is 25.0\% for ${\emph{Naive}}$ and 19.6\% for $\textrm{CryptMPI}$.

\iffalse
Because of high network latency,
the time of both naive and CrytMPI is very similar and has relatively low overhead than the InfiniBand
network. For instance, the average overhead for CryptMPI is $13.86\%$ and the naive approach is $17.52\%$.
\fi

\begin{table}[!tp]
	\centering

	\caption{Average Inter-node Communication Time (seconds) of NAS Parallel Benchmarks, Class D, 64-rank and 8-node, on Ethernet.}
	\begin{tabular}{p{0.25\linewidth}*4{p{0.09\linewidth}}}
	\toprule[1.25pt]
	 & \textbf{CG} & \textbf{LU} & \textbf{SP} & \textbf{BT} \\ \midrule
	\textbf{Unencrypted} & 32.73 &  12.42 & 48.13 & 25.40  \\ \midrule
	\textbf{CryptMPI} & 33.02 & 14.85 & 55.97 & 33.56  \\ \midrule
	\textbf{Naive} &  34.23 & 15.52 & 57.12 & 33.86  \\
	\bottomrule[1.25pt]
	\end{tabular}

	\label{tab:NAS_ETHERNET_INTER_NODE}
	\vspace{-1ex}
	\end{table}

\iffalse
\begin{table*}[t]

	\centering
	\captionsetup{justification=centering, labelsep=newline}

	\caption{\textcolor{blue}{Average Inter-node Communication ($t$\textsubscript{$icomm$}), Total Communication ($t$\textsubscript{$tcomm$}) and Total Execution ($t$\textsubscript{$exe$}) Time (seconds) of NAS Parallel Benchmarks, Class D, 64-rank and 8-node, on Ethernet.}}
	{\color{blue}\begin{tabular}{p{0.10\linewidth}*{12}{p{0.05\linewidth}}}
	\toprule[1.25pt]
	& \multicolumn{3}{|c|}{\textbf{CG}} & \multicolumn{3}{c|}{\textbf{LU}} & \multicolumn{3}{c|}{\textbf{SP}} & \multicolumn{3}{c|}{\textbf{BT}}\\
	& $t$\textsubscript{$icomm$} & $t$\textsubscript{$tcomm$} & $t$\textsubscript{$exe$} & $t$\textsubscript{$icomm$} & $t$\textsubscript{$tcomm$} & $t$\textsubscript{$exe$} & $t$\textsubscript{$icomm$} & $t$\textsubscript{$tcomm$} & $t$\textsubscript{$exe$} & $t$\textsubscript{$icomm$} & $t$\textsubscript{$tcomm$} & $t$\textsubscript{$exe$} \\ \midrule
	\textbf{Unencrypted} & 32.73 &  89.46 & 204.38 & 12.42  & 28.26 & 193.86 & 48.13 & 58.74 & 281.62 & 25.40 & 31.30 & 313.28 \\
	\textbf{CryptMPI}  & 33.02 &  87.69 & 203.63 & 14.85  & 30.73 & 197.08 & 55.97 & 65.53 & 291.49 & 33.56 & 41.58 & 326.75 \\
	\textbf{Naive}  & 34.23 &  88.53 & 204.17 & 15.52  & 30.59 & 197.24 & 57.12 & 65.02 & 288.09 & 33.86 & 40.83 & 323.06 \\
	\bottomrule[1.25pt]
	\end{tabular}}

	\label{tab:NAS_ETHERNET_INTER_NODE}

	\end{table*}
\fi

\fi

\heading{Stencil and NAS benchmarks.} Results for Stencil and NAS benchmarks on Noleland have similar trends as
those on PSC Bridges. We omit them due to a lack of space.

\subsection{Results for PSC Bridges} \label{sec:stencil}

\iffalse
\begin{figure*}[t!]
	\centering
	\subfloat[$256$KB-messages]{
	  \includegraphics[width=0.45\textwidth]{graphs/2d-256KB.eps}%
	}
	\subfloat[$512$KB-messages]{
	  \includegraphics[width=0.45\textwidth]{graphs/2d-512KB.eps}%
	}

	\subfloat[$1$MB-messages]{
	  \includegraphics[width=0.45\textwidth]{graphs/2d-1MB.eps}%
	}
	\subfloat[$2$MB-messages]{
	  \includegraphics[width=0.45\textwidth]{graphs/2d-2MB.eps}%
	}
	\captionsetup{singlelinecheck=false}
	\caption{2D Stencil communication time, for 784-rank and 112-node.}
	\label{fig:2d_stencil}
	\vspace{-1.5ex}

	\end{figure*}

	\fi

\iffalse
\begin{figure*}[t!]
\centering
	\subfloat[$30\%$ computation]{
	  \includegraphics[width=0.31\textwidth]{graphs/2d-30per.eps}
	} \quad
	\subfloat[$60\%$ computation]{
	  \includegraphics[width=0.31\textwidth]{graphs/2d-60per.eps}%
	} \quad
	\subfloat[$80\%$ computation]{
	  \includegraphics[width=0.31\textwidth]{graphs/2d-80per.eps}%
	}

	\captionsetup{singlelinecheck=false}
	\caption{2D Stencil, for 784-rank and 112-node.}
	\label{fig:2d_stencil}
	\vspace{-1.5ex}

	\end{figure*}
\fi

\noskipheading{Ping Pong.}
The ping-pong results on Bridges
are shown in \figref{fig:xsede_pingpong}. Because of
the low
of computation power, the naive approach has very high overhead on Bridges.
For instance, on 4MB
naive approach's overhead is 754.87\% compared to the unencrypted base,
whereas CryptMPI's overhead is just  38.12\%.
We can explain this performance using a similar reasoning as the analysis in Noleland:

\begin{itemize}
\item For messages under 1MB, CryptMPI's running time consists of (i) the time of multi-threading
    encryption-decryption, with $t \in \{4, 8, 16\}$ threads,
    and (ii) the underlying MPI communication time.
    For $64$KB messages, $\min\{T_0-T_1, t\} = 4$
    and thus the encryption-decryption throughput (2,786.08 MB/s) is about 67\% of the unencrypted ping-pong throughput  (4,105.55 MB/s).
    The ping-pong performance under CryptMPI can be estimated as
    $\frac{1 + 0.67}{0.67} \approx 2.50$ times slower than that of
    the unencrypted baseline,
    which is consistent to the reported $140.2\%$ overhead above.

    \item The 16-thread  encryption-decryption throughput for 512KB (8,091.82 MB/s) is 0.71 times of the unencrypted ping-pong throughput for 4MB (11,404.1 MB/s).
As a 512KB chunk is only $1/8$ the size of a 4MB message,
the ping-pong performance under CryptMPI can be estimated as
$\frac{1 + 0.71 \cdot 8}{0.71 \cdot 8} \approx 1.18$ times slower than that of the unencrypted baseline,
which is close to the reported $38.12\%$ overhead above.
\end{itemize}

\begin{figure}[!tp]
	\centering
	\vspace{-2ex}
		\includegraphics[width=0.4\textwidth]{graphs/infini-xsede-pingpong.eps}
		\vspace{-1.5ex}
	\caption{Average
	ping-pong throughput on PSC Bridges.}
	\label{fig:xsede_pingpong}

\end{figure}

\heading{OSU Multiple-Pair bandwidth.}
The multi-pair results on  PSC Bridges
are shown in
\figref{fig:xsede_multipair_infiniband}.
The trend is similar to
its counterpart in the Noleland cluster with InfiniBand (namely \figref{fig:multipair_infiniband_64KB}):
all libraries have similar performance when there are
enough pairs of communication.
When the number of concurrent pairs is small,
even for large messages, ${\emph{Naive}}$ has very high overheads. For instance,
for two pairs and 4MB messages, the overhead for ${\emph{Naive}}$  is 178.48\%,
whereas CryptMPI's overhead is 5.03\%.

\begin{figure}[t]
	\centering
	\vspace{-2.5ex}
	\subfloat[$64$KB-messages]{
	  \includegraphics[width=0.4\textwidth]{graphs/infini-multi-pair-xsede-64KB.eps}%
	}
	\\
	\vspace{-2.75ex}

	\subfloat[$4$MB-messages]{
	  \includegraphics[width=0.4\textwidth]{graphs/infini-multi-pair-xsede-4MB.eps}%
	}
	\vspace{-1.5ex}
	\captionsetup{singlelinecheck=false}
	\caption{OSU Multiple-Pair throughput on PSC Bridges. }
	\label{fig:xsede_multipair_infiniband}
	\vspace{-1.5ex}

	\end{figure}

\begin{table*}[!tbp]

		\centering

		\caption{Average inter-node communication time ($T_i$), total communication time ($T_c$),  and total execution time ($T_e$) in seconds, for NAS Parallel Benchmarks, Class D, 784-rank and 112-node on PSC Bridges. For CG, we used 512-rank and 128-node.}
		\begin{tabular}{p{0.13\linewidth}*{4}{|p{0.05\linewidth}p{0.05\linewidth}p{0.05\linewidth}}}
		\toprule[1.25pt]
		& \multicolumn{3}{c|}{\textbf{CG}} & \multicolumn{3}{c|}{\textbf{LU}} & \multicolumn{3}{c|}{\textbf{SP}} & \multicolumn{3}{c}{\textbf{BT}}  \\
		& $T_i$ & $T_c$ & $T_e$ & $T_i$ & $T_c$ & $T_e$ & $T_i$ & $T_c$ & $T_e$ & $T_i$ & $T_c$ & $T_e$ \\ \midrule
		\textbf{Unencrypted} & 7.77 &  13.17 & 27.09 & 6.30  & 32.11 & 52.17 & 24.67 & 35.94 & 62.40 & 26.49 & 40.54 & 69.89 \\
		\textbf{CryptMPI}  & 8.73 &  14.80 & 32.56 & 8.80  & 34.26 & 56.24 & 30.01 & 39.54 & 67.64 & 28.54 & 42.25 & 73.06 \\
		\textbf{Naive}  & 13.91 &  20.93 & 37.84 & 9.71  & 36.06 & 57.87 & 31.62 & 40.11 & 68.18 & 29.03 & 42.67 & 73.49 \\
		\bottomrule[1.25pt]
		\end{tabular}

		\label{tab:NAS_PSC_INTER_NODE}

\end{table*}

\heading{Stencil Kernels.}
We ran 784-rank Stencil kernels on 112 nodes.
The results for 2D stencil with different computation loads
are illustrated in~\figref{fig:2d_stencil}.
When the computational load is not heavy then CryptMPI
significantly improves the performance of the naive  approach.
For example, for 60\% load and 2MB messages,
the encryption overhead in CryptMPI is 206\%,
whereas that of the naive approach is 331\%.
In this setting CryptMPI uses $\min\{T_0-T_1, t\} = 2$ threads and $k = 4$ chunks.
Even when computational load is heavy---an unfavorable condition for CryptMPI,
the improvement of CryptMPI over the naive approach is still noticeable.
For example, under 80\% computational load and 256KB messages, CryptMPI's encryption overhead is 384\%,
whereas that of the naive approach is 450\%.
In this setting CryptMPI instead uses $\min\{T_0-T_1, t\} = 2$ threads and $k = 1$ chunk.

\begin{figure}[!tbp]
	\centering
	\vspace{-1.5ex}
	\subfloat[$256$KB-messages]{
	  \includegraphics[width=0.4\textwidth]{graphs/2d-256KB.eps}%
	}

    \vspace{-2.5ex}
	\subfloat[$2$MB-messages]{
	  \includegraphics[width=0.4\textwidth]{graphs/2d-2MB.eps}%
	}
	\vspace{-1.5ex}
	\captionsetup{singlelinecheck=false}
	\caption{2D Stencil communication time, for 784-rank and 112-node, PSC Bridges.}
	\label{fig:2d_stencil}
	\vspace{-1.5ex}

	\end{figure}

\heading{NAS benchmarks.}
The running time of NAS benchmarks on PSC Bridges is shown in Table~\ref{tab:NAS_PSC_INTER_NODE}.
We ran CG with 512 ranks and 128 nodes because CG can only run in the setting where the number of ranks is a power of two.
The other programs were run with 784 ranks and 112 nodes. The total execution time
overhead of CG is $20.2\%$ and $39.69\%$ for $\textrm{CryptMPI}$ and ${\emph{Naive}}$ respectively.
However, if we take into account only the inter-node communication time
then $\textrm{CryptMPI}$'s overhead is only $12.3\%$,
whereas ${\emph{Naive}}$'s overhead is $79\%$. In BT,
both $\textrm{CryptMPI}$ and ${\emph{Naive}}$ have relatively low overhead for total execution time: $4.53\%$ for CryptMPI
and $5.15\%$ for ${\emph{Naive}}$.
The reason for this phenomenon is as follows:

\begin{itemize}
\item Recall that CryptMPI only improves the naive approach
  for messages of at least 64KB, and thus there might be no noticeable
  difference between the two libraries
  for applications that have largely small messages.

\item CryptMPI's approach of using multi-thread encryption is only
  beneficial if there are still some idle computational resources to
  exploit, which may not hold for some computationally intensive situations.

\item Finally, CryptMPI's pipelining will give a diminishing return if
  there is already a significant overlapping between computation and
  communication in the application. Such a  situation
	hides the communication overheads,  and thus both ${\emph{Naive}}$ and CryptMPI should have
  low overheads. This happens in the BT benchmark.
\end{itemize}

\iffalse
\begin{table*}[!tbp]

	\centering
	\captionsetup{justification=centering, labelsep=newline}
	\caption{\textcolor{blue}{Average Inter-node Communication ($t$\textsubscript{$icom$}), Total Communication ($t$\textsubscript{$tcom$}) and Total Execution ($t$\textsubscript{$exe$})
	Time (seconds) of NAS Parallel Benchmarks, Class D, 784-rank and 112-node (CG 512-rank and 128-node), on PSC Bridges.}}
	{\color{blue}\begin{tabular}{p{0.1\linewidth}*{12}{p{0.045\linewidth}}}
	\toprule[1.25pt]
	& \multicolumn{3}{|c|}{\textbf{CG}} & \multicolumn{3}{c|}{\textbf{LU}} & \multicolumn{3}{c|}{\textbf{SP}} & \multicolumn{3}{c|}{\textbf{BT}}\\
	& $T_i$ & $T_c$ & $T_e$ & $T_i$ & $T_c$ & $T_e$ & $T_i$ & $T_c$ & $T_e$ & $T_i$ & $T_c$ & $T_e$ \\ \midrule
	\textbf{Unencrypted} & 7.77 &  13.17 & 27.09 & 6.30  & 32.11 & 52.17 & 24.67 & 35.94 & 62.40 & 26.49 & 40.54 & 69.89 \\
	\textbf{CryptMPI}  & 8.73 &  14.80 & 32.56 & 8.80  & 34.26 & 56.24 & 30.01 & 39.54 & 67.64 & 28.54 & 42.25 & 73.06 \\
	\textbf{Naive}  & 13.91 &  20.93 & 37.84 & 9.71  & 36.06 & 57.87 & 31.62 & 40.11 & 68.18 & 29.03 & 42.67 & 73.49 \\
	\bottomrule[1.25pt]
	\end{tabular}}

	\label{tab:NAS_PSC_INTER_NODE}

\end{table*}
\fi

\iffalse
We could explain the results in two ways. First, with increased message size CryptMPI's performance
increased. For instance, Fig~\ref{fig:2d_stencil}(a)  shows,
on 256KB message CryptMPI reduced 0.95 seconds than the naive
approach, however, on 2MB it reduced 5.16 seconds. The reasons for larger message benefits
are as follows. (i) On a large message, we do pipeline. Hence computation and
communication are overlapped. (ii) the larger message has high encryption throughput.
Second, when computation percentage is large then CrytMPI's gain becomes small, shown in
Fig~\ref{fig:2d_stencil}(c). For example,
on 2MB CryptMPI reduces 1.51 seconds than the naive approach. We could explain this as follows.
In an ideal scenario, the benefit of CrytMPI should remain the same regardless of the computation percentage.
Because we are reducing encrypted communication time.
However, in practice receiver computation could finish earlier than the sender and wait for the message.
Or it could be vice-versa. In both cases, this kind of delay hiding CrypMPI's actual gain.
\fi

\iffalse

\begin{table}[!t]
\centering
\begin{tabular}{p{0.20\linewidth}*4{p{0.09\linewidth}}}
\toprule[1.25pt]
& \textbf{256KB} & \textbf{512KB} & \textbf{1MB} & \textbf{2MB} \\ \midrule
\textbf{Unencrypted} & 1.05 &  1.71 & 4.26 & 7.32  \\ \midrule
\textbf{CryptMPI} 	& 1.28 	&  2.61	& 4.98 & 11.76  \\ \midrule
\textbf{Naive} 		&  2.45 &  4.55	& 8.97 & 16.21  \\
\bottomrule[1.25pt]
\end{tabular}
\caption{Average time (seconds) of 2D Stencil(25\% computation and 75\% communication), 784-rank and 112-node, on InfiniBand.}
\label{tab:2D_INFINIBAND_INTER_NODE_25_PERCENTAGE}
\end{table}

\begin{table}[!t]
\centering
\begin{tabular}{p{0.20\linewidth}*4{p{0.09\linewidth}}}
\toprule[1.25pt]
& \textbf{256KB} & \textbf{512KB} & \textbf{1MB} & \textbf{2MB} \\ \midrule
\textbf{Unencrypted} & 1.09  & 2.12  & 4.51 & 9.0  \\ \midrule
\textbf{CryptMPI} 	&  1.71	&  3.65	& 6.86 &  16.26 \\ \midrule
\textbf{Naive} 		&  2.78 &  5.3	& 10.26 & 18.66  \\
\bottomrule[1.25pt]
\end{tabular}
\caption{Average time (seconds) of 2D Stencil(50\% computation and 50\% communication), 784-rank and 112-node, on InfiniBand.}
\label{tab:2D_INFINIBAND_INTER_NODE_50_PERCENTAGE}
\end{table}

\begin{table}[!t]
\centering
\begin{tabular}{p{0.20\linewidth}*4{p{0.09\linewidth}}}
\toprule[1.25pt]
& \textbf{256KB} & \textbf{512KB} & \textbf{1MB} & \textbf{2MB} \\ \midrule
\textbf{Unencrypted} & 2.22  & 4.95  & 8.86 & 20.15  \\ \midrule
\textbf{CryptMPI} 	& 4.03 	& 9.09 	& 15.9 &  35.81 \\ \midrule
\textbf{Naive} 		& 4.27  & 9.33 	& 17.04 & 37.58  \\
\bottomrule[1.25pt]
\end{tabular}
\caption{Average time (seconds) of 2D Stencil(80\% computation and 20\% communication), 784-rank and 112-node, on InfiniBand.}
\label{tab:2D_INFINIBAND_INTER_NODE_80_PERCENTAGE}
\end{table}

\fi

\iffalse

\heading{3D Stencil.} The average time of 3D stencil for different computation
and communication percentage is present in the Table~\ref{tab:3D_INFINIBAND_INTER_NODE_40_PERCENTAGE},
~\ref{tab:3D_INFINIBAND_INTER_NODE_70_PERCENTAGE}, and ~\ref{tab:3D_INFINIBAND_INTER_NODE_90_PERCENTAGE}.
3D stencil data shows a similar trend as 2D stencil. On 2MB data in Table~\ref{tab:3D_INFINIBAND_INTER_NODE_90_PERCENTAGE},
the naive approach is taking less time than CrypMPI. However, on 512KB naive approach time
is twice of 256KB and on 1MB it is four times of 256KB. So, the expected time of 2MB should be close to 160 seconds.
But in practice, we received 143.63 seconds. This suggests the timing of 2MB data has some noise.

\begin{table}[!t]
	\centering
	\begin{tabular}{p{0.20\linewidth}*4{p{0.09\linewidth}}}
	\toprule[1.25pt]
	& \textbf{256KB} & \textbf{512KB} & \textbf{1MB} & \textbf{2MB} \\ \midrule
	\textbf{Unencrypted} & 2.77  & 5.65  & 11.3 & 22.19  \\ \midrule
	\textbf{CryptMPI} 	&  3.6	& 7.14 	& 14.92 & 30.7  \\ \midrule
	\textbf{Naive} 		&  5.95 & 11.65 & 21.85 & 43.71  \\
	\bottomrule[1.25pt]
	\end{tabular}
	\caption{Average time (seconds) of 3D Stencil(40\% computation and 60\% communication), 784-rank and 112-node, on InfiniBand.}
	\label{tab:3D_INFINIBAND_INTER_NODE_40_PERCENTAGE}
	\end{table}

	\begin{table}[!t]
	\centering
	\begin{tabular}{p{0.20\linewidth}*4{p{0.09\linewidth}}}
	\toprule[1.25pt]
	& \textbf{256KB} & \textbf{512KB} & \textbf{1MB} & \textbf{2MB} \\ \midrule
	\textbf{Unencrypted} & 4.63  &  9.64    & 18.32  &  37.64 \\ \midrule
	\textbf{CryptMPI} 	&  7.22	 &  14.89	& 28.94  &  61.54 \\ \midrule
	\textbf{Naive} 		&  7.97  &  16.12	& 31.48  &   62.13 \\
	\bottomrule[1.25pt]
	\end{tabular}
	\caption{Average time (seconds) of 3D Stencil(70\% computation and 30\% communication), 784-rank and 112-node, on InfiniBand.}
	\label{tab:3D_INFINIBAND_INTER_NODE_70_PERCENTAGE}
	\end{table}

	\begin{table}[!t]
	\centering
	\begin{tabular}{p{0.20\linewidth}*4{p{0.09\linewidth}}}
	\toprule[1.25pt]
	& \textbf{256KB} & \textbf{512KB} & \textbf{1MB} & \textbf{2MB} \\ \midrule
	\textbf{Unencrypted} & 11.06  & 22.45   & 43.91 & 92.2  \\ \midrule
	\textbf{CryptMPI} 	&  20.01  & 40.18 	& 79.48 & 168.76  \\ \midrule
	\textbf{Naive} 		&  20.26 &  40.51	& 79.72 & 143.63  \\
	\bottomrule[1.25pt]
	\end{tabular}
	\caption{Average time (seconds) of 3D Stencil(90\% computation and 10\% communication), 784-rank and 112-node, on InfiniBand.}
	\label{tab:3D_INFINIBAND_INTER_NODE_90_PERCENTAGE}
	\end{table}

\heading{4D Stencil.} The average time of 4D stencil for different computation
and communication percentage is present in the Table~\ref{tab:4D_INFINIBAND_INTER_NODE_20_PERCENTAGE},
~\ref{tab:4D_INFINIBAND_INTER_NODE_45_PERCENTAGE}, and ~\ref{tab:4D_INFINIBAND_INTER_NODE_75_PERCENTAGE}.
4D stencil shows the similar behavior as 2D stencil for 256KB and 512KB message. On 2MB (75\% computation),
it saved time is the close of 25\% computation time.

\begin{table}[!t]
	\centering
	\begin{tabular}{p{0.20\linewidth}*4{p{0.09\linewidth}}}
	\toprule[1.25pt]
	& \textbf{256KB} & \textbf{512KB} & \textbf{1MB} & \textbf{2MB} \\ \midrule
	\textbf{Unencrypted} & 4.25  & 8.77  & 17.89 & 34.76  \\ \midrule
	\textbf{CryptMPI} 	&  4.24	& 8.72 	& 17.55 & 34.21  \\ \midrule
	\textbf{Naive} 		&  5.2 & 9.89 & 18.15 & 38.27  \\
	\bottomrule[1.25pt]
	\end{tabular}
	\caption{Average time (seconds) of 4D Stencil(20\% computation and 80\% communication), 784-rank and 112-node, on InfiniBand.}
	\label{tab:4D_INFINIBAND_INTER_NODE_20_PERCENTAGE}
	\end{table}

	\begin{table}[!t]
	\centering
	\begin{tabular}{p{0.20\linewidth}*4{p{0.09\linewidth}}}
	\toprule[1.25pt]
	& \textbf{256KB} & \textbf{512KB} & \textbf{1MB} & \textbf{2MB} \\ \midrule
	\textbf{Unencrypted} & 4.26  &  8.79    & 17.98  & 35.7  \\ \midrule
	\textbf{CryptMPI} 	&  4.56	 &  9.97	& 20.27  & 38.61  \\ \midrule
	\textbf{Naive} 		&  5.76  &  12.31	& 23.76  & 48.24   \\
	\bottomrule[1.25pt]
	\end{tabular}
	\caption{Average time (seconds) of 4D Stencil(45\% computation and 55\% communication), 784-rank and 112-node, on InfiniBand.}
	\label{tab:4D_INFINIBAND_INTER_NODE_45_PERCENTAGE}
	\end{table}

	\begin{table}[!t]
	\centering
	\begin{tabular}{p{0.20\linewidth}*4{p{0.09\linewidth}}}
	\toprule[1.25pt]
	& \textbf{256KB} & \textbf{512KB} & \textbf{1MB} & \textbf{2MB} \\ \midrule
	\textbf{Unencrypted} & 7.38   &  16.66  & 35.21 & 68.33  \\ \midrule
	\textbf{CryptMPI} 	&  12.03  &  27.21	& 53.27 & 98.52  \\ \midrule
	\textbf{Naive} 		&  12.17 &  27.53	& 54.61 &  103.09 \\
	\bottomrule[1.25pt]
	\end{tabular}
	\caption{Average time (seconds) of 4D Stencil(75\% computation and 25\% communication), 784-rank and 112-node, on InfiniBand.}
	\label{tab:4D_INFINIBAND_INTER_NODE_75_PERCENTAGE}
	\end{table}

	\fi

\section{Related work}
\label{sec:related}

Most prior systems of encrypted
MPI~\cite{Ruan:2012:EMP:2197079.2197242,Maffina2013,RTSJ16,Shivaramakrishnan2014} only use weak encryption schemes, and therefore fail to deliver privacy.
For example, the ES-MPICH2 system~\cite{Ruan:2012:EMP:2197079.2197242}
relies on the Electronic Codebook (ECB) mode,
which is deemed insecure by cryptography textbooks~\cite[page 89]{Book:KL14}.
Likewise, the VAN-MPICH2 system~\cite{RTSJ16} attempts to build its
own encryption scheme, but this is trivially broken~\cite{Cluster:Naser19}.
In addition, those systems  also do not provide integrity.
Some, for example, use encryption with a form of checksum~\cite{Maffina2013},
but this approach does not provide integrity if the encryption scheme is the standard Cipher Block Chaining (CBC) mode of encryption~\cite{C:HB01}.
See the work of Naser et al.~\cite{Cluster:Naser19} for details of
the insecurity of the prior systems of encrypted MPI. Additionally, these
earlier systems were designed when the communication bottleneck was in
network links. As such, they do not consider techniques to optimize the use
of computing resources at end-nodes to maximize the encrypted communication
performance.

The work of Naser et al.~\cite{Cluster:Naser19} is the only existing
system that provides adequate privacy and integrity protection for MPI.
However, they only aim to investigate the performance of existing
cryptographic libraries in the MPI environment via a vanilla implementation.
Consequently, their system incurs high overheads as shown in
\figref{fig:motivate}. This motivates us to build a system that
meets both security and efficiency requirements of MPI applications.

\subsubsection{#1.}}
\newcommand{\headingb}[1]{\vspace{-5pt}\subsubsection{#1.}}
\newcommand{\heading}[1]{\vspace{5pt}\noindent\underline{\textsc{#1}}}
\newcommand{\headingu}[1]{\underline{\textsf{#1}}}
\newcommand{\noskipheading}[1]{\noindent\underline{\textsc{#1}}}
\newcommand{\noskipheadingu}[1]{\noindent\underline{\textsc{#1}}}
\newcommand{\headingg}[1]{\noindent\underline{\textsc{#1}}}

\newcommand{\twoColsNoDivide}[4]{
\begin{center}
        \framebox{
        \begin{tabular}{c@{\hspace*{.4em}}c@{\hspace*{.4em}}c}
        \begin{minipage}[t]{#1\textwidth}\setstretch{1.05}\small #3 \end{minipage}
        &
        \begin{minipage}[t]{#2\textwidth}\setstretch{1.05}\small #4 \end{minipage}
        \end{tabular}
        }
\end{center}
}

\newcommand{\twoCols}[4]{
\begin{center}
        \framebox{
        \begin{tabular}{c@{\hspace*{.4em}}|c@{\hspace*{.4em}}c}
        \begin{minipage}[t]{#1\textwidth}\setstretch{1.05}\small #3 \end{minipage}
        &
        \begin{minipage}[t]{#2\textwidth}\setstretch{1.05}\small #4 \end{minipage}
        \end{tabular}
        }
\end{center}
}

\newcommand{\oneCol}[2]{
\begin{center}
        \framebox{
        \begin{tabular}{c@{\hspace*{.4em}}}
        \begin{minipage}[t]{#1\textwidth}\setstretch{1.05}\small #2 \end{minipage}
        \end{tabular}
        }
\end{center}
}

\newcommand{\twoColsTwoRows}[6]{
\begin{center}
        \framebox{
        \begin{tabular}{c@{\hspace*{.4em}}|c@{\hspace*{.4em}}c}
        \begin{minipage}[t]{#1\textwidth}\setstretch{1.05}\small #3 \end{minipage}
        &
        \begin{minipage}[t]{#2\textwidth}\setstretch{1.05}\small #4 \end{minipage}
        \\ \hline
        \begin{minipage}[t]{#1\textwidth}\setstretch{1.05}\small #5
        \end{minipage} &
        \begin{minipage}[t]{#2\textwidth}\setstretch{1.05}\small #6
        \end{minipage}
        \end{tabular}
        }
\end{center}
}
\newcommand{\threeCols}[6]{
\begin{center}
        \framebox{
        \begin{tabular}{@{\hspace{-0.2em}}c@{\hspace{0.2em}}|@{\hspace{0.2em}}c@{\hspace{0.2em}}|@{\hspace{0.2em}}c@{\hspace{0.2em}}}
        \begin{minipage}[t]{#1\textwidth}\setstretch{1.05}\small #4
        \end{minipage} &
        \begin{minipage}[t]{#2\textwidth}\setstretch{1.05}\small #5
        \end{minipage} &
        \begin{minipage}[t]{#3\textwidth}\setstretch{1.05}\small #6
        \end{minipage}
        \end{tabular}
        }
\end{center}
}

\newcommand{\threeColstwoSplit}[6]{
\begin{center}
        \framebox{
        \begin{tabular}{@{\hspace{-0.2em}}c@{\hspace{0.2em}}|@{\hspace{0.2em}}c@{\hspace{0.2em}}@{\hspace{0.2em}}c@{\hspace{0.2em}}}
        \begin{minipage}[t]{#1\textwidth}\setstretch{1.05}\small #4
        \end{minipage} &
        \begin{minipage}[t]{#2\textwidth}\setstretch{1.05}\small #5
        \end{minipage} &
        \begin{minipage}[t]{#3\textwidth}\setstretch{1.05}\small #6
        \end{minipage}
        \end{tabular}
        }
\end{center}
}

\newcommand{\fourColstwoSplit}[8]{
\begin{center}
        \framebox{
        \begin{tabular}{@{\hspace{-0.2em}}c@{\hspace{0.2em}}|@{\hspace{0.2em}}c@{\hspace{0.2em}}@{\hspace{0.2em}}c@{\hspace{0.2em}}@{\hspace{0.2em}}c@{\hspace{0.2em}}}
        \begin{minipage}[t]{#1\textwidth}\setstretch{1.05}\small #5
        \end{minipage} &
        \begin{minipage}[t]{#2\textwidth}\setstretch{1.05}\small #6
        \end{minipage} &
        \begin{minipage}[t]{#3\textwidth}\setstretch{1.05}\small #7
        \end{minipage}  &
        \begin{minipage}[t]{#4\textwidth}\setstretch{1.05}\small #8
        \end{minipage}
        \end{tabular}
        }
\end{center}
}

\newcommand{\threeColsSplit}[6]{
\begin{center}
        \framebox{
        \begin{tabular}{@{\hspace{-0.2em}}c@{\hspace{0.2em}}||@{\hspace{0.2em}}c@{\hspace{0.2em}}|@{\hspace{0.2em}}c@{\hspace{0.2em}}}
        \begin{minipage}[t]{#1\textwidth}\setstretch{1.05}\small #4
        \end{minipage} &
        \begin{minipage}[t]{#2\textwidth}\setstretch{1.05}\small #5
        \end{minipage} &
        \begin{minipage}[t]{#3\textwidth}\setstretch{1.05}\small #6
        \end{minipage}
        \end{tabular}
        }
\end{center}
}

\newcommand{\fourCols}[8]{
\begin{center}
        \framebox{
        \begin{tabular}{@{\hspace{-0.2em}}c@{\hspace{0.2em}}|@{\hspace{0.2em}}c@{\hspace{0.2em}}|@{\hspace{0.2em}}c@{\hspace{0.2em}}|@{\hspace{0.2em}}c@{\hspace{0.2em}}}
        \begin{minipage}[t]{#1\textwidth}\setstretch{1.05}\small #5
        \end{minipage} &
        \begin{minipage}[t]{#2\textwidth}\setstretch{1.05}\small #6
        \end{minipage} &
        \begin{minipage}[t]{#3\textwidth}\setstretch{1.05}\small #7
        \end{minipage}&
        \begin{minipage}[t]{#4\textwidth}\setstretch{1.05}\small #8
        \end{minipage}
        \end{tabular}
        }
\end{center}
}

\newcommand{\threeColsTwoRows}[9]{
\begin{center}
        \framebox{
        \begin{tabular}{c@{\hspace*{.4em}}|c@{\hspace*{.4em}}|c@{\hspace*{.4em}}}
        \begin{minipage}[t]{#1\textwidth}\setstretch{1.05}\small #4
        \end{minipage} &
        \begin{minipage}[t]{#2\textwidth}\setstretch{1.05}\small #5
        \end{minipage} &
        \begin{minipage}[t]{#3\textwidth}\setstretch{1.05}\small #6
        \end{minipage}\\\hline
        \begin{minipage}[t]{#1\textwidth}\setstretch{1.05}\small
         #7 \end{minipage} &
        \begin{minipage}[t]{#2\textwidth}\setstretch{1.05}\small
         #8 \end{minipage} &
        \begin{minipage}[t]{#3\textwidth}\setstretch{1.05}\small
         #9
        \end{minipage}
        \end{tabular}
        }
\end{center}
}

\newcommand{\threeColsNoBox}[3]{
\begin{center}\begin{tabular}{c|c|c}
\begin{minipage}[t]{1in}\begin{tabbing}
12\=12\=12\=\kill
#1
\end{tabbing}\end{minipage} &
\begin{minipage}[t]{1in}\begin{tabbing}
12\=12\=12\=\kill
#2
\end{tabbing}\end{minipage} &
\begin{minipage}[t]{1in}\begin{tabbing}
12\=12\=12\=\kill
#3
\end{tabbing}\end{minipage}
\end{tabular}\end{center}}

\newcommand{\fourColsNoBox}[4]{
\begin{center}\begin{tabular}{c|c|c|c}
\begin{minipage}[t]{1in}\begin{tabbing}
12\=12\=12\=\kill
#1
\end{tabbing}\end{minipage} &
\begin{minipage}[t]{1in}\begin{tabbing}
12\=12\=12\=\kill
#2
\end{tabbing}\end{minipage} &
\begin{minipage}[t]{1in}\begin{tabbing}
12\=12\=12\=\kill
#3
\end{tabbing}\end{minipage} &
\begin{minipage}[t]{1in}\begin{tabbing}
12\=12\=12\=\kill
#4
\end{tabbing}\end{minipage}
\end{tabular}\end{center}}

\newcommand{\twoColsNoBox}[4]{
\begin{center}
        \begin{tabular}{c@{\hspace*{.4em}}|c@{\hspace*{.4em}}c}
        \begin{minipage}[t]{#1\textwidth}\setstretch{1.05}\small #3 \end{minipage}
        &
        \begin{minipage}[t]{#2\textwidth}\setstretch{1.05}\small #4 \end{minipage}
        \end{tabular}
\end{center}
}

\newcommand{\twoColsNoBoxNoDivide}[2]{
\begin{center}\begin{tabular}{ccc}
\begin{minipage}[t]{1in}\begin{tabbing}
12\=12\=12\=\kill
#1
\end{tabbing}\end{minipage} & \hspace{10pt} &
\begin{minipage}[t]{1in}\begin{tabbing}
12\=12\=12\=\kill
#2
\end{tabbing}\end{minipage}
\end{tabular}\end{center}}

\newcommand{\threeColsNoBoxOneDivide}[3]{
\begin{center}\begin{tabular}{ccc|c}
\begin{minipage}[t]{1in}\begin{tabbing}
12\=12\=12\=\kill
#1
\end{tabbing}\end{minipage} & \hspace{10pt} &
\begin{minipage}[t]{1in}\begin{tabbing}
12\=12\=12\=\kill
#2
\end{tabbing}\end{minipage} &
\begin{minipage}[t]{1in}\begin{tabbing}
12\=12\=12\=\kill
#2
\end{tabbing}\end{minipage}
\end{tabular}\end{center}}

\newcommand{\oneColNoBox}[1]{
\begin{center}\begin{tabular}{c}
\begin{minipage}[t]{1in}\begin{tabbing}
123\=123\=123\=\kill
#1
\end{tabbing}\end{minipage}
\end{tabular}\end{center}}

\newcommand{\mathrm{Keys}}{\mathrm{Keys}}
\newcommand{\mathrm{Dom}}{\mathrm{Dom}}

\newcommand{\secref}[1]{Section~\ref{#1}}
\newcommand{\apref}[1]{Appendix~\ref{#1}}
\newcommand{\thref}[1]{Theorem~\ref{#1}}
\newcommand{\sthref}[1]{Th.~\ref{#1}}
\newcommand{\defref}[1]{Definition~\ref{#1}}
\newcommand{\corref}[1]{Corollary~\ref{#1}}
\newcommand{\scorref}[1]{Cor.~\ref{#1}}
\newcommand{\lemref}[1]{Lemma~\ref{#1}}
\newcommand{\clref}[1]{Claim~\ref{#1}}
\newcommand{\propref}[1]{Proposition~\ref{#1}}
\newcommand{\factref}[1]{Fact~\ref{#1}}
\newcommand{\remref}[1]{Remark~\ref{#1}}
\newcommand{\obsref}[1]{Observation~\ref{#1}}
\newcommand{\figref}[1]{\textmd{Fig.}~\ref{#1}}
\newcommand{\tabref}[1]{Table~\ref{#1}}
\newcommand{\consfigref}[1]{Construction~\ref{#1}}
\renewcommand{\eqref}[1]{\mbox{Eq.~(\ref{#1})}}
\newcommand{\mathrm{IV}}{\mathrm{IV}}
\newcommand{{\,\|\,}}{{\,\|\,}}

\newcommand{{\:{\leftarrow{\hspace*{-3pt}\raisebox{.75pt}{$\scriptscriptstyle\$$}}}\:}}{{\:{\leftarrow{\hspace*{-3pt}\raisebox{.75pt}{$\scriptscriptstyle\$$}}}\:}}
\newcommand{\bm{M}}{\bm{M}}
\newcommand{\textbf{procedure }}{\textbf{procedure }}

\newcommand{\commentt}[1]{\small {// #1}}
\newcommand{\textbf{for }}{\textbf{for }}
\newcommand{\textbf{to }}{\textbf{to }}
\newcommand{\textbf{do }}{\textbf{do }}
\def\:;\:{\:;\:}
\newcommand{\hspace*{10pt}}{\hspace*{10pt}}
\newcommand{\textsl{last}}{\textsl{last}}
\newcommand{\textbf{if }}{\textbf{if }}
\newcommand{\textbf{else }}{\textbf{else }}
\newcommand{\textbf{then }}{\textbf{then }}
\newcommand{\mathsf{GCM}.\mathsf{Enc}}{\mathsf{GCM}.\mathsf{Enc}}
\newcommand{\textbf{return}}{\textbf{return}}
\newcommand{\textsl{Header}}{\textsl{Header}}
\newcommand*{{\sffamily CryptMPI}\xspace}{{\sffamily CryptMPI}\xspace}
\newcommand{\textrm{CryptMPI}}{\textrm{CryptMPI}}
\newcommand{\textrm{FastCTR}}{\textrm{FastCTR}}

\newtheorem{theorem}{Theorem}
\newtheorem{lemma}{Lemma}
\newtheorem{proposition}{Proposition}

\newcommand{\texttt{Enc}}{\texttt{Enc}}
\newcommand{\texttt{Dec}}{\texttt{Dec}}
\newcommand{\texttt{Gen}}{\texttt{Gen}}
\newcommand{{\mathcal M}}{{\mathcal M}}

\newcommand{T_{\mathrm{comm}}}{T_{\mathrm{comm}}}
\newcommand{\alpha_{\mathrm{comm}}}{\alpha_{\mathrm{comm}}}
\newcommand{\beta_{\mathrm{comm}}}{\beta_{\mathrm{comm}}}
\newcommand{T_{\mathrm{enc}}}{T_{\mathrm{enc}}}
\newcommand{\alpha_{\mathrm{enc}}}{\alpha_{\mathrm{enc}}}
\newcommand{\beta_{\mathrm{enc}}}{\beta_{\mathrm{enc}}}
\newcommand{T_{\mathrm{ecom}}}{T_{\mathrm{ecom}}}
\newcommand{\alpha_{\mathrm{ecom}}}{\alpha_{\mathrm{ecom}}}
\newcommand{\beta_{\mathrm{ecom}}}{\beta_{\mathrm{ecom}}}
\newcommand{R_{\mathrm{enc}}}{R_{\mathrm{enc}}}
\newcommand{R_{\mathrm{comm}}}{R_{\mathrm{comm}}}
\newcommand{A_{\mathrm{comm}}}{A_{\mathrm{comm}}}
\newcommand{B_{\mathrm{comm}}}{B_{\mathrm{comm}}}
\newcommand{\boldsymbol{C}}{\boldsymbol{C}}
\newcommand{\mathrm{AES}}{\mathrm{AES}}

\newcommand{\texttt{MPI\_IRecv} }{\texttt{MPI\_IRecv} }
\newcommand{\texttt{MPI\_Recv} }{\texttt{MPI\_Recv} }
\newcommand{\texttt{MPI\_ISend} }{\texttt{MPI\_ISend} }
\newcommand{\texttt{MPI\_Send} }{\texttt{MPI\_Send} }

\newcommand{\texttt{MPI\_Wait} }{\texttt{MPI\_Wait} }
\newcommand{\texttt{MPI\_Waitall} }{\texttt{MPI\_Waitall} }
\newcommand{\texttt{Encrypted\_Alltoall} }{\texttt{Encrypted\_Alltoall} }
\newcommand{\texttt{Encrypted\_Allgather} }{\texttt{Encrypted\_Allgather} }
\newcommand{\texttt{Encrypted\_Alltoallv} }{\texttt{Encrypted\_Alltoallv} }
\newcommand{\texttt{Encrypted\_IRecv} }{\texttt{Encrypted\_IRecv} }
\newcommand{\texttt{Encrypted\_Bcast} }{\texttt{Encrypted\_Bcast} }
\newcommand{\texttt{MPI\_Init}}{\texttt{MPI\_Init}}
\newcommand{{pk}}{{pk}}
\newcommand{{sk}}{{sk}}
\newcommand{\texttt{MPI\_Gather}}{\texttt{MPI\_Gather}}
\newcommand{\texttt{MPI\_Scatter}}{\texttt{MPI\_Scatter}}
\newcommand{\mathcal{K}}{\mathcal{K}}
\newcommand{{\emph{Unencrypted}}}{{\emph{Unencrypted}}}
\newcommand{{\emph{Naive}}}{{\emph{Naive}}}
\newcommand{T_i}{T_i}
\newcommand{T_c}{T_c}
\newcommand{T_e}{T_e}

\title{\textrm{CryptMPI}: A Fast Encrypted MPI Library}
\author{

\IEEEauthorblockN{Abu Naser \hspace{0.1in} Cong Wu \hspace{0.1in} Mehran Sadeghi Lahijani \hspace{0.1in} Mohsen Gavahi \hspace{0.1in} Viet Tung Hoang \hspace{0.1in} Zhi Wang \hspace{0.1in} Xin Yuan}
\IEEEauthorblockA{Department of Computer Science, Florida State University, Tallahassee, FL 30306\\
\{naser,wu,sadeghil,gavahi,tvhoang,zwang,xyuan\}@cs.fsu.edu}
}

\date{}

\begin{document}

\maketitle

\input{abs}

\input{intro}
\input{related}
\input{background}
\input{ours}
\input{perf}
\input{conclusion}

\bibliographystyle{unsrt}