|
Adaptive Special Soundness: Improved Knowledge Extraction by Adaptive Useful Challenge Sampling| title | Adaptive Special Soundness: Improved Knowledge Extraction by Adaptive Useful Challenge Sampling |
|---|
| start_date | 2024/04/02 |
|---|
| schedule | 11h |
|---|
| online | no |
|---|
| location_info | Salle 3071 |
|---|
| summary | Proving knowledge soundness of an interactive proof from scratch is often a challenging task. This has motivated the development of various special soundness frameworks which, in a nutshell, separate knowledge extractors into two parts: (1) an extractor to produce a set of accepting transcripts conforming to some structure; (2) a witness recovery algorithm to recover a witness from a set of transcripts with said structure. These frameworks take care of (1), so it suffices for a protocol designer to specify (2) which is often simple®.
However, special soundness fails to adequately capture guarantees provided by simple “probabilistic tests”, e.g., short random linear combinations as used in many lattice-based proof systems. In this talk, I will introduce (adaptive) special soundness, which captures many scenarios and discuss the rewinding-based knowledge extraction. Moreover, I will point out current limitations and open problems with regard to (adaptive) special soundness.
This talk is based on join work with Thomas Attema, Russell W. F. Lai, and Pavlo Yatsyna. |
|---|
| responsibles | Hamoudi |
|---|
Workflow history| from state (1) | to state | comment | date |
|---|
| submitted | published | | 2024/03/28 14:41 UTC |
| |
|