On the Limitations of Black-Box Constructions in Cryptography

Cryptography is the science of secure communication. Originating as an esoteric discipline based on heuristics, it underwent a mayor paradigm shift in the past century. Modern cryptographic schemes are indeed formally proven secure through reductions. Such approach allows arguing that security of a scheme holds as long as its base primitives are secure. A popular approach to achieve this is through black-box constructions. These informally rely on the underlying primitives only through its intended interface, therefore not utilizing any additional structure that only concrete instantiations may enjoy. Being black-box is a desirable feature for many constructions. As a design principle, it allows for greater modularity and a higher level of abstraction. For concrete efficiency and security, it means no expensive non-black techniques were deployed. The latter indeed often significantly affects performances, as in the case of garbling or indistinguishability obfuscation, or requires strong assumptions, as for SNARKS. Although desirable, a large body of research starting from Impagliazzo and Rudich's results (STOC `89), has shown that in some cases black-box constructions are not possible, or suffer limitations. In this thesis we push forward our understanding of the limitation of black-box constructions. We do so by providing new negative results and lower bounds for several primitives from standard cryptographic objects. First, we focus on primitives that can be realized from a cryptographic prime order group, i.e. where the discrete logarithm problem is hard. Such groups are the cornerstone of modern public key cryptography and many primitives are known to exist based on them. In the first three chapters, we study whether digital signatures, vector commitments, and non-interactive zero-knowledge (NIZK) could be realized from a black-box group. We find that in this setting, signatures only exist for polynomially small message spaces, vector commitments cannot be succinct, and NIZK do not exist for many useful languages. Second, we turn our attention to cryptographic group actions, discussed in the fourth chapter. These represent one of the few post-quantum sources of hard problems currently available. A problem of many threshold schemes in this setting is that computing the action of a secret-shared group element requires high round complexity. Specifically round-robin protocols, where parties interact sequentially, are currently the only black-box option. We show that such limitation is inherent. Specifically, any protocol (black-box in the underlying group action) computing the action of a shared secret, requires a number of rounds linear in the privacy threshold. Third, in the fifth chapter we investigate black-box realizations of Anamorphic Encryption (AE). AE is a new encryption paradigm, guaranteeing privacy even against a dictator who can enforce the usage of an encryption scheme of their choice and observe all user's secret keys. AE is defined with respect to a specific public key encryption (PKE) scheme, providing an alternative, indistinguishable, encryption mode. Generic constructions that are black-box with respect to the underlying PKE, and thus apply to any PKE, are known. However, these only allow communicating few bits per ciphertext, specifically logarithmically many in the security parameter. We prove this to be the best any black-box construction can achieve. Furthermore, we show how black-box constructions cannot satisfy stronger security notions, such as Fully Asymmetric AE, recently introduced by Catalano et al. (Eurocrypt `24). RESUMEN La criptografía es la ciencia de la comunicación segura. Originada como una disciplina esotérica basada en heurísticas, experimentó un cambio de paradigma significativo en el último siglo. Los esquemas criptográficos modernos son, de hecho, formalmente demostrados como seguros mediante reducciones. Este enfoque permite argumentar que la seguridad de un esquema se mantiene siempre que sus primitivas base sean seguras. Un enfoque popular para lograr esto es a través de construcciones "black-box", que informalmente dependen de las primitivas subyacentes solo a través de su interfaz prevista y por tanto no utilizan propiedades matemáticas adicionales de implementacións concretas de estas primitivas. Ser black-box es una característica deseable. Como principio de diseño, permite una mayor modularidad y un nivel más alto de abstracción. Para la eficiencia y seguridad concretas, significa que no se han implementado técnicas costosas que no son black-box. Estas últimas a menudo afectan al rendimiento, como en el caso de "garbling schemes" o "indistinguishability obfuscation", o requieren suposiciones fuertes, como en el caso de los SNARKS. Aunque deseables, una gran cantidad de investigaciones, comenzando con resultados de Impagliazzo y Rudich, han mostrado que en algunos casos las construcciones black-box no son posibles o presentan limitaciones. En esta tesis, avanzamos en nuestra comprensión de las limitaciones de las construcciones black-box. Lo hacemos proporcionando nuevos resultados negativos y límites inferiores para varias primitivas de objetos criptográficos estándar. Primero, nos centramos en primitivas que pueden realizarse a partir de un grupo criptográfico de orden primo, es decir, donde el problema del logaritmo discreto es difícil. Dichos grupos son la piedra angular de la criptografía de clave pública moderna, y muchas construcciones se basan en ellos. En los 3 primeros capítulos, estudiamos si las firmas digitales, los vector commitment y pruebas de conocimiento cero no interactivo (NIZK) podrían realizarse a partir de un grupo black-box. Encontramos que, en este contexto, las firmas solo existen para un espacio de mensajes polinomialmente pequeño, los vector commitments no pueden ser sucintos y las NIZK no existen para muchos lenguajes útiles. En el cuarto capítulo dirigimos nuestra atención a las acciones de grupo criptográficas. Estas representan una de las pocas fuentes de problemas difíciles en el contexto post-cuántico actualmente disponibles. Un problema de muchos esquemas de umbral en este contexto es que calcular la acción de un elemento de grupo compartido de forma secreta requiere una alta complejidad de rondas. De hecho, los protocolos de ronda en cadena, donde las partes interactúan secuencialmente, son actualmente la única opción black-box. Mostramos que tal limitación es inherente. En particular, cualquier protocolo black-box en la acción del grupo que calcule la acción de un secreto compartido, requiere un número de rondas lineal en el umbral de privacidad. En el quinto capítulo investigamos las realizaciones black-box de Cifrado Anamórfico (AE). AE es un nuevo paradigma de cifrado que garantiza privacidad incluso contra un dictador que puede imponer el uso de un esquema de cifrado de su elección y observar todas las claves secretas de los usuarios. AE se define con respecto a un esquema específico de cifrado de clave pública (PKE), proporcionando un modo de cifrado alternativo e indistinguible. Se conocen construcciones genéricas que son black-box con respecto al PKE subyacente, y que por lo tanto se aplican a cualquier PKE. Sin embargo, estas solo permiten comunicar un número limitado de bits por cada texto cifrado. Demostramos que este es el mejor rendimiento que una construcción black-box puede lograr. Además, mostramos cómo las construcciones black-box no pueden satisfacer nociones de seguridad más fuertes, como la "Fully Asymmetric AE", introducida recientemente por Catalano et al.