Che cosa significa "lo spazio di probabilità è sopra il lancio di monete di algoritmo M" significa?

Question

Che cosa significa "lo spazio di probabilità è sopra il lancio di monete di algoritmo M" significa?

#1 da (1 voti)

2

Nel libro The Algorithmic Foundations of Differential Privacy di Cynthia Dwork, Aaron Roth on pagina 16 (in realtà la pagina 20 nel visualizzatore pdf) dice nella parte inferiore della pagina:

Definition 2.2 (Randomized Algorithm). A randomized algorithm ℳ with domain A and discrete range B is associated with a mapping M : A → ∆(B). On input a ∈ A, the algorithm ℳ outputs ℳ(a) = b with probability (M(a))_b for each b ∈ B. The probability space is over the coin flips of the algorithm ℳ.

Che cosa significa la frase finale?

Qualcuno ha detto che gli autori potrebbero voler dire che una volta eseguita la ricetta descritta in quel paragrafo, esegui il trucco double-coin-flip plausible-deniability descritto al punto 2.3 a pagina 15. È questo che significa?

cryptography privacy

posta cheater 27.06.2016 - 17:07

fonte

1 risposta

Leggi altre domande sui tag cryptography privacy

Utilizzo di un hash al posto dei dati utente È possibile che un iPhone venga violato durante una telefonata?

score 1 · Accepted Answer

Ho contattato gli autori e sono stati molto utili. La citazione originale dice tutto:

The book is about randomized algorithms that act on data sets. You can always view these as deterministic algorithms, which take two inputs -- the data set, and also a string of random bits.

The definition of differential privacy has a probability operator, and what that remark means is that the probability is taken over the randomness of the random bit string (i.e. the internal randomness of the algorithm), holding the data set fixed.

La chiave di tutto questo è che la definizione dice: "l'algoritmo ℳ emette ... con probabilità ...". Questa è una scelta casuale, e la fonte della casualità è definita dalla frase "Lo spazio di probabilità è sopra la moneta lancia l'algoritmo ℳ".