PrivKV: Coleta de Dados Chave-Valor com Privacidade Diferencial Local

A privacidade diferencial local (LDP), onde cada usuário perturba seus dados localmente antes de enviar para um coletor de dados não confiável, é uma nova e promissora técnica para a coleta de dados distribuídos que preservam a privacidade. A vantagem da LDP é permitir que o coletor obtenha estimativas estatísticas precisas sobre dados sensíveis do usuário (por exemplo, localização e uso de aplicativos) sem acessá-los. No entanto, o trabalho existente em LDP é limitado a tipos de dados simples, como dados categóricos, numéricos e de conjuntos. Até onde sabemos, não há trabalho LDP existente em dados chave-valor, que é um modelo de dados NoSQL extremamente popular e a forma generalizada de dados de conjunto e numéricos. Neste artigo, estudamos esse problema de estimativa de frequência e média em dados chave-valor, projetando primeiro uma abordagem base chamada PrivKV dentro do mesmo paradigma "perturbação-calibração" das técnicas LDP existentes. Para abordar a baixa precisão da estimativa devido à perturbação inconsciente dos usuários, propomos então duas soluções iterativas, PrivKVM e PrivKVM+, que podem melhorar gradualmente os resultados da estimativa através de uma série de iterações. Uma estratégia de otimização é também apresentada para reduzir a latência da rede e aumentar a precisão da estimativa, introduzindo iterações virtuais no lado do coletor sem envolvimento do usuário. Verificamos a correção e a eficácia dessas soluções através de análise teórica e resultados experimentais extensivos.