icp备案网站信息修改,html5教程 pdf,网站建设公司推广广告语,wordpress 幻灯片 文章一、何为同态加密#xff08;HE#xff09;#xff1f;
HE是一种特殊的加密方法#xff0c;它允许直接对加密数据执行计算#xff0c;如加法和乘法#xff0c;而计算过程不会泄露原文的任何信息。计算的结果仍然是加密的#xff0c;拥有密钥的用户对处理过的密文数据进… 一、何为同态加密HE
HE是一种特殊的加密方法它允许直接对加密数据执行计算如加法和乘法而计算过程不会泄露原文的任何信息。计算的结果仍然是加密的拥有密钥的用户对处理过的密文数据进行解密后得到的正好是处理后原文的结果。
即满足下面的性质的加密算法 从明文空间和密文空间的角度来看密文空间具有特定的算符。明文空间的加法对应密文空间的 ⊕ 明文空间的乘法对应密文空间的 ⊙ 。如下图 根据支持的计算类型和支持程度同态加密可以分为以下三种类型 半同态加密Partially Homomorphic Encryption, PHE只支持加法或乘法中的一种运算。其中只支持加法运算的又叫加法同态加密Additive Homomorphic Encryption, AHE 部分同态加密Somewhat Homomorphic Encryption, SWHE可同时支持加法和乘法运算但支持的计算次数有限 全同态加密Fully Homomorphic Encryption, FHE支持任意次的加法和乘法运算当前算法复杂度高实际使用较少。
在同态加密概念被Rivest在1978年首次提出后学术界出现了多个支持PHE的方案如RSA、GM、Elgamal、Paillier。此后SWHE方案也相继问世如BGN。关于FHE如何实现学术界在很长的时间都没有答案。直到2009年Gentry使用理想格构造了第一个FHE方案轰动了整个学术界并引发了学者们对于FHE方案构造的研究热潮。此后相继涌现出多个优秀的FHE方案包括BFV、BGV、CKKS等以及多个优秀的开源算法库如SEAL、HELib等。 二、隐私计算与同态加密
隐私计算的应用场景非常广泛除满足多方的通用计算算数或布尔计算功能外还有如隐私集合求交(Private Set Intersection, PSI)、隐私保护机器学习、加密数据库查询、门限签名等等更加细分的应用。然而在几种主要的通用计算技术路线中每种方法各有各的效率/安全性缺陷。FHE在计算有限次乘法后需要较复杂的去除噪声的操作经典的通用MPC协议通信开销较大而TEE的安全性高度依赖于硬件厂商无法提供密码学上严谨的安全性。在复杂的计算场景中单独使用某种通用方法通常得不到一个可用的落地方案这也激发了学者们研究对于特定场景的特定解法。一个可行的方案通常是根据具体场景来进行定制化的设计通过组合、优化不同的技术组件来得到安全、高效的方案精准满足该场景需求。 PHE登场辅助多种隐私计算场景 由于通用安全计算方法的一些不足以及在一些特定场景只需要使用一种HE运算如加法即可完成功能PHE在隐私计算领域得到了大量使用在多个开源库和大量学术顶会的方案中都有它的身影。PHE的高效、支持无限次加法或乘法的特点使其成为隐私计算的重要基本组件可辅助完成多种隐私计算功能
1隐私保护数据聚合
由于加法PHE可以在密文上直接执行加和操作不泄露明文在到多方协作的统计场景中可完成安全的统计求和的功能。 在联邦学习中不同参与方训练出的模型参数可由一个第三方进行统一聚合。使用加法PHE可以在明文数据不出域、且不泄露参数的情况下完成对模型参数的更新此方法已应用在实际应用如FATE和多个顶会工作中如SIGMOD、KDD、ATC 在在线广告投放的场景中广告主如商家在广告平台如媒体投放在线广告并希望计算广告点击的转化收益。然而广告点击数据集和购买数据集分散在广告主和广告平台两方。使用PHE加密结合隐私集合求和Private Intersection-Sum-with-Cardinality, PIS-C)协议可以在保护双方隐私数据的前提下计算出广告的转化率。 该方案已被Google落地应用 在加密数据库SQL查询场景在数据库不可信的情况下可以通过部署协议和代理来保护请求者的查询隐私。其中PHE可以用来完成安全数据求和和均值的查询。
2乘法三元组生成
通用安全计算根据计算电路的不同可分为算数计算和布尔计算对于算数计算来说其中的难点是如何做乘法。而使用预生成的乘法三元组来辅助乘法运算的方法可以大大降低乘法的在线开销是目前最为流行的方法。PHE是用于计算乘法三元组的重要工具已在多个顶会方案和实际产品如Sharemind中得到应用对于加速安全计算具有重要意义。
3构造特定的隐私保护协议
在机器学习预测分类场景中若拥有模型的一方不可信如外部厂商在数据方输入样本进行预测分类时可能需要保护样本数据的隐私。PHE作为building block可以构造出隐私保护比较协议和argmax协议并可以此进一步构造出隐私保护朴素贝叶斯分类器和超平面决策分类器。此外用PHE还可构造出不经意选择Oblivious Selection协议来支持隐私保护决策树分类器。
4门限签名
传统签名方式要求签名时从存储介质如磁盘中拉取完整私钥到内存存在泄露风险如被木马、病毒窃取侧信道攻击等。 使用门限签名可以有效规避此类风险让多方协作完成签名过程并确保私钥没有在任何一方被恢复。特定的PHE算法可以用于实现门限签名相关方案已在集团密钥管理系统落地。
5同态秘密分享
同态秘密分享是一种前沿的安全计算技术可以用来大幅降低安全计算的交互通信量。具有特定代数结构的PHE方案经过特殊设计可以用来实现同态秘密分享具有广阔的应用前景。
6隐私集合求交
使用PHE结合多项式的方法可构造出PSI协议。 三、最著名的半同态加密方案Paillier
Paillier是一个支持加法同态的公钥密码系统由Paillier在1999年的欧密会EUROCRYPT上首次提出。此后在PKC01中提出了Paillier方案的简化版本是当前Paillier方案的最优方案。在众多PHE方案中Paillier方案由于效率较高、安全性证明完备的特点在各大顶会和实际应用中被广泛使用是隐私计算场景中最常用的PHE实例化方案之一。
其他的支持加法同态的密码系统还有DGK、OU和基于格密码的方案等。其中DGK方案的密文空间相比Paillier更小加解密效率更高但由于算法的正确性和安全性在学术界没有得到广泛研究和验证且实验表明算法的加解密部分存在缺陷不推荐在工业界代码中使用。OU和基于格的加法同态计算效率更高也是PHE不错的候选项。其中OU在方案中的使用频率相对较低而基于格的方案密文大小较大在一些特定场景有自身的优势。 四、Paillier原理
1.加法同态加密定义 在描述具体方案之前我们先定义加法PHE。首先列举方案具有的所有算法。 KeyGen()密钥生成算法。用于产生加密数据的公钥PKPublic Key和私钥SKSecret Key以及一些公开常数PPPublic Parameter Encrypt()加密算法。使用PK对用户数据Data进行加密得到密文CTCiphertext Decrypt()解密算法。用于解密得到数据原文PTPlaintext。
HE除了加解密以外还具有在密文上进行处理的能力所以还应拥有“处理”算法。对于加法PHE支持的算法有同态加以及同态标量乘标量乘法可看作多次加法。 Add()同态加算法。输入两个CT进行同态加运算。 ScalaMul()同态标量乘算法。输入一个CT和一个标量PT计算CT的标量乘结果。
2.Paillier算法原理
密钥生成 加密 解密 同态加法 同态标量乘法 加解密正确性 同态加法正确性 同态标量乘法正确性 注意明文的标量乘法是加密域的指数运算。
安全性
Paillier方案满足加密方案的标准安全定义语义安全即在选择明文攻击下的密文的不可区分性IND-CPA。直观地说就是密文不会泄露明文中的任意信息。方案安全性可以归约到判定性合数剩余假设Decisional Composite Residuosity Assumption, DCRA即给定一个合数n和整数z判定z是否在n^2下是否是n次剩余是困难的。这个假设经过了几十年的充分研究到目前为止还没有多项式时间的算法可以攻破所以Paillier加密方案的安全性被认为相当可靠。 五、Python-Paillier算法演示
我们使用了 Python 实现的 paillier 算法来演示一些性质。你可以使用如下命令安装对应库
pip install phe下面我们使用 phe 演示 paillier 的同态加法和标量乘法的性质 Benchmark key generation, encryption and decryption.
import random
import resource
import time
import phe.paillier as paillierdef bench_encrypt(pubkey, nums):for num in nums:pubkey.encrypt(num)def bench_decrypt(prikey, nums):for num in nums:prikey.decrypt(num)def bench_add(nums1, nums2):for num1, num2 in zip(nums1, nums2):num1 num2def bench_mul(nums1, nums2):for num1, num2 in zip(nums1, nums2):num1 * num2def time_method(method, *args):start time.time()method(*args)return time.time() - startdef bench_time(test_size, key_size128):print(*50)print(Paillier Benchmarks with key size of {} bits.format(key_size))pubkey, prikey paillier.generate_paillier_keypair(n_lengthkey_size)nums1 [random.random() for _ in range(test_size)]nums2 [random.random() for _ in range(test_size)]nums1_enc [pubkey.encrypt(n) for n in nums1]nums2_enc [pubkey.encrypt(n) for n in nums2]ones [1.0 for _ in range(test_size)]times [time_method(bench_encrypt, pubkey, nums1),time_method(bench_decrypt, prikey, nums1_enc),time_method(bench_add, nums1_enc, nums2),time_method(bench_add, nums1_enc, nums2_enc),time_method(bench_add, nums1_enc, ones),time_method(bench_mul, nums1_enc, nums2)]times [t / test_size for t in times]ops [int(1.0 / t) for t in times]print(operation: time in seconds (# operations per second)\nencrypt: {:.6f} s ({} ops/s)\ndecrypt: {:.6f} s ({} ops/s)\nadd unencrypted and encrypted: {:.6f} s ({} ops/s)\nadd encrypted and encrypted: {:.6f} s ({} ops/s)\nadd encrypted and 1: {:.6f} s ({} ops/s)\nmultiply encrypted and unencrypted: {:.6f} s ({} ops/s).format(times[0], ops[0], times[1], ops[1], times[2], ops[2],times[3], ops[3], times[4], ops[4], times[5], ops[5]))return timesdef bench_mem(test_size):r_init resource.getrusage(resource.RUSAGE_SELF).ru_maxrsspubkey, prikey paillier.generate_paillier_keypair()nums []for i in range(test_size):if not i % 10000:# This is probably KB (i.e. 1000 bytes) when run on linuxr resource.getrusage(resource.RUSAGE_SELF).ru_maxrss - r_initprint(Memory usage for {:,} encrypted numbers {:,} ({:.4f} per number).format(i, r, i and r / i))nums.append(pubkey.encrypt(random.random()))# bench_mem(1000000)
# NOTE: this will take a long timetimes []
key_sizes [128, 256, 512, 1024, 2048, 4096]
for key_size in key_sizes:times.append(bench_time(1000, key_size))
Benchmarks
