P Knows Secret s

Informally, P on public input x knows s if:

an extractor algorithm E s.t. EP (x) outputs s within expected polynomial time

EP(x): E can run P polynomial number of times on the same random tape,.

Remark: Extractor E has Black Box Access to P.

Let R be polynomial time testable. Let (x,s) e R.

E

Diapositive prÈcÈdente

Diapositive suivante

Revenir ý la premiËre diapositive

Afficher la version graphique