Loading
Nota de Estudos
Study Reminders
Support
Text Version

Construções Genéricas de Protocolo de Troca de Chave

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

    +

37Foundations de CryptographyDr. Ashish ChoudhuryDepartamento de Ciência da ComputaçãoInstituto Internacional de Tecnologia da Informação – BangalorePalestra -37Principais Protocolos de Intercâmbio Parte II(Consulte O Slide Time: 00:28)Olá a todos, bem-vindos a esta palestra. Bem só para relembrar na última palestra que tivemos apresentou o problema de troca de chave e temos visto várias noções de segurança e temos também visto a ideia envolvida por trás do Diffie – Hellman Key Exchange Protocol Embora, nós ainda não tenhamos visto os detalhes matemáticos exatos, mas vimos como dado algumas funções especiais de E e F como podemos projetar o Diffie – Hellman Key Exchange Protocol. Agora o que vamos fazer aqui é vamos continuar nossa discussão sobre os principais protocolos de troca e veremos construções genéricas de protocolos de troca de chave a saber: veremos construções baseadas em funções de trapdoor unidirecionais que são muito simpáticas primitivas ou primitivas criptográficas fundamentais que são mais potentes do que a noção de funções unidirecionais.(Consulte o tempo de deslizamento: 01:18)Então o que exatamente são funções de trapdoor unidirecionais? Por isso, antes de ir para a definição de uma forma funções de trapalheiro deixe-nos primeiro relembrar a definição de função de sentido único ou OWF. Portanto, uma função de sentido único F é uma função publicamente conhecida, uma função determinística do domíniox para o co-domínio y e os requisitos a partir desta função unidianal, são que ele deve ser fácil de computar para qualquer valor x do domínio x. Considerando que deve ser difícil inverter em tempo polinomial qualquer entrada aleatória do intervalo conjunto de f que significa se alguém me der um y que pertence ao intervalo de f e y é aleatoriamente escolhido do que em polinO deve ser difícil chegar a algum ao menos uma imagem para esta entrada de y. Agora o que exatamente é uma função de trapdoor de sentido único certo. Por isso soa como um tipo especial de função.E realmente é um tipo especial de função unidireta que também possui uma informação do trapdoor associado e o que exatamente esta informação do trapdoor vai te ajudar com bem ela ajuda você a inverter qualquer entrada do conjunto de intervalo da função f proporcionado você tem o conhecimento das informações do trapdoor que significa qualquer entidade que saiba a descrição dessas informações do trapdoor então ele pode facilmente inverter a função f em qualquer aleatório y do conjunto de intervalos de f. Mas na ausência das informações do trapdoor a função parece uma função unidireta para aquela entidade que não seria possível para aquela entidade que não processa essa informação do trapdoor para inverter esta função f em qualquer aleatório y do conjunto de intervalo da função f.(Consulte o Tempo do slide: 03:00)Então agora vamos tentar afirmar formalmente este requisito o que exatamente significamos por esta informação de trapdoor especial e é fácil inverter na presença das informações do trapdoor e difícil de inverter na ausência da informação do trapdoor. Por isso, quando dizemos que temos um esquema de função trapdoor T então ele passa por cima de um par de conjuntos finitos onde x será domínio da função e y será co-domínio da função.E quando dizemos um esquema de função de trapdoor basicamente nós significamos um triplet de algoritmos todos polytime algoritmos, polinomial em algum parâmetro de segurança o primeiro algoritmo é o algoritmo de geração de ou basicamente o algoritmo de geração de parâmetros (Gen) e a função f é a função neste contexto subjacente será uma função unidireia e correspondente à função f temos uma inversão função (Inv). Então sintaticamente o algoritmo de geração de parâmetros ou o algoritmo de geração de chaves é um algoritmo randomizado que não leva nenhuma entrada explícita, mas internamente ele tem alguma aleatoriedade interna de ele gera moedas aleatórias internas e com base no valor de moeda aleatória ela saída um par de chaves ou par de valores que eu denote por pk e sk. Por isso, o pk vai ser a chave pública que estará disponível no domínio público.E sk é a chave secreta que será conhecida ou que estará disponível apenas com algumas entidades designadas . Agora o que é uma função f? Bem é uma função do set x para o set y. Então, é uma função parametrizada por um pk de chave pública para que qualquer pessoa possa avaliar esta função desde que saiba da descrição da função e da descrição do pk de chave pública e a função tome duas entradas explícitas. A Saber a entrada x na qual a função precisa ser avaliada e a chave pública e ela lhe dá uma saída que eu denote por y e este y será um elemento do conjunto de domínio do co y e é um algoritmo determinístico que significa toda vez que você avaliar esta função f com a mesma entrada x e com o mesmo pk de chave pública você obterá a mesma saída y.Não há aleatoriedade que esteja ali como parte do algoritmo. Agora o algoritmo inverso ele também é uma função de entrada de 2 ele tira uma entrada y do conjunto y que queremos inverter e a chave secreta sk que significa esta função pode ser invocada apenas por uma entidade que possui a chave secreta que realmente em nosso contexto é uma informação de trapdoor. Se você não tiver a chave secreta ou as informações do trapdoor, então você não seria capaz de invocar esta função.Então, assumindo que entidade, uma entidade que conheça a entrada y na qual esta função Inv tem que ser invocada também conheça as informações do trapdoor, ele executa a função com esta entrada sk e y e ele vai obter uma saída x ou um bot de símbolo de status especial que denota uma entrada de inválida de entrada. Portanto, se a saída desta função inversa não for bot então ele vai ser um elementodo domínio da função f.Namely ele vai ser elemento de x enquanto que se a saída for bot então ele indica uma entrada inválida e veremos em breve o que exatamente significamos por uma entrada inválida com relação ao contexto subjacente e esta função inversa sempre vai ser algoritmo determinístico que significa se você invocar esta função inversa com a mesma y e a mesma chave secreta sk então você vai obter a mesma saída novamente e novamente. Agora quais são as propriedades que exigimos a partir desta função de trapdoor unidiretal? A primeira propriedade é a propriedade de correção que estabelece que para cada par de parâmetros ou chaves pk, sk gerado pelo seu algoritmo de geração de chaves e para cada entrada x do seu domínio da função f se você invocar a função na entrada x com relação a pk-chave e a saída resultante é dizer que é indicada como y.E então se você tentar chamar a função Inv na entrada y e com a chave secreta sk ou o trapdoor information sk então a saída deve ser a mesma entrada x e esta deverá guardar para cada pk, sk gerada por sua geração de chave ou geração de parâmetro algoritmo. Agora observe que assim que afirmar este requisito de correção significa automaticamente que sua função f que está lá como parte do seu esquema de função trapdoor tem que ser uma função de um-para-uma.Isso significa se você tiver 2 entradas distintas x1 e outra entrada x2 onde x1 não é igual a x2direito e se você tentar avaliar a função fpk na entrada x2 e na entrada x2 você não pode obter a mesma saída y porque se ambos x1 e x2 obtém mapa para a mesma saída y sob a função fpk então o que acontece quando você tenta inverter a entrada y com a chave secreta sk. Você pode obter x1 com alguma probabilidade você pode conseguir voltar x2 com alguma probabilidade.Mas isso estritamente vai contra o requisito de correção, o requisito de correção diz que você deve obter de volta a entrada exata com a qual você avaliou a função fpk e então tente executar o algoritmo inverso inequivocamente e isso é garantido apenas se o seu fpk de função é uma função de um-para-uma. No entanto, notou que mesmo que a fpk da função seja uma função de um-para-uma que não significa que a função tenha que ser um mapeamento. Pode haver várias entradas possíveis do seu conjunto de co-domínio y que podem não ter uma imagem presob a função f e é por isso que temos uma disposição especial para a saída da função inversa ser um símbolo de bot porque se estamos tentando chamar a função Inv em algum elemento y que não tem uma pre imagem que significa que este y não é um elemento do conjunto de gama de sua função f.Então devemos obter o bot output indicando que estamos tentando inverter algo que não tem direito de pré-imagem correspondente. Portanto, essa é uma definição de trapdoor de sentido único função. (Consulte Slide Time: 09:42)Então, vimos o requisito de correção agora temos que modelar a propriedade One-Waynesse lembrar a propriedade One-Wayness requer que qualquer entidade que possua a chave secretaou as informações do trapdoor devem ser capazes de inverter a função ou computar a saída da função Inv em qualquer y do conjunto de intervalo da função f, mas na ausência de a informação do trapdoor deve ser computacionalmente difícil de computar a saída da função inversa em qualquer y pertencente ao conjunto de intervalos da função f direito. E isso deve se manter mesmo que aquela entidade ou aquele algoritmo adverserie conheça a descrição de a chave pública ou pk de chave pública. Então, vamos tentar modelar esse requisito por um experimento que chamamos como um Invert?, f n experimento. Este experimento é quase o mesmo da maneira como experimento que usamos para modelar uma propriedade One-Wayness para função unidireta que faz não ter uma informação de trapdoor associada a ele.Mas agora terá algum requisito de segurança diferente aqui ou a saída do experimento é definida de uma maneira diferente e regras do experimento também são ligeiramente diferentes aqui. Portanto, o que se sabe publicamente é a descrição de um esquema de trapdoor a saber, o triplet de algoritmo (Gen, f, Inv) e o domínio e co-domínio da função f. Agora o desafio é gerado para o adversário é o seguinte.O desafiador do experimentador executa o algoritmo de geração de parâmetro para obter o par de chave pública e a chave secreta e ele escolhe um x aleatório do domínio da função fe o desafio lançado para o adversário são os seguintes. A chave pública é dada a o adversário e o valor da função f na entrada aleatória x a saber de y também é dado como um desafio para o adversário.E o objetivo do adversário é basicamente computar a imagem prévia deste y sem saber a chave secreta correspondente ou as informações do trapdoor sk. Portanto, basicamente adversário após quantidade de tempo polinomial vai indo para a saída de alguns x ’ do domínio da função f e dizemos que a saída do experimento é 1, significando que o adversário ganhou o experimento se e apenas se adversário A é capaz de vir corretamente a entrada x que deu a saída y. E minha definição de segurança é dizemos que uma função f que faz parte do seu esquema de função trapdoor é unidiremente se para qualquer adversário politime quem participa deste experimento há alguma função insignificante no parâmetro de segurança tal que a probabilidade de que o adversário vencer este experimento é superior delimitado por alguma função insignificante onde a probabilidade é tomada sobre a escolha aleatória do experimento.Namely a aleatoriedade envolvida na geração dos parâmetros pk, sk e a aleatoriedade utilizada para a seleção do valor de x aqui direita. Então basicamente a essência desse experimento é o desafio para o adversário é chegar com um certo x mesmo sem saber sk e segurança definição exige que se o adversário não souber as informações do trapdoor ou o segredo key sk então exceto com alguma probabilidade muito pequena ele deve ser computacionalmente difícil paraum adversário de politime vir a tona com um x correto. Na definição não vinculamos uma probabilidade de sucesso do adversário ganhar o experimento para ser 0 porque sempre há uma estratégia de adivinhação pelo adversário que pode simplesmente adivinhar algum aleatório x ’ do set x e com alguma probabilidade diferente de zero pode acontecer que um adivinhe x ’ de fato acaba sendo o x correto. Assim, o melhor que podemos esperar é que qualquer adversário de politime não deve ser capaz de fazer nada melhor do que adivinhar o aleatório x em que a função f é avaliada para computar o desafio y.(Consulte o Tempo do slide: 13:34)Agora uma vez que temos a definição de função de trapdoor unidireta deixe-nos definir uma noção relacionada a saber: Permutação do trapalhar unidireito OWTP direito. Portanto, a permutação do trapdoor unidirecional é um tipo especial de função de trapdoor unidirecional onde o domínio e o co-domínio de sua função f são os mesmos a saber o conjunto x e o conjunto y são iguais e este automaticamenteimplica que sua função fpk é um-para-um sobre mapeamento que significa que é uma função de trapdoor unidirecional então a propriedade de correção unidirecional então a propriedade de correção de implica que sua função f tem que ser uma função de um-para-uma mas ela precisa denão estar em função, mas assim que eu garantir que o meu domínio e o co-domínio são iguais e se ambos co-domínio e domínio são conjuntos finitos o que de fato vai ser caso para a construção que veremos mais adiante. Então se o meu x e y são iguais e eles são finitos e se minha função é um mapeamento um-para-um então ele automaticamente implica que a função também é sobre mapeamento, isso significa para cada x eu vou ter uma imagem exclusiva e eu não posso ter 2 diferente x mapeamento para o mesmo y e para cada y do conjunto y eu vou ter um distinto x tal que f (x) teria me dado aquele y. Isso automaticamente significa que se eu estiver considerando permutação de sentido único então a saída da minha função inversa nunca poderá ser um bot porque realmente eu vou invocar o meu algoritmo inverso em alguma entrada y pertencente ao conjunto y então já que minha função é uma função invertível ou ela é um-para-um no mapeamento eu sempre vou obter um elemento x pertencente ao domínio da função f a saber x. Por isso, bot não pode ser um resultado possível aqui. Sendo assim, essa é a única diferença para o caso de permutação de trapdoor unidiretal. (Consulte Slide Time: 15:30)Então agora assuma pelo momento que você tenha dado uma função de trapdoor de candidato nós ainda não vimos como se realmente ainda não vimos um trapdoor de candidato único função mais tarde em quando introduziremos o número teortico de número teóricos e número teorético Nós veremos exemplos de função de trapdoor unidireta, mas para o momento assumimos que você recebe uma função de trapdoor unidireia veremos como usando essa função de trapdoorpodemos projetar um protocolo anônimo chave de troca de chave anônima alcançando a noção de fraco privacidade. Então o que é conhecido publicamente é uma descrição do esquema de função de trapdoor único sobre alguns conjuntos finitos x, y e o objetivo aqui é projetar um protocolo de troca de chave a saber de um par de protocolos um para o emissor e um para o receptor atingir a noção de privacidade fraca onde usar este esquema de função de trapdoor unidireito e um esquema resultante vai ser um elemento deste conjunto y. E a partir da descrição da função de trapdoor unidireta qual exatamente a função de trapdoor de unidireço faz: permite que qualquer pessoa compute a função f, mas até e a menos que outra parte possui a informação do trapdoor não seria possível inverter a saída da função f. Então agora com base nessa intuição é muito simples chegar a um protocolo de troca de chave .Então o protocolo Π S e Π R para o remetente e o receptor, respectivamente, serão os seguintes. O que o receptor pode fazer aqui é ele pode executar o algoritmo de geração de parâmetros do esquema de funções do trapdoorde unidireia e obter o par de chave pública e chave secreta e ele pode dar a descrição da chave pública para o remetente aqui certo e uma vez que o remetente souber a descrição da chave pública o que ele faz é: é preciso o aleatório x do domínio da função f e ele sabe a descrição da função f e ele agora conhece o pk de chave pública. O que ele pode fazer é apenas pode avaliar a função f usando o pk da chave e a entrada x e obter uma saída y que ela comunica ao receptor. Agora o que o receptor pode fazer é uma vez que o receptor possui a chave secreta ou as informações do trapdoor sk, ele pode computar a saída da função inversa na entrada y sob a chave sk e pode obter o mesmo x com que foi usado pelo emissor para computar uma saída y e tanto emissor quanto receptor podem agora saída um valor comum ou uma chave comum a saber x. Agora a correção desse protocolo de troca de chave automaticamente segue a partir da propriedade de correção de seu esquema de função trapdoor de unidirecional direito. Porque desde que estamos no mundo passivo uma cópia do pk que foi comunicada pelo receptor para o remetente será uma cópia autenticada será a mesma pk que receptor gerou e correspondente sk é usado pelo receptor para computar o inverso de sob a chave secreta sk: Invsk (y). Assim, a correção de todo esse protocolo chave de troca de chavesegue a partir da propriedade de correção de seu esquema de função de trapdoor subjacente.E uma privacidade fraca de todo este protocolo de troca de chave segue a partir da propriedade One-Wayness da função subjacente f. Por isso, se temos um tempo polinomial eavesdropper que eavescai a comunicação e tirar a transcrição do protocolo para que exatamente seja o protocolo transcrição para o adversário. Do ponto de vista do adversário é um pk aleatório cujo correspondente informação de trapdoor não é conhecido do adversário.E o adversário está agora vendo o valor y que é a saída da função fpk em algum aleatório x onde o aleatório x não é conhecido do adversário e a exigência de fraca privacidade é que o resultante x que é a saída para o emissor e receptor aqui não deve ser conhecido na sua totalidade para o adversário. Não estamos mirando aqui para a indistinguibilidade definição de sigilo baseado.Na verdade estamos mirando para todos ou nada tipo de exigência de segurança aqui porque estamos em a configuração de privacidade fraca aqui. Portanto, se em todo o tempo de polinomial adversário ao aprender o pk de chave pública e uma saída de função y pode vir a tona com x em polenar com significativa probabilidade então significa que temos uma instância da privacidade fraca ou o experimento de Invert onde um adversário de politime pode ganhar aquele experimento com probabilidade de não desprezível o que vai contra a suposição de que o esquema de função trapdoor é um esquema de função de trapdoor de uma via. Assim, somente com probabilidade insignificante este eavesdropper polytime poderia vir à tona com o correto x, caso contrário o x não será conhecido do adversário e que garante que este protocolo de troca chave é de fato lhe dá a noção de privacidade fraca. Então isso me leva ao final desta palestra. Só para resumir nesta palestra introduzimos uma noção de função trapdoor de sentido únicoe introduzimos também uma noção de permutação de trapdoor unidireta. Função unidireta é um tipo especial de função unidireta que é fácil de inverter em qualquer aleatório ou qualquer valor a partir do co-domínio ou do conjunto de intervalo da função desde que tenha uma informação de trapdoor especial, mas na ausência de informações de trapdoor é muito difícil de inverter qualquer entrada aleatória do conjunto de intervalos da função e vimos que se você estiverdada uma função de trapdoor candidato unidireta então podemos projetar um protocolo de troca de chave alcançando a noção de privacidade fraca. Obrigado.