Extracteurs non-malleables à deux sources et affines pour une faible entropie

Les extracteurs non-malleables sont des généralisations et des renforcements des extracteurs de hasard standard, qui sont résilients à la manipulation adversariale. De tels extracteurs ont de larges applications en cryptographie et dans la construction explicite d'extracteurs. Dans les modèles bien étudiés des extracteurs non-malleables à deux sources et affines, les meilleures constructions précédentes ne fonctionnent que pour une taux d'entropie >2/3 et 1- respectivement par Li (FOCS' 23). Nous présentons des constructions explicites d'extracteurs non-malleables à deux sources et affines qui égalent les constructions à la pointe de la technologie des extracteurs standards pour une faible entropie. Nos résultats principaux incluent des extracteurs non-malleables à deux sources et affines (sur F₂) pour des sources sur n bits avec une min-entropie k C n et une erreur polynomialement faible, correspondant aux paramètres des extracteurs standards proposés par Chattopadhyay et Zuckerman (STOC' 16, Annals of Mathematics' 19) et Li (FOCS' 16), ainsi que ceux avec min-entropie k = O (n) et erreur constante, correspondant aux paramètres des extracteurs standards par Li (FOCS' 23). Nos constructions améliorent significativement les résultats précédents, et les paramètres (exigence d'entropie et erreur) sont les meilleurs possibles sans d'abord améliorer les constructions d'extracteurs standards. De plus, nos extracteurs non-malleables affines améliorés fournissent de fortes bornes inférieures pour un certain type de programmes de branches linéaires à lecture unique, récemment introduits par Gryaznov, Pudlák et Talebanfard (CCC' 22) comme une généralisation de plusieurs modèles computationnels bien étudiés. Ces bornes correspondent aux meilleurs résultats connus en moyenne concernant la dureté donnés par Chattopadhyay et Liao (CCC' 23) et Li (FOCS' 23), où les bornes inférieures de taille des programmes de branches sont proches de l'optimal, mais les fonctions explicites que nous utilisons ici sont différentes. \ Nos résultats suggèrent également une connexion peut-être plus profonde entre les extracteurs non-malleables et les extracteurs standards.