Loading
Nota de Estudos
Study Reminders
Support
Text Version

Instantiação Provavelmente Segura de PRGs

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 Informação Technology-BangaloreLecture-11Provably Secure Instantiação do PRGOlá todos, bem-vindos à palestra 10, o plano para esta palestra é o seguinte. (Consulte o Tempo do slide: 00 :33) Nesta palestra, discutiremos sobre a instanciação teórica de pseudo geradores aleatórios para os quais introduziremos o conceito de função de uma única forma. E depois de introduzir o conceito de uma só função, veremos como projetar PRG com uma expansão de um bit e então veremos como projetar PRG com expansão arbitrária. (Consulte o Tempo do slide: 00 :53) Então, a pergunta que queremos responder é a existência do PRG. Então, lembre-se que na última palestra, tínhamos visto que se você tem um pseudo gerador aleatório, então usando que é possível projetar cifras de fluxo, que permitem criptografar mensagens longas usando chave curta. Então, a pergunta que não queremos responder é fazer tal PRG existir ou não. E para relembrar, um PRG é um algoritmo determinístico que leva uma semente ou uma entrada de tamanho l bits que denotamos por s. E ele expande sua saída e ele produz uma saída que é significativamente maior do que a entrada e a segurança de PRG significa que a saída deste algoritmo determinístico G deve ser computacionalmente indistinguível da saída de um gerador verdadeiramente aleatório do mesmo tamanho, certo. Então, verifica-se que há 2 maneiras de projetar PRGs. A primeira maneira é provavelmente segura construções de PRGs de uma só função. E quando digo provavelmente seguro quero dizer que as construções que damos usando uma wayfunction para isso damos uma prova de que realmente a construção é PRG no sentido de que eles não existem nenhum distinguidor de tempo polinomial que pode distinguir resultado do PRG resultante do gerador de número aleatório verdadeiro correspondente. Infelizmente, não podemos utilizá-los na prática porque a quantidade de computação que estão envolvidos na construção resultante são de ordem de várias dimensões. Por outro lado, há instanciações práticas de geradores aleatórios pseudo, mas infelizmente não são provavelmente seguros no sentido em que acreditamos que estão heuristicamente seguros porque desde sua construção, nenhuma fraqueza foi relatada para tais pseudo geradores aleatórios, mas a vantagem de pesquisar heuristicamente seguros pseudo aleatórios aleatórios são eles são super fast.So, é por isso que na prática preferimos usar tais uma instanciação. Sendo assim, o foco para esta palestra serão as instanciações de construção provavelmente seguras de geradores aleatórios de uma função de uma só forma. Na próxima imagem discutiremos sobre as instanciações práticas de pseudo gerador aleatório. (Consulte o Tempo do slide: 03 :00) Então deixe-me introduzir o conceito de uma função de forma ou OWF em resumo, portanto, é uma função do domínio de bit string para o codomínio de bits de bit denotado por f. E, informalmente, é uma função que é fácil de computar, mas difícil de inverter. Mais especificamente, há 2 requisitos desta função. O primeiro requisito é que ele seja fácil de computar. A saber, se você recebe qualquer entrada x, computando o valor da função nessa entrada x deve ser o tempo polinomial, polinomial no tamanho da entrada x. O segundo requisito, que é a propriedade interessante a partir desta função de uma forma é a difícil de inverter a propriedade a saber, a exigência é que se você for dada uma amostra aleatória y, do codomínio, então encontrar a preimagem ou uma das pré-imagens deste dado y em tempo polinomial deve ser difícil, exceto com uma probabilidade insignificante. E esta propriedade é modelada por um experimento. (Consulte o Tempo do slide: 03 :58) Assim, neste experimento, nos é dada a descrição de uma função publicamente conhecida f. E o nome do experimento é Invert, jogado com respeito a um algoritmo de tempo polinomial cujo objetivo é inverter a saída de uma função em uma amostra aleatória com relação à função f, e n é o parâmetro de segurança aqui. Por isso, neste experimento, temos 2 entidades, a saber, o verificador e adversário. Assim, as regras do experimento são as seguintes. O verificador aqui escolhe um x aleatório do domínio que é uma cadeia de bits arbitrário e computa o valor da função nessa entrada x, o que é dado como um desafio para o adversário. Assim, o adversário não tem consciência da entrada x, só vê a saída da função na entrada x, a saber, y e o objetivo ou o desafio para o adversário é inverter-se à amostra y a saber, a saber, encontrar pelo menos uma das pré-imagens deste dado valor y.Por isso, submete a sua resposta a saber x ’ e dizemos que a função f tem uma propriedade wayness, iffor qualquer algoritmo de tempo polinomial A participando deste experimento existe uma função insignificante diz negl (n) tal que a probabilidade é que a probabilidade de que adversário seja realmente capaz de saída x ’, o que na verdade é uma preimagem do dado y é superior delimitado por uma função insignificante. Isso significa que nós exigimos que nenhum algoritmo de tempo polinomial deve ser capaz de inverter este yexceto aleatório com uma probabilidade insignificante. Portanto, nesta definição a exigência é que a probabilidade de sucesso desse adversário para inverter o aleatório y deva ser superior delimitado por uma função insignificante não até 0, pois sempre existem uma estratégia de adivinhação pelo adversário a saber, o adversário pode simplesmente adivinhar um aleatório x ’.E sempre existe uma probabilidade não nula de que o adivinhador x ’ de fato acaba sendo uma das prefeitas do dado y, é por isso que na definição, não exigimos que não impamos que a condição de que ela A deva ser capaz de inverter a amostra y deve ser superior delimitado por 0, damos a alavancagem e a superior amarrada a probabilidade de sucesso do adversário por uma probabilidade desprezível.Observe também que não é necessário que o adversário encontre o x exato, pois a função pode ser de muitos para uma função. Então, poderia ser possível que o dado y que é jogado como um desafio para o adversário tenha várias prefeitas. O objetivo do adversário é encontrar uma dessas pré-imagens direito. (Consulte o Tempo do slide: 06 :25) Então, vamos ver um exemplo para deixar nosso entendimento claro, considere a função f que é uma função 2input e a função é do conjunto de números naturais ao conjunto de números naturais. Assim, a função leva 2 entradas do conjunto de números naturais e a saída da função é basicamente o produto dos 2 insumos. Agora, a questão é essa função de uma única função que significa se alguém lhe der o valor de x dot y, seu x e y não são conhecidos por você. Será capaz de inverter ou encontrar uma das pré-imagens a saber: um par de x, y tal que cujo produto é igual ao produto dado em quantidade polinomial de tempo, e verifica-se que eles existem, realmente, existe de fato um algoritmo simples para encontrar uma das pré-imagens e o algoritmo é o seguinte. Portanto, você recebe uma amostra aleatória z, que é basicamente a saída da função em um par de entradas desconhecidas x, y. E o seu algoritmo de inversão é o seguinte. O algoritmo verifica se z é mesmo ou não, se z é mesmo então o algoritmo supera o par de preimagens a seguir, a primeira preimage x ’ é 2 e uma segunda preimage y ’ é z/2. Então, esse é um par de entradas que de fato lhe daria a saída z, enquanto se a amostra z que lhe é dada é ímpar então você apenas saída aleatoriamente x ’, y ’ no conjunto de numeros.Assim, verifica-se que a probabilidade de sucesso deste algoritmo de inversão é na verdade 3 por 4. Pois como a função é uma função de entrada de 2, os valores possíveis de x, y poderia ser (ímpar, ímpar), (ímpar, até mesmo), (mesmo, ímpar) e (mesmo, mesmo). E acontece que, dessas 4 combinações, para 3 das combinações, o seu z sempre estará mesmo. E se z é mesmo e de fato o algoritmo de inversão que é usado aqui, ou seja, ultrapassando 2 e z/2 como a possível pré-imagem é um algoritmo de sucesso. O único caso problemático é quando a amostra x, y é na verdade um par ímpar e ímpar em que o seu z pode não ser z não será um número par, nesse caso você pode estar superando um x ’, y ’. Então, verifica-se que em três quartas das instâncias, o adversário ou este algoritmo será capaz de inverter com sucesso o valor dado z. Daí, esta função f não é uma função de uma só forma porque a probabilidade de sucesso da inversão é de 3/4, o que é uma quantidade significativa de probabilidade.Por outro lado, vamos modificar ligeiramente esta função. Então, minha função f (x, y) ainda é produto de x e y mas em vez de dizer que x e y são números naturais aleatórios, coloque a restrição aqui que x e y são números prios aleatórios de aproximadamente mesmo tamanho. E acontece que essa função agora é conjecturada para ser uma função de uma só forma se x e y são grandes números primos dizem de ordem 1024 bits. Então eu ressalto aqui que é apenas conjecturado que esta função f (x, y) em que x e y são arbitrários grandes números primos é uma função de um só modo porque até agora, não temos nenhum algoritmo de tempo polinomial para inverter esta função. Não se provou formalmente que realmente esta função é uma função de uma só forma. E mais adiante, quando estaremos discutindo sobre a criptografia de chave pública, e estaremos discutindo a teoria do número onde veremos várias funções do tal candidato de uma forma, que são conjecturas em vários duros chamados de hard number teortic hard. Então, para o momento, acreditaremos que esta função f (x, y) onde x e y são números grandes arbitrários e a função é um produto de x e y é um produto candidato one way function. (Consulte o Slide Time: 10 :02) Então agora vamos definir outro conceito relacionado a saber: o de uma via permutação ou OWP. E basicamente uma permutação de um jeito é uma função de um só jeito, que também acontece de ser uma bijeção. A saber, o mapeamento é agora um one-one sobre mapeamento. Isso significa que cada y do codomínio terá uma preimagem única. E a exigência ou o difícil de inverter parte para uma via permutação é que se você é dado um acaso aleatório y do codomínio, o desafio para o adversário é descobrir uma pré-imagem única x que teria realmente dado aquela y em quantidade de tempo polinomial. Então a diferença aqui é para o caso de uma função de um só caminho, o desafio aleatório y poderia ter várias pré-imagens e seu objetivo era encontrar uma dessas pré-imagens. No caso de uma forma de permutação, amostra aleatória y que é dada a você terá apenas uma preimagem única. E seu objetivo é encontrar aquela preimagem única e quantidade polinomial de tempo. Percebamos que tanto no caso de uma mesma função como em uma forma de permutação, colocamos a restrição de que o algoritmo de inversão deve tomar quantidade de tempo polinomial. Porque se não colocamos qualquer restrição na quantidade de tempo, que é dada ao algoritmo de inversão, então há sempre existir um algoritmo de força bruta a saber, o algoritmo pode tentar sobre todo o possível candidato x do conjunto de candidato x e definitivamente ele atingirá sobre um x que será dado o aleatório y que é lançado como o desafio, mas o tempo de execução deste algoritmo de força bruta será exponencialmente ou será proporcional ao tamanho do domínio. E o tamanho do domínio é exponencialmente grande do que o tempo de execução de algoritmos de inversão também é exponencial. Por isso, é por isso que no experimento, onde modelamos a parte de inversão tanto para a função de um só modo como de uma forma permutação colocamos a restrição de que o tempo de execução desse adversário deve ser o tempo polinomial. (Consulte o Tempo do Slide: 11 :52) Então, agora vamos discutir outro conceito relacionado a interessante, a saber, o do predicado hard-core que será útil quando projetamos nosso candidato pseudo aleatório gerador aleatório de uma função de maneira e a motivação para este predicado hard-core é a seguinte. Então imagine que você recebe uma função f, que é uma função de uma só forma ou uma permutação de um jeito. E se você for dado o valor de função em uma entrada aleatória x, então definitivamente computar o x inteiro em quantidade de tempo polinomial é difícil. Porque é isso que é a propriedade de uma função de um só modo ou de uma forma de permutação, mas isso não significa necessariamente que você não pode computar nada sobre x em tempo polinomial, pode haver alguma informação sobre x, que você pode computar a partir do valor de f (x) em quantidade de tempo polinomial. Portanto, basicamente modelos de predicado hardcore o que pode ser computado sobre x de um f (x) em quantidade de tempo polinomial e o que não pode ser computado. Para deixar meu ponto mais claro, considerar a função?: {0, 1} ∗ → {0, 1} ∗ e dizer esta função f é uma função de uma maneira e utilizamos esta função g, projetamos outra função g, que é agora uma função 2input e a função g no par de entrada x1 ele é, e a segunda parte da saída desta função g é na verdade o valor da função f na segunda parte da entrada, a saber x2,? (x1, x2) = (x1,? (x2)). Ou seja, o forma que estou definindo minha função g. E a minha alegação é que se o tamanho de x1 e x2 são aproximadamente iguais, a saber, alguma função polinomial no parâmetro de segurança, então se a função f com a qual começamos é uma função de um só modo, então a função construída g, que é construída como esta também é uma função de uma só forma. Então, basicamente, a ideia aqui é que se g não é uma função de uma única forma, isso significa se alguém lhe der o valor de g (x1, x2), e você pode realmente descobrir x1, x2 em quantidade de tempo polinomial. Em seguida, intuitivamente usando esse algoritmo, você também pode computar o valor de x2 usando apenas dado f (x2), assim podemos estabelecer formalmente seu fato usando um argumento de redução. Por isso, não vou entrar no argumento de redução. Mas basicamente a ideia aqui é que se f é uma função via e a função g, que é uma função de entrada de 2 construída como esta também é uma função de uma maneira fornecida tanto x1 quanto x2 são aproximadamente o mesmo size.Agora, se você vir a função g, verifica-se que mesmo sendo uma função de uma única forma, ao ver a saída desta função g em um par aleatório de entrada, você realmente acaba aprendendo a metade da entrada, certo. Como a primeira metade da saída é realmente a primeira metade da entrada como ela é. Nesse sentido, mesmo que esta função g seja uma função de um só modo, não é o caso de se eu lhe der o valor dessa função g em um par arbitrário de entrada, não é possível computar de volta toda a entrada em quantidade de tempo polinomial. Há algo que você pode computar, há algo que não se pode computar em quantidade de tempo polinomial. Assim, essa noção de hardcore predicate precisamente modelos, o que é tempo polinomial computável a partir do valor da função f (x) na entrada aleatória x, certo. (Consulte o Tempo do slide: 15 :01) Então, vejamos a definição formal deste predicado hard-core. Então, imagine que você recebe uma função a partir de um domínio de bits de bits para o codomínio de bit string e eu ressalto que a função pode não ser uma função de um só modo pode ser uma função normal. Então, nós temos uma função f e correspondente à função f nós definimos outra função hc que é uma função booleana que significa, é preciso uma string binária arbitrária como uma entrada e ela produz uma saída booleana 0, 1.And então vemos que esta função hc associada a uma função f é um predicado hard-core se as seguintes 2 condições guardarem. Assim, a primeira condição é que se você for dado texto de entrada aleatória e computar o valor desta função, predicado hard-core a saber: hc de f deve ser computável de tempo polinomial que significa você deve ser capaz de computar o valor de hc de x em polinomial de tempo polinomial no tamanho da entrada x. A segunda propriedade interessante que realmente faz predicado hard-core muito interessante é a seguinte que se você for dado o valor de f (x) para um x aleatoriamente escolhido, então não é possível computar o valor de hc (x) com probabilidade significativamente melhor que a metade em quantidade de tempo polinomial. Isso significa que o desafio aqui é que se eu te der f (x) e eu não te contar o valor de x, em que x é escolhido aleatoriamente, então mesmo depois de aprender f (x), não devemos computar o valor da função hc de x em quantidade de tempo polinomial, exceto com probabilidade, insignificante melhor que a metade. Se for esse o caso, então dizemos que a função hc (x), hc é actuallythe hard-core predicate associado à função f. Então esse requisito de incapacidade de computar o valor de hc (x) com probabilidade significativamente melhor que a metade por um algoritmo de tempo polinomial é modelado por um experimento que chamamos como experimento hardcore. E agora esse experimento é projetado com relação a uma função f que é conhecida publicamente, que é uma função candidata que poderia ser uma função de candidato ou de uma forma permutação ou poderia ser apenas uma função e associada à função f temos um predicado hard-core de candidato, que é uma função booleana e experimento envolve 2 entidades. Portanto, a regra do experimento é a seguinte. O verificador aqui escolhe um x aleatório do domínio, computa o valor da função nessa entrada x. E a saída correspondente y é dada como um desafio para o adversário. E o objetivo do adversário ou o desafio para o adversário é depois de ver o valor de y que tem para computar o valor de hc (x) sem saber o x. Então, digamos hc (x) vai ser um pouco ele submete as saídas adversas um pouco o que poderia ser 0 ou 1.And dizemos que adversário venceu o jogo se na verdade b = hc (x). Então, isso significa, dizemos que a função hc associada à função f é um predicado hard-core, se para qualquer algoritmo de tempo polinomial participando deste experimento, a probabilidade de que adversário saídas b em que b é realmente igual a hc de x é superior delimitado por metade mais alguma probabilidade insignificante ou função insignificante no parâmetro de segurança. Se for esse o caso, então dizemos que a função hc é um predicado hard-core associado à função f. Então, perceba que há em definição, nós balizamos a probabilidade de sucesso do adversário ser metade mais insignificante, não exigimos que a probabilidade de sucesso do adversário seja de 0, pois sempre há uma estratégia de adivinhação ou adivinhação de adversário que pode apenas adivinhar um pouco e sempre existe uma probabilidade de 1/2 de que o hóspede seja de fato o valor de hc (x) corretamente.Fora isso nós também estamos dispostos a dar a esse adversário uma vantagem extra insignificante e superando com sucesso o predicado hard-core, porque estamos em um mundo computacionalmente seguro. Portanto, essa é a definição de predicado hard-core. (Consulte o Tempo do slide: 18 :53) Então agora a questão é, se nos é dado um candidato one way function ou one way permutationdoes existir um predicado hard-core associado ou não. E acontece que curiosamente a resposta é sim. E isso por causa de um teorema e criptografia muito fundamentais, que também é chamado de Teorema de Goldreich-Levin. E o teorema de Goldreich-Levin basicamente mostra como construir um predicado hard-core associado a qualquer função de uma maneira, ou qualquer uma dada via permutação. Então, não estaremos entrando na prova do teorema de Goldreich-Levin, vamos apenas aproximadamente ver a declaração do teorema e a intuição da segurança. Por isso, a declaração do teorema é a seguinte. Então imagine que você recebe uma função de candidato de uma forma dizer f ou um candidato de uma forma permutação. Agora usando esta função de candidato f, construímos uma função de entrada de 2 g, e a construção de gis da seguinte forma. Assim, ele passa a entrada como x, r. E a saída de g é definida da seguinte forma. Por isso, avaliamos a função f na primeira parte da entrada de g. Isso constitui a primeira parte da saída de g, e a segunda parte da entrada de g é copiada como está na saída do g. E aqui o tamanho das 2 entradas da g, a saber, x e r são de mesma ordem. Então, é assim que definimos a nossa função g. Agora podemos provar formalmente que se a função f com a qual começamos com é uma função única ou uma maneira de permutação então a função g que construímos como (f (x), r) é também uma função de uma forma ou de uma forma de permutação, respectivamente.E a prova é por um argumento de redução. Ou seja, podemos mostrar que se você tem um algoritmo de tempo polinomial para inverter a saída da função g que você construiu em um par aleatório de entrada x, r. Isso significa se você tiver um algoritmo que sem saber o par aleatório de entrada x, r, mas apenas ver o valor de g (x, r) pode te dar de volta x, r em quantidade polinomial de tempo. Em seguida, usando o mesmo algoritmo de inversão podemos construir outro algoritmo de tempo polinomial, que quando dado o valor de f (x) em um x aleatório sem saber o valor de x pode realmente dar de volta o valor de x, o que é uma contradição ao fato de f ser uma função de uma via ou de uma via permutação. Portanto, esse é um argumento de redução direta usando o qual podemos provar este teorema. Então, agora vamos nos concentrar na função g. E o que o teorema de Goldreich-Levin mostra você basicamente que se esta função g é uma função de um só modo, então podemos associar um predicte hard-core correspondente a esta função g. A saber, o predicado hard-core é a função booleana, que basicamente leva combinação linear aleatória dos bits da entrada x, certo. Então o que consideramos aqui é que o seu r é interpretado como um bit string de comprimento n, e o seu x também é considerado como um bit string de comprimento n, estes são as 2 entradas para a função g, e predicado hard-core associado, que está associado à função g é denotado pela função gl. E a função gl é basicamente combinação linear aleatória dos bits do x, onde os combinadores são definidos pela representação de bits da entrada r. E o que o teorema de Goldreich-Levin afirma basicamente que esta função gl (x, r) é o predicado hard?core associado com a função g. Isso significa, se alguém lhe der o valor da função g (x, r), para um aleatório x e r, então, exceto com probabilidade metade mais insignificante nenhum algoritmo de tempo polinomial pode computar o valor de gl (x, r). E a intuição por trás disso a prova do teorema de Goldreich-Levin é que apesar de você ser dado f (x) já que você não sabe o valor de x, basicamente o desafio para computar o gl de Goldreich, a saída da função gl (x, r) é basicamente computar o XOR dos subconjuntos aleatórios do bit de x mas já que o adversário não saberá os bits exatos do x, será difícil para o adversário computar que XOR dos subconjuntos aleatórios dos bits de x. Essa é basicamente a intuição deste teorema. No entanto, verifica-se que a prova deste teorema é de fato desafiador e involved.Assim, os alunos que se interessam por passar pela prova deste teorema de Goldreich-Levin eles podem se referir ao livro de Katz e Lindel, onde deram a prova detalhada, mas para nossa discussão, assumiremos que a função gl (x, r) é associado hard-core predicado que está associado ao nosso candidato one way function g (x, r) certo. (Consulte o Tempo do slide: 23 :36) Então, assumindo que temos agora um predicado hard-core, e temos um candidato de uma maneira permutação vamos ver como podemos construir PRG com mínima expansão, e o que queremos dizer com uma expansão mínima é que vamos supor que somos dadas a um candidato uma forma de permutações do conjunto de cordas de n bit para o conjunto de n bit strings. Isso significa que a função f leva uma entrada que é uma cadeia de comprimento n e ela produz saída que também é uma cadeia de comprimento n. E é uma permutação de uma forma. E associados à função f, temos um hard-corepredicate. Agora dado a isso construiremos um pseudo gerador aleatório onde a construção do pseudo gerador aleatório é a seguinte. A saber, podemos provar que nenhum distinguidor de tempo polinomial existe para a nossa construção, caso contrário, reduz-se para a segurança da função de uma forma subjacente e do hard-corepredicate. Espero que tenha gostado desta palestra. Obrigado.