Aleatoriedade extractor - Randomness extractor

Um extractor de aleatoriedade , muitas vezes simplesmente chamado um "extractor", é uma função, que está sendo aplicada a saída a partir de um fracamente aleatório entropia fonte, em conjunto com uma pequena semente, uniformemente aleatório, gera um altamente aleatória de saída que aparece independente a partir da fonte e uniformemente distribuída . Exemplos de fontes aleatórias fracamente incluem decaimento radioactivo ou de ruído térmico ; a única restrição à possíveis fontes é que não há maneira que eles podem ser inteiramente controlada, calculada ou prevista, e que um limite inferior na sua taxa de entropia pode ser estabelecida. Para uma determinada fonte, um extrator de aleatoriedade pode até mesmo ser considerado um verdadeiro gerador de números aleatórios ( TRNG ); mas não há extrator única que tem sido comprovada para produzir saída verdadeiramente aleatórios a partir de qualquer tipo de fonte de fracamente aleatória.

Às vezes o termo "viés" é utilizado para designar partida de um fonte fracamente aleatório de uniformidade e na literatura mais antiga, alguns extratores são chamados algoritmos unbiasing , como eles assumem a aleatoriedade de um chamado fonte "tendencioso" e saída de uma distribuição que aparece imparcial. A fonte fracamente aleatória será sempre maior do que a saída do extractor, mas um extractor eficiente é aquele que reduz este rácio de comprimentos, tanto quanto possível, enquanto simultaneamente mantendo o comprimento semente baixo. Intuitivamente, isso significa que tanto a aleatoriedade quanto possível foi "extraído" da fonte.

Note-se que um extrator tem algumas semelhanças conceituais com um gerador pseudo-aleatório (PRG), mas os dois conceitos não são idênticos. Ambos são funções que recebem como entrada um pequeno semente, uniformemente aleatória e produzem uma saída maior que "olha" uniformemente aleatória. Alguns geradores pseudo-aleatórios são, na verdade, também exaustores. (Quando um PRG é baseada na existência de predicados do núcleo duro , pode-se pensar na fonte fracamente aleatório como um conjunto de tabelas de verdade de tais predicados e provar que a saída é estatisticamente perto de uniforme.) No entanto, a definição geral PRG não especifica que uma fonte fraca aleatória deve ser utilizado, e enquanto no caso de um exaustor, a saída deve ser estatisticamente perto de uniforme, em um PRG ele só é necessário para ser computacionalmente indistinguível de ser uniforme, um conceito um pouco mais fraco.

NIST Publicação Especial 800-90B (projecto) recomenda vários extractores, incluindo o SHA família de hash e afirma que, se a quantidade de entropia de entrada é o dobro do número de bits de saída a partir deles, que a produção pode ser considerada essencialmente totalmente aleatório.

definição formal de extratores

O min-entropia de uma distribuição (indicado ), é o maior número real de tal modo que para cada na gama de . Em essência, este mede o quão provável é levar o seu valor mais provável, dando um pior caso ligado em como aleatórios aparece. Deixando denotar a distribuição uniforme ao longo de , claramente .

Para um n distribuição -bit com entropia min- k , podemos dizer que é uma distribuição.

Definição (Extractor): ( kε ) -extractor

Vamos ser uma função que recebe como entrada de uma amostra a partir de uma distribuição e um d -bit semente de , e debita um m cadeia de bits. é um ( kε ) -extractor , se para todas as distribuições , a distribuição de saída é ε -close para .

Na definição acima, ε -close refere-se a distância estatística .

Intuitivamente, um extractor leva um fracamente aleatório n entrada de bits e um curto, semente aleatória uniformemente e produz um m saída -bit que parece uniforme aleatória. O objetivo é ter um baixo (ou seja, usar o mínimo aleatoriedade uniforme quanto possível) e tão alto uma possível (ou seja, para sair como muitos bits close-to-aleatório de saída como nós podemos).

extratores fortes

Um extractor é forte se concatenando a semente com a saída do extractor produz uma distribuição que ainda é próximo de uniforme.

Definição (Extractor Strong): Um extractor -novo é uma função

tal que, para cada distribuição de distribuição (as duas cópias do denotar a mesma variável aleatória) é -close para a distribuição uniforme no .

extratores explícitas

Usando o método probabilística , pode ser mostrado que existe uma ( kε ) -extractor, ou seja, que a construção é possível. No entanto, ele geralmente não é suficiente apenas para mostrar que existe um extrator. Uma construção explícita é necessária, que é dada como segue:

Definição (explícita Extractor): Para funções k ( n ), ε ( n ), d ( n ), m ( n ) um Ext família = {Ext n } de funções

é um explícito ( kε ) -extractor, se Ext ( xy ) pode ser calculado em tempo polinomial (no seu comprimento de entrada) e para cada n , Ext n é um ( k ( n ),  ε ( n )) -extractor.

Pelo método probabilística, pode ser mostrado que existe uma ( kε ) -extractor com comprimento semente

e comprimento de saída

.

dispersores

Uma variante do extractor aleatoriedade com propriedades mais fracas é o dispersor .

extractores de aleatoriedade na criptografia

Um dos aspectos mais importantes de criptografia é aleatória geração de chaves . Muitas vezes é necessário para gerar chaves secretas e aleatórios a partir de fontes que são semi-secreta ou que pode ser comprometida em algum grau. Ao tomar uma chave aleatória simples, curto (e secreto) como uma fonte, um extrator pode ser usado para gerar uma chave mais pseudo-aleatório, que pode então ser usada para criptografia de chave pública. Mais especificamente, quando um extrator forte é usado sua saída aparecerá ser uniformemente aleatória, mesmo para alguém que vê a parte (mas não todos) da fonte. Por exemplo, se a fonte é conhecido, mas a semente não é conhecido (ou vice-versa). Esta propriedade dos extractores é particularmente útil no que é geralmente chamado de exposição-resiliente criptografia em que o extractor desejado é utilizado como uma função de exposição-resiliente (FER). Criptografia exposição-Resilient leva em conta que o fato de que é difícil manter em segredo a troca inicial de dados que muitas vezes ocorre durante a inicialização de uma criptografia de aplicação, por exemplo, o remetente da informação criptografada tem de fornecer os receptores com informações que são exigidas para a descodificação.

Os seguintes parágrafos definem e estabelecer uma relação importante entre dois tipos de ERF-- k -ERF e k -APRF --que são úteis na criptografia de exposição-resiliente.

Definição ( k -ERF): Uma adaptativo K-FER é uma função em que, para uma entrada aleatória , quando um adversário computacionalmente ilimitada pode adaptativamente ler todos excepto para os bits, para alguma função negligenciável (definido abaixo).

O objectivo é o de construir uma FER adaptativo cuja saída é altamente aleatória e uniformemente distribuído. Mas uma condição mais forte é muitas vezes necessária em que cada saída ocorre com probabilidade quase uniforme. Para este efeito, Funções resilientes Quase-Perfeito são utilizados (APRF). A definição de uma APRF é como se segue:

Definição (k-APRF): Um APRF é uma função em que, para qualquer configuração de bits de entrada para quaisquer valores fixos, o vector de probabilidade da saída sobre as escolhas aleatórias para os restantes bits de satisfaz a todos e para alguma função negligenciável .

Kamp e Zuckerman provaram um teorema afirmando que se uma função é um k -APRF, então é também um k -ERF. Mais especificamente, qualquer extractor ter suficientemente pequeno erro e tendo como entrada um alheio fonte, fixa-bit também é um APRF e, portanto, também um k -ERF. Um extractor mais específica é expressa nesta lema:

Lema: Qualquer -extractor para o conjunto de fontes de manipulação de bit alheado, onde é insignificante, é também um k-APRF.

Este lema é provado por Kamp e Zuckerman. O lema é comprovado pelo exame da distância uniforme da saída, que em um -extractor, obviamente, é, no máximo , o que satisfaz a condição do APRF.

O lema conduz à seguinte teorema, indicando que não há, de facto, existe uma k função -APRF como descrito:

Teorema (existência): Para qualquer constante positiva , existe um explícito k-APRF , calculável numa série linear de operações aritméticas em cadeias de bits, com e .

Definição (função desprezível): Na prova deste teorema, precisamos de uma definição de uma função desprezível . A função é definida como sendo insignificante se para todas as constantes .

Prova: Considere o seguinte -extractor: A função é um extrator para o conjunto de fonte de manipulação de bit alheio: . tem , e .

A prova da existência deste extractor com , bem como o fato de que é computável em tempo de computação linear no comprimento de pode ser encontrada no artigo de Jesse Kamp e David Zuckerman (p. 1240).

Que este extractor preenche os critérios do lema é trivialmente verdadeiro como é uma função desprezível.

O tamanho da é:

Desde que nós sabemos , em seguida, o limite inferior no é dominado por . Na última etapa, usamos o fato de que o que significa que o poder de , no máximo . E uma vez que é um inteiro positivo, sabemos que é no máximo .

O valor de é calculado usando a definição do exaustor, onde sabemos que:

e usando o valor do que temos:

Utilizando este valor de nós representam o pior caso, onde está a limite inferior. Agora por cálculos algébricos temos:

Que inseriu no valor de dá

,

o que demonstra que existe um extractor k-APRF explícita com as propriedades dadas.

Exemplos

Von Neumann extractor

Talvez o exemplo mais antigo é devido a John von Neumann . Sua extractor levou pares sucessivos de bits consecutivos (não-sobreposição) do fluxo de entrada. Se os dois bits compatível, nenhuma saída foi gerada. Se os bits diferente, o valor do primeiro bit estava de saída. O extractor de Von Neumann pode ser mostrado para produzir uma saída uniforme, mesmo que a distribuição de bits de entrada não é uniforme, desde que cada bit tem a mesma probabilidade de ser um e não há nenhuma correlação entre sucessivos bits.

Assim, toma como entrada uma sequência de Bernoulli com p não necessariamente igual a 1/2, e gera uma sequcia de Bernoulli com uma forma mais geral, aplica-se a qualquer sequência de permutável - que só se baseia no fato de que, para qualquer par, 01 e 10 são igualmente provável: para ensaios independentes, estes têm probabilidades , enquanto que para uma sequência de permutável a probabilidade pode ser mais complicado, mas ambos têm a mesma probabilidade.

máquina Chaos

Outra abordagem é a utilização da saída de uma máquina de caos aplicada ao fluxo de entrada. Esta abordagem geralmente se baseia em propriedades de sistemas caóticos . Bits de entrada são empurrados para a máquina, evoluindo órbitas e trajetórias em vários sistemas dinâmicos. Assim, pequenas diferenças na entrada produza muito diferentes saídas. Tal máquina tem uma saída uniforme, mesmo que a distribuição de bits de entrada não é uniforme ou tem falhas graves, e pode, portanto, utilizar fracos fontes de entropia . Além disso, este sistema permite uma maior complexidade, qualidade e segurança do fluxo de saída, controlada especificando três parâmetros: custo de tempo , memória necessária e chave secreta .

função hash criptográfico

É também possível utilizar uma função hash criptográfico como um extractor de aleatoriedade. No entanto, nem todo algoritmo de hash é adequado para esta finalidade.

aplicações

Aleatoriedade extractores são amplamente utilizados em aplicações de criptografia, através do qual um hash criptográfico função é aplicado a um de elevada entropia, mas fonte não-uniforme, tais como informações ou teclado da unidade de disco de temporização atrasos, para se obter um resultado uniforme aleatória.

Extractores de aleatoriedade ter desempenhado um papel nos recentes desenvolvimentos em criptografia quântica , onde os fótons são usados pelo extrator de aleatoriedade para gerar bits aleatórios seguros. [1]

Extração de aleatoriedade também é usado em alguns ramos da teoria da complexidade computacional .

extracção aleatória também é usada para converter os dados para uma amostra aleatória simples, que é normalmente distribuída, e independente, que é desejado por estatísticas.

Veja também

Referências