Existe-t-il actuellement des recherches sur la mise en œuvre des extracteurs de hasard?

Y a-t-il eu des recherches sur la mise en œuvre de constructions d'extracteurs aléatoires?

Il semble que les preuves d'extraction utilisent Big-Oh, laissant la possibilité de grandes constantes cachées, rendant les implémentations programmatiques potentiellement irréalistes.

Un peu de contexte: je suis intéressé par l'utilisation d'extracteurs aléatoires comme source rapide (de manière probante?) De nombres aléatoires à utiliser dans les simulations de Monte Carlo. Nous (un groupe ETHZ de physique computationnelle) avons des sources biaisées à haute entropie provenant de générateurs de nombres aléatoires quantiques dont nous aimerions extraire le caractère aléatoire. Un étudiant précédent a tenté de mettre en œuvre une construction Trevisan et a rencontré des problèmes de complexité spatiale. Mis à part cet étudiant, je n'ai trouvé aucune référence à des personnes essayant d'implémenter des extracteurs.

Remarque: je suis un étudiant de premier cycle CS qui est très nouveau dans le domaine des CS théoriques et des extracteurs aléatoires.

Une grande partie de la littérature sur les extracteurs concerne la minimisation de la longueur des graines, ce qui est important pour l'application de dérandomisation. Cependant, cela peut ne pas être crucial pour le vôtre. De plus, la littérature se concentre souvent sur une erreur relativement importante (par exemple, 1/100), ce qui est bien pour la dérandomisation mais peut être problématique dans d'autres contextes, qui nécessitent une erreur exponentiellement petite.

Dans votre contexte, il peut être correct de générer une fois pour toutes une longue graine aléatoire (par exemple en lançant des pièces), puis de l'utiliser pour extraire. Dans ce cas, vous pouvez utiliser des fonctions de hachage indépendantes par paire qui ont des implémentations plutôt efficaces. J'ai écrit un article avec Shaltiel et Tromer sur cette question. Vous pouvez également utiliser des fonctions de hachage presque indépendantes, qui peuvent être plus efficaces et avoir une graine plus petite. (Je ne connais pas d'office une bonne référence pour leur mise en œuvre efficace, bien qu'il y ait eu plusieurs travaux à ce sujet.)

Si vous disposez de plusieurs sources indépendantes , vous pouvez faire mieux. L'extracteur Hadamard classique fonctionne si le taux d'entropie est supérieur à 50% (cela doit être mentionné dans les enquêtes ci-dessus). Si l'entropie est inférieure à 50%, nous avons eu une construction simple avec Impagliazzo et Wigderson . La dépendance entre le nombre de sources et l'erreur obtenue sur le taux d'entropie n'est pas idéale, mais pour vraiment le comprendre, vous devrez regarder les limites exactes données par les théorèmes de produit de somme de l'état de l'art d'aujourd'hui. (Et si vous êtes prêt à supposer un certain nombre de conjectures théoriques, vous pouvez obtenir des extracteurs encore plus efficaces.) Cette construction a été considérablement améliorée de diverses manières, dont certaines pourraient être pertinentes pour votre application.Thèse d'Anup Rao .

Tout d'abord, consultez le sujet pertinent sur Wikipédia. Deuxièmement, vous pouvez jeter un œil au document suivant:

Développements récents dans les constructions explicites d'extracteurs par Ronen Shaltiel.

Le document est rédigé sous la forme d'une enquête et peut vous aider à trouver les «développements récents».

Enfin, si tout ce que vous voulez est une séquence de bits qui "semble" aléatoire (mais pas nécessairement sécurisée cryptographiquement), vous pouvez appliquer une fonction de hachage (telle que MD5 ou SHA-1) à votre source à haute entropie, et obtenir un excellent résultat (pour les expériences physiques) en un rien de temps.

Il y a aussi un beau papier de Dodis, Gennaro et al. qui considère les primitives cryptographiques pratiques qui peuvent être utilisées pour l'extraction. Ils montrent que les fonctions de hachage ne sont pas connues pour être de bons extracteurs, mais un chiffrement par bloc en mode CBC-MAC peut l'être (avec quelques caractères fins). Ils considèrent également les constructions HMAC. L'approche est attrayante pour la mise en œuvre car vous pouvez utiliser des bibliothèques de cryptographie standard.

Pour CBC-MAC, les "petits caractères" sont grosso modo:

• Suppose que le blockcipher est une permutation pseudo-aléatoire
• Doit être saisi avec une clé vraiment aléatoire (mais pas nécessairement secrète) qui peut être réutilisée
• Si la sortie est de m bits, l'entrée doit avoir au moins 2 m bits d'entropie min.
• La longueur de bloc et la longueur de clé doivent être identiques (donc si vous utilisez AES, cela signifie que seul AES-128 fonctionne)
• La longueur d'entrée est limitée mais la limite est élevée

Pour le cas du générateur pseudo-aléatoire cryptographique, vous pouvez également consulter HKDF . Dans l' article, ils discutent conceptuellement et pratiquement des extracteurs de hasard et donnent de belles références.

En guise de remarque pour générer de l'aléatoire pour Monte Carlo, il y a bien sûr HAVEGE . Si sa vitesse de bits et sa "prouvabilité" sont suffisantes, vous éviterez peut-être d'avoir à fouiner avec les générateurs quantiques.