Central (epsilon, delta)-DP guarantee obtained by shuffling n reports,
each produced by an epsilon0-locally-differentially-private randomiser.
Erlingsson et al., Theorem 7: for any integer n > 1 and
epsilon0, delta > 0 the shuffled mechanism satisfies
(epsilon, delta)-DP in the central model with
epsilon <= e1 sqrt(2 n log(1/delta)) + n e1 (exp(e1) - 1) for
e1 = 2 exp(2 epsilon0) (exp(epsilon0) - 1) / n. In particular,
for epsilon0 <= log(n/4)/3,
\(epsilon <= exp(2 epsilon0) (exp(epsilon0) - 1) sqrt(8 log(1/delta)/n)
+ 6 exp(4 epsilon0) (exp(epsilon0) - 1)^2 / n\), and for any
n >= 1000, 0 < epsilon0 < 1/2 and 0 < delta < 1/100
the simple form epsilon <= 12 epsilon0 sqrt(log(1/delta)/n), which
is the sqrt(n) amplification the paper advertises.
Value
List with estimate (general bound), epsilon,
epsilon_general, epsilon_refined, epsilon_simple,
epsilon1, epsilon0, delta, n,
log_inv_delta, amplification_factor,
refined_valid, simple_valid, amplifies,
method.
Details
All three are returned; estimate is the general bound, the only
one whose side conditions always hold. simple_valid and
refined_valid say whether each specialised form applies. For
epsilon0 > log(n/2)/3 the bound exceeds epsilon0 and there is no
amplification at all; amplifies flags that case.
Equations read from a rendered image of p. 11 of arXiv:1811.12469v2: the text layer drops the square-root signs.
References
Erlingsson, U., Feldman, V., Mironov, I., Raghunathan, A., Talwar, K. & Thakurta, A. (2019). Amplification by shuffling: from local to central differential privacy via anonymity. Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2468-2479, Theorem 7. doi:10.1137/1.9781611975482.151
Examples
Shfflm(epsilon0 = 5L, n = 5L, delta = 0.5)
#> $estimate
#> [1] Inf
#>
#> $epsilon
#> [1] Inf
#>
#> $epsilon_general
#> [1] Inf
#>
#> $epsilon_refined
#> [1] 1.265154e+13
#>
#> $epsilon_simple
#> [1] 22.33978
#>
#> $epsilon1
#> [1] 1298796
#>
#> $epsilon0
#> [1] 5
#>
#> $delta
#> [1] 0.5
#>
#> $n
#> [1] 5
#>
#> $log_inv_delta
#> [1] 0.6931472
#>
#> $amplification_factor
#> [1] 0
#>
#> $refined_valid
#> [1] 0
#>
#> $simple_valid
#> [1] 0
#>
#> $amplifies
#> [1] 0
#>
#> $method
#> [1] "Privacy amplification by shuffling (Erlingsson et al. 2019, Thm 7)"
#>
#> attr(,"class")
#> [1] "morie_rich_result" "list"