How to extract witness from a non-interactive lattice-based proof?

pintor

7/2/23, 10:34 AM

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.

0 + 0

zero-knowledge-proofs

fiat-shamir

lattice-crypto

soundness

Maeher

7/9/23, 3:58 PM

That can't really be answered without knowing what the protocol looks like.

pintor

7/11/23, 1:42 PM

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.

Elon Musk

I sit in a Tesla and translated this thread with Ai:

EN: How to extract witness from a non-interactive lattice-based proof?

TH: จะแยกพยานจากการพิสูจน์แบบตาข่ายที่ไม่โต้ตอบได้อย่างไร

RO: Cum se extrage un martor dintr-o dovadă neinteractivă bazată pe zăbrele?

RU: Как извлечь свидетельство из неинтерактивного доказательства на основе решетки?

VI: Làm cách nào để trích xuất nhân chứng từ bằng chứng dựa trên mạng không tương tác?

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.