Algebraic frameworks for pseudorandom functions

Caractérisations algébriques pour les fonctions pseudo-aléatoires

Alain Passelègue (1, 2)

1 DI-ENS - Département d'informatique - ENS Paris
2 CASCADE - Construction and Analysis of Systems for Confidentiality and Authenticity of Data and Entities

In this thesis, we study the algebraic structure underlying number-theoretic pseudorandom functions. Specifically, we define an algebraic framework that translates the pseudorandomness of a particular form of functions into a simple algebraic property. The resulting generic framework encompasses most of existing constructions and naturally extends to related primitives, such as related-key secure, aggregate, and multilinear pseudorandom functions. This framework holds under a family of MDDH assumptions, that contains especially different classical assumptions, such as DDH, DLin, or k-Lin. Therefore, setting accordingly the parameters in the constructions, our framework can be used to construct secure pseudorandom functions (or related primitives) whose security holds under these assumptions. Finally, we also study more specifically the case of related-key security. On the one hand, we propose a fix and some extensions to the Bellare-Cash framework and then build pseudorandom functions secure against larger classes of attacks. On the other hand, we construct the first pseudorandom function provably secure against XOR attacks. The latter construction relies on the existence of a weak form of multilinear maps.

Dans cette thèse, nous étudions la structure algébrique sous-jacente aux fonctions pseudo-aléatoires basées sur la théorie des nombres. Précisément, nous montrons que le caractère pseudo-aléatoire de fonctions d’une forme particulière est équivalent au fait que ces fonctions vérifient une propriété algébrique simple. Cette caractérisation algébrique s’applique à la plupart des constructions connues et s’étend naturellement aux généralisations des fonctions pseudo-aléatoires, par exemple aux fonctions pseudo-aléatoires sûres contre les attaques par clés liées, multilinéaires ou supportant l’agrégation. Cette caractérisation repose sur une famille d’hypothèses MDDH, qui contient en particulier différentes hypothèses classiques, comme DDH, DLin, ou k-Lin. Ainsi, en choisissant les paramètres des constructions selon, ce résultat permet de construire des fonctions pseudo-aléatoires (ou leurs généralisations) prouvées sûres sous ces différentes hypothèses. Enfin, nous étudions également plus précisément le cas de la sécurité contre les attaques par clés liées. D’une part, nous corrigeons et étendons la transformation proposée par Bellare et Cash pour ensuite construire de nouvelles fonctions pseudo-aléatoires sûres contre des attaques par clés liées plus puissantes. D’autre part, nous construisons la première fonction pseudo-aléatoire prouvée sûre contre des attaques par XOR. Cette construction repose sur l’existence d’une forme faible d’applications multilinéaires.

Mots clés: Cryptography; Pseudorandom functions; Provable security; Related-key security; Algebraic constructions; Computational assumptions

Mots clés: Cryptographie; Fonctions pseudo-aléatoires; Sécurité prouvée; Sécurité par clés liées; Constructions algébriques; Hypothèses calculatoires

Domaines: Cryptographie et sécurité [cs.CR]

Alain Passelègue. Algebraic frameworks for pseudorandom functions. Cryptography and Security [cs.CR]. Université Paris sciences et lettres, 2016. English. ⟨NNT : 2016PSLEE059⟩. ⟨tel-01422093v2⟩