simulabilidad en línea recta

11

¿Algún organismo conoce alguna buena referencia para el significado de la simulabilidad en línea recta? Actualmente estoy profundamente inmerso en el marco de Universal Composability (UC) de Canetti, pero no puedo encontrar ninguna buena referencia para el significado de la simulabilidad en línea recta. Cualquier ayuda es apreciada.

cr.crypto-security Yasser Sobhdel
fuente

Respuestas:

10

Aquí, "línea recta" se contrasta con "rebobinado". Un simulador es "en línea recta" si no "rebobina" la parte para la que está haciendo la simulación.

Por ejemplo, en un protocolo de conocimiento cero, el simulador generalmente rebobina el "verificador". En el sentido de "línea recta", este rebobinado no ocurre.

La primera vez que vi el término "simulador en línea recta" en el artículo de Rafael Pass ( Sobre la negabilidad en la cadena de referencia común y los modelos aleatorios de Oracle. (CRYPTO'03) ) y M.Sc. tesis ( Variantes alternativas de pruebas de conocimiento cero ).

Editar: Encontré un artículo anterior: Conocimiento cero simultáneo: Reducción de la necesidad de restricciones de tiempo por Cynthia Dwork y Amit Sahai, que data de 1998. Para obtener más consejos, consulte el comentario de Alon Rosen a continuación.

MS Dousti
fuente
No conozco el término "simulador de línea recta", pero para mí eso "línea recta" contrasta con "ramificación", análogo a las lógicas temporales de tiempo lineal versus tiempo de ramificación y equivalencia de traza versus equivalencia de bisimulación (ramificación). ¿Hay algo de esto?
Dave Clarke el
Bueno, no lo creo. Encontré otra referencia que se ajusta a mi definición.
MS Dousti
La explicación de Sadeq es la misma que en cualquier contexto en el que he escuchado los términos utilizados. Aquí hay algunas notas de clase de NYU de una clase en Adv Crypto del año pasado que discuten el tema; en particular, vea la Reclamación 8.
Daniel Apon el
El determinismo suena como un posible sinónimo.
Dave Clarke el
55
Los usos anteriores del concepto de simulación de línea recta (aunque posiblemente no bajo esta terminología) se pueden encontrar en: (1) Ran Canetti, Oded Goldreich, Shafi Goldwasser, Silvio Micali: conocimiento cero reiniciable (resumen extendido). STOC 2000: 235-244, y (2) Ran Canetti, Marc Fischlin: Compromisos de composición universal. CRYPTO 2001: 19-40. La noción surge en la definición de UC, porque no es posible rebobinar el "entorno". Surgió anteriormente en un contexto diferente en conocimiento cero concurrente, donde un simulador de rebobinado puede tener problemas.
Alon Rosen
3

No existe una definición formal de lo que significa ser un simulador de línea recta. Es solo una idea intuitiva que se puede usar para describir cosas de manera informal. Soy muy escéptico acerca de si uno puede definir lo que significa no rebobinar una máquina. De hecho, rebobinar una máquina es en sí mismo un término informal. Lo que realmente queremos decir al rebobinar una máquina es que podemos explorar muchas rutas posibles de ejecución de una máquina desde un estado dado. Los argumentos formales se basan en la cantidad de ejecuciones que necesitamos explorar antes de poder obtener una trampilla o alguna otra información que necesitemos para continuar nuestra prueba.


fuente