Fundamentos of Cryptography Dr. Ashish Choudhury Department of Computer Science Indian Institute of Science-Bangalore Lecture-44 El Gamal Public Key Encryption Scheme (Consulte Slide Time: 00:33) Olá a todos. Bem-vindo a esta palestra. Só para recapitular, na última palestra, vimos a sintaxe do esquema de criptografia de chave publicitário. Por isso, o roteiro para esta palestra é o seguinte. Nesta palestra, veremos um esquema de criptografia público-chave candidato, nomeadamente o sistema de cripto-chave El Gamal e vamos provar formalmente a sua segurança CPA e encerraremos a palestra com algumas das questões de implementação, que enfrentamos enquanto implementamos o esquema de encriptação El Gamal na prática. (Consulte O Tempo De Deslizamento: 00 :56) Então, vamos tentar entender a intuição do esquema de criptografia El Gamal. Então, para isso, relembrar o Diffie – Hellman key-exchange protocol. E, pela simplicidade, supõem que estamos considerando um grupo conjuntural multiplicativo. Por isso, os parâmetros públicos são a descrição de um grupo cíclico, um gerador e o tamanho do grupo, que é. E no Diffie – Hellman key-exchange protocol, dizem Sita e Ram, eles querem concordar sobre uma chave, cada um deles capta a sua própria contribuição para a chave geral. Então, Sita escolhe sua contribuição, e ela envia para Ram. E, de forma independente, Ram escolhe sua contribuição e envia. E chave geral que é acordada entre o emissor e o receptor é. E nós tínhamos provado formalmente a segurança do protocolo de troca de chave Diffie – Hellman. Por isso, agora, considere o seguinte processo de criptografia. Por isso, emissor e receptor primeiro executa uma instância do protocolo de troca de chave do Diffie – Hellman para obter uma chave compartilhada, denotada por, que é um elemento de grupo. E sabemos que se a assunção DDH se mantém no grupo subjacente, isso significa que se o problema DDH é difícil de ser resolvido no grupo subjacente, então a chave acordada é indistinguível de qualquer elemento aleatório do grupo. Agora imagine, Ram tem uma mensagem, diga texto simples, que é um elemento de grupo, que ele quer criptografar e enviá-lo para Sita. Então o que Ram pode fazer é, a partir do ponto de vista de Ram, Ram sabe que, ao rodar o protocolo de troca da chave Diffie – Hellman, Sita também vai ter a mesma chave E Ram também sabe que se houver um eavesdropper, quem eavescaiu a comunicação entre Sita e Ram, então a partir do ponto de vista desse adversário, a chave, que está disponível com Ram, é meio indistinguível de qualquer elemento aleatório do grupo. Então o que o Ram pode fazer é, para criptografar o texto simples, ele pode usar a chave para mascarar sua tarefa simples e já que estamos realizando operações no grupo, para mascarar o texto simples, o que o Ram pode fazer é, ele pode executar a operação do grupo na mensagem e na chave e o resultado é denotado por, que também é enviado com a mensagem, que Ram teria enviado como parte do protocolo de troca de chave Diffie – Hellman. Agora uma vez que Sita recebe as mensagens de Ram, ela passa a receber dois elementos do grupo. O primeiro elemento é a contribuição de Ram ’ como parte do protocolo de troca de chave Diffie – Hellman, que Sita usa para gerar a chave conforme as etapas do protocolo de troca de chave Diffie – Hellman. Como uma vez que recebeu a chave, para descriptografar o texto cifrado, o que Sita tem a fazer é, ela tem que simplesmente cancelar o efeito de chave ou ela tem que desmascarar a chave. E para desmascarar a chave, o que ela pode fazer é, ela pode apenas realizar a operação do grupo no texto cifrado e o inverso multiplicativo do elemento. Assim, uma vez que o elemento é conhecido por Sita e ela conhece a descrição do grupo, ela pode computar o inverso multiplicativo em tempo polinomial, que eu denote por − 1. E se ela realizar a operação do grupo no texto cifrado e − 1, o efeito de cancela fora. E Sita acaba conseguindo o texto simples. Agora, eu afirme aqui que o texto cifrado, que é o resultado da operação do grupo no texto simples e na chave, vai ser independente do texto simples subjacente. Vou provar isso muito em breve, mas para o momento supõem que esta afirmação é verdadeira. Se de fato esta afirmação é verdadeira, então todo esse protocolo, todo esse processo de criptografia e decriptografia de fato se parece com um esquema de criptografia de candidato. Pois se a distribuição do texto cifrado for independente da chave, então mesmo depois de ver o texto cifrado, adversário será incapaz de descobrir o que exatamente é criptografado, se é uma criptografia de 0, 1, 2, não pode figurar fora. Sendo assim, essa é a intuição geral do esquema de criptografia El Gamal. (Consulte O Slide Time: 05 :09) Então eu escrevi o blueprint do esquema de criptografia que eu havia discutido no último slide. Agora a questão é saber como podemos visualizar todo o processo que discutimos há pouco como uma instanciação do esquema de criptografia de chave publicitário? Pois lembre-se conforme a sintaxe do esquema de criptografia de chave pública, precisamos ter um algoritmo de geração de chaves, que iria saída de um par de chave pública, secrete-chave, devemos ter um algoritmo de criptografia e devemos ter um algoritmo de decriptografia. Então, pictorialmente, sabemos que agora temos um projeto de um processo de criptografia, mas agora temos que colocar tudo na sintaxe do processo de criptografia de chave publicitário. E esse processo de visualização de processo de criptografia acima como uma instância de esquema de criptografia de chave pública foi identificado por Taher El Gamal. E é por isso que esse processo de criptografia que nós vamos discutir agora é chamado como El Gamal esquema de criptografia. Então você pode estar se perguntando que como exatamente é diferente deste Diffie – Hellman key-exchange protocol? Bem, nós não estamos fazendo nada além do Diffie – Hellman key exchange protocol. Então essa parte da comunicação, que eu destaquei é exatamente o protocolo de troca de chave Diffie – Hellman. Mas, ainda por cima, estamos fazendo alguma comunicação adicional do lado do remetente ’, que permite que o receptor descriptografe o texto cifrado e recupere de volta o texto simples. Então o que nós vamos fazer é, todo o processo de criptografia que nós discutimos até agora visualmente, podemos imaginá-lo como uma instância de esquema de criptografia de chave pública da seguinte forma. Assim, podemos imaginar que a mensagem do receptor ’ aqui, a saber, a mensagem de Sita ’ como parte do protocolo de troca de chave Diffie – Hellman é a sua chave pública.E podemos visualizar isso como se, essa seja sua contribuição para o Diffie – Hellman key-exchange protocol com cada remetente potencial, uma vez por todos. Isso significa que o algoritmo de geração-generais que Sita pode executar aqui é o seguinte. Como parte de chave secreta, ela pode escolher aleatoriamente um índice na faixa de 0 e ela pode fazer sua chave pública ser. E será garantido que se trata de uma cópia autenticada. Isso significa, realmente isso é gerado por assim chamado Sita. Como exatamente é assegurado, veremos ou resolveremos esse problema mais adiante. Mas para o momento supõem que a Sita tenha gerado uma chave secreta como essa e ela computou a chave pública para ser e a disponibilou no domínio público. Em seguida, podemos imaginar como se esta fosse sua contribuição ou sua parte da mensagem para o Diferfie – Hellman key-exchange protocol com todo possível Ram, que gostaria de fazer uma comunicação segura com a Sita. Agora, assumem que temos um chamado Ram ou um remetente que quer criptografar um texto simples, digamos, usando a chave pública. Então o que o Ram vai fazer é: Ram vai escolher um aleatório na faixa de 0 e agora ele agora vai computar dois elementos do grupo. O primeiro elemento do grupo é 1, que não passa de nada. E um segundo elemento de grupo 2 é basicamente a operação do grupo sendo executada no texto simples e na chave, onde está a chave, que é obtida levantando a chave pública para o índice. Assim, as duas mensagens ou os dois elementos que o Ram está enviando, podem ser visualizados da seguinte forma. A primeira mensagem, você pode interpretar como se fosse a contribuição Ram ’ s contribuições ou sender ’ s contribuição para o Diffie – Hellman key-exchange protocol, porque se realmente Ram teria participado de uma instância do protocolo Diffie – Hellman key-exchange, então 1 é a mensagem, que Ram teria enviado para Sita em resposta à mensagem, que Sita já enviou e ficou offline. A segunda mensagem 2 ou o segundo elemento de grupo 2, você pode imaginar como se ele fosse mascaramento do texto simples com a chave resultante Diffie – Hellman, que Sita e Ram teriam concordado ao usar e como transcrição do protocolo. Então agora se imaginarmos esse processo de criptografia analisando as mensagens de Sita e Ram assim, então ele se encaixa automaticamente no framework do nosso processo de criptografia de chave pública. Para fazer a decriptografia, o que Sita tem a fazer é, a partir do primeiro elemento de grupo, que Ram enviou, usando essa e a chave pública que Sita enviou já para a chamada Ram, Sita pode executar seus passos do Diffie – Hellman key-exchange protocol e concordar sobre ou reter a mesma chave, que Ram usou para mascarar a mensagem. E uma vez que recupera a chave, para descriptografar o texto cifrado, é preciso o segundo componente do texto cifrado, a saber: 2 e realiza a operação do grupo no 2 e o inverso multiplicativo de − 1 para recuperar de volta o texto simples. A minha afirmação aqui é que em todo este processo, a distribuição do segundo componente do texto global cifrado, a saber, 2 é independente do texto simples subjacente. Por isso, em breve provaremos este fato, mas agora se imaginarmos essa coisa toda, como a forma como eu disse, agora você pode ver que temos agora uma instância de um esquema de criptografia de chave publicitário. (Consulte O Slide Time: 10:31) Então agora nos deixe colocar os detalhes formais exatos do processo de criptografia El Gamal. Por isso, o espaço à paisana e o espaço publicitário são ambos que vão ser o grupo. E o espaço segredo-chave vai ser Z, a saber, vai ser o conjunto {0, …,. E o texto cifrado geral será composto por dois elementos do grupo. Por isso, vai ser um par de elementos do grupo subjacente. O algoritmo de geração de chaves supera uma chave pública e uma chave secreta da seguinte forma. A chave secreta é um aleatório na faixa de 0 e uma chave pública. Para que você possa imaginar como se Sita estivesse fazendo a sua parte do Diferfie – Hellman key exchange protocol com todo receptor potencial uma vez por todas. O algoritmo de criptografia, que Ram ou qualquer remetente vai seguir para criptografar um texto simples é o seguinte. O remetente vai escolher um aleatório na faixa de 0 a 1. E computar, que vai ser o primeiro componente do texto cifrado. E a criptografia real da mensagem é a operação de grupo realizada no texto simples e a chave pública levantada para o poder. Então, pictorialmente, você pode imaginar que primeiro componente do texto cifrado não passa de contribuição do emissor ’ s para a chave Diffie – Hellman, que remetente e receptor vão concordar. E o segundo componente do texto cifrado é o mascaramento do texto simples com a chave Diffie – Hellman. Agora a operação de decriptografia é, você recebe um texto cifrado composto por dois elementos do grupo. Então você primeiro computa uma chave comum do Diffie – Hellman, que vai ser estabelecida entre o emissor e o receptor, levantando o elemento de grupo 1 para a chave secreta, de modo que você também obtenha, encontre um inverso multiplicativo dele. E então realizar a operação do grupo com o segundo componente do texto cifrado, de modo que o efeito de sumos e você acabe com o texto simples. Portanto, essa é a sintaxe formal do esquema de criptografia El Gamal. Agora queremos provar formalmente que este esquema de criptografia El Gamal é de fato COA seguro. Como temos discutido na última palestra, no mundo de chave pública, segurança do COA, segurança da CPA de mensagem única e segurança multi-mensagem CPA são todos equivalentes. Portanto, basta apenas provar a segurança do COA deste processo de criptografia. Assim como estou reivindicando ao longo dos últimos slides, a distribuição do componente de texto cifrado 2, ou seja, a operação do grupo sobre com a chave Diffie – Hellman, vai ser independente do texto simples subjacente. Isso significa, a partir do ponto de vista de um adversário computacionalmente delimitado, se ele ver 2, então a partir de seu ponto de vista, 2 poderia ser o resultado da aplicação da operação do grupo em qualquer e qualquer. E se esse for o caso, isso significa, se esta afirmação for de fato verdadeira, então ela implica automaticamente a segurança do COA. Intuitivamente isto é porque para cada instância do algoritmo de criptografia neste esquema de criptografia El Gamal, o remetente vai escolher um aleatoriamente. Não é o caso de que vai escolher o mesmo toda vez. E ifis escolhido de forma independente para cada instância da criptografia, então significa automaticamente que a chave Diffie – Hellman, que é usada para mascarar a mensagem também vai ser independente para cada instância. Porque a chave geral Diffie – Hellman é. Portanto, mesmo que o ecomponente na resultante Diffie – Hellman key, que remetente e receptor estejam usando para fazer a criptografia e decriptografia é o mesmo, é o que está acionando a aleatoriedade aqui e já que é captado de forma independente aqui, para cada instância da criptografia, a chave geral Diffie – Hellman, que é usada em cada instância é independente. E agora assumindo que esta afirmação é verdadeira, isso significa que a distribuição de 2 é independente do texto simples subjacente, obtemos a segurança do COA. (Consulte O Tempo De Deslizamento: 14:34) Então, agora, vamos formalizar essa intuição por uma prova rigorosa. E antes de entrar na prova, vamos fazer um warm up aqui e considerar uma variação do esquema de criptografia El Gamal. Principalmente nós vamos considerar uma variante perfeitamente segura do esquema de criptografia El Gamal. Eu ressalto aqui que não é a forma como vamos implementar o esquema de criptografia El Gamal e não é a forma como realmente usamos o esquema de criptografia El Gamal. Essa variação do esquema de criptografia El Gamal na configuração de chave privada é justamente para tornar a prova mais simples. Por isso, o esquema de criptografia El Gamal modificado na configuração de chave privada, estou denotando como Π. Ele tem seu próprio algoritmo de geração de chaves, algoritmo de criptografia e algoritmo de decriptografia. Os parâmetros públicos são o grupo cíclico, a descrição de grupo e um elemento de grupo uniformemente aleatório, onde não se sabe. Por isso, podemos imaginar como se fosse algum tipo de set up, que foi feito por um terceiro confiável e não é conhecido por ninguém. Agora uma vez que este é um processo de criptografia de chave simétrica, o algoritmo de geração de chaves vai a saída de uma chave aleatória uniformemente e a chave é um elemento do grupo. Para criptografar uma mensagem nesta variante do processo de criptografia El Gamal, nós computamos dois elementos do grupo, a saber: 1 e 2. Onde 1 é algum, onde é escolhido aleatoriamente do conjunto Z. E cifrar o componente de texto 2 é basicamente o mascaramento da mensagem com a chave. Uma vez que se trata de um esquema de criptografia de chave simétrica, vamos usar a mesma chave para a decriptografia também. E para recuperar o texto simples, nós basicamente tiramos o segundo componente do texto cifrado e realizamos a operação do grupo com relação ao inverso multiplicativo da chave. Observe que nesta variação do processo de criptografia El Gamal, o primeiro componente do texto cifrado, a saber, 1 e o publicamente conhecido, eles não são nem todos utilizados para o processo de criptografia e para o processo de decriptografia. Mas estou apenas retendo-as, para garantir que a sintaxe geral do texto cifrado que estamos a chegar aqui parece o mesmo que vamos obter na instanciação real do esquema de encriptação El Gamal. Agora eu afirme aqui que a variante de chave privada do processo de criptografia El Gamal está perfeitamente segura se o meu texto simples subjacente for o grupo. E isso porque essa variante de chave privada do esquema de encriptação El Gamal é exatamente semelhante ao esquema de plataforma única sobre o grupo. A única diferença é que no esquema one-time pad, executamos o XOR da chave com o texto simples. Mas já que estamos na configuração do grupo, vamos apenas substituir essa operação XOR pela operação do grupo. Mais formalmente, assuma que temos um texto cifrado arbitrário, digamos (1, 2) e digamos que consideremos um par de texto simples arbitrário, a saber, 0 e 1, que são elementos de grupo, porque aqui o meu espaço de texto simples é o grupo subjacente. Vou mostrar que realmente esse processo de criptografia satisfaz a definição de sigilo perfeito. A saber, considere a probabilidade de que esse texto cifrado arbitrário (1, 2) seja uma criptografia do texto simples 0. E, da mesma forma, considere a probabilidade de que esse texto cifrado arbitrário (1, 2) seja uma criptografia de 1. Acontece que esse texto cifrado arbitrário (1, 2) é uma criptografia de 0, apenas se o algoritmo de geração de chaves teria produzido uma chave, que é o resultado da operação de grupo realizado em 2 e o inverso multiplicativo de 0. Mas, uma vez que o algoritmo de geração de chave supera elementos uniformemente aleatórios do grupo como a chave, verifica-se que o algoritmo de geração de chaves de fato supera uma chave, que é igual a 2 de operação do grupo 0 − 1 é 1 sobre o tamanho do grupo. Agora executando exatamente o mesmo argumento, podemos afirmar que a probabilidade de que o texto simples 1 seja criptografado no texto cifrado (1, 2) é exatamente o mesmo, que meu algoritmo de geração de chaves supera uma chave, o que é igual à operação de grupo realizada em 2 e 1 − 1.And a probabilidade de que minha chave seja esta, é 1 sobre o tamanho do grupo. Isso significa, para qualquer adversário, mesmo que seja computacionalmente ilimitado, se ele participa de um experimento de indistinguibilidade perfeitamente seguro na configuração de chave simétrica ou no experimento do COA, então a probabilidade de ele poder distinguir se está vendo uma criptografia do elemento de grupo 0 ou se está vendo uma criptografia do elemento de grupo 1, é exatamente a metade. Isso significa, você não pode distinguir fora; com igual probabilidade é uma criptografia de 0, assim como a criptografia de 1. E é por isso que esta variante modificada ou simétrica-chave do processo de criptografia El Gamal é perfeitamente segura. (Consulte O Slide Time: 19:38) Agora vamos voltar para a segurança do COA do real esquema de criptografia El Gamal que projetamos na configuração de chave pública. Por isso, antes de ir mais longe, voltemos a lembrar o que provamos há pouco. Por isso, consideramos uma variante de esquema de criptografia El Gamal na configuração de chave simétrica e aqui está o algoritmo de criptografia. O algoritmo de criptografia produz dois elementos de grupo (1, 2), sendo que 1 é algum aleatório e 2 é o mascaramento da mensagem. E, para além disso, o adversário também tem uma informação pública, nomeadamente, onde não se sabe ao adversário. Portanto, se eu considerar a visão do adversário, a visão do adversário ’ consiste basicamente em três distribuições de probabilidade, a saber, ele tem um elemento, onde é escolhido aleatoriamente a partir de Z.Sabe-se o valor de, onde é escolhido aleatoriamente da Z. E sabe-se o mascaramento da mensagem com o texto simples, onde a chave é escolhida aleatoriamente do grupo subjacente. E nós provamos que esse processo de criptografia é perfeitamente seguro. Por outro lado, o verdadeiro esquema de criptografia de chave pública El Gamal, que projetamos, lá também o texto cifrado consiste em dois elementos do grupo. E segundo componente do texto cifrado é o mascaramento da mensagem com a chave Diffie – Hellman, a saber. Portanto, se eu considerar a visão do adversário ’ nesta instanciação real ou na instanciação real do esquema de criptografia El Gamal na configuração de chave pública, então a sua visão é a seguinte. Sabe o valor de, onde é desconhecido e uniformemente aleatório do conjunto Z. Sabe o valor de, onde é uniformemente aleatório do conjunto Z. E sabe o mascaramento da mensagem com a chave Diffie – Hellman, onde a chave Diffie – Hellman não é nada além, e pertence ao grupo subjacente. Agora se você ver aqui de perto, o que exatamente é diferente aqui, se eu considero as opiniões dos dois adversário aqui? A distribuição de nos dois mundos ou para os adversários é perfeitamente a mesma. Eles são exatamente indistinguíveis. Aqui também alfa é aleatório, aqui também alfa é aleatório, não conhecido do adversário e adversário sabe o valor de. Da mesma forma, a distribuição de em ambos os mundos são exatamente idênticos. O que é diferente aqui, é a natureza de 2 que adversário vê na variante chave simétrica do esquema El Gamal e na distribuição de 2, que adversário enxerga no real esquema de encriptação El Gamal. No mundo chave simétrico, o mascaramento é com um elemento de grupo uniformemente aleatório, enquanto que na chave pública El Gamal, o mascaramento do texto simples está com a chave pseudo-aleatória, que é uma chave do Diffie – Hellman. E se eu assumo que a assunção DDH se mantém no meu grupo subjacente, então sabemos que conforme o Diffie – Hellman assumpção, Diffie – Hellman triplet e um non Diffie – Hellman triplet, eles são computacionalmente indistinguíveis do ponto de vista de qualquer adversário computacionalmente delimitado. Isso significa, se o meu for uniformemente aleatório, isso significa que se eu estiver neste caso, então nesse caso é algum, onde é totalmente aleatório, não relacionado com e. Considerando que se eu considerar cifrado o texto 2 como per o public key Diffie – Hellman pulic-key El Gamal encryption scheme, então minha chave não é nada mas. Então, se meu adversário não puder distinguir entre um triplet DH e um triplet de DH, então posso dizer que a distribuição do componente de texto cifrado 2, que adversário vê em ambos os mundos também são computacionalmente indistinguíveis e que automaticamente provará que nosso processo de criptografia El Gamal é COA seguro. (Consulte O Tempo De Deslizamento: 23:45) Então, essa é a declaração formal que nós vamos provar agora. Vamos provar que se a assunção DDH se detém no meu grupo subjacente, então o processo de encriptação El Gamal é de fato COA assegurado. E nós estabelecemos formalmente esse fato dando uma redução. Então assuma, você tem um adversário de tempo poly que pode atacar o seu esquema de criptografia de chave pública El Gamal. Usando esse ataque, vamos projetar um solver DDH, um tempo de polia DDH solver que consegue distinguir um triplet de Diffie – Hellman triplet de um triplet não Diffie – Hellman. Por isso, participa de uma instância do experimento DDH. O experimento DDH prepara um desafio para o solver DDH dando-lhe (, onde e são elementos de grupo aleatórios. E terceiro componente do triplet também é, ou é um elemento uniformemente aleatório, dependendo se o desafiante tem ou. E a tarefa do solver DDH é encontrar se é um triplet de DH ou um triplet não DH. Para resolver isso, o solver DDH invoca o nosso atacante, que pode atacar o esquema de criptografia El Gamal e participa de uma instância do jogo COA e configura a chave pública a ser. Agora conforme as regras do jogo da COA, o atacante do COA vai enviar um par de textos simples do grupo subjacente e este solver DDH vai escolher aleatoriamente uma dessas duas mensagens e ela prepara o texto de cifração do desafio da seguinte forma. O segundo componente do triplet, que é dado como o desafio a este solver DDH, é configurado para ser o primeiro componente do texto cifrado e a criptografia real da mensagem é definida como, mascarada com o terceiro componente do triplet, que é lançado como um desafio ao solver DDH. Por isso, agora antes de prosseguir mais longe, vamos tentar entender o que está acontecendo nesta redução geral. Se você vir aqui que se este triplet é um triplet não DDH, isso significa neste caso em alguns, onde não está relacionado e, então a distribuição do texto cifrado (1, 2), que é dado a este atacante contra o esquema El Gamal, tem exatamente a mesma distribuição se este atacante teria participado do jogo COA contra a variante simétrica-chave do esquema de criptografia El Gamal. Pois é assim que esse texto de cifração do desafio se pareceria para o atacante naquele experimento. Considerando que, se o tríplet que é dado a este solver DDH for um triplet DH, então a distribuição de (1, 2) que este adversário está vendo é exatamente a mesma distribuição como se esse adversário tivesse visto participando de uma instância de jogo da COA contra o processo de criptografia El Gamal. Assim, vamos voltar a esse fato novamente. Por isso, agora esse adversário tem que identificar se já viu uma criptografia de 0 ou 1. Por isso, submete sua produção. E resposta do solver DDH é que, diz que está vendo um triplet de DH, se e somente se o adversário EG identificou corretamente se ele é 0 ou se é 1, o que é criptografado no texto da cifra contábeis (1, 2). Por isso, agora, vamos analisar a vantagem, a saber, com quanta probabilidade este solucionador DDH vai resolver uma instância aleatória do problema DDH. Por isso, afirme que se, isso significa que este triplet é um triplet não DDH. Então a probabilidade de que minhas saídas de solver DDH incorretamente, a saber, ela saídas ′ = 1, é exatamente a mesma com a qual este atacante do COA teria vencido o jogo da COA contra a variante simétrica-chave do esquema de criptografia El Gamal. E nós já provamos que é 1 ⁄ 2. Isso porque se estamos no estabelecimento onde, então como já provei que o texto cifrado, que o nosso adversário EG está vendo, tem exatamente a mesma distribuição que teria visto ao participar de uma instância do jogo COA contra o esquema de criptografia El Gamal modificado. Por outro lado, eu afirme que se o meu caso for, então a probabilidade de que minhas saídas de solver DDH ′ = 1 é exatamente a mesma que o meu adversário EG vence o jogo COA contra o esquema de criptografia El Gamal. E isso decorre do fato de que se estamos no caso em que, então, isso significa que o triplet que se dá é um triplet DDH ou Diffie – Hellman triplet, o que significa que a distribuição do texto cifrado, qualquer que seja visto o adversário é exatamente o mesmo que distribuição do texto cifrado que este adversário teria visto participando de uma instância de jogo da COA contra o esquema de criptografia El Gamal. Por isso, em síntese, o que estamos concluindo agora é que, se você ver a vantagem distintiva do nosso solver DDH, então são exatamente 1 ⁄ 2 menos a probabilidade com a qual nosso adversário poderia ter vencido o jogo COA contra o esquema de criptografia El Gamal. Mas como estou a assumir que a assunção DDH se mantém no grupo subjacente, então eu sei que a vantagem distintiva de qualquer solver DDH é superior delimitado por alguma probabilidade insignificante. Por isso, não conheço o texto simples, mas conheço a chave pública e tenho uma encriptação El Gamal desse texto simples desconhecido, que consiste em dois elementos de grupo, que estou denotando por e. E conforme a sintaxe do processo de criptografia El Gamal, terá esta propriedade, portanto, 1 é a aleatoriedade subjacente utilizada pelo remetente. E, da mesma forma, imagine que eu tenho uma criptografia El Gamal ou texto cifrado de uma mensagem desconhecida, novamente constituída por dois elementos do grupo. Agora suponhamos que eu multiplique o primeiro componente de ambos os textos cifrados. E independentemente eu multiplico o segundo componente de ambos os textos cifrados. E isso produzirá dois elementos de grupo, que matematicamente terão a seguinte propriedade. O primeiro elemento de grupo não será nada além da aleatoriedade do poder usado no primeiro texto cifrado mais a aleatoriedade usada no segundo texto cifrado. E o segundo componente será o produto dos dois textos corridos, multiplicado por para o poder público-chave vezes a somatória das duas aleatoriedade. E se você olhar de perto, isso não é nada mais que você possa imaginar como se este for um texto de cifração El Gamal para o texto simples, sob a aleatoriedade 1 + 2. E é por isso que eu digo que o meu processo de criptografia El Gamal é de homomorfalido multiplicativo. A razão pela qual é multiplicativa homomórfica é que se eu multiplicar dois textos cifrados El Gamal, então mesmo sem conhecer os textos simples subjacentes (eu ressalto que não conheço os textos simples subjacentes e subjacente aleatoriedade 1 e 2, que são usados individualmente), acabo obtendo um texto de cifração El Gamal de um texto corrido relacionado, a saber, sob alguma aleatoriedade desconhecida, a saber: 1 + 2. Portanto, esta é uma espécie de propriedade muito interessante do processo de encriptação El Gamal. E mais tarde em