coperlm's Blog

Beaver 三元组（Beaver triples）是安全多方计算（MPC）中一个超级聪明、实用的技巧，用来安全地做乘法 通俗类比：就好像你和朋友要乘两个私密数字，但你们提前准备了一个万能“乘法模板”，可以安全又正确地偷偷算出结果。 Motivation在安全多方计算里： 加法很容易做：每个人把自己数据碎片加一下就行。 但乘法就麻烦了，因为： 两个秘密数的乘积不能直接从碎片算 又不能暴露真实数值 所以需要巧妙地”绕过去“ Beaver 三元组应运而生 DefinationBeaver 三元组表示为： (a, b, c) \quad \text{where} \quad c = a \cdot b 所有参与方各自拿到这些数的“碎片”，但不知道完整的值。 它跟我们真正要计算的 $x \cdot y$ 没有关系，只是一个通用的乘法工具。 Algorithm假设两位参与方想计算： x \cdot y但每人都只知道自己的秘密（$x$ 或 $y$），又不想泄露给别人。 步骤如下： 每人拿到 $x$ 和 $y$ 的秘密共享，还有一个 Beaver 三元组 $(a,...

之前听师兄讲PCS（多项式承诺方案），听不懂一点，甚至有一次差点睡着（bushi 今天看Siniel，又遇到PCS了，故而通俗理解记录一下，也没时间看相关论文了~浅学一下，够用即可~~ Motivation：证明者有一个多项式 $p()$，验证者指定一个数 $z$ 来验证，通过承诺确保原多项式不会改变 这里，我们介绍 KZG。更具体的： KZG 方案是基于双线性对（bilinear pairing）和加法同态加密（homomorphic encryption）的密码学技术。它允许一个发送方承诺（commit）一个多项式，并稍后提供证明（proof），以便验证者确认多项式在某个点的值是否正确。 前置知识：双线性映射 设 $G_1,G_2$ 是两个循环群，阶为素数 $p$ 设 $e:G_1\times G_2\rightarrow G_T$，满足 $e(g^a,h^b)=e(g,h)^{ab}$ 对所有 $a,b\in\mathbb{Z}_p$ 成立，其中 $g,h$ 是群 $G_1$ 和 $G_2$ 的生成元 KGC的四个步骤：（对应图二） Setup（设置）：...

2025年2月21日周五晚这场牛客，掉大分了 A题快速切出来，后面就开始坐牢了（还好记得开ll了） B题憋了半天，感觉要开不止一对堆，然后一看榜C出的人多，就去看C了 然后C挂了两发，和21年csp-s差点ce的原因一样（ 当时是数组开到N，但是i也遍历到N 这次学聪明了，数据开到N+10，然后扫到N；结果忘了后面用到i+1了 然后挂了两发才发现 B题就有意思了，开了四个堆最终，调了好半天过样例了，结果一直WA 赛后找评论区的hack数据也找不出一点问题 最终对拍了下下，记录最大值的初始值是0，但是最大值有可能是负数··· 最终成绩 虽然没掉大分，不过这场也打得挺抽象的

...

本文用于记录牛客寒假赛的六场比赛的赛时解题和赛后补题 笔者水平：CF绿上蓝下 第一场 打红温了，头一次连打五个小时~ 题本身不难，就是实现上遇到比较多的障碍 A题签到题，如果没有1就输出1e9+7即可 D题也是直接模拟即可 G题排序后计算a[i]-i，就是每个点需要操作的次数了 B题一开始以为是有向图浪费了很多时间，树存在简单路径的充要条件是它是链 M题也属于思路很简单但是写起来比较困难的题 就拓扑排序一下，然后逐步拓展，取最优解即可 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071#include<iostream>#include<algorithm>#define int long longusing namespace std;const int N = 1e5;int n , a[N+10];struct...

由于后续CF比赛基本只参加VP，故特此记录一下 2025.01.17Codeforces Round 996 (Div. 2) 这把打爽了，表现分差点上紫，D题最后一分钟调出来过样例...

总结各种情况下的PPT如何制作 1. 组会汇报面向导师和同学，强调科研进展汇报和交流 格式要求： 中文字体：微软雅黑；英文字体：Times New...

今天阅读前置知识，搞了半天终于明白了IND-CCA2下的CP-ABE安全，记录一下 论文名称：Fine-Grained and Controlled Rewriting in Blockchains: Chameleon-Hashing Gone Attribute-Based 相关内容： 我们只看核心部分 我们大致划分为三个部分 第一部分，初始化，不再赘述 第二部分，攻击者交互阶段，攻击者$\mathcal{A}$选择任意属性集合$\mathbb{S}$进行请求，模拟器会这些请求的属性集合加入全局集合$S$，并生成与属性集合$\mathbb{S}$相对应的私钥$ssk$，将请求编号及生成的密钥记录到$Q$中 第三部分，挑战阶段，攻击者$\mathcal{A}$提供属性集合$A^{}$ （$A^{}\cap S=\emptyset$），模拟器随机选择$b\in{0,1}$，使用属性集合$A^*$对应的私钥加密$m_b$，将密文$c_b$提供给$\mathcal{A}$...

BST 二叉查找树 -> AVL 平衡二叉树 -> RBT 红黑树 二叉查找树 左子树上所有结点的值均小于或等于它的根结点的值 右子树上所有结点的值均大于或等于它的根结点的值 左、右子树也分别为二叉排序树 理想情况下是这样子 存在的问题：如果BST树的节点正好从大到小的插入，此时树的结构也类似于链表结构，这时候的查询或写入耗时与链表相同，最坏时间复杂为线性 这时候就有了平衡二叉树AVL（发明者名字简写） AVL也属于二叉搜索树的一种，与其不同的是AVL通过机制保证其自身的平衡 平衡二叉树 AVL树是最先发明的自平衡二叉查找树 在AVL树中任何节点的两个子树的高度最大差别为1，所以它也被称为高度平衡树 增加和删除可能需要通过一次或多次树旋转来重新平衡这个树 平衡二叉树的特性 对于任何一颗子树的root根结点而言，它的左子树任何节点的key一定比root小，而右子树任何节点的key...

241219阅读《Chameleon-Hashes with Ephemeral Trapdoors And Applications to Invisible Sanitizable Signatures》遇到了NIZKPoK，故学习一下 NIZKPoKNon-Interactive Zero-Knowledge Proof 非交互零知识证明 论文中的体现 \begin{align} &Generate\ \pi\leftarrow NIZKPoK\{(x):h=g^x\}\\ &if\ \pi\ is\ not\ valid, return\perp \end{align}解释证明着想要证明自己知道某个值$x$，而不透露$x$本身 Fiat-Shamir变换（简化的非交互证明） 初始化：$g$和$h$是公开的参数，$x$是秘密（证明者知道它） 生成证明：随机选择一个随机值$r$，计算承诺值$t=h*g^r$ 计算挑战：生成一个挑战$c$（通常通过哈希函数生成） 计算响应：计算...