Esquema de compromiso

Esquema criptográfico que permite comprometerse con un valor elegido

Este artículo necesita citas adicionales para su verificación . Por favor, ayuda a mejorar este artículo mediante la adición de citas de fuentes confiables . El material no obtenido puede ser cuestionado y eliminado. Buscar fuentes:  "Esquema de compromiso"  -  noticias  · periódicos  · libros  · académico  · JSTOR ( octubre de 2014 ) ( Aprenda cómo y cuándo eliminar este mensaje de plantilla )

Un esquema de compromiso es una primitiva criptográfica que le permite a uno comprometerse con un valor elegido (o declaración elegida) mientras lo mantiene oculto para otros, con la capacidad de revelar el valor comprometido más tarde. ^{[1] Los} esquemas de compromiso están diseñados para que una parte no pueda cambiar el valor o la declaración después de haberse comprometido con él: es decir, los esquemas de compromiso son vinculantes . Los esquemas de compromiso tienen aplicaciones importantes en varios protocolos criptográficos, incluido el lanzamiento seguro de monedas, las pruebas de conocimiento cero y la computación segura .

Una forma de visualizar un esquema de compromiso es pensar en un remitente como si estuviera poniendo un mensaje en una caja cerrada y entregándola a un receptor. El mensaje en el cuadro está oculto para el receptor, que no puede abrir la cerradura por sí mismo. Dado que el receptor tiene la caja, el mensaje que se encuentra dentro no se puede cambiar, simplemente se revela si el remitente elige darles la clave en algún momento posterior.

Las interacciones en un esquema de compromiso tienen lugar en dos fases:

1. la fase de compromiso durante la cual se elige un valor y se compromete a
2. la fase de revelación durante la cual el remitente revela el valor, luego el receptor verifica su autenticidad

En la metáfora anterior, la fase de confirmación es que el remitente coloca el mensaje en el cuadro y lo bloquea. La fase de revelación es el remitente que entrega la clave al receptor, quien la usa para abrir la caja y verificar su contenido. La caja cerrada es el compromiso y la llave es la prueba.

En protocolos simples, la fase de confirmación consiste en un solo mensaje del remitente al receptor. Este mensaje se llama compromiso . Es esencial que el receptor no pueda conocer el valor específico elegido en ese momento (esto se denomina propiedad de ocultación ). Una fase de revelación simple consistiría en un solo mensaje, la apertura , del remitente al receptor, seguida de una verificación realizada por el receptor. El valor elegido durante la fase de confirmación debe ser el único que el remitente pueda calcular y que se valide durante la fase de revelación (esto se denomina propiedad de vinculación ).

El concepto de esquemas de compromiso fue quizás formalizado por primera vez por Gilles Brassard , David Chaum y Claude Crepeau en 1988, ^[2] como parte de varios protocolos de conocimiento cero para NP , basados ​​en varios tipos de esquemas de compromiso (ver también: ^{[3] [4]} ). Pero el concepto se utilizó antes de eso sin ser tratado formalmente. ^{[5] [6]} La noción de compromisos apareció más temprano en los trabajos de Manuel Blum , ^[7] Shimon Even , ^[8] y Shamir et al. ^[9] La terminología parece haber sido originada por Blum,^[6] aunque los esquemas de compromiso pueden denominarse indistintamente esquemas de compromiso de bits, a veces reservados para el caso especial en el que el valor comprometido es un bit . Anteriormente, se consideró el compromiso a través de funciones hash unidireccionales, por ejemplo, como parte de, digamos, la firma de Lamport , el esquema original de firma de un solo bit de una sola vez.

Aplicaciones

Lanzamiento de monedas

Suponga que Alice y Bob quieren resolver alguna disputa lanzando una moneda al aire . Si están físicamente en el mismo lugar, un procedimiento típico podría ser:

1. Alice "llama" al lanzamiento de la moneda
2. Bob lanza la moneda
3. Si la llamada de Alice es correcta, ella gana; de lo contrario, Bob gana.

Si Alice y Bob no están en el mismo lugar, surge un problema. Una vez que Alice ha "llamado" el lanzamiento de la moneda, Bob puede estipular que los "resultados" del lanzamiento sean lo que sea más deseable para él. De manera similar, si Alice no anuncia su "llamada" a Bob, después de que Bob lanza la moneda y anuncia el resultado, Alice puede informar que llamó al resultado que sea más deseable para ella. Alice y Bob pueden usar compromisos en un procedimiento que les permitirá a ambos confiar en el resultado:

1. Alice "llama" al lanzamiento de la moneda, pero solo le dice a Bob un compromiso con su llamada,
2. Bob lanza la moneda e informa el resultado,
3. Alice revela a qué se comprometió,
4. Bob verifica que la llamada de Alice coincide con su compromiso,
5. Si la revelación de Alice coincide con el resultado de la moneda que informó Bob, Alice gana

Para que Bob pueda sesgar los resultados a su favor, debe poder comprender la llamada oculta en el compromiso de Alice. Si el esquema de compromiso es bueno, Bob no puede sesgar los resultados. Del mismo modo, Alice no puede afectar el resultado si no puede cambiar el valor al que se compromete. ^{[5] [7]}

Existe una aplicación de la vida real de este problema, cuando las personas (a menudo en los medios de comunicación) se comprometen con una decisión o dan una respuesta en un "sobre sellado", que luego se abre más tarde. "Averigüemos si eso es lo que respondió el candidato", por ejemplo en un programa de juegos, puede servir como modelo de este sistema.

Pruebas de conocimiento cero

Un ejemplo motivador particular es el uso de esquemas de compromiso en pruebas de conocimiento cero . Los compromisos se utilizan en las pruebas de conocimiento cero con dos propósitos principales: primero, para permitir que el evaluador participe en pruebas de "corte y elección" en las que al verificador se le presentará una opción de qué aprender, y el evaluador revelará solo lo que corresponda a elección del verificador. Los esquemas de compromiso permiten al probador especificar toda la información de antemano y solo revelar lo que debe revelarse más adelante en la prueba. ^{[10] En} segundo lugar, el verificador también utiliza los compromisos en las pruebas de conocimiento cero, que a menudo especificará sus opciones con anticipación en un compromiso. Esto permite que las pruebas de conocimiento cero se compongan en paralelo sin revelar información adicional al probador.^[11]

Esquemas de firma

El esquema de firma de Lamport es un sistema de firma digital que se basa en mantener dos conjuntos de paquetes de datos secretos, publicar hash verificables de los paquetes de datos y luego revelar selectivamente paquetes de datos secretos parciales de una manera que se ajuste específicamente a los datos que se van a firmar. De esta forma, el compromiso público previo con los valores secretos se convierte en parte crítica del funcionamiento del sistema.

Debido a que el sistema de firmas de Lamport no se puede usar más de una vez (consulte el artículo correspondiente para obtener más detalles), se desarrolló un sistema para combinar muchos conjuntos de claves de Lamport bajo un valor público único que se puede vincular a una persona y verificar por otros. Este sistema utiliza árboles de hashes para comprimir muchos conjuntos de compromisos de clave de lamport publicados en un único valor de hash que se puede asociar con el posible autor de datos verificados posteriormente.

Compartición secreta verificable

Otra aplicación importante de los compromisos es la compartición secreta verificable , un componente fundamental de la computación segura entre varias partes . En un esquema de intercambio secreto , cada una de las partes recibe "acciones" de un valor que debe estar oculto a todos. Si se reúnen suficientes partes, sus acciones pueden usarse para reconstruir el secreto, pero incluso una camarilla maliciosa de tamaño insuficiente no debería aprender nada. El intercambio secreto es la base de muchos protocolos para una computación segura: para calcular de forma segura una función de alguna entrada compartida, los recursos compartidos secretos se manipulan en su lugar. Sin embargo, si los recursos compartidos van a ser generados por partes malintencionadas, puede ser importante que se pueda verificar que esos recursos compartidos sean correctos. En un esquema de intercambio de secretos verificables, la distribución de un secreto va acompañada de compromisos con las acciones individuales. Los compromisos no revelan nada que pueda ayudar a una camarilla deshonesta, pero las acciones permiten que cada parte individual verifique si sus acciones son correctas. ^[12]

Definiendo la seguridad

Las definiciones formales de los esquemas de compromiso varían mucho en notación y sabor. El primero de estos tipos es si el esquema de compromiso proporciona seguridad perfecta o computacional con respecto a las propiedades de ocultación o unión. Otro aspecto de este tipo es si el compromiso es interactivo, es decir, si tanto la fase de confirmación como la fase de revelación pueden verse como ejecutadas por un protocolo criptográfico o si son no interactivas, que constan de dos algoritmos Commit y CheckReveal . En el último caso, CheckReveal a menudo se puede ver como una versión desaleatorizada de Commit , y la aleatoriedad utilizada por Commit constituye la información de apertura.

Si el compromiso C con un valor x se calcula como C: = Compromiso (x, abierto) con abierto la aleatoriedad utilizada para calcular el compromiso, entonces CheckReveal (C, x, abierto) simplemente consiste en verificar la ecuación C = Compromiso (x , abierto) .

Utilizando esta notación y algunos conocimientos sobre funciones matemáticas y teoría de la probabilidad , formalizamos diferentes versiones de las propiedades vinculantes y ocultas de los compromisos. Las dos combinaciones más importantes de estas propiedades son los esquemas de compromiso perfectamente vinculantes y que ocultan computacionalmente y los esquemas de compromiso computacionalmente vinculantes y que ocultan perfectamente. Tenga en cuenta que ningún esquema de compromiso puede ser al mismo tiempo perfectamente vinculante y perfectamente oculto: un adversario computacionalmente ilimitado puede simplemente generar Commit (x, open) para cada valor de x y abrir hasta encontrar un par que dé como resultado C , y en un perfectamente vinculante esquema esto identifica de forma única x.

Enlace computacional

Sea abierto entre un conjunto de tamaños , es decir, se puede representar como una cadena de k bits, y sea ​​el esquema de compromiso correspondiente. Dado que el tamaño de k determina la seguridad del esquema de compromiso, se denomina parámetro de seguridad.${\displaystyle 2^{k}}$${\displaystyle {\text{Commit}}_{k}}$

Entonces, para todos los algoritmos de tiempo polinomial probabilístico no uniforme que producen y de longitud creciente k , la probabilidad de que y sea ​​una función despreciable en k .${\displaystyle x,x'}$${\displaystyle open,open'}$${\displaystyle x\neq x'}$${\displaystyle {\text{Commit}}_{k}(x,open)={\text{Commit}}_{k}(x',open')}$

Esta es una forma de análisis asintótico . También es posible establecer el mismo requisito usando seguridad concreta : Un esquema de compromiso Commit es seguro, si para todos los algoritmos que se ejecutan en el tiempo t y dan como resultado la probabilidad de que y es como máximo .${\displaystyle (t,\epsilon )}$${\displaystyle x,x',open,open'}$${\displaystyle x\neq x'}$${\displaystyle {\text{Commit}}(x,open)={\text{Commit}}(x',open')}$${\displaystyle \epsilon }$

Ocultación perfecta, estadística y computacional

Sea la distribución uniforme sobre los valores de apertura para el parámetro de seguridad k . Un esquema de compromiso es, respectivamente, ocultamiento perfecto, estadístico o computacional, si para todos los conjuntos de probabilidad y son iguales, estadísticamente cercanos o computacionalmente indistinguibles .${\displaystyle U_{k}}$${\displaystyle 2^{k}}$${\displaystyle x\neq x'}$ ${\displaystyle \{{\text{Commit}}_{k}(x,U_{k})\}_{k\in \mathbb {N} }}$${\displaystyle \{{\text{Commit}}_{k}(x',U_{k})\}_{k\in \mathbb {N} }}$

Imposibilidad de esquemas de compromiso de composición universal

Es imposible realizar esquemas de compromiso en el marco de componibilidad universal (UC). La razón es que el compromiso de la UC tiene que ser extraíble , como muestran Canetti y Fischlin ^[13] y se explica a continuación.

La funcionalidad de compromiso ideal, indicada aquí por F , funciona aproximadamente de la siguiente manera. Committer C envía valor m a F , que almacena y envía "recepción" a receptor R . Más tarde, C envía "abierto" a F , que envía m a R .

Ahora, suponga que tenemos un protocolo π que realiza esta funcionalidad. Supongamos que el confirmador C está dañado. En el marco de UC, eso esencialmente significa que C ahora está controlado por el entorno, que intenta distinguir la ejecución del protocolo del proceso ideal. Considere un entorno que elige un mensaje my luego le dice a C que actúe según lo prescrito por π , como si se hubiera comprometido con m . Tenga en cuenta aquí que para realizar F , el receptor debe, después de recibir un compromiso, enviar un mensaje "recibo". Una vez que el entorno ve este mensaje, le dice a C que abra el compromiso.

El protocolo sólo es segura si este escenario es indistinguible del caso ideal, donde interactúa el funcionalidad con un simulador de S . Aquí, S tiene el control de C . En particular, siempre que R emite "recibo", F tiene que hacer lo mismo. La única manera de hacerlo es por S para decirle C para enviar un valor de F . Sin embargo, nota que por este punto, m no se conoce a S . Por lo tanto, cuando el compromiso se abre durante la ejecución del protocolo, es poco probable que F se abra am , a menos que S pueda extraer mde los mensajes que recibió del entorno antes de que R envíe el recibo.

Sin embargo, un protocolo extraíble en este sentido no puede esconderse estadísticamente. Suponga que existe tal simulador S. Ahora puede considerar un entorno que, en lugar de corromper C , corrompe R en su lugar. Adicionalmente se ejecuta una copia de S . Los mensajes recibidos desde C se introducen en S , y respuestas de S se reenvían a C .

El entorno inicialmente le dice a C que se comprometa con un mensaje m . En algún punto de la interacción, S se comprometerá con un valor m ′ ; este mensaje se entrega a R , que emite m ′ . Tenga en cuenta que, por suposición, tenemos m '= m con alta probabilidad. Ahora, en el proceso ideal, el simulador tiene que generar m . Pero esto es imposible, porque en este punto el compromiso aún no se ha abierto, por lo que el único mensaje que R puede haber recibido en el proceso ideal es un mensaje de "recepción". Tenemos, pues, una contradicción.

Construcción

Un esquema de compromiso puede ser perfectamente vinculante (es imposible que Alice altere su compromiso después de haberlo hecho, incluso si tiene recursos computacionales ilimitados); o ocultarlo perfectamente (es imposible para Bob descubrir el compromiso sin que Alice lo revele, incluso si tiene recursos computacionales ilimitados); o formulado como un esquema de compromiso dependiente de la instancia, que se oculta o vincula según la solución a otro problema. ^{[14] [15]} Un esquema de compromiso no puede ser oculto y vinculante al mismo tiempo.

Compromiso de bits en el modelo de oráculo aleatorio

Los esquemas de compromiso de bits son triviales de construir en el modelo de oráculo aleatorio . Dada una función hash H con un 3 k bit de salida, para cometer el k bits mensaje m , Alice genera una aleatorio k bit cadena R y envía Bob H ( R || m ). La probabilidad de que exista cualquier R ′ , m ′ donde m ′ ≠ m tal que H ( R ′ || m ′ ) = H ( R || m ) es ≈ 2 ^{- k} , pero para probar cualquier conjetura en el mensaje mBob deberá realizar 2 ^k (para una suposición incorrecta) o 2 ^{k -1} (en promedio, para una suposición correcta) consultas al oráculo aleatorio. ^[16] Observamos que los esquemas anteriores basados ​​en funciones hash, esencialmente se pueden pensar en esquemas basados ​​en la idealización de estas funciones hash como oráculo aleatorio.

Compromiso de bits de cualquier permutación unidireccional

Se puede crear un esquema de compromiso de bits a partir de cualquier función unidireccional que sea inyectiva. El esquema se basa en el hecho de que cada función unidireccional se puede modificar (a través del teorema de Goldreich-Levin ) para poseer un predicado computacionalmente duro (mientras se conserva la propiedad inyectiva). Sea f una función inyectiva unidireccional, con h un predicado de núcleo duro. Luego, para comprometerse con un bit b, Alice elige una entrada aleatoria xy envía el triple

${\displaystyle (h,f(x),b\oplus h(x))}$

a Bob, donde denota XOR, es decir , módulo de adición bit a bit 2. Para liberar, Alice simplemente envía x a Bob. Bob verifica calculando f ( x ) y comparándolo con el valor comprometido. Este esquema se oculta porque para que Bob recupere b debe recuperar h ( x ). Dado que h es un predicado computacionalmente duro, recuperar h ( x ) de f ( x ) con una probabilidad mayor que la mitad es tan difícil como invertir f . La unión perfecta se deriva del hecho de que f es inyectiva y, por tanto,${\displaystyle \oplus }$f ( x ) tiene exactamente una preimagen.

Compromiso de bits de un generador pseudoaleatorio

Tenga en cuenta que, dado que no sabemos cómo construir una permutación unidireccional a partir de ninguna función unidireccional, esta sección reduce la fuerza del supuesto criptográfico necesario para construir un protocolo de compromiso de bits.

En 1991, Moni Naor mostró cómo crear un esquema de compromiso de bits a partir de un generador de números pseudoaleatorios criptográficamente seguro . ^[17] La construcción es la siguiente. Si G es un generador pseudoaleatorio tal que G toma n bits a 3 n bits, entonces si Alice quiere comprometerse con un bit b :

• Bob selecciona un vector R aleatorio de 3 n bits y envía R a Alice.
• Alice selecciona un vector aleatorio de n bits Y y calcula el vector de 3 n bits G ( Y ).
• Si b = 1, Alice envía G ( Y ) a Bob; de lo contrario, envía el bit a bit exclusivo o de G ( Y ) y R a Bob.

La que se libera Alice envía Y a Bob, que puede entonces comprobar si se recibió inicialmente G ( Y ) o G ( Y ) R .${\displaystyle \oplus }$

Este esquema es estadísticamente vinculante, lo que significa que incluso si Alice no tiene límites computacionales, no puede hacer trampa con una probabilidad mayor que 2 ^{- n} . Para Alice engañar, ella tendría que encontrar un Y 'de tal manera que G ( Y' ) = G ( Y ) R . Si pudiera encontrar ese valor, podría liberarse enviando la verdad y Y , o enviar la respuesta opuesta y Y ' . Sin embargo, G ( Y ) y G ( Y ' ) solo pueden producir 2 ⁿ valores posibles cada uno (eso es 2 ^{2 n} ) mientras${\displaystyle \oplus }$ R se elige entre 2 ^{3 n} valores. Ella no elige R , por lo que hay una probabilidad de 2 ^{2 n} / 2 ^{3 n} = 2 ^{- n de} que exista una Y 'que satisfaga la ecuación requerida para hacer trampa.

La propiedad sigue ocultando de una reducción estándar, si Bob puede decir si Alice comprometido con un cero o uno, sino que también es capaz de distinguir la salida del generador pseudo-aleatorio G de la verdadera aleatoria, lo que contradice la seguridad criptográfica del G .

Un esquema perfectamente vinculante basado en el problema del registro discreto y más allá

Alice elige un anillo de primer orden p , con generador multiplicativo g .

Alice elige aleatoriamente un valor secreto x de 0 a p  - 1 a comprometerse a y calcula c = g ^x y publica c . El problema del logaritmo discreto dicta que a partir de c , computacionalmente no es factible calcular x , por lo que bajo esta suposición, Bob no puede calcular x . Por otro lado, Alice no puede calcular a x ' <> x , tal que g ^x' = c , por lo que el esquema es vinculante.

Este esquema no oculta perfectamente, ya que alguien podría encontrar el compromiso si logra resolver el problema del logaritmo discreto . De hecho, este esquema no se esconde en absoluto con respecto al juego de escondite estándar, donde un adversario no debería ser capaz de adivinar cuál de los dos mensajes que eligió estaba comprometido, similar al juego IND-CPA . Una consecuencia de esto es que si el espacio de valores posibles de x es pequeño, entonces un atacante podría simplemente probarlos todos y el compromiso no se escondería.

Un mejor ejemplo de un esquema de compromiso perfectamente vinculante es aquel en el que el compromiso es el cifrado de x bajo un esquema de cifrado de clave pública semánticamente seguro con una integridad perfecta, y la liberación es la cadena de bits aleatorios utilizada para cifrar x . Un ejemplo de un esquema de compromiso que oculta información teóricamente es el esquema de compromiso de Pedersen, que es vinculante bajo el supuesto de logaritmo discreto. Además del esquema anterior, utiliza otro generador h del grupo principal y un número aleatorio r . El compromiso está establecido . ^[18]${\displaystyle c=g^{x}h^{r}}$

Estas construcciones están estrechamente relacionadas y basadas en las propiedades algebraicas de los grupos subyacentes, y la noción originalmente parecía estar muy relacionada con el álgebra. Sin embargo, se demostró que es posible basar esquemas de compromisos estadísticamente vinculantes en supuestos generales no estructurados, mediante la noción de hash interactivo para compromisos a partir de supuestos de complejidad general (específica y originalmente, basados ​​en cualquier permutación de una sola vía) como en. ^[19]

Revelación parcial

Algunos esquemas de compromiso permiten que se presente una prueba de solo una parte del valor comprometido. En estos esquemas, el valor secreto es un vector de muchos valores separables individualmente.${\displaystyle X}$

${\displaystyle X=(x_{1},x_{2},...,x_{n})}$

El compromiso se calcula en la fase de compromiso. Normalmente, en la fase de revelación, el probador revelaría todos y algunos datos de prueba adicionales (como en el compromiso de bits simple ). En cambio, el probador puede revelar cualquier valor individual del vector y crear una prueba eficiente de que es el elemento auténtico del vector original el que creó el compromiso . La prueba no requiere ningún otro valor que no sea para ser revelado, y es imposible crear pruebas válidas que revelen valores diferentes para cualquiera de los verdaderos. ^[20]${\displaystyle C}$${\displaystyle X}$${\displaystyle X}$${\displaystyle R}$${\displaystyle X}$${\displaystyle i}$${\displaystyle C}$${\displaystyle X}$${\displaystyle x_{i}}$${\displaystyle x_{i}}$

Hash de vectores

El hash vectorial es un esquema de revelación parcial de compromiso vectorial ingenuo basado en compromiso de bits. Los valores se eligen al azar. Los compromisos individuales se crean mediante hash . El compromiso general se calcula como${\displaystyle m_{1},m_{2},...m_{n}}$${\displaystyle y_{1}=H(x_{1}||m_{1}),y_{2}=H(x_{2}||m_{2}),...}$

${\displaystyle C=H(y_{1}||y_{2}||...||y_{n})}$

Para probar un elemento del vector , el probador revela los valores${\displaystyle X}$

${\displaystyle (i,y_{1},y_{2},...,y_{i-1},x_{i},m_{i},y_{i+1},...,y_{n})}$

El verificador puede calcular a partir de y , y luego puede verificar que el hash de todos los valores es el compromiso . Este esquema es ineficaz ya que la prueba está en tamaño y tiempo de verificación. Alternativamente, si es el conjunto de todos los valores, entonces el compromiso es en tamaño y la prueba en tamaño y tiempo de verificación. De cualquier manera, el compromiso o la prueba se adaptan .${\displaystyle y_{i}}$${\displaystyle x_{i}}$${\displaystyle m_{i}}$${\displaystyle y}$${\displaystyle C}$${\displaystyle O(n)}$${\displaystyle C}$${\displaystyle y}$${\displaystyle O(n)}$${\displaystyle O(1)}$${\displaystyle O(n)}$

Árbol Merkle

Un ejemplo común de un esquema práctico de revelación parcial es un árbol Merkle , en el que se crea un árbol hash binario a partir de los elementos de . Este esquema crea compromisos de tamaño y pruebas de tamaño y tiempo de verificación. El hash raíz del árbol es el compromiso . Para probar que un revelado es parte del árbol original, solo los valores hash del árbol, uno de cada nivel, deben revelarse como prueba. El verificador puede seguir la ruta desde el nodo hoja reclamado hasta la raíz, haciendo hash en los nodos hermanos en cada nivel y, finalmente, llegando a un valor de nodo raíz que debe ser igual . ^[21]${\displaystyle X}$${\displaystyle O(1)}$${\displaystyle O(\log _{2}{n})}$${\displaystyle C}$${\displaystyle x_{i}}$${\displaystyle \log _{2}{n}}$${\displaystyle C}$

Compromiso de KZG

Un compromiso Kate-Zaverucha-Goldberg utiliza criptografía basada en emparejamiento para construir un esquema de revelación parcial con tamaños de compromiso, tamaños de prueba y tiempo de verificación de prueba. En otras palabras, a medida que aumenta el número de valores en , los compromisos y pruebas no aumentan, y las pruebas no requieren más esfuerzo para verificar.${\displaystyle O(1)}$${\displaystyle n}$${\displaystyle X}$

Un compromiso de KZG requiere un conjunto predeterminado de parámetros para crear un emparejamiento y un elemento de trampilla confiable. Por ejemplo, se puede utilizar un emparejamiento Tate . Suponga que son los grupos aditivos y es el grupo multiplicativo del emparejamiento. En otras palabras, el emparejamiento es el mapa . Sea el elemento de la trampilla (si es el primer orden de y ), y sean y los generadores de y respectivamente. Como parte de la configuración de los parámetros, asumimos que y son valores conocidos y compartidos para arbitrariamente muchos valores enteros positivos de , mientras que el valor de la trampilla en sí se descarta y nadie lo conoce.${\displaystyle \mathbb {G} _{1},\mathbb {G} _{2}}$${\displaystyle \mathbb {G} _{T}}$${\displaystyle e:\mathbb {G} _{1}\times \mathbb {G} _{2}\rightarrow \mathbb {G} _{T}}$${\displaystyle t\in \mathbb {F} _{p}}$${\displaystyle p}$${\displaystyle \mathbb {G} _{1}}$${\displaystyle \mathbb {G} _{2}}$${\displaystyle G}$${\displaystyle H}$${\displaystyle \mathbb {G} _{1}}$${\displaystyle \mathbb {G} _{2}}$${\displaystyle G\cdot t^{i}}$${\displaystyle H\cdot t^{i}}$${\displaystyle i}$${\displaystyle t}$

Cometer

Un compromiso de KZG reformula el vector de valores a comprometer como polinomio. Primero, calculamos un polinomio tal que para todos los valores de en nuestro vector. La interpolación de Lagrange nos permite calcular ese polinomio${\displaystyle p(i)=x_{i}}$${\displaystyle x_{i}}$

${\displaystyle p(x)=\sum _{i=0}^{n-1}x_{i}\prod _{0\leq j<n,j\neq i}{\frac {x-j}{i-j}}}$

Bajo esta formulación, el polinomio ahora codifica el vector, donde . Sean los coeficientes de , tales que . El compromiso se calcula como${\displaystyle p(0)=x_{0},p(1)=x_{1},...}$${\displaystyle p_{0},p_{1},...,p_{n-1}}$${\displaystyle p}$${\textstyle p(x)=\sum _{i=0}^{n-1}p_{i}x^{i}}$

${\displaystyle C=\sum _{i=0}^{n-1}p_{i}Gt^{i}}$

Esto se calcula simplemente como un producto escalar entre los valores predeterminados y los coeficientes polinomiales . Dado que es un grupo aditivo con asociatividad y conmutatividad, es igual a simplemente , ya que todas las sumas y multiplicaciones con pueden distribuirse fuera de la evaluación. Dado que se desconoce el valor de la trampilla , el compromiso es esencialmente el polinomio evaluado en un número conocido por nadie, con el resultado oculto en un elemento opaco de .${\displaystyle G\cdot t^{i}}$${\displaystyle p_{i}}$${\displaystyle \mathbb {G} _{1}}$${\displaystyle C}$${\displaystyle G\cdot p(t)}$${\displaystyle G}$${\displaystyle t}$${\displaystyle C}$${\displaystyle \mathbb {G} _{1}}$

Revelar

Una prueba de KZG debe demostrar que los datos revelados son el valor auténtico de cuándo se calcularon. Vamos , el valor revelado debemos probar. Dado que el vector de fue reformulado en un polinomio, realmente necesitamos probar que el polinomio , cuando se evalúa en, toma el valor . Simplemente, solo tenemos que demostrarlo . Haremos esto demostrando que restar de produce un cero en . Defina el polinomio como${\displaystyle x_{i}}$${\displaystyle C}$${\displaystyle y=x_{i}}$${\displaystyle x_{i}}$${\displaystyle p}$${\displaystyle i}$${\displaystyle y}$${\displaystyle p(i)=y}$${\displaystyle y}$${\displaystyle p}$${\displaystyle i}$${\displaystyle q}$

${\displaystyle q(x)={\frac {p(x)-y}{x-i}}}$

Este polinomio es en sí mismo la prueba de que , porque si existe, entonces es divisible por , lo que significa que tiene una raíz en , entonces (o, en otras palabras, ). La prueba KZG demostrará que existe y tiene esta propiedad.${\displaystyle p(i)=y}$${\displaystyle q}$${\displaystyle p(x)-y}$${\displaystyle x-i}$${\displaystyle i}$${\displaystyle p(i)-y=0}$${\displaystyle p(i)=y}$${\displaystyle q}$

El probador calcula a través de la división polinomial anterior, luego calcula el valor de prueba KZG${\displaystyle q}$${\displaystyle \pi }$

${\displaystyle \pi =\sum _{i=0}^{n-1}q_{i}Gt^{i}}$

Esto es igual a , como arriba. En otras palabras, el valor de prueba es el polinomio nuevamente evaluado en el valor de la trampilla , oculto en el generador de .${\displaystyle G\cdot q(t)}$${\displaystyle q}$${\displaystyle t}$${\displaystyle G}$${\displaystyle \mathbb {G} _{1}}$

Este cálculo solo es posible si los polinomios anteriores fueran divisibles uniformemente, porque en ese caso el cociente es un polinomio, no una función racional . Debido a la construcción de la trampilla, no es posible evaluar una función racional en el valor de la trampilla, solo evaluar un polinomio usando combinaciones lineales de las constantes conocidas precalculadas de . Por eso es imposible crear una prueba para un valor incorrecto de .${\displaystyle q}$${\displaystyle G\cdot t^{i}}$${\displaystyle x_{i}}$

Verificar

Para verificar la prueba, se usa el mapa bilineal del emparejamiento para mostrar que el valor de la prueba resume un polinomio real que demuestra la propiedad deseada, que es la que se dividió uniformemente por . El cálculo de verificación comprueba la igualdad${\displaystyle \pi }$${\displaystyle q}$${\displaystyle p(x)-y}$${\displaystyle x-i}$

${\displaystyle e(\pi ,H\cdot t-H\cdot i)\ {\stackrel {?}{=}}\ e(C-G\cdot y,H)}$

donde está la función de mapa bilineal como arriba. es una constante precalculada, se calcula en base a .${\displaystyle e}$${\displaystyle H\cdot t}$${\displaystyle H\cdot i}$${\displaystyle i}$

Al reescribir el cálculo en el grupo de emparejamiento , sustituyendo en y , y dejando que sea ​​una función auxiliar para subir al grupo de emparejamiento, la verificación de la prueba es más clara${\displaystyle \mathbb {G} _{T}}$${\displaystyle \pi =q(t)\cdot H}$${\displaystyle C=p(t)\cdot G}$${\displaystyle \tau (x)=e(G,H)^{x}}$

${\displaystyle e(\pi ,H\cdot t-H\cdot i)=e(C-G\cdot y,H)}$

${\displaystyle e(G\cdot q(t),H\cdot t-H\cdot i)=e(G\cdot p(t)-G\cdot y,H)}$

${\displaystyle e(G\cdot q(t),H\cdot (t-i))=e(G\cdot (p(t)-y),H)}$

${\displaystyle e(G,H)^{q(t)\cdot (t-i)}=e(G,H)^{p(t)-y}}$

${\displaystyle \tau (q(t)\cdot (t-i))=\tau (p(t)-y)}$

Suponiendo que el mapa bilineal se construye de manera válida, esto demuestra que , sin que el validador sepa qué o son. El validador puede estar seguro de esto porque si , entonces los polinomios evalúan la misma salida en el valor de la trampilla . Esto demuestra que los polinomios son idénticos porque, si los parámetros se construyeron de manera válida, nadie conoce el valor de la trampilla, lo que significa que es imposible diseñar un polinomio para que tenga un valor específico en la trampilla (según el lema de Schwartz-Zippel ). Si ahora se verifica que es verdadero, entonces se verifica que existe, por lo tanto, debe ser polinomio-divisible por , por lo que debido al teorema del factor${\displaystyle q(x)(x-i)=p(x)-y}$${\displaystyle p}$${\displaystyle q}$${\displaystyle \tau (q(t)\cdot (t-i))=\tau (p(t)-y)}$${\displaystyle x=t}$${\displaystyle q(x)(x-i)=p(x)-y}$${\displaystyle q}$${\displaystyle p(x)-y}$${\displaystyle (x-i)}$${\displaystyle p(i)-y=0}$. Esto prueba que el valor th del vector comprometido debe haber sido igual , ya que ese es el resultado de evaluar el polinomio comprometido en .${\displaystyle i}$${\displaystyle y}$${\displaystyle i}$

Por qué se utiliza el emparejamiento de mapas bilineales

La utilidad del emparejamiento de mapas bilineales es permitir que la multiplicación de por ocurra de forma segura. Estos valores realmente se encuentran en , donde se supone que la división es computacionalmente difícil. Por ejemplo, podría ser una curva elíptica sobre un campo finito, como es común en la criptografía de curva elíptica . Entonces, el supuesto de división se denomina problema de logaritmo discreto de curva elíptica , y este supuesto es también lo que evita que se calcule el valor de la trampilla, lo que lo convierte también en una base de los compromisos de KZG. En ese caso, queremos comprobar si . Esto no se puede hacer sin un emparejamiento, porque con valores en la curva de y , no podemos calcular . Eso violaría el${\displaystyle q(x)}$${\displaystyle x-i}$${\displaystyle \mathbb {G} _{1}}$${\displaystyle \mathbb {G} _{1}}$${\displaystyle q(x)(x-i)=p(x)-y}$${\displaystyle G\cdot q(x)}$${\displaystyle G\cdot (x-i)}$${\displaystyle G\cdot (q(x)(x-i))}$suposición computacional de Diffie-Hellman , una suposición fundamental en la criptografía de curva elíptica . En su lugar, utilizamos un emparejamiento para evitar este problema. todavía se multiplica por para obtener , pero el otro lado de la multiplicación se realiza en el grupo emparejado , por lo que ,. Calculamos , que, debido a la bilinealidad del mapa, es igual a . En este grupo de salida todavía tenemos el problema del logaritmo discreto , por lo que aunque conocemos ese valor y , no podemos extraer el exponente , evitando cualquier contradicción con el logaritmo discreto antes. Este valor se puede comparar con aunque, y si${\displaystyle q(x)}$${\displaystyle G}$${\displaystyle G\cdot q(x)}$${\displaystyle \mathbb {G} _{2}}$${\displaystyle H\cdot (t-i)}$${\displaystyle e(G\cdot q(t),H\cdot (t-i))}$${\displaystyle e(G,H)^{q(t)\cdot (t-i)}}$${\displaystyle \mathbb {G} _{T}}$${\displaystyle e(G,H)}$${\displaystyle q(t)\cdot (t-i)}$${\displaystyle e(G\cdot (p(t)-y),H)=e(G,H)^{p(t)-y}}$${\displaystyle e(G,H)^{q(t)\cdot (t-i)}=e(G,H)^{p(t)-y}}$podemos concluir que , sin saber nunca cuál es el valor real de , mucho menos .${\displaystyle q(t)\cdot (t-i)=p(t)-y}$${\displaystyle t}$${\displaystyle q(t)(t-i)}$

Además, un compromiso de KZG se puede extender para probar los valores de cualquier valor arbitrario de (no solo un valor), con el tamaño de la prueba restante , pero el tiempo de verificación de la prueba se escala con . La prueba es la misma, pero en lugar de restar una constante , restamos un polinomio que causa múltiples raíces, en todas las ubicaciones que queremos probar, y en lugar de dividir por , dividimos entre para esas mismas ubicaciones. ^[22]${\displaystyle k}$${\displaystyle X}$${\displaystyle O(1)}$${\displaystyle O(k)}$${\displaystyle y}$${\displaystyle x-i}$${\textstyle \prod _{i}x-i}$

Compromiso de bits cuánticos

Es una pregunta interesante en criptografía cuántica si existen protocolos de compromiso de bits incondicionalmente seguros en el nivel cuántico, es decir, protocolos que son (al menos asintóticamente) vinculantes y ocultos incluso si no hay restricciones en los recursos computacionales. Uno podría esperar que haya una forma de explotar las propiedades intrínsecas de la mecánica cuántica, como en los protocolos para la distribución de claves incondicionalmente segura .

Sin embargo, esto es imposible, como demostró Dominic Mayers en 1996 (ver ^[23] para la prueba original). Cualquier protocolo de este tipo puede reducirse a un protocolo en el que el sistema se encuentra en uno de dos estados puros después de la fase de compromiso, dependiendo del bit que Alice quiera comprometer. Si el protocolo oculta incondicionalmente, entonces Alice puede transformar unitariamente estos estados entre sí utilizando las propiedades de la descomposición de Schmidt , derrotando efectivamente la propiedad vinculante.

Una suposición sutil de la prueba es que la fase de confirmación debe finalizar en algún momento. Esto deja espacio para los protocolos que requieren un flujo de información continuo hasta que se revele el bit o se cancele el protocolo, en cuyo caso ya no es vinculante. ^[24] De manera más general, la prueba de Mayers se aplica solo a protocolos que explotan la física cuántica pero no la relatividad especial . Kent ha demostrado que existen protocolos incondicionalmente seguros para el compromiso de bits que explotan el principio de la relatividad especial que establece que la información no puede viajar más rápido que la luz. ^[25]

Compromisos basados ​​en funciones físicas no clonables

Las funciones físicas no clonables (PUF) se basan en el uso de una clave física con aleatoriedad interna, que es difícil de clonar o emular. Las PUF electrónicas, ópticas y de otro tipo ^[26] se han analizado ampliamente en la bibliografía, en relación con sus posibles aplicaciones criptográficas, incluidos los esquemas de compromiso. ^{[27] [28]}

Ver también

• Transferencia ajena
• Acumulador (criptografía)
• Fiesta de firma de llaves
• Web de confianza
• Zerocoin

Referencias

1. Oded Goldreich (2001). Fundamentos de la criptografía: Volumen 1, Herramientas básicas ( borrador disponible en el sitio del autor). Prensa de la Universidad de Cambridge. ISBN  0-521-79172-3 . (ver también http://www.wisdom.weizmann.ac.il/~oded/foc-book.html ) ^{: 224}
2. Gilles Brassard, David Chaum y Claude Crepeau, Pruebas de conocimiento mínimas de divulgación , Revista de Ciencias de la Computación y Sistemas, vol. 37, págs. 156-189, 1988.
3. Goldreich, Oded; Micali, Silvio; Wigderson, Avi (1991). "Pruebas que no aportan nada más que su validez". Revista de la ACM . 38 (3): 690–728. CiteSeerX 10.1.1.420.1478 . doi : 10.1145 / 116825.116852 . S2CID 2389804 .  
4. Russell Impagliazzo, Moti Yung: cálculos directos de conocimiento mínimo. CRYPTO 1987: 40-51
5. Moni Naor, Compromiso de bits mediante pseudoaleatoriedad , Journal of Cryptology 4: 2 págs. 151-158, 1991.
6. Claude Crépeau, Compromiso , MCgill.ca , consultado el 11 de abril de 2008
7. Manuel Blum, Coin Flipping by Telephone , Proceedings of CRYPTO 1981, pp. 11-15, 1981, reimpreso en SIGACT News vol. 15, págs. 23-27, 1983.
8. Incluso Shimon. Protocolo de firma de contratos. En Allen Gersho , ed., Advances in Cryptography (actas de CRYPTO '82), págs. 148-153, Santa Bárbara, CA, EE. UU., 1982.
9. A. Shamir, RL Rivest y L. Adleman, Mental Poker . En David A. Klarner , ed., The Mathematical Gardner , págs. 37-43. Wadsworth, Belmont, California, 1981.
10. Oded Goldreich , Silvio Micali y Avi Wigderson , Pruebas que no arrojan nada más que su validez, o todos los idiomas en NP tienen sistemas de prueba de conocimiento cero , Journal of the ACM , 38: 3, págs. 690–728, 1991
11. Oded Goldreich y Hugo Krawczyk , Sobre la composición de sistemas de prueba de conocimiento cero , SIAM Journal on Computing , 25: 1, págs. 169-192, 1996
12. Gennaro; Rosario; Rabin, Michael O .; Rabin, Tal. "VSS simplificado y cálculos multiparte de vía rápida con aplicaciones a la criptografía de umbral". Actas del Decimoséptimo Simposio Anual de ACM sobre Principios de Computación Distribuida . Junio ​​de 1998.
13. R. Canetti y M. Fischlin. Compromisos universalmente compostables.
14. Shien Hin Ong y Salil Vadhan (1990). Conocimiento cero perfecto en ronda constante, In Proc. STOC, pág. 482-493, citado en Shien Hin Ong y Salil Vadhan (2008). Equivalencia entre conocimiento cero y compromisos, teoría de la criptografía.
15. Toshiya Itoh, Yiji Ohta, Hiroki Shizuya (1997). Una primitiva criptográfica dependiente del idioma, In J. Cryptol., 10 (1): 37-49, citado en Shien Hin Ong y Salil Vadhan (2008). Equivalencia entre conocimiento cero y compromisos, teoría de la criptografía.
16. Wagner, David (2006), Solución de medio término , p. 2 , consultado el 26 de octubre de 2015
17. "Citas: compromiso de bits utilizando generadores pseudoaleatorios - Naor (ResearchIndex)" . Citeseer.ist.psu.edu . Consultado el 7 de junio de 2014 .
18. Tang, Chunming; Pei, Dingyi; Liu, Zhuojun; He, Yong (16 de agosto de 2004). "Pedersen: intercambio secreto verificable seguro no interactivo y teórico de la información" (PDF) . Archivo ePrint de criptología . Avances en criptología CRYPTO 1991 Springer. Archivado desde el original (PDF) el 11 de agosto de 2017 . Consultado el 2 de febrero de 2019 .
19. Moni Naor, Rafail Ostrovsky, Ramarathnam Venkatesan, Moti Yung: Argumentos perfectos de conocimiento cero para NP usando cualquier permutación unidireccional. J. Cryptology 11 (2): 87-108 (1998) [1]
20. Catalano, Dario; Fiore, Dario (2013). "Compromisos vectoriales y sus aplicaciones" . Criptografía de clave pública - PKC 2013 . Apuntes de conferencias en Ciencias de la Computación. Springer Berlín Heidelberg. 7778 : 55–72. doi : 10.1007 / 978-3-642-36362-7_5 . ISBN 978-3-642-36362-7. Catalano, Darío; Fiore, Dario (2013). "Compromisos vectoriales y sus aplicaciones" (PDF) . Asociación Internacional para la Investigación Criptológica .
21. Becker, Georg (18 de julio de 2008). "Esquemas de firma de Merkle, árboles de Merkle y su criptoanálisis" (PDF) . Ruhr-Universität Bochum. pag. 16 . Consultado el 20 de noviembre de 2013 .
22. Kate, Aniket; Zaverucha, Gregory; Goldberg, Ian (2010). "Compromisos de tamaño constante con polinomios y sus aplicaciones" (PDF) . Congreso Internacional de Teoría y Aplicación de la Criptología y Seguridad de la Información .
23. Brassard, Crépeau, Mayers, Salvail: una breve revisión sobre la imposibilidad del compromiso de bits cuánticos
24. A. Kent: Compromiso de bits clásico seguro mediante canales de comunicación de capacidad fija
25. Kent, A. (1999). "Compromiso de bits incondicionalmente seguro". Phys. Rev. Lett . 83 (7): 1447–1450. arXiv : quant-ph / 9810068 . Código Bibliográfico : 1999PhRvL..83.1447K . doi : 10.1103 / PhysRevLett.83.1447 . S2CID 8823466 . 
26. McGrath, Thomas; Bagci, Ibrahim E .; Wang, Zhiming M .; Roedig, Utz; Joven, Robert J. (12 de febrero de 2019). "Una taxonomía PUF" . Revisiones de física aplicada . 6 (1): 011303. Bibcode : 2019ApPRv ... 6a1303M . doi : 10.1063 / 1.5079407 .
27. Rührmair, Ulrich; van Dijk, Marten (1 de abril de 2013). "Sobre el uso práctico de funciones físicas no clonables en protocolos de transferencia inconsciente y compromiso de bits". Revista de Ingeniería Criptográfica . 3 (1): 17-28. doi : 10.1007 / s13389-013-0052-8 . hdl : 1721,1 / 103985 . ISSN 2190-8516 . S2CID 15713318 .  
28. Nikolopoulos, Georgios M. (30 de septiembre de 2019). "Esquema óptico para compromisos criptográficos con claves físicas no clonables". Optics Express . 27 (20): 29367–29379. arXiv : 1909.13094 . Código Bib : 2019OExpr..2729367N . doi : 10.1364 / OE.27.029367 . ISSN 1094-4087 . PMID 31684673 . S2CID 203593129 .   

enlaces externos

• Compromiso de bits cuánticos en arxiv.org
• Compromisos polinomiales de tamaño constante Kate-Zaverucha-Goldberg (KZG) - Alin Tomescu
• Compromisos polinomiales de Kate