Hibara

今天的论文题目是《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是对称密码 ...

比特安全性 关于基本的和通用的公钥密码函数比特安全性的实际结果意味着，只要明文消息是随机的，那么恢复有关明文的任何消息的问题就同这些基本函数求逆一样困难，这是因为后者是恢复整个明文消息的问题。 RSA比特 如果一条RSA密文是对不包含事前可猜测的信息进行的加密，那么从密文中提取一比特的明文信息就同提取整个明文组一样困难。

本文将介绍差分隐私及其相关概念。 差分隐私的承诺 一个有趣的例子： 医学数据库可能会告诉我们，吸烟会导致癌症，影响保险公司对吸烟者长期医疗费用的看法。吸烟者受到分析的伤害了吗？如果保险公司知道他吸烟，他的保险费可能会上涨。他可能也会得到帮助。但保险公司学习他的健康风险，使他进入戒烟计划。吸烟者的隐私被侵犯了吗？当然，研究结束后对他的了解比以前更多，但他的信息是不是“泄露”了？差分隐私将认为它不是，理由是对吸烟者的影响是相同的独立于他是否在研究中。是这项研究得出的结论影响了吸烟者，而不是他在数据集中的存在与否影响了实验得出的结论。 差分隐私解决了一个问题，即分析人员通过数据集学习整体信息的同时（趋势、统计信息），无法获取个人的详细信息。 对于给定的计算任务 TTT和给定的ε\varepsilonε值，将有许多不同的私有算法以ε\varepsilonε方式实现TTT。有些算法会比其他算法更准确。当ε\varepsilonε很小时，很难为任务TTT找到一个高精度的ε\varepsilonε-差分隐私算法，就像为一个特定的计算任务找到一个数值稳定的算法一样。 隐私保护的数据分析 数据不能完 ...

同态加密 同态加密（Homomorphic Encryption）是一种特殊的加密方法，允许对密文进行处理得到仍然是加密的结果。即对密文直接进行处理，跟对明文进行处理后再对处理结果加密，得到的结果相同。从抽象代数的角度讲，保持了同态性。 本文，我们先回顾传统的加密方式，再介绍几种典型的同态加密 传统的加密方式 构建一个加密系统，往往需要一个密钥（key），通过这个密钥，我们可以把明文的信息加密成密文，然后通过密钥再把密文变回原来的样子。所有的加密系统，无疑是做了三件事： KeyGen(1λ)KeyGen(1^ \lambda)KeyGen(1λ) 来随机生成一对加密和解密的密钥（EncKey,DecKeyEnc_{Key},Dec_{Key}EncKey​,DecKey​） 加密方通过加密密钥EncKeyEnc_{Key}EncKey​和加密算法EncryptionEncryptionEncryption来加密明文plaintextplaintextplaintext，得到密文ciphertestciphertestciphertest 解密方通过解密密钥DecKeyD ...

区块链基础 区块链究竟是什么？狭义地说，区块链就是比特币的底层技术；不过，经过7年的发展，区块链已经不再“依附于”比特币，而是独立地发展成为了一种革命性的技术，比特币则是区块链最大、最成功的应用。 从技术层面来看，区块链是一个基于共识机制、去中心化的公开数据库。共识机制是指在分布式系统中保证数据一致性的算法；去中心化是指参与区块链的所有节点都是权力对等的，没有高低之分，同时也指所有人都可以平等自由地参与区块链网络，唯一的限制就是个人自己的选择；公开数据库则意味着所有人都可以看到过往的区块和交易，这也保证了无法造假和改写。基于以上特性，可以总结得出：区块链由许多对等的节点组成，通过共识算法保证区块数据和交易数据的一致性，从而形成一个统一的分布式账本。 从价值层面来看，区块链是一个价值互联网，用于传递价值。目前的互联网仅用来传递消息，但是还不能可靠地传递价值；而比特币区块链却可以在全球范围内自由地传递比特币，并且能够保证不被双花、不被冒用。从这个角度来说，区块链是记录价值、传递消息和价值本身转移的一个可信账本。 以区块链技术为核心的系统包括如下四大最主要的特点。 Distributed ...

加密-非对称技术 在公钥密码体制中，加密不用密钥，密钥仅在解密阶段使用，Diffie和Hellman描述了几个可能用来实现公钥密码的数学变换，它们称之为单向陷门函数。 单向陷门函数 单向陷门函数 ft(x):D→Rf_t(x):D\rarr Rft​(x):D→R，是一个单向函数，即对任意的 x∈Dx\in Dx∈D，容易计算，而对几乎所有的 x∈Dx\in Dx∈D，求逆困难，但是如果知道陷门信息 ttt ，则对所有的 y∈Ry \in Ry∈R，容易计算满足 y=ft(x)y=f_t(x)y=ft​(x) 的 x∈Dx\in Dx∈D。 Diffie-Hellman密钥交换协议 与对称密码体制相比，公钥密码体制的一个显著优点就是远程通信各方无需安全信道就能实现相互交换密钥。最早实现这一点的方案是Diffie-Hellman指数密钥交换协议。 首先，假设用户Alice和Bob约定有限域FqF_qFq​和元素 g∈Fpg\in F_pg∈Fp​，g生成一个群。为简化，我们考虑有限域 FpF_pFp​，p为素数。协议如下： 协议：Diffie-Hellman密钥交换协议 共同输入 ( ...