同态加密简单理解

A. 同态加密的同态加密的相关概念

同态加密的思想起源于私密同态，代数同态和算术同态是私密同态的子集。
R 和 S 是域，称加密函数 E：R→S 为：
加法同态，如果存在有效算法⊕，E(x+y)=E(x)⊕E(y)或者 x+y=D(E(x)⊕E(y))成立，
并且不泄漏 x 和 y。
乘法同态，如果存在有效算法 ，E(x×y)=E(x) E(y)或者 xy=D(E(x) E(y))成立，
并且不泄漏 x 和 y。
混合乘法同态，如果存在有效算法 ，E(x×y)=E(x) y 或者 xy=D(E(x) y)成立，并
且不泄漏 x。
减法同态，如果存在有效算法○- ，E(x-y)=E(x)○- E(y)或者 x-y=D(E(x)○- E(y))成立，
并且不泄漏 x 和 y，则称 E 为减法同态。
除法同态，如果存在有效算法○/ ，E(x/y)=E(x)○/ E(y)或者 x/y=D(E(x)○/ E(y))成立，
并且不泄漏 x 和 y，则称 E 为减法同态。
代数同态，如果 E 既是加法同态又是乘法同态。
算术同态，如果 E 同时为加法同态、减法同态、乘法同态和除法同态。

B. 隐私保护技术 同态加密

安全多方计算
同态加密
差分隐私

同态加密逐渐被认为是在 PPML 中实现安全多方计算的一种可行方法。

设 表示使用 作为加密密钥的加密函数。设 表示明文空间， 且 表示密文空间。一个安全密码系统若满足以下条件，则可被称为同态的(homomorphic):

对于 中的运算符 和 中的运算符 ， 符号表示左边项等于或可以直接由右边项计算出来，而不需要任何中间解密。在本书中，我们将同态加密运算符设为 ，并且对密文的加法操作和乘法操作按如下方式重载:
加法：
标量乘法：

同态加密方法分为三类:部分同态加密 (Partially Homomorphic Encryption, PHE)，些许同态加密 (Somewhat Homomorphic Encryption, SHE) 和全同态加密 (Fully Homomorphic Encryption, FHE)。
//待补充

C. 区块链中现代密码学

1983年 - David Chaum描述的盲签
1997年 - Adam Back发明的HashCash（工作证明制度的一个例子）
2001年 - Ron Rivest，Adi Shamir和Yael Tauman向加密社区提出了环签名
2004年 - Patrick P. Tsang和Victor K.提出使用环签名系统进行投票和电子现金;
2008年 - 由Satoshi Nakamoto出版的Bitcoin白皮书
2011年 - 比特币系统中的匿名分析，Fergal Reid和Martin Harrigan
2012 - 目的地址比特币匿名（CryptoNote中的一次性地址）。

安全多方计算起源于1982年姚期智的百万富翁问题。后来Oded Goldreich有比较细致系统的论述。

姚氏百万富翁问题是由华裔计算机科学家、图灵奖获得者姚启智教授首先提出的。该问题表述为：两个百万富翁Alice和Bob想知道他们两个谁更富有，但他们都不想让对方知道自己财富的任何信息。该问题有一些实际应用：假设Alice希望向Bob购买一些商品，但她愿意支付的最高金额为x元；Bob希望的最低卖出价为y元。Alice和Bob都非常希望知道x与y哪个大。如果x>y，他们都可以开始讨价还价；如果z<y，他们就不用浪费口舌。但他们都不想告诉对方自己的出价，以免自己在讨价还价中处于不利地位。

该方案用于对两个数进行比较，以确定哪一个较大。Alice知道一个整数i；Bob知道一个整数j, Alice与B0b希望知道究竟i>=j还是j>i，但都不想让对方知道自己的数。为简单起见，假设j与i的范围为[1，100】。Bob有一个公开密钥Eb和私有密钥Db。

安全多方计算（Secure Multi-Party Computation）的研究主要是针对无可信第三方的情况下, 如何安全地计算一个约定函数的问题. 安全多方计算在电子选举、电子投票、电子拍卖、秘密共享、门限签名等场景中有着重要的作用。

同态加密（Homomorphic Encryption）是很久以前密码学界就提出来的一个Open Problem。早在1978年，Ron Rivest, Leonard Adleman, 以及Michael L. Dertouzos就以银行为应用背景提出了这个概念[RAD78]。对，你没有看错，Ron Rivest和Leonard Adleman分别就是着名的RSA算法中的R和A。

什么是同态加密？提出第一个构造出全同态加密（Fully Homomorphic Encryption）[Gen09]的Craig Gentry给出的直观定义最好：A way to delegate processing of your data, without giving away access to it.

这是什么意思呢？一般的加密方案关注的都是数据存储安全。即，我要给其他人发个加密的东西，或者要在计算机或者其他服务器上存一个东西，我要对数据进行加密后在发送或者存储。没有密钥的用户，不可能从加密结果中得到有关原始数据的任何信息。只有拥有密钥的用户才能够正确解密，得到原始的内容。我们注意到，这个过程中用户是不能对加密结果做任何操作的，只能进行存储、传输。对加密结果做任何操作，都将会导致错误的解密，甚至解密失败。

同态加密方案最有趣的地方在于，其关注的是数据处理安全。同态加密提供了一种对加密数据进行处理的功能。也就是说，其他人可以对加密数据进行处理，但是处理过程不会泄露任何原始内容。同时，拥有密钥的用户对处理过的数据进行解密后，得到的正好是处理后的结果。

有点抽象？我们举个实际生活中的例子。有个叫Alice的用户买到了一大块金子，她想让工人把这块金子打造成一个项链。但是工人在打造的过程中有可能会偷金子啊，毕竟就是一克金子也值很多钱的说… 因此能不能有一种方法，让工人可以对金块进行加工（delegate processing of your data），但是不能得到任何金子（without giving away access to it）？当然有办法啦，Alice可以这么做：Alice将金子锁在一个密闭的盒子里面，这个盒子安装了一个手套。工人可以带着这个手套，对盒子内部的金子进行处理。但是盒子是锁着的，所以工人不仅拿不到金块，连处理过程中掉下的任何金子都拿不到。加工完成后。Alice拿回这个盒子，把锁打开，就得到了金子。

这里面的对应关系是：盒子：加密算法盒子上的锁：用户密钥将金块放在盒子里面并且用锁锁上：将数据用同态加密方案进行加密加工：应用同态特性，在无法取得数据的条件下直接对加密结果进行处理开锁：对结果进行解密，直接得到处理后的结果同态加密哪里能用？这几年不是提了个云计算的概念嘛。同态加密几乎就是为云计算而量身打造的！我们考虑下面的情景：一个用户想要处理一个数据，但是他的计算机计算能力较弱。这个用户可以使用云计算的概念，让云来帮助他进行处理而得到结果。但是如果直接将数据交给云，无法保证安全性啊！于是，他可以使用同态加密，然后让云来对加密数据进行直接处理，并将处理结果返回给他。这样一来：用户向云服务商付款，得到了处理的结果；云服务商挣到了费用，并在不知道用户数据的前提下正确处理了数据；

聚合签名由Boneh等人提出，主要是通过聚合多个签名为一个签名，来提高签名与验证的效率。要对多个用户的数据进行签名，聚合签名能够极大地降低签名计算复杂度。CL就是聚合签名。

零知识证明过程有两个参与方，一方叫证明者，一方叫验证者。证明者掌握着某个秘密，他想让验证者相信他掌握着秘密，但是又不想泄漏这个秘密给验证者。

双方按照一个协议，通过一系列交互，最终验证者会得出一个明确的结论，证明者是或不掌握这个秘密。

对于比特币的例子，一笔转帐交易合法与否，其实只要证明三件事：

发送的钱属于发送交易的人
发送者发送的金额等于接收者收到金额
发送者的钱确实被销毁了
整个证明过程中，矿工其实并不关心具体花掉了多少钱，发送者具体是谁，接受者具体是谁。矿工只关心系统的钱是不是守恒的。

zcash 就是用这个思路实现了隐私交易。

零知识证明的三条性质对应：

（1）完备性。如果证明方和验证方都是诚实的，并遵循证明过程的每一步，进行正确的计算，那么这个证明一定是成功的，验证方一定能够接受证明方。
（2）合理性。没有人能够假冒证明方，使这个证明成功。
（3）零知识性。证明过程执行完之后，验证方只获得了“证明方拥有这个知识”这条信息，而没有获得关于这个知识本身的任何一点信息。

只有环成员，没有管理者，不需要环成员之间的合作，签名者利用自己的私钥和集合中其他成员的公钥就能独立的进行签名，不需要其他人的帮助，集合中的其他成员可能不知道自己被包含在了其中。
环签名可以被用作成一种泄露秘密的方式，例如，可以使用环形签名来提供来自“白宫高级官员”的匿名签名，而不会透露哪个官员签署了该消息。 环签名适用于此应用程序，因为环签名的匿名性不能被撤销，并且因为用于环签名的组可以被即兴创建。

1）密钥生成。为环中每个成员产生一个密钥对（公钥PKi，私钥SKi)
2）签名。签名者用自己的私钥和任意n个环成员的公钥为消息m生成签名a
3）签名验证。签名者根据环签名和消息m，验证签名是否是环中成员所签。如果有效就接收，如果无效就丢弃。

群签名的一般流程

盲数字签名（Blind Signature）简称盲签名——是一种数字签名的方式，在消息内容被签名之前，对于签名者来说消息内容是不可见的。1982年大卫·乔姆首先提出了盲签名的概念。盲签名因为具有盲性这一特点，可以有效保护所签署消息的具体内容，所以在电子商务和电子选举等领域有着广泛的应用。

类比例子：对文件签名就是通过在信封里放一张复写纸，签名者在信封上签名时，他的签名便透过复写纸签到文件上。

所谓盲签名，就是先将隐蔽的文件放进信封里，而除去盲因子的过程就是打开这个信封，当文件在一个信封中时，任何人不能读它。对文件签名就是通过在信封里放一张复写纸，签名者在信封上签名时，他的签名便透过复写纸签到文件上。

一般来说，一个好的盲签名应该具有以下的性质：

不可伪造性。除了签名者本人外，任何人都不能以他的名义生成有效的盲签名。这是一条最基本的性质。
不可抵赖性。签名者一旦签署了某个消息，他无法否认自己对消息的签名。
盲性。签名者虽然对某个消息进行了签名，但他不可能得到消息的具体内容。
不可跟踪性。一旦消息的签名公开后，签名者不能确定自己何时签署的这条消息。
满足上面几条性质的盲签名，被认为是安全的。这四条性质既是我们设计盲签名所应遵循的标准，又是我们判断盲签名性能优劣的根据。

另外，方案的可操作性和实现的效率也是我们设计盲签名时必须考虑的重要

因素。一个盲签名的可操作性和实现速度取决于以下几个方面：

1,密钥的长度；
2,盲签名的长度；
3,盲签名的算法和验证算法。
盲签名具体步骤
1,接收者首先将待签数据进行盲变换，把变换后的盲数据发给签名者。
2,经签名者签名后再发给接收者。
3,接收者对签名再作去盲变换，得出的便是签名者对原数据的盲签名。
4,这样便满足了条件①。要满足条件②，必须使签名者事后看到盲签名时不能与盲数据联系起来，这通常是依靠某种协议来实现的。

D. 人工智能与区块链的关系

区块链与人工智能其实并无直接关系，无论是在开发上还是在技术上，但二者并不是不能相关联。只要使用得当，二者也可以有很好的结合。

比如现阶段的区块链领域，公链技术发展停滞不前，其中关键的一环就是在出块的问题上，目前旧时代的公链技术在出块效率上存在很大的问题，不光浪费资源，而且在分配上也很不合理，导致公链资源大量被浪费，效率停滞不前。

而人工智能恰好可以很好的解决这一问题，比如通过人工智能（AI）优化的神经网络来增强 其共识算法，进行自我学习和自我优化的公链，致力于提高转账过程以及智能合约的 安全性、互操作性、和高度可扩展性。像Velas就是 采用通过 AI 增强的 DPoS 共识，在不降低安全性和交易速度的情况下，完全实现去中心化。

Velas 上的神经网络由许多简单的有机体组成，它们通过 80/20 共识消除区块链中 的不规则现象，确保网络按预期运行。 不光如此，Velas AI 计算出块时间和运行节点的奖励。AI 优化网络产生了可能的最佳结果，降 低了共识的成本，并使其可扩展至超过每秒 3 万次交易。

E. 隐私环境对保护心灵有作用吗

答：对保护心灵是有很好的作用的。

我们的心灵是受着外界环境的直接影响的，当你的外界环境非常美好的时候，你的心宴蚂灵也会非常的美好，同样当你的外部生活环境是非常恶劣的时候，直接就影响到了你的内心，也是非常恶劣的。所以，不同的环境对人们的心灵产生着不同的影响，从而说明了环境对心灵是有很大的作用的。

隐私的环境实际上就是对每个人的保护，尊重个人的隐私，尊纤孙重个人的独立，个体的一些相对的要求，这样就对人相对需要的安全环境达成了一种满足，只有在这种情况下毁祥链，人的心灵才能够更好的，更安全的，更舒适的生活下去。所以我们应该营造一些这样的氛围，也就是说我们现在的饭店里面为什么有的是大堂的餐桌，有的是包间，我们大家更喜欢去包间，因为它就是一种隐私的环境，她对我们就有一种非常好的保护，所以就能够让我们更好地拥有自己的心灵。

希望我的回答对你有帮助。

图片来源于网络

F. 零知识证明

https://arxiv.org/abs/1906.07221

零知识简洁的非交互知识论证（zk SNARK）是一种真正巧妙的方法，可以在不透露任何其他信息的情况下证明某件事是真的，然而，为什凯谈么它盯丛碰首先是有用的呢？

零知识证明在无数应用中是有利的，包括:

关于私人数据的证明声明:

匿名授权：

匿名付款：

外包计算：

尽管表面上听起来很棒，但底层方法是数学和密码学的“奇迹”，自 1985 年在主要着作“交互式证明系统的知识复杂性中引入以来，已经进行了第四个十年的研究 随后引入了非交互式证明，这在区块链的背景下尤为重要。

在任何零知识证明系统中，都有一个验证人想要说服验证人某些陈述是真实的，而不披露任何其他信息，例如，验证人了解到验证人的银行账户中有X多个，但没有其他信息（即，未披露实际金额）。协议应满足三个属性：

让我们从简单开始，并尝试证明某些东西，而不必担心零知识，非交互性，其形式和适用性。

想象一下，我们有一个长度为 10 数组，我们想向验证者（例如程序）证明所有这些位都设置为 1，即我们知道一个数组，使得每个元素都等于 1。

验证者一次只能检查 (即读取) 一个元素。为了验证语句，可以通过以某种任意顺序读取元素，并检查它是否真正等于1，如果是，则在第一次检查后该语句的置信度为10%，或者如果该位不等于1，则语句完全无效。验证者必须进入下一轮，直到他获得足够的信心。在一些情况下，可以信任证明者并且只需要50% 置信度，在需要95% 置信度的其他情况下，必须检查所有单元。很明显，这种证明协议的缺点是，必须进行与元素数量成比例的检查数量，如果我们考虑数百万个元素的数组，这是不切实际的。

让我们考虑多项式，有一个曲线对应于多项式： 。多郑蠢项式有一个有利的性质，即如果我们有两个不相等的次数最多为 d 的多项式，它们相交的点不超过 d。 例如，让我们稍微修改原始多项式 。如果我们想找到两个多项式的交点，我们需要将它们等同起来。例如，要找到多项式与x轴相交的位置 (即 )，我们将 等同，并且此类方程的解将是那些共享点: ， 和 。

同样，我们可以将多项式的原始版本和修改版本等同起来，以找到它们的交点。所得的多项式为1，且有明显的解 。因此只有一个交点。

对于任意次数为 d 的多项式，任何此类方程的结果始终是另一个次数最多为 d 的多项式，因为没有乘法可以产生更高的次数。 示例： ，简化为 。代数基本定理告诉我们，d 次多项式最多可以有 d 个解。因此，我们可以得出结论，任意点处的任何多项式的求值类似于其唯一身份的表示。让我们在x = 10处评估我们的示例多项式。

事实上，在所有要计算的x选项中，最多只有3个选项在这些多项式中具有相同的计算，而所有其他选项都会不同。这就是为什么如果证明者声称知道一些多项式 (无论其次数有多大)，他们可以遵循一个简单的协议来验证语句:

例如，如果我们考虑 x 从 1 到 的整数范围，则评估不同的点数为 。 此后，x 意外“击中”任何 个共享点的概率等于 ，这被认为可以忽略不计。

注意：与无效位检查协议相比，新协议只需要一轮，并且在声明中给出了压倒性的信心（假设 d 充分小于范围的上限，几乎 100%）。

这就是为什么多项式是zk-SNARK的核心，尽管也可能存在其他证明介质。

我们从证明多项式知识的问题开始，然后采用通用方法。 在此过程中，我们将发现多项式的许多其他性质。 到目前为止的讨论集中，关注一个弱的证明概念上，即各方必须相互信任，因为还没有措施来执行协议的规则。 例如，证明者不需要知道多项式，他可以使用任何其他可用的方法来得出正确的结果。 此外，如果验证者的多项式评估的幅度不大，比如说 10，验证者可以猜测一个数字，并且它被接受的概率是不可忽略的。 我们必须解决协议的这种弱点，但首先知道多项式意味着什么？ 多项式可以表示为以下形式（其中 n 是多项式的次数）：

如果有人说他知道一个 1 次多项式（即 ），那意味着他真正知道的是系数 。 此外，系数可以有任何值，包括 0。让我们说，证明者声称知道3次多项式，使得x = 1和x = 2是所有可能解中的两个。这样的有效多项式之一是 。

代数的基本定理指出，只要多项式是可解的，任何多项式都可以分解为线性多项式 (即代表直线的1次多项式)。因此，我们可以将任何有效多项式表示为其因子的乘积:

同样，如果这些因子中的任何一个为零，则整个方程为零，因此，所有 都是唯一的解。我们的示例可以分解为以下多项式:

x的值是：0，1，2，你可以很容易地在多项式的任一形式上检查这一点。

回到证明者声称他知道根为 1 和 2 的 3 次多项式，这意味着他的多项式具有以下形式：

换句话说，(x − 1) 和 (x − 2) 是所讨论的多项式的余因子。因此，如果证明者想要证明他的多项式确实具有这些根而不公开多项式本身，则他需要证明他的多项式p(x) 是那些协因子 的乘法，称为目标多项式，和一些任意多项式h(x) ，即:

换句话说，p(x) 具有t(x) 的所有根。找到h(x) 的自然方法是通过除法 。如果证明者找不到这样的h(x)，这意味着p(x) 没有必要的协因子t(x)，在这种情况下，多项式除法将具有余数。在我们的示例中，如果我们将 除以 。我们得到了无余数的结果 。

使用我们的多项式身份检查协议，我们可以比较多项式 和 ：

为了将其付诸实践，让我们在示例中执行此协议:

相反，如果证明者使用不同的 ，它没有正确的辅因子，例如 ，那么：

我们将得到 ，余数为 ，即: 。这意味着证明者必须将余数除以 才能评估 。因此，由于验证者对x的随机选择，因此对于余数 被t(x) 整除的概率很低，因此，如果验证者将检查p和h补是整数，这样的证明将被拒绝。但是，该检查要求多项式系数也必须是整数。

现在，我们可以在不学习多项式本身的情况下检查多项式的特定属性，因此这已经为我们提供了某种形式的零知识和简洁。尽管如此，此构造仍存在多个问题:

我们将在以下部分解决所有问题。

在上文中，如果将 和 不是明文给出，而是作为黑匣子给出，那将是理想的选择，因此人们无法篡改协议，但仍然能够计算对这些模糊值。类似于哈希函数，因此在计算时很难返回到原始输入。

这正是同态加密的目的。也就是说，它允许对一个值进行加密，并能够对这种加密应用算术运算。有多种方法可以实现加密的同态特性，我们将简要介绍一种简单的方法。

一般的想法是，我们选择一个基数的自然数g（比如5），然后对一个值进行加密，我们将g乘以该值的幂。例如，如果我们想要加密数字3：

其中125是3的加密。如果要将这个加密的数字乘以2，则将其提高为2的指数:

我们能够将未知值乘以2，并对其进行加密。我们还可以通过乘法添加两个加密值，例如3+2：

同样，我们可以通过除法减去加密的数字，例如5 − 3:

但是，由于基数5是公共的，因此很容易回到秘密数字，将加密的数字除以5，直到结果为1。除法的次数即为明文。

这就是模算法发挥作用的地方。模运算的思想如下：我们声明只选择前n个自然数，即0，1，…，n-1而不是拥有一个无限的数字集。如果任何给定的整数不在这个范围内，我们将其“环绕”。例如，让我们先选择六个数字。为了说明这一点，请考虑一个具有六个相等单位刻度的圆；这是我们的射程。

现在让我们看看数字8将落在哪里。 打个比方，我们可以把它想象成一根绳子，它的长度是八个单位。如果我们把绳子连接到圆圈的开头并开始将绳子缠绕在它周围，旋转一圈后，我们还剩下一部分绳子.因此，如果我们继续这个过程，绳子将在2处结束。

它是模运算的结果。 不管绳子有多长，它总是会停在圆圈的刻度之一处。 因此，模运算将使其保持在一定范围内。 15 个单位的绳索将在 3 处停止，即 6 + 6 + 3（两个完整的圆圈，剩余 3 个单位）。 负数的工作方式相同，唯一的区别是我们将其包装在相反的方向，对于 -8，结果将是 4。

而且，我们可以进行算术运算，结果总是在n个数的范围内。 我们现在将使用符号“mod ”来表示数字的范围。 例如：3 × 5 = 3 (mod 6); 5 + 2 = 1 (mod 6).

此外，最重要的特性是运算顺序无关紧要，例如，我们可以先执行所有运算，然后在每次运算后应用模或应用模。例如: 相当于：2 × 4 = 2 (mod 6); 2 − 1 = 1 (mod 6); 1 × 3 = 3 (mod 6).

那到底为什么有帮助呢？事实证明，如果我们使用模算术，则具有运算结果，回到原始数字是不平凡的，因为许多不同的组合将具有相同的结果: 5 × 4 = 2 (mod 6); 4 × 2 = 2 (mod 6); 2 × 1 = 2 (mod 6).

如果没有模算术，结果的大小为它的解决方案提供了线索。 否则，这条信息会被隐藏，而常见的算术属性会被保留。

如果我们回到同态加密并使用模运算，例如模 7，我们将得到：

和不同的指数会有相同的结果:

这是很难找到指数的地方。 事实上，如果模数足够大，这样做就变得不可行，而现代密码学的很大一部分是基于这个问题的“难度”。该方案的所有同态属性都保留在模领域中：

encryption:
multiplication:
addition:

让我们明确说明加密函数： ，其中 v 是我们要加密的值。

这种同态加密方案存在局限性，尽管我们可以将加密值乘以未加密值，但我们不能将两个加密值乘以 (和除以)，也不能对加密值求幂。虽然从第一印象来看是不幸的，但这些属性将成为zk-SNARK的基石。

有了这样的工具，我们现在可以评估一个加密随机值为x的多项式，并相应地修改零知识协议。

让我们看看如何评估多项式 。正如我们以前建立的那样，多项式就是知道它的系数，在这种情况下，它们是: 1,-3,2。因为同态加密不允许对加密值求幂，所以我们必须得到从1到3的x幂的加密值: ， ， ，这样我们可以对加密多项式求值如下:

作为这些操作的结果，我们在我们未知的某个 x 处对我们的多项式进行了加密。 这是一个非常强大的机制，并且由于同态特性，相同多项式的加密计算在加密空间中总是相同的。我们现在可以更新协议的先前版本，对于d次多项式:

Verifier:

Prover:

Verifier:

由于证明者对s一无所知，因此很难提出不合法但仍匹配的评估。

虽然在这样的协议中，证明者的敏捷性是有限的，但他仍然可以使用任何其他方法来伪造证明，而无需实际使用所提供的 s 幂的加密，例如，如果证明者声称仅使用 2 次幂 和 有一个令人满意的多项式 ，这在当前协议中无法验证。

多项式的知识是其系数 。 我们在协议中“分配”这些系数的方式是通过对秘密值 s 的相应加密幂求幂（即 ）。 我们已经在选择 s 的加密幂时限制了证明者，但这种限制并未强制执行，例如，可以使用任何可能的方法来找到满足方程 的任意值 和 并将它们提供给验证者而不是 和 。 例如，对于一些随机 ， 和 ，其中 可以从提供的 s 的加密幂计算。 这就是为什么验证者需要证明仅使用 s 的幂的加密来计算 和 而没有别的。

让我们考虑一个1次多项式的基本例子，该多项式具有一个变量和一个系数 ，相应地，s的加密 。我们正在寻找的是确保只有s的加密，即 ，被一些任意系数c同态“乘以”，而不是其他任何东西。所以对于任意的c，结果必须是 形式。

一种方法是要求对另一个移位的加密值与原始值一起执行相同的操作，充当“校验和”的算术模拟，确保结果是原始值的取幂。这是通过引入的指数知识假设Knowledge-of-Exponent Assumption (或KEA) 来实现的，更确切地说:

Alice有一个值a，她希望Bob指数到任何幂，唯一的要求是只有这个a可以指数，没有别的，以确保她：

因为 Bob 无法从元组 中提取 ，因此推测 Bob 可以产生有效响应的唯一方法是通过以下过程：

最终，这样的协议向Alice提供了一个证据，证明Bob确实将a乘以他已知的某个值，并且他不能进行任何其他操作，例如乘法、加法，因为这将消除 移位关系。

在同态加密上下文中，幂运算是加密值的乘法。我们可以在简单的单系数多项式 的情况下应用相同的构造：

这种结构限制证明者仅使用提供的加密 s，因此证明者可以仅将系数 c 分配给验证者提供的多项式。 我们现在可以将这种单项多项式方法缩放为多项多项式，因为每个项的系数分配是单独计算的，然后同态地“相加”在一起。 因此，如果向证明者提供 s 的加密幂以及它们的移位值，他可以评估原始多项式和移位多项式，其中必须进行相同的检查。 特别是对于 d 次多项式：

对于我们之前的示例多项式 ，这将是：

现在我们可以确定，验证程序除了使用验证程序提供的多项式外，没有使用任何其他方法，因为没有其他方法来保持 移位。此外，如果验证者希望确保在验证者的多项式中排除一些s的幂，例如j，他将不提供加密 及其移位 。

与我们一开始的相比，我们现在有了一个健壮的协议。 然而，无论加密如何，零知识属性仍然存在一个明显的缺点：虽然理论上多项式系数 可以有很大范围的值，但实际上它可能非常有限（上例中为 6），这意味着 验证者可以暴力破解有限范围的系数组合，直到结果等于证明者的答案。 例如，如果我们考虑每个系数的 100 个值的范围，则 2 次多项式将总共有 100 万个不同的组合，考虑到蛮力将需要不到 100 万次迭代。 此外，即使在只有一个系数且其值为 1 的情况下，安全协议也应该是安全的。

因为验证器只能从验证器发送的数据中提取关于未知多项式p（x）的知识，所以让我们考虑那些提供的值（证明）： 。他们参与以下检查：

gp=gh（多项式p（x）有t（x）的根）

（gp）α=gp′t（s）（使用正确形式的多项式）

问题是我们如何改变证据，使支票仍然有效，但无法提取任何知识？从上一节可以得出一个答案：我们可以用一些随机数δ（δ）来“移位”这些值，例如（gp）δ。现在，为了提取知识，首先需要找到被认为不可行的δ。此外，这种随机化在统计学上与随机性是无法区分的。

为了保持关系，让我们检查验证者的检查。证明者的值之一位于方程式的每一侧。因此，如果我们用相同的 δ “移动” 它们中的每一个，方程必须保持平衡。

具体地，证明者对随机 δ 进行采样，并用g α p(s) δ gh(s) δ 对其证明值求幂，并提供给验证者进行验证:

(gp)δ = gh δ t(s) (gp)δ α = gp′ δ

合并后，我们可以观察到支票仍然有效：

注意: 零知识是多么容易被编织到建筑中，这通常被称为 “免费” 零知识。

到目前为止，我们有一个交互式零知识方案。为什么会这样？由于该证明仅对原始验证者有效，其他任何人（其他验证者）都不能信任同一证明，因为：

因此，为了证明语句（在这种情况下是多项式的知识），需要与每个验证者进行单独的交互。

虽然交互式证明系统有其使用案例，例如，当证明人只想说服一个专用的验证人（称为指定验证人），这样证明就不能再用于向其他人证明同一陈述时，当一个人需要同时（例如，在区块链等分布式系统中）或永久地说服多方时，这是非常有效的。验证方需要始终保持在线，并对每个验证方执行相同的计算。

因此，我们需要的秘密参数是可重用的，公开的，可信的和不可滥用的。

让我们首先考虑在秘密 (t(s)，α) 产生后如何保护它们。我们可以像验证者在发送给证明者之前对s的指数进行加密一样对它们进行加密。然而，我们使用的同态加密不支持两个加密值的乘法，这对于验证检查以使t(s) 和h以及p和 α 的加密相乘都是必需的。这就是密码配对的地方。

密码配对（双线性映射）是一种数学构造，用函数 , 给定来自一组数字的两个加密输入（例如， ，允许将它们确定地映射到不同数字输出集中的乘法表示，即， 。

由于源和输出编号集合不同，因此配对的结果不能用作另一个配对操作的输入。我们可以将输出集 (也称为 “目标集”) 视为来自 “不同的宇宙”。因此，我们不能将结果乘以另一个加密值，并通过名称本身建议我们一次只能乘以两个加密值。在某种意义上，它类似于一个散列函数，它将所有可能的输入值映射到一组可能的输出值中的一个元素，并且它不是平凡可逆的。

注意: 乍一看，这种限制只能阻碍依赖的功能，具有讽刺意味的是，在zk-SNARK情况下，它是该方案的安全性所拥有的最重要的属性。

配对函数 的一个基本（技术上不正确）的数学类比是说明有一种方法可以“交换”每个输入的基数和指数，这样基数 在转换过程中会被修改成指数，例如 。 然后将两个“交换的”输入相乘，使得原始 a 和 b 值在相同的指数下相乘，例如：

因此，由于在“交换”期间使用结果 在另一个配对（例如， ）中改变了碱基，因此不会产生所需的加密乘法 。配对的核心属性可以用等式表示：

e(ga, gb) = e(gb, ga) = e(gab, g1) = e(g1, gab) = e(g1, ga)b= e(g1, g1) ab= . . .

从技术上讲，配对的结果是目标集不同生成器g下原始值的加密产物，即 。因此，它具有同态加密的特性，例如，我们可以将多对的加密产物添加到一起：

注意：加密配对利用椭圆曲线来实现这些属性，因此从现在起，符号 将表示曲线上的生成器点，该点将被添加到自身 次，而不是我们在前面部分中使用的乘法群生成器。

有了加密配对，我们现在可以设置安全的公共和可重用参数。让我们假设我们信任一个诚实的一方来生成秘密 s 和 α。一旦 α 和具有相应 α 位移的 s 的所有必要幂被加密（gα, gsi , gαsi for i in 0, 1, ..., d），必须删除原始值。

这些参数通常被称为公共参考字符串common reference string或CRS。CRS生成后，任何prover和verifier都可以使用它来执行非交互式零知识证明协议。虽然不重要，但CRS的优化版本将包括对目标多项式target polynomial 的加密评估。

此外，CRS分为两组（对于 中的 ）：

由于能够乘以加密值，verifier可以在协议的最后一步检查多项式，让verification key verifier进程从证明者那里接收到加密多项式评估 gp、gh、gp'：

虽然可信设置是有效的，但它并不有效，因为 CRS 的多个用户将不得不相信一个删除的 和 ，因为目前没有办法证明这一点。 因此，有必要最小化或消除这种信任。 否则，不诚实的一方将能够在不被发现的情况下制作假证据。

实现这一点的一种方法是由多方使用前面部分中介绍的数学工具生成复合 CRS，这样这些方都不知道秘密。这是一种方法，让我们考虑三个参与者 Alice、Bob 和 Carol，对应的索引为 A、B 和 C，对于 i 在 1、2、...中。 . . , d:

作为这种协议的结果，我们有复合 和 并且没有参与者知道其他参与者的秘密参数，除非他们串通。事实上，为了学习 和 ，必须与其他所有参与者串通一气。因此，即使一个人是诚实的，也无法提供假证明。

注意：此过程可以根据需要对尽可能多的参与者重复。

可能存在的问题是如何验证参与者是否与 CRS 的每个值一致，因为对手可以采样多个不同的 s1、s2、...。 . . 和α1, α2, . . .，并将它们随机用于 s 的不同幂（或提供随机数作为增强的公共参考字符串），从而使 CRS 无效且不可用。

幸运的是，因为我们可以使用配对来乘以加密值，所以我们能够执行一致性检查，从第一个参数开始，并确保每个下一个参数都是从它派生的。参与者发布的每个 CRS 都可以检查如下：

请注意，虽然我们验证每个参与者都与他们的秘密参数一致，但使用先前发布的 CRS 的要求并未对每个下一个参与者强制执行（在我们的示例中为 Bob 和 Carol）。因此，如果对手是链中的最后一个，他可以忽略先前的 CRS 并从头开始构造有效参数，就好像他是链中的第一个，因此是唯一知道秘密 s 和 α 的人。

我们可以通过额外要求除第一个参与者之外的每个参与者加密和发布他的秘密参数来解决这个问题，例如，Bob 还发布：

这允许验证 Bob 的 CRS 是 Alice 参数的适当倍数，因为 i in 1, 2, . . . , d:

同样，Carol必须证明她的CRS是Alice-Bob的CRS的适当倍数。

这是一个强大的CRS设置方案，不完全依赖任何一方。实际上，即使只有一方是诚实的，并且删除并且从不共享其秘密参数，即使所有其他各方都合谋，它也是非常明智的。因此，CRS 设置中不相关的参与者越多，伪造证据的可能性就越小，如果竞争方参与，其可能性就可以忽略不计。该方案允许涉及对设置的易读性有疑问的其他不受信任的各方，因为验证步骤确保他们不会破坏最终的公共参考字符串 (也包括使用弱 α 和s)。

我们现在准备巩固进化的zk-SNARKOP协议。形式上，为简洁起见，我们将使用大括号来表示由其旁边的下标填充的一组元素，例如si i ∈[d] 表示集合s1，s2，...，sd。

已商定目标多项式t（x）和校准仪多项式的d次：

Setup：

G. 隐私计算-密码学-同态加密

近年来，随着大数据与人工智能的盛行，针对个人的个性化的推荐技术的不断发展，人们在享受便利的同时，也深深的感觉到无处不在的监控与监事，比如刚刚浏览了一个网站的商品，当去其他网站访问的时候就会推荐类似的产品；刚刚搜索了某件商品，在很多其他的场景中都会给你推荐。这种体验，谈不上不好，也谈不上多坏，但是如果仔细想想，就感觉自己的网上进行裸奔，个人隐私，一清二楚，毫无隐私可言，细思极恐。

不过随着广大用户对于个人隐私的重视程度不断加强，以及法律法规的不断完善，针对个人隐私的保护提出了更高的要求，什么样的数据可以采集、收集与使用，如何使用都是一个比较敏感的问题。十三届全国人大常委会第三十次会议表决通过了《 中华人民共和国个人信息保护法 》，并与2021年11月1日起施行。确立个人信息保护原则、规范处理活动保障权益、禁止“大数据杀熟”规范自动化决策、严格保护敏感个人信息、赋予个人充分权利等。新规施行后，违法的主体将 最高可处五千万以下或者上一年度营业额百分之五 以下的罚款。

鉴于上述情况，近年来隐私计算技术被不断的提及，源于其有优秀的数据保护作用，使得 “数据不出域、数据可用不可见、数据可算不可见” ，限定了数据的使用场景，防止了数据的泄露，而引起了业界的热捧。

隐私计算技术的演进历程如下图描述，以下是杨强教授在KDD 2021中国区的分享材料：

可以看到，隐私计算技术从1979年就开始了，最开始是安全多方计算、到差分隐私、到TEE， 再到最近火的不能再火的联邦学习 ，一系列的技术应运而生。那为啥现在隐私计算这么火呢。

注：隐私计算技术成熟度曲线

但是这些技术本身的安全加密都是采用共同的方法与策略，下面讲述下隐私计算的加密技术。

本文主要介绍同态加密，

众所周知，优秀的程序员需要 严谨的逻辑思维与具象能力 ，当然在材料的时候，可能需要适当的渲染。但是对于技术的理解，对技术的探索，严谨的逻辑与坚实的推理是非常重要的。所以，对于“数据加密”这个命题，需要进行一番探索。

如此三态合一，即可保障数据的全链路的生命周期安全 。

那么有没有办法解决数据计算的安全问题呢？答案就是 同态加密技术 。保障数据的运行态的安全，那么同态加密技术具体是如何实现，如何应用，并且有哪些限制呢？

什么是同态加密？ ，引用Gentry大佬的原话：

同态加密（Homomorphic Encryption, HE），指满足密文同态运算性质的加密算法，即数据经过同态加密之后，对密文进行某些特定的计算，得到的密文计算结果在进行对应的同态解密后的明文等同于对明文数据直接进行相同的计算， 实现数据的“可算不可见” 。同态加密的实现效果如图所示。

举个例子： 国内某家大型的三甲医院，由于历史悠久，并且医术精湛，历史遗留了大量的用户病例数据 。如今思考基于这些病例数据进行建模分析。但是由于数据量特别巨大，医院本身的IT资源有限，计算能力不足。

这个时候，云厂商找了过来。但是对于医院来说，这些数据本身是用户的隐私信息，并且也是医院的核心价值，所以尽管云厂商再三保证数据安全， 但是医院还是不能够放心的将数据上传到云厂商进行计算 。

正当这个事情推进不下去的时候，云厂商从密码行业花大价钱招来某个大牛，大牛提出一个方案，这样吧，我们现在有 这样一门技术，不需要传输明文数据，只需要传输密文就好，而且加密秘钥由医院自己保存，我们基于上传的密文数据做不解密的密态运算（ 并计算函数医院提供就好），这样数据不会泄露，云厂商对数据无感知，之后传回密文结果，医院自己解密就好 。医院一听非常高兴，那就这么办吧。

下面将核心流程描述下。

这里，大家可能有个问题，这个f应该是什么样的函数，有什么样的限制条件？HE方案是支持任意的数据处理方法f，还是说只支持满足一定条件的f呢？根据f的限制条件不同，HE方案实际上分为了两类：

Paillier加密算法是Pascal paillier[1]在1999年发明的概率公钥加密算法，该算法 基于复合剩余类的困难问题，是一种满足加法的同态加密算法 ，已经广泛应用在加密信号处理或第三方数据处理领域。

前面我们分析过 同态加密的核心流程 ，大家可以一起回忆一下。核心的函数包括：秘钥生成、明文加密、密文解密，下面我们来一步一步的分析，并且描述下，

秘钥的生成主要有如下的步骤，

下面介绍一个完整的同态运算，m由 组成，介绍下同态加密的是如何使用密文计算的。

H. 同态加密(1) GSW同态加密方案

所有的更新都放在我的博客中, 本文地址为 https://lingeros-tot.github.io/2019/08/11/%E5%90%8C%E6%80%81%E5%8A%A0%E5%AF%86-1-GSW%E5%8A%A0%E5%AF%86%E6%96%B9%E6%A1%88/

GSW同态加密方案确实如论文标题一样, 概念清晰明了, 其Intuition简单到一个刚学完线性代数的大一新生也能理解. GSW还支持基于属性的加密, 但本文中我们将不介绍这一部分内容.

当然, 完全理解GSW方案仍然需要用到一些比较进阶的知识, 如LWE问题的困难性等. 我们在本文中不会对这些知识做过多的介绍, 这些知识将在今后其他的博文中介绍. 关于同态加密的基础知识可以参阅博文 同态加密(0) 基础概念 , 这篇博文完成后, 地址将被更新到这里.

GSW方案是由Craig Gentry [1] , Amit Sahai与Brent Waters于2013年提出的方案, 发表于论文[GSW13] [2] 中.

最基本的GSW同态加密方案的私钥( )是一个向量 [3] , 而所有的明文 都被加密一个矩阵 中, 其中 是以 为近似特征向量并以 为近似特征值的矩阵, 即我们要求

这里可以看出， 我们只需要挑选 中非 的位(最好是选较大的位), 如第 位 , 并比较 与 的值就可以解出 的值.

一个需要注意的地方就是, 虽然 取自 , 但被视作是 中的元素, 因此具体的运算也是按照 的运算方式来进行.

我们也可以将噪声(error)显式地写出来, 记作

其中 是非常小的向量. 因此可以看出, 如果 确实是一个较小的噪声, 那么我们就可以正确地解出 .

现在我们来验证该加密方案具有同态性质. 现在假设有两个密文 , 对对应的明文分别是 , 即

其中 均为较小的噪声, 那么令 , 我们检验 的解密结果

这里可以看出, 确实是一个比较小的噪声项, 但是要让 的噪声比较小, 那么就需要让 是一个较小的矩阵(即其最大的元素较小), 我们稍后会解释如何做到这一点.

虽然说是乘法同态性质, 但是由于 , 我们也可以将 视作是做了同态的与(AND)运算. 与运算相对来说是比较简单的, 但是仅有与运算是不够的, 因为与运算是单调的, 单调的电路不可能是完备的, 我们需要实现一个超强的逻辑门----与非门的同态运算.

设 , 其中 为 阶单位矩阵, 则

根据之前的讨论, 如果 是一个较小的项, 我们有把握能从 中解出 .

到这里有没有一种心情舒畅的感觉? 与非门生万物, 我们确实可以通过不断地叠加与非门来实现相当复杂的函数运算, 并且由于与非门是完备的, 仅用与非门可以实现任何一个布尔函数.

虽然与非门非常强大, 但是每一次进行与非门运算, 都会导致新密文得噪声变得更大, 因此较多层的运算后, 噪声可能大得导致解密错误! 因此我们必须评估我们究竟能进行多少次的运算, 以及在快要达到极限的时候使用Bootstrapping技术. 这一点我们将在详细介绍方案的时候来说明.

这里我们要首先介绍一种工具, 我们称其为Lattice Gadget, 它的本质是一些代数运算, 能够辅助我们从标准的LWE加密方案生成满足同态性质的密文.

第一个运算是 , 它的作用是将一个 [4] 向量的每一位按照二进制展开, 即每一个元素 表示成二进制的形式 , 其中 [5] . 即

即将 的每一位都展开成了二进制, 变成 位, 整个结果一共是 位. 显然, .

类似的, 我们可以定义 的反函数 , 令

即将每一位的二进制表示重新组合成了 表示. 但是要注意的是, 并没有要求参数一定要是只由 构成的向量, 我们可以定义一个全新的函数

这个操作有什么意义? 它将那些不是全由 构成的 重新"抹平"成了由 中的元素构成, 并且能够保持其一定的性质.

下面介绍另一个不是那么好看, 但是却非常简单的操作 . 的功能也是将一个 向量转换为 向量, 但是却使用的是完全不一样的方式.

即将 的每一位, 展开为 位, 并且后一位是前一位的两倍. 使得整个向量变成 . 这样做的好处是, 如果 分别是 中的一位, 那么

前面一部分就是 中第 组的第 位, 而后一部分就是 中第 组的第 位, 那么显然有

如果将 直接写成 的形式, 我们还有

实际上左右两边的两项都是由中间得到的, 这样就可以将左右两边连接在一起. 这样我们发现一个惊人的事实: 如果内积的第二项是标准的 结果的形式, 那么对第一项做 操作不会改变内积的结果! 实际上这也不难理解, 因为Flatten操作就是把数值过高的位分到权重更高的位而已. 但是这样做有一个好处就是, 使得 变成每一位都是 的 .

我们将以上几种记号都推广到对矩阵可用, 例如对于 , 令

其余几种记号也做类似的推广, 总之就是, 对矩阵的每一列的列向量做相应的操作. 这时我们发现, 如果密钥 确实是某个向量 进行 的结果, 即 , 那么就有

这可以使得 变成一个较小的矩阵, 而不改变最后与 的相乘的结果! 这样使得 可以代替 进行下一层的同态运算使得我们要求的 项较小! 我们直接将 的结果记作

现在我们开始具体介绍方案. 我们要说的是, GSW方案根据解密算法的选区不同, 实际上有构造两套方案. 第一种是选择 作为解密算法, 该算法仅能解出 , 因此整个同态运算中主要用与非门构建逻辑电路进行计算. 另一个解密算法 可以解出 , 这样就可以自然地使用加法与乘法进行运算.

首先我们要说的是, GSW并不是一个标准假设下的全同态加密方案. GSW如果要做到全同态加密, 需要用到Bootstrapping, 进而需要用到LWE加密方案的Circular Security假设(即用一对公私钥中的公钥来加密私钥相关信息的加密结果是安全的). 我们这里不介绍Bootstrapping的具体过程, 仅介绍Somewhat HE.

这里的参数较多, 需要逐一解释一下. 首先 是安全参数, 表示密码方案中基于的困难的问题的复杂程度, 所有的参数都应该(直接或间接)基于这个参数选择. 参数 表示同态运算的层数, 由于同态运算的层数由噪声的占比决定, 因此想要做更多的同态运算次数, 那么噪声就不应该太快掩盖 , 就应该相应地选择大一些. 而LWE问题的错误分布 还有维数 按理来说是应该根据 来选择, 但是这两个参数是可以根据 来进行权衡(tradeoff)的, 这里直接用基础参数 来代替 . 而参数 则是为了方便我们进行表示而引入的记号, 并且他们在前面也出现过.

实际上这里就是变相生成了一组LWE问题的实例, 如果对这里不熟悉, 可以跟进我的Blog学习知识. 相关博文更新后会在这里补充地址.

这就是整个加密的过程, 其中 操作是为了保证 是一个较小的矩阵, 我们知道 是一个 向量, 那么

也是一个小噪声, 因此密文符合我们的要求.

实际上这里的解密过程就是比较 与 的值. 而为了使得解密出错的概率最低, 所以选择 较大的一项, 这样使得错误最多可以积累到 而解密不出错.

接下来我们看一下进行 层同态运算后, 噪声的增长. 我们知道, 两个噪声为 的密文行一次加法运算, 噪声增长到 . (这里 , 表示解密中的噪声项), 而两个噪声为 的密文乘法结果的的噪声项为 , 最多为 . 如果初始噪声为 的密文进行 层运算, 则噪声最多增长为 , 由这一点可以看出, 我们最多可以进行对数次数的同态运算. 但是对数次的运算已经足够用于解密运算, 因此我们可以基于Circular Security假设, 使用Bootstrapping技术实现全同态.

I. 同态加密简介

同态加密是数据加密方式的一种，特点是允许数据在加密情况下实现数学或逻辑运算。

同态加密通常为非对称性加密。因此在介绍同态加密之前，简单介绍一下非对称性加密。非对称性加密分为三个步骤：

1. 生成一对钥匙，一个公钥pub和一个密钥priv；

2. 使用公钥pub加密原始数据，得到加密数据，公式：pub(原始数据）= 加密数据 ；

3. 使用密钥priv解密加密数据，得到原始数据，公式：priv( 加密数据 ）= 原始数据 ；

同态加密允许对 加密数据 进行处理，得到的解密结果等价于在原始数据下做运算。以联邦学习用到的Paillier算法举例，假设我有两个数 和 ，我希望把它们扔给第三方做加法运算，即 + 。同时不希望第三方知道 、 及它们之和的具体值，同态加密可以派上用场，具体步骤如下：

1. （本地）生成一对钥匙，公钥pub和密钥priv，公钥用于加密，密钥用于解密；

2. （本地）使用公钥pub分别加密 和 ，得到 ( )和 ( )；

3. （第三方）使用 函数处理 和 ，即 ；

4. （本地）使用密钥priv解密 ，即 ；

4中  =  + 。第三方通过上述步骤3实现了 和 在加密状态下做加法的操作。

为了更直观认识上述步骤，假设 =100， =200，步骤就变成：

1. （本地）生成一对钥匙，公钥pub和密钥priv，公钥用于加密，密钥用于解密；

2. （本地）使用公钥pub分别加密 和 ，得到 =1234， =4321 (举例）；

3.（第三方） 使用 函数处理 和 ，即 =12345678;

4. （本地）使用解密priv解密 ，得到  = 300。

第三方在不知道 =100和 =200，但是通过 函数依然可以在加密情况下实现相加运算。

J. 同态加密的实现原理是什么在实际中有何应用

同态加密是一种加密形式，它允许人们对密文进行特定的代数运算得到仍然是加密的结果，将其解密所得到的结果与对明文进行同样的运算结果一样。换言之，这项技术令人们可以在加密的数据中进行诸如检索、比较等操作，得出正确的结果，而在整个处理过程中无需对数据进行解密。其意义在于，真正从根本上解决将数据及其操作委托给第三方时的保密问题，例如对于各种云计算的应用。

这一直是密码学领域的一个重要课题，以往人们只找到一些部分实现这种操作的方法。而2009年9月克雷格·金特里（Craig Gentry）的论文 从数学上提出了“全同态加密”的可行方法，即可以在不解密的条件下对加密数据进行任何可以在明文上进行的运算，使这项技术取得了决定性的突破。人们正在此基础上研究更完善的实用技术，这对信息技术产业具有重大价值。