Generando gráficos con automatismos triviales

Estoy revisando un modelo criptográfico. Para mostrar su insuficiencia, he diseñado un protocolo artificial basado en el isomorfismo gráfico.

Es "común" (¡pero controvertido!) Asumir la existencia de algoritmos BPP capaces de generar "instancias difíciles del problema del isomorfismo gráfico". (Junto con un testigo de isomorfismo).

En mi protocolo artificial, voy a asumir la existencia de tales algoritmos BPP, que satisfacen un requisito adicional:

• Deje que los gráficos generados sean y . Solo hay un testigo (permutación) que asigna a .$G_1$$G_2$$G_1$$G_2$

Esto implica que solo tiene automorfismos triviales . En otras palabras, estoy asumiendo la existencia de algún algoritmo BPP, que funciona de la siguiente manera:$G_1$

1. En la entrada , generar un gráfico -vertex , tal que tiene automorfismos solamente triviales.$1^n$$n$$G_1$
2. Elija una permutación aleatoria sobre y aplíquela en para obtener .$\pi$$[n]=\{1,2,\ldots,n\}$$G_1$$G_2$
3. Salida .$\langle G_1,G_2,\pi \rangle$

Asumiré que, en el Paso 1, se puede generar según sea necesario, y es una instancia difícil del problema del isomorfismo gráfico. (Por favor, interprete la palabra "duro" de forma natural; Abadi et al. Dan una definición formal . Véase también el documento de Impaliazzo y Levin ).$G_1$$\langle G_1,G_2 \rangle$

¿Es razonable mi suposición? ¿Alguien podría señalarme algunas referencias?

Al menos el primer enfoque ingenuo en el que uno podría pensar no funciona. El enfoque que tengo en mente es simplemente generar puramente al azar. Dado que casi todos los gráficos no tienen simetrías (es decir, la proporción de gráficos en n vértices sin automorfismos no triviales se aproxima a 1 como n → ∞ ), G 1 no tendrá automorfismos no triviales con alta probabilidad, que es lo que queremos. Sin embargo, la versión de caso promedio del isomorfismo gráfico, donde los gráficos se eligen uniformemente al azar, se puede resolver en tiempo lineal [BK], por lo que esto no genera una distribución de instancias difíciles.$G_1$$n$$n \to \infty$$G_1$

Pero un segundo enfoque ingenuo tiene posibilidades de funcionar: generar un gráfico regular aleatorio (de grado no constante, ya que el isomorfismo del gráfico de grado constante está en P). Esto tampoco tiene automorfismos no triviales con alta probabilidad [KSV], pero el resultado de Babai-Kucera no se aplica (como señalan en el documento). Evidentemente, demostrar que este es un generador invulnerable requiere algunas suposiciones, pero uno podría imaginarse probando incondicionalmente que el isomorfismo de gráfico regular en el caso promedio es tan difícil como el isomorfismo de gráfico en el peor de los casos, aunque no sé cuán probable es esto. (Tenga en cuenta que el isomorfismo gráfico en el peor de los casos es equivalente al isomorfismo gráfico en el peor de los casos).

[BK] Laszlo Babai, Ludik Kucera, etiquetado canónico de gráficos en tiempo promedio lineal . FOCS 1979, pp.39-46.

[KSV] Jeong Han Kim, Benny Sudakov y Van H. Vu. Sobre la asimetría de gráficos regulares aleatorios y gráficos aleatorios . Estructuras aleatorias y algoritmos, 21 (3-4): 216–224, 2002. También disponible aquí .