Blogs

negl 可忽视函数定义一个定义在自然数集上的非负函数 是可忽视的当且仅当对任意的正多项式 都存在一个自然数 使得对于任意的大于 的整数，满足 一个等价的定义： 如果对任意一个 满足 那么就是可忽视的 计算安全The Adeversarial indistinguishable experiment (计算安全实验)对于模式 实验 首先输入参数 攻击者 给出两个等长的明文 然后输出给加密算法 加密算法随机依据安全参数调用生成器 Gen 随机生成密钥 key 然后随机采样 加密 并把密文给到 输出一个 如果 那么 赢得这个实验，即 否则为0 计算安全定义如果上面的实验满足对于任意的PPT时间内的敌手，都有那么这个加密方式是满足 eav 不可区分的。 CPA 安全CPA安全实验 首先运行密钥生成器 Gen 生成一个密钥 key 攻击者有向加密器 Enc 加密长度为 神谕机访问权限，并且可以根据访问得到的明文-密文对决定输出一对消息 ，长度也是 的 加密算法随机生成一个bit，即随机采样 然后输出密文 给到 攻击者 ...

Definition It’s conjugate（共轭） function is . 注意，这里其实 在输入之后是固定的，是平移 取到距离最远的点 Property 永远是凸函数 if is convex and closed 如果 是凸的并且是可微的，那么$$f^*(y) x^{T} \nabla f(x^) - f(x^*) = x^{*T} y -$$

PRGBackground提出的背景是生成真随机函数的速度太慢了，如果通过CPU温度来生成真随机，那么不能满足加密的速度要求，进而提出一种伪随机方法，来通过比较短的随机种子生成更长的随机串 Definition定义一个多项式 和一个确定的多项式时间的算法 ，对于输入 ， 输出一个长度为 的字符串，如果算法 满足以下性质，那么就称 是满足 PRG 的： 拓展性(Expansion): 对于任意PPT时间范围内的区分器 ,都有一个可忽略函数 使得其中的 均匀且随机，是真随机，而 是独立采样的，注意区分器是看不到 的，也不能看到 具体是什么 但是你构造反证的时候，是能够知道G的特征的，并且需要依据G的特殊性构造 这不是扯淡，因为你只需要证明存在一个D就可以了 ——By Danny 这里的实验分两种情况: 如果是走前半边，那么就是随机等可能从 里面采样出一个 出来，然后传给 输出一个数给判别器。 后半边是随机从 里面采样出一个 ，传给判别器 。 判别器 输出 ...

堆的概念堆是满足一下性质的树： 堆中某个节点的值总是不大于或不小于其父节点的值 堆总是一棵完全二叉树 堆的分类根据堆的节点大小关系，分为大根堆和小根堆。大根堆中每个节点都比它的子节点大，小根堆则是每个节点都比它的两个子节点小 大根堆示意图 小根堆示意图 在数组中储存的下标特征在储存堆的时候，一个节点如果下标是 那么它的父节点的下标是 。左子节点的下标是 ，右子节点的下标是 。 堆的操作以下操作均以大根堆为例 堆的插入 每次把一个节点放到数组的最后 依次比较它和其父节点的值，如果父节点更小，那么使用 shift up 操作，把当前节点和父节点交换，然后向上递归 如果父节点已经比此时调整的调整节点大了，调整结束时间复杂度是 级别的。 堆的删除堆只支持删除堆顶端的元素 找到最后一个插入的元素 将最后一个元素和顶部的元素互换 向下递归调整进行 shift down 相关文章[[Leftist heap]]

Nonnegative Weighted sumsFinite sums , is convex is convex Infinite sums略 Composition with an affine mapping Affine mappingsholds convexity Pointwise Maximum is convexis convex Proof is simple. Compositions h,g are convex is convex in some conditions <!–TODO: finish convex conditions>

Jensen’s InequalityDefinitionInfinite points , , Exceptionif function is convex, then

次水平集和超水平集次水平集定义对于 的次水平集是 性质 是凸的 是凸的 但是反过来不成立 超水平集定义对于 的超水平集是 性质 是 concave 是 convex DefinitionDefine the epigraph of function as Property is convex is convex is convex is concave

Sublevel setsDefinitionif is convex is convex Superlevel setsDefinitionif is concave is convex

什么是Block Cipher依赖工作流（Mode of operation），加密定长明文的算法 常见的工作模式ECB 模式按照可加密的长度切分明文之后，直接进行加密因为该模式可能泄露明文之间的关系，可被选择明文攻击不应该使用 CBC 模式每次先把明文和一个随机生成的 做异或，然后放到函数 里面做加密，得到结果 使用 再输入 做加密得到下一段密文 优点 加密是基于概率的 如果函数 满足PRF 安全，那么CBC模式满足CPA安全，即豁免选择明文攻击 缺点 整个加密流程是串行（sequential）的，并且无法进行并行化 OFB 模式首先生成随机的串，经过 加密之后作为输入传给下一个 同时用作密钥给明文做异或操作。 优点 密钥生成的部分是可以预处理的，所以理论上可以更快 函数 不要求是可逆的（因为此时其实只需要正向运用 得到每一次的密文就可以了） 如果函数 是满足 PRF 的，那么加密算法满足 PCA 安全 CTR 模式首先生成一个串 ctr 然后依次使用 作为输入给 获得密钥对对应的明文进行加密 优点 如果函数 是满足 PRF...

m路搜索树定义一般定义：一棵 m 路搜索树, 它或者是一棵空树, 或者是满足如下性质的树： 根最多有 m 棵子树, 并具有如下的结构： 其中， 是指向子树的指针，； 是关键码，。 在子树 中所有的关键码都小于 ，且大于 ，。 在子树 中所有的关键码都大于 在子树 中的所有关键码都小于 子树 也是 路搜索树，