Class Description
SKC: Statistical Knowledge Complexity
A hierarchy of generalizations of SZK, in which Arthur is allowed to gain some information from his interaction with Merlin.
Defined in [GP91].
There are several variants (which we only describe roughly), including:
- SKChint(k(n)): Hint sense. The simulator can reproduce Arthur's view of the protocol if given a hint string of size k(n).
- SKChint(k(n)): Strict oracle sense. The simulator can reproduce Arthur's view if allowed k(n) queries to an oracle O.
- SKCavg(k(n)): Average oracle sense. For each input, the expected number of queries the simulator makes to oracle O is at most k(n).
- SKCent(k(n)): Entropy sense. Defined in [ABV95]. For each input, the expectation (over Arthur's random coins) of -log(P) is at most k(n), where P is the probability that the view output by the simulator equals the view resulting from the actual protocol.
See also: PKC.
Linked From
No class.