simulabilidade linear

11

Alguém conhece alguma boa referência para o significado de simulabilidade em linha reta? Atualmente, estou profundamente dentro da estrutura de Canetti da Universal Composability (UC), mas não consigo encontrar nenhuma boa referência para o significado de simulabilidade em linha reta. Qualquer ajuda é apreciada.

cr.crypto-security Yasser Sobhdel
fonte

Respostas:

10

Aqui, "linha reta" é contrastada com "rebobinagem". Um simulador é "linear" se não "rebobinar" a parte para a qual está fazendo a simulação.

Por exemplo, em um protocolo de conhecimento zero, o simulador geralmente rebobina o "verificador". No sentido "linear", essa rebobinagem não ocorre.

Vi pela primeira vez o termo "simulador de linha reta" no artigo de Rafael Pass ( On Deniabililty in the Common Reference String e Random Oracle Models. (CRYPTO'03) ) e M.Sc. tese ( Variantes Alternativas das Provas de Conhecimento Zero ).

Edit: Encontrei um artigo anterior: Conhecimento Zero Simultâneo: Reduzindo a Necessidade de Restrições de Tempo por Cynthia Dwork e Amit Sahai, que remonta a 1998. Para mais dicas, consulte o comentário de Alon Rosen abaixo.

MS Dousti
fonte
Não conheço o termo "simulador de linha reta", mas para mim o termo "linha reta" contrasta com "ramificação", análogo às lógicas temporais de tempo linear versus tempo de ramificação e equivalência de traços vs equivalência de bisimulação (ramificação). Existe algo para isso?
Dave Clarke
Bem, acho que não. Encontrei outra referência que está de acordo com minha definição.
MS Dousti 14/11/2010
A explicação de Sadeq é a mesma de qualquer contexto em que ouvi os termos usados. Aqui estão algumas notas de aula da NYU de uma classe do Adv Crypto do ano passado que discutem o tópico; em particular, veja a reivindicação 8.
Daniel Apon 14/11/2010
Determinístico soa como um possível sinônimo.
Dave Clarke
5
Os usos anteriores do conceito de simulabilidade de linha reta (embora possivelmente não estejam de acordo com essa terminologia) podem ser encontrados em: (1) Ran Canetti, Oded Goldreich, Shafi Goldwasser, Silvio Micali: zero conhecimento redefinível (resumo estendido). STOC 2000: 235-244, e (2) Ran Canetti, Marc Fischlin: Compromissos Universalmente Compostos. CRYPTO 2001: 19-40. A noção surge na definição de UC, porque não é possível retroceder o "ambiente". Surgiu anteriormente em um contexto diferente no conhecimento zero simultâneo, onde um simulador de rebobinamento pode ter problemas.
Alon Rosen
3

Não existe uma definição formal do que significa ser um simulador de linha reta. É apenas uma ideia intuitiva que pode ser usada para descrever as coisas de maneira informal. Eu sou altamente cético quanto à possibilidade de definir o que significa não rebobinar uma máquina. De fato, rebobinar uma máquina é um termo informal! O que realmente queremos dizer com rebobinar uma máquina é que podemos explorar muitos caminhos possíveis de execução de uma máquina a partir de um determinado estado. Os argumentos formais são baseados no número de execuções que precisamos explorar antes de obtermos um alçapão ou alguma outra informação necessária para continuarmos nossa prova.


fonte