证明六级分数大于425
我们一提到零知识证明,首先想到的一定是阿里巴巴的故事,这个生动的小故事给我留下了深刻的印象:
经过学习我们知道,零知识证明是一种能力,这种能力能够让一方(the prover, 证明者)可以向另一方(the verifier, 证明者)证明他们知道值x,而无需传达任何信息,除了他们知道值x。零知识证明的本质是,通过简单地揭示信息来证明某人具有某些信息的知识是微不足道的。面临的挑战是在不透露信息本身或任何其他信息的情况下证明拥有这种财产。
根据零知识证明的定义可以得知零知识证明具有以下三个重要的性质:
- 完备性(
Completeness
):只要证明者拥有相应的知识,那么就能通过验证者的验证,即证明者有足够大的概率使验证者确信。; - 可靠性(
Soundness
):如果证明者没有相应的知识,则无法通过验证者的验证,即证明者欺骗验证者的概率可以忽略。 - 零知识性(
Zero-Knowledge
):证明者在交互过程中仅向验证者透露是否拥有相应知识的陈述,不会泄露任何关于知识的额外信息。
根据零知识证明的定义可以得知零知识证明具有以下三个重要的性质:
1.高效性:该过程计算量小,双方交换的信息量少。
2.安全性:其依赖于未解决的数学难题,如离散对数、大整数因子分解、平方根等。
3.许多零知识证明相关的技术避免了直接使用有政府限制的加密算法,这就给相关产品的出口带来了优势。
根据零知识证明的方式,可以分为交互式和非交互式。交互式一般是通过挑战响应的方式,非交互式一般通过承诺方案来实现。
符号简介
本人实在没有解决这个符号书写的问题,故在此说明一下符号的意义:
ECC曲线参数P: 大素数
ECC曲线参数G:基点
g:成绩
m:moe
id:i
成绩发布:
- 生成随机数m,计算$Q=(g+m)*G$,考生保存$mG$,因此,考生可以计算得到$(m+1)G,(m+2)G...(m+g)G$
- 使用MoE的私钥sk进行签名:$sig_by_m = signature_{sk}(cn_i||year||R)$
零知识证明:
假如此时正在面试,考官要求学生提供零知识证明CET6成绩超过425(如果没超过,就当考官没说)
- 考生向考官提供$sig_by_m$,考官通过验证平台或其他方式,使用MoE的公钥验证签名,得到$R=(g+m)*G$
- 考官发起挑战,要求学生提供$r=(g+k-425)*G$
- 如果学生成绩大于425,那么$g+k-425>k$,即学生可以提供$r'=(g+k-425)*G$,考官验证
$r==r'$ ,如果相等则通过验证。
合理性说明:
两个方案中都是利用成绩和随机数k做了一个计算链,同时允许考生知道其中的g个值,因为是单向函数,所以考生也只能提供这g个值。在零知识证明时,向考生请求g+k-425,那么考生的g必须大于425才能提供正确的值,因此可以实现正确性证明。
对此本人有一定的思路:
首先,正常的电路是审计(0,$2^n$)的电路,而本题中的425并不是2的幂次,因此我们需要通过相关数学原理设计出了将审查范围扩大到任意整数的电路结构。
定义两个数字Max、Min作为范围审查边界,由基本电路可知,我们可以证明0<x<$2^n$,如果我们将x替换为Max-x,x-Min,我们可以得出0 < Max – x <
针对普通电路来说,我们需要新增4个门:两个公共输入门,两个加法门。公共输入门代表两个范围值,加法门用来约束Max-x与x-Min。
之后根据基本审查电路原理,分别对a、b进行基本范围审查(n=64),需要注意的是,电路中门的数量必须是2的幂次,因此我们需要将后续的门全补为空门。至此,任意范围的审查电路构造完毕。简单来说,此电路的实现原理就是求出Max-x与x-Min,之后调用两次基本范围审查分别查验两值,以此达到任意范围审查的目的。