Loading
Nota de Estudos
Study Reminders
Support
Text Version

Operações sobre Geradores Pseudo-aleatórios

Set your study reminders

We will email you at these times to remind you to study.
  • Monday

    -

    7am

    +

    Tuesday

    -

    7am

    +

    Wednesday

    -

    7am

    +

    Thursday

    -

    7am

    +

    Friday

    -

    7am

    +

    Saturday

    -

    7am

    +

    Sunday

    -

    7am

    +

Fundamentos de CryptographyProf. Dr. Ashish Choudhury (Ex-) Infosys Foundation Career Development Cátedra Instituto de Tecnologia – BangaloreLecture – 9Composing PRGsOlá todos, bem-vindos a esta palestra. Nesta palestra, continuaremos nossa discussão sobre os geradores de pseudorandom, a saber, veremos como compor PRGs. (Consulte o Tempo do slide: 00 :39) Esta é uma operação muito popular que executamos em PRGs e compondo PRGs basicamente queremos aumentar o tamanho de entrada e o tamanho de saída da PRG. Isso significa, imagine que você recebe um PRG seguro, esqueça pelo momento os passos do algoritmo G e algoritmo G basicamente leva uma entrada de tamanho l bits e produz uma saída de tamanho L bits e agora nosso objetivo é basicamente compor muitas execuções independentes do algoritmo G, a saber, aqui iremos considerar a composição paralela de G.Em nossa discussão futura, também consideraremos a composição serial de G. Assim, fazendo a composição paralela do algoritmo G, nosso objetivo é projetar um novo gerador de número aleatório que eu denote por Gnew, que basicamente leva uma entrada de tamanho k.l bits e ele deve produzir um saída de tamanho k vezes L bits. Então, você pode imaginar que este algoritmo Gnew agora leva k blocos de entradas onde cada bloco é de tamanho l bits e cada um desses blocos de l bits são uniformemente aleatórios. Internamente o que este algoritmo Gnew está fazendo é ele está executando o algoritmo G o algoritmo existente G no primeiro bloco, independentemente ele está executando outra cópia do algoritmo G no segundo bloco e assim como que independentemente ele está executando uma cópia kth do algoritmo G com o último bloco como entrada. Ele simplesmente concatena o resultado de cada uma dessas chamadas independentes do algoritmo G e que é definido para ser o resultado deste algoritmo Gnewand que é como você realmente está compondo de forma paralela o algoritmo G.Now, queremos provar aqui que se o número de cópias ou o número de vezes que compusermos este algoritmo existente G, a saber k, é alguma função polinomial do seu parâmetro de segurança n e se o seu algoritmo existente G é um PRG seguro como por qualquer uma das definições indistinguível baseado em definição baseada em indistinguibilidade ou próximo bit preditor, então queremos provar que o novo algoritmo Gnew que nós ter obtido por compor o PRG em paralelo também é um PRG seguro. (Consulte o Slide Time: 02 :52) Para isso, vamos introduzir uma nova estratégia de prova que chamamos de argumento híbrido, e esta é uma estratégia de prova muito popular utilizada extensivamente em primitivas modernas de criptografias. Para fins de demonstrar esse argumento híbrido, considerarei o fator de repetição k = 2, isto é apenas pela simplicidade e mais tarde veremos o caso para um k genérico, em que k é qualquer função polinomial do parâmetro de segurança, certo. Então, se eu considerar k = 2 que significa, meu algoritmo Gnew agora consiste em 2 cópias independentes, 2 cópias paralelas do algoritmo existente G.Quero provar que esse algoritmo Gnew é um gerador pseudorandom, e eu quero usar a definição baseada em indistinção. Então, meu objetivo é mostrar que não existe um distinguidor de tempo polinomial que possa distinguir uma amostra uniformemente aleatória gerada por este algoritmo Gnew a partir de uma amostra uniformemente aleatória gerada pela execução de um gerador verdadeiramente aleatório, que supera as cadeias uniformemente aleatórias de comprimento 2L bits, certo. Assim, para isso, considere 2 experimentos diferentes, que são denotados por H0 e H1.In ambos esses experimentos, o desafio para o distinguidor é uma amostra formada por 2 blocos de bits L, que são denotados por y1 e y2. Em ambos os mundos, o distinguidor tem de descobrir a forma como esta amostra y1, y2 foi gerada. Assim, no experimento H0, a primeira parte da amostra assim como a segunda parte da amostra são ambas as cadeias uniformemente aleatórias de comprimento L bits e é assim que se pode imaginar uma amostra de desafio para o distinguidor teria sido gerada, se cadeia uniformemente aleatória de comprimento 2L bits teria sido dada como o desafio para o distinguidor. Considerando que no experimento H1, ambas as partes do desafio a saber, y1 e y2, são geradas invocando o algoritmo G existente em sementes uniformemente aleatórias s1 e s2 e executando o algoritmo G de forma independente duas vezes. Então você pode imaginar que este experimento H1 é a versão do experimento baseado em indistinção se o distinguidor teria participado do experimento baseado em indistinguibilidade. E a amostra de qual eu teria sido dada a D teria sido gerada pelo nosso algoritmo Gnew. Agora, nosso objetivo é provar que ambas as versões do experimento são computacionalmente indistinguíveis, o que denoço por esta notação? &assip;. Então, esta notação significa que estas 2 versões dos experimentos são computacionalmente indistinguíveis e o que eu quero provar aqui é que se o meu algoritmo existente G for realmente um PRG seguro conforme a noção de experimento baseado em indistinção, então com probabilidade quase igual D teria saída a mesma saída em experimento H0 assim como um experimento H1.That significa a probabilidade diferenciadora ou a vantagem distintiva do meu distinguidor para qualquer distinção de tempo polinomial é superior delimitado por uma função insignificante. É isso que eu quero provar quando eu digo que eu quero provar o meu algoritmo Gnew é um direito PRG seguro. Agora, verifica-se que não podemos provar diretamente ou não podemos reduzir diretamente a segurança do algoritmo Gnew para a instância da segurança do algoritmo existente G porque o algoritmo G produz apenas uma amostra de bits de tamanho L, enquanto que no algoritmo Gnew você está realmente invocando o seu algoritmo existente G twice.Então, para provar a indistinguibilidade computacional do experimento H0 e H1, o que eu vou fazer é introduzir um experimento intermediário que eu denote como Hint e em um nível muito alto, este experimento intermediário é um tanto intermediário entre H0 e H1. Isso significa, aqui também o distinguidor será dado uma amostra formada por 2 blocos de tamanho L bit, L bits, mas a diferença aqui é que a primeira parte da amostra que teria sido gerada executando o algoritmo G em uma entrada uniformemente aleatória. Considerando que a segunda parte da amostra que teria sido gerada por rodar um gerador verdadeiramente aleatório, e agora, o que vamos provar é, provaremos 2 reivindicações diferentes. A primeira reivindicação será a de que alegaremos que se meu algoritmo existente G for realmente um PRG seguro, então ambos o experimento H0 e experimento Hint são computacionalmente indistinguíveis. Isso significa, qualquer diferenciador de tempo polinomial vai para a saída dos mesmos bits de saída em ambas as versões do experimento se ele é H0 ou H1, exceto com uma probabilidade insignificante, que eu denote por negl1.Da mesma forma, vou provar que se o meu algoritmo existente G é um PRG seguro, então o meu experimento intermediário, Hint e H1 são computacionalmente indistinguíveis do ponto de vista de qualquer distinguidor de tempo polinomial. Isso significa que, com probabilidade quase idêntica de qualquer tempo polinomial, o distinguidor vai à saída do mesmo bit de saída independentemente de estar participando do experimento H1 ou se está participando do experimento H2, exceto com alguma função insignificante, que eu denove por negl2.Agora, se eu provar essas 2 afirmações, então ao somar essas 2 probabilidades diferenciadas, posso acabar mostrando que o meu experimento H0 e H1 também são computacionalmente indistinguíveis, a saber, a probabilidade com a qual o distinguidor poderia distinguir fora se está participando do experimento H0 ou se está participando do experimento H1 será superior delimitado pela somatória de 2 probabilidades insignificantes, e a partir da propriedade de encerramento da função de probabilidade insignificante, chegamos à conclusão de que a soma de 2 funções insignificantes também é uma probabilidade insignificante. (Consulte o Tempo de Slides: 09 :22) Então, vamos provar a primeira reivindicação. Isso significa, queremos provar que se G é um PRG seguro, então nenhum distinguidor de tempo polinomial não pode distinguir fora se está participando do experimento H0 ou se está participando do experimento Hint, exceto com alguma probabilidade insignificante de insucesso. A intuição por trás desta afirmação ou a afirmação é que se temos um distinguidor de tempo polinomial que pode distinguir significativamente se está participando do experimento H0 ou se é participar do experimento Hint, então usando esse distinguidor podemos projetar outro distinguidor que pode distinguir um y1 uniformemente aleatório de um pseudorandom y, e deixar-nos estabelecer formalmente esta intuição. Por isso, imagine para o momento que você tem um distinguidor D que pode distinguir fora se está participando de uma instância de experimento H0 ou se está participando de uma instância de um experimento Hint.Now, usando este distinguidor, nosso objetivo é projetar outro distinguidor de tempo polinomial que eu denote por A cujo objetivo é distinguir uma amostra uniformemente aleatória gerada por um algoritmo G versus uma amostra verdadeiramente aleatória de bits tamanho L gerada por um gerador verdadeiramente aleatório, certo. Assim, o algoritmo A participa de uma instância da minha definição ou experimento indistinguível para o PRG onde será lançado um desafio y1 de L bitsand o desafio para o algoritmo A é descobrir se y1 é gerado pelo algoritmo G ou por um generator.Agora, o que o algoritmo vai fazer é algoritmo vai levar a ajuda do algoritmo D,right. Antes de entrar em como exatamente o algoritmo A leva a ajuda do algoritmo D, deixe-me apenas relembrar que conforme a sintaxe do nosso experimento indistinguível, a forma como a amostra y1would foi gerada é a seguinte. O verificador do experimento baseado em indistinguibilidade teria tostado uma moeda, se a moeda teria saída 0, então a amostra y1 é gerada por um gerador verdadeiramente aleatório. Considerando que se a moeda for de 1, então a amostra y1 é gerada executando-se o algoritmo G em uma entrada uniformemente aleatória. O desafio para o nosso algoritmo A é descobrir o que é exatamente b é, se b = 0 ou se b = 1. Agora, o que o adversário vai fazer é ele mesmo vai gerar uma cadeia uniformemente aleatória que denoço por y2 de tamanho L bits e ela produz um novo desafio ou uma nova amostra para o distinguidor D concatenando o desafio y1 que foi lançado a A com a amostra y2 que ele gerou uniformemente aleatoriamente.Agora, o que exatamente está acontecendo aqui? Certo. Então, deixe-nos parar por aqui por um momento. Se você vir a maneira como o adversário A fez o cálculo aqui, se a amostra por que y1 teria sido gerada uniformemente aleatoriamente, então y1, y2 teria olado como se fosse um desafio que o adversário D teria esperado ao participar do experimento H0 pois no experimento H0 tanto y1 como y2 são gerados uniformemente aleatoriamente.Isso significa nessa redução, se a amostra y1 que é lançada como um desafio ao adversário for gerada executando um gerador verdadeiramente aleatório, e se for concatenada por uma amostra verdadeiramente aleatória, outra amostra independente de tamanho L bits, então y1, y2 teria olhado como um desafio que o adversário D teria esperado ao participar do experimento H0, certo. Por outro lado, se a amostra y1 que é lançada como um desafio ao adversário for gerada executando um gerador de pseudorandom G, então este y1 concatenado com uma amostra uniformemente aleatória y2 pareceria um desafio para o distinguidor, o qual o distinguidor teria esperado ao participar de uma instância do experimento Hint. Como neste experimento intermediário, a primeira parte da amostra é gerada executando um gerador de pseudorandom, enquanto que uma segunda parte da amostra a amostra de desafio é uniformemente aleatória. Agora, o nosso adversário A não sabe se ele realmente encaminhou uma amostra conforme o experimento H0 ou se ele encaminhou uma amostra conforme o experimentHint para o distinguidor. É um distinguidor D que pode realmente identificar se y1, y2 ele está vendo é gerado conforme H0 ou como por Hint. Isso é o que eu quero dizer quando digo que temos um distinguidor que pode distinguir significativamente se está participando de uma instância de H0 versus uma instância de experimento Hint, certo. Assim, qualquer que seja o caso baseado na amostra y1, y2 que é dada ao distinguidor, o distinguidor vai a saída um pouco, digamos b ’, que indica se a amostra é gerada conforme o experimento H0 ou se foi gerado conforme o Hint.Now, dependendo da saída do algoritmo D, qual é a saída de A? Vai-se produzir a mesma saída que D vai produzir. Isso significa se D diz que a amostra que está vendo é gerada conforme o experimento H0, então Uma etiquetas a amostra y1 como se ela for gerada por um gerador verdadeiramente aleatório, enquanto se o distinguidor D diz b ’ = 1, isso significa se ele diz que ythe sample y1, y2 é gerado conforme o experimento intermediário, então o adversário A diz que a amostra y1 é gerada conforme o pseudorandom generator.Então, agora vamos calcular a vantagem distintiva do algoritmo A, que construímos usando o distinguidor D. Então, calculemos primeiramente a probabilidade de que nosso algoritmo A outputs ou etiquetas uniformemente aleatoriamente amostra y1 como o resultado de um gerador de pseudorandom. Isso significa, queremos calcular a probabilidade de que uma saída b ’ = 1 mesmo que b = 0, e a alegação é essa é exatamente a mesma probabilidade com a qual nosso distinguidor D vai a saída b ’ = 1 no experimento H0, e isto é porque se b = 0, certo, se b = 0, então estamos no caso em que y1 teria sido gerado por um gerador verdadeiramente aleatório e que y1 concatenado por y2 teria criado uma amostra para D conforme o experimento H0 zero. A saber, a visão do distinguidor teria sido exatamente a mesma que teria por participar do experimento H0, certo? Considerando que a probabilidade de que o nosso algoritmo A supere b ’ = 1 dado b = 1, isso significa que supera a amostra y1 como ela rotula a amostra y1 como a saída de um gerador de pseudorandom, dado que foi realmente gerada por um gerador de pseudorandom é exatamente o mesmo com o qual nosso distinguidor D, o distinguidor D existente teria saída b ’ = 1 ao participar de uma instância do experimento Hint porque se b = 1, isso significa a amostra de desafio y1 para A gerada por um gerador de pseudorandom, então aquela amostra de pseudorandom gerada concatenada por uma amostra verdadeiramente aleatória pareceria uma amostra que D espera ao participar de uma instância do experimento Hint.So, com qualquer que seja a probabilidade D teria saída b ’ = 1 no experimento Hint, com exatamente a mesma probabilidade nosso adversário A está indo para a saída b ’ = 1 dado b = 1. Portanto, se você considerar a vantagem distintiva do algoritmo A que construímos, é exatamente o mesmo com o qual o algoritmo existente D pode distinguir o experimento H0versus experimento H1.So, se o distinguidor existente pode distinguir significativamente o experimento H0 do experimento Hint, então o que mostramos é um algoritmo A que pode distinguir significativamente uma amostra de pseudorandom gerada por algoritmo G a partir de uma amostra uniformemente aleatória, mas isso é uma contradição com a assunção que estamos fazendo, estamos dizendo que o algoritmo G existente é um seguro PRG.Isso significa que, uma vez que o algoritmo G existente é um PRG seguro, a vantagem distintiva do algoritmo A vai ser superior delimitado por uma probabilidade insignificante, o que implica ainda que a vantagem distintiva do algoritmo existente D também vai ser superior delimitado por probabilidade insignificante. Então, isso prova nossa primeira reivindicação. (Consulte o Tempo do slide: 18 :44) Da mesma forma, podemos provar que se o algoritmo G existente é seguro, então nenhum distinguidor de tempo polinomial pode distinguir significativamente uma instância do experimento Hint da instância do experimento H1. Novamente, a ideia da prova permanecerá a mesma. Assuma para o momento que você tenha um distinguidor existente que possa distinguir o experimento Hintfrom H1 um. Usando isso, projetamos outro distinguidor A, que pode distinguir uma amostra de pseudorandom de tamanho L bits a partir de uma amostra uniformemente aleatória de tamanho L bits.Então, ele participa de uma instância do experimento baseado em indistinção, em que é dada uma amostra y2 que é gerada uniformemente aleatoriamente ou é gerada executando um algoritmo G com uma entrada uniformemente aleatória. O objetivo do adversário A é descobrir se b = 0 ou b = 1. Ora, o que este A vai fazer é ir escolher uma semente própria, que é de tamanho l bits, e produz uma amostra de pseudorandom y1 e produz agora uma amostra de desafio maior para o distinguidor D existente concatenando a amostra de pseudorandom y1 com a amostra de desafio y2.So antes de prosseguirmos mais adiante, pode-se ver claramente aqui que se a amostra de desafio y2 for uniformemente aleatória, então uma amostra de pseudorandom y1 seguida de uma amostra verdadeiramente aleatória pareceria uma amostra que o D espera em uma instância da experiência Hint. Considerando que se a amostra y2 for amostra de pseudorandom, então um pseudorandom y1 concatenado com um pseudorandom y2 criaria uma amostra para D como por uma instância do experimento H1, right.Então, com base na mesma ideia que utilizamos para provar a afirmação anterior, podemos realmente acabar mostrando que a probabilidade com a qual A poderia distinguir se o desafio y2 é pseudorandom ou verdadeiramente aleatório é exatamente a mesma com a qual o distinguidor D poderia distinguir fora se está participando de uma instância do experimento Hint versus se está participando de uma instância do experimento H1. Portanto, se a vantagem distintiva do algoritmo G é não desprezível, então a vantagem distintiva do nosso algoritmo A é também não desprezível, mas isso é uma contradição com a suposição de que nosso algoritmo G é pseudorandom. (Consulte o Tempo do slide: 21 :17) Então, com base nisso, o resumo da prova é o seguinte. Nós realmente provamos 2 reclamações individuais. Se o algoritmo existente G for um gerador pseudorandom, então nenhum distinguidor de tempo polinomial pode distinguir fora se está participando do experimento H0 ou se está participando do experimento Hint, exceto com alguma função insignificante, diga negl1. Da mesma forma se o algoritmo existente é um PRG seguro, então nenhum distinguidor pode distinguir fora se está participando de uma instância de experimento Hint versus se está participando de uma instância de experimento H1, exceto com uma probabilidade insignificante que eu denote por negl2. Portanto, se eu somar essas 2 vantagens distintivas, obtenho que o experimento H0and experimento H1 também são computacionalmente indistinguíveis porque a soma de 2 funções insignificantes também é superior delimitado por uma função insignificante. Isso significa, se na verdade compor o algoritmo existente G duas vezes com entradas independentes, então o novo algoritmo também é um PRG seguro. (Consulte o Tempo de Slides: 22 :27) Então, vamos chegar ao caso geral, certo. O caso geral foi quando na verdade estávamos compondo o algoritmo G polinomial existente de vezes, e para provar que o novo algoritmo também é um PRG seguro. A saber, nós criamos 2 instâncias do experimento H0 e H1where H0 teriam realmente criado uma amostra de desafio para o distinguidor gerado conforme a execução dos tempos independentes do gerador aleatório k, enquanto que um experimento H1 a amostra que é dada ao distinguidor é realmente gerada executando o algoritmo G k vezes de forma independente.Nosso objetivo é provar que nenhum distinguidor de tempo polinomial pode distinguir fora se está participando do experimento H0 ou se está participando do experimento H1. Para provar essa afirmação basicamente, temos que introduzir agora o número polinomial de experimentos híbridos intermediários, certo. Nomeadamente, temos de introduzir k instâncias de híbridos intermédios. Sendo assim, o primeiro híbrido intermediário será quase idêntico ao H0, exceto que a primeira parte do desafio. A saber, o primeiro bloco da amostra de desafio que é dado ao distinguidor é realmente gerado por rodar uma instância de um gerador de pseudorandom, enquanto que os blocos restantes da amostra de desafio que é dada ao distinguidor são todos gerados uniformemente aleatoriamente. Então, essa é a única diferença entre o experimento H0 e Hint1 e podemos provar usando estratégia similar que utilizamos na reclamação anterior do exame anterior que se o algoritmo G for um PRG seguro, então o distinguidor D não pode distinguir uma instância de experimento H0 versus uma instância de experimento Hint1 .Da mesma forma, o segundo experimento híbrido intermediário será quase idêntico ao primeiro experimento híbrido Hint1. A diferença será que a segunda parte ou segundo bloco da amostra de desafio que é dada ao distinguidor é agora gerada executando um gerador pseudorandom e os blocos restantes (k – 2) do desafio são gerados uniformemente aleatoriamente, certo. Novamente, podemos provar que se o algoritmo existente G é um PRG seguro, então nenhum distinguidor de tempo polinomial pode distinguir uma instância de experimento Hint1 de uma instância do experimento Hint2 .Assim, a (k-1) th híbrida intermediária será a seguinte. Aqui, o primeiro (k – 1) blocos da amostra de desafio que é dado ao distinguidor é gerado por correria (k-1) instâncias independentes do algoritmo G e o último bloco da amostra de desafio é gerado uniformemente aleatório e podemos provar que se o meu algoritmo existente G é seguro PRG, então nenhum distinguidor de tempo polinomial pode distinguir uma instância desta (k-1) experiência híbrida thintermediate from (k – 2) th word intermediário híbrido experiment.Finalmente, iremos provar que se o algoritmo G existente é seguro, então nenhum distinguidor de tempo polinomial pode distinguir o intervalo o experimento H1 a partir de uma instância do experimento híbrido thintermediário (k-1). Então, se eu agora somo esse k distinguindo vantagens do adversário, o que eu acabo mostrando é que a vantagem distintiva de qualquer diferenciador de tempo polinomial para distinguir uma instância do experimento H0 de uma instância do experimento H1 é superior delimitado por alguma função k vezes insignificante. Já que k é uma função polinomial, a função k vezes insignificante também vai ser uma função insignificante, o que prova que o meu algoritmo Gnew também é um PRG seguro. (Consulte o Tempo do slide: 26 :18) Então, agora, vamos analisar o exemplo final para esta palestra. Estamos considerando agora alguma outra operação que podemos executar na PRG e obter PRG seguro. Então, aqui eu sou dado algum PRG seguro arbitrário e estou agora construindo um novo PRG G ’ em que a saída de G ’ é simplesmente obtida executando o algoritmo G, que é o algoritmo existente e por simplesmente inverter a saída do algoritmo G existente, certo. A minha alegação é que se o seu algoritmo existente G é um PRG seguro, então este novo algoritmo G ’ também é um PRG seguro. Novamente a prova será por redução e a intuição por trás do grupo de redução é a seguinte. Ao contrário, suponha que o seu novo algoritmo G ’ não seja um algoritmo seguro. Isso significa, suponha existir um algoritmo de tempo polinomial algoritmo que possa distinguir a saída de G ’ a partir de um resultado de um gerador verdadeiramente aleatório, então utilizando-se desse algoritmo podemos também projetar um distinguidor de tempo polinomial que pode distinguir um resultado de um algoritmo G a partir de um resultado de um gerador verdadeiramente aleatório, o que será uma contradição. A intuição por trás dessa redução é que inverso de qualquer cadeia uniformemente aleatória é também uma cadeia uniformemente aleatória e o reverso de uma string pseudorandom também é uma sequência pseudorandom. A saber, a ideia por trás de uma redução é a seguinte. Então, assuma por exemplo, você tem um distinguidor existente a DG ’ para o novo algoritmo para o G ’ nós construímos e utilizamos este algoritmo quero construir outra DG de tempo polinomial distinguidor DG para o meu algoritmo existente G. Assim o distinguidor DG recebe uma amostra, que é gerada uniformemente aleatoriamente ou executando o algoritmo G.O que este algoritmo DG vai fazer é ele vai simplesmente produzir uma nova amostra para o meu algoritmo DG ’ simplesmente invertendo os bits da amostra de desafio y. Por isso, antes de prosseguir ainda mais na redução, o ponto aqui é que se a amostra y é realmente uma amostra uniformemente aleatória, então é a nova amostra Y. Por outro lado, se a amostra y é uma amostra de pseudorandom, então é a nova amostra Y.Que significa com qualquer probabilidade que meu algoritmo existente DG ’ possa distinguir uma amostra verdadeiramente aleatória Y de uma amostra de pseudorandom Y, com quase a mesma probabilidade, meu novo algoritmo DG vai distinguir uma amostra uniformemente aleatória y de uma amostra uniformemente aleatória Y, essa é basicamente a ideia por trás de uma redução, e estou deixando os detalhes completos do redução para você. Basicamente, acabamos mostrando a vantagem distintiva do meu algoritmo DG é exatamente o mesmo que a vantagem distintiva do algoritmo existente DG ’, right.So, se isso provar se o meu algoritmo existente G é um PRG seguro, então é o novo algoritmo G ’ .Então, isso me leva até o final desta palestra. Só para resumir, nesta palestra, vimos um novo primitivo chamado gerador de pseudorandom, que é um algoritmo determinístico e o objetivo do gerador de pseudorandom é expandir sua entrada e gerar uma saída que é significativamente maior do que sua entrada. Mais importante ainda, o objetivo do pseudorandom generatoris de produzir uma amostra de saída que parece quase idêntica a uma saída que teria sido gerada por um gerador verdadeiramente aleatório. Temos visto várias definições equivalentes de gerador de pseudorandom, e também vimos como podemos compor paralelmente os geradores pseudorandom polinomial número de tempo para obter um novo gerador de pseudorandom. Espero que tenha gostado desta palestra. Obrigado.