Problema Diffie–Hellman

Sobre

• O problema Diffie-Hellman (PDH), em inglês Diffie–Hellman problem (DHP) é um problema matemático que foi primeiramente proposto por Whitfield Diffie e Martin Hellman no contexto de criptografia. A motivação para este problema é que muitos sistemas seguros usam operações matemáticas que são fáceis de calcular, e difíceis de inverter. Por exemplo, eles possibilitam encriptar uma mensagem, mas inverter a encriptação é difícil. Se resolver o PDH fosse fácil, estes esquemas seriam facilmente quebrados.

Complexidade Computacional

Na criptografia, para certos grupos, presume-se que o DHP é difícil, e isso é frequentemente chamado de suposição de Diffie-Hellman. O problema sobreviveu ao escrutínio por algumas décadas e nenhuma solução "fácil" foi divulgada ainda.

A partir de 2006, o meio mais eficiente conhecido para resolver o DHP é resolver o problema do logaritmo discreto (DLP), que é encontrar x dados ge gx. Na verdade, um progresso significativo (por den Boer, Maurer, Wolf, Boneh e Lipton) foi feito no sentido de mostrar que em muitos grupos o DHP é quase tão difícil quanto o DLP. Não há prova até o momento de que o DHP ou o DLP sejam um problema difícil, exceto em grupos genéricos (por Nechaev e Shoup). Uma prova de que qualquer um dos problemas é difícil implica que P ≠ NP.

Descrição do problema

• O problema Diffie-Hellman é declarado informalmente como seguinte: Dado um elemento g e os valores de g^x e g^y, qual o valor de g^xy? Formalmente, g é um gerador de algum grupo (tipicamente o grupo multiplicativo de um corpo finito ou m grupo de curva elíptica) e x e y são inteiros escolhidos aleatoriamente. Por exemplo, na troca de chave Diffie-Hellman, um abelhudo observa g^x e g^y, trocados como parte do protocolo, e as duas partes ambas calculam a chave partilhada g^xy. Um meio rápido de resolver o PDH permitiria um abelhudo violar a privacidade da troca de chave de Diffie-Hellman e muitas das suas variantes, incluindo o esquema de encriptação ElGmal.

Outras variantes

• Muitas variantes do problema Diffie-Hellman foram consideradas. A variante mais significativa é o problema decisional Diffie-Hellman (decisional Diffie-Hellman problem, DDHP), que consistir em distinguir g^xy de um grupo de elementos aleatórios, dados g, g^x e g^y. Algumas vezes o PDH é chamado o problema computacional Diffie-Hellman (computacional Diffie-Hellman problem) para distinguir mais claramente do DDHP. Recentemente, grupos com emparelhamentos tornaram-se populares e nestes grupos o DDHP é fácil, no entanto, o DHP é ainda assumido ser difícil.

Referências

Tradução do artigo em inglês [Diffie–Hellman]