Moment Generationg Function Moment Generating Function “我们需要更多的特征来描述分布,例如峰度,偏度,除了常用的平均值,方差,这些特征统一称为矩,那么有没有一个函数能够计算所有矩呢?当然有,矩母函数,你就可以通过微分来计算各种矩,而不是从定义的积分算,你肯定知道微分比积分容易吧!” 「矩」(moment)的实际含义 物理意义 数学中矩的概念来自物理学。在物理学中,矩是表示距离和物理量乘积的物理量, 2024-05-13 #Probability theory
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 计算机基础 #基础知识