Por que não combinamos geradores de números aleatórios?

60

Existem muitas aplicações em que um gerador de números pseudo-aleatórios é usado. Então, as pessoas implementam uma que acham ótima, apenas para descobrir mais tarde que ela é falha. Algo assim aconteceu recentemente com o gerador de números aleatórios Javascript. RandU muito mais cedo também. Há também problemas de propagação inicial inadequada para algo como o Twister.

Não consigo encontrar exemplos de alguém combinando duas ou mais famílias de geradores com o operador xor usual. Se houver energia suficiente no computador para executar coisas como implementações java.SecureRandom ou Twister, por que as pessoas não as combinam? ISAAC xor XORShift xor RandU deve ser um bom exemplo, e onde você pode ver a fraqueza de um único gerador sendo atenuada pelos outros. Também deve ajudar na distribuição de números em dimensões mais altas, pois os algoritmos intrínsecos são totalmente diferentes. Existe algum princípio fundamental de que eles não devem ser combinados?

Se você construísse um verdadeiro gerador de números aleatórios, as pessoas provavelmente recomendariam que você combinasse duas ou mais fontes de entropia. Meu exemplo é diferente?

Estou excluindo o exemplo comum de vários registros de troca de feedback linear trabalhando juntos, pois são da mesma família.

Paul Uszak
fonte
A resposta pode depender do aplicativo. Para que você deseja usar a sequência pseudo-aleatória?
Yuval Filmus
11
Você encontrou o Fortuna ( pt.wikipedia.org/wiki/Fortuna_%28PRNG%29 ) parece que está perto do que você descreve e agrega várias fontes aleatórias em um.
Little Code
11
@LittleCode Na verdade, parece completamente diferente. Fortuna gera dados de uma única função de hash. Ele apenas mexe com muitos mecanismos de coleta de entropia fracos antes de (re) hash-lo através de uma única função de saída. Minha pergunta relacionada à saída de várias funções (por que não 10 delas)? Se este for um dispositivo de preenchimento, a velocidade é irrelevante de qualquer maneira.
Paul Uszak
11
O falecido George Marsaglia, um notável pesquisador no campo de PRNGs que inventou vários tipos de PRNG, como multiply-carry-carry e xor-shift, fez exatamente isso quando propôs o gerador KISS nos anos 90, que é uma combinação de três PRNGs de tipo diferente. Eu tenho usado o KISS com sucesso nos últimos vinte anos, não para criptografia, é claro. Uma fonte secundária útil no que diz respeito a beijar é esse papel 2011 por Greg Rose na qual ele aponta um problema com um dos PRNGs constituintes, o que não invalida o conceito combinando
njuffa
4
Knuth relaciona o resultado de combinar ingenuamente geradores de números pseudoaleatórios (usando um número aleatório para escolher qual gerador usar) resultou em uma função que converge para um valor fixo! Então, nos dias que antecederam a revolução dos microcomputadores, ele nos alertou para nunca misturar geradores aleatórios.
JDługosz

Respostas:

7

IIRC (e isso é de memória), o best-seller Rand de 1955, A Million Random Digits, fez algo assim. Antes que os computadores ficassem baratos, as pessoas selecionavam números aleatórios neste livro.

Os autores geraram bits aleatórios com ruído eletrônico, mas isso acabou sendo influenciado (é difícil fazer um flip-flop passar exatamente iguais vezes no flip e no flop). No entanto, a combinação de bits tornou a distribuição muito mais uniforme.

Amador
fonte
45

Claro, você pode combinar PRNGs assim, se quiser, supondo que eles sejam semeados independentemente. No entanto, será mais lento e provavelmente não resolverá os problemas mais prementes que as pessoas têm.

Na prática, se você precisa de um PRNG de alta qualidade, usa um PRNG de força criptográfica bem testado e o semeia com verdadeira entropia. Se você fizer isso, seu modo de falha mais provável não será um problema com o próprio algoritmo PRNG; o modo de falha mais provável é a falta de entropia adequada (ou talvez erros de implementação). Fazer vários PRNGs não ajuda com este modo de falha. Portanto, se você deseja um PRNG de alta qualidade, provavelmente há pouco sentido em fornecê-los.

Como alternativa, se você deseja um PRNG estatístico que seja bom o suficiente para fins de simulação, normalmente a preocupação nº 1 é a velocidade (gerar números pseudo-aleatórios muito rápidos) ou a simplicidade (não queira gastar muito tempo de desenvolvimento pesquisando ou implementando). O Xoring diminui a velocidade do PRNG e o torna mais complexo, para que também não atenda às principais necessidades desse contexto.

Desde que você demonstre cuidado e competência razoáveis, os PRNGs padrão são mais que bons o suficiente, então não há realmente nenhuma razão pela qual precisamos de algo mais sofisticado (não há necessidade de xor-ing). Se você não tem níveis mínimos de cuidado ou competência, provavelmente não escolherá algo complexo como xoring, e a melhor maneira de melhorar as coisas é se concentrar em mais cuidado e competência na seleção do PRNG ao invés de xor-ing.

Conclusão : basicamente, o truque xor não resolve os problemas que as pessoas geralmente têm quando usam PRNGs.

DW
fonte
3
"falta de entropia adequada ... O armazenamento de múltiplos PRNGs não ajuda com isso" - na verdade, pode atrapalhar, pois você aumenta a quantidade de entropia necessária para propagar seus PRNGs. É por isso que você não deseja que seja prática rotineira combinar PRNGs bem testados, mesmo que de fato o proteja contra um desses PRNGs bem testados que se transformam em lixo completo (na implementação que você está usando) .
21816 Steve Jessop #
Outro motivo é que os erros de implementação são muito, muito, muito mais comuns do que problemas fundamentais com algoritmos, portanto, quanto mais simples, melhor. Um algoritmo padrão pode pelo menos ser testado em relação a outra implementação ou valores de referência, um xor personalizado não pode.
Gilles 'SO- stop be evil'
11
@DW Por que "semeado de forma independente?" Como minha pergunta se refere a combinações de diferentes famílias de geradores, cada família deve produzir uma sequência de saída única a partir de sementes idênticas. Por exemplo, java.SecureRandom e RC4 podem ser facilmente propagados da mesma chave e combinados.
Paul Uszak
11
@DW A grande suposição que você declara "usa um PRNG de força criptográfica bem testado". A realidade é praticamente impossível de determinar, como na maioria das cifras criptográficas, hashes e assim por diante - fraquezas são encontradas ao longo do tempo. Eles foram "bem avaliados" pelo conhecimento de ontem ou do passado.
Shiv
11
@PaulUszak, acho que nunca argumentei que xorar dois geradores o torna mais propenso a bugs. Estou dizendo que, se você escolher um bom PRNG (apenas um), um dos modos de falha mais prováveis ​​é a falha de propagação ou falha de implementação, e xoring dois geradores também não ajuda. (Obviamente, se o PRNG único não falhar, a criação de dois geradores também não será útil.) Então, basicamente, está abordando o problema errado. Em outras palavras, os geradores de xoring não aumentam muito a certeza, porque não tratam das causas mais importantes de incerteza.
DW
19

De fato, algo inovador acaba de ser anunciado, fazendo exatamente isso.

O professor de ciência da computação da Universidade do Texas, David Zuckerman, e o aluno de doutorado Eshan Chattopadhyay descobriram que um número aleatório de "alta qualidade" poderia ser gerado pela combinação de duas fontes aleatórias de "baixa qualidade".

Aqui está o artigo: Extratores explícitos de duas fontes e funções resilientes

NietzscheanAI
fonte
8
Este é um artigo puramente teórico sobre um tópico diferente que não tem absolutamente nenhuma relevância prática, apesar dos esforços de relações públicas da UT.
Yuval Filmus
4
@Yuval Filmus - você gostaria de expandir esse comentário?
NietzscheanAI
8
Há uma grande divisão entre teoria e prática. Normalmente, os profissionais não se importam com a teoria e vice-versa. Nesse caso, o ramo de relações públicas da UT decidiu se apegar a um excelente artigo teórico, descrevendo-o como praticamente relevante, o que não é. Os problemas considerados no artigo não são tão interessantes do ponto de vista prático, e têm soluções simples que funcionam bem o suficiente, embora seja impossível provar isso.
Yuval Filmus
2
Além disso, este artigo em particular é apenas um trabalho na área teórica de extratores. Você pode cobrar qualquer outro papel na área da mesma maneira. O objetivo é combinar fontes fracas para criar uma fonte forte. A diferença está apenas nos parâmetros.
Yuval Filmus 20/05
3
Finalmente, a construção no artigo provavelmente é um exagero, não algo que você gostaria de implementar. Parâmetros concretos para esse tipo de construção são difíceis de determinar e geralmente são extremamente ruins, pois os trabalhos sempre se concentram no regime assintótico e ignoram constantes.
Yuval Filmus
9

Suponha que é uma sequência binária pseudo-aleatória. Ou seja, cada X i é uma variável aleatória suportada em { 0 , 1 } e as variáveis X 1 , , X n não são necessariamente independentes. Podemos pensar nessa sequência sendo gerada da seguinte maneira: primeiro amostramos uma chave uniformemente aleatória K e, em seguida, usamos alguma função f ( K ) para gerar a sequência pseudo-aleatória.X1,,XnXi{0,1}X1,,XnKf(K)

Como medimos o quão boa é a sequência pseudo-aleatória ? Embora seja possível medir o quão boa é uma realização específica (digamos, usando a complexidade de Kolmogorov), aqui vou me concentrar em medidas que dependem de toda a distribuição da variável aleatória ( X 1 , ... , X n ) . Um exemplo é a entropia, mas somente serão necessárias duas propriedades de nossa medida L : (um L maior ( ) significa uma sequência mais aleatória)X1,,Xn(X1,,Xn)LL()

  • y1,,ynL(X1y1,,Xnyn)=L(X1,,Xn)

  • X0,X1T{0,1}Z=XTL(Z)min(X0,X1)

A primeira propriedade significa que a medida é invariável ao virar o bit. A segunda propriedade significa que, se misturarmos duas distribuições , o resultado será pelo menos tão bom quanto o pior.X , YiX,Y

Qualquer medida de aleatoriedade razoável satisfará a primeira propriedade. A segunda propriedade é satisfeita pelas medidas mais populares, como entropia e min-entropia .H HH

Agora podemos declarar e provar um teorema mostrando que XOR em duas seqüências pseudo-aleatórias é sempre uma boa idéia.

Teorema. Sejam duas sequências pseudo-aleatórias independentes do mesmo comprimento, e seja uma medida de aleatoriedade admissível (uma que satisfaça as duas condições acima). Então LL(XY )máx(L(X),L(Y)).X,YL

L(XY)max(L(X),L(Y)).

Prova. Suponha . Então é uma mistura do distribuições , misturadas de acordo com a distribuição de . Como e uma mistura é pelo menos tão boa quanto a pior distribuição que está sendo misturada, obtemos . L(X)L(Y)XYXyYL(Xy)=L(X)L(XY)L(X) 

O que esse teorema significa é que, se você XOR duas seqüências pseudo-aleatórias geradas usando duas chaves independentes , o resultado é sempre pelo menos tão bom quanto a melhor sequência sendo XOR, com relação a qualquer medida de aleatoriedade admissível.

Na prática, para usar duas chaves independentes, provavelmente expandimos uma chave para duas chaves de maneira pseudo-aleatória. As duas chaves não são independentes. No entanto, se usarmos uma maneira "cara" de expandir a chave única em duas chaves, esperamos que as duas chaves resultantes "pareçam" independentes e, assim, o teorema se mantenha "moralmente". Na criptografia teórica, existem maneiras de tornar essa afirmação precisa.


Deveríamos, então, XOR dois geradores de números pseudo-aleatórios? Se não somos restringidos pela velocidade, é certamente uma boa ideia. Mas, na prática, temos um limite de velocidade. Podemos então fazer a seguinte pergunta. Suponha que recebamos dois PRNGs, cada um com um parâmetro que controla o tempo de execução (e, portanto, a força) do gerador. Por exemplo, pode ser o comprimento de um LFSR ou o número de rodadas. Suponha que usamos um PRNG com o parâmetro , o outro com o parâmetro e XOR o resultado. Podemos assumir que , para que o tempo total de execução seja constante. Qual é a melhor escolha deTTT1T2T1+T2=tT1,T2? Aqui há uma troca que é difícil de responder em geral. Pode ser que a configuração seja muito pior que ou .(t/2,t/2)(t,0)(0,t)

O melhor conselho aqui é seguir um PRNG popular que é considerado forte. Se você pode poupar mais tempo para gerar sua sequência, faça XOR em várias cópias, usando chaves independentes (ou chaves geradas pela expansão de uma única chave usando um PRNG caro).

Yuval Filmus
fonte
Comentários não são para discussão prolongada; esta conversa foi movida para o bate-papo . Quando chegar a um fim construtivo, edite a resposta para incorporar os resultados de sua discussão.
Raphael
4

Vou tentar, já que estou suficientemente perturbado com os conselhos dados em algumas das outras respostas.

Sejam sequências de bits infinitas geradas por dois RNGs (não necessariamente PRNGs que são determinísticos quando o estado inicial é conhecido), e estamos considerando a possibilidade de usar a sequência com a esperança de melhorar o comportamento em algum sentido. Existem várias maneiras pelas quais podem ser considerados melhores ou piores em comparação com cada um dos e ; aqui estão algumas pequenas que considero significativas, úteis e consistentes com o uso normal das palavras "melhor" e "pior":X,YXYXYXY

  • (0) A probabilidade de aleatoriedade verdadeira da sequência aumenta ou diminui
  • (1) A probabilidade de não aleatoriedade observável aumenta ou diminui (com respeito a algum observador que aplica uma certa quantidade de exame, presumivelmente)
  • (2) A severidade / obviedade da não aleatoriedade observável aumenta ou diminui.

Primeiro, vamos pensar em (0), que é o único dos três que tem alguma esperança de ser preciso. Observe que, se, de fato, qualquer um dos dois RNGs de entrada realmente for verdadeiramente aleatório, imparcial e independente do outro, o resultado do XOR também será verdadeiramente aleatório e imparcial. Com isso em mente, considere o caso em que você acredita que são fluxos de bits isolados e não-aleatórios verdadeiramente aleatórios, mas não tem certeza. Se são as probabilidades respectivas de que você está errado em relação a cada uma delas, então a probabilidade de não ser verdadeiramente aleatória é , de fato muito menos desdeX,YεX,εYXYεXεY<min{εX,εY}εX,εY são assumidos muito próximos de 0 ("você acredita que sejam verdadeiramente aleatórios"). E, de fato, é ainda melhor que isso, quando também levamos em conta a possibilidade de ser verdadeiramente independente, mesmo quando nenhum deles é verdadeiramente aleatório: Portanto, podemos concluir que, no sentido (0), o XOR não pode prejudicar e pode ajudar muito.X,Y

Pr(XY not truly random)min{Pr(X not truly random),Pr(Y not truly random),Pr(X,Y dependent)}.

No entanto, (0) não é interessante para PRNGs, pois no caso de PRNGs nenhuma das seqüências em questão tem chance de ser verdadeiramente aleatória.

Portanto, para esta questão, que é de fato sobre PRNGs, devemos estar falando sobre algo como (1) ou (2). Como essas são em termos de propriedades e quantidades como "observável", "severo", "óbvio", "aparente", agora estamos falando sobre a complexidade de Kolmogorov, e não vou tentar fazer isso com precisão. Mas irei até o ponto de fazer a afirmação esperançosamente incontroversa de que, por essa medida, "01100110 ..." (período = 4) é pior que "01010101 ..." (período = 2) que é pior que " 00000000 ... "(constante).

Agora, pode-se adivinhar que (1) e (2) seguirão a mesma tendência que (0), e que, portanto, a conclusão "XOR não pode prejudicar" ainda pode se manter. No entanto, observe a possibilidade significativa de que nem nem foram observáveis ​​não aleatórios, mas que as correlações entre eles fazem com que sejam observáveis ​​não aleatórios. O caso mais grave disso, é claro, é quando (ou ); nesse caso, é constante, o pior de todos os resultados possíveis; em geral, é fácil ver isso, independentemente de quão bom e sejam,XYXYX=YX=not(Y)XYXYXe precisa estar "próximo" do independente para que seu xor seja não-notavelmente não-aleatório. De fato, ser não-observável-dependente pode ser razoavelmente definido como sendo não-observável-não-aleatório.YXY

Essa dependência surpresa acaba sendo um grande problema.


Um exemplo do que dá errado

A pergunta afirma: "Estou excluindo o exemplo comum de vários registros de troca de feedback linear trabalhando juntos, pois são da mesma família". Mas vou excluir essa exclusão por enquanto, para dar um exemplo claro e simples da vida real do tipo de coisa que pode dar errado com o XORing.

Meu exemplo será uma implementação antiga de rand () que estava em alguma versão do Unix por volta de 1983. IIRC, essa implementação da função rand () tinha as seguintes propriedades:

  • o valor de cada chamada para rand () era de 15 bits pseudo-aleatórios, ou seja, um número inteiro no intervalo [0, 32767).
  • valores de retorno sucessivos alternados par-ímpar-ímpar-par; ou seja, o bit menos significativo alternado 0-1-0-1 ...
  • o bit do menos para o menos significativo teve o período 4, o seguinte depois do período 8, ... então o bit de ordem mais alta teve o período .215
  • portanto, a sequência dos valores de retorno de 15 bits de rand () era periódica com o período .215

Eu fui incapaz de localizar o código-fonte original, mas eu estou supondo que a partir de juntar um par de mensagens de em https://groups.google.com/forum/#!topic/comp.os.vms/9k4W6KrRV3A que fez exatamente o seguinte (código C), que concorda com a minha memória das propriedades acima:

#define RAND_MAX 32767
static unsigned int next = 1;
int rand(void)
{
    next = next * 1103515245 + 12345;
    return (next & RAND_MAX);
}
void srand(seed)
unsigned int seed;
{
    next = seed;
}

Como se pode imaginar, tentar usar esse rand () de várias maneiras levou a uma variedade de decepções.

Por exemplo, em um ponto, tentei simular uma sequência de lançamentos aleatórios de moedas, repetidamente:

rand() & 1

ou seja, o bit menos significativo. O resultado foi simples alternância cara-coroa-cara-coroa. Isso foi difícil de acreditar no começo (deve ser um bug no meu programa!), Mas depois que me convenci de que era verdade, tentei usar o próximo bit menos significativo. Isso não é muito melhor, como observado anteriormente - esse bit é periódico com o período 4. Continuando a explorar bits sucessivamente mais altos, revelou o padrão que observei anteriormente: ou seja, cada próximo bit de ordem superior tinha o dobro do período do anterior. Nesse aspecto, o bit de mais alta ordem foi o mais útil de todos eles. Observe, no entanto, que não havia um limite em preto e branco "o bit é útil, o bit não é útil" aqui; tudo o que podemos dizer é que as posições de bits numeradas tinham graus variados de utilidade / inutilidade.ii1

Eu também tentei coisas como embaralhar os resultados ainda mais, ou juntar valores retornados de várias chamadas para rand (). XORing pares de valores sucessivos de rand () foi um desastre, é claro - resultou em todos os números ímpares! Para meus propósitos (ou seja, produzir uma sequência "aparentemente aleatória" de troca de moedas), o resultado de paridade constante do XOR foi ainda pior do que o comportamento alternativo par e ímpar do original.

Uma leve variação coloca isso na estrutura original: ou seja, seja a sequência de valores de 15 bits retornados por rand () com uma determinada semente e a sequência de uma semente diferente . Novamente, será uma sequência de números pares ou ímpares, o que é pior que o comportamento par / ímpar alternativo original.XsXYsYXY

Em outras palavras, este é um exemplo em que o XOR piorou as coisas no sentido de (1) e (2), por qualquer interpretação razoável. Também é pior de várias outras maneiras:

  • (3) O bit menos significativo do XOR é obviamente tendencioso, ou seja, possui frequências desiguais de 0 e 1, diferente de qualquer posição de bit numerada em qualquer uma das entradas que são todas imparciais.
  • (4) De fato, para cada posição de bit, existem pares de sementes para os quais essa posição de bit é tendenciosa no resultado XOR, e para cada par de sementes, existem (pelo menos 5) posições de bit tendenciosas no XOR resultado.
  • (5) O período de toda a sequência de valores de 15 bits no resultado XOR é 1 ou , comparado a para os originais. 2 15214215

Nenhum de (3), (4), (5) é óbvio, mas todos são facilmente verificáveis.


Finalmente, vamos considerar a reintrodução da proibição de PRNGs da mesma família. O problema aqui, eu acho, é que nunca fica realmente claro se dois PRNGs são "da mesma família", até / a menos que alguém comece a usar o XOR e observe (ou um invasor perceba) que as coisas pioraram no sentido de (1) e (2), ou seja, até que padrões não aleatórios na saída ultrapassem o limite de não notado para notado / embaraçoso / desastroso, e nesse ponto é tarde demais.

Estou alarmado com outras respostas aqui que dão conselhos não qualificados "O XOR não pode prejudicar" com base em medidas teóricas que me parecem fazer um péssimo trabalho de modelar o que a maioria das pessoas considera "bom" e "ruim" sobre PRNGs na vida real. Esse conselho é contradito por exemplos claros e flagrantes nos quais o XOR piora as coisas, como o exemplo rand () dado acima. Embora seja concebível que PRNGs relativamente "fortes" possam exibir consistentemente o comportamento oposto ao XOR em relação ao PRNG de brinquedo que era rand (), tornando o XOR uma boa idéia para eles, não vi nenhuma evidência nessa direção, teórica ou empírico, então não me parece razoável supor que isso aconteça.

Pessoalmente, tendo sido mordido de surpresa por XORing rand () na minha juventude e por inúmeras outras correlações de surpresa ao longo da minha vida, tenho poucas razões para pensar que o resultado será diferente se eu tentar táticas semelhantes novamente. É por isso que eu, pessoalmente, ficaria muito relutante em reunir vários PRNGs com XOR, a menos que análises e verificações muito extensas tenham sido feitas para me dar alguma confiança de que talvez seja seguro fazê-lo para os RNGs em questão. Como uma cura potencial para quando eu tenho pouca confiança em um ou mais PRNGs individuais, é improvável que o XORing os aumente minha confiança, portanto, é improvável que eu o use para esse fim. Imagino que a resposta para sua pergunta é que esse é um sentimento amplamente aceito.

Don Hatch
fonte
Então, como você explica o uso do A5 / 1 por literalmente bilhões de pessoas?
Paul Uszak
@PaulUszak Não faço ideia. O A5 / 1 usado por bilhões de pessoas contradiz algo que eu disse?
Don Hatch
É três PRNGs (na verdade da mesma família) XORed para formar um melhor na maneira que perturba e alarmes ...
Paul Uszak
O que me deixa perturbado e alarmado é o conselho não qualificado "se você não tiver certeza, vá em frente e faça um XOR junto com um monte de RNGs; isso não pode piorar as coisas". Não quis dizer ou sugerir que o XOR é ruim em todos os casos e não tenho nenhuma opinião sobre o A5 / 1 ou o uso do XOR nele. Ajudaria se eu alterasse minha declaração sumária boba final para tornar isso mais claro?
Don Hatch
11
Substituí o simplista "apenas diga não aos RNGs do XORing" no final por algo mais real e, espero, menos enganoso.
Don Hatch
0

AVISO LEGAL: Esta resposta é estritamente sobre "Nós não estamos fazendo isso" e não "aqui está a prova matemática de por que ele pode ou não pode funcionar". Não afirmo que o XOR introduz (ou não) vulnerabilidades criptográficas. Meu argumento é apenas que a experiência nos mostra que mesmo os esquemas mais simples quase sempre apresentam consequências imprevistas - e é por isso que as evitamos.

"Aleatoriedade" é apenas uma ponta do iceberg quando se trata de RNGs e PRNGs. Existem outras qualidades importantes, por exemplo, uniformidade.

Imagine um dado comum que seja bastante bom por si só. Mas agora digamos que você precise de um intervalo de 1-5 em vez de 1-6. A primeira coisa que vem à mente é simplesmente apagar a face 6 e substituí-la por 1 extra. A "aleatoriedade" permanece (os resultados ainda são verdadeiramente aleatórios), mas a uniformidade sofre muito: agora 1 é duas vezes mais provável que outros resultados.

A combinação de resultados de vários RNGs é uma inclinação igualmente escorregadia. Por exemplo. A simples adição de 2 dados lança completamente a uniformidade, já que "7" é agora 6 vezes mais provável que "2" ou "12". Concordo que o XOR parece melhor do que a adição à primeira vista, mas nos PRNGs nada acontece à primeira vista.

É por isso que tendemos a seguir implementações conhecidas - porque alguém gasta muito tempo e dinheiro pesquisando-as e todas as deficiências são bem conhecidas, entendidas e podem ser contornadas. Ao criar suas próprias, você potencialmente cria vulnerabilidades e deve fazer um esforço semelhante para provar isso. Como mostra o exemplo de adição de dados, a combinação não pode ser muito diferente de criar um novo a partir do zero.

A segurança é uma cadeia, tão forte quanto seu componente mais fraco. Uma regra prática em segurança: sempre que você combina duas coisas, geralmente obtém uma soma de falhas, não uma soma de pontos fortes.

Agent_L
fonte
7
Discordo fortemente. Se você XOR uma sequência verdadeiramente aleatória com uma sequência arbitrária, ainda obtém uma sequência verdadeiramente aleatória. Da mesma forma, se você XOR duas seqüências pseudo - aleatórias independentes (ou seja, geradas com chaves diferentes), obtém algo pelo menos tão forte quanto cada uma individualmente.
Yuval Filmus
3
Isso parece errado para mim. O caso usual aqui é que eu acho que tenho dois RNGs de alta qualidade produzindo bits essencialmente verdadeiramente aleatórios, mas há um pequeno épsilon de chance de que eu possa estar (talvez grosseiramente) equivocado sobre um (ou, muito menos provável, ambos). Se eu os juntar juntos, desde que eu esteja certo sobre pelo menos um deles, o resultado será verdadeiramente aleatório, e eu estou bem. Então, combinando-os, reduzi minha chance de ter um RNG ruim de aproximadamente epsilon / 2 para extremamente pequeno epsilon ^ 2, o que é definitivamente uma vitória. Suspeito que dinâmicas similares sejam válidas mesmo em casos menos complicados.
Don Hatch
2
Eu ainda não estou convencido. Quando escrevi "verdadeiramente aleatório", quis dizer "uniformemente aleatório". Se você XOR uma sequência aleatoriamente uniforme com uma sequência arbitrária, obtém uma sequência aleatória uniforme.
Yuval Filmus
2
@ DonHatch Certamente, isso se qualificaria. Digamos que o seu PRNG gere uma sequência de comprimento 100, depois uma versão barulhenta da mesma sequência e assim por diante. Suponha que a correlação bit a bit da segunda cópia com a primeira seja . A sequência XORed satisfaz . Desde, é justo dizer que as correlações não foram "amplamente ampliadas", mas bastante reduzidas. Z i = X iY i Pr [ Z i + 100 = Z i ] = ( 1 + ε 2 ) / 2 ε 2| £ |Pr[Xi+100=Xi]=(1+ϵ)/2Zi=XiYiPr[Zi+100=Zi]=(1+ϵ2)/2ϵ2|ϵ|
Yuval Filmus
3
@YuvalFilmus Você provavelmente está certo de que a correlação entre o item ie o item i + 100 foi brutalmente reduzida, mas esse não é o ponto. Para um exemplo muito específico e da vida real: lembro que a antiga implementação de baixa qualidade rand () no unix teve um comportamento periódico no bit de ordem mais baixa de cada número inteiro de 31 bits retornado, o que a maioria das pessoas não notou. Para aquela sequência de entradas com cópia deslocada de si mesma (que é o que você obtém quando usa uma semente diferente) de tamanho de turno infeliz, você obtém todos os números pares. Isso é muito pior do que o problema na sequência original, para a maioria dos propósitos.
Don Hatch