0
$\begingroup$

All practical probabilistic proof/argument systems I know of are based upon polynomial identity testing in finite fields. These constructions include QAPs, STARKs, GKR and many variants. In particular, they all rely on the Schwartz-Zippel lemma, and thus they all take place in a polynomial setting.

There are constructions that do not take place in a polynomial setting, such as the expander-graph based PCP. But they are impractical both asymptotically and in practice.

Are there constructions that do not take place in a polynomial setting, but are still potentially practical?

$\endgroup$
0
$\begingroup$

You can look the Groth-Sahai proof system; Its practical and has been well studied and it's not reliable to The Schwarz-Zippel lemma. But it depends of the form of the equations you want to prove.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.