Loading
Nota de Estudos
Study Reminders
Support
Text Version

Construção Teórica do Bloco Cifradores

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 of Cryptography Prof. Dr. Ashish Choudhury (Ex-) Infosys Foundation Career Development Cátedra Instituto de Technology-BangaloreLecture-18Theoretical Construções do Bloco CiphersOlá todos, bem-vindos à palestra 17. Nesta palestra veremos construções teóricas de cifras de blocos. Especificamente o roteiro para esta palestra é o seguinte. (Consulte o Tempo do slide: 00 :37) Então, até última palestra vimos que se temos uma função pseudo aleatória, então podemos projetar esquemas seguros de CPA candidatos usando a maioria das operações de funções pseudo aleatórias. Mas agora a questão é como realmente vamos sobre projetar a função pseudo aleatória. E acontece que há 2 formas de projetar funções pseudo aleatórias. A primeira fase, a primeira classe das construções são as construções provavelmente seguras, que nós vamos discutir aqui. E são considerados construções teóricas porque essa não é a forma como instanciamos as funções pseudo aleatórias nos protocolos do mundo real. Nas palestras posteriores, veremos as construções práticas, a saber, as construções que utilizamos em mundo real para instanciar a função pseudo aleatória. No entanto, apesar de não utilizarmos as chamadas instanciações teóricas de funções pseudoaleatórias, elas são muito fundamentais, são de fundamental importância na criptografia porque matematicamente aqui mostramos que as construções que vamos discutir elas podem ser provadas com base na suposição de que uma função só existe. Isso significa que temos agora garantias matemáticas que as construções que vamos ver nesta palestra são seguras, enquanto que as chamadas instanciações práticas que vamos dizer nas palestras subsequentes, para aquelas construções não temos garantias de segurança prováveis que significa que não há prova matemática de que realmente aquelas construções satisfaçam as definições de pseudo função aleatória, pseudo permutações aleatórias e assim por diante. É apenas uma crença ou uma suposição que desde a sua descoberta, nenhum ataque ou nenhuma insuficiência foram relatados naquelas construções. E é por isso que acreditamos que aquelas construções emulam o comportamento de uma função pseudo aleatória, pseudo permutações aleatórias e assim por diante. Por isso, agora voltando para esta palestra, o roteiro para esta palestra é o seguinte: veremos como construir provavelmente funções pseudo aleatórias dadas provavelmente seguras de geradores aleatórios pseudo. Em seguida, veremos as construções de permutações pseudoaleatórias provavelmente seguras a partir de uma função pseudo aleatória provavelmente segura. E essa construção também é chamada de Luby?Construção de Rackoff atribuída ao nome de seus inventores. E, então, finalmente, veremos como construir provavelmente fortes permutações pseudoaleatórias fortíssimas dadas provavelmente seguras pseudo permutação aleatória. (Consulte o Tempo do slide: 02 :59) Então, façamos a primeira coisa aqui. A saber, veremos como se você for dado um gerador pseudo aleatório provavelmente seguro, veremos como construir uma permutação pseudoaleatória provavelmente segura. E, para fins de demonstração, estou assumindo que tenho um comprimento duplicando de pseudo gerador aleatório. E isso você pode construir de maneira provavelmente segura a partir de uma função de mão única usando a construção Goldreich-Levin e assumindo que o predicado hard-core existia. Então, lembre-se em uma de nossas palestras anteriores, tínhamos visto construções provavelmente seguras de pseudo gerador aleatório, em que primeiro expandimos a saída ou a entrada do pseudo gerador aleatório por 1 bit usando predicado hard-core e então fazemos composição serial desse pseudo gerador aleatório polinomial número de vezes para expandir o comprimento do gerador pseudo aleatório aleatório por qualquer tipo polinomial. Assim, assumo que tenho um tal aleatório pseudo gerador, a saber, um comprimento dobrando pseudo gerador aleatório e o meu objetivo é basicamente construir PRF:. A construção é chamada de construção de árvores. E a razão pela qual é chamada de construção de árvore é que basicamente a maneira como definimos a função chaveada Fk é que construímos uma árvore binária completa de profundidade composta por 2nleaf nodesonde cada nó folha vai consistir de uma cadeia pseudo aleatória de comprimento 2n bits determinado pelo valor da chave subjacente k. Agora, a razão pela qual vamos construir uma árvore binária completa de profundidade n é que vamos ter 2nleaves e cada nó da folha é basicamente um valor da função Fk. E esta combina com a nossa semântica da função chaveada Fk que estamos interessados em construir porque o tamanho do bloco da minha função chaveada subjacente que eu quero construir é n bits. Isso significa, a minha função Fk (i) a saber o alcance deste i: 0 ≤ i ≤ 2n-1. Sendo assim, há entradas 2ncandidate para esta função. É por isso que estou interessado em projetar uma árvore constituída por 2nnodes. E o ith value ou o valor da função chaveada Fk na entrada i será basicamente a pseudo string aleatória que Iam vai armazenar no nó da i-ésima folha neste tree.Assim, a coisa toda resume-se a como exatamente esta árvore vai ser definida como uma função do meu chaveamento subjacente k. Então, para fins de demonstração, presumo que eu tenha um gerador de pseudo aleatório. E usando isso eu tenho que projetar uma função pseudo aleatória chaveada,. A construção é a seguinte: portanto, esta é a sua árvore binária completa de 8 nós. Então esta é a sua 0º folha. Esta é a sua primeira folha e esta assim, esta é a sua sétima folha. E isso vai denotar as cordas que vamos armazenar em cada um desses respectivos nós de folhas irá denotar o valor da função F que vamos definir em seus respectivos insumos. Então agora vamos ver o que exatamente serão as cordas de bits que vão ser armazenadas em cada um desses nós internos e os nós de folhas. Então, para começar com na raiz da árvore, vamos armazenar o valor k0k1 que é um pouco string de comprimento 6 bits, e que é gerado chamando realmente o pseudo gerador aleatório sobre a chave k. Por isso, lembre-se k é basicamente a chave da função pseudo aleatória que me interessa projetar, mas agora essa chave eu estou usando como semente para o pseudo gerador aleatório. E já que meu pseudo gerador aleatório expande a semente e me dá uma saída que é duas vezes o tamanho da entrada, obtenho uma saída pseudo aleatória que posso analisar como 2 blocos de 3 bits, 3 bits cada. Agora na minha nota lateral esquerda, que é que com o filho esquerdo dessa raiz, eu basicamente armazenei a saída do pseudo gerador aleatório sobre a entrada k0. Por isso, lembre-se que a string k0k1 é uma cadeia de comprimento 3 bits. Então você tem 3 bits aqui, você tem 3 bits aqui, o primeiro 3 bits parte eu estou denotando como k0, e eu chamo a função G naquela entrada para obter novamente uma nova pseudo string aleatória de comprimento 6bits, que novamente, eu posso dividir em 2 partes. E a criança certa da minha raiz basicamente armazena o valor da saída do gerador pseudo aleatório na string k1, que agora me dará outra pseudo cadeia aleatória de comprimentos 6bits que eu posso analisar como 2 pedaços de 3 bits, 3 bits cada. E então repito este processo na primeira camada desta árvore, isso significa que este nódulo terá agora o resultado do pseudo gerador aleatório sobre os 3 bits k00 como entrada. E esta nota terá a saída do gerador pseudo aleatório sobre a semente k01. E, novamente, obtenho uma saída de 6 bits e assim por diante. Sendo assim, é assim que as notas internas são preenchidas. E similarmente eu preenchi as notas de folhas também usando a mesma lógica para. Como exatamente eu estou indo para a saída de Fk (i)? Então imagine, essa árvore toda é basicamente a definição de Fk. Agora, eu tenho que definir o que exatamente será a saída dessa árvore na minha entrada eu. Então lembre-se, a função chaveada F leva 2 entradas, a entrada de chave e a entrada de bloco real. Por isso, com respeito à entrada chave eu defini uma árvore para ser assim. Agora eu tenho que definir como eu levo a saída dessa árvore para a entrada i. Então imagine por exemplo, eu quero definir ou computar o valor deste tão chamado de função Fk na entrada 3. Assim, 3 em binário podem ser escritos como 011. E basicamente, a ideia é agora eu tenho que apenas passar essa árvore baseada na representação binária de 3.So, eu passo o primeiro bit aqui que é 0, se for 0, a regra é eu ir para a esquerda do meu nó atual, então, eu começo a explorar a partir do primeiro bit é 0 eu vou para a nota esquerda, o bit seguinte na representação binária de 3 é 1. Por isso, a partir da minha nota atual, eu vou para a direita e o último bit na representação binária de 3s são 1. Então, isso significa a partir da minha nota atual, eu vou para a direita e este será o valor da minha função Fk na entrada 3.That é a maneira que eu vou definir a minha função Fk. Portanto, se você ver em um nível muito alto basicamente a forma como a função Fk é definida não é nada além de número polinomial de composições sequenciais do gerador verdadeiramente aleatório. Eu estou basicamente compondo o pseudo gerador aleatório G polinomial número de vezes dependendo da representação binária da minha entrada i. Neste caso a representação binária foi 011.So, estou basicamente invocando a função G três vezes na sequência uma após a outra onde o resultado da chamada anterior de G está servindo como a entrada para a próxima chamada de uma maneira específica. Dependendo da representação binária da minha entrada i, essa é a maneira como você pode interpretar internamente a execução ou a construção dessa função chaveada Fk. (Consulte o Tempo do slide: 10 :49) Agora, você pode estar se perguntando se essa construção é eficiente ou não, pois o tamanho da árvore é exponencialmente grande aqui. Ele consiste em 2n número de nós e onde n é o parâmetro de segurança. Então, isso significa que se eu estou definindo a função Fk assim, então alguém pode sentir que tanto o emissor quanto o receptor têm que manter essa árvore porque uma vez que eles sabem o valor do k eles têm que construir a árvore assim. Porque eles não sabem bem adiantar qual é o valor do i que eles vão usar poderia ser acabar com qualquer um dos nós da folha. Então, eles tinham a árvore toda com eles com antecedência, mas armazenar toda a árvore vai exigi-los quantidade exponencial de computação. Então, intuitivamente, essa construção pode parecer uma construção ineficiente, mas verifica-se que toda a árvore não é computada e armazenada para computar o valor de função discreta na entrada i. Porque dependendo do requisito, isso significa dependendo do valor de i, posso computar a parte real que preciso seguir nesta árvore apenas invocando o meu gerador aleatório de pseudo aleatório n número de vezes. Por exemplo, se eu quiser computar o valor da função Fk (i = 3), o que eu basicamente preciso é de apenas 3 invocações do PRG. Isso é tudo. Eu não preciso das chamadas restantes do PRG.Da mesma forma supor que mais tarde eu estou interessado em computar o valor de dizer Fk (4) portanto, na representação binária é 100, então eu não preciso de toda a árvore. Preciso apenas deste nódulo, a saber, esta invocação do PRG, seguida por esta invocação do PRG, seguida por esta invocação do PRG. Isso significa que cada valor de Fk (i) pode ser apenas computado executando número polinomial de instâncias do gerador de pseudo aleatório subjacente. É por isso que esta construção é computacionalmente eficiente. Ele não demanda quantidade exponencial de computação. Agora, a grande questão é essa construção de árvore, ou essa forma de definir a função chaveada Fk vai de fato me dar um PRG seguro. A resposta é sim. Porque intuitivamente o que é Fk (i), qual é a forma como eu computei Fk (i). Fk (i) você pode interpretar como um número polinomial de composições sequenciais de PRG.Lembre-se, quando estávamos discutindo pseudo gerador aleatório antes, tínhamos proveitantemente que número polinomial de composição sequencial da PRG também lhe dá um pseudo gerador aleatório a saber que a saída será pseudo aleatória e ela será indistinguível do resultado de um gerador verdadeiramente aleatório correspondente. Então, nesse sentido, essa maneira de definir a função Fk com base em uma árvore binária completa é de fato ir definir uma função pseudo aleatória. Mas agora, se eu quiser formalizar essa intuição em uma prova rigorosa, então há muitas sutilezas que estão envolvidas aqui. (Consulte o Tempo do slide: 13 :52) Assim, a prova real é de fato sutil e ela requer muitos tecnicismos avançados. Por isso, devido ao interesse do tempo e já que a prova está realmente fora de alcance deste curso, evitarei os detalhes formais completos da prova. Mas se você está realmente interessado em ver a prova completa, você pode ver a prova disponível no livro de Claude Shannon mas deixe-me discutir a prova geral idea.Então, como eu disse o valor da Fk (i) não passa de número polinomial de invocações do gerador pseudo aleatório. Então, o meu objetivo é basicamente mostrar que, se um adversário interage com o keyedfunction Fk ao pedir número de consultas polinomiais onde não se sabe o valor de k, ele conhece a estrutura da árvore, mas não sabe o valor do k e daí, não sabe quais são os fluxos aleatórios pseudo que são armazenados no indivíduo nodes.Então, imagine se eu tenho um adversário que está interagindo com Fk (i) ou uma função Fk polinomial número de vezes, meu objetivo é mostrar que não deve ser capaz de distinguir o comportamento da construção da árvore a partir do comportamento de uma função verdadeiramente aleatória, mas não posso diretamente reduzir essa indistinguibilidade à segurança da segurança subjacente do gerador pseudo aleatório, pois há número polinomial de invocações do gerador de pseudo-aleatórios que estão envolvidos. Então, o que basicamente nós exigimos aqui é o argumento híbrido. (Consulte o Slide Time: 15 :19) Então, vamos ver a segurança da construção da árvore basicamente, temos uma visão geral da ideia de prova aqui. E para a demonstração da ideia da prova, eu levo o caso onde estou construindo uma pseudo função aleatória, esta foi projetada usando um pseudo gerador aleatório .Assim, conforme a construção de árvore que discutimos há pouco, é assim que a função Fk vai parecer e agora, o que eu vou fazer é comparar essa construção baseada em árvore da função Fk com uma construção alternativa, em que todas as instâncias do pseudo gerador aleatório G vão ser substituídas por um gerador verdadeiramente aleatório G ’ .Então, o que estamos basicamente tentando construir aqui é estamos tentando construir um unkeyed verdadeiramente função aleatória que leva uma entrada de tamanho 3 bits e ele dá uma saída de 6 bits. E em um nível muito alto, a construção é exatamente a mesma que a construção de árvore, exceto que em cada nó todas as chamadas de sua função G são substituídas por G ’. Então, no nó raiz nós apenas chamamos a função G ’ .E já que a função G ’ é um verdadeiro gerador aleatório, ele não leva nenhuma entrada. Apenas dá alguma saída aleatória de 6 bit que será preenchida nesta raiz. Em seguida, quando vamos para o nó esquerdo novamente, invocamos a função G ’, que lhe dará outra sequência de 6 bit, verdadeiramente aleatória. E assim, você pode ver que cada nó que estamos basicamente apenas invocando por função G ’ .E como resultado, cada um desses nós desta árvore, que é construído na parte lateral direita terá 2 valores aleatórios de comprimento 6 bits. Então, foi assim que construímos a função f. Então, agora a construção sábia de diferença entre as 2 funções que construímos é que se quisermos o lado esquerdo k, ele define a sua função Fk. E se eu quiser computar o valor dessa função em alguma entrada, eu digo por exemplo, se eu quiser encontrar o valor dessa função, no seu lado esquerdo na entrada é igual a dizer que todo 0s.Then basicamente eu tenho que seguir o caminho 000 e o valor da minha Fk (i) será o valor armazenado aqui. E dizemos outra mão, se eu quiser computar o valor da função f que eu construí no lado direito sobre a entrada todos os 0s então novamente tenho que seguir como o eu tenho que percorrer ao longo desta árvore conforme a representação binária da minha entrada i e onde quer que eu tenha parado o nó da folha, o valor que é armazenado ali, que será considerado como o valor da função f na entrada i.Então, em termos da forma como estou computando e obtendo a saída da função, ele permanece o mesmo em ambas as funções. O que difere nas 2 funções é que a árvore lateral esquerda, todas as invocações são para um gerador aleatório pseudo e a árvore laterais direita todas as chamadas são para verdadeiro gerador de número aleatório. Agora informalmente, a prova a ideia por trás da segurança da construção de árvore que temos dado é que se a função subjacente G é um PRG seguro, então o que vamos mostrar está na prova de que nenhum distinguidor de tempo polinomial deve ser capaz de distinguir o valor da função, Fk sobre a entrada i do valor da função f na entrada i. Isso significa, não importa se ele interagiu com a construção de árvore no lado esquerdo polinomial do tempo, ou se ele interagiu com a árvore no lado direito polinomial número de vezes, do ponto de vista do adversário, a interação deve ser quase idêntica, exceto com probabilidade desprezível. Se de fato minha função G é um PRG seguro. Então, é isso que é basicamente a ideia geral da prova. (Consulte o Tempo do slide: 19 :39) É o que eu tenho que mostrar. E a ideia por trás de uma prova aqui é nós basicamente definimos n + 1 árvore binária completa, cada uma de profundidade n, onde cada nó vai armazenar strings de bit 2n, mas de uma maneira diferente. Então, comecemos com a árvore T0, que na verdade é uma árvore de profundidade em completa árvore binária de profundidade n onde cada um dos nós consiste basicamente de uma cadeia uniformemente aleatória de 1 n. E isso não é nada além do modo como uma função verdadeiramente aleatória f vai se comportar conforme a construção da árvore e a minha i-ésima árvore i será a seguinte. Na minha i-ésima árvore Ti, os primeiros níveis n-i, todos os nós naqueles níveis n -i consistirá de verdadeiras cadeias aleatoriais uniformemente uniformemente, enquanto todos os níveis restantes serão constituídos por sequências pseudo aleatórias aplicando o mecanismo chave ou a construção chave para o nódulo no nível anterior. Se eu for para a tecla i = a maneira como ele difere da i-ésima chave é que ele terá uma camada a menos de sequências aleatórias pseudo aleatórias e uma camada a mais de sequências aleatórias pseudo em comparação com a sequência anterior. E também sabemos que como podemos construir um eficiente esquema de criptografia segura de CPA a partir de PRFs usando modos de operação. Mais tarde neste curso, vamos ver que como podemos de fato construir mais poderoso processo de criptografia simétrica a saber, criptografia autenticada e criptografia segura CCA apenas usando funções pseudo aleatórias. Então, verifica-se que tudo só depende da existência de uma função de maneira que significa se você deseja construções provavelmente seguras de esquema de criptografia segura CPA, provavelmente seguro, seguro CCA, provavelmente seguro autenticado esquema de criptografia autenticado, então ele emite para apenas ter uma função de forma. Isso significa que basta você ter apenas uma função única você pode obter tudo de graça. E mais adiante neste curso, quando discutiremos a criptografia de chave pública, veremos que como exatamente podemos ir sobre e construir funções de uma forma baseada em premissas de dureza teóricas específicas de número específico. Então, tudo se resume à existência de funções de mão única. Então, isso me leva até o final desta palestra. Só para resumir nesta palestra, tínhamos visto uma visão geral de alto nível de como damos construções provavelmente seguras de pseudo função aleatória, permutação pseudoaleatória e forte competição aleatória. Obrigado!