A proof system for NP satisfies post-quantum proof of knowledge property if the following holds: if for any quantum prover convincing the verifier, there exists an extractor that can extract the witness from the prover with probability negligibly close to the acceptance probability. First studied by the seminal work of Unruh [Eurocrypt'15], this notion has been adopted by follow-up works, most notably in the construction of proof quantum knowledge protocols for QMA.

The post-quantum proof of knowledge protocol constructed by Unruh suffered from the drawback that the prover's state is destroyed after the extractor extracts the witness. This is especially problematic if this protocol is composed with other protocols. A more desirable feature is that the prover's state essentially remains undisturbed even after extraction. 

We show how to achieve post-quantum proof of knowledge from quantum hardness of learning with errors. Our result satisfies the above desirable property. We also show how to extend our result to the concurrent composition setting. 

Joint work with Kai-Min Chung and Rolando L. La Placa.