SCG/Avatar

Question: What are the refutation protocols that are available?

Classification

Alice claims

Bob provides problem, Alice solves

Alice provides problem, Bob solves

(Alice provides | Bob provides) (Alice solves Bob's problem| Bob solves Alice' problem)

Alice provides problem/secret sol., Bob solves

Bob provides problem/secret sol., Alice solves

Definitions

A domain Domain consists of the set of all problems, called Domain.Problems and the set of all solutions, called Domain.Solutions and a predicate called valid: (Domain.Problems, Domain.Solution)-> Boolean. There is also a function quality: (Domain.Problem, Domain.Solution)->[0,1]. In summary, Domain = (Problems,Solutions,valid,quality).

A claim C(D) for domain D consists of a set of problems in D.Problems, a quality q in [0,1] and a resource bound r in [0,1]. In summary, a claim C(D) is a triple: (problems,q,r).

Informally, the claim C(D) says that the claimant can take any problem in C(D).problems and calculate a solution of at least quality C(D).q using at most C(D).r resources.