Cifrado Homomórfico Total Eficiente a Partir de LWE (Estándar)

Un esquema de cifrado homomórfico total (FHE) permite a cualquier persona transformar un cifrado de un mensaje, m, en un cifrado de cualquier función (eficiente) de ese mensaje, f(m), sin conocer la clave secreta. Presentamos un esquema de FHE nivelado que se basa únicamente en la suposición de aprendizaje con errores (LWE) (estándar). (Los esquemas FHE nivelados se inicializan con un límite en la profundidad máxima de evaluación. Sin embargo, esta restricción puede eliminarse asumiendo la 'seguridad circular débil'.) Aplicando resultados conocidos sobre LWE, la seguridad de nuestro esquema se basa en la dureza en el peor de los casos de 'problemas de vectores cortos' en redes arbitrarias. Nuestra construcción mejora trabajos anteriores en dos aspectos: 1. Mostramos que el cifrado 'algo homomórfico' puede basarse en LWE, utilizando una nueva técnica de relajación. En contraste, todos los esquemas anteriores se basaron en suposiciones de complejidad relacionadas con ideales en varios anillos. 2. Nos desviamos del 'paradigma de aplastamiento' utilizado en todos los trabajos anteriores. Introducimos una nueva técnica de reducción de módulo en dimensión, que acorta los textos cifrados y reduce la complejidad de decriptación de nuestro esquema, sin introducir suposiciones adicionales. Nuestro esquema tiene textos cifrados muy cortos, y por lo tanto lo utilizamos para construir un protocolo de recuperación de información privada (PIR) basado en LWE de un solo servidor asintóticamente eficiente. La complejidad de comunicación de nuestro protocolo (en el modelo de clave pública) es k(k) +|DB| bits por consulta de un solo bit, para lograr seguridad contra adversarios de tiempo 2ᵏ (basado en los mejores ataques conocidos contra nuestras suposiciones subyacentes).