2
$\begingroup$

I'm trying to figure out how to construct an extractor for a non-interactive lattice-based proof. Specifically, I'm curious about the Fiat-Shamir transform applied to a five-move interactive protocol. Can you please explain to me what strategy should be used? Or share a link to an article with examples (references to extractors for non-interactive three-move protocol are welcome as well). Thank you!

Update: If we have a 5-move interactive lattice-based protocol, can we do 2-types of rewinds? Say first we rewind the protocol to get X proofs with the different first and second challenges, then we rewind right before the second challenge to get Y proofs with the same first but different second challenge. Does it make sense in lattice-based settings? Is there any article that does it?

Update 2: I'll be happy to get a link to any article that explains an extractor for a non-interactive case (FS, 3 or 5 rounds sigma protocol) or a 5-round interactive one. Mostly I just want to understand how aborts affect extraction strategy, especially for 5-pass sigma-like protocols.

$\endgroup$
2
  • $\begingroup$ That can't really be answered without knowing what the protocol looks like. $\endgroup$
    – Maeher
    Commented Mar 9, 2022 at 15:58
  • $\begingroup$ I'm looking for any existing example just to see how soundness can be proven for multiple rounds, especially when we have 2 FS transforms. Not quite sure that ideas from the non-lattice world will work due to the aborts. If it helps, say it's a sigma-like protocol (e.g. shuffle proof or a 5-pass authentication scheme): commit - get 1st challenge - send the 1st answer - get the 2nd challenge - send the 2nd answer. Honestly, I'll be happy to get a link to any article that explains an extractor for a non-interactive case (FS, 3 or 5 rounds sigma protocol) or a 5-round interactive one. $\endgroup$
    – pintor
    Commented Mar 11, 2022 at 13:42

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.