if $F\left(u,w\right)=y$, and $0$ otherwise.

A public verification computation scheme $VC$ must comply with the following properties of correctness, security, and efficiency:

-   Correctness: for any function $F$ and any inputs to $F$, if we run $\left(EK_{F},VK_{F}\right)\leftarrow\mbox{Keygen}\left(F,1^{\lambda}\right)$ and $\left(y,\pi_{y}\right)\leftarrow\mbox{Compute}\left(EK_{F},u,w\right)$ then we always get $\mbox{Verify}\left(VK_{F},u,w,y,\pi_{y}\right)=1$.

-   Efficiency: $\mbox{Keygen}$ is a one-time setup operation amortised over many calculations and $Verify$ is computationally cheaper than evaluating $F$.

-   Security: for any function $F$ and any probabilistic polynomial-time adversary $A$, we require that $$\mbox{Pr}\left[\left(\hat{u},\hat{w},\hat{y},\hat{\pi_{y}}\right)\leftarrow A\left(EK_{F},VK_{F}\right):F\left(\hat{u},\hat{w}\right)\neq\hat{y}\right]\leq\mbox{negl}\left(\lambda\right)$$ and $$1=\mbox{Verify}\left(VK_{F},\hat{u},\hat{w},\hat{y},\hat{\pi_{y}}\right)\leq\mbox{negl}\left(\lambda\right)$$ where $\mbox{negl}\left(\lambda\right)$ denotes a negligible function of inputs $\lambda$.

Additionally, we require the public verification computation scheme $VC$ to be succinct and zero-knowledge:

-   Succinctness: the generated proofs $\pi_{y}$ are of constant size, that is, irrespective of the size of the function $F$ and inputs $u$ and $w$.

-   Zero-knowledge: the verifier learns nothing about the prover’s input $w$ beyond the output of the computation.

Practical implementations are Pinocchio[@cryptoeprint:2013:279] and Geppeto[@cryptoeprint:2014:976], or Buffet[@cryptoeprint:2014:674] and Pequin[@pequin](a simplified version of Pepper[@Setty12makingargument]).

### Verifiable Validation of X.509 Certificates as Anonymous Credentials

The algorithm for certificate chain validation chain in section \[sub:X.509-Public-Key\] can be implemented with the public verifiable computation scheme of section \[sub:Verifiable-Computation\] using zk-SNARKS to obtain a verifiable computation 