A criptografia baseada em pareamentos é o uso de um pareamento entre elementos de dois grupos criptográficos para um terceiro grupo com um mapeamento para construir ou analisar sistemas criptográficos.
Definição A seguinte definição é comumente utilizada na maioria dos artigos acadêmicos.
Seja um corpo finito sobre um primo , dois grupos cíclicos de ordem prima (geralmente escritos na notação aditiva) e outro grupo cíclico de ordem escrito multiplicativamente. Um pareamento é uma aplicação: , que satisfaz as seguintes propriedades: Bilinearidade Não degenerescência Se é um gerador de e é um gerador de , então é um gerador de (ou seja, ). Computabilidade Existe um algoritmo eficiente para computar .
Classificação Se o mesmo grupo for usado para os dois primeiros grupos (ou seja, ), o pareamento é chamado de simétrico e é uma aplicação de dois elementos de um grupo para um elemento de um segundo grupo.
Alguns pesquisadores classificam as instanciações de pareamento em três (ou mais) tipos básicos: ; , mas existe um homomorfismo eficientemente computável ; e não existem homomorfismos eficientemente computáveis entre e .
Uso na criptografia Se forem simétricos, os pareamentos podem ser usados para reduzir um problema difícil em um grupo a um problema diferente, geralmente mais fácil, em outro grupo.
Por exemplo, em grupos equipados com uma aplicação bilinear como o pareamento de Weil ou o pareamento de Tate, acredita-se que generalizações do problema computacional de Diffie–Hellman (CDH) sejam inviáveis, enquanto o problema de Diffie–Hellman de decisão (DDH), mais simples, pode ser facilmente resolvido usando a função de pareamento. O primeiro grupo é às vezes chamado de Grupo de Gap devido à suposta diferença de dificuldade entre esses dois problemas no grupo.
Para ilustrar, seja um pareamento bilinear simétrico, não degenerado e eficientemente computável, onde é um grupo multiplicativo com gerador . Considere uma instância do problema CDH: dados , e , o objetivo é computar . A função de pareamento não nos ajuda diretamente a computar , mantendo o problema CDH presumivelmente difícil. No entanto, dado um candidato a solução , podemos verificar se (resolvendo o problema DDH) sem o conhecimento de , ou , testando se a seguinte igualdade é válida:
Pela propriedade de bilinearidade, podemos extrair os expoentes:
e
Como é um grupo de ordem prima, a igualdade implica diretamente que , validando a resposta de forma eficiente.
Embora tenham sido usados inicialmente para criptoanálise, os pareamentos também têm sido utilizados para construir muitos sistemas criptográficos para os quais nenhuma outra implementação eficiente é conhecida, tais como esquemas de criptografia baseada em identidade ou criptografia baseada em atributos.
A criptografia baseada em pareamentos é usada no esquema de compromisso criptográfico KZG e é exemplificada no esquema de assinatura digital BLS.
Criptoanálise Em junho de 2012, o Instituto Nacional de Tecnologia de Informação e Comunicação (NICT), a Universidade de Kyushu e a Fujitsu Laboratories Limited melhoraram o limite anterior para computar com sucesso um logaritmo discreto em uma curva elíptica supersingular de 676 bits para 923 bits.
Em 2016, o algoritmo Extended Tower Number Field Sieve (Crivo do Corpo de Números em Torre Estendida - exTNFS) permitiu reduzir a complexidade de encontrar logaritmos discretos em alguns grupos resultantes de pareamentos. Existem várias variantes do algoritmo de crivo de corpo de números em torre múltipla e estendida, expandindo a aplicabilidade e melhorando a complexidade do algoritmo. Uma descrição unificada de todos esses algoritmos com melhorias adicionais foi publicada em 2019. Tendo em vista esses avanços, vários trabalhos forneceram estimativas concretas revisadas sobre os tamanhos de chave de criptosistemas seguros baseados em pareamentos.
Referências
Ligações externas Aula sobre Criptografia Baseada em Pareamentos Biblioteca PBC de Ben Lynn
Categoria:Criptografia de curvas elípticas