Loading
Nota de Estudos
Study Reminders
Support
Text Version

Functions 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 Chair Professor de Technology-BangaloreLecture-14Pseudo Random Functions PRFsOlá todos, bem-vindos à palestra 13. (Consulte o Tempo do slide: 00 :31) O plano para esta palestra é o seguinte. Introduziremos um bloco de construção muito importante para a criptografia de chave simétrica a saber: pseudo função aleatória. E mais tarde veremos que como a pseudo função aleatória funciona como um bloco de construção fundamental para projetar muitas belas primitivas de chave simétrica. Discutiremos também variantes de pseudo função aleatória a saber: pseudo permutação aleatória e forte permutação pseudo aleatória. Veremos como construir pseudo geradores aleatórios a partir de pseudo função aleatória. (Consulte o Tempo do slide: 01 :01) Então, comecemos nossa discussão sobre a função pseudo aleatória. Em um nível muito alto, uma função pseudo aleatória é um algoritmo determinístico com duas entradas e um único outputwhere e. E assumiremos que o tamanho da chave é n e n é algum parâmetro de segurança. Por isso, é por isso que muitas vezes chamamos a função F como uma função chaveada porque ela vai ser operada por uma chave. Na prática, o tamanho de n, l e L pode tudo muito e mais adiante veremos várias instanciações de pseudo função aleatória. Realmente n, l, L todos são diferentes, mas asymptoticamente tudo tem que ser alguma função polinomial do seu parametrão.Agora, como vamos usar essa função pseudo aleatória. Assim, sempre que estamos projetando quaisquer primitivas criptográficas, a forma como usamos essa função pseudo aleatória é a seguinte: no início das instanciações do primitivo criptográfico, que usa esta função F, ou o emissor ou o receptor vai-se a gerar uma chave uniformemente aleatória. E de alguma forma ele será estabelecido com a festa de recebimento também. E não seria conhecido o atacante. Uma vez fixada a chave, não vamos alterar a chave durante toda essa sessão ou ao longo dessa instanciação. A chave permanecerá a mesma. Agora, uma vez que fixamos a chave, onde k vai ser corrigido e não seria conhecido o atacante. É assim que vamos utilizar uma função pseudo aleatória. Agora, o que exatamente é a propriedade de segurança que exigimos da função pseudo aleatória. E informalmente exigimos o seguinte: se a chave k é desconhecida, e uniformemente escolhidas aleatoriamente a partir do domínio do espaço chave, então nós basicamente exigimos que o comportamento ou a saída da função chave de Fk deve quase se assemelhe à saída de qualquer função verdadeiramente aleatória para. Por isso, lembre-se, uma função verdadeiramente aleatória é uma função deskeada. Então, o que basicamente quer é aquela função chaveada Fk, uma vez que a chave tenha sido escolhida aleatoriamente, seu comportamento deve quase se assemelhado ao comportamento de uma função pseudo aleatória. (Consulte o Tempo do slide: 03 :53) Então, deixe-nos ir um pouco mais fundo no que exatamente eu quero dizer com a declaração formal. Imagine que você tem uma função verdadeiramente aleatória que é uma função não chaveada, ela não tem nenhuma chave, apenas é preciso uma entrada de tamanho l bits e ele produz uma saída de bits tamanho L. Então, é fácil imaginar o comportamento de uma função verdadeiramente aleatória da seguinte forma: o que realmente funciona aleatoriamente é uma entrada de tamanho x, e ele produz uma saída de bits tamanho L. E você pode imaginar que basicamente, esta função verdadeiramente aleatória mantém uma tabela formada por 2lrows, onde basicamente as lojas de primeira linha. O segundo-rowstores e as lojas de última linha .Assim, sempre que essa função verdadeiramente aleatória recebe uma entrada x, o que basicamente faz é verificar internamente se já existe uma entrada para o valor dessa função verdadeiramente aleatória na entrada x. Se ela não estiver lá, então preencha essa linha, a saber, F (x) por. Para as futuras chamadas dessas funções verdadeiramente aleatórias disse que y para ser a saída dessa função verdadeiramente aleatória na entrada x. Por outro lado, se o valor x que foi passado, você já tem uma entrada correspondente a essa chave x nesta tabela então basta passar no valor que é armazenado nessa linha correspondente como a saída y. Sendo assim, é assim que se pode imaginar o comportamento de uma função verdadeiramente aleatória. O importante aqui é que, uma vez que essa função é uma função verdadeiramente aleatória, cada linha aqui é uma cadeia independente de bits de comprimento L. Isso significa e são independentes uns dos outros, para qualquer um. Isso significa, se existir um algoritmo, que tenha sido notyet visto o valor da função verdadeiramente aleatória em alguma entrada x, ele não pode prever qual será exatamente o valor da função para essa entrada x, exceto adivinhar a saída, e o adivinhador será bem sucedido com probabilidade 1/2L. Fora isso, não há como prever resultado da função verdadeiramente aleatória em alguma entrada x. E isso se mantém mesmo que aquele algoritmo que realmente esteja tentando prever resultado dessa função verdadeiramente aleatória na entrada x já tenha visto a saída dessa função verdadeiramente aleatória em vários valores de x anteriores, que podem estar relacionados a este novo x valores. Mas isso ocorre porque cada linha na tabela dessa função verdadeiramente aleatória é independente uma da outra. A propriedade de segurança que exigimos de uma função pseudo aleatória é que uma vez que fixemos a chave selecionando a chave uniformemente aleatoriamente então essa função chaveada também deve ter as propriedades semelhantes, exceto com uma probabilidade insignificante. (Consulte o Tempo do slide: 07 :02) Então, o que exatamente isso significa é que no seu lado esquerdo você tem uma função chaveada Fk, onde a descrição da função F é conhecida publicamente. Eu ressalto que a descrição da função é publicamente conhecida e o que não se sabe é basicamente o valor da chave. No lado direito, você tem uma função verdadeiramente aleatória que consiste basicamente de 2Lrows cada entrada consistindo de uma cadeia uniformemente aleatória de comprimento L bits. E quando digo que minha função F é uma função pseudo aleatória, o que basicamente eu quero dizer é que não existe um teste estatístico de tempo polinomial ou algoritmo estatístico que possa distinguir significativamente uma saída do algoritmo Fk da saída dessa função verdadeiramente aleatória. Isso significa, se o nosso distinguidor ou o teste estatístico são basicamente dadas saídas da função Fk ou da saída da função aleatória em vários insumos de adversário ’ s ou escolha de distinguidor. Do ponto de vista do distinguidor, essas saídas poderiam ser tão propensas a vir da função Fk como é provável que provem dessa função verdadeiramente aleatória. Agora, antes de irmos mais longe, esta condição é semelhante à forma como definimos a noção de gerador de pseudo aleatório. Portanto, lembre-se no pseudo gerador aleatório que a segurança é definida dizendo-se que não existe um teste estatístico, que quando dado uma amostra não pode distinguir se essa amostra é gerada executando um gerador aleatório de pseudo, ou executando um gerador verdadeiramente aleatório. Nesse experimento, esse distinguidor foi dado apenas uma amostra porque nosso pseudo gerador aleatório é uma única função de entrada. Para cada chamada do gerador de pseudo aleatório, a amostra vai ser diferente porque a chave para o pseudo gerador aleatório vai ser diferente. Mas, no contexto de pseudo função aleatória, a forma como vamos utilizar uma pseudo função aleatória em aplicação real mundial é que a chave será fixada uma vez para todos no início da sessão. E então os insumos x vão ser variados. E cada chamada da função será com a mesma chave. (Consulte o Tempo do slide: 09 :14) Então o que agora vamos fazer é que em nossa definição formal, basicamente o adversário vai receber muitas amostras, e ele tem que distinguir se essas amostras são geradas por rodar uma função chaveada Fk ou executando uma função verdadeiramente aleatória. Por isso, vejamos o que são exatamente os detalhes formais. Portanto, você recebe a descrição de uma função publicamente conhecida, e o experimento que chamamos como indistinção de experiência contra uma PRF com relação a um algoritmo diferenciador contra a função F e l é o parâmetro de segurança. As regras dos jogos são as seguintes: o distinguidor tem permissão para pedir a saída da função em muitos entradas x de sua escolha, e pode pedir suas consultas adaptivamente que significa que pode primeiro pedir a saída de função na entrada x1. Em seguida, com base na resposta, ele pode decidir o que deve ser x2. E então com base na resposta, ele pode decidir o que deve ser x3, e assim por diante. Não colocamos absolutamente nenhuma restrição sobre que tipo de consultas distinguidor é asking.Agora, uma vez que o distinguidor submete suas consultas, o desafiante aqui tem que apresentar a resposta, a saber, a saída das funções nesses insumos. E a forma como o desafiante teria preparado essas respostas é o seguinte: basicamente, o desafiante vai tosse uma moeda uniformemente aleatória, que vai indo para a saída 0 ou 1 com probabilidade 1/2. Se o tosse da moeda é de 0, então todas essas respostas y1, .., yq são basicamente geradas executando uma função verdadeiramente aleatória sobre aqueles x entradas. Em um mais detalhe todas essas cordas de y são basicamente independentes umas das outras e cada uma delas é basicamente uma cadeia de bits uniformemente aleatória de comprimento L bits. Por outro lado, se a tosca de moeda do desafiante é de 1, então esta y saídas são basicamente a saída de uma Fk de função chaveada, onde a chave é escolhida uniformemente aleatoriamente pelo desafiante. E agora o desafio para o distinguidor é descobrir como exatamente essas respostas y1, .., yq são geradas, se elas são geradas pelo mecanismo 0 ou se são geradas bymecanismo 1. Esse é um desafio para o nosso distinguidor. Portanto, distingue-se neste caso saídas b ’ que vai ser um pouco que basicamente diz se ele sente que uma amostras y1, .., yq são geradas por mecanismos 0 ou pelo mecanismo 1. E a nossa definição de segurança é dizemos que a função F é uma função pseudo aleatória se para cada algoritmo de tempo polinomial probabilístico D participando deste experimento, existe uma função insignificante como que a probabilidade de o distinguidor identificar corretamente o rótulo ou a natureza das amostras y1, .., yq é superior delimitado por ½ + negl (n). Novamente, a probabilidade é tomada aqui sobre a escolha aleatória do desafiante e as consultas aleatórias do distinguidor. Outra formulação equivalente da mesma definição é que dizemos que a função F é um PRFif a vantagem distintiva do nosso distinguidor é superior delimitado por uma função insignificante. Isso significa que não importa se b = 0 ou se b = 1 o que significa que não importa se as amostras de y são geradas por uma função verdadeiramente aleatória ou se são geradas por uma função aleatória pseudo. Em ambos os casos distinguidor deve saída a mesma saída, digamos b ’ = 1 exceto com probabilidade insignificante. E, novamente, podemos provar que se temos uma pseudo função aleatória que satisfaz a primeira condição, então ela aplica-se também é satisfaz a segunda condição e vice-versa. Assim, dependendo de nossa conveniência, podemos usar qualquer uma dessas duas definições. Sendo assim, essa é a definição de um pseudo aleatório funciona.Basicamente, a intuição neste experimento é que estamos dando ao nosso distinguidor um acesso oráculo à função em que a função é uma função verdadeiramente aleatória ou uma função chaveada. E o distinguidor tem que distinguir fora se está interagindo com um oráculo de função verdadeiramente aleatória ou se está interagindo com um oráculo de função chaveada. Esta definição de segurança demanda que, exceto com probabilidade insignificante ela não deve ser capaz de distinguir. Observe que aqui, somos obrigados a superior com a probabilidade de sucesso do adversário por ½ + negl (n). Não podemos colocar uma definição dizendo que uma probabilidade de sucesso do distinguidor deve ser de 0 porque sempre há possibilidade de que o distinguidor que possa apenas adivinhar que está interagindo com dizer TRF ou PRF e com probabilidade metade pode realmente identificar corretamente ou a probabilidade a metade de seu palpite poderia ser corrigido.Então, nunca podemos colocar uma condição de que a probabilidade de sucesso do distinguidor deve ser de 0. A vantagem insignificante adicional é basicamente devido ao mal necessário associado ao fato de que estamos no mundo computacional. (Consulte o Tempo do slide: 14 :25) Então, agora vamos ver, se é fácil ou se é o quão fácil ou o quão difícil é construir uma função pseudo aleatória. Então, imagine eu projetar uma função F da seguinte forma e para simplicidade, assumo que o comprimento de chave e comprimento de bloco e de saída são do mesmo tamanho a saber dizer n bitstrings e a forma como a saída da função é definida. É assim que a saída é computada. Nosso objetivo é comprovar ou desmentir se essa função é uma função pseudo aleatória. Na verdade queremos desmentir que essa construção não é uma PRF. E para isso, nós basicamente queremos argumentar se realmente, as saídas dessa função F vai produzir saídas pseudoaleatórias uma vez que consertamos a chave. E se você for um pouco mais fundo no algoritmo, você pode ver claramente o seguinte fato: se nós temos um mapeamento de função verdadeiramente aleatório n bits bits para n bit strings então a saída da função verdadeiramente aleatória em 2 entradas diferentes x1 e x2 será completamente independente uma da outra. Por outro lado, para a função disso estamos considerando,, para qualquer e qualquer. Isso significa que agora você tem um teste que sempre vai passar ou que sempre irá guardar para as amostras que são geradas pela função Fk. E você tem um teste, o mesmo teste pode nem sempre ser aplicável para as amostras geradas por um funcionalismo verdadeiramente aleatório .Então, isso basicamente nos dá uma intuição para projetar um distinguidor que pode distinguir o resultado dessa função F do resultado de uma função verdadeiramente aleatória. Então, aqui está a instância do distinguidor: ela basicamente pede o valor da função na entrada x1, x2 que são diferentes. Em resposta, o desafiante responde com saídas y1 e y2. A forma como são y1 e y2 teriam sido gerados conforme o jogo de indistinção da PRF é o seguinte: o desafiante teria basicamente tostado uma moeda se o tostão de moeda for 0 então y1 e y2 são aleatórios n bit strings. Considerando que, se a moeda tosca for de 1 então y1 e y2 os resultados da função chaveada Fk para a chave uniformemente aleatória conhecida apenas para o desafiante. E agora o distinguidor pode agir de forma inteligente e basicamente distinguir se y1 e y2 são gerados por uma função verdadeiramente aleatória ou uma função pseudo aleatória apenas realizando este teste. Ele verifica se x1 e x2 seu XOR é o mesmo que o XOR de y1 e y2. Se for esse o caso, então diz-se que, as amostras y1 e y2 são geradas pelo mecanismo b = 1, a saber, submete b ’ = 1. Considerando que se o ensaio falhar, e diz, as amostras y1 e y2 são geradas pelo mecanismo 0, nomeadamente b ’ = 0. Agora, analisemos qual é a vantagem distintiva deste distinguidor em particular. Portanto, analisemos primeiramente qual é a probabilidade de que nosso distinguidor esteja corretamente rotulando as amostras y1 e y2 geradas por uma função pseudo aleatória de fato sendo as amostras de uma função pseudo aleatória a saber: as pr [saídas de D b ’ = 1 / b = 1]. Eu afirme que essa probabilidade é igual a 1. Pois se de fato b = 1, ou seja, um caso, as amostras y1 e y2 são conforme as saídas de uma função pseudo aleatória. E, nesse caso, essa condição, o cheque que o adversário ou o diferenciador está realizando sempre vai passar. É por isso que a probabilidade 1, se b = 1, a estratégia do distinguidor será de fato saída b ’ = 1. Por outro lado, calculemos a segunda probabilidade de que qual é a probabilidade de que o nosso distinguidor incorretamente amostras aleatórias y1 e y2 sendo as amostras de uma função pseudo aleatória. Bem, se b = 0, isso significa que nossas amostras y1 e y2 são independentes umas das outras. Então a única maneira que o distinguidor ainda pode saída b ’ = 1 é que para uniformemente aleatória y1 e y2this condição segura ou em outras palavras, a pr [saída D b ’ = 1/b = 0] = 1/2n.So que nos dá a vantagem distintiva do distinguidor que projetamos. E se você tirar a diferença absoluta, ela é quase igual a 1 que faz com quase 100% de probabilidade. Se n se torna maior então este 1 – 1/2nalmost torna-se 1. Por isso, é por isso que com quase 100% de probabilidade um distinguidor pode distinguir o resultado de função chave F da saída de uma função verdadeiramente aleatória. E é por isso que esta função F não é a função pseudo aleatória. Assim, isso significa projetar pseudo-função aleatória é realmente uma tarefa desafiadora. Veremos as construções candidatas mais adiante. (Consulte o Tempo do slide: 19 :56) Agora vamos definir apenas algumas outras variantes de funções pseudo aleatórias com propriedades mais fortes e garantias de segurança. Por isso, a primeira variante é chamada como a pseudo permutação aleatória, que também é conhecida como cifra de blocos. E aqui novamente temos uma função keyed F.A única diferença aqui é que a função chaveada Fk deve ser agora uma bijeção,. Esse é o único diference.Informalmente, a propriedade de segurança que exigimos aqui é que exigimos que uma vez fixemos a chave selecionando uma chave uniformemente aleatória, e a chave não seja conhecida do invasor ou de um distinguidor. Então, nenhum distinguidor de tempo polinomial pode distinguir o comportamento de saída ou a natureza desta função chave Fk de um mapeamento de bijeição verdadeiramente aleatória L bit strings a L bit strings, que novamente pode ser modelado como um experimento de indistinção. (Consulte o Tempo de Slides: 20 :53) Então este é um experimento indistinguível que chamamos como experimento indistinguível PRP e temos uma bijeção aqui, bijeção chaveada. Queremos captar a intuição de que nenhum distinguidor deve ser capaz de distinguir o comportamento desta bijeção chaveada a partir de uma bijeição verdadeiramente aleatória. Por isso, as regras dos experimentos são as seguintes: consultas de distingue para vários x insumos de sua escolha e em resposta o desafiante devolvem as respostas. As respostas são preparadas puxando qualquer uma das seguintes regras: ela joga uma moeda e se a moeda é 0, então todas essas amostras y1, .., yq são basicamente geradas executando uma permutação verdadeiramente aleatória. Considerando que se a moeda tosse for 1 que todas estas amostras são geradas pela execução da função chaveada F em uma chave uniformemente aleatória não conhecida do distinguidor. O desafio para o distinguidor é descobrir o que exatamente é a forma como essas amostras são geradas. Isso significa que ele tem que saída um pouco e nossa definição de segurança é que dizemos que a bijeição chaveada F é um PRP, se a probabilidade de que algum distinguidor de tempo polinomial possa identificar corretamente a natureza da amostra é superior delimitado por ½ + negl (n). Equivalentemente a dizer que a vantagem distintiva do nosso distinguidor deve ser superior delimitado por um funcionalismo insignificante .Assim, em essência tudo é igual ao caso da função pseudo aleatória, a única diferença é que agora estamos basicamente neste caso de função PRP é agora uma bijeção. (Consulte o Tempo do slide: 22 :34) Então, é interessante ver a relação entre esses 2 primitivos pseudo aleatório de função aleatória e permutação pseudoaleatória. Por isso, na sua parte lateral esquerda você tem uma função pseudo aleatória. A diferença aqui ela é uma função, isso significa que o comprimento de entrada, o comprimento de bloco e o comprimento de saída poderiam ser diferentes. Considerando que no caso da permutação pseudo aleatória, é abijeição. Isso significa que, no caso de funções pseudoaleatórias, poderia ser de muitos a uma funcionalidade enquanto que no caso de pseudo permutação aleatória, é um de um mapeamento. Como a nossa PRF pode não ser uma bijeição, é fácil perceber que uma PRF pode não ser um PRP. E o outro caminho por aí? Curiosamente, podemos provar que se o tamanho da saída L for maior do que igual a l, ou em termos mais genéricos, se o tamanho da saída for alguma função polinomial do parâmetro de segurança n então podemos visualizar uma permutação pseudo aleatória como uma função pseudo aleatória. E a intuição para esta afirmação é a seguinte: Nós imaginamos que nos é dada uma permutação chaveada. Então, esse Fk é uma bijeção chaveada. E como é um PRP seguro que significa nenhum distinguidor de tempo polinomial pode distinguir além e interação com esta função chaveada Fk de uma bijeição não chaveada verdadeiramente aleatória, esse sentido tanto este primitivo Fk como FTRP são computacionalmente indistinguios.Agora, se compararmos uma função verdadeiramente aleatória mapeando cordas de bits a L bit strings, como exatamente ela vai ser diferente de uma permutação verdadeiramente aleatória, bem, a única diferença entre uma função verdadeiramente aleatória a partir de uma função verdadeiramente aleatória e uma permutação verdadeiramente aleatória é que uma função verdadeiramente aleatória é que uma função precisa não ser uma bijeção. Isso significa que há chances de colisões que significa que poderia ser uma muitas para uma função onde vários x insumos poderiam dar a mesma saída y. Considerando que no caso de permutação verdadeiramente aleatória, não há chances de colisões. Sendo assim, a única maneira que qualquer distinguidor pode distinguir fora deschaveada função verdadeiramente aleatória a partir desta bijeição chaveada Fk é o seguinte. Se assim acontece que o nosso distinguidor está interagindo com função verdadeiramente aleatória e se assim acontece que algumas de suas consultas lhe dão a mesma saída e ela pode identificar claramente que está interagindo com uma função verdadeiramente aleatória. Porque se estiver interagindo com esta bijeição chaveada Fk, as colisões não vão acontecer. Isso significa que podemos dizer que condicionados ao evento de que nossas consultas de distinguidor nunca vão levar a uma colisão, então a interação do nosso distinguidor com Fk e FTRF é quase a mesma de se o distinguidor estiver interagindo com Fk versus FTRP e já que nossa função Fk é uma permutação chaveada. Sabemos que aquela interação é computacionalmente indistinguível. Então, condição no evento em nosso distinguidor não está recebendo colisões de suas consultas, a interação do nosso distinguidor com a função verdadeiramente aleatória e chaveamento de bijetivação chaveada quase que vai ser idêntica. Agora a questão é qual é a probabilidade de o distinguidor obter uma colisão fazendo q consultas aleatórias através da função verdadeiramente aleatória deskeada?Se estiver fazendo q consultas aleatórias então usando um resultado bem conhecido, o que chamamos como paradoxo do aniversário, que discutiremos com mais rigor no contexto da função hash, podemos provar que as chances de obter uma colisão podem ser superiores arredondadas pela probabilidade q2 /2L. E é por isso que se o seu L é alguma função polinomial do parâmetro de segurança n, então claramente, esta é uma grandeza insignificante. Isso significa que as chances de colisões estarem acontecendo são insignificantes. E é por isso que podemos dizer, ou podemos tratar a bijeição chaveada Fk também como uma pseudo função aleatória. Portanto, essa é a relação entre funções pseudo aleatórias e permutações pseudoaleatórias. (Consulte o Tempo do slide: 27 :00) Agora vejamos a variante final de funções pseudo aleatórias que chamamos de fortes permutações aleatórias ou SPRP, que é um tipo especial de permutação pseudo aleatória. E basicamente aqui nós exigimos que a bijeição chaveada Fk deva ser indistinguível de uma permutação verdadeiramente aleatória mesmo que o distinguidor obtenha acesso oráculo ao inverso da permutação. O que eu quero dizer com isso é demonstrado neste experiment.Então, este experimento de indistinção é chamado como Experimento. E aqui o distinguidor agora dá acesso ou resposta para 2 tipos de consultas. Ele tem acesso oráculo aos valores das permutações, e também tem acesso oracle ao inverso da permutação. O que eu quero dizer com isso é que pode adaptativamente pedir o valor das permutações a vários x insumos de sua escolha e em resposta, ele recebe de volta as saídas y correspondentes. E também é permitido pedir o inverso da permutação de vários valores y de sua choiceand ver os valores x correspondentes. E a forma como o desafiante teria respondido é o seguinte que teria tostado uma moeda uniformemente aleatória se o tostão da moeda for de 0, então todas essas consultas são respondidas avaliando uma permutação verdadeiramente aleatória. Isso significa que todos esses valores x são avaliados como por esta permutação verdadeiramente aleatória. E todas essas consultas inversas também são respondidas consultando o inverso daquela permutação verdadeiramente aleatória correspondente. Por outro lado, se o coin toss b = 1, então todos esses valores y e todos esses valores inversos são computados executando a função chaveada Fk e inverso dessa função chaveada Fk. E o desafio para o distinguidor como de costume é identificar se ele interagiu com oráculo que representa uma permutação verdadeiramente aleatória ou se ela é interagiu com um oráculo chaveado. Nossa definição de segurança é dizemos que a função F é uma forte permutação pseudo aleatória se nenhum distinguidor de tempo polinomial pode identificar corretamente a natureza de seu oráculo, exceto com probabilidade ½ + negl (n) ou colocá-lo em outras palavras, essa vantagem distintiva de nosso distinguidor deve ser superior delimitado por uma grandeza insignificante. Acontece que, se temos uma forte permutação pseudoaleatória, então por definição, ela também é uma pseudo permutação aleatória. E podemos dar construções onde a construção será uma pseudo permutação aleatória. Isso significa, ele será seguro apenas quando o adversário conseguir acesso às consultas oracle para a saída de função. Mas pode não ser uma forte permutação pseudoaleatória que significa, assim que fornecemos o acesso diferenciador ao oráculo inverso o adversário pode distinguir o intervalo. Isso significa que a forte permutação pseudo aleatória é primitiva mais forte do que a pseudo permutação aleatória. (Consulte o Tempo do slide: 30 :01) Agora, deixe-me encerrar esta palestra dando um exemplo de como construir um pseudo gerador aleatório a partir de uma função pseudo aleatória. Então imagine que você recebe uma PRF segura,. Agora, usando isso eu posso construir um pseudo gerador aleatório G, .E basicamente, a maneira como esse algoritmo G opera é a seguinte: ele leva a semente k para o algoritmo G e cria o k para a função pseudo aleatória F. E a pseudo função aleatória F é agora avaliada em entradas publicamente conhecidas 1 2 3 até t. Isso significa que as entradas de blocos que são usadas dentro deste algoritmo G são publicamente conhecidas são 1 para cima para t, é apenas a chave que não vai ser conhecida do distinguidor. E cada invocação desta função F é com a mesma chave, que na verdade é a entrada de nossos pseudo geradores aleatórios. E a saída do pseudo gerador aleatório é basicamente a concatenação das saídas individuais que estão obtendo pela execução das instâncias t da função chaveada Fk, é assim que o nosso pseudo gerador aleatório vai ser operado. Agora queremos provar que se a função chaveada Fk é uma PRF segura conforme a nossa noção de indistinguibilidade, então o algoritmo G que construímos também é um PRG seguro. Conforme o jogo de indistinguibilidade do PRG fornecido, o número de vezes que invocamos a pseudo função aleatória Fk, a saber, t, que é alguma função polinomial do parâmetro de segurança. Para provar isso, vamos primeiro entender a nossa intuição. Nós basicamente consideramos outra versão do algoritmo G, que eu chamo como GTRG, onde cada instância de função chaveada Fk é substituída por uma instância de um mapeamento de função verdadeiramente aleatório l bit strings a L bit strings. Introduzimos o conceito de pseudo função aleatória; vimos a definição. E introduzimos várias variantes de funções pseudoaleatórias como pseudo permutação aleatória, forte pseudo permutação aleatória, e tínhamos visto como construir provavelmente seguro pseudo gerador aleatório a partir de uma função aleatória segura pseudo. Obrigado!