Hibara

承诺 承诺分为三个步骤：承诺，打开承诺，验证承诺。 承诺：承诺:发送方将某个值xxx封装为yyy发送给接收方。(1)发送方不能修改信封中的值(绑定性);(2)接收方无法知道xxx(隐藏性)。 打开承诺:发送方揭露xxx。 校验承诺:接收方校验打开的值xxx与yyy中封装的xxx是否相同。 承诺一个值 承诺：选择xxx，计算y=f(x)y=f(x)y=f(x)，发送函数值yyy 打开承诺：发送原象xxx 校验承诺：函数一致性y=f(x)y=f(x)y=f(x) 对函数有一定要求： 函数求逆是 NP 困难的,需要指数时间暴力搜索。防止根据承诺值 y 计算 x。 但是校验简单,仅需要多项式时间计算复杂度。 该函数通常是哈希函数或 pedersen 承诺函数等。 承诺一个多项式 承诺：选择n+1n+1n+1个随机数a0,a1,...,ana_0,a_1,...,a_na0​,a1​,...,an​，构造多项式f(x)=Σi=0naixif(x)=\Sigma_{i=0}^na_ix^if(x)=Σi=0n​ai​xi，计算Ai=aiG, i=0,...,nA_i=a_iG,\ i ...

本文介绍图灵机，确定性多项式时间类和非确定性多项式时间问题。 图灵机 为了精确定义有效程序(即算法)这一概念，图灵构思了一种称为图灵机(Turing machine)的计算设备，把它作为一个计算原型，但却是非常通用的计算模型。这里要介绍的计算复杂性材料沿用了图灵机计算模型。下面介绍图灵机的个变型，这对我们学习计算复杂性的目的来说已经足够了。 在我们的变型里，图灵机由有限状态控制单元、k(≥1)条纸带( tape)以及同样数量的读写头( tapehead)组成。有限控制单元控制磁头读写纸带的操作，每个读写头访问一条纸带(称为它的纸带)，沿着纸带或左或右地移动完成这一操作。每一条纸带分成无限个单元(cell)。图灵机求解一个问题时,读写头扫描一个有有限个字符的串。该串从纸带最左边的单元开始按顺序存放在纸带上，每个字符占用一个单元,右边剩下的是空白(blank)单元，该串称为问题的一个输入。扫描从含有输入的纸带左端开始，同时图灵机赋一个初态( initial state）。任何时刻图灵机都只有一个读写头访问它的纸带。读写头对它的纸带的一次访问称为一个合法移动。 如果图灵机从初始状态开始， ...

本文介绍密码学中常用的一些符号和数学知识。 标准符号 #S\#S#S，集合SSS中的元素数目 FqF_qFq​，q个元素的有限域 desc(A)desc(A)desc(A)，代数结构A的描述 x←Dx\larr Dx←D，根据分布DDD进行赋值 x←USx\larr _USx←U​S，按SSS为均匀分布进行赋值 ord(x)ord(x)ord(x)，群元素的阶 <g><g><g>，由g生成的循环群 概率论和信息论 概率论和信息论是现代密码技术发展必不可少的工具。 现代密码系统，特别是公钥密码系统，对概率行为的要求已经达到相当苛刻的程度：语义安全性。 概率论的基本概念 令SSS为一个任意确定的点的集合,称之为概率空间(或样本空间)。任意元素x∈Sx\in Sx∈S称为样点(也称为结果、简单事件或不可分事件;为了简单我们将只用点)。一个事件(也称为合成事件或可分事件)是SSS的一个子集,通常用一个大写字母表示(比如EEE)。一次实验或观察是一种从SSS中产生(取出)一个点的动作。一个事件EEE的发生就是一个试验产生某个点x∈Sx\in Sx∈S,并满 ...

Provable Security 在密码学中，当我们已经设计出一个密码系统或协议时，我们不能直接说它是安全的，因为这样很缺乏信服力。可证明安全通常是用来确定一个密码系统或协议是安全的。 针对确定的安全目标，构造一个形式化的敌手模型及思维实验，利用概率论和计算复杂性理论，把敌手对密码算法或密码协议的攻击归约到对已知困难问题（大数分解，离散对数）的攻击。 目前对于安全性有两种角度的理解。 第一种称为“real vs random”，也就是如果加密所得的真实密文的概率分布，看起来和随机（均匀）选取一个密文一样，那么偷听者将无法从密文中获取信息。下面是形式化定义： 一个密码算法Σ\SigmaΣ有一次性的均匀分布的密文（one-time uniform ciphertexts），当且仅当 k←ΣKeyGenc←ΣEnc(k,m)return c=c←ΣCreturn ck\larr \Sigma KeyGen\\ c\larr \Sigma Enc(k,m)\\ return\ c\\ = c\larr \Sigma C\\ return\ c k←ΣKeyGenc←ΣEnc(k,m)re ...

本文将介绍差分隐私中和熵相关的概念。 Renyi Entropy 熵在密码学中有很多应用，比如说常见的香农熵和Hartley Function，它们都是由Renyi Entropy推广得到的： Hα(X)=11−αlog(Σi=1npiα), α≥0, α≠1H_{\alpha}(X)=\frac{1}{1-\alpha}log(\Sigma_{i=1}^np_i^{\alpha}),\ \alpha \ge0,\ \alpha\ne1 Hα​(X)=1−α1​log(Σi=1n​piα​), α≥0, α​=1 至于说Renyi Entropy是如何得到其他熵的？是不同的α\alphaα对应不同的熵 如果将ppp看成向量，括号里的形式实际上可以被看成向量的α\alphaα范数 Hα(X)=11−αlog(Σi=1npiα)=α1−αlog∥p∥αH_{\alpha}(X)=\frac{1}{1-\alpha}log(\Sigma_{i=1}^np_i^{\alpha})=\frac{\alpha}{1-\alpha}log\| p \| _{\alpha} Hα​(X)=1−α ...

今天的论文题目是《Private and Reliable Neural Network Inference》 论文地址：https://doi.org/10.1145/3548606.3560562 DPIS: An Enhanced Mechanism for Differentially Private SGD with Importance Sampling 摘要 如今，差分隐私（DP）已成为隐私保护的广泛认可标准，而深度神经网络（DNN）在机器学习领域取得了巨大成功。将这两种技术相结合，即具有差分隐私的深度学习，有望保护隐私地发布使用敏感数据（如医疗记录）训练的高效用模型。为此，经典的机制是 DP-SGD，它是一种用于 DNN 训练的差分隐私版本的随机梯度下降（SGD）优化器。随后的方法改进了模型训练过程的各个方面，包括噪声衰减时间表、模型架构、特征工程和超参数调整。然而，自原始 DP-SGD 算法以来，SGD 优化器中强制执行 DP 的核心机制一直未发生变化，这越来越成为限制 DP 合规机器学习解决方案性能的基本障碍。受此启发，我们提出了 DPIS，一种新颖的差分隐私S ...

Hash函数 Hash函数能将任意长度的输入变换为固定长度的输出且不可逆的单向密码体制。它的主要功能是数字签名和消息完整性检验。 原理 Hash函数是一个单向函数，从明文到密文的不可逆映射，只有加密过程，没有解密过程。 Hash函数可以将满足要求的任意长度的输入进行转换，从而得到固定输出，输出称为原消息的散列值（Hash Value）或消息摘要（Message Digest）。Hash的数学表达：h=H(m)h =H(m)h=H(m)，H是Hash函数，m是任意长度明文，h是固定长度的Hash值。 如果两个不同的消息x,x′x,x^\primex,x′，有H(x)=H(x′)H(x) =H(x^\prime)H(x)=H(x′)，则称发生了一个碰撞。 典型的Hash函数有两类：消息摘要算法（MD5）和安全散列算法（SHA）。 Hash函数的特点： 易计算：对于任意给定的消息，计算其Hash值比较容易。 单向性：对于给定的Hash值h，要找到m′m^\primem′使得H(m′)=hH(m^\prime) =hH(m′)=h在计算上 是不可行的，即求Hash的逆很困难。 抗碰撞性：理想 ...

本文介绍经典零只是证明协议——zk-SNARKs zk-SNARK 算法简介 zk-SNARK 是 zero-knowledge succint non-interactive arguments of knowledge 的简称，其中： 非交互指的是 Prover 和 Ver­i­fier 之间可以不进行任何的交互（P 和 V 来回发送消息） 零知识允许 Prover 向 Ver­i­fier 证明一项陈述为真，而不泄露除了该陈述为真以外的任何有效的信息（比如给定一个随机数的散列，Prover 可以向 Ver­i­fier 证明其知道这个随机数而不透露这个数） 简洁则意味着证明可以在短时间内完成（比如毫秒级别的时间），即便对于非常大的陈述而言证明也是非常快的，且不需要太多的通信量（仅需要几百字节） 因为以往的交互式证明系统中 P 和 V 需要互相发送消息，甚至为了降低合理性错误需要很多的交互轮次，从而导致通信量急剧增加，而非交互的简洁的结构中，P 可以仅向 V 发送一个包含少量自己的消息就可以完成验证，为了做到这种短到足以让其发布到区块链上的非交互式的证明，目前采用的方法是 P ...

盲签名 随着互联网的普及，为在线支付营造了丰沃的土壤，支付宝、微信支付与各大银行App纷纷登上在线支付的头把交椅。有的人甚至说“只需要一部手机就可以走遍天下”。但是，在线支付虽然便捷且交易的是一串数字但并不是电子现金，在线支付并不具备匿名性，容易追踪到某笔交易金额的来源和购买的商品，而电子现金具备匿名性，无法追踪电子现金来源。其中技术用到了假名、零知识证明、环签名、盲签名等等。 电子现金 电子现金(Electronic Cash)其实是一种用电子形式模拟现金的技术。电子现金系统企图在多方面为在线交易复制现金的特性：方便、费用低（或者没有交易费用）。不记名以及其他性质。但不是所有的电子现金系统都满足这些特点，多数电子现金系统都能为小额在线交易提供快捷与方便。 电子现金优于真实现金之处在于它安全、超距、迅速、低成本、匿名性、精确性等，这大大强化了现金的可移动性。电子现金通过信息网络系统和公共信息平台实现流通、存取、支付。在电子现金的支付中有三方参与：银行、用户、商家。 电子现金在线交易一般需要以下三个基本阶段： **取款阶段：**用户从自己的银行账户上提取数字现金 **支付阶段：**用 ...

同态加密GSW方案 本文将介绍同态加密中的一个方案——GSW，它利用近似特征向量技术，设计了无需计算密钥的全同态加密方案。原论文：《Homomorphic Encryption from Learning with Errors: Conceptually-Simpler, Asymptotically-Faster, Attribute-Based》 GSW整体思想 基本思想 矩阵有着这样的一个性质：一个矩阵CCC乘以vvv等于一个特征值乘以vvv，vvv是这个矩阵的特征向量，μ\muμ是特征值:C⋅v=μ⋅mod qC\cdot v =\mu \cdot mod \ qC⋅v=μ⋅mod q 那么，我们现在可以把CCC看作密文，vvv看作密钥，要加密的消息是μ\muμ: 很容易可以发现这个形式具有同态的性质：密文的加或乘相当于明文的加或者乘。 C1⋅v=μ1⋅v mod qC2⋅v=μ2⋅v mod qC1⋅C1⋅v=μ1⋅μ2⋅v mod qC_1\cdot v=\mu_1 \cdot v\ mod \ q \\ C_2\cdot v=\mu_2 \cdot v\ mod ...

markdown常用数学公式和符号 如何插入公式：行内公式(此时插入公式需要修改markdown配置文件，打开偏好设置中的内联公式) 1$数学公式$ 行间公式 123$$公式xxx$$ 常见公式和符号 希腊字母 显示 命令 显示 命令 α \alpha β \beta γ \gamma δ \delta ε \epsilon ζ \zeta η \eta θ \theta ι \iota κ \kappa λ \lambda μ \mu ν \nu ξ \xi π \pi ρ \rho σ \sigma τ \tau υ \upsilon φ \phi χ \chi ψ \psi ω \omega 矩阵 pmatrix ：小括号边框 bmatrix ：中括号边框 Bmatrix ：大括号边框 vmatrix ：单竖线边框 Vmatrix ：双竖线边框 横省略号：\cdots 竖省略号：\vdots 斜省略号：\ddots 不带括号的矩阵 1234567$ \begin{matrix
...

格密码学 Lattice-based cryptography，格密码学，是一种基于格（lattice）的密码学算法，目前是后量子密码学的重要候选方案，与 RSA、Diffie-Hellman 或椭圆曲线密码系统等更广泛使用和众所周知的公钥方案（理论上可以在量子计算机上使用肖尔算法击败这些方案）不同，一些基于格的构造似乎既能抵御经典计算机的攻击，也能抵御量子计算机的攻击。 关于格 传统公钥密码学的安全，往往建立在数学问题的困难性上，RSA基于大整数分解的困难性，Elgamal，ECC基于有限域上离散对数求解的困难性，这些难题均可使用量子计算机并应用秀尔算法破解。虽然大型量子计算机尚未普及，但是后量子密码学已经成为人们关注的焦点。格密码学是后量子密码学的代表之一。 格，是一种类似向量空间的数学空间，实数空间RRR上的向量空间VVV,是一些向量的集合，任意两个向量可以相加，任意一个向量可以和一个实数相乘，运算具有封闭性。在lattice中，与向量空间有所区别，具体来说，就是乘法中的乘数，从实数改为整数。如下图，是几种不同的格空间。 数学表示，给定nnn维实数空间RnR^nRn中的一组 ...

认证协议 认证这一概念可以分为三个子概念，数据源认证（验证消息的某个声称属性），实体认证（验证消息发送者所声称的身份），认证的密钥建立（产生一条安全信道，用于后继的应用层安全通话） 数据源认证 数据源认证涉及通信，是一种安全服务，消息接收者用它来验证消息是否来源于所声称的消息源，数据完整性不一定包含通信过程。其次，数据源认证必然涉及消息源的识别，数据完整性不一定涉及。数据源认证必然涉及确认消息的新鲜性。 我们可以将数据源认证这一概念的特征总结如下： 包含从某个声称的源(发送者)到接收者的消息传输过程,该接收者在接收时会验证消息。 接收方执行消息验证的目的在于确认消息发送者的身份。 接收方执行消息验证的目的还在于确认在原消息离开消息发送者之后的数据完整性。 验证的进一步目的在于确认消息传输的“活现性”。 实体认证 实体认证是一个通信过程，通过这个过程某个实体和另一个实体建立一种真实通信，并且第二主体声称的身份应该和第一主体所寻求的通信方一致。 根据协议主体的不同归类方法，在分布式系统中，实体认证可以分为若干类型，包括如下：主机-主机类型，用户-主机类型，进程-主机 ...

拜占庭将军问题（Byzantine Generals Problem），是由莱斯利·兰波特在其同名论文中提出的分布式对等网络通信容错问题。 在分布式计算中，不同的计算机通过通讯交换信息达成共识而按照同一套协作策略行动。但有时候，系统中的成员计算机可能出错而发送错误的信息，用于传递信息的通讯网络也可能导致信息损坏，使得网络中不同的成员关于全体协作的策略得出不同结论，从而破坏系统一致性。 在第t轮训练迭代中，一个诚实的参与者上传梯度： Δωi(t):=▽Fi(ωi(t))\Delta \omega _i ^{(t)}:=\bigtriangledown F_i(\omega_i^{(t)}) Δωi(t)​:=▽Fi​(ωi(t)​) 而一个恶意用户可能会上传任意值。 Δωi(t)={∗,malicious▽Fi(ωi(t)),otherwise\Delta \omega _i ^{(t)}= \begin {cases} *,malicious\\ \bigtriangledown F_i(\omega_i^{(t)}),otherwise \end {cases} Δωi(t)​ ...

数据完整性 我们需要一种机制，使得到消息的接收者可以验证该消息确实是来自所声称的消息源，且在传输的过程中未受到未授权方式修改。数据完整性就是抗击对消息未授权修改的安全服务。 定义 数据完整性保护 设Data为任意信息，KeKeKe未编码密钥，KvKvKv为与该编码密钥相匹配的验证密钥。Data的数据完整性保护如下：检测码的生成：MDC←f(Ke,Data)MDC\larr f(Ke,Data)MDC←f(Ke,Data) 检测码的验证： G(Kv,Data,MDC)={True,MDC=f(Ke,Data)False,MDC≠f(Ke,Data)G(Kv,Data,MDC)= \begin {cases} True,MDC=f(Ke,Data) \\ False ,MDC≠f(Ke,Data) \end {cases} G(Kv,Data,MDC)={True,MDC=f(Ke,Data)False,MDC​=f(Ke,Data)​ 其中f和g都是有效的密码变换：前者由一个辅助输入Ke参数化，后者由任意输入Kv参数化、 对称技术 在实现数据完整性的对称技术中，密码变换f和g是对称密码 ...