simulabilité en ligne droite

11

Un organisme connaît-il une bonne référence pour la signification de la simulabilité linéaire? Je suis actuellement profondément dans le cadre de la composabilité universelle (UC) de Canetti, mais je ne trouve aucune bonne référence pour le sens de la simulabilité en ligne droite. Toute aide est appréciée.

cr.crypto-security Yasser Sobhdel
la source

Réponses:

10

Ici, la "ligne droite" contraste avec le "rembobinage". Un simulateur est "en ligne droite" s'il ne "rembobine" pas la partie pour laquelle il fait la simulation.

Par exemple, dans un protocole à connaissance zéro, le simulateur rembobine généralement le "vérificateur". Dans le sens "linéaire", ce rembobinage ne se produit pas.

J'ai vu pour la première fois le terme "simulateur en ligne droite" dans l'article de Rafael Pass ( On Deniabililty in the Common Reference String and Random Oracle Models. (CRYPTO'03) ) et M.Sc. thèse ( Variantes alternatives de preuves de connaissances nulles ).

Edit: J'ai trouvé un article antérieur: Concurrent Zero-Knowledge: Reducing the Need for Timing Constraints de Cynthia Dwork et Amit Sahai, qui remonte à 1998. Pour plus de pointeurs, voir le commentaire d'Alon Rosen ci-dessous.

MS Dousti
la source
Je ne connais pas le terme "simulateur en ligne droite", mais pour moi, cela signifie que "ligne droite" contraste avec "ramification", analogue à la logique temporelle linéaire-temps vs ramification-temps et l'équivalence de trace vs équivalence de bisimulation (ramification). Y a-t-il quelque chose à cela?
Dave Clarke
Eh bien, je ne pense pas. J'ai trouvé une autre référence qui correspond à ma définition.
MS Dousti
L'explication de Sadeq est la même que dans tout contexte dans lequel j'ai entendu les termes utilisés. Voici quelques notes de cours de NYU d'une classe d'Adv Crypto de l'année dernière qui discutent du sujet; en particulier, voir la revendication 8.
Daniel Apon
Des sons déterministes comme un possible synonyme.
Dave Clarke
5
Des utilisations antérieures du concept de simulabilité en ligne droite (bien que ce ne soit peut-être pas dans cette terminologie) peuvent être trouvées dans: (1) Ran Canetti, Oded Goldreich, Shafi Goldwasser, Silvio Micali: Réinitialiser la connaissance zéro (résumé étendu). STOC 2000: 235-244, et (2) Ran Canetti, Marc Fischlin: Engagements universellement composables. CRYPTO 2001: 19-40. La notion revient dans la définition de l'UC, car il n'est pas possible de rembobiner «l'environnement». Il est apparu plus tôt dans un contexte différent dans la connaissance zéro simultanée, où un simulateur de rembobinage peut rencontrer des problèmes.
Alon Rosen
3

Il n'y a pas de définition formelle de ce que signifie être un simulateur de ligne droite. Ce n'est qu'une idée intuitive qui peut être utilisée pour décrire les choses de manière informelle. Je suis très sceptique quant à savoir si l'on peut même définir ce que signifie ne pas rembobiner une machine. En effet, le rembobinage d' une machine est en soi un terme informel! Ce que nous voulons vraiment dire par rembobinage d'une machine, c'est que nous pouvons explorer de nombreux chemins possibles d'exécution d'une machine à partir d'un état donné. Les arguments formels sont ensuite basés sur le nombre de ces exécutions que nous devons explorer avant de pouvoir obtenir une trappe ou d'autres informations dont nous avons besoin pour continuer notre preuve.


la source