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 $e:G_{1}\times G_{2}\to G_{T}$ para construir ou analisar sistemas criptográficos.

Definição

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

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

Bilinearidade [en]

$\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

$e\neq 1$

Computabilidade

Existe um algoritmo eficiente para calcular $e$.

Classificação

Se o mesmo grupo for usado para os primeiros dois grupos (ou seja, $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. $G_{1}=G_{2}$;
2. $G_{1}\neq G_{2}$ mas há um homomorfismo eficientemente computável $\phi :G_{2}\to G_{1}$;
3. $G_{1}\neq G_{2}$ e não há homomorfismos eficientemente computáveis entre $G_{1}$ e $G_{2}$.

Uso em criptografia

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, 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.

Criptoanálise

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.

Ligações externas

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