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

2023-10-09 15:59

本文主要是介绍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, M A ⊆ A M MA\subseteq AM MAAM。pover对 x x x的proof m m m若为真,则verifier通过运行polynomial time test信服该proof的概率应不低于2/3,若proof为假,则信服该结果的概率应不高于1/3。

  • if x ∈ L x\in L xL, then ∃ m \exist m m, P r r ( V ( m , r ) = 1 ) ≥ 2 3 Pr_r(V(m,r)=1)\geq \frac{2}{3} Prr(V(m,r)=1)32,
  • if x ∉ L x\notin L x/L, then ∀ m \forall m m, P r r ( V ( m , r ) = 1 ) ≤ 1 3 Pr_r(V(m,r)=1)\leq \frac{1}{3} Prr(V(m,r)=1)31.

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

  • if x ∈ L x\in L xL, then ∃ m \exist m m, P r r ( V ( m , r ) = 1 ) ≥ 1 − 1 2 n Pr_r(V(m,r)=1)\geq 1-\frac{1}{2^n} Prr(V(m,r)=1)12n1,
  • if x ∉ L x\notin L x/L, then ∀ m \forall m m, P r r ( V ( m , r ) = 1 ) ≤ 1 2 n Pr_r(V(m,r)=1)\leq \frac{1}{2^n} Prr(V(m,r)=1)2n1.

所以,综上对MA的perfect completeness表述可为:

  • if x ∈ L x\in L xL, then ∃ m \exist m m, P r r ( V ( m , r ) = 1 ) = 1 Pr_r(V(m,r)=1)=1 Prr(V(m,r)=1)=1,
  • if x ∉ L x\notin L x/L, then ∀ m \forall m m, P r r ( V ( m , r ) = 1 ) ≤ 1 2 Pr_r(V(m,r)=1)\leq \frac{1}{2} Prr(V(m,r)=1)21.

参考资料:
[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》

这篇关于Arthur-Merlin protocol交互式知识证明系统的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/173978

相关文章

windows系统上如何进行maven安装和配置方式

《windows系统上如何进行maven安装和配置方式》:本文主要介绍windows系统上如何进行maven安装和配置方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不... 目录1. Maven 简介2. maven的下载与安装2.1 下载 Maven2.2 Maven安装2.

使用Python实现Windows系统垃圾清理

《使用Python实现Windows系统垃圾清理》Windows自带的磁盘清理工具功能有限,无法深度清理各类垃圾文件,所以本文为大家介绍了如何使用Python+PyQt5开发一个Windows系统垃圾... 目录一、开发背景与工具概述1.1 为什么需要专业清理工具1.2 工具设计理念二、工具核心功能解析2.

Linux系统之stress-ng测压工具的使用

《Linux系统之stress-ng测压工具的使用》:本文主要介绍Linux系统之stress-ng测压工具的使用,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录一、理论1.stress工具简介与安装2.语法及参数3.具体安装二、实验1.运行8 cpu, 4 fo

ubuntu20.0.4系统中安装Anaconda的超详细图文教程

《ubuntu20.0.4系统中安装Anaconda的超详细图文教程》:本文主要介绍了在Ubuntu系统中如何下载和安装Anaconda,提供了两种方法,详细内容请阅读本文,希望能对你有所帮助... 本文介绍了在Ubuntu系统中如何下载和安装Anaconda。提供了两种方法,包括通过网页手动下载和使用wg

ubuntu系统使用官方操作命令升级Dify指南

《ubuntu系统使用官方操作命令升级Dify指南》Dify支持自动化执行、日志记录和结果管理,适用于数据处理、模型训练和部署等场景,今天我们就来看看ubuntu系统中使用官方操作命令升级Dify的方... Dify 是一个基于 docker 的工作流管理工具,旨在简化机器学习和数据科学领域的多步骤工作流。

使用Python和SQLAlchemy实现高效的邮件发送系统

《使用Python和SQLAlchemy实现高效的邮件发送系统》在现代Web应用中,邮件通知是不可或缺的功能之一,无论是订单确认、文件处理结果通知,还是系统告警,邮件都是最常用的通信方式之一,本文将详... 目录引言1. 需求分析2. 数据库设计2.1 User 表(存储用户信息)2.2 CustomerO

Linux系统调试之ltrace工具使用与调试过程

《Linux系统调试之ltrace工具使用与调试过程》:本文主要介绍Linux系统调试之ltrace工具使用与调试过程,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐... 目录一、ltrace 定义与作用二、ltrace 工作原理1. 劫持进程的 PLT/GOT 表2. 重定

Springboot实现推荐系统的协同过滤算法

《Springboot实现推荐系统的协同过滤算法》协同过滤算法是一种在推荐系统中广泛使用的算法,用于预测用户对物品(如商品、电影、音乐等)的偏好,从而实现个性化推荐,下面给大家介绍Springboot... 目录前言基本原理 算法分类 计算方法应用场景 代码实现 前言协同过滤算法(Collaborativ

Windows系统宽带限制如何解除?

《Windows系统宽带限制如何解除?》有不少用户反映电脑网速慢得情况,可能是宽带速度被限制的原因,只需解除限制即可,具体该如何操作呢?本文就跟大家一起来看看Windows系统解除网络限制的操作方法吧... 有不少用户反映电脑网速慢得情况,可能是宽带速度被限制的原因,只需解除限制即可,具体该如何操作呢?本文

CentOS和Ubuntu系统使用shell脚本创建用户和设置密码

《CentOS和Ubuntu系统使用shell脚本创建用户和设置密码》在Linux系统中,你可以使用useradd命令来创建新用户,使用echo和chpasswd命令来设置密码,本文写了一个shell... 在linux系统中,你可以使用useradd命令来创建新用户,使用echo和chpasswd命令来设