Funções pseudorandom constrangidas seguras adaptativamente no modelo padrão

Resumo

Funções pseudorandom constrangidas (CPRFs) permitem aprender chaves PRF "constrangidas" que podem avaliar a PRF em um subconjunto do espaço de entrada, ou com base em algum predicado. Introduzidas pela primeira vez por Boneh e Waters [AC'13], Kiayias et al. [CCS'13] e Boyle et al. [PKC'14], elas se mostraram uma primitiva criptográfica útil com muitas aplicações. Essas aplicações frequentemente requerem que as CPRFs sejam seguras adaptativamente, o que permite que o adversário aprenda valores PRF e chaves constrangidas em uma ordem arbitrária. No entanto, não há uma construção conhecida de CPRFs seguras adaptativamente com base em uma suposição padrão no modelo padrão para qualquer classe não trivial de predicados. Além disso, mesmo se nos basearmos em ferramentas fortes como ofuscação indistinguível (IO), a construção de CPRFs seguras adaptativamente no modelo padrão só suporta a classe limitada de predicados NC1. Neste trabalho, desenvolvemos novas CPRFs seguras adaptativamente para vários predicados a partir de diferentes tipos de suposições no modelo padrão. Nossos resultados são resumidos abaixo. • Construímos CPRFs seguras adaptativamente e O(1)-resistentes à colusão para predicados em forma normal conjuntiva (t-CNF) a partir de funções de sentido único (OWFs), onde t é uma constante. Aqui, O(1)-resistência à colusão significa que podemos permitir que o adversário obtenha um número constante de chaves constrangidas. Observe que t-CNF inclui predicados de fixação de bits como um caso especial. • Construímos CPRFs seguras adaptativamente e de chave única para predicados de produto interno a partir da suposição de aprendizado com erros (LWE). Aqui, segurança de chave única significa que apenas permitimos que o adversário aprenda uma chave constrangida. Observe que os predicados de produto interno incluem predicados t-CNF para uma constante t como um caso especial. Portanto, essa construção suporta uma classe mais expressiva de predicados do que a suportada pela primeira construção, embora perca a resistência à colusão e dependa de uma suposição mais forte. • Construímos CPRFs seguras adaptativamente e O(1)-resistentes à colusão para todos os circuitos a partir da suposição LWE e ofuscação indistinguível (IO). As primeiras e segundas construções são as primeiras CPRFs para qualquer predicado não trivial a alcançar segurança adaptativa fora do modelo de oráculo aleatório ou dependendo de suposições criptográficas fortes. Além disso, a primeira construção também é a primeira a alcançar qualquer noção de privacidade de chave única nesse cenário. Além disso, provamos que as primeiras e segundas construções satisfazem a privacidade de chave única fraca, que significa aproximadamente que uma chave constrangida não revela a restrição correspondente. A terceira construção é uma melhoria sobre as CPRFs seguras adaptativamente anteriores para predicados menos expressivos com base em IO no modelo padrão.