Evaluación selectiva de funciones privadas con aplicaciones a estadísticas privadas

Motivados por la aplicación del análisis estadístico privado de grandes bases de datos, consideramos el problema de la evaluación selectiva de funciones privadas (SPFE). En este problema, un cliente interactúa con uno o más servidores que tienen copias de una base de datos z = zt,. . . , z, para calcular f (z~t,. . . , z~, , , ), para alguna función f e índices i = it,. . . , i, ~ elegidos por el cliente. Idealmente, el cliente no debe aprender nada más sobre la base de datos que f (zit,. . . , zi, , ~), y los servidores no deben aprender nada. Las soluciones genéricas para este problema, basadas en técnicas estándar para la evaluación segura de funciones, incurren en una complejidad de comunicación que es al menos lineal en n, haciéndolas prohibitivas para grandes bases de datos incluso cuando f es relativamente simple y m es pequeño. Presentamos varios enfoques para construir protocolos de evaluación de funciones privadas con comunicación sublineal, tanto para el problema general como para casos especiales de interés. Nuestras soluciones no solo ofrecen una complejidad de comunicación sublineal, sino que también son prácticas en muchos escenarios.