Loading
Nota de Estudos
Study Reminders
Support
Text Version

Segurança Semântica

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 Tecnologia da Informação – BangaloreLecture – 7Semantic Security (Consulte o Tempo do slide: 00 :32) Olá, todos, bem-vindos à palestra 7. O plano para esta palestra é o seguinte. Definiremos a noção de segurança semântica no modelo de ataque cifrado somente e veremos uma versão equivalente a esta definição baseada em jogo indistinguível e introduziremos também provas baseadas em redução que é central para criptografia. (Consulte o Tempo do slide: 00 :51) Então, vamos começar com a definição semântica de segurança no modelo de ataque cifrado somente e o cenário é o seguinte. Então, nós estamos no modelo de ataque cifrado apenas em que temos um adversário, e agora vamos considerar um adversário computacionalmente delimitado. Pois lembre-se, na última palestra discutimos que se a reusabilidade chave é o seu objetivo final, então você tem que garantir que seu adversário seja computacionalmente ilimitado. Então, assumimos que temos um adversário computacionalmente delimitado, que está vendo um texto cifrado c de alguma mensagem desconhecida m criptografada pelo remetente usando uma chave desconhecida conforme o algoritmo de criptografia, em que as etapas do algoritmo de criptografia são conhecidas do adversário. Intuitivamente, vamos dizer que o nosso processo de criptografia é semanticamente seguro neste modelo de ataque cifrado somente se o texto cifrado não revelar nenhuma informação adicional sobre o texto demandado subjacente ao invasor. Além disso, isso deve segurar mesmo que o adversário tenha qualquer tipo de informação externa prévia sobre o texto à plaina subjacente, que poderia ter sido vazado para o invasor por qualquer outro meio antes de o texto cifrado ter sido comunicado. Por isso, ainda que essa intuição seja muito direta para entender, é extremamente desafiador formalizar a intuição acima. Então, vamos proceder para formalizar essa intuição, certo. (Consulte o Tempo do slide: 02 :11) Então, introduzimos, primeiramente, uma função abstrata aqui, a saber, h (m), que modela qualquer tipo de informação externa prévia sobre o texto à plaina subjacente, que pode ser vazado para o adversário através de outros meios antes de qualquer texto cifrado ter sido comunicado. Portanto, esta h (m) é meio que alguma função de história. Pode haver em algum contexto ou pode ser um cenário em que o adversário pode não ter absolutamente nenhuma informação externa prévia, nesse caso, minha função h (m) será uma função vazia, mas pode haver um cenário em que o adversário possa ter alguma informação externa prévia sobre o nitido subjacente, que foi vazado para o adversário através de alguns outros meios. Então, seja qual for o caso, introduzimos essa função abstrata para modelar essa informação externa prévia sobre o plaintexto subjacente, que o adversário tem. Nós próximos introduzimos outra função f (m), que basicamente modela as informações adicionais sobre o plaintexto subjacente, qual adversário gostaria de computar depois de ver o texto cifrado ou qual adversário gostaria de saber, certo? Sendo assim, esses modelos as informações adicionais e intuitivamente, o objetivo da segurança semântica é garantir o seguinte. Dizemos que o nosso processo de criptografia é semanticamente seguro se a probabilidade com que o adversário poderia computar essas informações adicionais, a saber, a função f (m) usando o cand cifrado cand usando a ajuda da função de histórico ou as informações prévias é quase a mesma com a qual o adversário poderia ter computado a função f (m) apenas usando a informação prévia na ausência do texto cifrado. Se for esse o caso, então a implicação que obtemos aqui é que o texto cifrado não é de nenhuma ajuda para o atacante em computação f (m). (Consulte o Tempo do slide: 04 :04) O que eu quero dizer com isso é pictorialmente o seguinte. Então você imagina que, neste mundo, temos um adversário, que na verdade está vendo um texto cifrado, que é uma criptografia de alguma mensagem desconhecida sob a chave desconhecida e o adversário também tem acesso à função de histórico, a saber, qualquer tipo de informação prévia, que teria sido vazada para o adversário através de algum mecanismo externo sem o conhecimento do texto cifrado. Por isso, o adversário neste mundo é chamado A. Você se compara por imaginar outro mundo onde temos novamente outro adversário, digamos A ’, que não vê o texto cifrado e este adversário A ’ tem acesso apenas à função de histórico, a saber, as informações prévios sobre o texto demandado subjacente, que remetente pode comunicar sobre o canal. Ora, a intuição por trás da segurança semântica é que a probabilidade com a qual A e A ’ poderia computar o f (m), a saber, as informações adicionais sobre o texto demandado subjacente são quase as mesmas, a saber, vamos dizer que o nosso processo de criptografia é semanticamente seguro no modelo de ataque de texto cifrado se a diferença absoluta entre as duas probabilidades a seguir é superior delimitado por alguma função insignificante. Então letus ver mais perto. Vejamos um olhar mais atento sobre esta respetivos probabilidades, nomeadamente: ??? [? ? ??? , h? =?? ] e?? ’ (h (?)) =? (?)] Então sua primeira probabilidade é a probabilidade com a qual o adversário A, a saber, o adversário no primeiro mundo, supera o valor de f (m), em que o adversário recebe o texto cifrado assim como a função histórico. Considerando que a segunda probabilidade é a probabilidade com a qual o adversário no segundo mundo, a saber, o adversário A ’, computa o valor de f (m) apenas usando o valor da função de histórico. Portanto, se a diferença absoluta entre essas duas probabilidades é superior delimitado por uma probabilidade insignificante, então o que significa é que qualquer que seja o adversário poderia ter computado ao ver o texto cifrado, a saber, qualquer que o adversário pudesse ter sabido sobre f (m) usando a ajuda de c com quase o mesmo adversário de probabilidade poderia ter computado f (m) sem ver de fato o c. Se for esse o caso, então significa que nosso processo de criptografia é tão bom que o texto cifrado é meio que algumas sequências de bits aleatórios, e ele ajuda ou não fornece nenhum tipo de auxílio ao adversário em computação f (m) com uma vantagem significativa, é o que é a intuição por trás da noção de segurança semântica, certo. (Consulte o Tempo de Slides: 06 :42) Então esta é a definição original de segurança semântica, e acontece que se quisermos provar a segurança semântica de um processo arbitrário de criptografia conforme esta definição original, então isso é um pouco complicado, onde porque aqui você tem que trazer a função história também como aqui você tem que trazer a função arbitrária f (m) qual adversário gostaria de computar. Em vez disso, o que vamos fazer é veremos uma versão equivalente a esta definição baseada em experimento baseado em indistinção. Essa definição alternativa baseada em experimento baseado em indistinção, você pode imaginar que é a variante computacionalmente segura de indistinguibilidade baseada em definição de sigilo perfeito, certo. (Consulte o Tempo do slide: 07 :27) Então, vamos primeiro relembrar a definição baseada em indistinguibilidade que usamos para definir o sigilo perfeito. Então, a essência dessa definição baseada em indistinção de sigilo para definir o sigilo perfeito é que se você tem um cenário em que um remetente tem 2 mensagens m0 ou m1 e ele tem criptografado aleatoriamente uma dessas mensagens, e se adversário estiver ciente do fato de que o remetente tenha criptografado m0 ou m1, então mesmo depois de ter essa informação prévia e ver o texto cifrado c, adversário não deve ser capaz de identificar o que foi criptografado no texto cifrado c com probabilidade melhor que a metade. Essa foi a intuição que queríamos captar através da indistinguível definição baseada em segredo perfeito. Isso foi capturado muito bem pelo experimento a seguir, certo. Portanto, este é o experimento, que usamos para definir a noção de perfeito sigilo, onde temos um esquema publicamente conhecido, a saber, um tripleto de algoritmos sobre algum espaço de mensagens, e no modelo de perfeito sigilo, tivemos um adversário computacionalmente ilimitado, e o nome do experimento foi este: ?????, Π ???. Por isso, só para relembrar a nomenclatura do experimento é a seguinte. PrivK denota que queremos modelar um experimento, que no contexto de uma chave privada ou de criptografia simétrica, eav significa que estamos considerando um adversário que é um eavesdropper, A é o nome do algoritmo contraditório e Π é o nome do esquema, e neste experimento, as regras são as seguintes. Adversário é permitido submeter qualquer par de mensagens do espaço à plaintexto com a restrição de que o tamanho do dois plaintexto deve ser mesmo, e o experimento ou o verificador, o verificador hipotético faz o seguinte: Ele gera aleatoriamente uma chave executando um algoritmo de geração de chaves e ele criptografa aleatoriamente uma das mensagens usando a chave, e o desafio para o adversário é identificar o que o plaintexto foi criptografado na cifração de impugnação c, seja ele m0 ou m1. Por isso, adversário supera um pouco, a saber, seu palpite sobre o que exatamente foi criptografado no texto do desafio cifrado. Definimos o esquema Π estar perfeitamente seguro ou dizemos que um esquema é perfeitamente indistinguível se a probabilidade com a qual adversário poderia identificar com sucesso o que a mensagem foi criptografada é superior delimitado pela metade. Então, se adversário poderia identificar com sucesso qual mensagem foi criptografada no texto do desafio cifrado, então dizemos que adversário venceu o jogo ou dizemos que a saída do experimento é igual a 1. Isso significa que essa notação de que a saída do experimento é 1 denota a probabilidade de b ’ igual a b. Portanto, no contexto de perfeito sigilo, nosso requisito era que um adversário de probabilidade pudesse identificar b, b ’ igual a b corretamente deveria ser superior delimitado pela metade. (Consulte o Tempo do slide: 10 :25) Agora, vejamos a definição baseada em indistinção para modelar a noção de segurança semântica no modelo de ataque cifrado somente. Vamos fazer as seguintes mudanças. A primeira mudança que vamos fazer é a seguinte. Em vez de assumir que nosso adversário é computacionalmente ilimitado, vamos supor que nosso adversário é computacionalmente delimitado. Trará-se de modelar o primeiro relaxamento que combinamos que devemos fazer em modelo de segurança computacional certo. Então lembre-se da última palestra que discutimos que se a reusabilidade chave é o seu objetivo final, então devemos destinar a alcançar a segurança apenas contra um adversário computacionalmente delimitado, a saber, um adversário cujo tempo de execução é superior delimitado por alguma função polinomial do parâmetro de segurança. Por isso, é por isso que fizemos essa primeira mudança no experimento, não estaremos considerando um adversário cujo tempo de execução é computacionalmente ilimitado. Consequentemente, o nome do experimento vai ser? ?????, Π??? (?). Então, em vez de dizer EAV, eu estou agora chamando esse experimento de COA para denotar que este é o experimento de indistinção no modelo de ataque cifrado somente e a segunda diferença aqui na nomenclatura é que agora estou introduzindo esse parâmetro de segurança n porque o tempo de execução do adversário vai ser delimitado por uma função polinomial do parâmetro de segurança, enquanto se você vê na nomenclatura para o experimento baseado em indistinção no mundo do sigilo perfeito, nenhum parâmetro de segurança foi lá porque nosso adversário foi autorizado a ter execução ilimitada tempo. Então este é o segundo relaxamento. Esta é a segunda mudança no experimento, e a terceira mudança é que em vez de dizer que nosso processo de criptografia é perfeitamente indistinguível, vamos dizer que o nosso processo de criptografia é computacionalmente indistinguível. Se a probabilidade com a qual adversário poderia identificar corretamente o que foi criptografado na cifração do desafio é superior delimitado por alguma função insignificante mais a metade, essa é uma terceira mudança que vamos fazer em nosso experimento, certo. Então no experimento para perfeito sigilo, a exigência era que o adversário não fosse capaz de identificar o que foi criptografado no texto do desafio cifrado com probabilidade melhor que a metade, mas agora estamos dando ao adversário extra insignificante vantagem para identificar corretamente o que foi criptografado na cifração de impugnação c. Esta vantagem extra, a saber, uma vantagem de função desprezível e vantagem de alguma probabilidade insignificante é modelar o segundo relaxamento que temos que fazer no modelo de segurança computacional se a reusabilidade da chave é o seu objetivo final. Então, novamente relembramos na última palestra, vimos que se você deseja projetar um esquema parque-chave reusabilidade é o seu objetivo final, que em vez de exigir que adversário não deve aprender nada adicional, você deve estar disposto a deixar o adversário aprender algo sobre sua mensagem subjacente ou deixar o adversário quebrar seu esquema com algum adicional probabilidade e essa probabilidade adicional deve ser tão pequena em que deve ser uma probabilidade insignificante, que para a maioria dos propósitos práticos você pode ignorá-lo off.Então, é por isso que estou trazendo essa vantagem adicional de função insignificante de n em minha definição de segurança. Sendo assim, esse é o experimento de versão baseado em indistinção de indistinção computacionalmente no modelo de ataque cifrado apenas. Por isso, a essência deste experimento é a seguinte. O que queremos capturar através deste experimento é o seguinte. Se você tem um cenário em que um remetente está tendo um par de mensagem, digamos m0 e m1 e se o adversário tiver consciência disso onde nosso adversário é computacionalmente delimitado, se uma dessas 2 mensagens m0or m1 foi criptografada pelo remetente e comunicada ao receptor e nosso adversário intercepta um texto cifrado, então exigimos a seguinte propriedade do nosso processo de criptografia. Nós exigimos que um adversário computacionalmente delimitado não deve ser capaz de identificar se o texto cifrado c que ele está vendo é uma criptografia de m0 ou se é uma criptografia de m1with probabilidade melhor do que a metade mais insignificante. É isso que é o cenário ou o cenário mundial real que estamos tentando captar por meio desse experimento. (Consulte O Tempo De Deslizamento: 14 :33) Então agora temos as 2 definições a seguir. A primeira definição é, na verdade, a definição original de segurança semântica no modelo de ataque de texto cifrado apenas, em que queremos capturar que a vantagem do adversário no primeiro mundo e o adversário no segundo mundo é superior delimitado por probabilidade insignificante, enquanto que a segunda definição é a definição baseada em indistinção. Acontece que ambas as duas definições são equivalentes. Namely se temos um processo de criptografia que satisfaça a primeira condição, então podemos canprovar que para o mesmo processo de criptografia na segunda condição também se mantém e vice-versa. Ou seja, se temos um processo de criptografia onde a segunda condição se mantém, então para o mesmo processo de criptografia, a primeira condição também se mantém. Gostaria de salientar o seguinte. No experimento, que discutimos quando digo que a probabilidade de que o adversário identifique corretamente o que foi criptografado na cifração do desafio deve ser superior delimitado pela metade mais insignificante, então essa probabilidade é sobre a aleatoriedade do experimento. Por isso, lembre-se que o experimento poderia escolher a mensagem m0 para ser criptografada no texto do desafio cifrado com probabilidade metade e com probabilidade metade do experimento ou o verificador poderia escolher a mensagem m1 para ser criptografada no texto cifrado c. Essa probabilidade de identificar corretamente o que tenha sido criptografado em c deve ser também sobre a aleatoriedade do adversário, certo, pois toda a experiência vai ser um experimento randomizado, direito.Assim, como eu disse que essas 2 noções de segurança ou essas 2 definições são equivalentes, e a comprovação de que essas 2 definições são equivalentes é um pouco complicado e devido ao interesse do tempo, não vamos entrar nos detalhes da prova. No entanto, se você quiser ter uma visão geral de nível muito alto da prova, você pode consultar o livro de Katz e Lindell. Curiosamente, verifica-se que a equivalência dessas 2 definições mantém-se nos outros modelos também, direitinho, atualmente o que estamos considerando é o modelo de ataque cifrado somente modelo de ataque e no modelo de ataque cifrado, o adversário tem acesso à criptografia de alguma mensagem, mas se eu for para o modelo de ataque superior significa modelo de ataque superior significa modelo de ataque mais potente, digamos o modelo de ataque CPA onde além do texto cifrado, o adversário também consegue acesso ao oráculo de criptografia então podemos ter uma versão semeticamente segura da definição que estamos dando atualmente aqui para o modelo de COA, certo. A saber, gostaríamos de afirmar que a vantagem adversarial ou a diferença das probabilidades absolutas de computação adversário a função f (n) nos 2 mundos deve ser superior delimitado por uma função insignificante, onde no primeiro mundo afora o texto cifrado, adversário também terá acesso ao oráculo de criptografia se levarmos essa definição para o modelo de CPAattack. Da mesma forma se levarmos essa definição para o modelo de ataque CCA, então, além do texto cifrado, adversário no primeiro mundo terá acesso ao oráculo de criptografia, ele terá acesso ao oráculo de descriptografia e assim on.Assim, podemos chegar a uma versão semântica segura, podemos chegar a uma versão da segurança semântica no modelo CPA, no modelo CCA e assim por onde a essência da definição será que a diferença absoluta entre as duas probabilidades da computação adversária f (m) no primeiro mundo e f (m) no segundo mundo deve ser superior delimitado por uma probabilidade insignificante, que será a essência da definição de segurança semântica em CPAmodel, modelo CCA e assim por diante. Acontece que independentemente do modelo, podemos chegar a uma definição baseada em indistinguibilidade correspondente e podemos provar que a versão semântica segura da definição, a versão original da segurança semântica será equivalente à definição baseada em indistinção baseada em indistinções. Então, é por isso que para o restante do curso, não estaremos vendo a versão original da definição de segurança semântica. Vamos estar bastante seguindo a definição de segurança baseada em indistinção e dependendo se estamos no mundo CPA, CCA mundo, aprimoraremos o experimento baseado em indistinguibilidade, certo. (Consulte o Slide Time: 18 :53) Então, esta é a definição baseada em indistinção de indistinção no modelo de ataque cifrado e verifica-se que poderíamos chegar a uma versão alternativa dessa definição, certo. Assim, a definição original exige que a probabilidade de que o nosso adversário seja corretamente capaz de identificar a mensagem que é criptografada em c deva ser superior delimitado pela metade mais insignificante, é isso que é a definição original. A definição alternativa exige que a saída do adversário seja mesma independentemente do que exatamente é a mensagem que tenha sido criptografada no desafio cifrado c.So, lembre-se que uma vez que esta definição baseada em indistinção é um experimento randomizado com probabilidade metade, meu b poderia ser igual a zero e com probabilidade metade da mensagem que foi criptografada e cifrada c poderia ser m1, certo. O objetivo do adversário é identificar se ele é m0 que é criptografado em c ou se ele é m1 que foi criptografado em c. Portanto, essa definição alternativa demanda que a saída do adversário deve ser mesma independentemente de ser m0 que é criptografada em c ou se é m1 que é criptografada em c. Mais formalmente, não importa se a mensagem m1 foi criptografada ou a mensagem m0has foi criptografada em c, em ambos os casos, a saída do adversário ’ deve ser quase igual a não ser com uma probabilidade insignificante. Isso significa vantagem absoluta do adversário distinguir se ele está vendo uma criptografia de m0 em cifração c ou se ele está vendo uma criptografia de m1 no texto cifrado c deve ser superior delimitado por alguma função insignificante. Se este for o caso, então dizemos que o nosso processo de criptografia tem criptografia indistinguível no modelo de ataque cifrado apenas, certo. Então, outra interpretação dessa diferença dessas duas probabilidades é superior delimitado por uma probabilidade insignificante é que uma vantagem diferenciada, você pode visualizar a diferença entre essas 2 probabilidades como a vantagem distintiva do nosso adversário, certo? Por isso, a essência dessa definição alternativa é que a vantagem distintiva do nosso adversário neste experimento deve ser superior delimitado por uma probabilidade insignificante. (Consulte o Tempo do slide: 21 :12) Acontece que essas 2 versões das definições baseadas em indistinção são equivalentes. A saber, podemos dizer que o nosso processo de criptografia é computacionalmente indistinguível se a probabilidade com a qual adversário poderia corretamente saída b igual a b ’ é superior delimitado pela metade mais alguma função insignificante. A segunda definição diz que a vantagem distintiva do atacante para distinguir fora se ele está vendo uma criptografia de m0 ou se ele está vendo uma criptografia de m1 deve ser superior delimitado por uma probabilidade insignificante.Acontece que ambas as 2 condições são equivalentes. A saber, podemos provar que se temos um processo de criptografia Π onde a primeira condição se mantém e para o mesmo processo de criptografia, a segunda condição também se mantém e vice-versa. Portanto, o que vamos fazer é seguir a implicação na direção que a condição 2 implica condição 1, a saber, vamos supor que temos um processo de criptografia onde a condição 2 se mantém, a saber, a vantagem distintiva do atacante é superior delimitado por alguma probabilidade insignificante.Se for esse o caso, então vamos mostrar que independentemente da forma como o adversário participa do experimento baseado em indistinção, a probabilidade de que adversário possa identificar corretamente b igual a b ’ ou ela garante b igual a b ’ é superior delimitado pela metade mais alguma função insignificante. Então, vamos provar isso. Então, qual é a probabilidade de que no experimento baseado em indistinção, as saídas de adversário b sejam iguais a b ’ porque se adversário outputs b igual a b ’, é o que é a interpretação de que o experimento supera 1.Now, se você se recorda, há 2 versões do experimento. Uma versão equivalente dessa definição é a definição baseada em indistinção, em que o requisito é que se o adversário vê uma encriptação de uma mensagem escolhida aleatoriamente a partir de um par de mensagens em que o par de mensagens é conhecido pelo invasor, então a probabilidade com a qual ele pode identificar se é uma encriptação desta 0º mensagem ou a primeira mensagem é superior delimitado pela metade mais insignificante. Sendo assim, o que pode ser declarado também como a vantagem distintiva do atacante e distinguindo-se se o texto de impugnação que vê no experimento, no experimento baseado indistinguível pertence a m0 ou m1, não pode separar-se à exceção, exceto com uma probabilidade insignificante. Também vimos uma ilustração onde mostramos na verdade que se o seu processo de criptografia satisfaz a definição baseada em indistinguibilidade, então ele de fato implica que o adversário não pode computar qualquer um dos bits subjacentes do texto à plaina. Nessa ilustração, introduzimos uma prova de redução?baseada, que são centrais para a criptografia. Espero que tenha gostado desta palestra. Obrigado.