Quantum Rewinding for Many-Round Protocols

Lattice bulletproofs and quantum rewinding are explored in multi-round protocols, presenting a novel algorithm and key results, including the post-quantum PoK of a SIS preimage. The text delves into classical PoK, soundness notions, and recursive extraction algorithms. The challenges in the quantum setting despite existing techniques are addressed within the context of quantum rewinding.

• Quantum
• Rewinding
• Multi-Round
• Protocols
• Lattice Bulletproofs

---

---

Please find below an Image/Link to download the presentation.

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.

You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.

Presentation Transcript

---

1. Quantum Rewinding for Many-Round Protocols Nick Spooner, University of Warwick TCC 2022, Chicago Joint work with Russell Lai and Giulio Malavolta

2. Lattice bulletproofs [BLNS20, AL21, ACK21] ? $ ? wide matrix ? Succinct PoK of SIS preimage: short ? such that ? = ?? ? ?(?,?,?) ?(?,?) ? $? ? ??+ ??? ?/2 ? ,????,???? ? = ???+ ?? ?/2 ? ? = ?? + ????+ ?2????= ? Recurse ? = log? times; total communication ?(log?)

3. Our main result Theorem. Lattice bulletproofs is a post-quantum PoK of a SIS preimage, assuming quantum hardness of RLWE (Prior reductions only for classical adversaries) 1. New soundness notions for multi-round protocols: recursive special soundness and last-round collapsing 2. We give a novel quantum rewinding algorithm for any protocol satisfying both properties 3. We show that lattice bulletproofs satisfies both properties, assuming QRLWE

4. Classical PoK: tree special soundness ? ?,? ? ?1 ?3 ?2 ,?1,?1 ,?2,?2 ,?3,?3 ?1 ?2 ?3

5. Classical recursive tree extraction algorithm ??1, ,?? 1: Run ?,? ? ?1, ,?? 1 *Choose ?(?) ?, run ?? If ??+1outputs fail , output fail Else repeat * until 2 more successes Return ?? 1= ?(?,?,?? ? ?1, ,??: Run ? ,?,? ? ?1, ,?? If accepting transcript, return ? ,?,? , else fail ?? ?(1) (1) ??+1 ? ?1, ,?? ?(2) (3)) 1,?? 2,?? ?(? 1) ??+1 ? ?1

6. ??1,,??1: Run ?,? ? ?1, ,?? 1 *Choose ?(?) ?, run ?? If ??+1outputs fail , output fail Else repeat * until 2 more successes Return ?? 1= ?(?,?,?? Analysis ?? (1) ??+1 ? ?1, ,?? ? Pr ? ???? (3)) 1,?? 2,?? ?(?), ,?(?)[ ? ?1, ,?? wins] ?(?1, ,?? 1) Pr ??1, ,?? 1 fail = ? ?1, ,?? 1 Pr ?? 1 + ? 2 ? Time ?? ? Time ??+1 = 3 ?[Time ??+1] ? = poly ? 3log ?= poly(?,?) ? ???? ?1

7. Why does this fail in the quantum setting? ? ??1, ,?? 1: Run ?,? ? ?1, ,?? 1 *Choose ?(?) ?, run ?? If ??+?outputs fail , output fail Else repeat * until 2 more successes Return ?? 1= ?(?,?,?? ?? (1) ??+1 ? ?1, ,?? (3)) 1,?? 2,?? By now we have powerful techniques for quantum rewinding [CMSZ21, LMS22, CCLY2?] why are they not already enough?

8. ??1,,??1: ?,? ? ?1, ,?? 1 1,?? If QRewindoutputs fail , output fail Return ?? 1= ?(?,?,?? ?? ?) 2,?? 3) QRewind(??+1 (?? (3)) 1,?? 2,?? Problem: Known QRewinds need ??+1 to be projective Usually this is achieved by running ??+1coherently This won t work here: ??+1 is only expected polytime

9. Fixed polytime extraction, classically; first attempt ??1, ,?? 1: ?,? ? ?1, ,?? 1 Repeat at most Choose ?(?) ?, run ?? ??+1,? Return ?? 1= ?(?,?,?? ??,? 1? times: ? ?1, ,?? (3)) 1,?? 2,?? Markov: ??,? succeeds w.p. ? ?? so need ? ? But running time is 1?log ?> 1?log ?

10. Fixed polytime extraction, classically ??1, ,?? 1: ?,? ? ?1, ,?? 1 Repeat at most Choose ?(?) ?, estimate ? = ?(?1, ,??) If ? ?(1 1,?? ??,? 100??? times: ? ?1, ,?? 1 10?), compute ?? ??+1,? 2,?? (3)) Return ?? 1= ?(?,?,?? Succeeds w.p. 1 2 ? ? succeeds w.p. ? ?1,? Running time ? 3log ? poly(?) = poly(?,?) ?

11. Quantum extractor via [CMSZ21] measure-and-repair ??1, ,?? 1: ?,? ? ?1, ,?? 1 Repeat at most Choose ?(?) ?, measure if ?(?1, ,??) ?(1 ? ??,? 100??? times: 1 10?) ?1, ,??projectively(*) If yes, measure ?? ??+1,? Repair?(?1, ,?? ?) to ? Return ?? 1= ?(?,?,?? (3)) 1,?? 2,?? Proof idea: (*) is comp. indistinguishable from measuring if ? ?1, ,?? (requires last-round collapsing to undetectably measure ??) ?

12. Thanks! ePrint 2022/889