Informations pratiques
Séminaire habituellement le jeudi à 11h, Bâtiment Descartes, 3ème étage.
Prochain Séminaire:
Jeudi 8 avril 2021 à 11h00 via Zoom
LPN a densité variable, et fonctions faiblement
pseudoaléatoires dans des classes de complexité basses
Variable-density LPN and low-complexity weak pseudorandom functions
Les fonctions faiblement pseudoaléatoires (WPRFs) sont des fonctions F_K indistinguables d’une fonction totalement aléatoire à partir de paires (x, F_K(x)) pour des x aléatoires. Ces fonctions ont diverses applications en cryptographie symétrique - elles permettent par exemple de construire des MACs, ou des systèmes de chiffrement à flot - et l’existence de telles fonctions dans des classes de complexité basses est une question fondamentale en théorie de l’apprentissage. Dans ce papier, nous étudions l’existence de WPRFs dans une classe de complexité particulièrement faible : les circuits booléens de taille polynomiale et de profondeur 2, avec une rangée de portes ET (de degré entrant arbitraire), et une unique porte XOR avant la sortie. Le choix de cette classe particulière est aussi motivé par une application surprenante au domaine du calcul sécurisé : nous démontrons que l’existence d’une WPRF dans cette classe permet d’améliorer radicalement l’efficacité de la phase de précalcul d’essentiellement tous les protocoles de calcul sécurisé modernes.
Nous introduisons une nouvelle variante de l’hypothèse LPN (qui conjecture la difficulté de décoder des mots de codes bruités dans un code linéaire aléatoire), où la matrice génératrice du code et le vecteur de bruit ont tous deux une densité variable. Nous montrons que sous cette nouvelle hypothèse, il est possible de construire une WPRF calculable avec une rangée de ET, et un unique XOR. Nous étudions ensuite la sécurité de cette nouvelle construction, sous l’angle d’une variante de LPN, et sous l’angle des fonctions booléennes. Nous démontrons que de nombreuses classes d’attaques (attaques linéaires, attaques algébriques, attaques par requêtes statistiques, cryptanalyse linéaire, et attaques AC0) ne peuvent pas asymptotiquement invalider cette hypothèse.
Basé sur des travaux joints avec Elette Boyle, Niv Gilboa, Yuval Ishai, Lisa Kohl, et Peter Scholl, présentés à FOCS 2021.