百科问答小站 logo
百科问答小站 font logo



如何构造一个数学例子来证明零知识证明可行? 第1页

  

user avatar   tony-zheng 网友的相关建议: 
      

1. 概念

零知识证明 zero-knowledge proofs,简写为 ZKPs,最初由 S.Goldwasser、S.Micali 及 C.Rackoff 在 1985 年的论文《互动证明系统的知识复杂性》提出,指的是证明者能够在不向验证者提供任何有用信息的情况下,使验证者相信某个论断是正确的。

2. 基于同态隐藏的零知识证明实现

用数学语言描述零知识证明的过程:
已知两个数 和 ,需要在不泄漏这两个数的前提下,证明 。(注:这只是零知识证明的一种场景)

要实现这一点,需要引入一个同态隐藏函数 ,该函数满足一下3个条件:

(1)知道 的值,无法反推 的值;

(2)如果 ,那么 ;

(3)根据 和 ,可以算出 ,比如: g

使用同态隐藏函数,则零知识证明过程为:

证明者把 和 告诉验证者,验证者算出 ,然后判断是否等于 。也就是说,把验证 转化成了验证 。

根据同态隐藏函数的3个条件,以上证明过程显然是成立的。

3. 同态隐藏的实现

3.1 数据基础

3.1.1 模 加法

模 加法,就是加完之后对 取模。比如( ):

x 0 1 2 3 4 5 6
(x+1)|mod 7 1 2 3 4 5 6 0

集合 称为有限群。集合中元素的个数,称为有限群的

3.1.2 模 乘法

模 乘法,就是相乘之再对 取模。比如( ):

x 0 1 2 3 4 5 6
(x*2)|mod 7 0 2 4 6 1 3 5

使集合 中每个元素对自身不对地做模 乘法,则有:

观察元素3和5,可以发现集合中每个元素都可以被生成出来。这种群称为循环群,元素3和5称为一个生成元。实际上,所有素数阶的有限群都是循环群。

3.2 函数构建

生成元 ,取,则 。

以下验证满足前面的3个条件:

(1)由于生成的元素是乱的,所以无法根据 反推出 。(在实际应用中,p通常是一个大素数,比如 量级的数,以目前计算机的计算能力,是没有办法算出完整的表的,术语叫离散对数难题);

(2)如果 ,那么 。这条是满足的,因为生成元的作用就是生成集合中的每一个元素,从表中的数据也可以看出来;

(3)根据 和 可以算出 。根据指数运算法则: 。

3.3 扩展

实际上,基于同态隐藏的ZKPs,不仅仅支持加法,也支持所有的“线性组合”,比如 :

【参考】
[1]稀土掘金 - 什么叫同态隐藏


—— 更多内容,请访问专栏:【隐私计算




  

相关话题

  阿拉伯文是从右往左写,那么阿拉伯人写数学算式的时候也是从右往左写吗? 
  如何客观评价丘成桐老师的学术贡献呢? 
  如何看待任正非说的「发展芯片光砸钱不行,还要砸物理学家数学家」? 
  已知若干个独立同分布的随机变量之积的分布,如何求单个随机变量的分布? 
  大家都这么关注韦神,谁能给学渣讲讲韦东奕研究了什么,用通俗易懂的语言给大家科普科普? 
  数学学来有什么用? 
  数学专业考研(数分高代)如何做笔记? 
  如何看待美国数学学会(AMS)即将在其旗下期刊进行数学论文双盲审? 
  超理论坛是个怎样的论坛? 
  根号 2 与根号 3 之和约等于 π,这是巧合,还是有什么特殊意义? 

前一个讨论
陕西一公司高管因家暴妻子被停职,具体情况如何?该男子将承担哪些责任?
下一个讨论
怎么评价徐小圆 una 自称多重人格并可以互相感知到各自的存在这件事?





© 2025-04-26 - tinynew.org. All Rights Reserved.
© 2025-04-26 - tinynew.org. 保留所有权利