Loading
Nota de Estudos
Study Reminders
Support
Text Version

Premissas De Dureza Criptográfica

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 da Cryptography Dr. Ashish Choudhury Department of Computer Science International Institute of Information Technology – Bangalore Lecture-39 Cryptographic Hardness Supostos in the Cyclic Groups Olá todos, bem-vindos a esta palestra. Só para relembrar na última palestra nós tínhamos visto as ideias subjacentes que estão envolvidas no Diffie – Hellman Key Exchange Protocol. No entanto, ainda não tínhamos visto os passos exatos do Diffie – Hellman Key Exchange Protocol. (Consulte Slide Time: 00:42) Então nesta palestra introduziremos várias suposições de dureza criptográficas no contexto de grupos cíclicos a saber: assunção de log discreto, Diffie computacional – Hellman assunção e decisional Diffie – Hellman assunção e então com base nessas suposições veremos os passos exatos do Diffie – Hellman Key Exchange Protocol. (Consulte O Slide Time: 01:00)Então, vamos começar primeiro com o problema de log discreto e a suposição de log discreta. Por isso, o problema de log discreto é basicamente que você tem que computar eficientemente o log discreto de um elemento de grupo aleatório onde você é apenas dada a descrição do gerador e um elemento aleatório do grupo. Sendo assim, isso é modelado por um experimento aqui que tocou entre um adversário computacionalmente delimitado e um verificador hipotético do experimento. Onde a descrição do grupo cíclico é divulgada e o que eu quero dizer com a descrição do grupo cíclico é que você conhece a operação de grupo subjacente que está lá no grupo e o tamanho do grupo a saber, o número de elementos e o gerador porque você recebe um grupo cíclico e assumimos aqui que a esta notação (| |q| |) barra dupla esta notação significa basicamente que os números de bits que exigimos representar o valor q é n. Ou seja, significa que cada elemento do grupo G requer n número de bits para a representação e também assumimos que temos algoritmos de polítime para realização de operações de grupo e exponenciação e tempo de polinização em que o polinomial no número de bits que você leu para representar o valor q. Assim, os passos ou as regras do experimento como está a seguir. Assim, o desafiante ou o experimento escolhe um índice aleatório α na faixa de 0 a q – 1. E uma vez que ele escolhe o índice α ele computa o valor u que é g α e dá-o ao desafiante. Por isso, antes de prosseguir aqui eu gostaria de ressaltar que todo esse experimento esse experimento de log discreto eu estou formulando assumindo uma representação de grupo multiplicativo, mas você pode imaginar que o experimento correspondente também está lá para um grupo cíclico de grupo onde a operação subjacente é aditiva. Assim, uma vez que o índice α é escolhido aleatoriamente do conjunto 0 para q – 1 que automaticamente significa que o elemento u que é lançado como um desafio ao adversário é também um elemento de grupo aleatório ok e agora o desafio para o adversário é descobrir o log discreto de u a saber o valor α. Assim, tem de saída um valor α’ e na faixa de 0 q – 1 e as regras do experimento dizem que dizemos que o adversário venceu o experimento ou a saída do experimento é 1 se e somente se o α’ qual adversário apresentou realmente é um log discreto do valor u, a saber se g α’ = u mantém e dizemos que a discreta assunção de log segura no grupo (G, o) se para cada adversário de politime participante neste experimento há alguma função insignificante tal que o adversário de probabilidade vence o experiência ou a saída do experimento é estofada por aquela função insignificante e ali verifica-se que existem vários grupos de candidatos, onde realmente a discreta assunção de log acredita-se fortemente. Eu ressalto que só se acredita que nesses grupos candidatos o problema de log discreto é de fato difícil de ser resolvido, mas ainda não está provado formalmente que significa ao longo dos últimos 30, 40 anos mesmo depois de realizar pesquisas rigorosas ninguém é capaz de apresentar algoritmo de polítime ou algoritmo eficiente que possa solucionar ou computar um log discreto para elementos escolhidos aleatoriamente desses grupos candidatos. É por isso que acreditamos fortemente que o problema de log discreto é de fato duro nesses grupos e é por isso que chamamos todo esse problema como a suposição de log discreta. (Consulte Slide Time: 04:42)Agora vamos ver uma assunção relacionada a qual chamamos como Diffie computacional – Hellman assunção ou CDH assunção e para isso vamos introduzir primeiramente a noção de Diffie – Hellman function. Por isso, imagine que nos seja dada a descrição de um grupo cíclico onde o gerador g é conhecido e o tamanho do grupo é q e dizem que somos dados elementos u e v do grupo. Eu imploro seu perdão, a função Diffie – Hellman da entrada u, v com relação ao gerador g DH   é definido como sendo o valor g para o log discreto de u multiplicado por log discreto de v: (DLog). Novamente esta função Diffie – Hellman é definida assumindo que a operação do grupo subjacente é multiplicativa, mas você pode imaginar a função Diffie – Hellman correspondente, onde a operação subjacente no grupo é uma operação aditiva. Se você olhar de perto então a maneira como definimos esta função Diffie – Hellman então acontece que desde u e v são elementos do grupo então u pode ser expresso como alguma g α. E da mesma forma o elemento v pode ser expresso como algum g β que significa se eu disser a maneira como o Diffie – Hellman função na entrada u, v não é nada, mas g para o poder o log discreto de (g α β). Agora o que exatamente é o problema computacional Diffie – Hellman problema ou CDH bem o problema aqui é que você recebe a descrição de um grupo cíclico e o gerador e recebe-se um par de elementos escolhidos aleatoriamente do grupo e o desafio ou o problema que estamos interessados em resolver é computar o Diffie – Hellman funciona com relação a esses pares de entradas. E a assunção CDH basicamente afirma que existem grupos de candidatos ou existem um grupo onde o problema da CDH é de fato difícil de ser resolvido em quantidade de tempo polinomial. Por isso, formalmente modelamos esse requisito por um experimento que chamamos como experimento CDH jogado entre um adversário computacionalmente delimitado e um experimento ou um verificador o que é divulgado publicamente é a descrição do grupo, a operação do grupo, o gerador e o tamanho do grupo. E assumimos que o número de bits que precisamos para representar o valor q é n, onde n é parâmetro de segurança. As regras do experimento são as seguintes. O desafio prepara o desafio para o adversário, escolhem índices aleatórios α, β na faixa de 0 q – 1 e computa o elemento g α e g β. Então você pode estar se perguntando que é eficiente para computar. É sabido como eficiência computar g α, g β se dado α e β e g sim ele acaba a resposta é sim é isso que eu estou assumindo aqui que para o grupo subjacente temos algoritmos de polítime para realizar a exponenciação do grupo devido a falta de tempo eu não estou discutindo aqueles algoritmos exatos como computar g α em poltica de n quantidade de tempo. E você pode ver o livro de Katz & Lindell ou qualquer referência padrão em que você possa ver os detalhes de como exatamente computar ou realizar a exponenciação de grupo em quantidade de tempo polinomial. Por isso, uma vez que o experimento ou o desafiante tenha preparado ou computado os elementos u, v o par (u, v) é lançado como um desafio para o adversário e o desafio para o adversário é computar a função Diffie – Hellman neste par de entrada (u, v). Assim, uma vez que aquela saída da função Diffie – Hellman também vai ser um elemento de grupo basicamente o adversário tem que submeter um elemento ou saída um elemento do grupo que eu denote como esta wand as regras do experimento diz que dizemos que o adversário venceu o experimento ou a saída do experimento de CDH é 1 se e somente se a saída enviada pelo adversário é exatamente a mesma que o valor da função Diffie – Hellman no par de entrada (u, v) a saber, é igual a g α β. Então isso significa que o desafio aqui para o adversário é computar g α β sem realmente saber α e β que são escolhidos aleatoriamente pelo desafiante aqui e o pressuposto de CDH diz basicamente que dizemos que a assunção CDH se mantém no grupo (G, o) se para cada adversário de politime participar deste experimento com relação ao grupo (G, o) a probabilidade de que o adversário possa vencer este experimento ou resolver o problema de CDH é superior delimitado por alguma função insignificante no parâmetro de segurança. E acontece que há vários grupos de candidatos onde a assunção CDH acredita fortemente ser verdadeira outra vez eu ressalto que só acreditava fortemente que não existe um adversário politemporal que possa resolver de forma significativa, quem pode resolver o problema da CDH com probabilidade significativa, mas ainda não se provou formalmente que é apenas uma suposição. Ao longo de um período de tempo mesmo após tentativas rigorosas nenhum algoritmo de polítime foi obtido. E é por isso que acreditávamos que nesses grupos candidatos o problema da CDH é de fato difícil de ser resolvido e é por isso que dizemos que nesses grupos candidatos a assunção CDH se mantém. (Consulte O Slide Time: 09:54) E finalmente nos deixe ver outro problema ou assunção relacionado que chamamos como DDH ou decisional Diffie – Hellman assunção e para isso deixe-me introduzir a definição de Diffie – Hellman triple. Assim, um tripleto de elemento do grupo que eu digo denotam como g α, g β e g γ é chamado como Diffie – Hellman triple if γ = produto de α e β. Novamente esta definição de Diffie – Hellman triplet é com relação a um grupo cíclico onde a operação subjacente em multiplicativa, mas esta definição pode ser modificada com relação a um grupo cíclico onde a operação subjacente é a operação de adição. Agora o problema do DDH é para distinguir eficientemente um triplet de Diffie escolhido aleatoriamente a partir de um triplet aleatoriamente escolhido sobre o grupo. Isso significa que um adversário ou um algoritmo receberá um triplet que poderia ser um triplet Diffie – Hellman ou pode ser um triplet arbitrário escolhido aleatoriamente e ele tem que distinguir se está vendo um triplet de Diffie – Hellman triplet ou um triplet escolhido aleatoriamente e este requisito é formalizado por um experimento que chamamos como experimento DDH e o experimento é jogado entre um adversário computacionalmente delimitado e desafiador arbitrário ou o experimento onde a informação pública que está disponível é a descrição de um grupo cíclico a saber, a operação o o tamanho do grupo e o gerador e o desafio para o adversário é preparado da seguinte forma. O desafiante escolhe alguns índices aleatórios α, β, γ uniformemente aleatoriamente no conjunto 0 ao q -1 e computar os primeiros 2 componentes do triplet que vai ser lançado como um desafio ao adversário. A saber, u é computada como g α e v é computada como g β. Já que α e β são escolhidos aleatoriamente ela implica automaticamente que os elementos u e v também são elementos aleatórios do grupo e agora para gerar o terceiro componente do desafio que vai ser lançado para o adversário o desafiante escolhe ou lança uma moeda uniformemente aleatória com probabilidade metade poderia ser 0 com provavelmente a metade poderia ser 1. Se a moeda tosca é 0 então o terceiro componente do triplet a saber de w é g γ que significa w é um elemento uniformemente aleatoriamente independente de u e v enquanto que se a moeda toss for 1 então w is set to be g α β e agora uma vez que o w é decidido o triplet u, v, w é lançado como um desafio para o adversário e o desafio para o adversário é decidir ou distinguir se está vendo um triplet Diffie – Hellman. Ou se está vendo um triplet verdadeiramente aleatório sobre o grupo; isso significa que tem que identificar se o triplet u, v, w é gerado de acordo com o método b = 0 ou se é gerado de acordo com o método b = 1 portanto adversário submete a sua resposta a saber-se saída um bit b’ e as regras do experimento e a definição do experimento é que dizemos que adversário venceu a experiência ou a saída do experimento é 1, se e somente se o adversário é corrigível para identificar se viu um triplet pelo método b = 0 ou pelo método b = 1 a saber-se identificou corretamente b’ = b e dizemos que a assunção de DDH se mantém no grupo (G, o) se para cada adversário de politime participante dessa experiência existirem alguma função insignificante tal que a probabilidade de que a saída de experimento DDH seja de 1 com relação a esse adversário é superior delimitado pela metade + insignificante. Portanto, observe que para o experimento DLog e para o experimento de CDH a definição foi que a saída do experimento é 1 deve ser superior delimitado por alguma função insignificante porque lá o objetivo do adversário era não distinguir algo versus algo. Se o desafio para o adversário era computar alguma coisa, mas neste experimento DDH ou neste problema DDH o objetivo do adversário é distinguir um tipo de triplet contra outro tipo de triplet. E é por isso que estamos dando uma definição de tipo indistinguível e é por isso que a definição é que dizemos que a assunção DDH se mantém apenas se nenhum adversário de politime pode distinguir um triplet de Diffie – Hellman triplet de um triplet não Diffie – Hellman triplet exceto com provavelmente metade + insignificante. Equivalentemente a mesma condição pode ser colocada desta forma. Podemos dizer que a assunção de DDH se mantém no grupo se não importa se o tripleto que é lançado como um desafio a esse adversário é gerado pelo método b = 1 ou pelo método b = 0. A resposta do adversário é quase idêntica a saber dizer b’ = 1 em ambos os casos, exceto com alguma probabilidade insignificante e pode ser provado que ambas as condições são equivalentes umas às outras. Novamente acontece que há vários grupos de candidatos onde o pressuposto DDH é fortemente acreditado para ser verdade e mais uma vez eu ressalto que só se acredita fortemente que naqueles grupos a assunção DDH ou o problema DDH é difícil de resolver não é matematicamente provado. É só porque não temos nenhum algoritmo de polítime até agora para resolver o problema do DDH nesses grupos é por isso que acreditamos que o problema do DDH é de fato difícil de ser resolvido nesses grupos de candidatos. (Consulte O Slide Time: 15:26) Então agora vamos ver a relação entre a suposição DLog, Assunção CDH e assunção DDH. Por isso, para sua referência escrevi o experimento para a assunção de DLog com assunção de CDH e DDH assunção e em todas essas experiências a informação pública é a descrição de um grupo cíclico novamente pela simplicidade assumo que a operação subjacente é operação multiplicativa. O tamanho do grupo é q e o gerador é g que é conhecido publicamente e um número de bits que é usado para representar o valor q é n e eu uso a notação Zq para denotar o conjunto 0 para q – 1 direito. Por isso, em todo esse experimento sempre que o desafiante foi escolher ou tentar gerar um elemento uniformemente aleatório do grupo foi basicamente escolher um índice aleatório do set 0 para q – 1. Todos aqueles passos onde o desafiante estava escolhem um índice aleatório do set 0 para q – 1 podem ser representados como se o desafiante estivesse escolhando um índice aleatoriamente a partir do conjunto Zq. Por isso, agora vamos ver pela primeira vez a relação entre a assunção DLog e a assunção CDH. Acontece que se a assunção CDH se mantém no grupo G então ela implica que a assunção DDH também se mantém nesse grupo. Coloque de outra maneira se você ver o contrapositivo dessa implicação se o problema DLog for de fato fácil de resolver computacionalmente fácil de resolver no grupo então usando esse algoritmo ele é muito fácil para qualquer adversário de politime também para resolver o problema de CDH também nesse grupo porque se você pode computacionalmente resolver se você pode computar o DLog de um elemento aleatório em tempo de polia e então se você usar esse algoritmo no experimento de CDH, então usando esse algoritmo, o adversário, A pode computar o DLog de u e ele pode computar o DLog de v a saber que pode extrair os valores α e β em poltica quantidade de tempo e uma vez ele conhece α e β então ele mesmo pode computar g α β corretamente. Isso significa que será de fato a saída do Diffie – Hellman função no par aleatório de entradas u, v. Isso significa que se o problema DLog é fácil então é o problema de CDH. Assim, isso prova a implicação na primeira direção. Agora o que dizer sobre a implicação na outra direção inversa que significa podemos dizer que se a assunção de DLog se mantém no grupo então também implica que a assunção CDH se mantém no grupo também e curiosamente a resposta é que não sabemos nada sobre este fato. Na verdade, nós acreditamos fortemente que pode haver grupos onde o problema da CDH é mais fácil de resolver mesmo que o problema da DLog seja difícil de ser resolvido. A razão para isso é que se você ver a descrição do experimento de CDH do problema de CDH o objetivo do adversário é computar g α β onde ele não conhece α e β. Uma forma de computação g α β poderia ser computar α da u e β a partir de v a saber de resolver o problema de log discreto, mas essa necessidade não é a única maneira pela qual um adversário ou um algoritmo de politime poderia tentar computar o valor de g α β. Pode haver algum atalho ou alguma outra maneira de computar g α β sem realmente computar α e β e é por isso que pode ser o caso de que mesmo que no seu grupo o problema de CDH seja mais fácil de resolver o problema de log discreto pode ser ainda difícil de ser resolvido. E é por isso que assunção sábia dizemos que CDH fazendo uma suposição de que um problema de CDH é difícil de resolver em seu grupo é uma suposição mais forte em comparação com a hipótese de que o problema DLog é difícil de ser resolvido em seu grupo porque parece que o problema da CDH é relativamente mais fácil de ser resolvido em comparação com o problema de log discreto acertado. Então, assunção sábia a assunção CDH é uma assunção mais forte. Pois o problema dificultosamente o problema de CDH pode ser mais fácil de ser resolvido em comparação com o problema de log discreto. Sendo assim, essa é uma relação entre a suposição de log discreta e a assunção CDH. Vejamos agora a relação entre a assunção CDH e a assunção DDH. Por isso, verifica-se que se no seu grupo o assunção DDH detém então a assunção CDH também se mantém e isso pode ser provado facilmente por um contrapositivo. Especificamente, se você tem um algoritmo de polítime que pode resolver o problema de CDH com probabilidade significativa então usando esse algoritmo é muito fácil até mesmo resolver qualquer instância do problema DDH nesse grupo. Basicamente o que o solver DDH tem a fazer é ele tem que, dado o par u, v, w o que ele tem que fazer é tem que invocar o solver CDH no par u, v e obter o valor da saída do Diffie – Hellman function on the input pair u, v. E comparar essa saída com w e, consequentemente, o solver DDH pode decidir se está vendo um triplet de Diffie – Hellman ou um triplet aleatoriamente escolhido sobre o grupo para que seja a implicação em uma direção agora que tal a implicação na outra direção. Podemos dizer que se a assunção CDH se mantém no grupo então é a assunção do DDH e a resposta neste caso é clara não. Acontece que temos alguns grupos específicos onde sabemos como resolver o problema DDH em polia quantidade de tempo, mas apesar de sabermos como resolver um problema DDH em tempo de polia de tempo nesses grupos não temos ainda nenhum algoritmo de polítime para resolver o problema de CDH com probabilidade significativa nesses grupos que significa que fazer a suposição de que o problema DDH é difícil de resolver em um grupo é uma suposição mais forte em comparação com a suposição de que um problema de CDH é difícil de resolver naquele grupo. Porque dificuldade sábia sentimos que um problema DDH é mais fácil de resolver comparar para resolver o problema de CDH que significa se considerarmos essas 3 suposições discreta log assunção é a suposição mais milenar porque dificuldade sábia solução o problema de log discreto é o mais difícil enquanto fazer o DDH assunção é a suposição mais forte porque difícil solução sábia o problema DDH pode ser computacionalmente menos dispendioso em comparação com a resolução do problema de CDH em comparação com a resolução do problema DLog. (Consulte O Slide Time: 21:48) Então agora temos os 3 pressupostos que a CDH a discreta assunção de log, Assunção CDH e a assunção DDH e agora vamos ver as etapas matemáticas exatas ou as etapas concretas do Diferfie – Hellman Key Exchange Protocol. Por isso, lembre-se na última palestra que vimos as etapas do Diffie – Hellman Key Exchange Protocol assumindo que estamos dando alguma função especial E e F certo. Assim, apenas para resumir a exigência da função E deve ser que deve ser fácil computar, deve ser de uma maneira e não só isso dado α e o valor da função E (β) mesmo sem saber β deve ser fácil de computar F (α, β) se você conhece α e nós também tínhamos visto que se você quer obter um Diferfie – Hellman Key Exchange Protocol com a noção de privacidade fraca então o requisito da função E e F deve ser que se alguém te der o valor de E (α) e E (β) então só conhecendo E (α) e E (β) deve ser difícil para você computar F (α, β) na sua totalidade, mas se quiser alcançar uma noção mais forte de sigilo nomeadamente a privacidade forte do Diffie – Hellman Key Exchange Protocol então precisamos de exigência adicional da função E e F a saber, exigimos que o valor de F (α, β) deve ser computacionalmente indistinguível de qualquer valor aleatório a partir do conjunto y. Mesmo que você seja dado com o valor de E (α) e com o valor de E (β).   Mas ao executar este Diffie – Hellman Key Exchange Protocol um remetente e o receptor só podem concordar sobre um elemento de grupo pseudo aleatório não em uma sequência de bits pseudo aleatório. Por isso, uma solução potencial para resolver ou conviver com esse problema é usar uma função de derivação de chave que tínhamos visto durante nossa discussão sobre a função hash e podemos usar qualquer função de derivação de chave padrão com base na função hash. E supondo que o elemento de grupo aleatório resultante pseudo aleatório que remetente e receptor estão indo para a saída no final do Diffie – Hellman Key Exchange Protocol tem uma entropia suficientemente grande então aplicando a função de derivação de chave naquela pseudo saída comum aleatória tanto o emissor quanto o receptor podem obter localmente uma sequência de bits pseudo aleatório que eles agora podem usar como chave para qualquer primitivo criptográfico simétrico. E vamos encontrar essa ideia novamente e novamente mais tarde em quando discutirmos a noção de sistema de cripto publicitário e cripto híbrido. A segunda limitação que está aí no Diffie – Hellman Key Exchange Protocol é que ele te dá segurança apenas contra um eavesdropper que monitora a comunicação entre o emissor e o receptor. Acontece que se o nosso adversário é um adversário ativo onde pode interceptar pacote ou onde pode mudar o conteúdo das mensagens comunicadas entre o remetente e o receptor então pode lançar vários tipos de ataques como ataque de imitação, homem no ataque do meio e assim por diante. É por isso que no protocolo mundial real não utilizamos o Diffie – Hellman Key Exchange Protocol como está em sua forma básica. Fazemos modificações em cima do Diffie – Hellman Key Exchange Protocol para garantir que cuidemos até mesmo de um adversário ativo. Então isso me leva até o final desta palestra. Só para resumir nesta palestra introduzimos várias suposições criptográficas em grupo cíclico nomeadamente a suposição de log discreta, a assunção de CDH e a assunção DDH e com base nestas premissas