in

¿Cuál es la estructura más pequeña, cíclica en 3 direcciones, consistente de valores aleatorios que se puede ocultar en la máquina del adversario? (alguna comparación)

O más general cada miembro puede ser parte de hasta tres planos euclidianos locales 2D de 2 dimensiones diferentes.
[pic1]

(cada uno de esos planos es cíclico en dos direcciones ortogonales, como un toro)

Dado solo un miembro, podría verse como una red de nodos:
(solo un nodo con algún vecindario que se muestra aquí. Esos vecinos tienen nuevamente vecinos que no se muestran aquí)
(izquierda: 1 plano, intersección derecha de 2 planos)
ingrese la descripción de la imagen aquí ingrese la descripción de la imagen aquí
intersección de 3 planos:
ingrese la descripción de la imagen aquí

A pesar de eso, debe haber alguna forma determinista de mapear la vecindad de un nodo en gráficos planos en esos tres planos euclidianos 2D (con densidad de nodo constante). Por lo tanto, los vecinos de nodos adyacentes tienden a ser vecinos también y no tienen $n$-crecimiento de barrio que necesita por ejemplo espacio hiperbolico para la representacion.
Comenzando en un nodo $n$ y (principalmente) seguir una dirección de progresión conducirá al mismo nodo nuevamente después (en el mejor de los casos) $C_n$ pasos. Entonces es cíclico con la duración del ciclo. $C_n$. En el mejor de los casos, esto es igual para todos los nodos en todas las direcciones. Pero para ser menos estrictos, es posible alguna variación siempre que la duración del ciclo sea similar a la de los nodos cercanos.

La meta:
Encontrar una estructura tal que minimice la duración del ciclo. $C$ (mejor $ \ le 2^{50} $) y el número total de nodos $N$ (mejor caso $N=C^3$ o $ \ le 2^{150} $) manteniendo lo más difícil posible calcular la relación entre dos nodos aleatorios (mejor $\ge O(C^2)$ y $ O (\ sqrt[3]{N^2})$ o en números $\ge 2^{100}$)


Especializados en métodos criptográficos:

Hasta donde yo sé, en criptografía solo hay estructuras que son más especializadas o en parte más generales que la estructura descrita anteriormente.
Si, por ejemplo, el número de vecinos de un nodo se establece en un valor fijo de 6, obtenemos una estructura como esta:
(izquierda: intersección de 3 planos en un solo nodo/número, derecha: cada nodo/número tiene esta estructura aquí)

intersección de 3 planos en un solo nodo/número.  Cada generador es igual a una dirección de progresión.  Un plano tiene todos los valores posibles usando dos generadores aparte de la estructura más general por encima de cualquier número/nodo tiene la misma estructura aquí.  Entonces cada número tiene 3*2 posibilidades de progresión con 3 generadores y sus inversos

Esto se puede lograr con 3 generadores y un adecuado $ \ bmod P $ como se indica a continuación.
Para cada tipo, agregaré algunas razones por las que no funciona y (mis) hilos relacionados para obtener más detalles.


Comparación con los métodos criptográficos probados:

  1. Tres generadores $q,r,s$ con $\bmod P = 2\cdot Q \cdot R \cdot S +1$ y $q^Q \equiv r^R \equiv s^S \equiv 1 \bmod P$ $\texto{ } $[1]

    • $-$ $P$ debe ser muy grande para evitar la factorización $\gg 2^{150}$
    • $-$ al conocer los tamaños de ciclo, se puede reducir a un problema mucho más fácil con el algoritmo de Pohlig-Hellman
  2. Curvas elípticas con 3 generadores $F,G,H$ y con estos valores $i \cdot F + j \cdot G + k \cdot H$ [1] [2]

    • $-$ el tamaño del ciclo para cada dirección es en todo el dominio
    • $+$ solo se necesitan números relativamente pequeños
    • $-$ pero todavía un tamaño de dominio/ciclo de $2^{200}$ necesario (tamaño del ciclo objetivo solamente $2^{50}$)
  3. AES o cifrado de bloque similar:

    • $-$ separados en múltiples ciclos con tamaño desconocido, solo se conoce la distribución [1]
    • $-$ uno por dirección? $\flecha derecha $ dominio de $2^{300}$ necesario y puede reducirse a un problema de una sola dimensión
    • $-$ concatenar 3 AES a un solo miembro? $\flecha derecha $ grande $n$-vecindario, similar a simplemente usar valores aleatorios $\flecha derecha $ se puede encontrar una coincidencia en AES128 alternativo (modo ECB) después de $\aprox.\sqrt{2^{64}}$ pasos de progresión [2]
  4. secuencia de 3 direcciones $ s_ {ijk} = s_0 ^ {\ estilo de texto \ beta ^ i \ gamma ^ j \ delta ^ k} \ bmod (N = P \ cdot Q) $ – difícil de resolver porque $\fi(N)$ desconocido

    • por $N=(2\cdot p +1)\cdot (2\cdot q +1)$ con gen. $\beta,\gamma,\delta$ raíces primitivas de $p,q$ [1]
      • $+$ $ O (\ sqrt[2]{C^3})$ (por lo que sé)
      • $-$ pero solo si $\fi(N)$ es desconocido. Alcanzar $100$-bit de seguridad $N$ necesito estar cerca $2000$-tamaño de bit y con esto $p,q$ y el tamaño del ciclo también aumenta
    • por $N=(2p_s p_b +1)\cdot (2 q_s q_b +1)$
      $ = (2 (2p_1p_2p_3+1) (6p_0+1)+1)\cdot (2 (2q_1q_2q_3+1) (6q_0+1)+1)$ [2]

      • $-$ solamente $O(\raíz cuadrada{C^3})$ (Hasta donde yo sé, es posible que me haya perdido algo en [2])
      • $+$ podría funcionar con $C^3 \aproximadamente 2^{200}$ (otra vez a menos que me perdí algo)
      • $+$ tamaño de $N$ se puede escalar con constante $C^3$
    • $-$ los valores necesitan mucho almacenamiento
    • $-$ tiene 4 estructuras disjuntas de este tipo (no todos los valores aleatorios se pueden conectar)
  5. Reflexión de geometría sobre campo finito (triángulos [1]tetraedro [2] – ambos sin solución) o más general una cadena de multiplicación de matrices. dejar que el $n$-vecindario que no crece demasiado rápido necesitan ser invariantes sobre el orden de su multiplicación. por lo que se pueden reducir a $A^iB^jC^k$ – pero hasta ahora no pude encontrar ninguna matriz de este tipo que también hiciera $i,j,j$ difícil de determinar

    • $-$ o demasiados $n$-vecinos o demasiado fáciles de calcular los índices

Pregunta: ¿Se puede hacer mejor? puede menos de $N=2^{200}$ los valores se distribuyan a lo largo de 3 dimensiones con un tamaño de ciclo de menos de $C=2^{65}$ cada uno mientras que encontrar la relación entre dos miembros toma al menos $2^{100}$ pasos de cálculo (en promedio)?
Para esto tiene que ser más difícil que $ O (\ raíz cuadrada {N}) $ (con $N<2^{200}$ y $C<2^{65}$)


Notas adicionales:

  • además de 3 direcciones en dirección hacia adelante, también es necesario que exista su inversa en dirección hacia atrás. Todos deberían tener aproximadamente el mismo tiempo de cálculo.
  • en el mejor de los casos, todos los valores aleatorios válidos pueden generar la misma estructura. Pero un pequeño ($<\aprox. 10$) también es posible un conjunto de estructuras similares disjuntas (como en 4.).
  • en caso de uso, se generará un valor inicial aleatorio y se gastará iterativamente con sus vecinos más cercanos (después de esto, los vecinos de los vecinos, etc.). Finalmente resultaron (después de un tiempo interminable de generación) en la misma estructura consistente (secreta). Debería ser lo más difícil posible priorizar cualquier dirección de progresión para alcanzar un determinado valor objetivo más rápido. Por lo tanto, generar solo puntos aleatorios no funcionará. Los siguientes valores generados siempre deben estar cerca de los que ya se han generado. Eso también significa generar la $i-$El siguiente valor no es necesario (como suele hacerse con generadores), un paso en una dirección es suficiente (como en AES/cifrado de bloque)
  • sin función de estiramiento como solo contar cada $n$-th miembro como válido (para aumentar la seguridad (mayor tamaño de miembro $N$) con tamaño de miembro verdadero constante $\frac{N}{n}$). Esto ya se usará. Debería, técnicamente hablando, ser posible (si alguien realmente lo quiere) generar un ciclo completo en una dirección en una PC estándar en una pequeña cantidad de años de CPU. Con esto, el tamaño del ciclo debe ser más pequeño que $2^{60}$. Pero encontrar la relación entre dos valores objetivo debería ser inviable en los próximos 50 años. Encontrarlo para algunas combinaciones está bien, incluso es bueno tenerlo. hasta donde yo sé sobre $2^{100}$ pasos de cálculo es un límite adecuado para esto.
  • un paso de cálculo significa cualquier tipo de operación básica (+-*/^) aplicada a dos valores $
  • esos miembros de la estructura pueden ser cualquier cosa como números, vectores, cadenas, matrices, incluso las imágenes de arte ascii funcionarían. Solo es necesario que haya alguna función para generar un valor pseudoaleatorio sin filtrar información relacionada con la seguridad. La generación de múltiples de ellos no debería revelar ninguna información sobre la relación entre ellos. Entonces algo como $g^r$ con un generador $g$ y $r$ el valor aleatorio no funcionaría. Generarlos no necesita ser tan rápido, $<20$sec en una PC estándar es suficiente.
  • en el caso de uso de destino, estos miembros servirán como semillas para los RNG. La estructura de esos miembros como un arreglo para esas semillas. Algunas secuencias de números aleatorios generadas por esos RNG serán mejores que otras. Si se han encontrado muy buenos de ellos, debería ser lo más difícil posible conectarlos (= calcular uno a partir del otro).
  • los adversarios serán iguales al usuario normal. Tiene acceso a todo el código fuente, variables de tiempo de ejecución, claves, variables, etc.
  • lo mejor que tengo hasta ahora es 4.[2] con $N=2^{200}$ y $C\aproximadamente 2^{66}$ a menos que me perdí algún problema de seguridad allí. Las publicaciones sobre esto también serían bienvenidas (en un hilo relacionado). Alternativas con menos almacenamiento necesario pero similares $N,C$ también son bienvenidos.
  • Además de las enumeradas aquí, también probé muchas más técnicas en los últimos 3 años (como autómata celular (sin inversa), teselado (no determinista o demasiado fácil de resolver), cifrado homomórfico (sin desbordamiento/ciclo, no funciona si todo en la PC adversaria) ). – Nada funcionó hasta ahora. Me encantaría cualquier idea que pudiera funcionar. Si te preocupa la recompensa, un método adecuado que sea mejor/más difícil que $ O (\ raíz cuadrada {N}) $ (con $N<2^{200}$ y $C<2^{65}$ obtendrá una recompensa extra. (O como espectáculo alternativo que no es posible). Si desea ayudar y publicar una respuesta (algo más larga) que usa cierta propiedad por seguridad, puede hacer un breve comentario primero si esta propiedad puede funcionar. Como hay tantas formas posibles de solución, es posible que haya pasado por alto algún requisito aquí.

0

¿Te ayudó la respuesta?

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

¿Qué son exactamente los valores personales?

Para variables aleatorias $X,Y$, mostrar $E[X E(Y | \mathscr{G}) ] = mi[E(X | \mathscr{G}) Y ]ps