<jupyter_start><jupyter_text>Bounds on Privacy Amplification by ShufflingBased on **Balle, Bell, Gascón, and Nissim, *The Privacy Blanket of the Shuffle Model*, CRYPTO 2019** This notebook illustrates the use of `amplification_bounds.py` to compute privacy bounds obtained from amplification by shuffling. We refer to the paper for details on how these bounds are obtained. The present implementation was used to produce the plots in the paper.  MechanismsMost of the bounds in `amplification_bounds.py` use properties of specific mechanisms (ie. local randomizers). The classes in `mechanisms.py` implement the calculation of these properties for well-known mechanisms.<jupyter_code>from shuffleddp.mechanisms import *

# Bounds can be obtained for generic mechanisms satisfying pure local DP
generic = LDPMechanism()
# But bounds are usually better if they incorporate information about the specific randomizer
laplace = LaplaceMechanism()
# By default Randomized Response is over a set with two elements
rr = RRMechanism()
# But the class also accepts a paratemeter 'k' to determine the size of the alphabet
rrk = RRMechanism(k=100)

mechanisms = [generic, laplace, rr, rrk]
# By default all mechanisms are initialized to be 1-LDP
print(generic.get_eps0())
# This can be modified at construction or by calling set_eps0
eps0 = 4
for m in mechanisms:
    m.set_eps0(eps0)
print(generic.get_eps0())
# By giving a target epsilon ('eps') after shuffling we can compute properties
# of the privacy amplification random variable for each mechanism.
# These properties are used in the amplification bounds.
eps = 0.25
{m.get_name(): (m.get_gamma(), m.get_max_l(eps), m.get_range_l(eps), m.get_var_l(eps)) for m in mechanisms}<jupyter_output><empty_output><jupyter_text>BoundsSeveral bounds are implements in `amplification_bounds.py`:1. The closed-form bound of Erlingsson et al. [SODA'19]2. A numeric bound based on Hoeffding's inequality3. A numeric bound based on Bennett's inequality<jupyter_code>from shuffleddp.amplification_bounds import *

# This bound does not use infomation about the underlying mechanism
erlingsson = Erlingsson()
all_bounds = [erlingsson]

# The other two bounds can use a 'Generic' mechanism or a specific mechanism
bound_types = [Hoeffding, BennettExact]
for m in mechanisms:
    for B in bound_types:
        all_bounds.append(B(m))

# We can fix an eps0-LDP guarantee for a mechanism and shuffle n copies of it
n = 5000
eps0 = 0.4

# Then we can get a delta parameter for a target epsilon
print(erlingsson.get_delta(0.15, eps0, n))

# Numeric bounds admit a larger range of parameters than the closed-form bound
eps = 0.005
{b.get_name(): b.get_delta(eps, eps0, n) for b in all_bounds}
# Bounds also be used to get an epsilon for a fixed delta
delta = 1e-6
{b.get_name(): b.get_eps(eps0, n, delta) for b in all_bounds}
# Bounds can also be used for calibrating the eps0 parameter of a mechanism
# to achieve a target (eps,delta)-DP guarantee after shuffling
{b.get_name(): b.get_eps0(eps, n, delta) for b in all_bounds}<jupyter_output><empty_output><jupyter_text>PlotsIt is easier to compare the different bounds by plotting different parameters.<jupyter_code>import matplotlib.pyplot as plt
%matplotlib inline

def plot_panel(f, xs, bounds, with_mech=True, debug=False):
    fig = plt.figure()
    for b in bounds:
        ys = list()
        for x in xs:
            if debug:
                print('{}: {}'.format(b.get_name(), x))
            ys.append(f(b, x))
        if with_mech:
            plt.plot(xs, ys, label=b.get_name())
        else:
            plt.plot(xs, ys, label=b.get_name(with_mech=False))
    plt.legend()
# How fast does eps decrease as we increase n?

eps0 = 0.5
delta = 1e-6
ns = np.geomspace(1000, 1000000, num=100, dtype=int)

def eps(bound, n):
    return bound.get_eps(eps0, n, delta)

bounds = [Erlingsson(),
          Hoeffding(LDPMechanism()),
          BennettExact(LDPMechanism())]

plot_panel(eps, ns, bounds, with_mech=False)
plt.xlabel('$n$')
plt.ylabel('$\\varepsilon$')
plt.title('Generic, $\\varepsilon_0 = {:.1f}, \\delta = 10^{}$'.format(eps0, '{-%d}' % np.log10(1/delta)))
plt.xscale('log')
# How large can we set eps0 as the number of users increase?

eps = 0.1
delta = 1e-6
ns = np.geomspace(100, 100000, num=100, dtype=int)

def eps0(bound, n):
    return bound.get_eps0(eps, n, delta)

bounds = [Erlingsson(),
          Hoeffding(LDPMechanism()),
          Hoeffding(RRMechanism(k=2)),
          Hoeffding(RRMechanism(k=100)),
          Hoeffding(LaplaceMechanism())]

plot_panel(eps0, ns, bounds)
plt.xlabel('$n$')
plt.ylabel('$\\varepsilon_0$')
plt.title('$\\varepsilon = {:.1f}, \\delta = 10^{}$'.format(eps, '{-%d}' % np.log10(1/delta)))
plt.xscale('log')
# How much better is the Bennett bound vs. the Hoeffding bound?

eps = 0.1
delta = 1e-6
ns = np.geomspace(100, 100000, num=100, dtype=int)

def eps0(bound, n):
    return bound.get_eps0(eps, n, delta)

mechanisms = [RRMechanism(),
              RRMechanism(k=100),
              LaplaceMechanism()]
Bounds = [Hoeffding,
          BennettExact]
bounds = []
for m in mechanisms:
    for B in Bounds:
        bounds.append(B(m))

plot_panel(eps0, ns, bounds, with_mech=True)
plt.xlabel('$n$')
plt.ylabel('$\\varepsilon_0$')
plt.title('$\\varepsilon = {:.1f}, \\delta = 10^{}$'.format(eps, '{-%d}' % np.log10(1/delta)))
plt.xscale('log')
# What if k and delta depend on n?

eps = 0.1
ns = np.geomspace(100, 100000, num=50, dtype=int)

def eps0(bound, n):
    bound.mechanism.set_k(int(n**(1/3)))
    return bound.get_eps0(eps, n, 1.0/n**2)

bounds = [Hoeffding(RRMechanism()),
          BennettExact(RRMechanism())]

plot_panel(eps0, ns, bounds, with_mech=False)
plt.xlabel('$n$')
plt.ylabel('$\\varepsilon_0$')
plt.title('$RR_k, \\varepsilon = {}, \\delta = n^{}, k = n^{}$'.format(eps, '{-2}', '{1/3}'))
plt.xscale('log')<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.12635869565217392, 'fraction_numerical': 0.026834239130434784, 'mean_word_length': 4.216120460584588, 'pattern_counts': {'":': 0, '<': 13, '<?xml version=': 0, '>': 13, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '3', 'dir': 'jupyter-structured-clean-dedup', 'id': '490366', 'license': 'Apache-2.0', 'n_tokens_mistral': 2146, 'n_tokens_neox': 2008, 'n_words': 634, 'path': 'Bounds on Privacy Amplification by Shuffling.ipynb', 'repo_name': 'BorjaBalle/amplification-by-shuffling', 'size': '5888'}