Arthur-Merlin protocol交互式知识证明系统

Arthur-Merlin protocol（以下简称AM）为交互式证明系统，其中Merlin为prover, Arthur为verifier。verifier公开投掷硬币（对prover也可见）来query prover，并对prover提供的proof进行验证来决定是否接受。

1. interactive proof system交互式证明系统

源自论文《Private coins versus public coins in interactive proof systems》：
交互式证明系统中的prover通常被认为具有无限的资源，verifier具有有限的资源。verifier通过抛硬币的方式query prover（有可能询问相同的问题），并对prover返回的结果（proof）进行验证测试，通过测试才认为prover的回答为正确的。
可把这个证明系统扩展为NP问题，其中verifer不需要抛硬币或询问问题，仅需要听（接收）及验证。
在交互式证明系统中，proof的正确性不是数学意义上的，而是概率意义上的，具有一个非零可忽略的错误概率。

可把verifier想象为具有随机数生成器的普通计算机，而将prover想象为具有无限算力的预言机。prover需回答verifier的询问，由verifier来判断prover的回答是否可信。

在论文《Private coins versus public coins in interactive proof systems》中，证明了verifier秘密抛硬币和公开抛硬币在交互式证明系统中的等价性。

2. MA（Arthur-Merlin protocol的1-message模式）

如上图所示，若在AM中仅有一次消息交互，则可称为该种情况下可称为MA，$MA\subseteq AM$。pover对$x$的proof $m$若为真，则verifier通过运行polynomial time test信服该proof的概率应不低于2/3，若proof为假，则信服该结果的概率应不高于1/3。

• if $x\in L$, then $\exists m$, $P{r}_r(V(m,r)=1)\ge \frac{2}{3}$,
• if $x\notin L$, then $\forall m$, $P{r}_r(V(m,r)=1)\le \frac{1}{3}$.

若并行运行以上流程$n$次，则有，对于$\forall n$:

• if $x\in L$, then $\exists m$, $P{r}_r(V(m,r)=1)\ge 1-\frac{1}{2^n}$,
• if $x\notin L$, then $\forall m$, $P{r}_r(V(m,r)=1)\le \frac{1}{2^n}$.

所以，综上对MA的perfect completeness表述可为：

• if $x\in L$, then $\exists m$, $P{r}_r(V(m,r)=1)=1$,
• if $x\notin L$, then $\forall m$, $P{r}_r(V(m,r)=1)\le \frac{1}{2}$.

参考资料：
[1] https://en.wikipedia.org/wiki/Arthur–Merlin_protocol
[2] 讲义：lect22-An Arthur-Merlin proof for the Hilbert’s Nullstellensatz
[3] 讲义：Lecture 17- Arthur-Merlin games, Zero-knowledge proofs
[4] 论文《Private coins versus public coins in interactive proof systems》