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.

L’événement aura lieu en ligne via Zoom.

https://uvsq-fr.zoom.us/j/91963933158?pwd=MnlRVHRGTTQwOEdVUEdJMFZoa1pRQT09