Funciones pseudorandom restringidas seguras de forma adaptativa en el modelo estándar

Resumen

Las funciones pseudorandom restringidas (CPRFs) permiten aprender claves de PRF "restringidas" que pueden evaluar la PRF en un subconjunto del espacio de entrada, o basadas en algún predicado. Introducidas por primera vez por Boneh y Waters [AC’13], Kiayias et al. [CCS’13] y Boyle et al. [PKC’14], han demostrado ser un primitivo criptográfico útil con muchas aplicaciones. Estas aplicaciones a menudo requieren que las CPRFs sean seguras de forma adaptativa, lo que permite al adversario aprender valores de PRF y claves restringidas en un orden arbitrario. Sin embargo, no se conoce ninguna construcción de CPRFs seguras de forma adaptativa basada en una suposición estándar en el modelo estándar para cualquier clase no trivial de predicados. Además, incluso si nos basamos en herramientas fuertes como la ofuscamiento indistinguible (IO), la construcción de CPRFs seguras de forma adaptativa en el modelo estándar solo admite la clase limitada de predicados NC1. En este trabajo, desarrollamos nuevas CPRFs seguras de forma adaptativa para varios predicados a partir de diferentes tipos de suposiciones en el modelo estándar. A continuación, se resumen nuestros resultados. • Construimos CPRFs seguras de forma adaptativa y resistentes a la colusión O(1) para predicados en forma normal conjuntiva (t-CNF) a partir de funciones de una vía (OWFs) donde t es una constante. Aquí, la resistencia a la colusión O(1) significa que podemos permitir que el adversario obtenga un número constante de claves restringidas. Tenga en cuenta que t-CNF incluye predicados de fijación de bits como un caso especial. • Construimos CPRFs seguras de forma adaptativa y de una sola clave para predicados de producto interior a partir de la suposición de aprendizaje con errores (LWE). Aquí, la seguridad de una sola clave significa que solo permitimos que el adversario aprenda una clave restringida. Tenga en cuenta que los predicados de producto interior incluyen predicados t-CNF para una constante t como un caso especial. Por lo tanto, esta construcción admite una clase más expresiva de predicados que la admitida por la primera construcción, aunque pierde la resistencia a la colusión y se basa en una suposición más fuerte. • Construimos CPRFs seguras de forma adaptativa y resistentes a la colusión O(1) para todos los circuitos a partir de la suposición LWE y la ofuscamiento indistinguible (IO). Las primeras y segundas construcciones son las primeras CPRFs para cualquier predicado no trivial que logren la seguridad adaptativa fuera del modelo de oráculo aleatorio o que se basen en suposiciones criptográficas fuertes. Además, la primera construcción también es la primera en lograr algún concepto de resistencia a la colusión en este contexto. Además, demostramos que las primeras y segundas construcciones satisfacen la privacidad de 1 clave débil, que roughly significa que una clave restringida no revela la restricción correspondiente. La tercera construcción es una mejora sobre las CPRFs seguras de forma adaptativa anteriores para predicados menos expresivos basados en IO en el modelo estándar.