# Minimizing Information Leakage under Padding Constraints

Sebastian Simon  LIX
École Polytechnique
Paris, France  Cezara Petrui  LIX
École Polytechnique
Paris, France  Carlos Pinzón  Inria and LIX
École Polytechnique
Paris, France  Catuscia Palamidessi  Inria and LIX
École Polytechnique
Paris, France

###### Abstract

An attacker can gain information of a user by analyzing its network traffic.
The size of transferred data leaks information about the file being
transferred or the service being used, and this is particularly revealing when
the attacker has background knowledge about the files or services available
for transfer. To prevent this, servers may pad their files using a _padding
scheme_ , changing the file sizes and preventing anyone from guessing their
identity uniquely. This work focuses on finding optimal padding schemes that
keep a balance between privacy and the costs of bandwidth increase. We
consider Rényi-min leakage as our main measure for privacy, since it is
directly related with the success of a simple attacker, and compare our
algorithms with an existing solution that minimizes Shannon leakage. We
provide improvements to our algorithms in order to optimize average total
padding and Shannon leakage while minimizing Rényi-min leakage. Moreover, our
algorithms are designed to handle a more general and important scenario in
which multiple servers wish to compute padding schemes in a way that protects
the servers’ identity in addition to the identity of the files.

###### Index Terms:

network traffic analysis, privacy, padding, renyi entropy, leakage, adversary,
server identity, file identity

##  I Introduction

This paper focuses on the problem of minimizing the information that an
adversary can obtain when he analyzes the network traffic of a user.

Network traffic analysis is a powerful tool that is needed for optimizing the
routing and transmission speed of data in telecommunications networks [Wel05,
PLB11], as well as for detecting anomalies [BBK17] and possibly some types of
attacks. In addition to this, traffic analysis is, on its own, a subject which
sparks various research topics. For instance, there has been discovered
evidence of self-similar patterns in network traffic [PW00]. Nonetheless, it
can also be used to infer users’ demographics [LXZ+16] and the types of web
services they are using [HKDV15, CKS+09]. Therefore, network traffic analysis
is an active and important research topic in telecommunications, networking,
privacy, computer security, as well as in mathematics.

Since the vast majority of modern traffic is encrypted, the research on
traffic analysis has increasingly been focused towards the analysis of
encrypted traffic, in which the adversary willing to gain information can not
observe the content of the messages, but can make inferences based on their
timing and sizes. Although data-encryption provides a strong limitation for
the attacker, it is possible, with a substantial degree of accuracy, to detect
information about the activity of the users, such as what site is being
browsed [SJVR+18, CHJ17] or the format of a streamed video [WUB15].

Moreover, as pointed out in [WCM09], packet sizes and timing are essential
tools that can reveal the language of a VoIP call [WBMM07], passwords in
secure shell logins [Son01], or even web browsing habits [SSW+02, LL06]. The
danger of these inferences is highly increased when the adversary combines
several of them, possibly also with additional background knowledge about the
user or about application standards, e.g. if Google Meet and Skype use
different video formats by default, the attacker would be able to identify
which application is being used.

Padding messages is a well-known technique for reducing the quality of the
inferences that the traffic observer can do. It increases the sizes of the
files being transferred across a network in order to make them harder to
recognize. More precisely, padding reduces the probability that the attacker
infers correctly the file being transferred. But it also increases the
bandwidth use of the network. Therefore, it is necessary to design padding-
schemes that achieve an optimal trade-off between reducing bandwidth overhead
and its costs while maintaining a high level of privacy.

We propose different algorithms that minimize Rényi-min leakage subject to
three different types of bandwidth constraints that occur naturally in
practice. We prove the correctness of all the algorithms described in the
paper, test them against brute-force implementations over small datasets, and
compare them to other methods in the literature over a large dataset.

##  II Related Works

The need for padding has been identified already in [SJVR+18] and solved for
specific applications in [WCM09] and [RR21].

This paper is strongly related with the work of Reed and Reiter [RR21], in
which the authors propose three padding algorithms, PRP_Shannon, POP_Shannon
(referred to as PopSh in this document) and PwoD (padding without a
distribution), for finding padding schemes that minimize Shannon leakage under
different bandwidth constraints. They formalize the padding problem as a
server that pads its files before or while serving them to clients.

We extend [RR21] in two ways. First, we take also into consideration the
problem of _server identity protection_ , in which several servers coordinate
themselves before deploying their optimal padding-schemes such as to protect
their identities in addition to the individual identities of the files. We
adequate their POP algorithm to minimize Shannon leakage for this new
scenario. Secondly, we redesign all their algorithms to find padding functions
that minimize Rényi-min leakage [Smi09a] instead of Shannon leakage, and we
provide some heuristics for Rényi-then-Shannon and Rényi-then-bandwidth
minimization, i.e. finding among all schemes that minimize Rényi-min leakage,
the one that minimize Shannon leakage or bandwidth respectively.

We believe that Rényi-min leakage is a better metric for privacy than Shannon
leakage for the the file padding problem. We justify this claim in this paper
by pointing out that Rényi-min leakage is directly related via a bijective
function with the probability of an attacker’s best inference to be true. This
correspondence can also be interpreted as an instance (to network traffic
analysis) of the general operational interpretation of Rényi-min leakage in
terms of one-try attacks [Smi09a]. For Shannon, which is more related to
information theoretic applications like compression, the attackers’ success
and the leakage are highly correlated, however, they are not directly related
via a linear function. This fact is corroborated experimentally in [RR21], as
well as in our paper.

In general, in the privacy community, metrics are better described in terms of
their associated attacker rather than their information-theoretic properties
[ACPS12, Rom20]. For this particular application, the direct pragmatic
connection between Rényi-min leakage and a simple adversary success makes it
very appealing. The same argument is used in [Che17], whose privacy measure is
closely related with ours.

##  III Problem formalization

Generally speaking, the objective is to determine how much to pad each of the
files stored in a server to minimize the information gained by a potential
adversary analyzing network traffic.

The files in the server store are denoted as
$E=\\{e_{1},e_{2},\dots,e_{n}\\}$. We assume the files in $E$ to be sorted
non-decreasingly by their sizes ${|e_{i}|}$, and to be accessed with frequency
$p_{i}\in[0,1]$, where $\sum_{i=1}^{n}p_{i}=1$. To denote a random file from
the server, we use the random variable $X$ that takes values in $E$ with
probabilities
$\IfStrEq{X=e_{i}}{{{\operatorname*{\mathbb{P}}}(\mathbb{P}{(X{\mkern
0.0mu\mathchar 61\relax\mkern
1.0mu}e_{i})})}\stackrel{{\scriptstyle{\scriptscriptstyle\mathrm{def}}}}{{\coloneqq}}p_{i}}$.
We define the set of file sizes
$S\stackrel{{\scriptstyle{\scriptscriptstyle\mathrm{def}}}}{{\coloneqq}}{\\{|e||e\in
E\\}}$ and enumerate its unique elements in increasing order as
$S=\\{s_{1},s_{2},\dots,s_{m}\\}$. Note that $m\leq n$, since there may be
different files with the same size.

Given a fixed multiplicative constraint $c\geq 1$, a _padding function_ , or
padding scheme, is a (possibly randomized) function $f:E\rightarrow\mathbb{N}$
that satisfies, for all $i\in[1..n]$, ${|e_{i}|}\leq f(e_{i})\leq
c\cdot{|e_{i}|}$ (with probability $1$). The padding function will determine
the size of the files in the server after padding them, and the double
inequality represents, on the one hand, the fact that files can only be padded
to a size greater than the initial one:

$\IfStrEq{f(e)\geq{|e|}}{{{\operatorname*{\mathbb{P}}}(\mathbb{P}{(f(e)\geq{|e|})})}=1,}$
(III.1)

and on the other hand, the constraint of avoiding unexpectedly large paddings:

$\IfStrEq{f(e)\leq
c\cdot{|e|}}{{{\operatorname*{\mathbb{P}}}(\mathbb{P}{(f(e)\leq
c\cdot{|e|})})}=1.}$ (III.2)

The latter constraint guarantees both for the server and the client that the
bandwidth used is not excessive. It is multiplicative instead of additive
because we consider typical cases in which the largest files are accessed less
frequently than the smallest ones, hence, it is desirable to limit more
severely the padding added to smaller files. Also, it might be randomized in
case the server has the infrastructure to pad files independently for each
transfer request. Moreover, in the favor of clients, the constraint is
enforced for each individual file instead of a single global expectation of
bandwidth increase because if a client accesses just one or two files, it is
of his interest that the bandwidth is bounded for each of those two files.

The objective is to find a padding function $f:E\to\mathbb{N}$ that minimizes
a given metric of information leakage $\mathbb{I}({|X|},f(X))$, while
respecting the constraints ${|e_{i}|}\leq f(e_{i})\leq c\cdot{|e_{i}|}$, for
each $i\in\\{1,...,n\\}$.

In the rest of this section, we describe all the variations of the problem by
considering two different leakage functions from the literature, as well as
several additional types of constraints that may arise in real-world
applications.

###  III-A Leakage functions

In the literature there are multiple options for quantifying the leakage
$\mathbb{I}{({|X|},f(X))}$ of a padding function $f:E\rightarrow\mathbb{N}$.
We will further use the notation
$\mathbb{I}(f)\stackrel{{\scriptstyle{\scriptscriptstyle\mathrm{def}}}}{{\coloneqq}}\mathbb{I}{({|X|},f(X))}$
to reduce verbosity since the random variable $X$ is fixed.

In [RR21], they use Shannon mutual information as a leakage measure. Shannon
leakage is based on Shannon entropy $\mathbb{H}$ and is given by:

$\mathbb{I}_{1}{({|X|},f(X))}\stackrel{{\scriptstyle{\scriptscriptstyle\mathrm{def}}}}{{\coloneqq}}\mathbb{H}{({|X|})}-\mathbb{H}{({|X|}{\mkern
2.0mu\mid\mkern 1.5mu}f(X))}$ (III.3)

Shannon leakage is a particular case ($\alpha=1$) of a family of leakages
$\mathbb{I}_{\alpha}$ based on $\alpha$-Rényi entropy. A particular case of
interest for privacy applications is what we call _Rényi-min leakage_
($\alpha=\infty$), whose derivation and importance is highlighted in [PR18]
and [Smi09b]:

$\mathbb{I}_{\infty}({|X|},f(X))=\mathbb{H}_{\infty}({|X|})-\mathbb{H}_{\infty}({|X|}\mid
f(X)).$ (III.4)

Both Shannon leakage and Rényi-min leakage are directly related (in one-to-one
relation) to the probability of success of an attacker, but the specific
assumptions about the attacker and his objective are different. In the case of
Shannon leakage, the attacker is assumed to have the power to perform set-
queries of the type ”is the secret in _this_ set?”, and his objective is to
guess the secret using the minimal number of queries. For Rényi-min leakage,
the attackers’ power is reduced to a one-try attack, i.e. he can only make one
query of the type ”is _this_ the secret?”, and his objective is to maximize
the probability of being correct. In both cases, to protect against worst-case
scenarios, the attacker is assumed to know the server’s files’ sizes and
frequencies, as well as the padding-scheme used by the server. This knowledge
may arise in practice if the server hosts public files and the attacker has
had time to request each of the files, possibly multiple times in case of a
randomized padding scheme. Notice that the fact that the server files are
public, does not reduce at all the need for privacy. For instance, although
the files of an adult video site are public, the users are very interested
that no adversarial third party knows exactly which video is being watched.
Therefore, it is clear from the point of view of attackers, that Rényi-min
leakage is superior to Shannon leakage as a measure of privacy for this
particular application.

We conclude this section by proving an important property of padding functions
that minimize Rényi-min leakage. The same holds true for paddings that
minimize Shannon leakage, as shown in [RR21].

######  Proposition 1.

Let $\mathbb{I}$ denote Rényi-min leakage, $S$ the set of sizes of the files
and $f:E\rightarrow\mathbb{N}$ a padding-scheme. Then, there is a padding-
scheme $f^{*}:E\rightarrow S$ such that $\mathbb{I}(f^{*})\leq\mathbb{I}(f)$
and $\mathbb{I}_{\infty}(f^{*})\leq\mathbb{I}_{\infty}(f)$.

###### Proof.

We consider that the files are sorted in non-decreasing order with respect to
their sizes, denoted by the set $S=\\{s_{1},s_{2},\dots,s_{m}\\}$. We have $X$
the random variable associated to $E$ and denote the random variable $Y=f(X)$.
We define $g:\mathbb{N}\rightarrow S$ to be the function satisfying
$g(f(e_{i}))=\max\\{s\in S|s\leq f(e_{i})\\}$. Denote by $Z$ the random
variable $(g\circ f)(X)$ equipped with the probability space of $E$. We use
the Data Processing Inequality for ${|X|},Y,Z$ as stated in Theorem 6.2 of
[MCPS12] and Theorem 8 of [MMS+14], and remarked also in Theorem 5.1 of
[Smi15]. $Z$ only depends on $Y$ and is conditionally independent of ${|X|}$
because $Z$ is a deterministic function of $Y$. Since this holds for any
$g$-leakage function, we have
$\mathbb{I}({|X|},f(X))\geq\mathbb{I}({|X|},(g\circ f)(X))$ and
$\mathbb{I_{\infty}}({|X|},f(X))\geq\mathbb{I_{\infty}}({|X|},(g\circ f)(X))$.
Hence, we proved that there exists a function $f^{*}=g\circ f:E\rightarrow S$
such that it has a lower leakage than $f$. ∎

######  Corollary 2.

A padding function that has minimal leakage must pad each file to the size of
another file in the initial set.

###  III-B Variations of the padding problem

The padding problem can have additional restrictions that arise commonly in
practice, giving rise to the following variations, of which the first two are
also considered in [RR21].

  1. 1.

POP (Per-object-padding)

In this variation, the server plans to pad the files only once and forever.
This saves the server from costs and complexity associated to repeated
padding. Hence, our objective in this variation is to compute a deterministic
padding function $f$.

  2. 2.

PRP (Per-request-padding)

In this variation, we assume no additional constraints to the padding function
others than Equations III.1 and III.2. This means that the store can pad the
files before every transaction.

  3. 3.

Server identity protection

Note that although the generic problem has no restriction on the output sizes
$f(X)$, Corollary 2 implies that the optimal padding is achieved when
$f(X)=S$, meaning that the files of the store can only be padded to sizes of
other files in the set $E$. This fact has a critical implication regarding the
protection of server identities. For instance, assume that an attacker who
knows that server $A$ and $B$ have file sizes $20,22,24$ and $21,23,25$
respectively, and he observes a (padded) file of size $22$ being transferred
to a user; then he does not know if the file is that of size $20$ or $22$, due
to padding, but he knows certainly that the user accessed server $A$. In order
to protect the server identity, we suggest a standardized protocol among the
servers. This protocol involves having all the servers padding the files to
the same pre-determined set of sizes $Z$ such that $f(X)\subset Z$. In
practice, $Z$ can be a set of rounded sizes such as
$\\{5\texttt{Mb},10\texttt{Mb},20\texttt{Mb},30\texttt{Mb},\dots\\}$. We keep
the padding constant $c$ and conditions (III.1) and (III.2). Additionally, we
add the constraint that, $\forall{i\in[1..n]}$:

${\\{z\in Z{\mkern 2.0mu\mid\mkern 1.5mu}z\geq{|e_{i}|},\;z\leq
c\cdot{|e_{i}|}\\}}\neq\emptyset$ (III.5)

meaning that the set $Z$ has enough possible padding sizes to be consistent
with (III.2). Moreover, the protocol aforementioned for protecting the servers
holds not only for Per-Object-Padding, but also for Per-Request-Padding, i.e.
it does not influence in any way if the padding function $f$ is deterministic
or probabilistic, since we can apply the same procedure for both cases.

###  III-C Generalization

All the aforementioned variations of the padding problem can be written as
instances of a single input-output problem specification. The specification
requires to standardize the bandwidth constraints as pairs $[l_{i},r_{i}]$,
meaning that file $e_{i}$ can only be padded to sizes
${\\{z_{l_{i}},...,z_{r_{i}}\\}}$, for some fixed increasing sequence of
output values $Z={\\{z_{1},...,z_{|Z|}\\}}$. Naturally, these pairs must
satisfy some minimal properties to reflect a possible instance of the padding
problem. Namely, we say a sequence ${\\{{[l_{i},r_{i}]}\\}}_{i\mathchar
61\relax 1}^{n}$ is _a valid sequence of constraints_ for $Z$ if $l_{i}\leq
r_{i}$ holds for all $i\in[1..n]$, and the sequences
${\\{l_{i}\\}}_{i\mathchar 61\relax 1}^{n}$ and ${\\{r_{i}\\}}_{i\mathchar
61\relax 1}^{n}$ are non-decreasing and satisfy $l_{1}=1$ and
$l_{n}=r_{n}=|Z|$.

We now state the problem specification and proceed to explain how it captures
all variations of the padding problem. All the algorithms in following
sections follow this specification.

######  Problem specification 3.

Input:

  * A set $E$ of $n$ files ${\\{e_{i}{\mkern 2.0mu\mid\mkern 1.5mu}i\in[1..n]\\}}$ with sizes ${|e_{i}|}$ and frequencies $p_{i}$; a set $Z$ of possible output sizes ($Z=S$ unless otherwise specified) with a valid sequence of constraints ${\\{[l_{i},r_{i}]\\}}_{i\mathchar 61\relax 1}^{n}$; and a leakage function $\mathbb{I}$ that measures the informational leakage of padding-schemes.

Desired output:

  * A padding function $f:E\to Z$ (deterministic for POP, possibly randomized for PRP) that minimizes the information leakage $\mathbb{I}({|X|},f(X))$, where $\IfStrEq{X=e_{i}}{{{\operatorname*{\mathbb{P}}}(\mathbb{P}{(X{\mkern 0.0mu\mathchar 61\relax\mkern 1.0mu}e_{i})})}\stackrel{{\scriptstyle{\scriptscriptstyle\mathrm{def}}}}{{\coloneqq}}p_{i}}$ for each $i\in\\{1,...,n\\}$.

If $f$ is deterministic, it can be encoded as a list ${(f(e_{i}))}_{i\mathchar
61\relax 1}^{n}$, and in the general probabilistic case as the channel-matrix
$(p_{ij})$ of size $n\times|Z|$ between the secrets $X$ and the observables
$f(X)$.

Firstly, we argue that the specification generalizes the variations POP and
PRP. In both cases, we invoke Corollary 2 which mandates $Z=S$, hence the the
padding function will have signature $f:E\rightarrow S$. Condition (III.1) is
attained by choosing
$l_{i}\stackrel{{\scriptstyle{\scriptscriptstyle\mathrm{def}}}}{{\coloneqq}}\min{\\{j\in[1..m]{\mkern
2.0mu\mid\mkern 1.5mu}{|e_{j}|}\geq{|e_{i}|}\\}}$ and
$r_{i}\stackrel{{\scriptstyle{\scriptscriptstyle\mathrm{def}}}}{{\coloneqq}}\max{\\{j\in[1..m]{\mkern
2.0mu\mid\mkern 1.5mu}s_{j}\leq c\cdot{|e_{i}|}\\}}$, thus specifying the
padding restriction individually for each file. Note that this also
generalizes POP and PRP, allowing the store to have special padding
restrictions for each specific file rather than a universal constant $c$, e.g.
a list $c_{i}$ for $i\in[1..n]$.

Secondly, to deal with the server identity protection case, we start with a
padding-scheme $f:E\rightarrow Z$, the probability distribution $\mathbb{P}$,
and the set $S$, with the purpose of adapting these three to the generalized
problem. For each $i\in[1..n]$, let $L^{*}_{i}=\min{\\{z\in Z{\mkern
2.0mu\mid\mkern 1.5mu}z\geq{|e_{i}|}\\}}$, i.e. the smallest file size in $Z$
that file $e_{i}$ can be padded to. Define $e^{*}_{i}$ to be a file with size
$L^{*}_{i}$. Due to (III.5), $L^{*}_{i}$ exists, $\forall{i\in[1..n]}$, and
consider the multiset $S^{*}:={\\{L^{*}_{i}{\mkern 2.0mu\mid\mkern
1.5mu}i\in[1..n]\\}}$. Because each file is mapped injectively to an element
of $S^{*}$, we consider that we pad each element to the closest one in $Z$ and
then apply the padding problem for the new files. Using this and Corollary 2,
we reduce the problem to finding a padding-scheme $f^{*}:E^{*}\rightarrow
S^{*}$, and a sequence of restrictions $[l_{i},r_{i}],i\in[1..n]$ that satisfy
the relation $r_{i}:=\max{\\{j{\mkern 2.0mu\mid\mkern 1.5mu}L^{*}_{j}<c\cdot
L^{*}_{i}\\}}$, where $L^{*}_{j}$ is the size of the file in $E^{*}$. Note
that the sizes of the files are given in the three variations of the problem,
but not in the generalization, as these can be reduced to the restrictions
sequence.

##  IV Algorithms (and proofs)

In this section, we give algorithms that minimize the Rényi-min leakage as
defined in (III.4) for the POP and PRP cases, namely PopRe and PrpRe, which
contrast those for Shannon mutual information minimization, found in the paper
[RR21]. The complexities of these algorithms are summarized in Table I.

Algorithm | Minimizes | WC Runtime complexity
---|---|---
PopRe | Rényi-min leakage | $O(n^{2}\,\bar{m})$
PrpRe | Rényi-min leakage | $O(n\,{\bar{m}})$
PopSh | Shannon leakage | $O(n\,{\bar{m}})$
ShannonPRP | Shannon leakage | $O(\textsc{iters}\cdot n\,m)$
Table I:  Complexities. Here, $m\leq n$ is the number of different file sizes
and
${\bar{m}}\stackrel{{\scriptstyle{\scriptscriptstyle\mathrm{def}}}}{{\coloneqq}}(\nicefrac{{1}}{{n}})\sum_{i=1}^{n}r_{i}-l_{i}+1$
is the average number of available choices for each file, thus,
$O(n\,{\bar{m}})\leq O(n\,m)$.

Notice that the algorithm ShannonPRP is an approximation algorithm and has a
runtime complexity that depends on the degree of accuracy imposed by the user
and the limit number of iterations iters allowed. Also, the complexities of
the dynamic programming algorithms appear overestimated in the theoretical
worst-case scenario when compared to the actual implementations. For instance,
although PopRe has two parameters varying in $[1..n]$, not all combinations
need to be calculated in a top-down implementation.

###  IV-A PopRe

In this section we develop the algorithm that minimizes Rényi-min leakage in
the POP variation following Specification 3. Before starting with the
algorithm, we will prove Observation 4, which will be used as the main update
of the entries of the channel-matrix.

Let $f:E\rightarrow S$ (by the Corollary 2) be an optimal padding-scheme. We
want to minimize

$\mathbb{I}_{\infty}({|X|},f(X))=\mathbb{H}_{\infty}({|X|})-\mathbb{H}_{\infty}({|X|}\mid
f(X)),$

but since $\mathbb{H}_{\infty}({|X|})$ is constant in regards to the padding-
scheme, maximizing $\mathbb{H}_{\infty}({|X|}\mid f(X))$ is a sufficient
condition. As introduced in [PR18], we have:

$\mathbb{H}_{\infty}({|X|}\mid
f(X))=-\log_{2}\sum_{j\in[1..m]}\max_{i\in[1..n]}(p_{i}\cdot\mathbb{P}(f(e_{i})=s_{j})).$

Given that $X\rightarrow f(X)$ can be seen as Markov Chain, it is natural to
denote $\mathbb{P}(f(e_{i})=s_{j})=p_{ij}$. Note that we are in the case of
per-object-padding, so $p_{ij}\in{\\{0,1\\}}\forall i\in[1..n]\text{ and
}j\in[1..m]$. Because the logarithmic function is increasing, the problem
reduces to minimizing:

$\sum_{j\in[1..m]}\max_{i\in[1..n]}(p_{i}\cdot p_{ij}).$ (IV.1)

$\vdots$$e_{9}$$e_{10}$$\mathbf{e_{11}}$$e_{12}$$\vdots$$\cdots$$s_{10}$$s_{11}$$\mathbf{s_{12}}$$s_{13}$$\cdots$$1$$1$$1$$\mathbf{1}$$1$$1$$0$$0$$0$$0$$0$$0$$0$$0$$0$$0$$0$$0$

$\vdots$$e_{9}$$e_{10}$$\mathbf{e_{11}}$$e_{12}$$\vdots$$\cdots$$s_{10}$$s_{11}$$\mathbf{s_{12}}$$s_{13}$$\cdots$$1$$\mathbf{1}$$\mathbf{1}$$\mathbf{1}$$\mathbf{1}$$1$$0$$0$$0$$0$$0$$0$$0$$0$$0$$0$$0$$0$

Figure IV.1:  Visualization for Observation 4. The file with maximal frequency
is $e_{11}$, and the left and right padding-schemes are respectively $f$ and
$f^{*}$. If the left one is optimal, the right one must be as well.

######  Observation 4.

Let $f$ be a Rényi-min optimal padding-scheme and $e_{i}$ be the file with the
highest associated frequency $p_{i}$, and assume that $p_{ij}=1$ for some
$j\in[1..m]$. Then there exists a padding-scheme $f^{*}$ with the same Rényi-
min leakage such that $p_{kj}=1$ for all $k\in[1..n]$ such that
$j\in[l_{k}..r_{k}]$.

###### Proof.

We consider the padding-scheme $f$ to be represented as the channel-matrix
between the secrets and the observables. Let $P$ be the $n\times m$ matrix
which contains on every entry $(a,b)$ with $a\in[1..n],b\in[1..m]$ the
probability $p_{ab}$. When we want to minimize (IV.1) we sum over each column
of the matrix $P$. In particular, on the column $j$ we have
$\max_{a\in[1..n]}(p_{a}\cdot p_{aj})=p_{i}$ since $p_{i}$ is the highest
frequency among the frequencies of the files and $p_{ij}=1$. Now, let us
consider the padding-scheme $f^{*}$ such that with the associated matrix
$P^{*}$, moving, on the same line, every 1 that we can to column j:

$p^{*}_{ab}=\begin{cases}p_{ab}&\text{ if }b\neq j\text{ and }a\in[1..n]\text{
such that }j\not\in[l_{a}..r_{a}]\\\ 1&\text{ if }b=j\text{ and
}a\in[1..n]\text{ such that }j\in[l_{a}..r_{a}]\\\
0&\text{otherwise}\end{cases}$

On the column $j$ of the matrix $P^{*}$ we will still have
$\max_{a\in[1..n]}(p_{a}\cdot p^{*}_{aj})=p_{i}$ because the padding-scheme
$f^{*}$ preserves the maximum on column $j$. Moreover, on the rest of the
columns, the maximum either decreases or stays the same since we created more
entries $p^{*}_{ab}=0$, which means that the product $p_{a}\cdot
p^{*}_{ab}=0$. However, we chose $f$ to be the Rényi-min optimal padding-
scheme and with the observations above, $f$ and $f^{*}$ give the same leakage.
∎

Figure IV.1 depicts an example of a sub-matrix of $P$ as described in
Observation 4. In the figure, we have exactly one entry equal to $1$ in each
line because the channel-matrix is stochastic and we are in the POP case.
Additionally, the quantity in (IV.1) represents the sum of the maximum over
columns where each $1$ counts for the frequency of the file. Then, the update
does not increase the (IV.1) because the $1$ with maximal frequency dominates
its column, and moving all possible $1$’s above or below it does not increase
Rényi-min leakage.

Using Observation (4) we can divide the padding problem into sub-problems that
minimize (IV.1) and leverage dynamic programming: $\forall a\leq b\in[1..n]$,
we define

$D[a][b]=\min_{\text{P channel
matrix}}{\sum_{j\in[1..m]}\max_{i\in[a+1..b]}(p_{i}\cdot p_{ij}}),$

i.e. $D[a][b]$ gives the minimal leakage for the sub-problem that pads files
from $e_{a+1}$ to $e_{b}$, under the general constraints.

By convention, we consider $D[i][i]=0$, which will be the base case. To write
the recurrence formula, we need to take the file $e_{i_{max}}$ with maximum
frequency $p_{i_{max}},i_{max}\in[a+1,b]$. We go through every size index
$k\in[1..m]$ such that $e_{i_{max}}$ can be padded to the size of $s_{k}$ and
we update the channel-matrix according to Observation 4, i.e. add $1$’s on
$k$-th column if we can (taking into consideration the padding constraints)
and complete the lines that have a fixed $1$ with $0$’s on the remaining
entries. Then, we apply the recurrence on the rows which are not updated, i.e.
from $a$ to
$a^{*}\stackrel{{\scriptstyle{\scriptscriptstyle\mathrm{def}}}}{{\coloneqq}}\max(a,\max_{i\in[1..n]}\\{i|r_{i}<k\\})$,
and, respectively, from
$b^{*}\stackrel{{\scriptstyle{\scriptscriptstyle\mathrm{def}}}}{{\coloneqq}}\min(k,b)$
to $b$. Hence,

$D[a][b]=p_{i_{max}}+\min_{k\in[l_{i_{max}}..r_{i_{max}}]}{(D[a][a^{*}]+D[b^{*}][b])}$

After applying the dynamic algorithm program with the aforementioned
recurrence, we get the minimization of (IV.1) in $D[0][n]$, from which we can
compute the minimal Rényi-min leakage. If we want to recover the channel-
matrix itself, in $D[a][b]$ we pass on the index $k$ for which the maximum
happens, as an argument. In case of a tie, we choose the smallest index
$k\in{\\{1,\dots,n\\}}$ in order to reduce average padding. Bandwidth
minimization is further analyzed in Section V. Hence, we know in each sub-
interval $[a,b]$ what we pad everything to, so the information is enough to
recover the channel matrix. The implementation can be found in [PPS22].

In Figure IV.2 we depict the channel-matrix of the files with sizes
$S=\\{1000,1050,1100,1120,1140\\}$ and associated frequencies
$\\{22\%,5\%,23\%,12\%,18\%,20\%\\}$. As shown in the visual representation of
the padding-scheme in the right, we observe that, for both of the existing
padded sizes, there are multiple files that are padded to the same element,
making them indistinguishable for an attacker. Moreover, the _blue_ and _red_
bars on the graph indicate the frequencies of the files, respectively, the
maximum frequency among the frequencies of the files padded to each specific
size. These are used in order to highlight the terms of the sum (IV.1).

$22\%$$\phantom{0}5\%$$23\%$$12\%$$18\%$$20\%$$s_{1}$$s_{2}$$s_{3}$$s_{4}$$s_{5}$$s_{6}$$1$$1$$1$$1$$1$$1$$0$$0$$0$$0$$0$$0$$0$$0$$0$$0$$0$$0$$0$$0$$0$$0$

Figure IV.2: Visualization of PopRe for a dataset having the padding
constraint $c=1.1$ and sizes $\\{1000,1050$, $1100,1110$, $1120,1140\\}$

###  IV-B PrpRe

In this section, we treat the case of Per-Request-Padding and provide an
algorithm for finding the probabilistic channel-matrix $P$ which minimizes the
Rényi-min leakage. We will look at the joint distribution matrix $I$ with
entries $I_{ij}=p_{i}\cdot p_{ij},\forall i\leq n,j\leq m$, for which the row-
wise sum $\sum_{j=1}^{m}I_{ij}$ is equal to $p_{i},\forall i\in[1..n]$.

We proceed by finding iteratively, for each of the $m$ columns, starting from
the last one, the Rényi-min optimal manner of setting the entries of $I$ given
the padding constraints. We define the _optimal distribution of $p_{i}$ across
the $i$-th row, $1\leq i\leq n$_ to be the way we fill in the entries
$p_{i1},\dots,p_{im}$ such as to obtain the minimum sum of the type (IV.1) and
preserve the relation $p_{i1}+...+p_{im}=p_{i}$.

The proof of our algorithm requires us to consider sub-problems in which the
sequence $(p_{i})_{1\leq i\leq n}$ is updated at each step of the algorithm,
thus being different from the initial set of frequencies associated to each
file. Hence, we rewrite the problem as a more general one in terms of a
_budget_ sequence ${(b_{i})}_{1\leq i\leq n}$ of length $n$ (initialized as
${(p_{i})}_{1\leq i\leq n}$), which dictates the remaining value to be
distributed across each row $i,\text{ for }i\in[1..n]$. The general problem is
stated below: Given a non-negative budget sequence ${(b_{i})}_{i\mathchar
61\relax 1}^{k}$ of length $k\in[1..n]$, find a solution matrix $I_{k\times
m}$ that minimizes Equation (IV.1), under the padding constraints for rows
$i\in[1..k]$, namely the set $\\{[l_{1},r_{1}],\dots,[l_{k},r_{k}]\\}$ and
$\sum_{j=1}^{m}I_{ij}=b_{i}$.

We will design the algorithm to solve the general problem recursively by
returning the matrix $I$ for the budget sequence $\\{p_{1},\dots,p_{n}\\}$
with $n$ terms. The recurrence relationship can be described using the
following observation that will be used when we create the probabilistic
channel-matrix for the padding-scheme $f$:

######  Observation 5.

The solution $I_{k\times m}$ for a given ${(b_{i})}_{i\mathchar 61\relax
1}^{k}$ that minimizes Rényi leakage satisfies the recurrence relationship

$I_{ij}=\begin{cases}b_{i}&\text{ if }j=m\text{ and
}i\in[1..k],{|e_{i}|}\mathchar 61\relax s_{m}\\\
b_{i}-b_{i}^{^{\prime}}&\text{ if }j=m\text{ and }i\in[1..k-1],{|e_{i}|}\neq
s_{m},\\\ &m\in[l_{i}..r_{i}]\\\ I^{^{\prime}}_{ij}&\text{ otherwise}\\\
\end{cases}$

where $I^{^{\prime}}_{(k-t)\times(m-1)}$ is the solution to the same
minimization problem for the sequence ${(b^{^{\prime}}_{i})}_{i\mathchar
61\relax 1}^{k-t}$ of length $k-t$, $t=$ number of files from $E$ which can be
padded to $s_{m}$, such that for any $i\in[1..k-t]$, it is defined as:

$b_{i}^{^{\prime}}=\begin{cases}\max(b_{i}-b_{t_{max}},0)&\text{ if
}m\in[l_{i}..r_{i}]\text{ and }\\\
&b_{t_{max}}=\max\\{b_{i}|{|e_{i}|}\mathchar 61\relax s_{m}\\}\\\ b_{i}&\text{
otherwise}\end{cases}$

###### Proof.

If there are no files among ${\\{e_{1},\dots,e_{k}\\}}$ which can be padded to
$s_{m}$, we set $t=0$ and solve the minimization problem for the same budget
sequence and for the set of $m-1$ sizes ${\\{s_{1},\dots,s_{m-1}\\}}$.

If there are files that can be padded to $s_{m}$, then due to the padding
constraints, the element $e_{i}$ can only be padded to $s_{m}$, so the entry
$I_{im}$ must necessarily be equal to $b_{i},\text{ for all }i$ such that
${|e_{i}|}\mathchar 61\relax s_{m}$. Let us denote by
$T={\\{k-t+1,\dots,k\\}}$ the set of indices satisfying ${|e_{i}|}\mathchar
61\relax s_{m},\forall i\in T$ and $b_{t_{max}}=\max\\{b_{i}|i\in T\\}$.
Clearly, for every $i\in T$, $I_{ij}=0,\forall j\in{\\{1,\dots,k-1\\}}$. On
the $m$-th column of the matrix $I$, we have $\max_{i\in[1..k]}I_{im}\geq
b_{t_{max}}$.

In order to minimize the sum (IV.1) and taking into consideration that the
maximum entry on column $m$ is at least $b_{t_{max}}$, we aim to distribute,
for every $i$ such that $e_{i}$ can be padded to $s_{m}$ but ${|e_{i}|}\neq
s_{m}$, a quantity equal to $b_{t_{max}}$ (or, if $b_{i}<b_{t_{max}}$, then we
distribute the whole $b_{i}$) on the entry $I_{im}$, such that we preserve the
maximum on this last column to be $b_{t_{max}}$. This way, we can assure that,
among the other columns, we’ll have to distribute a smaller fraction of
$b_{i}$, which means that the maximum on each column between $1$ and $m-1$
will decrease, and so will (IV.1).

The problem reduces to find the optimal sub-matrix
$I^{^{\prime}}_{(k-t)\times(m-1)}$ to complete the first $k-t$ rows of $I$,
and with the aforementioned observation, we can actually consider
$I^{^{\prime}}$ to be the solution given the updated sequence
$(b^{^{\prime}}_{i})_{1\leq i\leq k-t}$ which is defined, for every $i$ such
that file $e_{i}$ that can be padded to $s_{m}$, as either $0,\text{ if
}b_{i}\leq b_{t_{max}}$, or as $b_{i}-b_{t_{max}},\text{ if }b_{i}\geq
b_{t_{max}}$. When we reconstruct the matrix $I$, on the $m$-th column we will
have the value $I^{^{\prime}}_{im}+b_{t_{max}}$ or $I^{^{\prime}}_{im}+b_{i}$
(depending whether $b_{i}$ is smaller, respectively larger, than
$b_{t_{max}}$).

Now, let us show that, for the sub-matrix $I^{^{\prime}}$, we have $0$’s on
every entry of the $m$-th column. By definition, $I^{^{\prime}}$ must be a
Rényi-min optimal solution for the updated sequence of $b^{^{\prime}}_{i}$’s.
Using Proposition 1, there exists a Rényi-min optimal padding-scheme
$f^{^{\prime}}$ which maps
$e_{i},i\in[1..k-t]\rightarrow\\{s_{1},\dots,s_{k-t}\\}$, for any set of files
$\\{e_{1},\dots,e_{k-t}\\}$ with the associated frequencies
$\\{b^{^{\prime}}_{1},\dots,b^{^{\prime}}_{k-t}\\}$. Consequently, for every
$i\in[1..k-t],\mathbb{P}(f^{^{\prime}}(e_{i})=s_{m})=0\Rightarrow
I^{^{\prime}}_{im}=0$. ∎

Therefore, we have proved that the matrix $I$ can be recursively expressed
using the sub-matrices obtained when we update the budget sequence
accordingly, at each step decreasing by $1$ the number of columns and by at
least $1$ the number of rows of the matrix returned from the algorithm, until
we reduce a problem to finding the Rényi-min optimal scheme for a budget
sequence with a single element. Since we want to minimize (IV.1) in the case
of $n$ files with frequencies $\\{p_{1},\dots,p_{n}\\}$ and the associated set
of sizes ${\\{s_{1},\dots,s_{m}\\}}$, we proceed the induction on the number
of rows and columns as described in Observation 5 and eventually fill in all
the entries of the solution $I_{n\times m}$. If we want to recover the
channel-matrix $P$ of conditional probabilities, we return the matrix with
entries:

$P_{ij}=I_{ij}/p_{i},\forall i\in[1..n],j\in[1..m].$

This approach also handles a problem tackled in [RR21], in which the
distribution of the files’ frequencies is unknown. By supposing an uniform
distribution of the files, our algorithm PrpRe minimizes the Sibson mutual
information of order infinity as introduced in [IWK19], hence solving the
problem discussed in [RR21].

##  V Algorithms for further minimizations

We observe that there might be numerous padding-schemes that achieve minimal
Rényi-min leakage. In this section we provide improvements to our algorithms
in order to optimize average total padding and Shannon leakage after
minimizing Rényi-min leakage. That is, we start with a Rényi-min optimal
padding scheme found with the algorithms of the previous section and apply
several heuristics to reduce the average padding or the Shannon leakage, while
preserving minimal Rényi-min leakage.

###  V-A Average padding minimization

In this section, we show improvements for the Per-Object-Padding and Per-
Request-Padding cases in order to reduce the average padding while keeping the
Rényi-min leakage at its minimum.

  1. 1.

POP(Per-Object-Padding)

The heuristic for reducing bandwidth is already part of the design of
algorithm PopRe. The heuristic consists of resolving ties by always choosing
to pad the file with maximal frequency to the file with the least possible
size.

Technically, this heuristic guarantees we find the padding-scheme with minimal
bandwidth among those that are reachable using zero or more _moves_ (see
Section V-B for all details). We verified this experimentally, with more than
$10{,}000$ random generated tests using the code in [PPS22], as well as the
fact that this heuristic is limited and does not find the minimal bandwidth
among all padding functions with optimal Rényi-min leakage.

  2. 2.

PRP(Per-Request-Padding) Suppose $f$ is the padding scheme resulting from
PrpRe and $I$ is its joint distribution matrix. Let the list $C$ of maximums
on each column, i.e. $C={\\{\max_{i\in[1..n]}I_{ij}|j\in[1..m]\\}}$, where
$C_{j}=\max_{i\in[1..n]}I_{ij}$ for every $j\in[1..m]$.

Define a _move_ to be a change in the matrix $I$ performed on two of the
entries of the matrix on line $i,\text{ for some }i\in[1..n]$ such that
$(I_{ia},I_{ib})$ becomes $(I_{ia}-\alpha,I_{ib}+\alpha)$ while keeping the
entries of $I$ positive, i.e. $\alpha\leq I_{ia}$.

Now, we will describe an _update_ on line $i$, which will consist of a series
of _moves_ and will return a new matrix $I^{*}$. We start with $I^{*}$ to be
the matrix $I$, but with $0$’s on the $i$-th line. Since the sum on row $i$ is
equal to $p_{i}$, we start with this quantity and go through the columns in
order from $j=1$ to $j=m$. For each column, we set:

$I_{ij}=\begin{cases}C_{j}&\text{if }C_{j}+\sum_{k=1}^{j-1}I_{ik}\leq p_{i}\\\
p_{i}-\sum_{k=1}^{j-1}I_{ik}&\text{ otherwise }\end{cases}$

The algorithm ends by applying the update on all lines, regardless of their
order. As for the case before, we will later discuss the performance of this
algorithm.

In the next section we refer to this improvement of the algorithm which
performs average padding minimization as PrpReBa.

###  V-B Shannon leakage minimization

We aim to improve Shannon leakage while keeping the Rényi-min leakage minimal.
For instance, in Figure IV.2, if we pad the file with frequency $10\%$ to size
$96$ instead of $84$, then Rényi-min leakage is preserved while Shannon
leakage changes.

In this section, instead of working with the channel-matrix
$P=(p_{ab})_{a\in[1..n],b\in[1..m]}$ of dimension $n\times m$, we will talk
about the matrix $I=(p_{ab}\cdot p_{a})_{a\in[1..n],b\in[1..m]}$. This is
intuitive since minimizing the Rényi-min leakage is equivalent to minimizing
(IV.1). However, the sum in (IV.1) is equal to
$\sum_{j\in[1..m]}\max_{i\in[1..n]}(I_{ij})$, i.e. the sum of the maximal
entries of the columns of matrix $I$.

We consider a _move_ to be a change of a padding-scheme $f$ to a different
padding-scheme $f^{*}$ such that the two functions differ in one element only,
and $f^{*}$ respects the padding constraints inherent to $f$. Our goal is to
start from matrix $I$ and apply a series of _moves_ in order to eventually
reach a matrix that preserves Rényi-min leakage but has lower Shannon leakage.

We focus on keeping the Rényi-min leakage constant after each single _move_.
This does not find the universal Rényi-min optimal padding with the least
Shannon leakage, a fact that was tested experimentally [PPS22], but in
practice it performs very well (refer to Section VI for details).

Starting from the initial matrix $I$, we want to get the matrix $I^{*}$ such
that, at any step during the sequence of _moves_ applied, the following
property holds for all columns $j\in[1..m]$:

$\max_{i\in[1..n]}I_{ij}=\max_{i\in[1..n]}I^{*}_{ij}$

This property ensures that the Rényi-min leakage stays the same due to the
fact that the quantity in IV.1 remains constant. By restricting our algorithm
to only perform _moves_ that respect the above condition, we define a list of
positions where the file $e_{i}$ can be padded to, named poss[i], for each $i$
in $[1..n]$:

$\texttt{poss[i]}\stackrel{{\scriptstyle{\scriptscriptstyle\mathrm{def}}}}{{\coloneqq}}\\{j\in[1..m]|j\in[l_{i}..r_{i}]\text{
and }\max_{a\in[1..n]}I_{aj}\geq p_{i}\\}.$

Allowing to pad file $e_{i}$ only to files with index in poss[i] will preserve
the minimal Rényi-min leakage. Now, the method to minimize the Shannon mutual
information is rooted in the following underlying observation:

######  Observation 6.

Consider $f$ to be a Rényi-min optimal padding-scheme with $P=(p_{ab})_{a\leq
n,b\leq m}$ its channel-matrix and let $j\in[1..m]$ be the index of the column
of the channel-matrix $(p_{ab})_{a\leq n,b\leq m}$ with the highest associated
probability $\mathbb{P}(f(X)=s_{j})={\sum_{a=1}^{n}p_{a}\cdot p_{aj}}$. Then,
any _move_ of $1$’s to the $j$-th column gives a padding-scheme with less
Shannon leakage.

###### Proof.

The Shannon mutual information is
$\mathbb{I}({|X|},f(X))=\mathbb{H}({|X|})-\mathbb{H}({|X|}\mid
f(X))=\mathbb{H}(f(X))-\mathbb{H}(f(X)\mid{|X|})$. Since we are still in the
case POP, $f(X)$ is a deterministic function of ${|X|}$, so
$\mathbb{H}(f(X)\mid{|X|})=0$. Hence, in order to minimize Shannon mutual
information, it is sufficient to minimize:

$\mathbb{H}(f(X))=-\sum_{j=1}^{m}\mathbb{P}(f(X)=s_{j})\cdot\log_{2}\mathbb{P}(f(X)=s_{j})$
(V.1)

Suppose there exists $i$ an index such that $p_{ij}=0$, and
$i\in[l_{j}..r_{j}]$. Then, $\exists k\neq j$ with $p_{ik}=0$. We want to show
that _moving_ the $1$ from position $P_{ik}$ to $P_{ij}$ decreases the initial
Shannon leakage. Consider the updated scheme $f^{*}$ resulting after the
_move_ to column $j$, with the associated channel-matrix
$P^{*}=(p_{ab}^{*})_{a\leq n,b\leq m}$:

$p^{*}_{ab}=\begin{cases}p_{ab}&\text{ if }a\neq i\\\ 1&\text{ if }a=i\text{
and }b=j\\\ 0&\text{ otherwise }\end{cases}$

It is sufficient to prove that the sum (V.1) is smaller for $f^{*}$ than for
$f$. For simplicity, let us denote $\tilde{p}(x)=-x\cdot\log_{2}x$, so (V.1)
can be written as $\sum_{b=1}^{m}\tilde{p}(g(b))\text{ where for every
}b\in[1..m],\text{ we define }g(b):=\mathbb{P}(f(X)=s_{b})\text{ and
}g^{*}(b):=\mathbb{P}(f^{*}(X)=s_{b})$.

We see that:

$\displaystyle
D=\sum_{b=1}^{m}\tilde{p}(g(b))-\sum_{b=1}^{m}\tilde{p}(g^{*}(b))=\tilde{p}(g(j))+\tilde{p}(g(k))-$
$\displaystyle\tilde{p}(g^{*}(j))-\tilde{p}(g^{*}(k)).$

But note that $g(j)>g(k)$, $g^{*}(j)>g(j)$, $g(k)>g^{*}(k)$ and, moreover,
$g^{*}(j)-g(j)=p_{t}=g(k)-g^{*}(k)$. Using the properties of the concave
function $\tilde{p}(x)$ on $[0,1]$, we get that
$\tilde{p}(g(j))+\tilde{p}(g(k))\geq\tilde{p}(g^{*}(j))+\tilde{p}(g^{*}(k))$.
Hence $D\geq 0$, so the sum in (V.1) is smaller for the padding-scheme
$f^{*}$.

This shows that the _move_ from position $P_{ik}$ to $P_{ij}$ decreases
Shannon leakage. ∎

This observation implies that a padding-scheme with optimal Rényi-min leakage,
satisfying that no further _move_ can reduce the Shannon leakage, has a
column, call it _maximal_ such that any $1\text{ on line }i$ that could have
been moved to that column, given poss[i], was already _moved_ there. This
corollary prompts us to leverage dynamic programming and divide the problem
into sub-problems.

We define $D[a][b]$ to be the partial Shannon leakage, looking at the columns
from $a$ to $b$ on which we only place non-zero elements in lines $i\text{
such that }\texttt{poss[i]}\subset[a..b]$. So, any file which can be padded to
a size $s_{t}\text{ with }t\notin[a..b]$, will not be taken into account in
the sub-problem $D[a][b]$. We will use the convention $D[j+1][j]=0$ since it
acts on no columns, and we consider this to be a base case. With the
observation above we deduce the following recurrence formula:

$\displaystyle D[a][b]=\min_{j\in[a..b]}(D[a][i-1]+D[i+1][b]+$
$\displaystyle\sum_{x\in\\{i|j\in\texttt{poss}[i]\\}}-x\cdot\log x)$

Note that this recurrence only keeps in memory the value of the Shannon
leakage. If we want to recover the channel-matrix itself, we need to pass on
as an argument the column which was _maximal_ in $[a..b]$ at each step. This
information is enough to reconstruct the channel-matrix given the _maximal_
property of the columns.

Below we give representations of the different outputs returned by the
algorithms PopReSh and PopSh. By comparing Figure IV.2 with Figure V.1, we
highlight the reduction in Shannon leakage produced by PopReSh. Moreover, in
the case analyzed below, we observe that PopSh gives a higher Rényi-min
leakage compared to PopReSh. In the case of PopSh, it is obvious for an
attacker that the first padded size comes from the first file. An example of
the proficiency of PopReSh and PopRe compared to PopSh is that they don’t have
any file padded in an unique way, making it non-trivial for the attacker to
guess the initial file in the example below.

Figure V.1: Padding-schemes returned by PopReSh(left) and PopSh (right) in a
fixed example; the value of the padding constraint is $c=1.1$

##  VI Experiments and Comparison

Several experiments were carried out for three distinct purposes, namely, (1)
to test the correctness of the implementations against brute-force algorithms
for small sized problems, (2) to corroborate the direct link between Rényi-min
leakage and the success rate of an attacker and (3) to compare the runtime,
bandwidth and leakages of all the algorithms on a large real-world dataset.
The code of all the experiments is available in [PPS22].

###  VI-A Brute-force tests

All the algorithms developed, including our re-implementation of PopSh to
handle the server identity problem, were tested against brute-force
implementations for small datasets (with at most $10$ elements). That is, for
each randomly generated test case of file sizes and frequencies, we explored
(exhaustively) all the POP padding schemes satisfying the constraints, and
chose among them, the ones that minimized Rényi-min leakage, Shannon leakage
or bandwidth, with the purpose of comparing them with the solutions returned
by our algorithms.

We ran tens of thousands of experiments (code available in [PPS22]), all
corroborating that: (a) among all POP schemes, PopRe achieves minimal Rényi-
min leakage and PopSh achieves minimal Shannon leakage; (b) PopReSh is always
better than PopRe; (c) PrpRe leaks at most the Rényi-min leakage of PopRe.

###  VI-B Attacker tests

We simulated a real attacker who observes the padded size of a file
transferred in the network and tries to guess the original file. We assume
that the attacker knows the joint distribution matrix $I$ and guesses, for a
padded size $s_{j},j\in[1..m]$, the file $e_{j^{*}},j^{*}\in[1..n]$ which
satisfies $p_{j^{*}}\cdot p_{j^{*}j}=\max_{a\in[1..n]}I_{aj}$. If $A$ is the
random variable, taking the value $0$ each time the attacker is wrong, and $1$
if the attacker is right, we see that the expected value of $A$ can be
expressed in the following way:

$\mathbb{E}[A]=\sum_{j=1}^{m}p_{j^{*}}\cdot p_{j^{*}j}.$

$-1{,}000$$0$$1{,}000$$2{,}000$$3{,}000$$4{,}000$$5{,}000$$6{,}000$$7{,}000$$8{,}000$$9{,}000$$10{,}000$$11{,}000$$0.3$%$0.35$%$0.4$%$0.45$%$0.5$%$0.55$%$0.6$%$0.65$%$0.7$%Number
of usersRate of succesful attacksPrpReTheoretical optimum Figure VI.1:
Convergence of the attacker’s success

This proves that the expected value of the success of the attacker, by the law
of large numbers, should converge to $\mathbb{E}[A]$, which is equal to the
value of (IV.1). This means that building a padding-scheme that minimizes the
success of the attacker is indeed equivalent to finding the optimal Rényi-min
leakage, and this can be observed graphically in Figure VI.1.

###  VI-C NodeJS dataset tests

The dataset of NodeJS packages was proposed in [RR21]. This dataset consists
of a list of $423{,}450$ javascript packages provided by NPM for browser and
nodeJS applications, each with its associated file size and access frequency,
as of August 2021. These packages are used by most websites, which pull them
from Content Delivery Networks such as jsDelivr, unpkg or cdnjs, and
therefore, having information about pulled packages leaks some information
about the website identity, since the specific packages used by each webpage
can be though of a fingerprint. For this security reason, and taking into
account the large number of files, we used the NodeJS dataset to benchmark the
algorithms.

We used two versions of the NodeJS dataset: the _large_ NodeJS dataset is the
original dataset with 423,450 files, and the _small_ consists of only the 1000
most frequently accessed files. The small NodeJS dataset allowed us to
benchmark and compare the algorithms with large complexity, which timeout on
the large dataset.

Firstly, we compared our own developed algorithms PopRe, PopReSh, PrpRe,
PrpReBa, and the algorithm PopSh from [RR21], which minimizes Shannon mutual
information, against the Small NodeJS dataset. We present the following two
plots which make the comparison between these algorithm in terms of both min-
leakage and Shannon leakage:

$0.99$$1$$1.01$$1.02$$1.03$$1.04$$1.05$$1.06$$1.07$$1.08$$1.09$$1.1$$1.11$$4$$4.5$$5$$5.5$$6$$6.5$$7$$7.5$$8$$c$Rényi-
min leakagePrpReBaPrpRePopRePopReShPopSh Figure VI.2: Rényi-min leakage using
the small NodeJS dataset.

In Figure VI.2, we observe that, for the various values of the constant $c$
ranging from $1$ to $1.1$, the Rényi-min leakage becomes significantly smaller
for the PrpReBa and PrpRe in comparison with the rest of the algorithms
presented. This difference can be noticed from a slight change in $c$ from
$1$, which describes that the file sizes are not padded at all, to the value
$1.02$. As the value of $c$ increases, allowing the files to be padded more,
the Rényi-min leakage is decreased by about $40\%$ from $c=1$ to $c=1.1$. We
remark that, for each of the $6$ values of the padding constraint $c$, PrpReBa
and PrpRe provide a smaller leakage than PopRe and PopReSh. However, the
reduction of PopRe is tiny compared to PopSh, suggesting that the algorithm
provided by Reed and Reiter [RR21] is comparable in terms of Rényi-min leakage
with our per-object-padding algorithm, however, our per-request-padding
algorithm PrpRe is more efficient to reduce information gain of an attacker.

$0.99$$1$$1.01$$1.02$$1.03$$1.04$$1.05$$1.06$$1.07$$1.08$$1.09$$1.1$$1.11$$5$$6$$7$$8$$9$$10$$c$Shannon
leakagePrpReBaPrpRePopRePopReShPopSh Figure VI.3: Shannon leakage using the
small NodeJS dataset.

In Figure VI.3, we remark a reversed behavior than the one present in the
previous graph. More specifically, the Shannon leakage in the two per-request-
padding case is greater than the one given by the three algorithms using per-
object-padding. Again, as $c$ increases by $10\%$, the Shannon leakage
decreases by roughly $40\%$. Nonetheless, the Shannon leakage returned by our
improvement PopReSh is similar overall with the Shannon leakage of PopSh.
Consequently, our algorithm PopReSh gives a better Rényi-min leakage and a
similar Shannon leakage compared to PopSh developed by [RR21].

$0.99$$1$$1.01$$1.02$$1.03$$1.04$$1.05$$1.06$$1.07$$1.08$$1.09$$1.1$$1.11$$1$$2$$3$$4$$5$$c$Runtime
(seconds)PrpReBaPrpRePopRePopReShPopSh Figure VI.4: Small NodeJS runtime plot.
The JIT compilation takes $7$ additional seconds.

Figure VI.4 depicts the runtime of the algorithms under analysis. As predicted
by the complexity analysis explained in section dedicated to algorithms and
proofs, PrpRe has the smallest runtime among the algorithms that we developed,
and it is similar to PopSh for the Small NodeJS dataset. However, our
algorithm remains more efficient in terms of the running time, as it can be
observed for the cases $c=1.08$ and $c=1.1$. As the value of $c$ increases,
the execution time of PopRe increases most significantly as it has complexity
$O(n\,m^{2})$, $m$ denoting the number of available sizes where to pad the
files. Nonetheless, the same behavior occurs in the case of PrpReBa. The
latter has a greater runtime than PrpRe, difference which can be seen starting
from $c=1.02$. Their complexity is polynomially the same, $O(n\,{\bar{m}})$
(refer to Table I), but in practice PrpRe runs faster as it often fills up a
row in $O(1)$ rather than $O(m)$ or $O({\bar{m}})$. For the algorithm PopReSh,
the running time appears to be decreasing in the value of the padding
constraint $c$. This indicates that a higher $c$ allows PopRe to give a result
which has a Shannon leakage closer to the optimal, as seen in Figure VI.3,
which diminishes the number of improvements that PopReSh can act on and
consequently its runtime.

$0.99$$1$$1.01$$1.02$$1.03$$1.04$$1.05$$1.06$$1.07$$1.08$$1.09$$1.1$$1.11$$0$%$0.5$%$1$%$1.5$%$2$%$2.5$%$3$%$3.5$%$c$Bandwidth
increasePrpReBaPrpRePopRePopReShPopSh Figure VI.5: Bandwidth increase using
the small NodeJS dataset; for reference, the average bandwidth use without
padding is $52{,}487$

Next, we analyze the performance of our algorithms in terms of the bandwidth
increase generated by the padding of the file sizes. Figure VI.5 depicts the
percentage increase in the bandwidth for the same values of $c$ previously
analyzed. The bandwidth increase is a non-decreasing function of the padding
constraint, i.e. allowing the servers to pad more the files in order to find
optimal Rényi-min leakage also generates an increase in the bandwidth. Hence,
we conclude that, as the padding limitations are relaxed, the intuition behind
the fact that it is better for reducing leakage to pad more the objects is
reinforced. As suggested by the graph, the algorithm PrpReBa proves to be
efficient in reducing the average padding over a network, as it always gives
the smallest bandwidth increase out of the $5$ algorithms under analysis.
Conversely, PopSh gives the highest average padding in all the cases except
for $c=1.1$.

From now on, we analyze the large NodeJS dataset. The only algorithms
efficient enough to run on this data are PrpReBa, PrpRe and to a lesser extent
PopSh. Once more, we will plot Rényi-min leakage, Shannon leakage, bandwidth
increase and runtime.

In Figure VI.6, as compared to Figure VI.2, we can see that a larger dataset
allows for greater differences in Rényi-min leakage between the optimal
algorithm PrpRe and PopSh. Moreover, the results of this figure corroborate
the fact that PrpRe and PrpReBa give the same Rényi-min leakage.

$0.99$$1$$1.01$$1.02$$1.03$$1.04$$1.05$$1.06$$1.07$$1.08$$1.09$$1.1$$1.11$$4$$5$$6$$7$$8$$c$Rényi-
min leakagePrpReBaPrpRePopSh Figure VI.6: Rényi-min leakage using the entire
NodeJS dataset
$0.99$$1$$1.01$$1.02$$1.03$$1.04$$1.05$$1.06$$1.07$$1.08$$1.09$$1.1$$1.11$$5$$6$$7$$8$$9$$10$$11$$12$$c$Shannon
leakagePrpReBaPrpRePopSh Figure VI.7: Shannon leakage using the entire NodeJS
dataset

Figure VI.7, which analyses the Shannon leakage, depicts once again an
opposite behavior compared to the one in Figure VI.6. Naturally, PopSh has a
smaller Shannon leakage than our algorithms PrpRe and PrpReBa. Once again, we
notice that both the Shannon leakage and the Rényi-min leakage follow a
decreasing trend in the value of $c$, exactly as observed in the experiments
performed for the small NodeJS dataset.

It can be observed in Figure VI.8 the proficiency of the optimization PrpReBa
compared to its initial variant PrpRe and to PopSh. This makes PrpReBa ideal
for a web server who wants to limit the total expected average bandwidth on
top of the individual bounds set by $c$.

Lastly, Figure VI.9 highlights the scalability of the three algorithms,
especially PrpRe and PrpReBa. For all values of $c$ plotted in this graph, the
runtime for PrpRe is under $7$ seconds, which makes it the fastest algorithm
among all of its competitors, while optimizing its measure of privacy, Rényi-
min leakage. We can also see that PrpReBa has a great running time compared to
PopSh, peaking at $c=1.1$ with around $3$ minutes versus $15$ minutes, which
is a clear advantage.

$0.99$$1$$1.01$$1.02$$1.03$$1.04$$1.05$$1.06$$1.07$$1.08$$1.09$$1.1$$1.11$$0$%$2$%$4$%$6$%$8$%$c$Bandwidth
increasePrpReBaPrpRePopSh Figure VI.8: Bandwidth increase using the NodeJS
dataset
$0.99$$1$$1.01$$1.02$$1.03$$1.04$$1.05$$1.06$$1.07$$1.08$$1.09$$1.1$$1.11$$10^{1}$$10^{2}$$10^{3}$$10^{4}$$10^{5}$$c$Runtime
(seconds)PrpReBaPrpRePopSh Figure VI.9: NodeJS runtime plot

##  VII Future Work

One natural improvement in our work would be to make our extended algorithms,
namely PopReSh and PrpReBa, find the padding-scheme with optimal Shannon
mutual information, respectively minimal average padding among all the
channels with minimal Rényi-min leakage. In order to better delve into the
problem, let us consider a graph $G$ for each algorithm, such as the one in
Figure VII.1, where the nodes represent all the Rényi-min optimal padding-
schemes. We draw a _dotted edge_ between two vertices if we can apply exactly
one _move_ (each algorithm has a different type of _move_) to one of the
padding-schemes and reach the other one. On the other hand, we draw a
_straight edge_ between two padding-schemes if we can apply a single _move_ to
one function in order to reach the other one, and, furthermore, preserve the
set of maximal elements on the columns, as in the solution for PopReSh, or
PrpReBa. Clearly, every two vertices united by a straight edge are also united
by a dotted one. Denote by $G_{\emph{\text{dotted edges}}}$ and
$G_{\emph{\text{straight edges}}}$ the sub-graphs of $G$ containing solely
dotted, respectively straight edges. Our algorithms find the optimal vertex in
the connected component of $G_{\emph{\text{dotted edges}}}$ which includes the
node returned by PopRe. A future upgrade would be to find the optimal padding-
scheme in the connected component of $G_{\emph{\text{straight edges}}}$, or in
the whole graph $G$.

For instance, if PopRe returns one of the blue nodes in Figure VII.1, then
PopReSh will find the blue bold node, as it minimizes Shannon leakage in its
connected component, thus it will fail to find the bold green node, which
achieves the actual global minimum.

Shannon leakage Figure VII.1: Graph containing the Rényi-min leakage optimal
padding-schemes

Secondly, we prioritized the minimization of Rényi-min leakage over the
measure of average padding. Future work can be directed in finding an optimal
trade-off between the two, not necessarily giving absolute priority to the
bandwidth of each costumer using the constant $c$.

Lastly, our paper and [RR21] provided algorithms to minimize Rényi-min and
Shannon leakage. As mentioned in the subsection Problem formalization, we
could also try to minimize $\mathbb{I}_{\alpha}$, the Rényi-min leakage.
However, thanks to the applicability of the notion of Rényi-min leakage to
measure the success of a real adversary, we believe that Rényi-min leakage is
the most adequate measure of leakage for this problem.

##  VIII Conclusion

In this paper we used Rényi-min leakage as the main measure for privacy,
arguing that it is the most suitable for simulating a real-life attacker. We
built two types of algorithms that minimize Rényi-min leakage, treating not
only the per-object-padding case in which the files are padded in a
deterministic way, but also the per-request-padding, in which each single file
is padded to every available size with a given probability.

We provided several improvements that lowered the average padding and the
Shannon leakage. We want to highlight the algorithms PrpRe and PrpReBa, which
have proven a better running time compared to all of their competitors.
Nonetheless, the latter one also has an impressive bandwidth advantage. We
analyzed all of our algorithms numerically, using many artificial examples and
also the NodeJS dataset.

Furthermore, we described a method for designing padding-schemes for multiple
servers that protect the identities of both the files and the servers. The
servers should simply agree on a fixed standard set of possible output sizes
and run our algorithms.

## References

  * [ACPS12] Mário S. Alvim, Konstantinos Chatzikokolakis, Catuscia Palamidessi, and Geoffrey Smith.  Measuring information leakage using generalized gain functions.  In Proceedings of the 25th IEEE Computer Security Foundations Symposium (CSF), pages 265–279, 2012.
  * [BBK17] Monowar H Bhuyan, Dhruba K Bhattacharyya, and Jugal K Kalita.  Network traffic anomaly detection and prevention: concepts, techniques, and tools.  Springer, 2017.
  * [Che17] Giovanni Cherubin.  Bayes, not naïve: Security bounds on website fingerprinting defenses.  Proceedings on Privacy Enhancing Technologies, 2017(4):215–231, oct 2017.
  * [CHJ17] Giovanni Cherubin, Jamie Hayes, and Marc Juárez.  Website fingerprinting defenses at the application layer.  Proc. Priv. Enhancing Technol., 2017(2):186–203, 2017.
  * [CKS+09] Arthur Callado, Carlos Kamienski, Géza Szabó, Balázs Péter Gero, Judith Kelner, Stênio Fernandes, and Djamel Sadok.  A survey on internet traffic identification.  IEEE communications surveys & tutorials, 11(3):37–52, 2009.
  * [HKDV15] Amjad Hajjar, Jawad Khalife, and Jesús Díaz-Verdejo.  Network traffic application identification based on message size analysis.  Journal of Network and Computer Applications, 58:130–143, 2015\.
  * [IWK19] Ibrahim Issa, Aaron B Wagner, and Sudeep Kamath.  An operational approach to information leakage.  IEEE Transactions on Information Theory, 66(3):1625–1657, 2019\.
  * [LL06] Marc Liberatore and Brian Neil Levine.  Inferring the source of encrypted http connections.  In Proceedings of the 13th ACM conference on Computer and communications security, pages 255–263, 2006.
  * [LXZ+16] Huaxin Li, Zheyu Xu, Haojin Zhu, Di Ma, Shuai Li, and Kai Xing.  Demographics inference through wi-fi network traffic analysis.  In IEEE INFOCOM 2016-The 35th Annual IEEE International Conference on Computer Communications, pages 1–9. IEEE, 2016.
  * [MCPS12] S Alvim M’rio, Kostas Chatzikokolakis, Catuscia Palamidessi, and Geoffrey Smith.  Measuring information leakage using generalized gain functions.  In 2012 IEEE 25th Computer Security Foundations Symposium, pages 265–279. IEEE, 2012.
  * [MMS+14] Annabelle McIver, Carroll Morgan, Geoffrey Smith, Barbara Espinoza, and Larissa Meinicke.  Abstract channels and their robust information-leakage ordering.  In International Conference on Principles of Security and Trust, pages 83–102. Springer, 2014.
  * [PLB11] Federico Montesino Pouzols, Diego R Lopez, and Angel Barriga Barros.  Mining and Control of Network Traffic by Computational Intelligence, volume 342.  Springer, 2011.
  * [PPS22] Carlos Pinzón, Cezara Petrui, and Sebastian Simon.  min-leakage-padding.  https://github.com/caph1993/min-leakage-padding, 2022.  Accessed: August 2022.
  * [PR18] Catuscia Palamidessi and Marco Romanelli.  Feature selection with rényi min-entropy.  In IAPR Workshop on Artificial Neural Networks in Pattern Recognition, pages 226–239. Springer, 2018.
  * [PW00] Kihong Park and Walter Willinger.  Self-Similar Network Traffic: An Overview.  Wiley Online Library, 2000.
  * [Rom20] Marco Romanelli.  Machine learning methods for privacy protection: leakage measurement and mechanisms design.  PhD thesis, Institut Polytechnique de Paris; Università degli studi (Sienne, Italie), 2020.
  * [RR21] Andrew C. Reed and Michael K. Reiter.  Optimally hiding object sizes with constrained padding, 2021.
  * [SJVR+18] Sandra Siby, Marc Juarez, Narseo Vallina-Rodriguez, Carmela Troncoso, et al.  Dns privacy not so private: the traffic analysis perspective.  In The 11th Workshop on Hot Topics in Privacy Enhancing Technologies (HotPETs 2018), 2018.
  * [Smi09a] Geoffrey Smith.  On the foundations of quantitative information flow.  In Luca de Alfaro, editor, Proceedings of the 12th International Conference on Foundations of Software Science and Computation Structures (FOSSACS 2009), volume 5504 of LNCS, pages 288–302, York, UK, 2009. Springer.
  * [Smi09b] Geoffrey Smith.  On the foundations of quantitative information flow.  In International Conference on Foundations of Software Science and Computational Structures, pages 288–302. Springer, 2009.
  * [Smi15] Geoffrey Smith.  Recent developments in quantitative information flow (invited tutorial).  In 2015 30th Annual ACM/IEEE Symposium on Logic in Computer Science, pages 23–31. IEEE, 2015.
  * [Son01] Dawn Song.  Timing analysis of keystrokes and ssh timing attacks.  In Proc. of 10th USENIX Security Symposium, 2001, 2001.
  * [SSW+02] Qixiang Sun, Daniel R Simon, Yi-Min Wang, Wilf Russell, Venkata N Padmanabhan, and Lili Qiu.  Statistical identification of encrypted web browsing traffic.  In Proceedings 2002 IEEE Symposium on Security and Privacy, pages 19–30. IEEE, 2002.
  * [WBMM07] Charles V Wright, Lucas Ballard, Fabian Monrose, and Gerald M Masson.  Language identification of encrypted voip traffic: Alejandra y roberto or alice and bob?  In USENIX Security Symposium, volume 3, pages 43–54, 2007.
  * [WCM09] Charles V Wright, Scott E Coull, and Fabian Monrose.  Traffic morphing: An efficient defense against statistical traffic analysis.  In NDSS, volume 9. Citeseer, 2009.
  * [Wel05] Michael Welzl.  Network congestion control: managing internet traffic.  John Wiley & Sons, 2005.
  * [WUB15] Christopher Wampler, Selcuk Uluagac, and Raheem Beyah.  Information leakage in encrypted ip video traffic.  In 2015 IEEE Global Communications Conference (GLOBECOM), pages 1–7. IEEE, 2015.