Acumulador (criptografía)

En criptografía , un acumulador es una función hash de pertenencia unidireccional . Permite a los usuarios certificar que los candidatos potenciales son miembros de un determinado conjunto sin revelar los miembros individuales del conjunto. Este concepto fue introducido formalmente por Josh Benaloh y Michael de Mare en 1993. ^{[1] [2]}

Definiciones formales

Existen varias definiciones formales propuestas en la literatura. En esta sección se enumeran por proponente, en orden aproximadamente cronológico. ^[2]

Benaloh y de Mare (1993)

Benaloh y de Mare definen una función hash unidireccional como una familia de funciones que satisfacen las siguientes tres propiedades: ^{[1] [2]} ${\displaystyle h_{\ell }:X_{\ell }\times Y_{\ell }\to Z_{\ell }}$

1. Para todo , se puede calcular en el tiempo . (Aquí el símbolo "poli" se refiere a un polinomio no especificado, pero fijo). ${\displaystyle \ell \in \mathbb {Z} ,x\in X_{\ell },y\in Y_{\ell }}$ ${\displaystyle h_{\ell }(x,y)}$ ${\displaystyle {\text{poly}}(\ell ,|x|,|y|)}$
2. Ningún algoritmo de tiempo polinomial probabilístico , para valores suficientemente grandes , mapeará las entradas y encontrará un valor tal que con una probabilidad más que insignificante. ${\displaystyle \ell }$ ${\displaystyle \ell \in \mathbb {Z} ,(x,y)\in X_{\ell }\times Y_{\ell },y'\in Y_{\ell }}$ ${\displaystyle x'\in X_{\ell }}$ ${\displaystyle h_{\ell }(x,y)=h_{\ell }(x',y')}$
3. Para todo , se tiene . (Una función que satisface esta propiedad se llama cuasi-conmutativa ). ${\displaystyle \ell \in \mathbb {Z} ,x\in X_{\ell },y_{1},y_{2}\in Y_{\ell }}$ ${\displaystyle h(h(x,y_{1}),y_{2})=h(h(x,y_{2}),y_{1})}$

(Con las dos primeras propiedades se recupera la definición normal de una función hash criptográfica).

A partir de una función de este tipo, se define el "hash acumulado" de un conjunto y el valor inicial es . El resultado no depende del orden de los elementos porque es cuasi conmutativo. ^{[1] [2]} ${\displaystyle \{y_{1},\dots ,y_{m}\}}$ ${\displaystyle x}$ ${\displaystyle z}$ ${\displaystyle h(h(\cdots h(h(x,y_{1}),y_{2}),\dots ,y_{m-1}),y_{m})}$ ${\displaystyle y_{1},y_{2},...,y_{n}}$ ${\displaystyle h}$

Si pertenece a algunos usuarios de un criptosistema, entonces todos pueden calcular el valor acumulado . Además, el usuario de puede calcular el valor acumulado parcial de . Entonces, el usuario puede proporcionar el par a cualquier otra parte, para autenticar . ${\displaystyle y_{1},y_{2},...,y_{n}}$ ${\displaystyle z.}$ ${\displaystyle y_{i}}$ ${\displaystyle z_{i}}$ ${\displaystyle (y_{1},...,y_{i-1},y_{i+1},...,y_{n})}$ ${\displaystyle h(z_{i},y_{i})=z.}$ ${\displaystyle i-}$ ${\displaystyle (z_{i},y_{i})}$ ${\displaystyle y_{i}}$

Barić y Pfitzmann (1997)

La funcionalidad básica de una función hash cuasi conmutativa no se desprende de la definición. Para solucionarlo, Barić y Pfitzmann definieron una definición un poco más general, que es la noción de un esquema acumulador que consta de los siguientes componentes: ^{[2] [3]}

1. Gen: un algoritmo probabilístico que toma dos parámetros (el parámetro de seguridad y la cantidad de valores que se pueden acumular de forma segura, respectivamente) y devuelve una clave apropiada . ${\displaystyle \lambda ,N}$ ${\displaystyle k}$
2. Eval: un algoritmo probabilístico que toma una clave y un conjunto de acumulación , donde , y devuelve un valor acumulado e información auxiliar . Insistimos en que Eval debe ser determinista para . ${\displaystyle k}$ ${\displaystyle Y:=\{y_{1},\dots ,y_{N'}\}}$ ${\displaystyle N'\leq N}$ ${\displaystyle z}$ ${\displaystyle aux}$ ${\displaystyle z}$
3. Wit: un algoritmo probabilístico que toma una clave , un valor , un valor acumulado de algún conjunto y alguna información auxiliar , y devuelve un testigo o el símbolo especial . Insistimos en que, si , Wit devuelve un testigo y, en caso contrario, devuelve . ${\displaystyle k}$ ${\displaystyle y}$ ${\displaystyle z}$ ${\displaystyle Y}$ ${\displaystyle aux}$ ${\displaystyle w}$ ${\displaystyle \bot }$ ${\displaystyle y\in L}$ ${\displaystyle \bot }$
4. Ver: un algoritmo determinista que toma una clave , un valor , un testigo y un valor acumulado , y devuelve un valor Sí/No. Insistimos en que si se generó al ejecutar Wit en una tupla , donde se generó al ejecutar Eval en algún , y donde se eligió arbitrariamente y se eligió al ejecutar Gen, Ver siempre devuelve Sí. ${\displaystyle k}$ ${\displaystyle y}$ ${\displaystyle w}$ ${\displaystyle z}$ ${\displaystyle w}$ ${\displaystyle (k,y,z,aux)}$ ${\displaystyle z,aux}$ ${\displaystyle k,L}$ ${\displaystyle L}$ ${\displaystyle k}$

Es relativamente fácil ver que se puede definir un esquema acumulador a partir de cualquier función hash cuasi-conmutativa, utilizando la técnica mostrada arriba. ^[2]

Camenisch y Lysyanskaya (2002)

Se observa que, para muchas aplicaciones, el conjunto de valores acumulados cambiará muchas veces. Ingenuamente, se podría rehacer por completo el cálculo del acumulador cada vez; sin embargo, esto puede ser ineficiente, especialmente si nuestro conjunto es muy grande y el cambio es muy pequeño. Para formalizar esta intuición, Camenish y Lysyanskaya definieron un esquema de acumulador dinámico que consta de los 4 componentes de un esquema de acumulador ordinario, más tres más: ^{[2] [4]}

1. Añadir: un algoritmo (posiblemente probabilístico) que toma una clave , un valor acumulado y otro valor a acumular , y devuelve un nuevo valor acumulado e información auxiliar . Insistimos en que si se generó acumulando algún conjunto , entonces debe ser como si se hubiera generado acumulando el conjunto . ${\displaystyle k}$ ${\displaystyle z}$ ${\displaystyle y}$ ${\displaystyle z'}$ ${\displaystyle aux}$ ${\displaystyle z}$ ${\displaystyle L}$ ${\displaystyle z'}$ ${\displaystyle L\cup \{y\}}$
2. Del: un algoritmo (posiblemente probabilístico) que toma una clave , un valor acumulado y otro valor a acumular , y devuelve un nuevo valor acumulado e información auxiliar . Insistimos en que si se generó acumulando algún conjunto , entonces debe ser como si se hubiera generado acumulando el conjunto . ${\displaystyle k}$ ${\displaystyle z}$ ${\displaystyle y}$ ${\displaystyle z'}$ ${\displaystyle aux}$ ${\displaystyle z}$ ${\displaystyle L}$ ${\displaystyle z'}$ ${\displaystyle L\backslash \{y\}}$
3. Upd: un algoritmo determinista que toma la clave , un valor , un testigo , el valor acumulado e información auxiliar , y devuelve un nuevo testigo . Insistimos en que si fue generado por Gen, es parte de un conjunto , es un testigo por ser miembro de , y es un valor acumulado para , y fue generado al ejecutar Add o Del, entonces será un testigo por ser miembro del nuevo conjunto. ${\displaystyle k}$ ${\displaystyle y}$ ${\displaystyle w}$ ${\displaystyle z}$ ${\displaystyle aux}$ ${\displaystyle w'}$ ${\displaystyle k}$ ${\displaystyle y}$ ${\displaystyle L}$ ${\displaystyle w}$ ${\displaystyle y}$ ${\displaystyle L}$ ${\displaystyle z}$ ${\displaystyle L}$ ${\displaystyle aux}$ ${\displaystyle w'}$ ${\displaystyle y}$

Fazio y Nicolosi señalan que, dado que Add, Del y Upd se pueden simular volviendo a ejecutar Eval y Wit, esta definición no agrega ninguna funcionalidad fundamentalmente nueva. ^[2]

Ejemplos

Un ejemplo es la multiplicación de números primos grandes . Se trata de un acumulador criptográfico, ya que se necesita un tiempo superpolinomial para factorizar un número compuesto (al menos según la conjetura), pero se necesita sólo una pequeña cantidad de tiempo (de tamaño polinomial) para dividir un primo en un entero para comprobar si es uno de los factores y/o factorizarlo. Se pueden añadir o restar nuevos miembros al conjunto de factores multiplicando o factorizando el número respectivamente. En este sistema, dos acumuladores que han acumulado un único primo compartido pueden descubrirlo de forma trivial calculando su MCD, incluso sin conocimiento previo del primo (que de otro modo requeriría la factorización prima del acumulador para descubrirlo). ^{[ cita requerida ]}

Los acumuladores más prácticos utilizan una función hash cuasi-conmutativa , de modo que el tamaño del acumulador no crece con el número de miembros. Por ejemplo, Benaloh y de Mare proponen un acumulador criptográfico inspirado en RSA : la función cuasi-conmutativa para algún número compuesto . Recomiendan elegir que sea un entero rígido (es decir, el producto de dos primos seguros ). ^[1] Barić y Pfitzmann propusieron una variante donde se restringió a ser primo y como máximo (esta constante es muy cercana a , pero no filtra información sobre la factorización prima de ). ^{[2] [3]} ${\displaystyle h(x,y):=x^{y}{\pmod {n}}}$ ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle y}$ ${\displaystyle n/4}$ ${\displaystyle \phi (n)}$ ${\displaystyle n}$

David Naccache observó en 1993 que es cuasi conmutativo para todas las constantes , generalizando el acumulador criptográfico inspirado en RSA anterior. Naccache también señaló que los polinomios de Dickson son cuasi conmutativos en el grado, pero se desconoce si esta familia de funciones es unidireccional. ^[1] ${\displaystyle e_{n,c}(x,y):=x^{y}c^{y-1}{\pmod {n}}}$ ${\displaystyle c,n}$

En 1996, Nyberg construyó un acumulador que es demostrablemente seguro en teoría de la información en el modelo de oráculo aleatorio . Eligiendo un límite superior para la cantidad de elementos que se pueden acumular de forma segura y el parámetro de seguridad, defina la constante como un múltiplo entero de (de modo que se pueda escribir ) y sea una función hash criptográficamente segura . Elija una clave como una cadena de bits aleatoria de -bit. Luego, para acumular utilizando el esquema de Nyberg, use la función hash cuasi-conmutativa , donde es la operación y bit a bit y es la función que interpreta su entrada como una secuencia de cadenas de bits de -bit de longitud , reemplaza cada cadena de bits de todos ceros con un solo 0 y cada otra cadena de bits con un 1, y genera el resultado. ^{[2] [5]} ${\displaystyle N=2^{d}}$ ${\displaystyle \lambda }$ ${\displaystyle \ell :\approx {\frac {e}{\log _{2}(e)}}\lambda N\log _{2}(N)}$ ${\displaystyle d}$ ${\displaystyle \ell =rd}$ ${\displaystyle H:\{0,1\}^{*}\to \{0,1\}^{\ell }}$ ${\displaystyle k}$ ${\displaystyle r}$ ${\displaystyle h(x,y):=x\odot \alpha _{r}(H(y))}$ ${\displaystyle \odot }$ ${\displaystyle \alpha _{r}:\{0,1\}^{\ell }\to \{0,1\}^{r}}$ ${\displaystyle d}$ ${\displaystyle r}$

Aplicaciones

Haber y Stornetta demostraron en 1990 que los acumuladores pueden utilizarse para marcar con fecha y hora documentos mediante encadenamiento criptográfico (este concepto anticipa la noción moderna de cadena de bloques criptográfica ). ^{[1] [2] [6]} Benaloh y de Mare propusieron un esquema alternativo en 1991 basado en la discretización del tiempo en rondas. ^{[1] [7]}

Benaloh y de Mare demostraron que los acumuladores pueden utilizarse para que un grupo grande de personas puedan reconocerse entre sí en un momento posterior (lo que Fazio y Nicolosi llaman una situación de "depósito de identidad"). Cada persona selecciona un que represente su identidad, y el grupo selecciona colectivamente un acumulador público y un secreto . Luego, el grupo publica o guarda la función hash y el hash acumulado de todas las identidades del grupo con respecto al secreto y al acumulador público; simultáneamente, cada miembro del grupo mantiene tanto su valor de identidad como el hash acumulado de todas las identidades del grupo excepto la del miembro . (Si el grupo grande de personas no confía entre sí, o si el acumulador tiene una trampilla criptográfica como en el caso del acumulador inspirado en RSA, entonces pueden calcular los hashes acumulados mediante un cálculo multipartito seguro ). Para verificar que un miembro declarado pertenecía efectivamente al grupo más tarde, presenta su identidad y su hash acumulado personal (o una prueba de conocimiento cero de los mismos); Al acumular la identidad del miembro reclamado y compararla con el hash acumulado de todo el grupo, cualquiera puede verificar a un miembro del grupo. ^{[1] [2]} Con un esquema de acumulador dinámico, también es fácil agregar o eliminar miembros posteriormente. ^{[2] [4]} ${\displaystyle y}$ ${\displaystyle h}$ ${\displaystyle x}$ ${\displaystyle x}$ ${\displaystyle y}$

Los acumuladores criptográficos también se pueden utilizar para construir otras estructuras de datos criptográficamente seguras :

• Barić y Pfitzmann demuestran que es posible construir firmas de detención de fallas con solo espacio constante explotando la propiedad de compresión. ^{[2] [3]}
• Goodrich et al. construyeron un diccionario autenticado, dinámico, eficiente y que no tiene en cuenta el tamaño (que permite que los directorios no confiables brinden respuestas criptográficamente verificables a las consultas de membresía). ^{[2] [8]}
• Papamanthou et al. construyeron una tabla hash criptográficamente segura , cuya funcionalidad puede ser autenticada cuando se almacena de forma remota. ^[9]

El concepto ha recibido un renovado interés debido al complemento Zerocoin para Bitcoin , que emplea acumuladores criptográficos para eliminar los enlaces rastreables en la cadena de bloques de Bitcoin, lo que haría que las transacciones sean anónimas y más privadas. ^{[10] [11] [12]} Más concretamente, para acuñar (crear) un Zerocoin, uno publica una moneda y un compromiso criptográfico con un número de serie con un valor aleatorio secreto (que todos los usuarios aceptarán siempre que esté correctamente formateado); para gastar (reclamar) un Zerocoin, uno publica el número de serie de Zerocoin junto con una prueba de conocimiento cero no interactiva de que conocen algún compromiso publicado que se relaciona con el número de serie reclamado, luego reclama la moneda (que todos los usuarios aceptarán siempre que el NIZKP sea válido y el número de serie no haya aparecido antes). ^{[10] [11]} Desde la propuesta inicial de Zerocoin, ha sido reemplazado por el protocolo Zerocash y actualmente se está desarrollando en Zcash , una moneda digital basada en el código base de Bitcoin. ^{[13] [14]}

Véase también

• Criptografía
• Prueba de conocimiento cero

Referencias

1. Benaloh, Josh; de Mare, Michael (1994). "Acumuladores unidireccionales: una alternativa descentralizada a las firmas digitales" (PDF) . Avances en criptología — EUROCRYPT '93 . Apuntes de clase en informática. Vol. 765. págs. 274–285. doi : 10.1007/3-540-48285-7_24 . ISBN . 978-3-540-57600-6. Recuperado el 3 de mayo de 2021 .
2. Fazio, Nelly; Nicolosi, Antonio (2002). «Acumuladores criptográficos: definiciones, construcciones y aplicaciones» (PDF) . Archivado (PDF) desde el original el 3 de junio de 2006. Consultado el 30 de enero de 2021 .
3. Barić, Niko; Pfitzmann, Birgit (1997). "Acumuladores sin colisiones y esquemas de firma de detención de fallos sin árboles". En Fumy, Walter (ed.). Avances en criptología — EUROCRYPT '97 . Apuntes de clase en informática. Vol. 1233. Berlín, Heidelberg: Springer. págs. 480–494. doi : 10.1007/3-540-69053-0_33 . ISBN 978-3-540-69053-5.
4. Camenisch, Jan; Lysyanskaya, Anna (2002). "Acumuladores dinámicos y aplicación a la revocación eficiente de credenciales anónimas". En Yung, Moti (ed.). Avances en criptología — CRYPTO 2002. Apuntes de clase en informática. Vol. 2442. Berlín, Heidelberg: Springer. págs. 61–76. doi : 10.1007/3-540-45708-9_5 . ISBN. 978-3-540-45708-4.
5. Nyberg, Kaisa (1996). "Hashing acumulado rápido". En Gollmann, Dieter (ed.). Fast Software Encryption . Notas de clase en informática. Vol. 1039. Berlín, Heidelberg: Springer. págs. 83–87. doi : 10.1007/3-540-60865-6_45 . ISBN. 978-3-540-49652-6.
6. Haber, Stuart; Stornetta, W. Scott (1991). "Cómo sellar con fecha y hora un documento digital". En Menezes, Alfred J.; Vanstone, Scott A. (eds.). Avances en criptología — CRYPT0' 90. Apuntes de clase en informática. Vol. 537. Berlín, Heidelberg: Springer. págs. 437–455. doi : 10.1007/3-540-38424-3_32 . ISBN . 978-3-540-38424-3.
7. Benaloh, J.; de Mare, M. (agosto de 1991). "Sellado de tiempo de transmisión eficiente". Microsoft . CiteSeerX 10.1.1.38.9199 . MSR-TR 91-1. 
8. Goodrich, Michael T.; Tamassia, Roberto; Hasić, Jasminka (11 de noviembre de 2001). "Un acumulador criptográfico distribuido y dinámico eficiente" (PDF) . Seguridad de la información . Apuntes de clase en informática. Vol. 2433. págs. 372–388. doi :10.1007/3-540-45811-5_29. ISBN 978-3-540-44270-7. Archivado desde el original el 13 de marzo de 2003.
9. Papamanthou, Charalampos; Tamassia, Roberto; Triandopoulos, Nikos (18 de agosto de 2009). "Acumuladores criptográficos para tablas hash autenticadas". Archivo de publicaciones electrónicas de criptología . CiteSeerX 10.1.1.214.7737 . 
10. Ian, Miers; Garman, Christina; Green, Matthew; Rubin, Aviel D. (2013). "Zerocoin: dinero electrónico distribuido anónimo a partir de Bitcoin" (PDF) . Simposio IEEE sobre seguridad y privacidad de 2013. págs. 397–411. doi :10.1109/SP.2013.34. ISBN 978-0-7695-4977-4. S2CID  9194314 . Consultado el 3 de mayo de 2021 .
11. Green, Matthew (11 de abril de 2013). «Zerocoin: haciendo que Bitcoin sea anónimo». Algunas reflexiones sobre ingeniería criptográfica . Archivado desde el original el 21 de mayo de 2014. Consultado el 3 de mayo de 2021 .
12. Zerocoin: Dinero electrónico distribuido de forma anónima a partir de Bitcoin Archivado el 8 de febrero de 2014 en Wayback Machine
13. "Proyecto Zerocoin". zerocoin.org . Consultado el 4 de mayo de 2021 .
14. "Moneda digital que protege la privacidad | Zcash". Zcash . Consultado el 4 de mayo de 2021 .