O Preço da Privacidade Diferencial sob Observação Contínua

Estudamos a precisão de mecanismos de privacidade diferencial no modelo de liberação contínua. Um mecanismo de liberação contínua recebe um conjunto de dados sensíveis como um fluxo de T entradas e produz, após receber cada entrada, uma saída precisa sobre as entradas obtidas. Em contraste, um algoritmo de lote recebe os dados como um único lote e produz uma única saída. Fornecemos os primeiros limites inferiores fortes sobre o erro dos mecanismos de liberação contínua. Em particular, para dois problemas fundamentais que são amplamente estudados e usados no modelo de lote, mostramos que o erro no pior caso de cada algoritmo de liberação contínua é Ω (T^1/3) vezes maior do que o do melhor algoritmo de lote. Trabalhos anteriores mostram apenas uma lacuna polilogarítmica (em T) entre o erro no pior caso alcançável nesses dois modelos; além disso, para muitos problemas, incluindo a soma de atributos binários, a lacuna polilogarítmica é apertada (Dwork et al., 2010; Chan et al., 2010). Nossos resultados mostram que problemas intimamente relacionados à soma -- especificamente, aqueles que requerem selecionar o maior de um conjunto de somas -- são fundamentalmente mais difíceis no modelo de liberação contínua do que no modelo de lote. Nossos limites inferiores assumem apenas que a privacidade se mantém para fluxos fixos com antecedência (o cenário "não adaptativo"). No entanto, fornecemos limites superiores correspondentes que se mantêm em um modelo onde a privacidade é exigida mesmo para fluxos selecionados adaptativamente. Este modelo pode ser de interesse independente.