# Supervised and Reinforcement Learning from Observations in Reconnaissance
Blind Chess

Timo Bertram  JKU Linz, Austria  Johannes Fürnkranz  JKU Linz, Austria  Martin
Müller  University of Alberta, Canada

###### Abstract

In this work, we adapt a training approach inspired by the original AlphaGo
system to play the imperfect information game of Reconnaissance Blind Chess.
Using only the observations instead of a full description of the game state,
we first train a supervised agent on publicly available game records. Next, we
increase the performance of the agent through self-play with the on-policy
reinforcement learning algorithm Proximal Policy Optimization. We do not use
any search to avoid problems caused by the partial observability of game
states and only use the policy network to generate moves when playing. With
this approach, we achieve an ELO of 1330 on the RBC leaderboard, which places
our agent at position 27 at the time of this writing. We see that self-play
significantly improves performance and that the agent plays acceptably well
without search and without making assumptions about the true game state.

##  I Introduction

Games have served as immensely popular test domains for artificial
intelligence, but the ever-increasing performance in classical board games
such as chess and Go has long surpassed human capabilities [1]. However,
imperfect information games, where the game state is not perfectly observable,
still provide many research challenges for developing competent AI agents. In
many of these games, human and AI performance is much closer together [2, 3,
4, 5, 6, 7], and humans still hold their own in some of these domains. We
focus on the game of _Reconnaissance Blind Chess (RBC)_ , an imperfect
information variant of classical chess, where players only receive limited
information about the placement of the opponent’s pieces. We aim to apply the
training approach used by AlphaGo [1], which works in perfect information
games, to imperfect information games by making some practical adjustments.
Specifically, we avoid problems caused by trying to use forward search without
having perfect information by only using the trained policy network, which is
fully capable of playing the game on its own.

###  I-A Reconnaissance Blind Chess

In RBC, the game starts with the regular setup of chess pieces. However, a
player can only learn about the opponent’s moves by a limited form of sensing,
which strongly reduces their knowledge of the current state. At the start of
each turn, a player senses a $3\times 3$ area of the $8\times 8$ board, and
the true state of these squares is revealed. A player is also informed if
their selected move was legal and if they capture a piece. If a move attempts
to move through an opponent’s piece, the move is truncated to capturing it.
Players are also notified whenever one of their own pieces is captured, so
they retain perfect information about their own pieces. A game is won by
capturing the opponent’s king. Finally, check-related chess rules do not
apply, so it is legal to castle through a check or even move a king into
check. As a consequence, draws are much less common, as stalemate does not
exist and even a bare king can still win.

###  I-B Contributions

Our main contribution is to adapt an AlphaGo-inspired approach [1] to an
imperfect information game setting. In AlphaGo, the state is fully observable,
so the legal actions of both players are known, which allows deep forward
search. In RBC, we generally do not know the true state of the board, which
implies that a player cannot know the opponent’s options precisely without
making significant assumptions beyond the known observations. This greatly
restricts the ability to simulate games or conduct a search through a tree of
variations. In our work, we adapt the early AlphaGo framework, which first
primes a neural network by supervised training and then improves it via self-
play [1]. Concretely, we make two main adaptations to account for imperfect
information:

  1. 1.

We use the history of observations as our input and avoid any attempt to guess
or directly reconstruct the unknown full game state.

  2. 2.

We ignore search and solely use the trained policy network to play.

Thus, our network learns to directly map observations to a distribution of
actions, which is used to play the game. The aim of this work is to
demonstrate that working directly with the given observations of a complex
game like RBC, without assumptions about the full hidden game state, is
possible and leads to acceptable performance. This opens another angle to work
on RBC, which previously strongly focused on trying to explicitly reconstruct
the true game state.

##  II Related Work

Most previous work on RBC is focused on trying to eliminate the uncertainty of
RBC, thereby reducing it to normal chess, which then allows the usage of
strong search-based chess engines. For example, the runner-up of the 2019 RBC
competition, PiecewiseGrid agent [8], maintains a probability distribution
over the possible squares for each piece and uses this to compute the
likelihood of game states. The program then uses full game states to choose
moves with Stockfish [9], a state-of-the-art chess engine. The 2020 winner
Penumbra [10] does not use a regular chess engine but tries to reduce
uncertainty by identifying the opponent, which limits the possible game
states, again allowing forward search. Their approach trains a separate
network for a list of hand-selected opponents through supervised learning, as
well as one catch-all network which is used if the recognition fails. They
then generate an approximation of the current state, which is used as the
input to the network. However, using opponent-specific training severely
limits the flexibility of the approach. The work most similar to ours [11]
uses an approach similar to AlphaZero. However, their method did not achieve
strong performance and barely outperformed a random player. Like many other
prior works, they also aimed to reduce uncertainty by trying to identify the
most likely game states, which were then used for forward search.

To the best of our knowledge, there is no previous work on RBC which directly
works on the given observations, and we consider this to be the main
contribution of our approach. In poker, some previous work exists on directly
learning from observations. [12] learned to play simple poker versions from
observations of hands, which resulted in a good, but not very strong
performance. [13] proposed a self-play algorithm that guarantees to converge
to a Nash equilibrium. While resulting in similar outcomes, they train a
neural network to approximate the average of the past best-responses and we
use multiple past agents, leading to a slight difference between their work
and the reinforcement learning part of our work. Other strong results in
imperfect-information domains are often based on counterfactual regret
minimization [14, 15, 16], which may also work well in RBC, but has so far not
been explored.

##  III Method

TABLE I: Input representation for the agent (one observation)

Size of layer | Information represented
---|---
1 | Square where opponent captured one of our pieces
73 | Last move taken (see [17] for how a move is encoded)
1 | Square where agent captured opponent’s piece
1 | 1 if last move was illegal
6 | Position of own pieces (One layer per piece type)
1 | Last sense taken
6 | Result of last sense (One layer per piece type)
1 | Color

In this work, we explicitly aim to not make assumptions about the true game
state, but rather learn a policy that directly maps imperfect observations to
moves. For this, we represent all information received at each turn to build
up a history of observations, which forms the input to our network. The most
recent information for a player is represented by a 90 $8\times 8$ bitboard
(see Table I). Of this, a single 1 in a $73\times 8\times 8$ stack encodes the
last move, which is an idea put forward by [17]. Whether the last move was
illegal, and the color of the player, could be represented by a single 0 or 1,
but a whole plane is used to facilitate the convolution-based structure of the
network. To represent the past, a fixed-size history of the last 20
observations forms the input of size $1800\times 8\times 8$ to our network.
The network consists of a shared convolutional block, followed by two separate
heads for the sense and the move policy (see Figure 1. As a third output, we
also tasked the network to predict a scalar outcome of the game, $1$ for win
and $-1$ for loss, which was used as the starting network of the critic in
reinforcement learning. Although a sequence-based architecture, e.g. a Long
Short-Term Memory (LSTM) network or Gated Recurrent Unit (GRU), may
intuitively make more sense, we found that in our setup, those networks
required more training time without increasing the accuracy of the
predictions. Therefore, we speculate that a history of 20 turns is
sufficiently long to capture all important information, but even shorter
histories could yield benefits by reducing the amount of unnecessary
information. We again use $73\times 8\times 8$ outputs to describe the
proposed move of the network, but we add one more output to represent the
option of passing, i.e., to complete the turn without making a move. The
sensing policy is modeled as an $8\times 8$ output, denoting all possible
squares on the board. All of our experiments used only a few days of training
on a single Tesla M40 and can be reproduced using commonly available hardware.

Figure 1: Network architecture

###  III-A Supervised Learning

Similar to the setup in [1], we first train our network on human data before
using self-play to tune the policy. To this end, we used a dataset previously
used for training the opponent-specific networks of Penumbra [10]. From these
games, we construct training examples by using the taken actions as the target
output of the network, with the history of observations as the network’s
input. In contrast to games like chess and Go, a turn in RBC consists of two
actions, sensing and moving. To optimize these two separate but related
policies, we use the cross-entropy loss of both heads of the network and
optimize their sum. We use all games in the dataset, including losses and
games of lower-skilled opponents. Importantly, we do not mask illegal moves,
which adds significant difficulty for the network, as only a fraction of all
4673 possible moves is legal in a given position. We also do not mask the 28
outer squares of the board in the sensing policy, which are inferior sensing
actions that are dominated by choosing a square in the inner 6x6 area of the
board. This decision was made to account for the significant number of sub-
optimal senses in the dataset. Future experiments may explore the differences
in results when masking those.

After training for 5 epochs, which is equal to about 8 hours of wall time on
our machine, the network achieved a 49.71% sense and 48.34% move accuracy on a
held-out test set of 10% of the data, and 50.78% sensing and 53.91% moving
accuracy on the training data. We stopped training at this point as the
network started to overfit. To compute the accuracy, we only counted the
outputs of the network which exactly matched the chosen action in the data. A
significant number of predictions involve a large degree of randomness, so
there is no “correct” answer for many decisions, but achieving these levels of
accuracy in this setting indicates that the data is rather homogeneous. We
also counted sensing actions that were strictly better than the sense in the
target data as mistakes, such as sensing at g7, which reveals the content of 9
squares, instead of sensing on h8, which only shows a subset of 4 squares. A
different measure would have been to count the overlap between the predicted
and the target sensing action, but the main problem with this approach is that
the purpose of the sensing action is unknown. For example, its true intent
might have been collecting information about one particular square only.

###  III-B Reinforcement Learning

Although with our agent achieved a good accuracy of predictions through
supervised training, it did not learn learn to actually win the game.
Supervised learning attributes the same importance to correctly predicting to
capture the opponent’s king (which wins the game) as to playing the opening
move 1. e4. Moreover, it may also learn low-quality in-game actions such as
sensing at the edge of the board, which is never an optimal decision. Since
the goal of the agent should be to win the game, the second stage of training
by reinforcement learning rewards the agent only for achieving this objective.
We frame the problem as a Markov decision problem (MDP), where the opponent is
part of the stochastic environment, and use an on-policy reinforcement
learning algorithm. Although RBC is a partially observable Markov decision
problem (POMDP), we disregard the partial observability of the domain and use
the history of observations as if they were a complete description of the
state, thus approximating the POMDP as an MDP.

We train the agent by self-play and collect the actions taken and the result
of each game. With this experience, we optimize our agent using our own
implementation of Proximal Policy Optimization (PPO) [18]. To simultaneously
optimize both policies (sensing and moving) we compute separate losses for
both of them and perform gradient descent on their sum. While sensing is a
passive action that never directly results in winning the game, we reward the
final winning move and the sense just before it with a reward of 1. To reduce
overfitting to the current version of the agent, we let it play against
randomly selected past versions of itself, which are saved whenever they reach
a 65% win rate. This is similar to playing against the average strategy of
past best-responses, and a well-known technique [7, 14, 15].

In training, the probability $p_{i}$ of playing against a version $i$ of the
network depends on the win-rate $w_{i}$ of the training against it:

$p_{i}=1-(w_{i}/\sum_{i}w_{i})$ (1)

The win-rate $w_{i}$ is approximated as the average of the $K=500$ most recent
results of the training agent against it.

One important consideration in RBC, and an important difference from normal
chess, is that due to the partial observability, the optimal strategy should
be stochastic, as a deterministic strategy can easily be exploited. However,
when testing our agent, we found that choosing the action with highest
probability lead to slightly better performance.

##  IV Results

We tested the performance of our agent at two time points; after supervised
training and after reinforcement learning. The hypothesis is that adding
reinforcement learning, which directly aims to optimize the real objective of
winning games, should increase the win-rate compared to only supervised
training on public games.

###  IV-A ELO Performance

In order to evaluate the performance, we uploaded both versions to the public
leaderboard111https://rbc.jhuapl.edu/, which results in an approximate ELO
rating for each agent. After the supervised training, our agent’s performance
is similar to that of the publicly available baseline agent Trout, which is a
naive Stockfish-based agent. However, as seen in Table II, reinforcement
learning leads to a tangible performance benefit on the leaderboard. In
training, observed that it consistently learned to win against its previous
version. For example, the reinforced agent exhibits a win rate of more than
80% against the supervised agent throughout training. At the time of this
writing, these results put our agent at rank 27 out of 84 on the leaderboard,
although we did not see an indication of convergence.

TABLE II: Performance comparison of the proposed agent Name | Performance
---|---
Supervised agent | 1118
Reinforced agent | 1330
Trout (Public Stockfish baseline) | 1111

###  IV-B Analysis of Example Games

We observed that our agent has a highly aggressive, even reckless at times,
playing style. It often aims for very quick attacks on the enemy king,
sacrificing one or more pieces (including very early queen sacrifices) in
order to get to a position where the opponent’s king is no longer surrounded
by defenders and is not able to defend reliably against multiple possible and
unobserved threats of the agent. This kind of strategy works well against many
lower and middle-skilled opponents, and even scores the occasional win against
top contenders.

One game we want to highlight can be replayed at
https://rbc.jhuapl.edu/games/462287, where the agent played against one of the
higher-rated opponents on the leaderboard. In the game, our agent created two
situations where the opponent could not certainly determine from which square
its king was attacked but was able to sense the correct positions in order to
defend against the threats. In contrast, playing against a lower-rated
opponent (https://rbc.jhuapl.edu/games/462288) the same strategy worked well,
as the opponent did not have information about the bishop on c4, which lead to
a quick win. Similarly, in https://rbc.jhuapl.edu/games/462249, our agent
continuously made threats, which in the end led to an undetected knight
capturing the king. Such a strategy would not work well in classical chess,
which provides some evidence that policies in chess and RBC are not
necessarily similar, and that trying to reduce RBC to chess may be problematic
at times.

##  V Conclusion

In this work, we show our first results on applying an AlphaGo-inspired
training regime to the imperfect information game of Reconnaissance Blind
Chess. Our agent learns to use a history of observations to create
distributions of actions for both sensing and playing. First, we use
supervised training on publicly available expert games, where the task is to
predict the actions of the experts. Next, we use on-policy reinforcement
learning with self-play to strengthen the playing performance of the agent.
With this approach, we reached rank 27 of 84 on the leaderboard and an
estimated ELO of 1330, using no further game-specific optimizations.

To continue this work, we aim to refine our self-playing process. It is
currently unclear whether this process alone can lead to top performance..
Incorporating experience gained from playing on the leaderboard is much slower
than playing games against itself offline but may lead to more valuable
information from varied strong opponents, thus facilitating quicker
improvement. An additional angle that we aim to tackle is a combination of the
trained agent with a classical engine like Stockfish. Combining action
suggestions from both, or adapting Stockfish’s moves by using the probability
distribution of the agent, can lead to a more normal and classical playing
style, while also using learned experience from RBC self-play.

## Acknowledgements

We thank the reviewers of this paper for providing excellent feedback on
improving the presentation, pointers to related works that we had missed, and
suggestions for continuing this line of work.

## References

  * [1] David Silver et al.  “Mastering the game of Go with deep neural networks and tree search”  In _Nature_ 529.7587 Nature Publishing Group, 2016, pp. 484–489
  * [2] Nolan Bard et al.  “The Hanabi challenge: A new frontier for AI research”  In _Artificial Intelligence_ 280 Elsevier, 2020
  * [3] Christopher Berner et al.  “Dota 2 with Large Scale Deep Reinforcement Learning”  In _CoRR_ , 2019  arXiv:1912.06680
  * [4] Noam Brown and Tuomas Sandholm  “Superhuman AI for multiplayer poker”  In _Science_ 365.6456, 2019, pp. 885–890
  * [5] Noam Brown, Anton Bakhtin, Adam Lerer and Qucheng Gong  “Combining deep reinforcement learning and search for imperfect-information games”  In _Advances in Neural Information Processing Systems_ 33, 2020, pp. 17057–17069
  * [6] Matej Moravčík et al.  “DeepStack: Expert-level artificial intelligence in heads-up no-limit poker”  In _Science_ 356.6337, 2017, pp. 508–513
  * [7] Oriol Vinyals et al.  “Grandmaster level in StarCraft II using multi-agent reinforcement learning”  In _Nature_ 575.7782 Nature Publishing Group, 2019, pp. 350–354
  * [8] Timothy Highley, Brendan Funk and Laureen Okin  “Dealing with uncertainty: A piecewise grid agent for reconnaissance blind chess”  In _Journal of Computing Sciences in Colleges_ 35.8 Consortium for Computing Sciences in Colleges, 2020, pp. 156–165
  * [9] Tord Romstad, Marco Costalba and Joona Kiiski  “Stockfish” [accessed 26-April-2022], https://stockfishchess.org/, 2022
  * [10] Gregory Clark  “Deep Synoptic Monte-Carlo Planning in Reconnaissance Blind Chess”  In _Advances in Neural Information Processing Systems_ 34, 2021
  * [11] Sergey Savelyev  “Mastering Reconnaissance Blind Chess with Reinforcement Learning”, 2020
  * [12] Nikolai Yakovenko, Liangliang Cao, Colin Raffel and James Fan  “Poker-CNN: A Pattern Learning Strategy for Making Draws and Bets in Poker Games Using Convolutional Networks”  In _Proceedings of the 30th AAAI Conference on Artificial Intelligence_ AAAI Press, 2016, pp. 360–368
  * [13] Johannes Heinrich and David Silver  “Deep Reinforcement Learning from Self-Play in Imperfect-Information Games”  In _CoRR_ , 2016  arXiv:1603.01121
  * [14] Eric Steinberger, Adam Lerer and Noam Brown  “DREAM: Deep Regret minimization with Advantage baselines and Model-free learning”  In _CoRR_ abs/2006.10410, 2020
  * [15] Eric Steinberger  “Single Deep Counterfactual Regret Minimization”  In _CoRR_ abs/1901.07621, 2019
  * [16] Martin Schmid et al.  “Player of Games”  In _CoRR_ abs/2112.03178, 2021
  * [17] David Silver et al.  “Mastering Chess and Shogi by Self-Play with a General Reinforcement Learning Algorithm”  In _CoRR_ , 2017  arXiv:1712.01815
  * [18] John Schulman et al.  “Proximal Policy Optimization Algorithms”  In _CoRR_ , 2017  arXiv:1707.06347


# The Privacy-preserving Padding Problem: Non-negative Mechanisms for
Conservative Answers with Differential Privacy

Benjamin M. Case, James Honaker, Mahnush Movahedi Research Scientist,
Facebook<EMAIL_ADDRESS>Scientist, Facebook;
<EMAIL_ADDRESS>Scientist, Facebook<EMAIL_ADDRESS>
###### Abstract

Differentially private noise mechanisms commonly use symmetric noise
distributions. This is attractive both for achieving the differential privacy
definition, and for unbiased expectations in the noised answers. However,
there are contexts in which a noisy answer only has utility if it is
conservative, that is, has known-signed error, which we call a padded answer.
Seemingly, it is paradoxical to satisfy the DP definition with one-sided
error, but we show how it is possible to bury the paradox into approximate
DP’s $\delta$ parameter. We develop a few mechanisms for one-sided padding
mechanisms that always give conservative answers, but still achieve
approximate differential privacy. We show how these mechanisms can be applied
in a few select areas including making the cardinalities of set intersections
and unions revealed in Private Set Intersection protocols differential private
and enabling multiparty computation protocols to compute on sparse data which
has its exact sizes made differential private rather than performing a fully
oblivious more expensive computation.

##  1 Motivation

> Scenario: Jane wants to kill her husband Lord Edgware. She has an elaborate
> false alibi but is uncertain if Lord Edgware will be attending a particular
> dinner party. The butler is to be informed how many people to provision for;
> Jane may have already learned which other people are attending. Protective
> of his guests, the host sends the butler a differentially private count, so
> that if Jane intercepts the message, Jane can not learn if Lord Edgware will
> be attending so as to murder him. However, the butler does as is told, and
> it would be an impropriety for there not to be enough provisions for
> everyone in attendance. It is therefore essential that the number given to
> the butler is both differentially private (so no one is murdered), _and
> never be less than the true number of attendees_ (so every attendee can be
> accomodated).

The solution to this problem has direct applications to a number of scenarios
where a differentially private answer is needed to preserve privacy, but the
answer must be _conservative_ and thus any noise added must be non-negative
and never give an answer less than the true value. Conservative answers are
often desirable in contexts where the utility loss from error is more heavily
weighted on one side. One might carry a conservative amount of cash for a
purchase, because having left over cash has no cost, but having insufficient
cash means the purchase is not completed.

There are a number of applied contexts where a non-negative DP noise mechanism
would provide an important solution and basic building block:

  * •

As a computational example, Kellaris et al. [1] consider the problem where an
adversary is monitoring the size of traffic between a secure database and an
owner subsetting observations by range queries. Even if the queries
transmitted and the rows returned are encrypted, if the adversary observes the
true distribution of the size of returns, they are eventually able to
reconstruct the distribution of the dataset. Sending query responses with
differentially private numbers of rows defeats the adversary. However while
sending a larger than correct subset (that is, padding with removable fake
data) has low cost, sending a smaller than correct subset (by omitting
observations that satisfy the query) has a high utility cost.

  * •

Similarly, private set intersection (PSI) that enable computation on the
intersection of two private sets are important building block of secure
solutions [2, 3, Pinkas2019circuitlinear] which allows two parties to locate
the intersection of their data without directly revealing to either party
which observations the other has in common. However, many PSI protocols either
reveal the cardinalities of the set intersections and unions as an intended
output or as an additional leakage to the intended output; this opens up
attacks such as differencing for membership inference. Padding the set
intersection and union with dummy records sampled according to non-negative DP
machanisms can solve this problem by making the cardinalities differentially
private from the view of both parties.

  * •

In MPC games for conversion measurement, such as in [4] a mechanism for
positively padded DP histograms would provide a means to prevent the leakage
of the number of conversions without computationally inefficient padding of
all conversion event data to the upper bound of conversion count.

  * •

More generally, side-channel attack through timing or data access patterns
have been a long recognized problem in both MPC and differentially private
systems [5] when such side-channels are considered parts of the output that
need to meet the differential privacy definition. Methods suggested to avoid
such attacks have involved making all computations _constant-time_ but using
our mechanisms to pad compute or storage with a stocastically drawn strictly
positive DP waiting time we show can be a much more efficient solution.

  * •

In the foundational question of releasing a differentially private mean on a
set of unknown size, Covington et al. [6] show a setting where lowest mean
squared error is achieved when you can privately undercount the set (which is
an example of needing a conservative answer with non-positive error).

In this work, we present a general approach to creating noise mechanisms with
error with guaranteed sign, and solidify three such mechanisms. We show how
this provides a padding solution to PSI intersection and union leakages, as
well as one example of overcoming distribution and differencing attacks on MPC
implementations in the context of conversion measurement.

##  2 One-sided Noise

We are going to consider privatizing noise addition mechanisms, where the
noise $z$ is drawn from some distribution $p$ with no support on the negative
numbers, that is:

$\displaystyle M(X)$ $\displaystyle=f(X)\pm z;\qquad z\sim
p:p(s)=0\quad\forall\ s<0$ (1)

Statistical estimators whose error is of a guaranteed sign are called
_conservative_ , and can be desirable in certain applied contexts. We use
$\pm$ to highlight that we can guarantee the sign of the error in either
direction; we can add $z$ or subtract $z$. Throughout this paper, we write as
if we are adding $z$ so as to guarantee non-negative errors and _overvalued_
answers, but everything holds if instead we need to subtract $z$ to guarantee
non-positive errors in a differentially private _undervalued_ answer.

Let us first highlight the key dilemma of any such mechanism. Imagine two
neighbouring datasets $X$ and $X^{\prime}$ which happen to have
$f(X)<f(X^{\prime})$. We release a differentially private answer $M$. Then
whenever we observe a release $M<f(X^{\prime})$ we know we must be in dataset
$X$ and never in $X^{\prime}$; the mechanism $M$ can never give an answer
below $f(X^{\prime})$ if $X^{\prime}$ is the private data. This means we can
leak with certainty which state of the world we are in, which in turn violates
differential privacy. For example, if we are doing a counting query, and know
we have either dataset $X$ which has count 100, or neighboring dataset
$X^{\prime}$ which has count 101, and we use a non-negative noise
distribution, then whenever we see an answer of 100, we know we were in
dataset $X$. To remove this probability we are going to have to move to
approximate differential privacy and bury all $M<f(X^{\prime})$ into $\delta$.
We now consider distributions $p$ that satisfy
$(\epsilon,\delta)$-differential privacy in this way.

##  3 Mechanisms

###  3.1 Truncated Laplace

In the continuous case, consider a differentially private mechanism, $M$, that
releases answers to a query, $f$, on a dataset, $X$, with truncated Laplace
noise as:

$\displaystyle M(X)$ $\displaystyle=f(X)+z;\quad z\sim
p_{TruncatedLaplace}(b,\mu)$ (2) $\displaystyle
Pr_{TruncatedLaplace}(x|b,\mu)$
$\displaystyle=\left\\{\begin{array}[]{ll}0&x<0\\\ \frac{A}{2b}\
\textrm{exp}\Big{(}-\frac{|x-\mu|}{b}\ \Big{)}&x\geq 0\\\
\end{array}\right.\quad\textrm{where }b=\frac{\Delta}{\epsilon}$ (5)

with mode $\mu$, and shape parameter $b$ (variance $2b^{2}$ when untruncated),
and where all the mass below 0 has been truncated, so we need a normalizing
constant $A$, to bring the total probability mass back to one. We can solve
for $A$ (assuming $x<\mu$) as:

$\displaystyle A$ $\displaystyle=\Big{(}1-\int_{-\infty}^{0}\frac{1}{2b}\
\textrm{exp}\Big{(}-\frac{|x-\mu|}{b}\
\Big{)}dx\Big{)}^{-1}=\Big{(}1-\frac{1}{2}\
\textrm{exp}\Big{(}\frac{-\mu}{b}\Big{)}\Big{)}^{-1}\quad\ $ (6)

Note because $A$ works here by inflating the entire distribution by a constant
factor, in any ratio, these factors cancel. Thus the truncated Laplace
continues to obey the differential privacy definition which is itself defined
in terms of ratios. (This is only true when we truncate the distribution at
the same distance from the mean for all datasets.)

Whereas the Laplace satisfies pure $\epsilon$-differential privacy, the
truncated version is ($\epsilon$,$\delta$)-differentially private, so long as:

$\displaystyle\delta$ $\displaystyle\geq\int_{0}^{\Delta}\frac{A}{2b}\
\textrm{exp}\Big{(}-\frac{|x-\mu|}{b}\
\Big{)}dx=\frac{A}{2b}\textrm{exp}\Big{(}\frac{-\mu}{b}\Big{)}\int_{0}^{\Delta}\textrm{exp}\Big{(}\frac{x}{b}\Big{)}dx=\frac{A}{2}\textrm{exp}\Big{(}\frac{-\mu}{b}\Big{)}\Big{[}\textrm{exp}\Big{(}\frac{\Delta}{b}\Big{)}-1\Big{]}$
(7)

Figure 1: Depicted are two truncated Laplace noise distributions with the same
parameters, offset by some worst-case sensitivity $\Delta$. The shaded region
(exaggerated for visibility) shows the region with support in only one
distribution. Releases in this part of the noise distribution, can potentially
reveal which of two neighbouring datasets are true. That probability mass
needs to be covered by $\delta$.

A further note is that we can also symmetrically truncate the right tail of
the distribution for no additional cost, as represented in Figure 2. While
this means the regions where the distributions do not overlap apparently sum
now to $2\delta$, we are either in dataset $X$, which fails with $\delta$
probability in the left tail, or in dataset $X^{\prime}$ which fails with
$\delta$ probability in the right tail. In any state of the world, there
remains only a $\delta$ chance of failure. This slightly reduces the variance
of the noise, and returns the distribution to symmetry which conveniently
means the mode and mean are once again both at $\mu$. This makes the revised
inflationary constant:

$\displaystyle
A=\big{(}1-\textrm{exp}\Big{(}\frac{-\mu}{b}\Big{)}\big{)}^{-1}$ (8)

Figure 2: When the Laplace is doubly and symmetrically truncated, two
distributions that are offset by the worst-case sensitivity, $\Delta$, have
two regions that have no overlap. However, if there is a $p$ probability of
being in the Red distribution, and a corresponding $1-p$ probability of being
in the blue distribution, the total worst-case probability of a realized
outcome in a non-overlapping region remains $\delta$. This allows us to
truncate both tails under approximate differential privacy, and retain a
symmetric distribution.

We now require to know the mode as a function of $\epsilon$. In conventional
uses of the Laplace, $\mu=0$. In this use, we need $\mu$ to be sufficiently
distant from zero that the integral for $\delta$ is satisfied. At equality,
Equation 7 together with 8 gives us:

$\displaystyle\delta=\frac{\textrm{exp}\Big{(}\frac{-\mu}{b}\Big{)}}{2\big{[}1-\textrm{exp}\Big{(}\frac{-\mu}{b}\Big{)}\big{]}}\Big{[}\textrm{exp}\Big{(}\frac{\Delta}{b}\Big{)}-1\Big{]}$
$\displaystyle=\frac{\textrm{exp}\Big{(}\frac{-\mu\epsilon}{\Delta}\Big{)}}{2-2\
\textrm{exp}\Big{(}\frac{-\mu\epsilon}{\Delta}\Big{)}}\Big{(}e^{\epsilon}-1\Big{)}\Rightarrow\;\textrm{exp}\Big{(}\frac{-\mu\epsilon}{\Delta}\Big{)}=\frac{2\delta}{2\delta+e^{\epsilon}-1}$
$\displaystyle\Rightarrow\quad\mu$ $\displaystyle=-\frac{\Delta}{\epsilon}\
\textrm{ln}\Big{(}\frac{2\delta}{2\delta+e^{\epsilon}-1}\Big{)}$ (9)

Which ends up being quite succinct. Note that $e^{\epsilon}\\!-\\!1>0$ so the
logarithmic term is always a negative number, giving us a strictly positive
$\mu$ as expected.

####  3.1.1 Example

If we have $\epsilon=0.5$ and $\delta=10^{-6}$ for a sum query with
sensitivity $\Delta=1$ then this gives us $\mu=25.4$. Thus we would expect to
add 25.4 to the true sum. Given the truncated symmetry of the noise
distribution, we could add 0, and we would never add more than twice the mean,
or 50.8. At $\epsilon=1$ the expectation shrinks almost by half to 13.7.

###  3.2 Truncated Geometric/Discrete Laplace

Many of the use cases of padding involve adding integer counts of dummy users
or events to mask true totals. It is natural then to turn to distributions
over the Whole numbers. The geometric mechanism gives a discretized analog to
the Laplace mechanism over the integers, and we can truncate this distribution
similar to how we truncated the Laplace. Symmetric about zero, Kotz et al.
refer to this straightforwardly as the _double geometric distribution_ [7,
p.130]. Consider a mechanism using this distribution:

$\displaystyle M(X)$ $\displaystyle=f(X)+z;\quad z\sim p_{DoubleGeometric}(n)$
(10) $\displaystyle\textrm{Pr}_{DoubleGeometric}(x|n)$
$\displaystyle=Ae^{-\epsilon|n-x|};\qquad x\in\\{0,\ldots,2n\\}$ (11)

For some normalizing constant $0<A<1$ and some $n\in\mathbb{N}$.

(a) Example of the double geometric for $n=10$. (b) Two geometric
distributions offset by worst case sensitivity, $\Delta$, set here in this
example to 1. The parameter $\delta$ has to cover either of the tail extremes
that are not non-overlapping in distribution.

Figure 3: Normalization and truncation of the geometric distribution.

As a probability this must sum to 1, which lets us solve for $A$. Let
$r=e^{-\epsilon}$. Then we can rewrite as a classic geometric sequence as:

$\displaystyle 1=\Big{(}2A\sum_{k=0}^{n}e^{-k\epsilon}\Big{)}-A$
$\displaystyle=A\Big{(}-1+2\sum_{k=0}^{n}r^{k}\Big{)}=A\Big{(}-1+2\frac{1-r^{n+1}}{1-r}\Big{)}=A\Big{(}\frac{1+r-2r^{n+1}}{1-r}\Big{)}$
$\displaystyle\Rightarrow\quad A$
$\displaystyle=\frac{1-r}{1+r-2r^{n+1}}=\frac{1-e^{-\epsilon}}{1+e^{-\epsilon}-2e^{-\epsilon(n+1)}}$
(12)

If we have sensitivity $\Delta\in\mathbb{Z}^{+}$, then we need $\delta$ to
cover the tail as:

$\displaystyle\delta$ $\displaystyle\geq
A\sum_{k=n-\Delta+1}^{n}e^{-k\epsilon}$ (13)

For the common case of $\Delta=1$, such as in counting queries of users, at
equality this simplifies (see appendix A) to:

$\displaystyle\delta=Ae^{-n\epsilon}=Ar^{n}$
$\displaystyle=\frac{r^{n}(1-r)}{1+r-2r^{n+1}}$ (14)
$\displaystyle\Rightarrow\quad n$
$\displaystyle=\Big{\lceil}-\frac{1}{\epsilon}\
ln\Big{(}\frac{\delta(1+r)}{1-r+2r\delta}\Big{)}\Big{\rceil}$ (15)

The geometric distribution is unwieldy analytically beyond $\Delta=1$ so it is
natural to consider alternative distributions that do not have to be truncated
to the non-negative integers, but naturally only have support there.

###  3.3 Example

Consider we again target privacy-loss parameters of $\epsilon=0.5$ and
$\delta=10^{-6}$ for a sum or counting query with sensitivity $\Delta=1$. Then
this would solve to $n=25$ as the expected value of the added noise, with the
upper bound being 50.

###  3.4 Poisson

The Poisson distribution is the most common introductory statistical model of
counting processes, and a useful starting point when we consider
conservatively privatizing functions such as counting queries that have
support over non-negative integers.

Consider a mechanism with Poisson noise:

$\displaystyle M(X)$ $\displaystyle=f(X)+z;\quad z\sim
p_{\textrm{Poisson}}(\lambda)$ (16)
$\displaystyle\textrm{Pr}_{Poisson}(y|\lambda)$
$\displaystyle=\frac{\lambda^{y}e^{-\lambda}}{y!};\quad\lambda>0.$ (17)

for some constant rate parameter $\lambda$. We assume $f(.)\in\mathbb{Z}$ has
sensitivity $\Delta\in\mathbb{N}$. Assume two neighbouring datasets are
ordered for convenience such that $f(X)\leq f(X^{\prime})$.

In the region $k\geq f(X)+\Delta$ we know any two neighbouring datasets must
have overlapping release distributions, whose ratio we can define as:

$\displaystyle
e^{\epsilon}\geq\max_{X,X^{\prime}}\frac{M(X^{\prime})}{M(X)}=\max_{y}\frac{\frac{\lambda^{y}e^{-\lambda}}{y!}}{\frac{\lambda^{y+\Delta}e^{-\lambda}}{(y+\Delta)!}}\quad\Rightarrow\quad\epsilon=-\Delta\textrm{log}(\lambda)+\max_{y}\prod_{i=1}^{\Delta}(y+i)$
(18)

However, this rightmost term has no limit as $y\Rightarrow\infty$, so the
right tail behavior of Poisson ratios does not collapse in a fashion that can
converge to a limit. One solution is that we can truncate the right tail of
the Poisson so this limit isn’t reached. Another solution would be to
determine the additional $\delta$ that is required to cover this tail
behaviour, as is done for the Gaussian mechanism. However, we instead shift
now to distributions with improved tail behaviour.

###  3.5 Negative Binomial

While the Poisson has an intuitive generative form, the constraint that both
the mean and the variance are directly determined by the same underlying
parameter $\lambda$ can lead to inflexibility in applied settings. There are,
therefore, many practical generalizations of the Poisson that allow the mean
and variance to be decoupled to independent parameters. Moreover, the Poisson
could not meet the differential privacy definition because it does not have a
sub-exponential tail. We turn now to a heavier tailed distribution on counts,
the Negative Binomial, and show it can meet the approximate differential
privacy definition as a noise mechanism.

Consider a mechanism with Negative Binomial noise as:

$\displaystyle M(X)$ $\displaystyle=f(X)+z;\quad z\sim
p_{\textrm{NegBin}}(\lambda)$ (19) $\displaystyle\textrm{Pr}_{NegBin}(y|r,p)$
$\displaystyle={k+r-1\choose r-1}(1-p)^{k}p^{r};\quad r\in\mathbb{N},\
0\\!>\\!p\\!>\\!1.$ (20)

We first show the ratio of the tails converges:

$\displaystyle\max_{X,X^{\prime}}\frac{Pr[M(X^{\prime})=k]}{Pr[M(X)=k]}$
$\displaystyle=\max_{k}\frac{{k+r-1\choose
r-1}(1-p)^{k}p^{r}}{{k+r-1+\Delta\choose
r-1}(1-p)^{k+\Delta}p^{r}}=\max_{k}\frac{(k+r-1)!(k+\Delta)!}{(k+r-1+\Delta)!(k)!}(1-p)^{-\Delta}$
$\displaystyle=(1-p)^{-\Delta}\lim_{k\rightarrow\infty}\frac{\prod_{j=1}^{\Delta}k+j}{\prod_{j=1}^{\Delta}k+r-1+j}=(1-p)^{-\Delta}$
(21)

Which allows us to solve for $\epsilon$ as:

$\displaystyle
e^{\epsilon}\geq(1-p)^{-\Delta}\quad\Rightarrow\quad\epsilon=-\Delta\;\textrm{ln}(1-p)\quad\Leftrightarrow\quad
p=1-\textrm{exp}(-\frac{\epsilon}{\Delta})$ (22)

Note this is roughly $p\approx\epsilon/\Delta,\forall\epsilon/\Delta<1$. Since
$\epsilon$ and $p$ are related, we attempt to fix $\delta$ simply as a
function of the remaining free parameter, $r$. As before:

$\displaystyle\delta\geq\sum_{j=0}^{\Delta-1}Pr_{NegBin}(j|p,r)$ (23)

For the common case where $\Delta=1$, as for example depicted in Figure 4,
this means:

$\displaystyle\delta\geq{r-1\choose
r-1}(1-p)^{0}p^{r}=p^{r}\quad\Rightarrow\quad\delta=p^{r}\quad\Leftrightarrow\quad
r=\Big{\lceil}\frac{\textrm{ln}(\delta)}{\textrm{ln}(p)}\Big{\rceil}$ (24)

Figure 4: Depicted are two negative binomial distributions with the same
parameters, offset by some worst-case sensitivity $\Delta$, where here
$\Delta=1$. The shaded region (exaggerated for visibility) shows the region
with support in only one distribution which has to be covered by $\delta$.

###  3.6 Example

Consider again we have $\epsilon=0.5$, and $\delta=10^{-6}$ for a sum or
counting query with sensitivity $\Delta=1$. This gives us $p=0.39$ from which
we can compute $r=15$. The negative binomial has expection $r(1-p)/p$ which
calculates to an expected value of 23.2 using the negative binomial mechanism.
This is a close but slightly lower number of padded values than using the
truncated Laplace or geometric mechanisms.

###  3.7 Discretized Uniform and Binomial Distributions

Two heuristics for padding of records that we have seen are to add records
drawn from a uniform distribution, or flip a (typically small) number of coins
and add records for every coin that comes up heads. Since we now have a
framework for formalizing the privacy of padding distributions, we briefly
point out the associated DP privacy parameters these heuristics imply.

$\displaystyle Pr_{DisUniform}(k|N)$ $\displaystyle=1/(N+1);$
$\displaystyle\quad k\in\\{0,1,\cdots,N\\}$ $\displaystyle\Rightarrow\epsilon$
$\displaystyle=0$ $\displaystyle\quad\delta$ $\displaystyle=\Delta/(N+1)$ (25)
$\displaystyle Pr_{Binomial}(k|N)$ $\displaystyle={N\choose k}0.5^{N};$
$\displaystyle\quad k\in\\{0,1,\cdots,N\\}$ $\displaystyle\Rightarrow\epsilon$
$\displaystyle=\textrm{ln}{N\choose\Delta}$ $\displaystyle\quad\delta$
$\displaystyle=0.5^{N}\sum_{j=0}^{\Delta-1}{N\choose j}$ (26)

From this perspective we see: (1) the discretized uniform mechanism has a very
large $\delta$ term, unless $N$ is of the same order as the size of the
dataset, (2) the binomial distribution has a very large $\epsilon$ for any $N$
that gives a conventionally sized $\delta$.

##  4 Application to Private Set Intersection

Private Set Intersection considers the problem where two parties $X$ and $Y$
hold private sets $D_{X},D_{Y}\subset D$ and wish to compute some function on
the intersection of their two sets; this function could i) reveal the
intersection to one or both parties $f(D_{X},D_{Y})=D_{X}\cap D_{Y}$
[meadows1986more, dhoriginal, freedman2004efficient, kissner2005privacy] or
ii) compute the cardinality of the intersection or union
$f(D_{X},D_{Y})=|D_{X}\cap D_{Y}|$ or $f(D_{X},D_{Y})=|D_{X}\cup D_{Y}|$ [8]
or iii) as more recent research on PSI has focused, enable a more general
computation on the intersection and associated values to each record and only
have parties learn this intended output. For instance, [9] appends one of the
sets $D_{X}$ with values $(D_{X},V_{X})$ and computes the sum of values for
intersected records $\sum_{x_{i}=y_{j}}v_{i}$ and [4] computes a sum also
conditioned on a comparison, for $(D_{X},T_{X},V_{X})$ and $(D_{Y},T_{Y})$
compute $\sum_{x_{i}=y_{j},t_{i}\geq t_{j}}v_{i}$.

The intended outputs of $f$ can be secured by various DP methods depending on
the nature of $f$, e.g. making a sum of associated values differentially
private. However, a common issue that many PSI protocols have is an additional
leakage of the intersection size $|D_{X}\cap D_{Y}|$ and union size
$|D_{X}\cup D_{Y}|$ besides the intended outputs. This is the case with the
Private-ID, PS3I, and Private Join and Compute protocols [3, 9, 10].

We assume a PSI protocol will leak intersection and union sizes, and that any
fix should treat the protocol as a black box and be entirely fixed by means of
the datasets submitted by the parties. This requires both parties to be semi-
honest, which is the assumption already being made in most PSI protocols. To
do this we consider how two parties can each independently draw observations
from a shared pool to pad the private data they submit to PSI. Whenever a
collision occurs, that is, both parties draw the same fictitious observation
from the pool, then the intersection count is padded by one more unit. We want
to ensure (1) that neither party can work out the other’s padded observations
(or the collisions) so they can not reverse engineer the noise addition, and
(2) the number of collisions—which increase the intersection size leaked by
PSI—is guaranteed to form a differentially private distribution and thus
sufficiently mask the true intersection size. To additionally protect the size
of the union we will have both parties draw fictitious records from non-
intersecting pools and append them to their input sets.

Our techniques naturally apply to give output privacy to protocols such as [8]
that compute the cardinality of the intersection and the union. Other PSI
protocols that our techniques can be applied to include the semi-honest
constructions from [2, 3, 11] that compute functions on the intersection while
leaking the size of the intersection in the process. Our techniques are
straighforward to apply as long as any associated values to dummy rows can be
assigned appropriately so as not the change the intended output. Since our
construction is semi-honest, it is not compatible with the maliciously secure
private intersection-sum and cardinality protocols of [12].

###  4.1 DP intersection size for both parties

Let $X$ and $Y$ be two parties who have private finite sets
$D_{X},D_{Y}\subset D$ whose intersection is unknown of size $I=|D_{X}\cap
D_{Y}|$. Let $A_{X}$ and $A_{Y}$ be public finite disjoint sets with no
intersection to each other or $D$. Let $p(\epsilon,\delta)$ be a non-negative
differentially private probability distribution on $\mathbb{N}_{0}$, such as
from those developed in Section 3. We have party $X$ draw an integer
$z_{x}\sim p(\epsilon_{x},\delta_{x})$ and then sample a random subset
$a_{X}\subset A_{X}$ of size $z_{x}$. They then submit a padded dataset
$D_{X}^{+}=\\{D_{X}\cup a_{X}\cup A_{Y}\\}$ to some PSI protocol, that is,
they combine their private data, with their recent sample and the entirety of
the set they did not sample from. In parallel, $Y$ draws $z_{y}\sim
p(\epsilon_{y},\delta_{y})$, samples $a_{Y}\subset A_{Y}$ of size $z_{y}$, and
submits padded data $D_{Y}^{+}=\\{D_{Y}\cup A_{X}\cup a_{Y}\\}$. What is core
to see is that the random subset $X$ generates, $a_{X}$, will all have
collisions in the PSI protocol because $Y$ submits the superset $A_{X}$, and
vice versa.

To ensure that there are $z_{x}$ or $z_{y}$ elements available to be sampled,
we can use the doubly truncated geometric distribution which has a known
maximum which we use to populate $A_{X}$ and $A_{Y}$ accordingly (otherwise we
need $A_{X}$, $A_{Y}$ to be unbounded sets, which even if approximated
increases communication). When we run PSI on $D_{X}^{+}$ and $D_{Y}^{+}$ we
leak the intersection size, which is $I+z_{x}+z_{y}$, to both parties. Party
$X$ privately knows $z_{x}$ so can subtract that and learn $I+z_{y}$ which is
still $(\epsilon_{y},\delta_{y})$-DP. Correspondingly, party $Y$ can subtract
$z_{y}$ and only learn $I+z_{x}$ which is $(\epsilon_{x},\delta_{x})$-DP. Thus
each party only learns a differentially private answer to the intersection
size, whose privacy-loss is controlled by their adversary.

The additional computation and communication is low. Recall that for the
doubly truncated geometric distribution the expectation, $n$, is given in Eq.
15 as a function of $\epsilon$ and $\delta$, and is typically of size 10–100.
For simplicity assume both parties use the same privacy-loss parameters, and
thus the same $n$. Then the sets $A_{X}$ and $A_{Y}$ will be of size $2n$, the
expected padding to $D_{X}^{+},D_{Y}^{+}$ will each be $3n$ and the padding to
$\\{D_{X}^{+}\cap D_{Y}^{+}\\}$ will have expectation $2n$.

Many PSI protocols that reveal the size of the intersection also reveal the
size of the union $|D_{X}\cup D_{Y}|$ as a result of revealing the sizes of
the input sets $D_{X}$ and $D_{Y}$; this reveals the union size since
$|D_{X}\cup D_{Y}|=|D_{X}|+|D_{Y}|-|D_{X}\cap D_{Y}|$. When we apply our above
technique for DP intersection sizes, it does not give a DP protection to the
size of the union, but we can modify it to do so. This is because the size of
the union is revealed when running on our input sets $D_{X}^{+}=\\{D_{X}\cup
a_{X}\cup A_{Y}\\}$ and $D_{Y}^{+}=\\{D_{Y}\cup A_{X}\cup a_{Y}\\}$. The union
size is $|D_{X}^{+}\cup D_{Y}^{+}|=|D_{X}\cup D_{Y}|+2n$ where
$n=|A_{X}|=|A_{Y}|$, and since $n$ is public both parties learn the true size
of $|D_{X}\cup D_{Y}|$.

The reason this does not also leak the size of the intersection through the
relation $|D_{Y}^{+}\cup D_{X}^{+}|=|D_{X}^{+}|+|D_{Y}^{+}|-|D_{X}^{+}\cap
D_{Y}^{+}|$ is that party $X$ (without loss of generality) in the formula

$\displaystyle|D_{Y}^{+}\cup D_{X}^{+}|$
$\displaystyle=|D_{X}^{+}|+|D_{Y}^{+}|-|D_{X}^{+}\cap D_{Y}^{+}|$
$\displaystyle|D_{Y}\cup D_{X}|+2n$
$\displaystyle=(|D_{X}|+z_{x})+(|D_{Y}|+z_{y})-(|D_{X}\cap
D_{Y}|+z_{x}+z_{y})$

knows the value of the left hand side, and the values of $|D_{X}|$, $z_{X}$,
$|D_{Y}|+z_{y}$ and $|D_{X}\cap D_{Y}|+z_{y}$. So moving all the terms $X$
knows to the left side

$\displaystyle|D_{Y}\cup D_{X}|+2n-|D_{X}|$
$\displaystyle=(|D_{Y}|+z_{y})-(|D_{X}\cap D_{Y}|+z_{y})$

we see $X$ cannot solve for any of the values of $|D_{Y}|$, $z_{y}$, or
$|D_{X}\cap D_{Y}|$ and can only conclude that $|D_{Y}|+|D_{X}\cap D_{Y}|=v$
where $X$ knows the value of $v$. Said another way $X$ learns only a
differentially private size of the party $Y$’s input and the intersection.

$a_{X,1}$ $a_{X,2}$ $a_{X,3}$ $a_{X,4}$ $a_{X,5}$ $a_{X,6}$ $a_{X,7}$
$a_{X,8}$ $a_{X,9}$ $a_{X,10}$ $a_{Y,1}$ $a_{Y,2}$ $a_{Y,3}$ $a_{Y,4}$
$a_{Y,5}$ $a_{Y,6}$ $a_{Y,7}$ $a_{Y,8}$ $a_{Y,9}$ $a_{Y,10}$ $a_{X,1}$
$a_{X,2}$ $a_{X,3}$ $a_{X,4}$ $a_{X,5}$ $a_{X,6}$ $a_{X,7}$ $a_{X,8}$
$a_{X,9}$ $a_{X,10}$ $a_{Y,1}$ $a_{Y,2}$ $a_{Y,3}$ $a_{Y,4}$ $a_{Y,5}$
$a_{Y,6}$ $a_{Y,7}$ $a_{Y,8}$ $a_{Y,9}$ $a_{Y,10}$ Selected Rejected
$A_{X}$$A_{Y}$$X$ Selects$Y$ Selects Figure 5: _The common pool of
observations with example selections from the collision protocol. Party $X$,
whose selections are shown on the right, randomly samples from $A_{X}$ and
takes all of $A_{Y}$. Party $Y$, shown on left, randomly samples from $A_{Y}$
and takes all of $A_{X}$. Each party’s random samples are guaranteed to
collide in the PSI protocol, creating padded users from the desired
differentially private distribution._

###  4.2 DP union size for both parties

We can extend our method to also give differential privacy to union
cardinality by considering another two sets $B_{X}$ and $B_{Y}$ which are
public finite disjoint sets with no intersection to each other or the sets
$D$, $A_{X}$, or $A_{Y}$. Similar to before we let $p(\epsilon,\delta)$ be a
non-negative differentially private probability distribution on
$\mathbb{N}_{0}$ and have party $X$ draw an integer $v_{x}\sim
p(\epsilon_{x},\delta_{x})$ and then sample a random subset $b_{X}\subset
B_{X}$ of size $v_{x}$. They then submit the padded dataset
$D_{X}^{++}=\\{D_{X}\cup a_{X}\cup A_{Y}\cup b_{x}\\}$. In parallel $Y$ draws
$v_{y}\sim p(\epsilon_{y},\delta_{y})$ and samples $b_{Y}\subset B_{Y}$ of
size $v_{x}$ and submits the padded data $D_{Y}^{++}=\\{D_{Y}\cup A_{X}\cup
a_{Y}\cup b_{Y}\\}$. Now the additionally padded sets $b_{x}$ and $b_{Y}$ will
not have any collisions and so will not contribute to the intersection size
but they will contribute to the union size so that $|D_{X}^{++}\cup
D_{Y}^{++}|=|D_{X}\cup D_{Y}|+2n+v_{x}+v_{y}$. These sets are illustrated in
Figure 7 in the Appendix. Thus if a PSI protocol reveals or leaks the size of
the union, Party $X$ knows $v_{x}$ and $n$ and so can subtract to learn
$|D_{X}\cup D_{Y}|+v_{y}$ which is still $(\epsilon_{y},\delta_{y})$-DP.
Correspondingly, party $Y$ can learn $|D_{X}\cup D_{Y}|+v_{y}$ which is still
$(\epsilon_{x},\delta_{x})$-DP. Thus each party only learns a differentially
private answer to the union size whose privacy-loss is controlled by their
adversary.

###  4.3 DP intersection size for one party

In some compute settings, only one party, say $X$, observes the intersection
size from PSI. In this simpler setting we only need to conceal the
intersection size from that party. We can then have $Y$ submit
$D_{Y}^{+}=\\{D_{Y}\cup a_{Y}\\}$, where $a_{Y}$ is generated as before, and
$X$ submit $D_{X}^{+}=\\{D_{X}\cup A_{Y}\\}$.

###  4.4 Integration with the Private-ID protocol

The private Private-ID protocol [3] allows the parties to privately compute a
set of pseudorandom universal identifiers (UID) corresponding to the records
in the union of their sets, where each party additionally learns which UIDs
correspond to which items in its set but not if they belong to the
intersection or not. This allows both parties to independently sort their UIDs
and the associated records and feed them to any general purpose MPC that
ignores the non-matching records and computes on the matching ones. This
protocol leaks the sizes of the input sets, union, and intersection to both
parties. Applying our techniques for DP intersection causes the sizes of the
input sets and intersection to be differential private. If we additionally
apply our techniques for DP unions, the size of the union becomes
differentially private. In the downstream usage of the UID, both parties will
input null associated records for the dummy rows created by the DP noise. This
will allow the DP noise added to secure the leakages of the Private-ID
protocol not to effect the actual outcomes computed in any downstream MPC
process, which may have its own separate DP mechanisms. Applying our
techniques to the multi-identifier version of the Private-ID protocol [10] is
a bit more complicated due to the greater leakage in that protocol; we leave
this as future work.

###  4.5 Integration with the PS3I protocol

The PS3I protocol is a decisional Diffie–Hellman (DDH) PSI variant that
attaches additive homomorphic encryptions (HE) of associated values to each
identifier; the output is secret shares of the associated values for matched
records. Both parties learn the sizes of each others input sets, the
intersection size, and thus the union size. If we apply our technique for DP
intersection sizes, we make the sizes of the input sets and the intersection
size differentially private, and further if we apply our technique for DP
union sizes, we make the union size differentially private. These additional
dummy rows can be assigned a zero associated value or other null value which
will be secret shared between the two parties and passed to some other
downstream MPC.

###  4.6 Integration with the Private Join and Compute protocol

The Private Join and Compute protocol [2] is similar to the PS3I protocol
except that attached HE encrypted values are not secret shared but rather
joined for users in the intersection. Downstream operations on these encrypted
values are thus limited by the additive HE scheme to being linear operations.
Both parties learn the sizes of each others input sets, the intersection size,
and thus the union size. If we apply our technique for DP intersection sizes,
we make the sizes of the input sets and the intersection size differentially
private, and further if we apply our technique for DP union sizes, we make the
union size differentially private. The dummy rows can include homomorphic
encryption of zero so as not to change the result of the downstream additive
HE calculation. Of course, the additive HE could be replaced with fully
homomorphic encryption enabling other additional operations in the downstream,
and depending on the nature of the downstream computation other values might
be included for the null values. For instance, if the downstream included all
multiplications, then encrypting the multiplicative identity, 1, for dummy
rows would ensure the downstream result was not effected by the noise.

##  5 Application to MPC side-channel attacks and DP Histograms

The blending of secure multiparty computation and differential privacy (MPDPC)
as interwoven privacy enhancing technologies has the promise to offer privacy
across stores, across computation, and across releases, that is, enabling a
computation to occur across the data of multiple parties while encrypting the
data during computation and offering differentially private answers at the
conclusion (sometimes described as input and output privacy respectively). In
simple settings this blend means the algorithm that is encoded in the MPC game
needs itself to have differentially private outputs, such as noise mechanisms
for the released values. However, in the typical DP threat models
(particularly in the centralized curator model) the “output” is only the final
answers released to the world at the end of the computation, whereas in the
MPC threat model, the act of computation is itself a continuous output under
observation by the adversarial parties. While MPC shields all the data values
and intermediate calculations, it is often susceptible to inference on the
data by sidechannels, a risk receiving increasing attention.

Consider an MPC implementation that counts a grand sum of a predicate over
user records. This is a common generic task, as for example in the style of
[4], where a dataset consists of the events associated with each user, and we
are counting the sum of all user events that meet a filter. The grand sum can
be made differentially private by noise additon, however, oftentimes one loops
first over users, and then over those user’s events. Within the MPC
calculation either (1) the storage access pattern, or (2) the total time to
compute the predicate over that user’s records, can directly leak the number
of events for each user.

Thus while MPC encrypts the data, storage access and timing present common
side channels, which are themselves an output (as for example explicitly
considered by [5]). If the goal of MPDPC is to privatize all outputs, then we
need DP promises on all such channels. The main solution to timing attacks and
storage in MPC has been to enforce constant-time/constant-storage
computations, which typically entail lengthening compute time to the worst
case, often at severe efficiency loss.

###  5.1 Non-negative padding for side-channel solution

A partial solution to this is to shuffle the order in which users are
evaluated. This means if we leak compute time or record recall for the first
user in the dataset and determine they had five events, we don’t know which
user had those five events. However, at the end of the grand sum, we will have
witnessed the number of events for each user in the dataset, leaking the
histogram of the number of events. If an adversary can rerun the computation
with a differencing attack, say by removing Alice’s data, then the category in
the histogram that changed will reveal Alice’s data, deterministically.

The constant-time/constant-storage solution to this is to pad all users with
the maximum number of events (but make sure that the fake events fail the
predicate being counted). From the differencing attack perspective, now the
histogram has only one category and no information is revealed. However, the
computational cost of this can be enormous, particularly if a rare number of
important users have very many events.

Instead of padding each user’s events, non-negative DP noise can be used to
generate new users whose data makes the leaked histogram differentially
private. Consider a dataset, $D$, of $N$ individuals who can have up to
$\\#d_{i}\leq K$ events, and assume the histogram of $\\#d$ is leaked by
timing. For each $i=\\{0,\cdots,K\\}$ we draw $j_{i}\sim p(\epsilon,\delta)$
from a non-negative DP noise distribution on $\mathbb{N}_{0}$, and add $j_{i}$
users with $i$ (predicate failing) events to dataset $D$. The resulting
histogram is $(\epsilon,\delta)$-DP and masks the histogram of user events.

###  5.2 Example

Assume users are roughly uniformly distributed in number of events across
$\\{0,\cdots,K\\}$. This is conservative as oftentimes such distributions have
modes at zero and heavy tails. A constant-time solution requires each user now
to have exactly $K$ events for MPC to cycle over, meaning we have padded the
data with $N\\!K/2$ events in expectation. If instead we add DP padded users
to each event number, we add $\sum_{i=0}^{K}nK=nK(K+1)/2$ padded events, where
$n$ is again the expectation of the DP distribution $p$ as in Eq. 15. For
datasets with many more users than possible events, that is $N\\!\gg\\!K$,
then $n(K\\!+\\!1)\\!\ll\\!N$ and the number of padded events—and hence added
MPC compute time—is much lower from using DP non-negative padded users, than
from constant-time computation.111We note that this is not a complete analysis
of the timing difference. There might be costs in shuffling the data, which
are not required in the constant-time solution, as well as fixed timing costs
in overhead per user (unrelated to number of events). These can be added for
an exact comparison if the timing difference is close, however, the key logic
remains.

###  5.3 Shuffle of Private-ID Universal Identifiers

The Private-ID protocol [3] allows the parties to privately compute a set of
pseudorandom universal identifiers (UID) corresponding to the records in the
union of their sets, where each party additionally learns which UIDs
correspond to which items in its set but not if they belong to the
intersection or not. This allows both parties to independently sort their UIDs
and the associated records and feed them to any general purpose MPC that
ignores the non-matching records and computes on the matching ones. The number
of associated records to be passed into the downstream MPC computation varies.
Non-matched records have zero associated records while matched records may
have many records depending on the application. In order to not reveal the
number of records per row, we can apply our padding for DP Histograms as long
as we can perform a shuffle on the Private-ID UIDs. The cost of an oblivious
shuffle of $n$ elements in MPC is often estimated as requiring $cnlog(n)^{2}$
where $c$ is a constant in the range $[4,7]$.

(a) Constant time versus DP padded datasets (b) Privacy-preserving histogram
from DP padding

Figure 6:  _On the left figure we see a dataset padding every user to the
worst case. In the center is a dataset plus the padded observations created by
adding a DP non-negative number of users for each event count. These are
separated in the center for visual clarity, but are shuffled along with the
original data on the right. Far fewer padded events (blue items) are required
with DP padding.
On the right figure we see the privacy preserving histogram that would result
from this solution, broken into the contributions by the original data (gray)
and padded data (blue). The resulting blue noise in this DP histogram defeats
any differencing attack._

##  6 Prior Work

The combination of padded records and differential privacy in the context of
storage and joins has been recognized as a solution for side-channel attacks.
While we believe our mechanisms are lightweight and straightforward in
construction, and thus well tailored to individual queries, previous papers
have achieved positive padding for database stores in large scale ways that
permit repeated queries. Encryted storage techniques, such as Oblivious RAM,
have been shown to be susceptible to side-channel attacks on data access
patterns and communication volume [13, 14, 15]. Bogatov et al. [16] considers
a DP sanitization solution that uses a DP tree hierarchy. This effectively
results in buckets of storage each of which have some padded users and combine
to offer a DP guarantee to queries on the store. Relatedly, Xu et al. [17]
implement a DP padding solution for the same problem that uses a shifted and
tail-censored Laplace. This is the closest to anything we present, however,
their use of a $\delta$ parameter is censoring of the entire left tail of the
Laplace, whereas we use $\delta$ for a narrower purpose. Groce et al. [18]
also improve this Laplace approach within a Bayesian context. Allen et al.
[19] use a padding procedure on Oblivious RAM that adds sufficiently large
numbers of fake records that the standard (zero-centered) ($\epsilon$,0)-DP
Laplace mechanism computationally is ensured to result in answers that can be
filled with all the true records plus some number of the fake records which
act as padding, functionally quite similar to this shifted and tail-censored
Laplace mechanism reoccuring in the literature.

Differential privacy has been considered in the context of solving side-
channel leakage in private record linkage by [20, 21, 22]. Within private
record linkage, He et al. [23] explicitly connect this to private set
intersection, using the shifted tail-censored Laplace, and [18] extends this
work. The side-channel they both consider is load estimates in blocks from
hashing.

Any DP noise distribution on $\mathbb{R}$ (or $\mathbb{Z}$) can be converted
to a non-negative distribution on $\mathbb{R}_{\geq 0}$ (or $\mathbb{N}_{0}$)
by proceedures we have used for truncating and shifting the Laplace and
geometric mechanisms. However, some mechanisms from prior work naturally
generate releases on a bounded interval, and like our use of the negative
binomial, these could be more readily converted. Quick [24, 25, 26] has a
differentially private formulation of the Poisson-gamma distribution that is
used to make all DP released counts strictly non-negative, and it would be
straightforward to convert this mechanism from making the release non-negative
to the noise to be non-negative. Similarly, implementations of the Dirichlet
distribution going back to Machanavajjhala et al. [27] could be so converted.

##  7 Conclusion

Differentially private noise mechanisms typically have symmetric noise about
the true sample value. However, there are useful applications where we require
an error with a known sign. Truncations of the Laplace and geometric
distributions, as well as count distributions with subexponential tails, such
as the negative binomial, can be converted into non-negative (or non-positive)
noise mechanisms under approximate differential privacy. Such mechanisms are
particularly appealing for operations where we need to pad the underlying data
with extra observations so as to make any system leakage differentially
private, as in oblivious storage, private set intersection, and timing and
storage side-channels in MPC.

##  Appendix A Appendix

The derivation of the $\delta$ constraint for the geometric mechanism can be
shown as:

$\displaystyle Ae^{-n\epsilon}=Ar^{n}$
$\displaystyle=\frac{r^{n}(1-r)}{1+r-2r^{n+1}}<\delta$ (27)
$\displaystyle\Rightarrow\quad r^{n}$
$\displaystyle<\frac{\delta(1+r-2r^{n+1})}{1-r}$ (28)
$\displaystyle\Rightarrow\quad r^{n}\Big{(}1+\frac{2r\delta}{1-r}\Big{)}$
$\displaystyle<\frac{\delta(1+r)}{1-r}$ (29) $\displaystyle\Rightarrow\quad
r^{n}\Big{(}\frac{1-r+2r\delta}{1-r}\Big{)}$
$\displaystyle<\frac{\delta(1+r)}{1-r}$ (30) $\displaystyle\Rightarrow\quad
r^{n}(1-r+2r\delta)$ $\displaystyle>\delta(1+r)$ (31)
$\displaystyle\Rightarrow\quad r^{n}$
$\displaystyle>\frac{\delta(1+r)}{1-r+2r\delta}$ (32)
$\displaystyle\Rightarrow\quad e^{-\epsilon n}$
$\displaystyle>\frac{\delta(1+r)}{1-r+2r\delta}$ (33)
$\displaystyle\Rightarrow\quad n$
$\displaystyle=\Big{\lceil}-\epsilon^{-1}ln\Big{(}\frac{\delta(1+r)}{1-r+2r\delta}\Big{)}\Big{\rceil}$
(34)

$a_{X,1}$ $a_{X,2}$ $a_{X,3}$ $a_{X,4}$ $a_{X,5}$ $a_{X,6}$ $a_{X,7}$
$a_{X,8}$ $a_{X,9}$ $a_{X,10}$ $a_{Y,1}$ $a_{Y,2}$ $a_{Y,3}$ $a_{Y,4}$
$a_{Y,5}$ $a_{Y,6}$ $a_{Y,7}$ $a_{Y,8}$ $a_{Y,9}$ $a_{Y,10}$ $b_{X,1}$
$b_{X,2}$ $b_{X,3}$ $b_{X,4}$ $b_{X,5}$ $b_{X,6}$ $b_{X,7}$ $b_{X,8}$
$b_{X,9}$ $b_{X,10}$ $b_{Y,1}$ $b_{Y,2}$ $b_{Y,3}$ $b_{Y,4}$ $b_{Y,5}$
$b_{Y,6}$ $b_{Y,7}$ $b_{Y,8}$ $b_{Y,9}$ $b_{Y,10}$ $a_{X,1}$ $a_{X,2}$
$a_{X,3}$ $a_{X,4}$ $a_{X,5}$ $a_{X,6}$ $a_{X,7}$ $a_{X,8}$ $a_{X,9}$
$a_{X,10}$ $a_{Y,1}$ $a_{Y,2}$ $a_{Y,3}$ $a_{Y,4}$ $a_{Y,5}$ $a_{Y,6}$
$a_{Y,7}$ $a_{Y,8}$ $a_{Y,9}$ $a_{Y,10}$ $b_{X,1}$ $b_{X,2}$ $b_{X,3}$
$b_{X,4}$ $b_{X,5}$ $b_{X,6}$ $b_{X,7}$ $b_{X,8}$ $b_{X,9}$ $b_{X,10}$
$b_{Y,1}$ $b_{Y,2}$ $b_{Y,3}$ $b_{Y,4}$ $b_{Y,5}$ $b_{Y,6}$ $b_{Y,7}$
$b_{Y,8}$ $b_{Y,9}$ $b_{Y,10}$ Selected Rejected $A_{X}$$A_{Y}$$X$ Selects$Y$
Selects$a_{Y}$$a_{X}$$b_{Y}$$b_{X}$ Figure 7: _Union and intersection DP
padded inputs_

## References

  * [1] G. Kellaris, G. Kollios, K. Nissim, and A. O’Neill, “Accessing data while preserving privacy,” _arXiv preprint arXiv:1706.01552_ , 2017.
  * [2] M. Ion, B. Kreuter, A. E. Nergiz, S. Patel, M. Raykova, S. Saxena, K. Seth, D. Shanahan, and M. Yung, “On deploying secure computing: Private intersection-sum-with-cardinality,” Cryptology ePrint Archive, Report 2019/723, 2019, https://ia.cr/2019/723.
  * [3] P. Buddhavarapu, A. Knox, P. Mohassel, S. Sengupta, E. Taubeneck, and V. Vlaskin, “Private matching for compute.” _IACR Cryptol. ePrint Arch._ , vol. 2020, p. 599, 2020.
  * [4] M. Movahedi, B. M. Case, J. Honaker, A. Knox, L. Li, Y. P. Li, S. Saravanan, S. Sengupta, and E. Taubeneck, “Privacy-preserving randomized controlled trials: A protocol for industry scale deployment,” _arXiv preprint_ , 2021\.
  * [5] A. Haeberlen, B. C. Pierce, and A. Narayan, “Differential privacy under fire.” in _USENIX Security Symposium_ , vol. 33, 2011.
  * [6] C. Covington, J. Honaker, and M. Shoemate, “Smartnoise: Working with unknown dataset sizes,” Notebook, 2020, https://github.com/opendp/smartnoise-samples/blob/master/analysis/unknown_dataset_size.ipynb.
  * [7] S. Kotz, T. Kozubowski, and K. Podgorski, _The Laplace Distribution and Generalizations: A Revisit with Applications to Communications, Economics, Engineering, and Finance_. Boston: Birkhäuser Basel, 2001.
  * [8] E. De Cristofaro, P. Gasti, and G. Tsudik, “Fast and private computation of cardinality of set intersection and union,” in _International Conference on Cryptology and Network Security_. Springer, 2012, pp. 218–231.
  * [9] M. Ion, B. Kreuter, A. E. Nergiz, S. Patel, M. Raykova, S. Saxena, K. Seth, D. Shanahan, and M. Yung, “On deploying secure computing: Private intersection-sum-with-cardinality,” Cryptology ePrint Archive, Report 2019/723, 2019, https://eprint.iacr.org/2019/723.
  * [10] P. Buddhavarapu, B. M. Case, L. Gore, A. Knox, P. Mohassel, S. Sengupta, E. Taubeneck, and M. Xue, “Multi-key private matching for compute,” Cryptology ePrint Archive, Report 2021/770, 2021, https://ia.cr/2021/770.
  * [11] G. Garimella, P. Mohassel, M. Rosulek, S. Sadeghian, and J. Singh, “Private set operations from oblivious switching,” Cryptology ePrint Archive, Report 2021/243, 2021, https://ia.cr/2021/243.
  * [12] P. Miao, S. Patel, M. Raykova, K. Seth, and M. Yung, “Two-sided malicious security for private intersection-sum with cardinality,” in _Annual International Cryptology Conference_. Springer, 2020, pp. 3–33.
  * [13] G. Kellaris, G. Kollios, K. Nissim, and A. O’Neill, “Generic attacks on secure outsourced databases,” in _Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security_ , 2016, pp. 1329–1340.
  * [14] P. Grubbs, M.-S. Lacharité, B. Minaud, and K. G. Paterson, “Pump up the volume: Practical database reconstruction from volume leakage on range queries,” in _Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security_ , 2018, pp. 315–331.
  * [15] Z. Gui, O. Johnson, and B. Warinschi, “Encrypted databases: New volume attacks against range queries,” in _Proceedings of the 2019 ACM SIGSAC Conference on Computer and Communications Security_ , 2019, pp. 361–378.
  * [16] D. Bogatov, G. Kellaris, G. Kollios, K. Nissim, and A. O’Neill, “$\mathcal{E}\text{psolute}$: Efficiently querying databases while providing differential privacy,” 2021.
  * [17] M. Xu, A. Papadimitriou, A. Haeberlen, and A. Feldman, “Hermetic: Privacy-preserving distributed analytics without (most) side channels,” _External Links: Link Cited by_ , 2019.
  * [18] A. Groce, P. Rindal, and M. Rosulek, “Cheaper private set intersection via differentially private leakage,” _Proceedings on Privacy Enhancing Technologies_ , vol. 2019, no. 3, 2019.
  * [19] J. Allen, B. Ding, J. Kulkarni, H. Nori, O. Ohrimenko, and S. Yekhanin, “An algorithmic framework for differentially private data analysis on trusted processors,” _Advances in Neural Information Processing Systems_ , vol. 32, pp. 13 657–13 668, 2019.
  * [20] A. Inan, M. Kantarcioglu, G. Ghinita, and E. Bertino, “Private record matching using differential privacy,” in _Proceedings of the 13th International Conference on Extending Database Technology_ , 2010, pp. 123–134.
  * [21] M. Kuzu, M. Kantarcioglu, A. Inan, E. Bertino, E. Durham, and B. Malin, “Efficient privacy-aware record integration,” in _Proceedings of the 16th International Conference on Extending Database Technology_ , 2013, pp. 167–178.
  * [22] J. Cao, F.-Y. Rao, E. Bertino, and M. Kantarcioglu, “A hybrid private record linkage scheme: Separating differentially private synopses from matching records,” in _2015 IEEE 31st International Conference on Data Engineering_. IEEE, 2015, pp. 1011–1022.
  * [23] X. He, A. Machanavajjhala, C. Flynn, and D. Srivastava, “Composing differential privacy and secure computation: A case study on scaling private record linkage,” in _Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security_ , 2017, pp. 1389–1406.
  * [24] H. Quick, “Generating poisson-distributed differentially private synthetic data,” _Journal of the Royal Statistical Society: Series A (Statistics in Society)_ , vol. 184, no. 3, pp. 1093–1108, 2021. [Online]. Available: https://rss.onlinelibrary.wiley.com/doi/abs/10.1111/rssa.12711
  * [25] H. Quick, K. Chen, and D. DeLara, “Comparison of poisson-gamma and laplace mechanisms for differential privacy,” in _2021 Workshop on Theory and Practice of Differential Privacy_ , 2021.
  * [26] H. Quick, “Improving the utility of poisson-distributed, differentially private synthetic data via prior predictive truncation with an application to cdc wonder,” _arXiv preprint arXiv:2103.03833_ , 2021.
  * [27] A. Machanavajjhala, D. Kifer, J. Abowd, J. Gehrke, and L. Vilhuber, “Privacy: Theory meets practice on the map,” in _2008 IEEE 24th international conference on data engineering_. IEEE, 2008, pp. 277–286.