Criptografia baseada em emparelhamento

A criptografia baseada em emparelhamento é o uso de um emparelhamento [en] entre elementos de dois grupos criptográficos para um terceiro grupo com um mapeamento ${\displaystyle e:G_{1}\times G_{2}\to G_{T}}$ para construir ou analisar sistemas criptográficos.

A seguinte definição é comumente usada na maioria dos artigos acadêmicos.^[1]

Seja ${\displaystyle F_{q}}$ um campo finito sobre o primo ${\displaystyle q}$, ${\displaystyle G_{1},G_{2}}$ dois grupos cíclicos aditivos de ordem principal ${\displaystyle q}$ e ${\displaystyle G_{T}}$ outro grupo cíclico de ordem ${\displaystyle q}$ escrito multiplicativamente. Um par é um mapa :${\displaystyle e:G_{1}\times G_{2}\rightarrow G_{T}}$, que satisfaz as seguintes propriedades:

Bilinearidade [en]

${\displaystyle \forall a,b\in F_{q}^{*},P\in G_{1},Q\in G_{2}:\ e\left(aP,bQ\right)=e\left(P,Q\right)^{ab}}$

Não degenerescência

${\displaystyle e\neq 1}$

Computabilidade

Existe um algoritmo eficiente para calcular ${\displaystyle e}$.

Se o mesmo grupo for usado para os primeiros dois grupos (ou seja, ${\displaystyle G_{1}=G_{2}}$), o emparelhamento é denominado simétrico e é um mapeamento de dois elementos de um grupo para um elemento de um segundo grupo.

Alguns pesquisadores classificam as instanciações de emparelhamento em três (ou mais) tipos básicos:

1. ${\displaystyle G_{1}=G_{2}}$;
2. ${\displaystyle G_{1}\neq G_{2}}$ mas há um homomorfismo eficientemente computável ${\displaystyle \phi :G_{2}\to G_{1}}$;
3. ${\displaystyle G_{1}\neq G_{2}}$ e não há homomorfismos eficientemente computáveis entre ${\displaystyle G_{1}}$ e ${\displaystyle G_{2}}$.^[2]

Se simétricos, os pares 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 um mapeamento bilinear [en], como o emparelhamento Weil [en] ou o emparelhamento de Tate [en], as generalizações do problema computacional Diffie–Hellman são consideradas inviáveis, enquanto o problema de Diffie-Hellman decisional [en] mais simples pode ser facilmente resolvido usando a função de emparelhamento. O primeiro grupo é às vezes chamado de Grupo Gap devido à diferença de dificuldade assumida entre esses dois problemas no grupo.

Embora usado pela primeira vez para criptoanálise,^[3] os emparelhamentos também foram usados ​​para construir muitos sistemas criptográficos para os quais nenhuma outra implementação eficiente é conhecida, como criptografia baseada em identidade ou esquemas de criptografia baseada em atributos [en].

A criptografia baseada em emparelhamento é usada no esquema de confirmação criptográfica KZG [en].

Um exemplo contemporâneo de uso de pares bilineares é exemplificado no esquema de assinatura de Boneh–Lynn–Shacham [en].

A criptografia baseada em emparelhamento depende de suposições de dureza separadas, por exemplo, do problema do logaritmo discreto da curva elíptica, que é mais antigo e tem sido estudado por um longo tempo.

Em junho de 2012, o Instituto nacional de tecnologia da informação e comunicação (NICT) [en], a universidade Kyushu e os Laboratórios da Fujitsu [en] aprimoraram o limite anterior para calcular com sucesso um logaritmo discreto em uma curva elíptica supersingular [en] de 676 bits para 923 bits.^[4]

Referências

• Palestra sobre criptografia baseada em emparelhamento (em inglês)
• Biblioteca de criptografia baseada em emparelhamento (PBC) de Ben Lynn (em inglês)