Criptografia baseada em emparelhamento: diferenças entre revisões

Conteúdo apagado Conteúdo adicionado

Em linha

Edição atual tal como às 22h05min de 3 de novembro de 2023

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[editar | editar código-fonte]

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

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[editar | editar código-fonte]

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:

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

Uso em criptografia[editar | editar código-fonte]

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.

Criptoanálise[editar | editar código-fonte]

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

↑ Koblitz, Neal; Menezes, Alfred (2005). «Pairing-based cryptography at high security levels». Cryptography and Coding. Col: Lecture notes in Computer science (em inglês). 3796. [S.l.: s.n.] pp. 13–36. ISBN 978-3-540-30276-6. doi:10.1007/11586821_2
↑ Galbraith, Steven; Paterson, Kenneth; Smart, Nigel (2008). «Pairings for cryptographers». Discrete applied Mathematics (em inglês). 156 (16): 3113–3121. doi:10.1016/j.dam.2007.12.010
↑ Menezes, Alfred J. Menezes; Okamato, Tatsuaki; Vanstone, Scott A. (1993). «Reducing elliptic curve logarithms to logarithms in a finite field». IEEE transactions on Information theory (em inglês). 39 (5): 1639–1646. doi:10.1109/18.259647
↑ «NICT, Kyushu University and Fujitsu laboratories achieve world record cryptanalysis of next-generation cryptography». Comunicado de imprensa do NICT (em inglês). 18 de junho de 2012

Ligações externas[editar | editar código-fonte]

[1] Koblitz, Neal; Menezes, Alfred (2005). «Pairing-based cryptography at high security levels». Cryptography and Coding. Col: Lecture notes in Computer science (em inglês). 3796. [S.l.: s.n.] pp. 13–36. ISBN 978-3-540-30276-6. doi:10.1007/11586821_2

[pfc-2] Galbraith, Steven; Paterson, Kenneth; Smart, Nigel (2008). «Pairings for cryptographers». Discrete applied Mathematics (em inglês). 156 (16): 3113–3121. doi:10.1016/j.dam.2007.12.010

[3] Menezes, Alfred J. Menezes; Okamato, Tatsuaki; Vanstone, Scott A. (1993). «Reducing elliptic curve logarithms to logarithms in a finite field». IEEE transactions on Information theory (em inglês). 39 (5): 1639–1646. doi:10.1109/18.259647

[4] «NICT, Kyushu University and Fujitsu laboratories achieve world record cryptanalysis of next-generation cryptography». Comunicado de imprensa do NICT (em inglês). 18 de junho de 2012

[1]

[2]

[3]

[4]

@@ Linha 1: / Linha 1: @@
-A '''criptografia baseada em emparelhamento''' é o uso de um <!-- [[:en:Pairing]] -->emparelhamento entre elementos de dois [[Grupo (matemática)|grupos]] criptográficos para um terceiro grupo com um mapeamento <math>e :G_1 \times G_2 \to G_T</math> para construir ou analisar [[Sistema criptográfico|sistemas criptográficos]].
+A '''criptografia baseada em emparelhamento''' é o uso de um emparelhamento{{Ill|en||Pairing|nlk=true}} entre elementos de dois [[Grupo (matemática)|grupos]] criptográficos para um terceiro grupo com um mapeamento <math>e :G_1 \times G_2 \to G_T</math> para construir ou analisar [[Sistema criptográfico|sistemas criptográficos]].
 ==Definição==
-A seguinte definição é comumente usada na maioria dos artigos acadêmicos.<ref>{{cite journal|last1=Koblitz|first1=Neal|last2=Menezes|first2=Alfred|title=Criptografia baseada em emparelhamento em altos níveis de segurança|journal=LNCS|date=2005|volume=3796|language=en}}</ref>
+A seguinte definição é comumente usada na maioria dos artigos acadêmicos.<ref>{{Cite book|last1=Koblitz|first1=Neal|last2=Menezes|first2=Alfred|title=Cryptography and Coding|chapter=''Pairing-based cryptography at high security levels''|series=''Lecture notes in Computer science''|year=2005|volume=3796|pages=13–36 |doi=10.1007/11586821_2|isbn=978-3-540-30276-6|language=en}}</ref>
 Seja <math>F_q</math> um [[Corpo finito|campo finito]] sobre o primo <math>q</math>, <math>G_1, G_2</math> dois [[Grupo cíclico|grupos cíclicos]] aditivos de ordem principal <math>q</math> e <math>G_T</math> outro grupo cíclico de ordem <math>q</math> escrito multiplicativamente. Um par é um mapa :<math> e: G_1 \times G_2 \rightarrow G_T </math>, que satisfaz as seguintes propriedades:
-; <!-- [[:en:Bilinear map]] -->Bilinearidade: <math> \forall a,b \in F_q^*,\ \forall P\in G_1, Q\in G_2:\ e\left(aP, bQ\right) = e\left(P, Q\right)^{ab}</math>
+; Bilinearidade{{Ill|en||Bilinear map|nlk=true}}: <math> \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}</math>
 ; [[Degeneração (matemática)|Não degenerescência]]: <math>e \neq 1</math>
 ; Computabilidade: Existe um [[algoritmo]] eficiente para calcular <math>e</math>.
@@ Linha 17: / Linha 17: @@
 # <math> G_1 = G_2</math>;
 # <math> G_1 \ne G_2</math> mas há um [[homomorfismo]] ''eficientemente computável'' <math>\phi : G_2 \to G_1</math>;
-# <math> G_1 \ne G_2</math> e não há homomorfismos ''eficientemente computáveis'' entre <math>G_1</math> e <math>G_2</math>.<ref name="pfc">{{cite journal|last1=Galbraith|first1=Steven|last2=Paterson|first2=Kenneth|last3=Smart|first3=Nigel|title=Emparelhamentos para criptógrafos|journal=Discrete Applied Mathematics|date=2008|volume=156|issue=16|pages=3113 à 3121|doi=10.1016/j.dam.2007.12.010<!-- |doi-access=free -->|language=en}}</ref>
+# <math> G_1 \ne G_2</math> e não há homomorfismos ''eficientemente computáveis'' entre <math>G_1</math> e <math>G_2</math>.<ref name="pfc">{{Cite journal|last1=Galbraith|first1=Steven|last2=Paterson|first2=Kenneth|last3=Smart|first3=Nigel|title=''Pairings for cryptographers''|journal=Discrete applied Mathematics|year=2008|volume=156|issue=16|pages=3113–3121|doi=10.1016/j.dam.2007.12.010|doi-access=free|language=en}}</ref>
 ==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 <!-- [[:en:Bilinear map]]-->mapeamento bilinear , como o <!-- [[:en:Weil pairing]] -->emparelhamento Weil ou o <!-- [[:en:Tate pairing]] -->emparelhamento Tate , as generalizações do [[Problema Diffie–Hellman|problema computacional Diffie–Hellman]] são consideradas inviáveis, enquanto o <!-- [[:en:Decisional Diffie–Hellman assumption]] -->problema Diffie-Hellman decisional 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.
+Por exemplo, em grupos equipados com um mapeamento bilinear{{Ill|en||Bilinear map|nlk=true}}, como o emparelhamento Weil{{Ill|en||Weil pairing|nlk=true}} ou o emparelhamento de Tate{{Ill|en||Tate pairing|nlk=true}}, as generalizações do [[Problema Diffie–Hellman|problema computacional Diffie–Hellman]] são consideradas inviáveis, enquanto o problema de Diffie-Hellman decisional{{Ill|en||Decisional Diffie–Hellman assumption|nlk=true}} 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]],<ref>{{cite journal|last1=Menezes|first1=Alfred J. Menezes|last2=Okamato|first2=Tatsuaki|last3=Vanstone|first3=Scott A.|title=Reduzindo logaritmos da curva elíptica para logaritmos em um campo finito|journal=Transações IEEE na teoria da informação|date=1993|volume=39|issue=5|language=en}}</ref> os emparelhamentos também foram usados para construir muitos sistemas criptográficos para os quais nenhuma outra implementação eficiente é conhecida, como <!--  [[:en:Identity-based encryption]] -->criptografia baseada em identidade ou esquemas de <!-- [[:en:Attribute-based encryption]] -->criptografia baseada em atributos.
+Embora usado pela primeira vez para [[criptoanálise]],<ref>{{Cite journal|last1=Menezes|first1=Alfred J. Menezes|last2=Okamato|first2=Tatsuaki|last3=Vanstone|first3=Scott A.|title=''Reducing elliptic curve logarithms to logarithms in a finite field''|journal=IEEE transactions on Information theory|year=1993|volume=39|issue=5|pages=1639–1646 |doi=10.1109/18.259647|language=en}}</ref> os emparelhamentos também foram usados para construir muitos sistemas criptográficos para os quais nenhuma outra implementação eficiente é conhecida, como <!--  [[:en:Identity-based encryption]] -->criptografia baseada em identidade ou esquemas de criptografia baseada em atributos{{Ill|en||Attribute-based encryption|nlk=true}}.
-A criptografia baseada em emparelhamento é usada no <!-- [[:en:Commitment scheme#KZG commitment]] -->esquema de confirmação criptográfica KZG.
+A criptografia baseada em emparelhamento é usada no esquema de confirmação criptográfica KZG{{Ill|en||Commitment scheme#KZG commitment|nlk=true}}.
-Um exemplo contemporâneo de uso de pares bilineares é exemplificado no esquema de assinatura <!-- [[:en:BLS digital signature]] -->Boneh–Lynn–Shacham.
+Um exemplo contemporâneo de uso de pares bilineares é exemplificado no esquema de assinatura de Boneh–Lynn–Shacham{{Ill|en||BLS digital signature||nlk=true}}.
 A criptografia baseada em emparelhamento depende de suposições de dureza separadas, por exemplo, do [[Criptografia de curva elíptica|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 <!-- [[:en:National Institute of Information and Communications Technology]] -->instituto nacional de [[tecnologia da informação]] e comunicação (''NICT''), a [[universidade Kyushu]] e os <!-- [[:en:Fujitsu#Fujitsu Laboratories]] -->Laboratórios ''Fujitsu'' aprimoraram o limite anterior para calcular com sucesso um logaritmo discreto em uma <!-- [[:en:Supersingular elliptic curve]] -->curva elíptica supersingular de 676 ''bits'' para 923 ''bits''.<ref>{{cite web |work=Press release from NICT |date=18-06-2012 |url=http://www.nict.go.jp/en/press/2012/06/18en-1.html |title=O instituto nacional de tecnologia da informação e comunicação (''NICT''), a universidade Kyushu e os Laboratórios Fujitsu alcançam recorde mundial de criptoanálise de criptografia de última geração |language=en}}</ref>
+Em junho de 2012, o Instituto nacional de [[tecnologia da informação]] e comunicação (''NICT''){{Ill|en||National Institute of Information and Communications Technology|nlk=true}}, a [[universidade Kyushu]] e os Laboratórios da ''Fujitsu''{{Ill|en||Fujitsu#Fujitsu Laboratories|nlk=true}} aprimoraram o limite anterior para calcular com sucesso um logaritmo discreto em uma curva elíptica supersingular{{Ill|en||Supersingular elliptic curve|nlk=true}} de 676 ''bits'' para 923 ''bits''.<ref>{{Cite web|work=Comunicado de imprensa do NICT|date=18-06-2012|url=http://www.nict.go.jp/en/press/2012/06/18en-1.html|title=''NICT, Kyushu University and Fujitsu laboratories achieve world record cryptanalysis of next-generation cryptography''|language=en}}</ref>
-{{referências}}
+{{Referências}}
 ==Ligações externas==
-*[https://courses.csail.mit.edu/6.897/spring04/L25.pdf Palestra sobre criptografia baseada em emparelhamento (em inglês)]
+* [https://courses.csail.mit.edu/6.897/spring04/L25.pdf Palestra sobre criptografia baseada em emparelhamento (em inglês)]
-*[http://crypto.stanford.edu/pbc/ Biblioteca PBC de Ben Lynn]
+* [http://crypto.stanford.edu/pbc/ Biblioteca de criptografia baseada em emparelhamento (''PBC'') de Ben Lynn (em inglês)]
 [[Categoria:Criptografia de chave pública]]
+<!-- [[:en:Category:Elliptic curve cryptography]] -->