En criptografía , un acumulador es una función hash de membresía unidireccional . Permite a los usuarios certificar que los candidatos potenciales son miembros de un conjunto determinado 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
Hay varias definiciones formales que se han propuesto en la literatura. Esta sección los enumera por proponente, en un orden cronológico aproximado. [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]
- Para todos , uno puede calcular a tiempo . (Aquí el símbolo "poli" se refiere a un polinomio no especificado, pero fijo).
- Ningún algoritmo probabilístico de tiempo polinomial lo hará, para lo suficientemente grande, mapear las entradas , encuentra un valor tal que con una probabilidad más que insignificante.
- Para todos , uno tiene . (Una función que satisface esta propiedad se llama cuasi-conmutativa ).
(Con las dos primeras propiedades, se recupera la definición normal de una función hash criptográfica).
A partir de tal función, se define el "hash acumulado" de un conjunto wrt un valor ser - estar . (Esto no depende del orden de los elementos porquees cuasi conmutativo.) [1] [2]
Barić y Pfitzmann (1997)
La funcionalidad básica de una función hash cuasi conmutativa no es inmediata a partir de la definición. Para solucionar este problema, 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]
- Gen: un algoritmo probabilístico que toma dos parámetros (el parámetro de seguridad y el número de valores que se pueden acumular de forma segura, respectivamente), y devuelve una clave adecuada .
- Eval: un algoritmo probabilístico que toma una clave y conjunto de acumulación , dónde y devolviendo un valor acumulado e información auxiliar . Insistimos en que Eval debe ser determinista para.
- Ingenio: 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, que Wit devuelve un testigo, y que Wit, de lo contrario, regresa .
- 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 , dónde se generaron a partir de ejecutar Eval en algunos , y donde fue elegido arbitrariamente y Fue elegido de correr Gen, que Ver siempre devuelve Sí.
Es relativamente fácil ver que se puede definir un esquema de acumulador a partir de cualquier función hash cuasi conmutativa, utilizando la técnica que se muestra arriba. [2]
Camenisch y Lysyanskaya (2002)
Se observa que, para muchas aplicaciones, el conjunto de valores acumulados cambiará muchas veces. Ingenuamente, uno podría rehacer completamente el cálculo del acumulador cada vez; sin embargo, esto puede resultar ineficaz, 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]
- Agregue: un algoritmo (posiblemente probabilístico) que toma una clave , un valor acumulado , y otro valor para acumular y devuelve un nuevo valor acumulado e información auxiliar . Insistimos en que si fue generado acumulando algunos conjuntos , luego debe ser como si se generara acumulando el conjunto .
- Del: un algoritmo (posiblemente probabilístico) que toma una clave , un valor acumulado , y otro valor para acumular y devuelve un nuevo valor acumulado e información auxiliar . Insistimos en que si fue generado acumulando algunos conjuntos , luego debe ser como si se generara acumulando el conjunto .
- 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 testigo de ser miembro de , y es un valor acumulado para , y se generó ejecutando Aux o Del, luego será testigo de ser miembro del nuevo grupo.
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 de
Un ejemplo es la multiplicación sobre números primos grandes . Este es un acumulador criptográfico, ya que se necesita un tiempo superpolinomial para factorizar un número compuesto (al menos de acuerdo con la conjetura), pero solo se necesita una pequeña cantidad de tiempo (polinomio en tamaño) para dividir un número primo en un entero para verificar si es uno de los factores y / o factorizarlo. Los nuevos miembros se pueden sumar o restar 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 trivialmente calculando su MCD, incluso sin un 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 aumenta 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 elegirser un entero rígido (es decir, el producto de dos números primos seguros ). [1] Barić y Pfitzmann propusieron una variante donde estaba restringido a ser primo y como máximo (esta constante está muy cerca de , pero no filtra información sobre la factorización prima de ). [2] [3]
David Naccache observó en 1993 que es cuasi conmutativo para todas las constantes , generalizando el acumulador criptográfico anterior inspirado en RSA. 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]
En 1996, Nyberg construyó un acumulador que es probadamente seguro desde el punto de vista teórico de la información en el modelo de oráculo aleatorio . Elegir un límite superior para la cantidad de elementos que se pueden acumular de forma segura y el parámetro de seguridad, define la constante ser un múltiplo entero de (para que uno pueda escribir ) y deja ser una función hash criptográficamente segura . Elige una clave como un azar -bit cadena de bits. Luego, para acumular usando el esquema de Nyberg, use la función hash cuasi-conmutativa, dónde es el bit a bit y la operación y es la función que interpreta su entrada como una secuencia de -bit cadenas de bits de longitud , reemplaza cada cadena de bits completamente cero con un solo 0 y todas las demás cadenas de bits con un 1, y genera el resultado. [2] [5]
Aplicaciones
Haber y Stornetta demostraron en 1990 que los acumuladores se pueden usar para sellar documentos a través del encadenamiento criptográfico. (Este concepto anticipa la noción moderna de una 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 se pueden utilizar para que un gran grupo de personas pueda reconocerse entre sí en un momento posterior (lo que Fazio y Nicolosi denominan una situación de "depósito de identidad"). Cada persona selecciona un que representa 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 el secretoy acumulador público; simultáneamente, cada miembro del grupo mantiene tanto su valor de identidady el hash acumulado de todas las identidades del grupo excepto la del miembro . (Si el gran grupo de personas no confían entre sí, o si el acumulador tiene una trampilla criptográfica como en el caso del acumulador inspirado en RSA, entonces pueden calcular los valores hash acumulados mediante un cálculo seguro de varias partes ). de hecho, el miembro perteneció al grupo más tarde, presentan su identidad y hash personal acumulado (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, es además fácil agregar o quitar miembros posteriormente. [2] [4]
Los acumuladores criptográficos también se pueden utilizar para construir otras estructuras de datos criptográficamente seguras :
- Barić y Pfitzmann muestran que se pueden construir firmas de parada de falla con solo un espacio constante explotando la propiedad de compresión. [2] [3]
- Goodrich y col. construyó un diccionario autenticado dinámico, eficiente y ajeno al tamaño (que permite a los directorios que no son de confianza dar respuestas criptográficamente verificables a las consultas de membresía). [2] [8]
- Papamanthou y col. construyó una tabla hash criptográficamente segura , cuya funcionalidad se puede autenticar cuando se almacena de forma remota. [9]
El concepto ha recibido un interés renovado debido al complemento de Zerocoin para bitcoin , que emplea acumuladores criptográficos para eliminar el enlace rastreable en la cadena de bloques de bitcoin, lo que haría que las transacciones fueran anónimas y más privadas. [10] [11] [12] Más concretamente, para acuñar (crear) una Zerocoin, se 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 tenga el formato correcto ); para gastar (reclamar) una Zerocoin, uno publica el número de serie de Zerocoin junto con una prueba no interactiva de conocimiento cero 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 como 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 sucedido por el protocolo Zerocash y actualmente se está desarrollando en Zcash , una moneda digital [ palabras de comadreja ] en toda regla . [13] [14]
Ver también
- Criptografía
- Prueba de conocimiento cero
Referencias
- ^ a b c d e f g h Benaloh, Josh; de Mare, Michael (1994). "Acumuladores unidireccionales: una alternativa descentralizada a las firmas digitales" (PDF) . Avances en Criptología - EUROCRYPT '93 . LCNS. 765 : 274-285. doi : 10.1007 / 3-540-48285-7_24 . ISBN 978-3-540-57600-6. Consultado el 3 de mayo de 2021 .
- ^ a b c d e f g h i j k l m n o 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 .
- ^ a b c Barić, Niko; Pfitzmann, Birgit (1997). Fumy, Walter (ed.). "Acumuladores sin colisiones y esquemas de firmas de parada de emergencia sin árboles" . Avances en Criptología - EUROCRYPT '97 . Apuntes de conferencias en informática. Berlín, Heidelberg: Springer. 1233 : 480–494. doi : 10.1007 / 3-540-69053-0_33 . ISBN 978-3-540-69053-5.
- ^ a b Camenisch, Jan; Lysyanskaya, Anna (2002). Yung, Moti (ed.). "Acumuladores dinámicos y aplicación a la revocación eficiente de credenciales anónimas" . Avances en criptología - CRYPTO 2002 . Apuntes de conferencias en informática. Berlín, Heidelberg: Springer. 2442 : 61–76. doi : 10.1007 / 3-540-45708-9_5 . ISBN 978-3-540-45708-4.
- ^ Nyberg, Kaisa (1996). Gollmann, Dieter (ed.). "Hash acumulado rápido" . Cifrado de software rápido . Apuntes de conferencias en informática. Berlín, Heidelberg: Springer. 1039 : 83–87. doi : 10.1007 / 3-540-60865-6_45 . ISBN 978-3-540-49652-6.
- ^ Haber, Stuart; Stornetta, W. Scott (1991). Menezes, Alfred J .; Vanstone, Scott A. (eds.). "Cómo sellar la fecha y hora de un documento digital" . Avances en Criptología-CRYPTO '90 . Apuntes de conferencias en informática. Berlín, Heidelberg: Springer. 537 : 437–455. doi : 10.1007 / 3-540-38424-3_32 . ISBN 978-3-540-38424-3.
- ^ Benaloh, J .; de Mare, M. (agosto de 1991). "Sellado de tiempo de emisión eficiente" . Departamento de Matemáticas e Informática de la Universidad de Clarkson . TR 91-1. CiteSeerX 10.1.1.38.9199 - a través de Citeseer.
- ^ Goodrich, Michael T .; Tamassia, Roberto; Hasić, Jasminka (11 de noviembre de 2001). "Un acumulador criptográfico dinámico y distribuido eficiente" (PDF) . Conferencia Internacional sobre Seguridad de la Información . ISC 2002: 372–388. Archivado desde el original el 13 de marzo de 2003.
- ^ Papamanthou, Charalampos; Tamassia, Roberto; Triandopoulos, Nikos (18 de agosto de 2009). "Acumuladores criptográficos para tablas hash autenticadas" . Archivo ePrint de criptología . CiteSeerX 10.1.1.214.7737 . Consultado el 3 de mayo de 2021 .
- ^ a b Ian, Miers; Garman, Christina; Green, Matthew; Rubin, Aviel D. (2013). "Zerocoin: E-Cash distribuido anónimo de Bitcoin" (PDF) . Simposio de IEEE sobre seguridad y privacidad de 2013: 397–411. doi : 10.1109 / SP.2013.34 . ISBN 978-0-7695-4977-4. S2CID 9194314 . Consultado el 3 de mayo de 2021 .
- ^ a b Green, Matthew (11 de abril de 2013). "Zerocoin: hacer Bitcoin anónimo" . Algunas reflexiones sobre la ingeniería criptográfica . Archivado desde el original el 21 de mayo de 2014 . Consultado el 3 de mayo de 2021 .
- ^ Zerocoin: E-Cash distribuido anónimo de Bitcoin Archivado el 8 de febrero de 2014 en Wayback Machine
- ^ "Proyecto Zerocoin" . zerocoin.org . Consultado el 4 de mayo de 2021 .
- ^ "Moneda digital que protege la privacidad | Zcash" . Zcash . Consultado el 4 de mayo de 2021 .