Hibara

群上的离散对数问题：给定群GGG的生成元ggg和GGG中的随即元素hhh，计算log⁡gh\log _ghlogg​h。这个问题在许多群中都被认为是困难的，称其为离散对数假设。 令GroupGen是一个多项式时间算法，其输入为安全参数K\mathcal{K}K，输出为一个阶等于qqq的循环群GGG的描述，以及一个生成元g∈Gg\in Gg∈G，它的离散对数假设定义如下： GroupGen的离散对数问题是困难的，如果对于所有的PPT算法AAA，下式是可忽略的 Pr[(G,g)←GroupGen(K);h←RG;x←A(G,g,h)],st gx=hPr[(G,g)\larr GroupGen(\mathcal{K});h\larr _RG;x\larr \mathcal{A}(G,g,h)],st\ g^x=h Pr[(G,g)←GroupGen(K);h←R​G;x←A(G,g,h)],st gx=h 如果GroupGen的离散对数是困难的，且G是一个有GroupGen输出的群，则称离散对数问题在G中是困难的。 ElGamal加密算法是IND-CPA安全的， 密钥产生过程： KenG ...

公钥加密方案在选择明文攻击（Chosen Plaintext Attack，CPA）下的IDA（Indistinguishability）游戏称为IND-CPA游戏如下： （1） 初始化。挑战者产生系统Π\mathcal{\Pi}Π，敌手A\mathcal {A}A获得系统的公开钥。 （2） 敌手产生明文消息，得到系统加密后的密文（可多项式有界次）。 （3） 挑战。敌手输出出两个长度相同的消息M0M_0M0​和M1M_1M1​。挑战者随机选择β←R{0,1}\beta \larr _R\{0,1\}β←R​{0,1}，将MβM_{\beta}Mβ​加密，并将密文C∗C^*C∗（称为目标密文）给敌手。 （4） 猜测。敌手输出β′\beta^{\prime}β′，如果β=β′\beta=\beta^{\prime}β=β′，则敌手攻击成功。 敌手的优势可定义为参数K\mathcal{K}K的函数： AdvΠ,ACPA(K)=∣Pr[β′=β]−12∣Adv_{\mathcal{\Pi},\mathcal{A}}^{CPA}(\mathcal{K})=|Pr[\beta^{\prime}= ...

本文将翻译Fuchun Guo老师所编写的Introduction to Security Reduction一书，本书主要讲述密码学协议是如何构造一个安全性证明的。 Introduction to Security Reduction https://doi.org/10.1007/978-3-319-93049-7 Preface 安全还原（原文是security reduction，也可以说是安全性降低）是证明公钥密码学安全性的一种非常流行的方法。粗略地说，通过安全还原，我们可以证明破解一个方案就像解决一个数学难题一样困难。然而，如何利用对手的自适应攻击来编制正确的安全还原是相当复杂的。原因在于，并不存在适用于所有建议方案的通用安全还原。 密码学研究论文中给出的安全还原通常很难被初学者完全理解。为了帮助初学者，一些密码学教科书用较简单的例子说明了如何正确编制安全还原程序。不过，研究论文和以往教科书中提到的安全还原通常是针对特定方案的。不同方案的安全还原不同，导致初学者无所适从。我们需要一本系统介绍如何为密码系统（而非特定方案）正确编写安全还原程序的书籍。有鉴于此，我们编写了这本 ...

什么是openSSL OpenSSL 是一个开源的安全套接字层密码库，提供了各种密码和加密算法的实现。OpenSSL 头文件是用于在 C/C++ 代码中访问 OpenSSL 库功能的接口定义。 下面介绍一些常用的 OpenSSL 头文件： <openssl/ssl.h>：包含与 SSL/TLS 协议相关的函数和数据结构的声明，用于实现安全的网络通信。 <openssl/evp.h>：包含对称加密算法和哈希算法的函数和数据结构的声明，用于实现数据的加密、解密和摘要计算。 <openssl/rsa.h>：包含 RSA 加密算法的函数和数据结构的声明，用于实现 RSA 密钥的生成、加密和解密。 <openssl/dh.h>：包含 Diffie-Hellman 密钥交换算法的函数和数据结构的声明，用于实现 DH 密钥的生成和共享密钥的计算。 <openssl/x509.h>：包含 X.509 数字证书和公钥基础设施（PKI）相关的函数和数据结构的声明，用于实现证书的读取、验证和操作。 <openssl/bio.h>： ...

公认的区块链1.0的最好的书，在线阅读Mastering Bitcoin 介绍 什么是比特币 比特币是由一系列概念和技术作为基础构建的数字货币生态系统。 比特币可以做传统货币能做的所有事，例如买卖商品、给个人或组织汇款、贷款。用户可以在专门的交易所里买卖比特币或兑换其他货币。 不同于传统货币，比特币是完全虚拟的。用户只要有证明其控制权的密钥，用密钥解锁，就可以发送比特币。这些密钥通常存储在计算机的数字钱包里。 比特币是通过“挖矿”产生的，挖矿就是验证比特币交易的同时参与竞赛来解决一个数学问题。任何参与者（比如运行一个完整协议栈的人）都可以做矿工，用他们的电脑算力来验证和记录交易。 比特币协议还规定，每四年新币的开采量减半，同时限制比特币的最终开采总量为2,100万枚。这样，流通中的比特币数量非常接近一条曲线，并将在2140年比特币将达到2,100万枚。由于比特币的开采速度随时间递减，从长期来看，比特币是一种通货紧缩货币。 比特币的构成： 去中心化的点对点网络 公共的交易账簿 去中心化的数学的和确定性的货币发行 去中心化的交易验证系统 比特币发展史 2008年，一个化名为中本聪的人 ...

横向联邦学习的定义 横向联邦学习也称为按样本划分的联邦学习（Sample-Partitioned Federated Learning 或 Example-Partitioned Federated Learning），可以应用于联邦学习的各个参与方的数据集有相同的特征空间和不同的样本空间的场景，类似于在表格视图中对数据进行水平划分的情况。事实上，横向一词来源于术语 横向划分（horizontal partition）。“横向划分” 广泛用于传统的以表格形式展示数据库记录内容的场景，例如表格中的记录按照行被横向划分为不同的组，且每行都包含完整的数据特征。我们将横向联邦学习的条件总结为： xi=xj,yi=yj,Ii≠Ij,∀Di,Dj,i≠jx_i=x_j,y_i=y_j,I_i\ne I_j,\forall D_i,D_j,i\ne j xi​=xj​,yi​=yj​,Ii​​=Ij​,∀Di​,Dj​,i​=j Di,DjD_i,D_jDi​,Dj​表示第i方和第j方拥有的数据集。我们假设两方的数据特征空间和标签空间对，即(xi,yi),(xj,yj)(x_i,y_i),( ...

分布式机器学习介绍 分布式机器学习也称为分布式学习，是指利用多个计算节点（也可称为工作者，worker）进行机器学习或者深度学习的算法和系统，旨在提高性能，保护隐私，并可扩展至更大规模的训练数据和更大的模型。如图所示。训练数据被分为不相交的数据分片并被发送给各个工作者，工作者将在本地执行随机梯度下降（Stochastic Gradient Descent，SGD）。工作者将梯度∇Wi\nabla W^i∇Wi或者模型参数WiW^iWi发送至服务器。参数服务器对收到的梯度或者模型参数进行聚合，从而得到全局梯度∇W\nabla W∇W或全局模型参数WWW。 面向扩展性的DML 大规模机器学习 在大数据时代，ML面临的主要问题是如何处理大规模的高纬度数据集，随着大趋势的变化，ML社区正面临着计算性能和好事与数据规模不匹配的挑战，这使得大规模的训练样本中耗费合理的计算代价和时间进行学习变得愈加不可能。 内存短缺 传统ML方法只在一块独立内存中对训练样本进行所有的操作，因此，可能出现：训练模型可能不能收敛或性能低下（低准确率和召回率）。 不合理的训练时间 ML算法中的一些优化过程可能不能匹 ...

面向隐私保护的机器学习 不断发生的数据泄露和隐私侵权事件使得社会公众更加认识到，在人工智能系统的构建与使用中，需要保护用户隐私和数据机密性，由此产生的系统便称作面向隐私保护的机器学习（Privacy-Preserving Machine Learning，PPML）系统。 我们对于信息安全有如下定义：由个人，团体或机构自行决定何时，如何以及在多大程度上将有关他们的信息传达给他人。 面向隐私保护的机器学习与安全机器学习 我们首先要分清PPML和安全机器学习（Secure ML）的区别。这二者的区别在于它们被设计用来应用不同类型的安全威胁。在安全机器学习中，敌手被假设违反了机器学习系统的完整性和可用性。在PPML中，递手被假设违反了机器学习的隐私性和机密性 完整性（Integrity） 对完整性的攻击可能导致机器学习系统会出现检测错误，例如可能会将入侵点检测为正常。 可用性（Availability） 对可用性的攻击可能导致系统会出现分类错误（假阴性和假阳性），即系统会变成不可用的。这是比完整性攻击更宽泛的一种攻击类型。 机密性（Confidentiality） 对机密性的攻击可能会导 ...

本文介绍零知识证明中的一对概念：R1CS和QAP 概述 zk-SNARKS是目前最常用的零知识证明系统，但是由于其复杂性，不能直接应用于任何计算问题，因此需要对计算问题进行一步步的转化，其中就包含了R1CS和QAP。 R1CS 全程 Rank-1 Con­straint Sys­tem，一阶约束系统，其本质是一个可计算的三元方程组。 而 QAP 全称 Qua­dratic Arith­metic Peoblem，二次算术问题，QAP 转换不仅可以将函数的代码转换为 QAP，还可以在转换的同时构建一个对应于代码输入的解（又称为 QAP 的 Wit­ness），之后再基于这个 wit­ness 构建一个实际的零知识证明系统。 本文的参考是V神 QAP 在V神的文章中，给出了一个例子：P希望向V证明其知道方程x3+x+5=35x^3+x+5=35x3+x+5=35的解（P知道这个方程的解，因此witness为x=3x=3x=3），接下来是如何转化为QAP问题 首先，我们用程序语言描述这个问题： 123def find(x): y=x**3 return y+x+5 Flatt ...

Sigma零知识证明，知道秘密ω\omegaω，且与公开输入QQQ满足离散对数关系Q=ωGQ=\omega GQ=ωG Sigma零知识证明协议 设关系R⊆X∗YR\subseteq X *YR⊆X∗Y, 那么<P, V> 构建在R上的一个Sigma 协议为： P是一个叫证明的交互式协议，其输入为一个witness-statement对(x,y)∈R(x,y)\in R(x,y)∈R. V是一个叫验证的交互式协议，其输入为一个statement，y∈Ry\in Ry∈R P和V交互过程为： 首先，P计算一个承诺(commitment) t ，将其发送给V； 在收到来自P的消息后，V在有限的挑战空间C中随机选取一个挑战元素(challenge) c，并将其发送给P ； 在接收到来自V的挑战后， P计算出一个反馈(response) z ,将其发送给V 在收到了来自P的反馈后, V输出accept或者reject。 例子 1）P计算h=gxmod ph=g^xmod\ ph=gxmod p作为秘密 2）P选择随机数r∈zqr\in z_qr∈zq​，计算 ...

承诺 承诺分为三个步骤：承诺，打开承诺，验证承诺。 承诺：承诺:发送方将某个值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−α ...