Average- and worst-case complexity Average Case Hardness(平均困难度) 平均情况下的困难度:随机选择参数,解决该问题的困难度。 密码学中要求的困难:随机选择一个key,没有敌手能在多项式时间内以不可忽略的概率破解该问题,即平均困难度 例如: 大整数分解问题,我们要求的并非是最难分解的N难以分解,而是按照我们的方式选择出来的N大部分都难以分解; 对于Ajtai的OWF问题,如果我们随机的抽取 \(\mathbf 2024-04-18 #Lattice
Minkowski定理 Minkowski Theorem Minkowski Theorem 1 若多面体 \(\mathrm{S}\) 的体积 \(\operatorname{Vol}(S)>\operatorname{Vol}(P)\), 则 \(\mathrm{S}\) 中必然存在两点 \(\mathrm{x}, \mathrm{y}\) 满足 \(x \neq y, x-y \in L\) 证明:首先, 2024-04-18 #Math, Lattice
关于Lipschitz的思考 关于Lipschitz的思考 今天在看TFHE论文的过程中,看到了 \(\kappa\)-Lipschitz的概念 The notion of Lipschitz function always refers to the \(\ell_{\infty}\)-distance: a function \(f: \mathbb{T}^m \rightarrow\) \(\mathbb{T}^n\) 2024-04-17 #Math
Interactive Proof Interactive Proof 在本篇笔记中,笔者参考CS294课程详细记录了交互式证明的定义、性能等并自行补充了一些内容,主要分为以下几个部分,读者可以根据自己需要进行判断 交互式证明的定义、GNI的交互式证明协议、\(\mathrm{P}\subseteq \mathrm{PSPACE}\) Sumcheck协议、\(\mathrm{co-NP}\subseteq \mathrm{IP 2024-02-11 #Complexity theory
GMR89:The knowledge complexity of interactive proof systems GMR89:The knowledge complexity of interactive proof systems 这篇博客有点头重脚轻的感觉,因为笔者觉得后面的很多定义没有必要重述,对于文章中的协议也没有进行重写,笔者的思考好像也在introduction都讲了,这篇文章感觉也是重在引入,因此在后面写的比较简略,只记录了相对比较重要的内容,大年初一属实是有点太累了😫,一会还想陪女朋友聊会天 2024-02-10 #Complexity Theory
Complexity class Complexity Class 在计算复杂度理论中,一个复杂度类指的是一群复杂度类似的问题的集合。一个典型的复杂度类的定义有以下形式: 可以被同一个抽象机器M使用O(f(n))的资源R所解决的问题的集合(n是输入资料的大小)。 L (Logarithm space class) L,也称为LSPACE或DLOGSPACE,是能被确定型图灵机利用对数空间解决的判定问题集合。 对数空间是指与输入 2024-02-09 #Computation Complexity
Why and How zk-SNARK Works Definitive Explanation Why and How zk-SNARK Works: Definitive Explanation Abstract 本篇论文对于zk- SNARK做了一个简单的阐述,不仅解释了它是如何工作的,更解释了它为什么如此工作和它如何变成这样。 1. Introduction 零知识简洁非交互式知识论证(Zero-knowledge succinct non-interactive arguments 2024-01-16 Zero Knowledge Proof #ZKP
LPCP和LIP LIP 在线性 IP (Linear IP, LIP) 模型中,Prover 和 Verifier 进行对话。但是,相比于 IP 模型,增加了一些限制条件:Prover 只能是线性的。 什么是线性的 Prover 呢? 首先, Verifier 发给 Prover 的消息只能是 \(\mathbb{F}^n\) 中的向量, 而 Prover 的消息只能是 Verifier 消息的线性函数。一个向 2023-12-23 Zero Knowledge Proof #ZKP
算术电路与布尔电路相互转换 布尔电路 to 算术电路 在\((\mathbb{F},+,\cdot)\)上考虑一个函数\(f\),该函数可以由大小为多项式的布尔电路在其输入大小上计算,例如,在标准基础\(\{ \mathsf{XOR},\mathsf{AND},\mathsf{NOT} \}\)。要在\(\mathbb {F}\)上模拟计算,请将\(0\)编码为\(0_ \mathbb {F}\)(在\(\mathbb {F 2023-12-21 计算机基础 #基础知识
KZG_polynomial_commitment_scheme Zero knowledge proofs have garnered an air of mystery around them, due to their mathematical complexity. They are affectionately referred to as “moon math,” as they are seen by most as otherworldly m 2023-12-18 Zero Knowledge Proof #ZKP