¿Hay un candidato para una acción grupal unidireccional post-cuántica?

9

¿Existe una familia conocida de acciones grupales con un elemento designado
en el conjunto sobre el que se está actuando, donde se sabe cómo eficientemente

muestra (esencialmente uniforme) de los grupos, calcula las operaciones inversas, calcula las operaciones del grupo y calcula las acciones del grupo

y no existe un algoritmo cuántico eficiente conocido
para tener éxito con una probabilidad no despreciable en

dado como entradas el índice de una acción de grupo y el resultado de un elemento de grupo muestreado que actúa sobre el elemento designado, encuentra un elemento de grupo cuya acción sobre el elemento designado es la segunda entrada

?


Hasta donde sé, proporcionan las únicas construcciones conocidas de compromisos de ocultación estadística no interactivos en los que el conocimiento de una trampilla permite una equivocación eficiente e indetectable, una propiedad que es útil para protocolos de conocimiento cero y seguridad adaptativa.

Cualquier familia de homomorfismos grupales unidireccionales con las primeras tres propiedades (de la tercera y cuarta línea de esta publicación) se puede convertir en tal cosa haciendo que los dominios actúen en los codicios a través de , con los elementos de identidad como los elementos que se distinguen.una,sih(una)si

Se puede obtener una versión restringida del esquema de compromiso de Pedersen como un caso especial de aplicar la conversión anterior al homomorfismo exponencial grupal, cuya unidireccionalidad es equivalente a la dureza del problema del logaritmo discreto, aunque eso no es difícil para los algoritmos cuánticos. (Consulte el algoritmo de Shor y la sección de esa página sobre el logaritmo discreto).


fuente

Respuestas:

4

, hay una vieja propuesta para esto debido a Couveignes , que Rostovtsev y Stolbunov redescubrieron de forma independiente .

En ambos casos, el conjunto de curvas elípticas con un poco de anillo endomorphism común O se actúa sobre por el grupo de la clase ideal de O . La clave secreta es esencialmente una descripción de una isogenia a través de su ideal de núcleo, y la acción de un elemento de grupo [una] lleva una curva mi al codominio de dicha isogenia:

([una],mi)mi/ /una=mi/ /αunakerα.
Hay una buena interpretación gráfica de esta acción, que se describe (por ejemplo) en la Sección 14.1 deApuntes de clase de Luca De Feo . (¡También contienen más de los antecedentes necesarios para comprender esta construcción!)

Si bien es posible invertir la acción grupal resolviendo una instancia del problema de desplazamiento oculto, dando lugar a un ataque cuántico subexponencial , el sistema permanece intacto para tamaños de parámetros razonablemente grandes. Un problema mucho mayor es que estos esquemas son dolorosamente lentos en la práctica: incluso después de un esfuerzo considerable de optimización , un cálculo de la acción grupal todavía lleva minutos .

El problema del rendimiento ha sido abordado por una propuesta reciente llamada CSIDH al cambiar a curvas elípticas supersingulares, lo que mejora drásticamente la eficiencia mientras mantiene esencialmente la misma estructura subyacente. Todavía es lento en relación con esquemas pre-cuánticos comparables, así como con esquemas post-cuánticos incomparables, pero puede tener un lugar en un mundo post-cuántico debido a sus características únicas.

aaaaaaa
fuente