Variantes of ElGamal With a Better Security Analysis

No último segmento, vimos que a
Sistema de criptografia de chave pública ElGamal é

escolhida texto cifrado seguro sob um pouco
suposição estranha. Neste segmento, estamos

vai olhar para as variantes de ElGamal que
tem um texto cifrado muito melhor escolhido

análise de segurança. Agora, devo dizer que
na última década, tem havido uma tonelada

de pesquisas sobre a construção de chave pública
criptografias que são escolhidos texto cifrado

seguro. Eu realmente debatido por algum tempo
sobre a melhor forma de apresentar este aqui. E

finalmente, decidi tipo de mostrar um
levantamento dos principais resultados do último

décadas, especificamente como eles se aplicam ao
Sistema ElGamal. E, em seguida, no final da

o módulo, sugiro uma série de documentos
que você pode olhar para outras leituras.

Então deixe-me começar por lembrar que a forma como o
Sistema de criptografia ElGamal funciona. Tenho certeza de que

agora você se lembrar de como tudo funciona ElGamal,
mas apenas para ser seguro, deixe-me lembrá-lo

que a geração de chave no ElGamal escolhe um
gerador aleatório, um expoente aleatório de ZN

e, em seguida, a chave pública é simplesmente o
gerador de g e este elemento ao a,

ao passo que a chave secreta é simplesmente o
logaritmo discreto de h base de g. Este valor A.

Agora, a nossa forma de criptografar é que escolher um aleatório
expoente B de ZN. Calculamos o hash

G para a B e H para a B. E eu vou
Lembramos que H para o B é o Diffie

Hellman segredo, G para a AB. E então nós
realmente criptografar uma mensagem usando um

sistema de criptografia simétrica com a chave K
que é derivada da função hash. E

finalmente, a saída de texto cifrado é a G
a B, e o texto cifrado simétrico. O

nossa forma de descriptografar é que você sabe, como vimos
antes, basicamente, através de hash U ea

Diffie Hellman segredos, descriptografar o
sistema simétrico, e produzir o

mensagem M. Agora, no último segmento dissemos
ElGamal que é escolhido cifrado seguro sob

este interativo engraçado Diffie-Hellman
suposição. Eu não vou lembrá-lo que

o pressuposto é aqui, mas eu também vou dizer
que este tipo teorema de suscita duas muito

questões naturais. A primeira pergunta é
podemos provar CCA segurança de

ElGamal apenas com base no padrão
Pressuposto de Diffie-Hellman computacional,

a saber, a G para A, G para o B,
não pode calcular G para a AB. Podemos provar

escolhido-texto cifrado de segurança apenas com base em
isso? E a verdade é que existem dois

maneiras de fazer isso. A primeira opção é usar
um grupo onde o Diffie computacional

Pressuposto de Hellman é difícil. Mas é
comprovadamente equivalente ao interativo

Diffie Hellman suposição. E acontece
fora não é realmente difícil de

construção de tais grupos. Estes grupos são
chamados grupos bilineares. E de tal

grupos, sabemos que o sistema é ElGamal
texto cifrado escolhido seguro, estritamente baseadas

sob a Computational Diffie Hellman
suposição, pelo menos no oráculo aleatório

modelo. Eu vou te dizer que estes bi-linear
grupos são realmente construídos a partir de muito

especiais curvas elípticas. Portanto, há um pouco
mais estrutura algébrica que permite-nos

para provar esta equivalência de IDH e CDH.
Mas, em geral, quem sabe, talvez não

quer usar grupos curvas elípticas, talvez
você quer usar estrela ZP por algum motivo.

Então é uma pergunta muito natural perguntar.
Podemos mudar o sistema de tal forma que ElGamal

cifrado escolhido segurança de ElGamal agora pode ser provado, directamente com base no CDH, para qualquer grupo

CDH onde é difícil? [Agora com isso??] Assumindo
qualquer estrutura adicional sobre o grupo,

E acontece que a resposta é sim. E
há um tipo de uma construção elegante

chamado ElGamal gêmeo, então deixe-me mostrar-lhe
como gêmeo obras ElGamal. É uma forma muito simples

variação de ElGamal que faz o
sequência. Mais uma vez, na geração de chaves, nós

escolher um gerador aleatório. Mas, desta vez,
vamos escolher dois expoentes, A1 e

A2 como a chave secreta. Portanto, a chave é segredo
vai consistir desses dois expoentes, A1

e A2. Conhece a chave pública do curso
se vai consistir em nosso gerador. E

então nós vamos liberar G para a A1 e G
para a A2. Então lembre-se que em regular

ElGamal que a chave pública é simplesmente g
para o A e é isso. Aqui temos dois

expoentes A1 e A2 e, portanto, nós, nós
solte G para a A1 e G para a A2.

Agora, a nossa forma de criptografar, você vai notar a
chave pública é aqui um elemento de mais de

ElGamal regular. A forma como criptografar usando
esta chave pública é realmente muito semelhante

para ElGamal regular. Nós escolhemos um B aleatória,
e agora o que vamos hash é, na verdade, não

G apenas para a B e H1 para o B, mas,
de facto, para o G B, H1 para a B, e H2

para o B. Ok então nós basicamente hash
três elementos em vez de dois elementos e

então nós basicamente criptografar a mensagem
usando a chave de criptografia simétrica derivada

e como de costume, a saída para o g b e c como o nosso
último texto cifrado. Como podemos decifrar?

Bem, agora a chave secreta consiste em
esses dois expoentes, A1 e A2. E a

texto cifrado consiste em U, e a
simétrica texto cifrado C. Então deixe-me perguntar-lhe

um quebra-cabeça, e veja se você pode descobrir
como obter a chave de criptografia simétrica

K, dado apenas a chave secreta eo valor
U. Então, é uma espécie de quebra-cabeça bonito e eu

espero que todos trabalhados, a solução
que é basicamente o que podemos fazer é que

U pode levar à potência de A1, e que é
G basicamente à A1 B e U para a A2

que é G para a A2 B. E que, basicamente,
nos dá exatamente os mesmos valores, como a H1

o B e H2 para a B. Portanto, a forma como este
decryptor chega à mesma simétrica

chave que o codificador fez. Então, ele decifra
o texto cifrado com o sistema simétrico

e, finalmente, gera a mensagem M. Então você
Note que isto é uma modificação muito simples

para ElGamal regular. Tudo o que fazemos é ficar
mais um elemento para a chave pública. Quando

nós fazemos o hash, que um hash mais
elemento, em vez de apenas dois elementos.

Nós hash de três elementos. E da mesma forma, nós
descriptografia fazer fazendo, e nada mais

mudanças. O texto cifrado é o mesmo
comprimento como antes, e é isso, agora o

coisa surpreendente é que esta simples
modificação permite-nos agora provar escolhido

segurança texto cifrado diretamente com base em
padrão computacional Diffie-Hellman

suposição, ok? Ainda vamos
precisa assumir que temos uma simétrica

sistema de criptografia que nos fornece
autenticada criptografia e que o hash

função que estamos usando é um hash ideal
função no que chamamos de um oráculo aleatório

Mas, no entanto, dado que, o que pudermos
provar a segurança da cifra escolhida texto estritamente

baseado numa Computational Diffie-Hellman
suposição. Então agora o que é o custo disso?

Claro, se você pensar sobre isso, durante
criptografia e descriptografia, criptografia tem

fazer mais uma exponenciação, eo
decodificação tem que fazer mais uma

exponenciação. Assim, o codificador faz agora
exponenciações três em vez de dois, e

o decoder faz duas exponenciações
em vez de um. Então a questão é agora,

agora é uma questão filosófica. É este o
esforço extra vale a pena? Então você faz um trabalho mais

durante a criptografia e descriptografia. E sua
chave pública é um pouco maior, mas

que realmente não importa. O trabalho
durante a criptografia e descriptografia é mais

significativo. E, como resultado você começa
cifrado escolhido segurança baseado em espécie

de uma hipótese mais natural, ou seja,
Computational Diffie-Hellman em oposição a

estes interativo de aparência estranha
Diffie-Hellman suposição. Mas vale a pena

isso? Tipo de questão é que existem
grupos onde CDH detém IDH, mas não

segurar? Se houvesse tais grupos, então
seria definitivamente vale a pena, porque

esses grupos, o ElGamal duplo seria
seguro, mas o ElGamal regular não

CCA ser seguro. Mas, infelizmente, nós não
saber se existe qualquer desses grupos e em

fato de, tanto quanto sabemos, é certamente
possível que qualquer grupo que detém CDH,

IDH também tem. Portanto, a resposta é, realmente,
não sabemos se o custo extra é

vale a pena ou não, mas, em seguida, no entanto, é
um resultado bonito que mostra que se você quiser

para atingir cifrado escolhido
segurança diretamente da CDH, você pode fazer

TI sem muitas mudanças para o ElGamal
sistema. A próxima pergunta é se nós

pode se livrar deste pressuposto de que o
função hash é uma função ideal de hash

principalmente que é um oráculo aleatório. E esta
é realmente um grande tema. Há um monte de

trabalhar nesta área, sobre como construir
eficientes sistemas de criptografia de chave pública

que são escolhidos cifrado seguro sem
oráculos aleatórios. Esta é uma área muito ativa

de pesquisa, como eu disse na última década
e ainda mais tempo. E eu vou falar que, como

isto aplica-se a ElGamal, eles são, basicamente,
novamente duas famílias de construções. O

primeira construção é uma construção que
usa esses grupos especiais chamados estes

grupos bilineares que acabei de mencionar
antes. Acontece que a estrutura extra

desses grupos bilineares permite
construir muito eficiente escolhido cifrado

sistemas seguros sem referindo-se ao acaso
oráculos e como eu disse no final do

módulo, eu apontar para uma série de documentos que
explicar como fazer isso. Este é um grande

construção interessante. Mas vai demorar
me várias horas para o tipo de explicar como

obras. A outra alternativa é efectivamente
usar grupos, onde uma forte hipótese

denominada decisão suposição Diffie-Hellman
mantém. Mais uma vez, eu não vou definir esta

suposição aqui. Vou apenas dizer-lhe que
esta hipótese, na verdade, tem em

subgrupos de ZP estrela, em particular se
olhar para a forma principal de um subgrupo de

ZP estrela. A decisão Diffie-Hellman
suposição parece ter nesses grupos

e, em seguida, os grupos que podemos realmente
construir uma variante de ElGamal, chamado

sistema Cramer Shoup que é escolhido
cifrado seguro ea decisão

Diffie-Hellman suposição sem aleatório
oráculos. Mais uma vez, este é um belo

belo resultado, mas novamente seria necessário um
par de horas para explicar e por isso não tenho

vou fazer isso aqui. Este é provavelmente um
essas coisas que eu vou deixar para

tanto os tópicos avançados ou para fazer uma
curso avançado de modo que nós vamos fazê-lo em um

depois do tempo. Mas, novamente eu aponta para um papel
no final do módulo apenas um caso em que você

quiser ler mais sobre isso. Então aqui vai uma
lista de documentos que proporciona uma leitura mais

material. Então se você quer ler sobre
Suposições Diffie Hellman, eu acho que

escreveu um artigo sobre isso há muito tempo,
que fala sobre várias suposições

relacionado, a Diffie Hellman. E em
particular, estudos Diffie decisão

Suposição Hellman. E se você quer aprender
sobre como construir escolhida texto cifrado

sistema seguro de decisão Diffie-Hellman
e premissas gostar. Há um muito

papel bonito por volta Kramer e Shoup
a partir de 2002 que mostra como fazê-lo. Isto é

mais uma vez um papel muito bem recomendado. Se
você quer aprender a construir escolhido

cifrado segurança destas
grupos bilineares, em seguida, o papel é para ler

a um, aqui citados, que, na verdade, usa um
mecanismo geral chamada Identidade Baseado

Criptografia que muito surpreendentemente,
Acontece que realmente nos dá escolhido

cifrado segurança quase de graça.
Assim, uma vez que construímos baseado em identidade

criptografia escolhido cifrado segurança cai
imediatamente. E isso é abordado neste

papel que eu, que eu descrevê-la. O
Dupla construção Diffie-Hellman e sua

prova é descrito neste trabalho que eu
referência aqui E, finalmente, se você meio que

quero ver um papel muito recente. Que
dá um quadro muito geral para

construção de sistemas de texto cifrado, escolhidos segura, utilizando
o que é chamado de hash que extraíveis provas

é mais uma vez um papel bonito por Hoeteck Wee, que
foi recentemente publicado. Eu definitivamente

recomendo a leitura de tudo, tudo tem
idéias muito, muito elegantes eles. Eu gostaria de

poderia cobrir todos eles no básico
claro, mas eu vou ter que deixar algumas de

estes para o curso mais avançado ou
talvez os tópicos mais avançados no

final do curso. Ok, então eu vou parar
aqui e no segmento seguinte, eu vou amarrar

Criptografia RSA e ElGamal
em conjunto para que você veja como o tipo dois

de acompanhamento de um princípio mais geral.