in

¿Es seguro este esquema de oráculo aleatorio distribuido?

Esta pregunta proviene de un problema planteado en otra pregunta: ¿Firma de umbral no interactivo sin emparejamiento bilineal (es posible)?

¿Es seguro el modelo de oráculo aleatorio propuesto cuando se intenta generar un resultado distinto y aleatorio? $m \veces G = M$ ¿valor?

Haciendo la interpolación para $t$ acciones comprometidas $m^{‘}_i$ resultados en: $l_0 \times M_0 + \sum^t_{i=1} l_i \cdot m^{‘}_i \times G = m \times G$ que se reduce a $(m – \sum^{t}_{i=1} l_i \cdot m^{‘}_i) \cdot l^{-1}_0 \times G = M_0$donde $M_0$ siempre es diferente para cada firma. Entonces, supongo que no podemos reutilizar los valores anteriores para realizar el ataque.

¿Cómo resuelves un buscado? $m$ valor sin resolver el DLP? Buscando $m^{‘}_i$ y $m$ por algún desconocido $m_0$ es la fuerza bruta del DLP, ¡incluso en el contexto de k-sums!

Lo que he visto en el problema de k-sumas/cumpleaños generalizado es una forma de resolver $x_1 \oplus … \oplus x_n = 0$. Asignando este enfoque a nuestro problema, debemos tratar de resolver para $x_1 \oplus … \oplus x_n = m_0$ equivalente a $x_1 \oplus … \oplus x_n \oplus m_0 = 0$. El problema es, $m_0$ tiene un valor específico, pero el solucionador lo desconoce debido a DLP. ¿Cómo podemos resolver algo que no sabemos? Si tal solución fuera posible, ¿no será esto la solución del DLP?

¿Necesito una aclaración matemática para explicar exactamente cómo se realiza este ataque?

Editado 1: prueba matemática ampliada:
Tratando de seguir la lógica de @Aman Grewal, intentemos atacar en un escenario de k-sum.

Todas las variables marcadas en el formulario $c^*$ son controlados por el atacante. El objetivo del atacante es firmar un contrato aleatorio $B^*$ para un enviado $B$ tal que $B^* \neq B$. El atacante tiene acceso a $M_0$ y $c=H(A||M||B)$ para este o cualquier mensaje anterior. Suponga que el atacante tiene conocimiento de $t$ acciones de $y_i$.

Eliminamos los coeficientes de Lagrange $l_i$ de las matemáticas, ya que son públicas y no afectan la prueba final. Para una sola firma tenemos:

  1. Para un conjunto de seleccionados al azar $m_i^* \veces G = M_i^*$ uno puede derivar $\sum_{i=1}^t M_i^* + M_0 = M^*$
  2. Luego $c^* = H(Y||M^*||B^*)$ y la salida de una sola firma es $(m_0 + c \cdot y_0) + \sum_{i=1}^t (m_i^* + c_i^* \cdot y_i) = m^* + c^* \cdot y$. Asumiendo $m_0 + \sum_{i=1}^t m_i^* = m^*$ y $c + \sum_{i=1}^t c_i^* = c^*$ (este último no es del todo correcto, ya que eliminamos los coeficientes de Lagrange, pero esto es aún más fácil de atacar)

Uno no puede resolver por $c_i^*$ en $\sum_{i=1}^t (m_i^* + c_i^* \cdot y_i) = (m^* + c^* \cdot y) – (m_0 + c \cdot y_0)$. Incluso suponiendo que $m^*$ es igual a algún resultado anterior y que $c^*$ depende directamente de $c_i^*$. Hay $t + 3$ incógnitas correspondientes a $(c_i^*, y_0, y, m_0)$. Entonces… vamos a expandirlo a $j$ firmas:

La ecuación real que debemos resolver es:
$\sum_{j=1}^n \sum_{i=1}^t (m_{ij}^* + c_{ij}^* \cdot y_i) = \sum_{j=1}^n [(m_j^* + c_j^* \cdot y) – (m_{0j} + c_j \cdot y_0)]PS

Suponiendo que de alguna manera puede tener muchas igualdades en este sistema de ecuaciones entre firmas $j$todavía te queda $(t + 2) + j$ incógnitas para $(c_i^*, y_0, y, m_{0j})$. Por cada nueva ecuación, tienes una nueva incógnita $m_{0d}$ que no puedes alcanzar. $m_{0d}$ es distinto para cada nueva firma por la definición del modelo de amenaza.

Editado2: Eq versión pública:
La versión pública de la ecuación es:
$\sum_{j=1}^n \sum_{i=1}^t (M_{ij}^* + c_{ij}^* \cdot Y_i) = \sum_{j=1}^n [(M_j^* + c_j^* \cdot Y) – (M_{0j} + c_j \cdot Y_0)]PS

En este caso solo existen los $c_{ij}^*$ incógnitas, pero tenemos el DLP. Si hay una manera eficiente de resolver esto, ¿estamos rompiendo el DLP?

Si alguien puede cuestionar esta lógica matemática para lograr un ataque exitoso, aceptaré su respuesta.

1 respuesta
1

Los atacantes pueden elegir su $M_0, m_0$ par sin resolver DLP.

¿Te ayudó la respuesta?

Subscribirse
Notificar por
guest
0 Comentarios
Inline Feedbacks
Ver todas las Respuestas

JavaScript asíncrono eliminar documento de base de fuego

Extraiga la información de dmidecode a través de SSH y guarde la información en un archivo local con la entrada del nombre de host