网站新功能演示用什么技术做的,安装字体怎么在wordpress,app软件定制聚顶科技好,企业建设网站有什么作用我们前面有谈到《Paillier半同态加密算法》#xff0c;半同态加密算法除了支持密文加法运算的 Paillier 算法#xff0c;还有支持密文乘法计算的 RSA 算法#xff0c;早期的PSI(隐私求交)和PIR(匿踪查询)都有使用基于RSA盲签名技术来实现。今天我们来谈谈能够有效支持任意函… 我们前面有谈到《Paillier半同态加密算法》半同态加密算法除了支持密文加法运算的 Paillier 算法还有支持密文乘法计算的 RSA 算法早期的PSI(隐私求交)和PIR(匿踪查询)都有使用基于RSA盲签名技术来实现。今天我们来谈谈能够有效支持任意函数密文计算的全同态加密算法 (fully homomorphic encryption, FHE) 。鉴于全同态加密的强大功能一经提出便成为密码界的公开问题被誉为“密码学圣杯”。目前可以构造全同态加密的密码学假设主要有理想格上的理想陪集问题(Ideal Coset ProblemICP)、整数上的近似最大公因子问题(Approximate Greatest Common Devisior, AGCD)、带错学习问题(Learning with ErrorsLWE)等等。 什么是全同态
加密能让敏感信息在存储或传输时受到保护。但是标准加密技术要求数据解密才能操作。同态加密背后的想法是不解密并直接计算加密数据。这一名字来自于数学概念同态性Homomorphism一个集合的元素在保持原有元素间关系的情况下转换为另一集合的元素。全同态加密Fully Homomorphic Encryption简称FHE是一种创新的加密技术它可以实现在不解密的情况下对加密数据进行任意计算并得到与明文计算结果相同的加密结果。而我们说的“全”同态需要它能同时支持密文的加法和乘法因为所有的程序都能表示为电路的加法和乘法。 全同态加密方案可以解释为这样一种加密方案给定一些密文对明文的加法乘法操作都可以通过直接在密文上进行且无需要解密。
记全同态加密方案为共有4个算法密钥生成算法KeyGen、加密算法Enc、解密算法Dec、同态运算算法Eval其主要工作流程为
(1) 给定安全参数运行密钥生成算法 生成公钥私钥同态计算公钥。
(2) 给定明文和公钥 对 运行加密算法 生成密文。
(3) 给定函数和一些密文同态计算公钥运行同态运算算法获得密文在经过函数同态运算的密文结果。
(4)用私钥对密文运行解密算法获得相应的明文。
其中第(3)步的同态运算算法就是同态加密方案的核心对Eval输入密文可以实现任意函数的计算更进一步还可以计算解密函数这也是构造全同态加密方案的重要途径。
一个安全且合理的全同态加密方案具有4个安全性质正确性语义安全性同态性紧凑性。 全同态发展历史
2009 年Gentry首次给出了全同态加密算法的一个理论可行的蓝图这是对全同态加密算法探索的第一个重大突破。在 Gentry 工作的基础上全同态加密研究得到飞速发展包括更高的计算效率、更一般的困难性假设以及更广泛的应用在内的一系列改进工作纷纷涌现。自 2009 年 Gentry 的突破性工作至今全同态加密算法根据其构造方法可划分为四代。 第一代以 Gentry 基于理想格的方案以及 van Dijk 等基于整数的方案为代表。Gentry的全同态加密方案找到了理想格这个既支持同态加法又支持同态乘法的工具还开创性地提出了自举的思想使得全同态加密方案可以通过类同态加密方案构造。但这一代算法的通病是错误增长速度过快对算法的安全性和效率有较大负面影响。
第二代全同态加密算法起源于 2011 年 Brakerski-Vaikuntanathan 以及 Brakerski 等的工作这一代算法基于格困难问题使用了比第一代算法更通用的安全假设、更优的错误控制技术、更好的明文编码技术大幅改进了密文计算效率。它率先提出了密钥切换操作控制密文乘法的维数扩展、模切换操作控制噪声增长速度的想法。在此基础上后续的同态方案对BV11的效率和噪声控制进行了优化并设计了适配的自举算法。
第三代全同态加密算法的研究开始于 Gentry 等的工作由Gentry、Sahai和Waters提出了基于矩阵的近似特征向量技术的同态加密方案这一代算法使用了与第二代不同的构造模式在控制错误增长方面具有很好的潜力。它的技术特点是使用了矩阵的密文形式矩阵密文做乘法避免了向量密文的维数扩张问题同时将乘法噪声的增长速度由指数级降低到线性级。
第四代全同态加密算法以 CKKS (Cheon-Kim-Kim-Song) 算法为代表其核心思路是使用近似计算取代原有全同态加密算法中的精确计算以取得更高的计算效率。它适用于一些不需要精确计算的场景在自举操作中用多项式函数近似计算替代了精确的比特提取。
下图展示了4类全同态方案诞生的时间顺序括号内列举了其分支下的重要论文箭头表示两类方案存在一定的相关性但发表时间有先后BGV方案继承了Gentry类方案的主要思想但方案构造的基础假设不同控制噪声的技术也不同。GSW方案与BGV的基础假设相同但改变了密文结构CKKS方案的密文结构、同态操作与BGV基本相同但消息空间不同、适用运算场景不同。 全同态加密的不同技术路线分支及其代表性方案 第一代全同态加密Gentry 的技术路线
Gentry 开创性的给出了基于理想格设计 FHE 的技术路线算法的安全性基于理想格上的稀疏子集和问题(sparsesubset sum problem,SSSP)。此后, Gentry 受到了 van Dijk 等工作的启发在其博士论文中设计了基于整数全同态加密算法的雏形这一工作在他们随后的论文中得以完善算法基本原理如下
令大奇数 表示整数加密方案的私钥对于明文比特 其对应的密文 。当随机选取整数 、 满足时密文 与私钥 的整数倍 接近。因此可通过对密文执行模 运算得到 再对结果模 2 得到 从而实现解密。
对于上述整数加密方案可以对两个相同密钥加密的密文执行加法或乘法运算即有 令 , 则与原密文结构相似且满足: 其中表示某个整数。因此当初始错误 相对于 p足够小时, 则密文加法和乘法的结果仍可正确地解密。也就是说该整数加密方案可支持次数较低的多项式密文运算所得结果解密后与对明文比特执行在上的多项式运算一致。van Dijk 等证明了该方案的安全性可以归约到近似的最大公约数问题保证了算法的可证明安全性。
上述算法虽然能在一定程度上实现同态运算但不满足紧凑性即密文的大小随着评估函数次数增大。同时该算法仅支持较低次数的多项式计算这是由于算法中的错误随着乘法次数快速增长当错误大于p/2时算法就无法正确解密。van Dijk 等提出了一种解决紧凑性问题的方法: 首先公开多个不同长度的p的倍数再使用这些公开参数进行模数转换来控制密文的增长。对于错误增长导致解密错误的问题则需要使用自举技术 (bootstrapping) 来加以解决。
自举技术
Gentry 在其开创性工作中提出: “对于任意的同态加密算法若算法支持评估其自身的解密函数电路 (以及一个额外的与非门)则该算法可以转换为一个全同态加密算法。” 这句话中所提出的 “评估自身的解密函数电路” 指的正是自举技术。因此自举技术是 Gentry 提出的全同态算法技术路线中的核心也是当前延续 Gentry 技术路线发展而来的三代全同态加密算法实现全同态计算的关键。具体来说对于任意的密文考虑以下函数: 函数的输入是私钥用该私钥解密密文得到明文再输出的与非结果。如果同态加密的密文计算深度能够支持对任意密文对执行函数评估则该同态加密方案为可自举的方案能够转化为全同态方案。
第一代全同态加密的特点
第一代全同态加密的主要工作有 Gentry 基于理想格的方案、van Dijk 等基于整数的方案及其变种。这些方案的普遍缺陷是错误增长速度过快限制了同态计算的深度。具体来说对于初始错误为 的密文经过次数为 d 的多项式运算后其结果中蕴含的错误大小约为 。尽管这些算法的解密函数深度较浅但快速增长的错误依然限制了它们对自身解密函数的评估由此引起的自举困难降低了第一代全同态加密算法的实用价值。 第二代全同态加密BV 算法的技术路线
2011 年Brakerski 与 Vaikuntanathan 给出了基于 LWE 及 RLWE 问题的全同态加密算法的构造方法标志着第二代全同态加密算法的开端其基本思想如下:
对于一个 LWE 问题的样本 以及私钥 。令 表示明文其加密后的密文为: 其中 表示采样自错误分布 的随机错误。当解密时通过以下公式完成解密运算: 。容易验证当错误 时以上加解密流程可以正确得到明文。 若将 记为 则有 。
对于两个相同密钥加密的明文
则有 注意到对于相同密钥加密的明文其加法同态性是显然的而它们的乘积可以视为一组以为私钥的 LWE 问题样本若能够将乘积中对应的项转换为密钥 的表达式则可以将密文乘法 的结果转换为 LWE 问题的标准形式从而进一步执行其他的同态计算因此这一转换的过程是第二代全同态加密算法的关键技术被称为重线性化 (re-linearization technique) 或密钥转换技术 (key switching technique)。
密钥转换和模转换技术
重线性化或密钥转换技术的提出可以解决基于 LWE/RLWE 问题的第二代全同态加密算法在计算密文乘法时密钥规模以平方的规模快速增大的问题其核心思想是通过将原密钥中的每一项及由这些项所组成的全部二次项使用新密钥加密使原密钥加密下的密文乘法的结果可通过新密钥的线性函数表示此时可将结果转换为以新密钥加密的标准 LWE 问题样本。
此外Brakerski 还提出了一项显著降低全同态加密错误增长速度的技术称之为模转换技术 (modulus switching techinque)。其核心思想是对于 上的密文 通过令 中的各项分别乘以 并取整可以将密文 转换为上的密文此时因同态加密积累的错误总量也同步减少了约 倍。通过精心选取参数 与 的大小能够将错误的增长速度控制在较小的规模。
第二代全同态加密的特点
第二代全同态加密算法以 2011 年 Brakerski 等 的工作为代表。第二代算法在第一代算法的基础上实现了多个实用性的优化包括更好的错误增长控制技术、 更标准的困难性假设以及多项效率优化技术。利用错误增长控制技术可使第二代全同态加密算法中错误增长速度从密文计算深度的线性量级降为对数量级这一技术是 “分层” 同态算法以及全同态算法得以实用化的关键。第二代全同态加密算法使用的标准困难问题假设包括容错学习问题 (learning with errors) 或 NTRU 问题等这些问题的困难性有着更完备的归约并经历了长时间的考验, 能够为 全同态加密算法奠定更牢固的安全性基础。第二代算法在效率优化方面的改进主要包括明文打包技术 (packing) 以及自举效率优化这些优化技术大幅改进了全同态加密算法的计算效率使算法的密文计算效率较明文计算效率在渐进复杂度上仅付出约的额外开销其中 表示安全强度 为常数。 第三代全同态加密GSW 算法的技术路线
第二代全同态加密算法的核心技术是密钥转换和模转换。2013 年Gentry 等给出了一种基于 LWE/RLWE 问题设计全同态加密算法的新思路在他们的技术路线中无需使用密钥转换和模转换技术仍可以有效控制同态加密的错误增长其主要设计思路如下:
对于一个 LWE 问题的样本令公钥为 私钥为 。则有 。
令 表示明文其加密后的密文为 其中 是 域上的随机矩阵 表示块对角矩阵。
解密时需要计算当且较小时, 则有。因此 ,即可根据已知的私钥 获得明文。
对于两个相同密钥加密的明文 , 容易观察到: 。可知能够满足加法同态性.
而对于密文乘法则需要定义非对称乘法规则如下: 。
即 所得结果对应于两个明文乘积的密文。
非对称密文乘法
第三代全同态加密算法的核心是非对称乘法该技术利用了以下原理: 对于任意的整数 可将其表示为一组二进制向量 即 其中 。同理对于任意向量 ,可以将 扩展为块对角矩阵 满足 其中 表示 中每个元素的二进制展开记为 显然有 。此外由于 中各元素均取自 {01}可知该矩阵的范数较小这是确保上述非对称乘法成立的关键。
第三代全同态加密的特点
2013 年Gentry 等给出了一种不同于第二代全同态加密算法的设计思路其核心思想是采用非对称的乘法降低错误增长速度。具体来说该方案的同态乘法具有非对称性即 所得的密文不同于 所得密文。在该同态乘法中错误的增长速度也与乘法顺序有关被乘数对错误增长速度的影响较乘数更大。利用这一性质可进一步降低密文乘法的错误增长速度从而使第三代全同态算法在参数选取和安全性归约上更具优势、算法流程更加简洁。 第四代全同态加密CKKS 算法的技术路线
第四代全同态算法以 CKKS 算法为代表其加解密流程与第二代全同态加密算法类似主要区别在于其采取了近似计算的策略即所得计算结果附带一定的误差这一特点虽然降低了算法的计算精度但大幅提高了算法的运算效率因此在一些全同态分类中将 CKKS算法及其改进称为第四代全同态加密算法。
该算法的设计思想如下
对于一个 LWE 问题的样本 则公钥为 私钥为 评估密钥为。令 表示明文多项式其加密后的密文为:
其中表示以 0.5 的概率输出 1 或 −1 的随机函数。解密时则需要计算 。
对于两个相同密钥加密的明文
容易验证其加法同态性: 。
对于乘法令 其中
可以验证 即 。
第四代全同态加密的特点
在经典的同态加密算法中为获得准确的计算结果通常有两类明文编码方式, 一种利用密文空间中的高比特位保存明文另一种利用密文空间中的低比特位保存明文。例如: 明文空间模 t密文空间模 q则前者的解密运算可表示为 后者的解密运算则可表示为。为确保解密正确性, 两者均要求错误 e 较小, 这一条件限制了同态加密算法的参数选取与计算深度。而在 CKKS 算法中解密运算表示为此时错误 e 与明文 m 直接求和无法通过取整计算将错误从结果中消去。但在另一方面由于放弃计算 m 的精确结果CKKS 算法仅需考虑 e 与 m 的相对大小 (即相对误差)因此能够在参数选取和计算过程中采取更直接的方法控制错误的增长速度如使用模转换技术同步减小明文和错误从而令错误大小随算法深度呈线性增长而非指数增长。 小结
当前BGV (Brakerski-Gentry-Vaikuntanathan)BFV (Brakerski-Fan-Vercauteren)TFHE (fully homomorphic encryption over the torus) 和 CKKS 是应用最广泛的全同态算法涵盖了第二到四代全同态加密构造方案值得指出的是全同态加密算法的四代构造并非改进与替代的关系而是各具特点和适用场景正因如此当前学术界呈现出上述四种算法同步发展的现状。总的来说, 第二代和第四代全同态加密算法均可通过高效的明文打包技术实现对多个明文的并行计算非常适合计算量较大的数值计算其中第二代适用于需要精确计算的场景而第四代面向近似计算场景第三代全同态加密算法不支持明文打包但其设计结构对于逻辑运算友好能够高效地完成逻辑门形式的密文运算如下表所示。 全同态常用加密库 Concretehttps://github.com/zama-ai/concrete 使用Rust语言实现了Zama的TFHE变体。Concrete的密码算法基于LWE问题和RLWE问题研究证明基于这类问题的密码算法是抗量子的。 HElibhttps://github.com/HomEnc/HElib HElib 是一个实现同态加密HE的开源代码库。目前实现的方案是包括带有引导的 Brakerski-Gentry-Vaikuntanathan (BGV) 方案和 Cheon-Kim-Kim-Song (CKKS) 的近似数方案的实现仓库使用了许多优化技术使同态运算更快。 SEALhttps://github.com/microsoft/SEAL Microsoft SEAL 是一个易于使用的开源MIT 许可同态加密库由 Microsoft 的密码学和隐私研究小组开发。Microsoft SEAL 是用现代标准 C 编写的易于在许多不同的环境中编译和运行。 SEAL-pythonhttps://github.com/Huelse/SEAL-Python/ SEAL-python使用pybind11为SEAL的C代码提供python接口方便开发者使用python进行开发。 Palisade: https://gitlab.com/palisade Palisade是一个开源的同态加密和安全多方计算库由新墨西哥大学和Sandia国家实验室开发。它支持多种同态加密方案包括全同态加密、部分同态加密和同态签名等并提供了C和Python的API接口。 PALISADE-Python是Palisade同态加密库的Python绑定。它为Python开发者提供了使用Palisade库进行同态加密的能力。 Lattigohttps://github.com/tuneinsight/lattigo Lattigo实现了基于RLWE的同态加密方案以及基于同态加密的多方安全计算协议。Lattigo使用go语言实现。Lattigo 旨在支持分布式系统和微服务架构中的 HE选用go是因为其并发模型和可移植性。 HEAANhttps://github.com/snucrypto/HEAAN HEAAN 是实现支持定点算法的同态加密 (HE) 的软件库。该库支持有理数之间的近似运算。近似误差取决于一些参数与浮点运算误差几乎相同。 cuFHEhttps://github.com/vernamlab/cuFHE 支持GPU加速的全同态加密仓库。它实现了 Chillotti 等人提出的 TFHE 方案 [CGGI16][CGGI17]。使用英伟达泰坦Xp显卡进行实验比使用CPU进行计算的TFHE方案快20多倍。 cuYASHEhttps://github.com/cuyashe-library/cuyashe cuYASHE 是第一个在 GPGPU 上实现水平全同态方案 YASHE。该库采用 CUDA 平台以及代数技术如 CRT、FFT 以及多项式和模约简的优化获得显了著的性能改进。与CPU、GPU 和 FPGA 中最先进的实现方案相比他有更优异的性能。特别是多项式乘法有 6 到 35 倍的加速。 FINALhttps://github.com/KULeuven-COSIC/FINAL FINAL实现了论文 FINAL: Faster FHE instantiated with NTRU and LWE提出的全同态加密方案。 NuFHEhttps://github.com/nucypher/nufhe NuFHE是基于GPU实现的环上全同态加密方案。该库使用 CUDA 和 OpenCL 实现了 TFHE 的完全同态加密算法。与在内部使用 FFT 来加速多项式乘法的 TFHE 不同nufhe 可以使用 FFT 或纯整数 NTT有限域上的类似 DFT 的变换。后者基于 cuFHE 的算术运算和 NTT 方案。 OpenFHEhttps://github.com/openfheorg/openfhe-development OpenFHE 是一个开源 FHE 库包括所有常见 FHE 方案的有效实现。 SparkFHEhttps://github.com/SpiRITlab/spark Spark提供了基于全同态加密算法的分布式数据流。 TenSEALhttps://github.com/OpenMined/TenSEAL TenSEAL 是一个用于对张量进行同态加密操作的库构建在 Microsoft SEAL 之上。它通过 Python API 提供易用性同时通过使用 C 实现其大部分操作来保持效率。 HEhubhttps://github.com/primihub/HEhub 由原语科技推出的同态加密开源算法库 HEhub作为 PrimiHub 开源生态的一部分。HEhub 是一个易于使用可扩展性强且性能优秀的密码学算法库致力于汇集各类同态加密算法及其应用。其目前包含了 BGV、CKKS、TFHE 等全同态加密算法并将进一步集成更多同态加密方案、常用的计算逻辑以及上层应用接口。 全同态加密算法的选择 对BFV、BGV、CKKS、FHEW、TFHE五种全同态协议进行比较可归类如下 BFV/BGV适合处理小区间上的整数向量无精度损失 CKKS适合处理浮点数向量精度控制在1e-6~1e-8 FHEW/TFHE适合处理分段函数/非连续函数精度控制在1e-4。 全同态加密应用场景
外包存储及外包计算
同态加密最直接的应用场景是外包计算。该应用中云端提供大规模存储和高性能计算服务客户端 (如: 小型企业) 将私有数据以同态加密形式保存在云端。云端可利用自身的计算能力和同态加密性质直接对这些密文数据执行操作并将密文结果返回给客户端客户端对密文解密即可获得需要的计算结果。这里同态加密算法提供了一种简洁的云计算安全解决方案既保护了云上数据的安全性又使云平台具备了对云上数据操作的能力。
隐私信息检索及查询
另一个全同态加密的典型应用场景是面向数据库或搜索引擎的隐私信息查询。该应用中, 服务器拥有大型数据库并提供检索服务客户端可借助全同态加密技术实现对该数据库的隐私信息检索 (private information retrieval) 既获取服务器检索数据又避免服务器得到关于查询条目的任何信息。具体来说, 服务器可利用数据库构造密文检索函数客户端加密需要查询的索引 i 并发送给服务器服务器使用评估函数得到的密文结果并将其返回客户端客户端解密后即达到隐私信息检索的目的。类似做法也可应用于更复杂的查询操作 (如数据库 SQL 查询、 搜索引擎的自由格式查询等) 以满足更实用化的隐私检索和查询任务的需要。
通用两方安全计算
外包计算和隐私信息检索都属于安全多方计算的研究范畴可看作通用安全多方计算研究中的两种特例。事实上一般化的安全多方计算模型也可以通过全同态加密算法实现。在通用的两方安全计算模型中参与方 A 持有输入 x参与方 B 持有输入 y两方共同计算某个已知函数 F参与方 A 能获得结果 F(xy)参与方 B 得不到任何额外信息。在半诚实敌手模型中参与方 A 可使用其公钥加密输入 x 并发送给 B参与方 B 评估函数 并将密文结果返 回给 A。这就实现了半诚实假设下基于全同态加密的通用两方安全计算模型。在这个过程中同态加密算法的语义安全性 (semantic security) 保证了参与方 B 无法获取额外信息。使用隐藏评估函数的同态加密方案可以防止参与方 A 获取除结果 F(xy) 外的额外信息。利用标准的技术可以将该协议进一步转化为恶意假设下的安全多方计算协议。
除此之外全同态加密在 Web3 中可以用于交易隐私保护、AI 隐私保护和隐私保护协处理器。其中尤其看好隐私保护 EVM它比现存的环签名、混币技术和 ZK 都要更灵活更适配 EVM。 关于全同态加密的学习路线可参考陈智罡博士 - 如何学习全同态加密(致远老师-知乎) 和 全同态加密学习路线(六三老师-知乎) 。
