Ist jemand über ein Papier informiert, das die "weniger clevere" Version von FRI formal analysiert, bei der die Abfragen unabhängig in jeder Schicht gewählt werden? (Auf Kosten von 2x in der Beweislänge).

Insbesondere die beiden Beispiele, die du für ein schlechtes Ergebnis gibst, sind meiner Meinung nach nicht problematisch - d.h. du musst nur fri erkennen, ob du *weit entfernt* von einem Codewort gestartet bist, ich denke, es ist dir egal, ob das Codewort gewechselt wurde oder ob du weit entfernt von einem Codewort geendet hast (was tatsächlich erkannt wird, da der Verifier das gesamte Wort in der letzten Schicht liest)

@GuilleAngeris Übrigens, ist die Annahme in diesem Papier, dass wir uns im UDR befinden?

@UHaboeck @GiacomoFenzi Meine Motivation war es, das Papier mit der kleinsten "Editierdistanz" zu korrigieren. Insbesondere wollte ich die schlechten Ereignisse beibehalten, bei denen das Falten die Distanz nicht verringert hat, anstatt das etwas komplexere schlechte Ereignis in MCA.

@UHaboeck @GiacomoFenzi Fix, weil es die fehlerhafte Analyse aus diesem Papier über Vorproximitätslücken verwendet hat.

@UHaboeck @GiacomoFenzi Das heißt, eines meiner Erkenntnisse von heute war, dass man für die unabhängige Abfrage FRI einfach mit "regulärem" CA analysieren kann, anstatt mit gewichtetem oder gegenseitigem. Aber ich habe das so schnell gemacht, dass ich vielleicht morgen demütig sein werde :)

@UHaboeck @GiacomoFenzi Und obendrauf musst du jedes Mal eine zufällige Schicht auswählen, um die beste Fehlergrenze zu überprüfen, anstatt alle Schichten abzufragen. Das hat mit (1-delta/t)^t zu tun, das größer ist als 1-delta für (mindestens einige Werte von) t>1

@aszepieniec *wir beide haben einen Tippfehler - es ist (1-1/r)^r und nicht (1-r)^r

@aszepieniec *Das erste `this` bezieht sich auf den obigen Tweet, und das zweite `this` auf den verlinkten Tweet :)

@aszepieniec Genauer gesagt scheint es, dass wir für den gegebenen Abstand delta die Erfolgswahrscheinlichkeit der unabhängigen Abfrage FRI mit e^{-delta} begrenzen können, während wir für das reguläre FRI 1-delta erhalten können, was z.B. um ~0.1 kleiner ist für delta=1/2