Criptosistema Bonnet-Go-Nissima

El criptosistema Bonet-Go-Nishima es un criptosistema parcialmente homomórfico , que es una modificación del criptosistema Paye [1] y del criptosistema Okamoto-Uchiyama [2] . Desarrollado en 2005 por Dan Bonet [3] con Yu Jin Go y Koby Nissim [4] [5] . Basado en grupos finitos de orden compuesto y emparejamientos bilineales en curvas elípticas; el sistema permite evaluar polinomios cuadráticos multivariados sobre textos cifrados (por ejemplo, forma normal disyuntiva de segundo orden (2- DNF )).

El sistema tiene un homomorfismo aditivo (admite sumas arbitrarias y una multiplicación (seguida de sumas arbitrarias) para datos encriptados).

El algoritmo utilizado en el criptosistema BGN se basa en el problema de Burnside . [6] .

Algoritmo de operación

Como todos los sistemas de cifrado homomórfico, CBGN incluye los siguientes procesos: Generación de claves, cifrado y descifrado.

La construcción utiliza algunos grupos finitos de orden compuesto que admiten un mapeo bilineal. Se utiliza la siguiente notación:

${\ estilo de visualización \ mathbb {G}}$ y son dos grupos cíclicos de orden finito . ${\ estilo de visualización \ mathbb {G} _ {1}}$ ${norte}$
${gramo}$ - generador . ${\ estilo de visualización \ mathbb {G}}$
${\ estilo de visualización {f}}$ es una aplicación bilineal . En otras palabras, para todos y tenemos . También requerimos que : sea un generador ${\displaystyle {f}:\mathbb {G} \times \mathbb {\mathbb {G} } \rightarrow \mathbb {G} _{1))$ ${u},{v}\en \mathbb {G}$ ${a},{b}\en \mathbb {Z}$ ${f}({u}^{a},{v}^{b})={f}({u},{v})^{{a}{b))$ ${\ estilo de visualización {f} ({g}, {g})}$ ${\ estilo de visualización \ mathbb {G} _ {1}}$

Decimos que es un grupo bilineal si existe un grupo y un mapeo bilineal definido anteriormente. [7] ${\ estilo de visualización \ mathbb {G}}$ ${\ estilo de visualización \ mathbb {G} _ {1}}$

Generación de claves

Generar_Clave( ) : $\tau$

Dado el parámetro de seguridad como entrada , calculamos el algoritmo para obtener una tupla . El algoritmo funciona así: ${\displaystyle \tau \in \mathbb {Z} ^{+))$ ${\ estilo de visualización X (\ tau)}$ $({q}_{1},{q}_{2},\mathbb {G} ,\mathbb {G}_{1},{f})$
1. Generemos dos números de bits aleatorios y establezcamos . $\tau$ ${\ estilo de visualización {q}_{1}}$ ${\ estilo de visualización {q} _ {2}}$ ${n}={q}_{1}{q}_{2}\en \mathbb {Z}$
2. Vamos a crear un grupo bilineal de orden , donde > 3 es un número dado que no es divisible por 3: ${\ estilo de visualización \ mathbb {G}}$ ${norte}$ ${norte}$
  1. Encuentre el número natural más pequeño tal que sea un número primo y . $\ell \in \mathbb {Z}$ ${p}=\ell{n}-1$ ${\displaystyle {p=3{\bmod {4))))$
  2. Considere un grupo de puntos en una curva elíptica definida sobre . Como la curva tiene puntos en . Por tanto, el grupo de puntos de la curva tiene un subgrupo de orden , que denotaremos por . ${\ estilo de visualización {y^{2}=x^{3}+x}}$ ${\ estilo de visualización \ mathbb {F} _ {p}}$ ${\displaystyle {p=3{\bmod {4))))$ ${p}+1=\ell{n}$ ${\ estilo de visualización \ mathbb {F} _ {p}}$ ${norte}$ ${\ estilo de visualización \ mathbb {G}}$
  3. Sea el subgrupo de orden . El algoritmo de emparejamiento de Weil modificado (el emparejamiento de Weyl es un mapeo bilineal, asimétrico, no degenerado [8] [4] [9] [10] ) en una curva produce un mapeo bilineal que satisface las condiciones dadas ${\ estilo de visualización \ mathbb {G} _ {1}}$ $\mathbb {F}_{{p}^{2}}^{*}$ ${norte}$ ${\displaystyle {f}:\mathbb {G} \times \mathbb {\mathbb {G} } \rightarrow \mathbb {G} _{1))$
3. En la salida obtenemos . $({q}_{1},{q}_{2},\mathbb {G} ,\mathbb {G}_{1},{f})$
deja _ Elijamos dos generadores aleatorios y definamos como . Entonces es un generador de orden de subgrupos aleatorios . Clave pública: . Clave privada: . [11] [7] ${n}={q}_{1}\times {q}_{2}$ ${g},{u}{\xleftarrow {R}}\mathbb {G}$ ${\ estilo de visualización {h}}$ ${h}={u}^{q_{2))$ ${\ estilo de visualización {h}}$ ${\ estilo de visualización \ mathbb {G}}$ ${q_{1}}$ ${O}{K}=({n},\mathbb {G} ,\mathbb {G_{1}} ,{f},{g},{h})$ ${S}{K}={q_{1}}$

Cifrado

Cifrado( ): ${\ estilo de visualización OK, M}$

Suponemos que el espacio del mensaje consta de números enteros en el conjunto . Para cifrar un mensaje utilizando la clave pública , elegimos un parámetro aleatorio y calculamos ${\ estilo de visualización \ {0, T \}}$ $METRO$ $OK$ ${r}{\xleftarrow {R}}\{0,1,...,{n}-1\}$

${C}={g}^{M}{h}^{r}\en \mathbb {G}$ .

El resultado es el texto cifrado. [11] [7]

Descifrado

Decodificar( ): $SK,C$

Para descifrar el texto cifrado usando la clave privada , considere la siguiente expresión $SK=q_{1}$

${C}^{q_{1}}=({g}^{M}{h}^{r})^{q_{1}}=({g}^{q_{1}}) ^{M}$ .

deja _ Para restaurar , basta con calcular el logaritmo discreto a la base . ${\sombrero {g}}={g}^{q_{1}}$ ${METRO}$ ${\ estilo de visualización {C}^{q_{1))}$ ${\ estilo de visualización {\ sombrero {g))}$

Cabe señalar que el descifrado en este sistema requiere un tiempo polinomial en el tamaño del espacio del mensaje. [11] [7]

Ejemplos

Un ejemplo de cómo funciona el algoritmo

Primero elegimos dos primos diferentes

${\ estilo de visualización {{q}_{1} = 7}}$ ${\ estilo de visualización {{q}_{2} = 11}}$ .

Calcular el producto

${\displaystyle {{n}={q}_{1}{q}_{2}=7\times 11=77))$ .

A continuación, construimos un grupo de curvas elípticas con order , que tiene un mapeo bilineal. Ecuación de la curva elíptica ${norte}$

${\ estilo de visualización {y^{2}=x^{3}+x}}$

que se define sobre un campo para algún número primo . En este ejemplo, estamos configurando ${\ estilo de visualización \ mathbb {F} _ {p}}$ ${\displaystyle {p=3{\bmod {4))))$

${\ estilo de visualización {p = 307}}$ .

Por lo tanto, la curva es supersingular con # puntos racionales, que contiene un subgrupo de orden . En el grupo, elegimos dos generadores aleatorios. ${(E(p))=p+1=308}$ ${\ estilo de visualización \ mathbb {G}}$ ${\ estilo de visualización {{n} = 77 (= 308/4)))$ ${\ estilo de visualización \ mathbb {G}}$

${\ estilo de visualización {g = [182240]}}$ , ${\ estilo de visualización {u = [28262]}}$

donde estos dos generadores tienen orden y calculan ${norte}$

${h=u^{q_{2}}=[28 262]^{11}=[99 120]}$

donde esta el orden . Calculamos el texto cifrado del mensaje ${\ estilo de visualización {h}}$ ${\ estilo de visualización {q_ {1} = 7))$

${\ estilo de visualización {M} {= 2}}$ .

Tomemos y calculemos ${\ estilo de visualización {r = 5}}$

${C={g}^{M}{h}^{r}=[182 240]^{2}\oplus [99 120]^{5}=[256 265]}$ .

Para descifrar, primero calculamos

${\sombrero {g}}={g^{q_{1}}=[182,240]^{7}=[146,60]}$

${C}^{q_{1}}=({g}^{M}{h}^{r})^{q_{1}}=({g}^{q_{1}}) ^{M}={[256,265]^{7}=[299,44]}$ .

Ahora encontramos el logaritmo discreto, clasificando todas las potencias de la siguiente manera ${\sombrero {g}}={g}^{q_{1}}$

${\sombrero {g}}^{1}={[146,60]}$

${\sombrero {g}}^{2}={[299,44]}$

${\sombrero {g}}^{3}={[272,206]}$

${\sombrero {g}}^{4}={[191,151]}$

${\sombrero {g}}^{5}={[79,171]}$

${\sombrero {g}}^{6}={[79,136]}$

${\sombrero {g}}^{7}={[191,156]}$

${\sombrero {g}}^{8}={[272,101]}$

${\sombrero {g}}^{9}={[299,263]}$

${\sombrero {g}}^{10}={[146,247]}$

${\hat {g}}^{11}={\infty}$ .

Tenga en cuenta que Por lo tanto, el descifrado del texto cifrado es igual a , que corresponde al mensaje original. [12] ${\displaystyle {\sombrero {g}}^{2}={C^{q_{1))))$ ${\ estilo de visualización {2}}$

Evaluación 2-DNF

Un sistema parcialmente homomórfico permite estimar 2- DNF .

Entrada: Alice tiene una fórmula 2-DNF y Bob tiene un conjunto de variables . Ambos lados de la entrada contienen una configuración de seguridad . $\phi (x_{1},...,x_{n})=\lor _{i=1}^{k}(l_{i,1}\land l_{i,2})$ ${a=a_{1},...,a_{n}\en \{0,1\}^{n))$ $\tau$

Bob hace lo siguiente:
1. Ejecuta el algoritmo Generate_Key( ) para calcularlo y enviárselo a Alice. $\tau$ ${O}{K},{SK}$ ${\ estilo de visualización {O} {K}}$
2. Calcula y envía Cipher( ) ${O}{K},{a_{j))$ para . ${\ estilo de visualización {j = 1,..., n}}$
Alicia hace lo siguiente:
1. Realiza la aritmetización reemplazando “ ” por “ ”, “ ” por “ ”, y “ ” por “ ”. Tenga en cuenta que este es un polinomio de grado 2. ${\ estilo de visualización \ phi (\ phi)}$ $\lor$ $+$ $\tierra$ $\veces$ ${\ estilo de visualización {\ bar {x_ {j}}}}$ ${\ estilo de visualización (1-x_ {j})}$ $\Fi$
2. Alice calcula un cifrado para uno elegido al azar utilizando las propiedades homomórficas del sistema de cifrado. El resultado se envía a Bob. ${r}\veces \Phi ({a})$ ${r}$
Si Bob recibe el cifrado " ", genera " "; de lo contrario, genera " ". [13] ${\ estilo de visualización 0}$ ${\ estilo de visualización 0}$ $una$

Propiedades homomórficas

El sistema es aditivamente homomórfico. Sea la clave pública. Sean los textos cifrados de los mensajes, respectivamente. Cualquiera puede crear un cifrado distribuido uniformemente calculando el producto de un número aleatorio en el rango . $({n},\mathbb {G} ,\mathbb {G_{1)) ,{f},{g},{h})$ ${C_{1}},{C_{2}}\en \mathbb {G} _{1}$ ${m_{1}},{m_{2}}\en \{0,1\}$ ${m_{1}}+{m_{2}}{\bmod{n}}$ ${C}={C_{1}}{C_{2}}{h}^{r}$ ${r}$ ${\ estilo de visualización \ {0,1,..., {n}-1\))$

Más importante aún, cualquiera puede multiplicar dos mensajes encriptados una vez usando el mapeo bilineal. Definamos y . Entonces ordena y ordena . Además, para algún parámetro (desconocido) , escribimos . Supongamos que conocemos dos textos cifrados , . Para construir la encriptación del producto , elegimos un número aleatorio y lo configuramos . Obtenemos , donde se distribuye uniformemente en , según se requiera. ${g_{1}}={f}({g},{g})$ ${h_{1}}={f}({g},{h})$ ${\ estilo de visualización {g_{1))}$ ${norte}$ ${\ estilo de visualización {h_ {1}}}$ ${q_{1}}$ ${\ estilo de visualización \ alfa \ en \ mathbb {Z}}$ ${\ estilo de visualización {h} = {g} ^ {\ alfa {q_ {2}}}}$ ${C_{1}}={g}^{m_{1}}{h}^{r_{1}}\en \mathbb {G}$ ${C_{2}}={g}^{m_{2}}{h}^{r_{2}}\en \mathbb {G}$ ${m_{1}}\veces {m_{2}}{\bmod {n}}$ ${r}\en \mathbb {Z_{n}}$ ${C}={f}({C_{1}},{C_{2}}){h_{1}^{r}}\en \mathbb {G}_{1}$ ${C=f(C_{1},C_{2})h_{1}^{r}=f(g^{m_{1}}h^{r_{1}},g^{m_ {2}}h^{r_{2}})h_{1}^{r}=g^{m_{1}m_{2}}h^{m_{1}r_{2}+r_{2} m_{1}+\alpha q_{2}r_{1}r_{2}+r}=g_{1}^{m_{1}m_{2}}h_{1}^{\tilde {r}} }\en \mathbb {G} _{1}$ ${{\tilde {r}}=m_{1}r_{2}+r_{2}m_{1}+\alpha q_{2}r_{1}r_{2}+r}$ $\mathbb {Z_{n}}$

Por lo tanto, es un cifrado distribuido uniformemente , pero solo en el grupo , no en (por lo que solo se permite una multiplicación). [once] ${\ estilo de visualización {C}}$ ${m_{1}}\veces {m_{2}}{\bmod {n}}$ ${\ estilo de visualización \ mathbb {G} _ {1}}$ ${\ estilo de visualización \ mathbb {G}}$

Estabilidad del sistema

La estabilidad de este esquema se basa en el problema de Burnside : conociendo un elemento de un grupo de orden compuesto , es imposible determinar si pertenece a un subgrupo del orden . ${\ estilo de visualización {n} = {q}_{1}{q}_{2}}$ ${q_{1}}$

Sea , y sea una tupla creada por , donde . Considere el siguiente problema. Para un elemento dado , imprima " " si el orden es igual a , de lo contrario imprima " ". En otras palabras, sin conocer la factorización del grupo de orden , se necesita saber si un elemento está en un subgrupo del grupo . Este problema se llama problema de Burnside [7] . ${\displaystyle \tau \in \mathbb {Z} ^{+))$ $({q}_{1},{q}_{2},\mathbb {G} ,\mathbb {G}_{1},{f})$ $X$ ${\ estilo de visualización {n} = {q}_{1}{q}_{2}}$ ${\ estilo de visualización ({n}, \ mathbb {G}, \ mathbb {G} _ {1}, {f})}$ ${x}\en \mathbb {G}$ $una$ ${X}$ ${q_{1}}$ ${\ estilo de visualización 0}$ ${norte}$ ${X}$ ${\ estilo de visualización \ mathbb {G}}$

Está claro que si podemos tener en cuenta el orden de grupo en el criptosistema, entonces conocemos la clave privada y, como resultado, el sistema está roto. Además, si podemos calcular los logaritmos discretos en el grupo , entonces podemos calcular y . Así, las condiciones necesarias para la seguridad son: la complejidad de factorizar y la complejidad de calcular logaritmos discretos en . [catorce] ${norte}$ ${q_{1}}$ ${\ estilo de visualización \ mathbb {G}}$ ${q_{2}}$ ${q_{1}=n/q_{2}}$ ${norte}$ ${\ estilo de visualización \ mathbb {G}}$

Notas

↑ Pascal Paillier. Criptosistemas de clave pública basados en clases de residuosidad de grado compuesto // Avances en criptología - EUROCRYPT '99 / Jacques Stern. — Springer Berlín Heidelberg, 1999. — P. 223–238 . — ISBN 9783540489108 . -doi : 10.1007 / 3-540-48910-x_16 . Archivado desde el original el 26 de junio de 2019.
↑ Tatsuaki Okamoto, Shigenori Uchiyama. Un nuevo criptosistema de clave pública tan seguro como el factoraje // Avances en Criptología - EUROCRYPT'98 / Kaisa Nyberg. — Springer Berlín Heidelberg, 1998. — P. 308–318 . — ISBN 9783540697954 . -doi : 10.1007/ bfb0054135 . Archivado desde el original el 29 de agosto de 2018.
↑ Mihir Bellare, Juan A. Garay, Tal Rabin. Verificación rápida por lotes para exponenciación modular y firmas digitales // Avances en criptología - EUROCRYPT'98 / Kaisa Nyberg. — Springer Berlín Heidelberg, 1998. — P. 236–250 . — ISBN 9783540697954 . -doi : 10.1007/ bfb0054130 . Archivado desde el original el 7 de junio de 2018.
↑ 1 2 Dan Boneh, Matt Franklin. Cifrado basado en identidad del emparejamiento Weil // Avances en criptología - CRYPTO 2001 / Joe Kilian. — Springer Berlín Heidelberg, 2001. — P. 213–229 . — ISBN 9783540446477 . -doi : 10.1007 / 3-540-44647-8_13 . Archivado desde el original el 22 de febrero de 2020.
↑ Evaluación de fórmulas 2-DNF en textos cifrados . Consultado el 20 de febrero de 2021. Archivado desde el original el 8 de agosto de 2017. (indefinido)
↑ Computación segura II // Teoría de la criptografía: Segunda conferencia sobre teoría de la criptografía, TCC 2005, Cambridge, MA, EE. UU., 10 al 12 de febrero de 2005: actas . - Berlín: Springer, 2005. - P. 326. - 1 recurso en línea (xii, 619 páginas) p. - ISBN 9783540305767 , 3540305769, 3540245731, 9783540245735.
↑ 1 2 3 4 5 Takuho Mitsunaga, Yoshifumi Manabe, Tatsuaki Okamoto. Protocolos de subasta seguros y eficientes basados en el cifrado Boneh-Goh-Nissim . — 2010-11-22. - T. E96A . — S. 149–163 . -doi : 10.1007 / 978-3-642-16825-3_11 .
↑ ON Vasilenko. Sobre el cálculo de los emparejamientos de Weyl y Tate // Tr. por discr. Matem.. - M. : FIZMATLIT, 2007. - T. 10. - S. 18-46.
↑ Antoine Joux. Un protocolo de una ronda para Tripartite Diffie-Hellman . — 2006-12-30. - T. 17 . — S. 385–393 . -doi : 10.1007/ 10722028_23 .
↑ Víctor Miller. El emparejamiento de Weil y su cálculo eficiente // J. Cryptology. — 2004-09-01. - T. 17 . — S. 235–261 . -doi : 10.1007/ s00145-004-0315-8 .
↑ 1 2 3 4 Computación segura II // Teoría de la criptografía: Segunda conferencia sobre teoría de la criptografía, TCC 2005, Cambridge, MA, EE. UU., 10 al 12 de febrero de 2005: actas . - Berlín: Springer, 2005. - P. 329. - 1 recurso en línea (xii, 619 páginas) p. - ISBN 9783540305767 , 3540305769, 3540245731, 9783540245735.
↑ Yi, Xun (profesor universitario), . Cifrado homomórfico y aplicaciones . — Cham. — 1 recurso en línea (xii, 126 páginas) p. - ISBN 978-3-319-12229-8 , 3-319-12229-0.
↑ Teoría de la criptografía: Segunda Conferencia de Teoría de la Criptografía, TCC 2005, Cambridge, MA, EE. UU., 10 al 12 de febrero de 2005: actas . - Berlín: Springer, 2005. - P. 332. - 1 recurso en línea (xii, 619 páginas) p. - ISBN 9783540305767 , 3540305769, 3540245731, 9783540245735.
↑ EUROCRYPT 2010 (2010: Riveria, Francia). Avances en criptología--EUROCRYPT 2010: 29° Congreso Internacional Anual sobre Teoría y Aplicaciones de Técnicas Criptográficas, Riviera Francesa, 30 de mayo al 3 de junio de 2010: actas . - Springer, 2010. - ISBN 9783642131905 , 3642131905.

Literatura

S. M. Vladimirov, E. M. Gabidulin, A. I. Kolybelnikov, A. S. Kshevetsky. Métodos criptográficos de protección de la información. - 2ª ed. - MIPT, 2016. - S. 225-257. — 266 págs. - ISBN 978-5-7417-0615-2 .

Enlaces

SI Adian. El problema de Burnside y preguntas relacionadas // Uspekhi Mat. - 2010. - Septiembre ( vol. 65 , número 5 ).

Criptosistemas de clave pública

Algoritmos

Factorización de números enteros	criptosistema Benalo Bluma - Goldwasser Cayley sobrecargo Damgorda - Eureka GMR Goldwasser-Micali Nakasha - popa paga Rabín RSA Okamoto-Uchiyama Schmidt-Samoa
logaritmo discreto	BLS Cramer - Shoup Protocolo de Diffie-Hellman DSA ECDH Curva25519 X448 ECDSA EdDSA Ed25519 Ed448 ECMQV Intercambio de claves cifradas Esquema de ElGamal esquema de firma MQV esquema de Schnorr HABLA PVP STS
Criptografía en celosías	NTRUEncriptar NTRUSign Intercambio de claves basado en el aprendizaje con errores Entrenamiento basado en firmas con errores en el ring FELICIDAD Nueva Esperanza
Otro	AE CEILIDH EPOC Ecuaciones de campo ocultas IES la firma de lamport McEliece Criptosistema de mochila Merkle-Hellman Criptosistema de mochila Naccache-Stern Protocolo de tres pasos XTR

Teoría

Logaritmo discreto en una curva elíptica
Criptografía elíptica
Criptografía basada en hash
Criptografía no conmutativa
problema RSA
Función unidireccional con entrada secreta

Estándares

CRYPTREC
IEEE P1363
NESSIE
Paquete B de la NSA
Criptografía post cuántica

Temas

Firma electronica
OAEP
Huella dactilar
PKI
red de confianza
Tamaño de clave
Criptografía basada en identidad
Criptografía poscuántica
Tarjeta OpenPGP