Houve pesquisas para implementar construções de extratores aleatórios?
Parece que as provas do extrator fazem uso do Big-Oh, deixando a possibilidade de grandes constantes ocultas, tornando as implementações programáticas potencialmente irrealistas.
Algum contexto: estou interessado em usar extratores de aleatoriedade como uma fonte rápida de (provavelmente?) Números aleatórios para uso em simulações de Monte Carlo. Nós (um grupo de Física Computacional da ETHZ) enviesamos fontes de alta entropia de geradores de números aleatórios quânticos dos quais gostaríamos de extrair a aleatoriedade. Um aluno anterior tentou implementar uma construção Trevisana e teve problemas de complexidade espacial. Além desse aluno, não encontrei nenhuma referência a pessoas tentando implementar extratores.
Nota: Sou um graduado em CS muito novo na área de Extratores de CS teórico e aleatoriedade.
fonte
Respostas:
Grande parte da literatura sobre extratores trata da minimização do comprimento das sementes, o que é importante para a aplicação da des randomização. No entanto, pode não ser crucial para o seu. Além disso, muitas vezes a literatura concentra-se em erros relativamente grandes (por exemplo, 1/100), o que é bom para des aleatorização, mas pode ser problemático em outras configurações, que exigem um erro exponencialmente pequeno.
Na sua configuração, pode ser bom gerar de uma vez por todas uma semente aleatória longa (por exemplo, jogando moedas) e depois usá-la para extrair. Nesse caso, você pode usar funções hash independentes em pares que possuem implementações bastante eficientes. Escrevi um artigo com Shaltiel e Tromer sobre esse assunto. Você também pode usar funções hash quase independentes, que podem ser mais eficientes e ter sementes menores. (Não conheça de imediato uma boa referência para sua implementação eficiente, embora tenha havido vários trabalhos sobre isso.)
Se você tiver várias fontes independentes , poderá fazer coisas melhores. O extrator Hadamard clássico funciona se a taxa de entropia for maior que 50% (isso deve ser mencionado nas pesquisas acima). Se a entropia for menor que 50%, teríamos uma construção simples com Impagliazzo e Wigderson . A dependência entre o número de fontes e o erro obtido na taxa de entropia não é ideal, embora, para realmente entendê-lo, você precise examinar os limites exatos dados pelos atuais teoremas do produto de soma de ponta. (E se você estiver disposto a assumir certas conjecturas teóricas dos números, poderá obter extratores ainda mais eficientes.) Essa construção foi bastante aprimorada de várias maneiras, algumas das quais podem ser relevantes para a sua aplicação.Tese de Anup Rao .
fonte
Primeiro de tudo, consulte o tópico relevante na Wikipedia. Em segundo lugar, você pode dar uma olhada no seguinte artigo:
Desenvolvimentos recentes em construções explícitas de extratores por Ronen Shaltiel.
O artigo foi escrito na forma de uma pesquisa e pode ajudá-lo a encontrar os "desenvolvimentos recentes".
Finalmente, se tudo o que você deseja é uma sequência de bits que pareça aleatória (mas não necessariamente segura criptograficamente), você pode aplicar uma função hash (como MD5 ou SHA-1) à sua fonte de alta entropia e obter uma excelente resultado (para experimentos físicos) em quase nenhum momento.
fonte
Há também um belo artigo de Dodis, Gennaro, et al. que considera primitivas criptográficas práticas que podem ser usadas para extração. Eles mostram que as funções de hash não são boas extratoras, no entanto, pode ser uma cifra de bloco no modo CBC-MAC (com algumas letras pequenas). Eles também consideram construções HMAC. A abordagem é atraente para implementação, pois você pode usar bibliotecas de criptografia padrão.
Para CBC-MAC, a "impressão fina" é aproximadamente:
fonte
Para o caso criptográfico do gerador pseudo-aleatório, você também pode procurar no HKDF . No artigo, eles discutem os extratores de aleatoriedade conceitualmente e praticamente e fornecem boas referências.
Como uma nota lateral para gerar aleatoriedade para Monte Carlo, é claro que existe o HAVEGE . Se a velocidade de bits e a "provabilidade" forem suficientes, você poderá evitar ter que mexer nos geradores quânticos.
fonte