Loading
Nota de Estudos
Study Reminders
Support
Text Version

Geradores pseudoaleató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 – 8Pseudorandom Geradores (Consulte Slide Time: 00 :30) Olá, todos, bem-vindos à palestra 8. O plano para esta palestra é o seguinte: aqui, discutiremos como se livrar da primeira restrição imposta pelo sigilo perfeito. Ou seja, discutiremos como criptografar longas mensagens usando chaves curtas e para isso introduziremos nosso primeiro primitivo no mundo computacionalmente seguro, a saber, geradores pseudorandom. Discutiremos várias definições equivalentes para geradores de pseudorandom. (Consulte o Tempo do slide: 00 :54) Então, a ideia por trás de criptografar mensagens longas arbitrárias usando teclas curtas é a seguinte: Recheça o esquema de pad único em que o espaço da mensagem, espaço de chave e espaço cifrado todo M=? =? = {0, 1}?. Para criptografar uma mensagem m ∈ {0, 1}?, emissor e receptor concordam sobre uma chave uniformemente aleatória k ∈ {0, 1}? gerado pelo algoritmo de geração de chaves e para criptografar a mensagem, remetente simplesmente executa? basta? ?? ?? ?? ???????????? ?discutimos com rigor que esta noção deste processo de criptografia lhe fornece a noção mais forte de sigilo, a saber, o sigilo perfeito, em que se garante que se um adversário computacionalmente ilimitado eavescai o texto cifrado, então não pode distinguir se o texto cifrado é uma criptografia de m0 ou se é uma criptografia de m1 porque a chave chave k ∈ {0, 1}?. Essa foi a ideia básica do one-time pad scheme.Now, aqui nosso objetivo é chegar a um mecanismo de criptografia onde você deseja criptografar mensagens longas usando teclas curtas. Por isso, para isso, introduzimos nova função ou um primitivo que denotamos por G. Vamos muito em breve ver o que exatamente este primitivo é e quais são as propriedades que exigimos deste primitivo. Então, o que essa função G faz é?: {0, 1l → {0, 1}?. Onde tanto l como L são funções polinomiais de seu parâmetro de segurança, mas a saída desta função G é significativamente grande em comparação com a entrada desta função G. Agora, a primeira modificação que vamos fazer no blueprint de uma hora pad é que em vez de emissor e receptor concordam com uma chave, que é de tão grande quanto a mensagem, tanto o emissor quanto o receptor passam a concordar sobre uma cadeia uniformemente aleatória de comprimento l bits, e nowsender simplesmente não pode XOR esta string s com a mensagem porque o tamanho da mensagem e o tamanho da string s são diferentes. Então, o que remete vai fazer é em vez de XORing a mensagem com a chave que estava acontecendo em um pad time, o remetente computes?? (?). Assim, uma vez que a saída da função G vai ser uma sequência de bits de comprimento L, podemos executar o XOR dos bits da mensagem com a saída da função G em entrada s, e o texto cifrado resultante é comunicado sobre o adversário, e o que esperamos é se em vez de um adversário computacionalmente ilimitado cujo tempo de execução é polinomialmente delimitado e se for assegurado que o adversário computacionalmente delimitado não pode distinguir a saída da função G sobre a entrada s de uma cadeia de bits uniformemente aleatória de bits de comprimento L, então será garantido que o adversário computacionalmente delimitado não pode distinguir se o texto cifrado c que ele está observando é uma criptografia de m0 ou se ela é uma criptografia de m1.So, essa é a ideia básica por trás de criptografar mensagens longas usando teclas curtas. A ideia básica é em vez de? basta k, vamos agora realizar???) e vamos supor que um adversário delimitado computacionalmente não pode distinguir a saída desta função G de uma cadeia de bits uniformemente aleatória de bits de comprimento L. (Consulte o Tempo do slide: 04 :43) Então esta função G é chamada de gerador de pseudorandom. Vejamos os detalhes internos e as propriedades de segurança deste primitivo chamado gerador de pseudorandom. Então em um nível muito alto, um gerador de pseudorandom, indicado por G é um algoritmo determinístico,?: {0, 1l → {0, 1}?. Os requisitos a partir deste algoritmo G é o seguinte: em primeiro lugar, o tempo de execução deste algoritmo G deve ser uma função polinomial de um parâmetro de segurança que significa que o seu G deve ser um algoritmo eficiente. Isto internamente significa que tanto o valor l como L são algumas funções polinomiais do seu parâmetro de segurança. Sendo assim, esse é o primeiro requisito do seu gerador de pseudorandom. O segundo requisito é expansão? > l. O terceiro requisito que é a exigência de segurança deste primitivo é a exigência de pseudo aleatoriedade. Informalmente, os requisitos de pseudo randomness requerem que nenhum teste estatístico eficiente deve separar significativamente uma saída que é produzida pelo algoritmo G a partir de uma saída de um gerador verdadeiramente aleatório. Isso significa, se você considerar um gerador verdadeiramente aleatório, que eu denote como G ’, que vai uniformemente saída aleatoriamente um bit string de comprimento L bits, então o pseudo randomness requisito é que nenhum teste estatístico deve ser capaz de distinguir G (s) versus uma cadeia uniformemente aleatória produzida pelo algoritmo G ’. (Consulte o Tempo do slide: 06 :38) Isto internamente significa que o comportamento de saída de seu algoritmo G e G ‘ deve ser quase idêntico, e este é capturado anteriormente por experimento baseado em indistinção, onde a intuição por trás do experimento baseado em indistinção é que nenhum algoritmo eficiente deve ser capaz de distinguir separadamente uma amostra aleatória gerada pelo algoritmo G a partir de uma amostra aleatória gerada por um gerador verdadeiramente aleatório G ’. (Consulte O Tempo De Deslizamento: 07 :10) Vamos ver a definição indistinguível de PRG. Neste experimento, temos um distinguidor cujo objetivo é distinguir uma amostra gerada pelo gerador de pseudorandom a partir de uma amostra gerada por um gerador verdadeiramente aleatório e temos um verificador hipotético ou um experimento. No experimento, o verificador desafia o distinguidor por uma sequência ou uma amostra de bits de comprimento L. O desafio para este distinguidor é descobrir se a amostra y é gerada executando o gerador pseudorandom ou executando um gerador verdadeiramente aleatório a saber, a amostra y que é lançada como um desafio no experimento para o distinguidor poderia ter sido gerada por uma das duas formas seguintes. O verificador teria tostado uma moeda uniformemente aleatória, e se o tosse da moeda é de 0, então a amostra de desafio que é dada ao distinguidor é uma amostra uniformemente aleatória gerada por um gerador de número verdadeiramente aleatório. Considerando que B = 1, então o que o verificador teria feito é que teria colhido uma semente ou a entrada para a função G uniformemente aleatoriamente e ela teria computado a função G sobre esta entrada s e teria produzido uma amostra y.Por isso, agora, o desafio para o distinguidor é descobrir como exatamente a amostra é gerada, se ela é gerada executando um gerador verdadeiramente aleatório ou se ela é gerada executando o algoritmo G em uma semente uniformemente aleatória. O distinguidor tem quantidade polinomial de tempo para dizer se o y é gerado pelo método 0 ou pelo método 1. Sendo assim, a saída do distinguidor é um pouco que denotamos como b ’.A definição de gerador de pseudorandom é nós dizemos que um algoritmo G é um gerador pseudorandom se para cada distinção de tempo polinomial participante participante deste experimento baseado em indistinção, a probabilidade de que ele possa identificar corretamente b = b ’ é superior delimitado pela metade mais alguma função insignificante no parâmetro de segurança, em que a probabilidade de nossa D outcolocando b = b ’ é sobre a aleatoriedade do distinguidor e da aleatoriedade do experimento ou do verificador. Então, aqui o termo PPT que eu estou introduzindo aqui significa tempo polinomial probabilístico. Por um algoritmo de tempo polinomial probabilístico, refiro-me a um algoritmo de tempo polinomial que é de natureza randomizada. Assim, para o restante do curso, uma vez que estaremos discutindo primitivas computacionais garantidas, estaremos considerando adversários cujo tempo de execução será tempo polinomial probabilístico. Então, agora nesta definição, nós exigimos que a probabilidade de que D seja capaz de identificar o mecanismo pelo qual y é gerada deve ser superior delimitado pela metade mais insignificante. Por que metade mais insignificante? Porque sempre há uma estratégia de distinção trivial para o distinguidor apenas adivinhar o método pelo qual y é gerado, e a probabilidade pela qual essa estratégia de adivinhação do distinguidor será bem-sucedida é a metade. Assim, nunca podemos exigir nesta definição que a probabilidade de que a saída do distinguidor ’ s esteja correta deve ser 0 porque há sempre um distinguidor de 1/2probability que pode distinguir ou dizer se a amostra y é gerada aleatoriamente ou executando o gerador verdadeiramente pseudorandom. Além da metade da probabilidade, também estamos dispostos a deixar adversário identificar o mecanismo correto pelo qual a amostra y é gerada com uma probabilidade de sucesso insignificante e isto é porque estamos no mundo computacionalmente seguro, e olhando adiante, estaremos usando este PRG para criptografar arbitrarialmente longo mensagens. Lembre-se no mundo computacionalmente seguro, um dos males necessários que está associado no modelo computacionalmente seguro é que devemos estar dispostos a deixar que o adversário quebre ou ataque o esquema com uma probabilidade de erro insignificante ou muito pequena.Então, que por que essa probabilidade insignificante adicional é permitida para que o adversário vença o experimento ou identifique se a amostra é gerada aleatoriamente ou executando o gerador de pseudorandom. Eu ressalto aqui que em todo esse experimento, a descrição do algoritmo G é publicamente conhecida, pois conforme o princípio de Kerckhoffs ’, nunca supomos que as etapas do algoritmo estejam ocultas. No experimento, o que está escondido do adversário é se a semente com a qual o experimento teria invocado o algoritmo G. O objetivo do distinguidor é descobrir se y é gerado aleatoriamente ou executando o gerador de pseudorandom. Acontece que há uma definição equivalente para o gerador de pseudorandom e a definição equivalente basicamente exige que independentemente da forma como o verificador tenha decidido escolher a amostra, a saída do distintivo deve ser idêntica. Isso significa, a definição alternativa exige que você que diferença absoluta entre essas duas probabilidades deve ser superior delimitado por um funcionalismo insignificante .Então, vejamos o que exatamente essas duas probabilidades são todas. A primeira probabilidade é a probabilidade de que D rotule a amostra y como o resultado de um gerador de pseudorandom apesar de ter sido gerada por um gerador verdadeiramente aleatório. Isso significa, qual é a probabilidade de que D outputs b ’ = 1 dado que b = 0. Portanto D saída b ’ = 1, que significa D está rotulando a amostra y que é lançada para ele como um desafio como sendo o resultado de um gerador de pseudorandom, dado que b = 0.That significa, o verificador decidiu escolher a amostra aleatoriamente, enquanto que a segunda probabilidade é a probabilidade de que D rotule a amostra y como resultado de um gerador de pseudorandom, dado que de fato foi gerado por um gerador pseudorandom. Sendo assim, a segunda definição alternativa exige a vantagem distintiva do distinguidor. Dizemos que a diferença absoluta entre estas 2 probabilidades é a vantagem distintiva do distinguidor com o qual pode distinguir se a amostra foi gerada por um gerador de pseudorandom ou generator.Então, esta definição alternativa exige que independentemente da forma pela qual a amostra y teria sido gerada, estas respostas devem ser quase idênticas em ambos os casos, exceto com uma probabilidade insignificante, e verifica-se que podemos provar que ambas as definições ou condições são equivalentes. A saber, podemos provar que se temos um gerador de pseudorandom, que satisfaz a primeira condição, então implica também que ela tenha de satisfazer a segunda condição e vice-versa. Isso significa, ambas as definições são equivalentes a cada other.Daí, no restante do curso, podemos utilizar qualquer uma dessas duas condições para mencionar a definição de segurança do gerador de pseudorandom como por nossa conveniência. Basta lembrar que a primeira definição diz que a probabilidade é que D descubra corretamente o mecanismo pelo qual y é gerado deve ser superior delimitado pela metade mais insignificante, enquanto que a segunda condição exige que você que a vantagem distintiva do distinguidor, a saber, a sua vantagem de separar se y é gerada por mecanismo 1 ou mecanismo 2 deve ser superior delimitado por uma probabilidade insignificante. (Consulte o Tempo de deslizamento: 14 :58) Então, vejamos um exemplo de gerador de pseudorandom. Na verdade, a construção que vamos ver não é um gerador pseudorandom e nós vamos provar formalmente isso. Por isso, neste exemplo, a função G é a seguinte. Ele leva entrada de tamanho l bits e ele estende sua entrada por 1 bit, a saber, ele produz uma saída cujo comprimento é um a mais do que o comprimento de sua entrada, e a maneira como ele está esticando é a seguinte: os primeiros bits de saída l do algoritmo são iguais às entradas do algoritmo, isso significa que eles vão ser uniformemente aleatórios enquanto que o último bit de saída do algoritmo G é simplesmente o XOR dos bits dos bits dos insumos de algoritmo. Então essa é uma descrição do algoritmo G que é dada a você e agora você tem que provar ou desmentir se esse algoritmo G é gerador de pseudorandom ou não. Por isso, de fato, verifica-se que este algoritmo G não é um gerador pseudorandom e para isso, podemos considerar o seguinte teste estatístico eficiente que pode distinguir qualquer amostra gerada por um algoritmo G de uma cadeia uniformemente aleatória de comprimento l + 1 bits. Se considerarmos qualquer amostra gerada pelo algoritmo G em uma entrada uniformemente aleatória s, verifica-se que nessa saída, o bit l + tinto tem que ser o XOR do primeiro l bits porque esse é a propriedade de saída de qualquer saída gerada pelo algoritmo G. Considerando que se considerarmos qualquer cadeia uniformemente aleatória de comprimento l + tinto bits gerado por um verdadeiramente gerador aleatório, pode acontecer que l + tl bit é de fato o XOR do primeiro l bits, mas a probabilidade de isso acontecer é apenas 1/2.That significa que você agora tem uma condição que definitivamente vai ser satisfeita para uma amostra sempre se a amostra teria sido gerada por algoritmo G, enquanto que a probabilidade de que a mesma condição se mantenha para uma amostra aleatória gerada por um algoritmo é no máximo a metade. Agora, com base nessa intuição, podemos converter este teste estatístico em um distinguidor eficiente que pode distinguir uma amostra gerada por um algoritmo G de um gerador verdadeiramente aleatório com uma probabilidade significativa e a estratégia de distinguidor é a seguinte. O distinguidor será lançado com um desafio, que será constituído por uma cadeia de comprimento l + 1 bits e o desafio para o distinguidor é descobrir como ele é gerado, a saber, se é gerado uniformemente aleatoriamente ou se ele foi gerado executando o algoritmo G em uma semente de entrada uniformemente aleatória s. Agora, a estratégia diferenciadora para o distinguidor é a seguinte: o distinguidor rotula a amostra y como o resultado do gerador de pseudorandom. Ou seja, diz b ’ = 1 ou saídas b ’ = 1 se e somente se encontrar o bit l + tinto do desafio que lhe é dado é o XOR dos bits restantes l do desafio. Agora, calculemos a vantagem distintiva desta estratégia diferenciadora.Vamos primeiro descobrir qual é a probabilidade de que esta amostra de etiquetas de estratégia distingue que é uniformemente aleatória como uma amostra gerada por um gerador de número verdadeiramente aleatório, e verifica-se que a probabilidade de que D supere b ‘ = 0 dado que b = 0 é a metade, porque se b = 0 isso significa que a amostra y é verdadeiramente aleatória e apenas com probabilidade 1/2 e será assegurada que o bit l + tinto é realmente o XOR dos bits restantes l. Neste caso o distinguidor teria saída b ’ = 1, enquanto que a probabilidade de que as saídas b ‘ = 1, considerando-se que b = 1, é de fato 1, pois se b = 1, isso significa que o desafio ou a amostra que foi dada ao distinguidor é gerada por um gerador de pseudorandom, nesse caso será realmente o caso que l + 1thbit é o XOR dos restantes l bits e para esse caso, o distinguidor vai para a saída 1.So se considerar a vantagem distintiva do distinguidor, ela é a metade, que é simplesmente uma boa probabilidade distintiva, é uma função não desprezível no parâmetro de segurança, e daí este distinguidor ou este algoritmo G não satisfaz a definição de gerador de pseudorandom. (Consulte o Tempo do slide: 19 :24) Então, lembre-se o jogo gerador pseudorandom e no jogo de indistinguibilidade do pseudorandom gerador, destacamos que o distinguidor deve ser um algoritmo eficiente, deve ser um algoritmo de tempo polinomial. Por que temos que colocar essa restrição? Acontece que independentemente da forma como você projeta um gerador de pseudorandom, pode ser sempre distinguido por um distinguidor de força bruta onde a estratégia de distinguidor será fazer uma força bruta do que são todos os inputs possíveis para o algoritmo G. Este distinguidor de força bruta pode sempre distinguir uma amostra verdadeiramente aleatória de uma amostra de pseudorandom com probabilidade, o que é quase equivalente a 1. Então, vamos entender isso. Qualquer gerador de pseudorandom, uma vez que tem de produzir uma saída que é significativamente maior do que a sua entrada, ela tem de expandir deterministicamente sua entrada, e consequentemente, a saída do gerador pseudorandom vai estar longe de um stringente uniformemente aleatório porque para um gerador verdadeiramente aleatório, cada um dos bit de saída é gerado de forma independente, enquanto que para um gerador de pseudorandom, cada um dos bits de saída é realmente uma função determinística da entrada. Por isso, para demonstrar meu ponto, consideremos um gerador de pseudorandom arbitrário. Não nos concentremos nos detalhes internos deste algoritmo G e imaginemos que este é um gerador de pseudorandom de comprimento duplicado, que expande a entrada por entrada de tamanho duplo. Isso significa que se for preciso uma entrada de tamanho n bit, ele produz uma saída de tamanho 2n bits. Queremos comparar este algoritmo com um gerador verdadeiramente aleatório G que teria produzido cadeias uniformemente aleatórias de comprimento 2n bits.Agora, se compararmos as saídas do algoritmo G, verifica-se que a maioria das cordas de comprimento 2n bits não ocorrem na faixa de algoritmo G. Então, o que eu quero dizer por faixa de G é o conjunto de todas as saídas possíveis que poderiam ter sido geradas executando o algoritmo G em várias entradas possíveis. A saber, a gama de gerador verdadeiramente aleatório é o círculo maior, que é o conjunto de todas as cordas possíveis de comprimento 2n bits, pois um gerador verdadeiramente aleatório vai produzindo cada um da cadeia de bits do candidato 2n como um resultado com probabilidade 1/2 para a potência 2n enquanto que, se considerarmos o algoritmo G, não é o caso de que todas as cordas de comprimento 2n bits provavelmente vão ocorrer conforme a saída. O número máximo de saídas distintas que o algoritmo G poderia produzir é no máximo 2n, a saber, o número de entradas possíveis para o algoritmo G porque desde que o algoritmo G é um algoritmo determinístico, para cada entrada você obterá uma saída específica. Assim, no máximo o melhor que você pode esperar a partir disso é para cada entrada distinta, o algoritmo G está dando um output.So distinto, o número máximo de saídas que o algoritmo G pode produzir é no máximo 2n. Como se pode ver claramente que 2nis um subconjunto muito, muito pequeno, do espaço maior, a saber 22n. Isto significa que se considerarmos a probabilidade de que uma cadeia de bits 2n uniformemente aleatória, que teria sido produzida por um gerador verdadeiramente aleatório, e se calcularmos a probabilidade de que uma cadeia aleatória de comprimento 2n de comprimento poderia ter ocorrido também como resultado do algoritmo G.Bem, a probabilidade para isso é 2n /22nbecause a probabilidade de que aquela cadeia verdadeiramente aleatória teria sido também produzida por G depende de existir uma semente, que quando usada com o algoritmo G também teria produzido uma cadeia verdadeiramente aleatória e a probabilidade de acontecer que seja 2-n. (Consulte O Slide Time: 23 :12) Agora, com base nessa ideia, não podemos projetar o seguinte distinguidor que pode distinguir esses 2 geradores de número aleatórios com probabilidade significativa. Por isso, no seu lado esquerdo você tem o comprimento dobrando PRG, enquanto que no seu lado direito você tem o gerador verdadeiramente aleatório gerando cordas de comprimento 2n bits e aqui está o nosso distinguidor. O distinguidor recebe um desafio, uma amostra de comprimento dois 2n bits e tem que descobrir se ele foi gerado executando o primeiro algoritmo ou o segundo algoritmo a saber, o verificador teria gerado moeda, e se a moeda teria sido de 0, a amostra teria sido gerada aleatoriamente e se a moeda teria sido 1, então a amostra teria sido gerada executando o algoritmo G em uma semente uniformemente aleatória. Agora, a estratégia distintiva para o distinguidor é a seguinte: ela faz uma força bruta, a saber, ela passa por todos os valores possíveis de candidatos de s e executa o algoritmo G e verifica se para algum candidato s, G (s) teria dado a amostra y. Se for esse o caso, então distinguidor rotula o desafio y a ser gerado pelo gerador de pseudorandom, caso contrário, rotula uma amostra y como sendo gerada por um gerador verdadeiramente aleatório. É claro que o tempo de execução deste distinguidor é de ordem 2nbecause tem que fazer uma força bruta de um espaço chave de um espaço de sementes cujo tamanho é 2n. Então, claramente é ineficiente, mas o ponto que eu quero deixar claro através deste exemplo é que essa estratégia de distinção pode sempre distinguir de diferença significativamente esses dois algoritmos. Então, vamos calcular a vantagem distintiva deste distinguidor. Então, qual é a probabilidade de que uma amostra verdadeiramente aleatória seja rotulada por este distinguidor como uma amostra gerada por gerador de pseudorandom, isso significa qual é a probabilidade D saídas b ‘ = 1 dada b = 0? Pois bem, como discutimos anteriormente a probabilidade para isso é 2-n enquanto que se a amostra y teria sido realmente gerada por um gerador de pseudorandom, a estratégia de distinção seria de fato saída b ‘ = 1 com probabilidade 1.So, isso significa, se você tirar a diferença absoluta destas 2 probabilidades, a vantagem distintiva do distinguidor acaba sendo quase 1, a saber, 100%. Assim, pode-se distinguir claramente se a amostra foi gerada pelo PRG ou pelo fato gerador verdadeiramente aleatório, mas como em nossa definição, estamos considerando a segurança apenas contra um diferenciador eficiente, essa estratégia diferenciadora não seria considerada como uma ameaça conforme o nosso modelo. (Consulte O Tempo De Deslizamento: 25 :55) Então, vimos duas definições de PRG baseadas na noção de indistinguibilidade. Acontece que há uma definição alternativa, que é diferente da definição indistinguível-basedada e a definição alternativa é a seguinte: imagine um gerador verdadeiramente aleatório G ’ que produz uma cadeia de comprimento L bits, e como o gerador verdadeiramente aleatório teria funcionado? Para i = 1 L, teria tostado uma moeda justa, inbiased coin L times e teria produzido o resultado. Uma vez que a moeda é imparcial com probabilidade metade, cada um dos bits de saída teria sido 0 ou 1. Isso significa, se houver um adversário ou um algoritmo que tenha observado os primeiros iresultados desse gerador verdadeiramente aleatório, em que isso é qualquer coisa na faixa de 1 L-1, não pode prever o próximo bit de saída do gerador verdadeiramente aleatório, exceto com probabilidade metade porque cada um dos bits de resultado de um gerador verdadeiramente aleatório é independente um do outro. Isso significa, se a probabilidade que é algoritmo A ter observado o primeiro i bits do gerador verdadeiramente aleatório saídas corretamente o bit é sempre superior delimitado por 1/2 e este mantém para qualquer i na faixa de 1 a L-1. A definição alternativa de gerador de pseudorandom é que devemos esperar que algo semelhante aconteça também para gerador de pseudorandom. Isso significa, para um gerador de pseudorandom, mesmo que haja um diferenciador de tempo de polia ou um algoritmo, que tenha visto o primeiro i bits da saída do gerador pseudorandom em uma semente desconhecida, ele não deve ser capaz de prever o próximo bit de saída do gerador pseudorandom, exceto com probabilidade meia mais insignificante, e que a intuição agora é capturada por um experimento que chamamos como experimento de previsão do próximo bit. Neste experimento, temos o algoritmo G para o qual queremos considerar a segurança. A descrição do algoritmo é publicamente conhecida, e o desafio para o adversário é gerado da seguinte forma: o experimento ou o verificador executa o algoritmo G selecionando uma entrada uniformemente aleatória para este algoritmo G e ele produz o resultado do algorítme o adversário pergunta ou desafia as adversidades diz “ okay! você me dá qualquer um i bits da saída que você gerou ”, onde i é qualquer coisa na faixa de 1 a L-1. Assim, dependendo de i, o experimento, ou o verificador lança o primeiro i bits da saída gerada pelo verificador e o desafio para o adversário é computar o próximo bit da saída y gerada pelo verificador observando-se os primeiros bits de saída da amostra como gerados pelo verificador. Nós dizemos que o algoritmo G, que está disponível publicamente é imprevisível se a probabilidade de que Uma saídas i + 1 bit corretamente seja superior delimitado por metade mais insignificante. Então, observe que neste experimento, o adversário não deve distinguir algoritmos de 2 bits, apenas uma amostra gerada por algoritmo 1 versus algoritmo 2. A essência deste experimento é que o adversário tem que prever corretamente o próximo bit de saída do algoritmo G, tendo observado os primeiros bits de saída do algoritmo G em um input.I desconhecida ressalta que a entrada s não é conhecida do algoritmo, pois se a entrada s também é conhecida no algoritmo A, então o adversário pode prever corretamente a próxima saída de y com probabilidade 1. O desafio para o adversário está na ausência da entrada s, ele tem que prever corretamente i + saída de tinto, e na definição, nós superiores amarramos a probabilidade de sucesso do adversário pela metade mais insignificante. De novo, metade porque sempre há um adversário que pode adivinhar o que pode ser o próximo bit de saída do algoritmo G, e com probabilidade 1/2, essa estratégia de adivinhação sempre vai ser correta. Além disso, também estamos dispostos a deixar o adversário corretamente saída a próxima ith output bit do algoritmo G com uma probabilidade insignificante, e isso vem do fato de que estamos no mundo computacionalmente seguro e um dos males associados ao mundo computacionalmente seguro é que devemos estar dispostos a deixar o adversário quebrar seu esquema ou atacar seu esquema com uma pequena probabilidade de sucesso.Então, acontece que podemos provar que se algum algoritmo G satisfaz este experimento de bits próximo ou se o seu algoritmo G é imprevisível como por esta definição, então ele também satisfaz a definição indiferenciada de PRG que vimos anteriormente. Espero que tenha gostado desta palestra. Obrigado.