QuSoft Seminar: Nick Spooner (Boston University)

Everyone is welcome to attend the online QuSoft seminar with Nick Spooner (Boston University), title: Post-Quantum Succinct Arguments. Please contact Jop Briet or Subhasree Patro if you like to join.
  • What Not a Seminar English Algorithms & Complexity Seminars
  • When 23-04-2021 from 16:00 to 17:00 (Europe/Amsterdam / UTC200)
  • Contact Name
  • Add event to calendar iCal

Everyone is welcome to attend the online QuSoft seminar with Nick Spooner (Boston University)

Title: Post-Quantum Succinct Arguments.

Abstract:
A succinct argument is a proof system for NP where the total communication is much smaller than the NP witness. Almost 30 years ago,
Kilian showed how to build succinct arguments sound against classical adversaries, under standard cryptographic assumptions. In this work, we show that the same construction is sound against quantum adversaries, under a standard post-quantum assumption. We achieve this by designing a new quantum rewinding procedure which achieves asymptotically optimal extraction guarantees. The procedure relies on a novel "state repair" algorithm, an "interleaved" variant of the Marriott-Watrous QMA amplification procedure.

Please contact Jop Briet or Subhasree Patro if you like to join.