同态加密的最新进展 在信号加密领域可能的未来外文翻译资料

英语原文共 10 页，剩余内容已隐藏，支付完成后下载完整资料

同态加密的最新进展

在信号加密领域可能的未来

自从Rivest等人引入了隐私同态的概念以来， 在20世纪70年代末，高效和安全的加密方案的设计允许在加密域中执行一般计算已经是加密社区的圣杯之一。 尽管有了许多答案，设计这样一个强大的原始的问题仍然保持开放，直到完全同态加密（FHE）计划由Gentry在21世纪后期出版的理论突破。 从那时起，进展快速，现在可以合理地说，在不久的将来，基于实际同态加密的计算将成为现实。

这篇文章调查了（某种程度）FHE从加密和软件工程的角度来看的最新进展。 它还提供了实用的实验结果与一个（迄今为止）最有希望的一个实现有些FHE方案......

简介

传统上，数据机密性是密码学家的问题，并且通过设计和使用加密方案来解决。 但是，尽管存在对诸如RSA或高级加密标准（AES）的常见加密方法的永久需要，但是在过去30年中对特定方案的兴趣已经增长并且扩展到越来越多的领域，包括信号处理。 这尤其是由于多媒体内容分发平台的部署，生物测定技术的发展以及云计算模型对越来越关键的应用的广泛采用。

在这样的应用中，一些方（通常是最终用户）可能希望保留它们外包的数据或其对服务器的请求的隐私。作为一个直接的例子，最终用户可能希望保留他的电子邮件的机密性，同时仍然能够设置过滤器或执行搜索。通常，这样的隐私问题在加密方案的帮助下解决。这导致需要加密技术，其必须符合云中的外包加密数据的存储和处理，私人信息检索，（加密）数据的（私人）搜索或分析，代理广播的加密信号的处理等。图1-3示出了可以组合并包含这样的使用情况的一些通用情形。当然，将必须处理这样的加密数据或请求的服务器必须提供好像和没有加密的相关结果。从技术上讲，服务器提供的结果必须解密。由客户端使用为了一致性，如果对原始数据执行，解密结果必须等于预期的计算值。

【图一】需要在外包计算的场景中处理加密数据。 例如，对私有图像或更多应用一次性增强算法从而实现私人语音呼叫的自动即时翻译。

【图2】需要保持外包数据的隐私，同时能够继续对它们的一些请求。 一个典型的例子是关于外包加密电子邮件箱的关键字搜索或过滤。

一些关于同态加密的故事

1978年，Rivest，Adleman和Dertouzos提出通过现在称为同态加密来解决这些隐私问题[28]。 从这篇具有启发性的论文开始，高效和安全的同形加密方案的设计已经成为加密社区的圣杯之一。

在深入研究主题之前，要着重注意的是，出于安全原因，这样的加密方案必然是概率性的。 这意味着对于给定的加密密钥，每个纯文本可以在几个不同的密文中加密。 这意味着可能的密文集合明显大于可能的纯文本集合。 换句话说，这意味着密文比纯文本更长。 对于给定的概率加密方案，这两个长度之间的比率称为方案的扩展。 当然，设计者试图针对给定的安全级别提出具有最小可能扩展的方案。

从1978年到2008年，已经出版了几个同态加密方案，例如，着名的Paillier方案及其派生，它能够处理加密数据，但一次只用一种算法（加法或乘法）[15]。 2009年，Gentry提出了第一个尚未破碎的FHE方案[16]。 FHE是指能够在加密域中处理加法和乘法的密码系统。使用这样的方案，可以计算关于加密数据的任何多项式函数。这真的是一个突破经过30年的巨大努力，因为它开辟了道路到许多更强大的实际应用程序比以前。然而，由于它

巨大的算法复杂性，大密钥大小和密文扩展，当前的FHE方案在实践中仍然没有效率。自2009年以来，许多出版物提供了变体和改进。特别地，已经提出了几个所谓的有些FHE密码系统，其允许任何数目的加法，但有限数目的乘法[2]，[19]。这些方案非常有趣，因为它们不如完全同态的那些复杂，并且能够处理对于大多数应用而言足够的多个乘法。因此，它们今天被认为是实际应用中最有希望的方案。

但是尽管有这些有希望的特性，但是它们的开销仍然太高，使得它们在实践中不能直接使用。 主要有两种方法来提高效率。 第一个是提出不复杂的新的棘手变体。另一个是找到一些狡猾的方式来实现它们。 不幸的是，很少的实现已经发布和公开讨论，以衡量我们在实际应用中的使用程度。 本文提出的原始实验结果有助于回答这个精确的问题。

【图3】需要对公共数据执行私有请求。 典型的例子是深度包检测而不显示，例如跟踪IP地址。

对信号处理有什么影响？

在加密域中处理信号是一个重要的挑战。 近年来，越来越多的研究者设计了专门针对许多应用的定制解决方案。尽管没有详尽的描述，可以提及隐私保护表面识别[11]，隐私保护电路信号分类[4]，生物识别数据的隐私保护[ 14]，买方 - 卖方协议[22]，[26]，[20]和零知识水印检测[1]，[25]，[29]。 同时，其他工作开发了一些通用工具，用于处理加密信号上的某些特定操作，这在许多应用中是有用的，例如Gram-Schmidt正交化[13]，离散色变换计算[5]和离散傅里叶变换计算[6]。 最后，可以提及对加密信号的处理的一般性讨论[12]，并且尝试找到用于这种处理的适当表示，如[7]。

这些出版物依赖于常规同态加密。因此，在需要时，对涉及加法和乘法的加密数据函数的计算是非常困难的。 它需要在广告hocmanner中使用多元计算技术来线性化计算。 这要求使用重的协议，准确地为每个应用程序。 此外，这些协议需要在各方之间进行许多交互才能正确地完成工作。 关于信号处理应用中的隐私问题和同态加密的更多细节可以帮助解决它们，我们请读者参考[23]。

利用可访问（有些）FHE方案，可以直接计算多项式函数，而不需要线性化或多方计算技术。 当然，支付的费用将直接与使用的（有点）FHE方案的复杂性有关。 但根据最近的工作，这种方案的复杂性目前正在下降比预期，甚至一年前。 还有很多工作要做一个非常有效的方案，但每个步骤推进实际应用比以前更近。

许多算法改进已经并将被公布以使（有点）FHE方案的实现更容易处理。 然而，提供这些方案的实际实施仍然是一个主要挑战。但是，这些方案很难理解，甚至难以实施。 它解释了为什么现在有很少的实现可用。 另一个面临的困难是他们的进步和改进。 因此，实现需要像方案一样快速地发展，以利用每个重要的改进。

在本文中，我们专注于Brakerski-Gentry-Vaikuntanathan（BGV）方案[8]，这似乎是今天最有价值的FHE方案，但是在文献中讨论的单个先前实现集中在AES的评估[19]。 在解释为什么在实践中更有意义地使用某些FHE方案而不是FHE方案，我们简要呈现BGV。 由于它操作位，并且，在大多数应用程序中，我们需要处理整数，我们然后讨论如何处理整数而不是位。 在下一节中，提出了一种实现框架，以在实现处理加密数据的函数时最小化程序员的设计工作。 最后，我们提供BGV方案的一般实现的第一个实际结果，并与其他方案的少数其他可用实现进行比较。 这最后一节的目的是向那些具有关于这种方案的实现和性能的具体数据提供。

关于完全同态加密

第一个FHE方案的效率使实用性几乎没有希望。为了理解为什么FHE方案有这么大的开销，让我们首先看看van Dijk等人在2010年提出的方案[30]。

这个方案是建立在整数。 在其对称版本中，秘密密钥是奇整数p（其中大小取决于安全性标准）。 加密一个位m！ {0,1}，我们选择随机整数q和r（由安全问题定义的范围），使得2r lt;p / 2并且设置。

c =Enc(m) =qp 2r m.

可以通过计算mod modod 2来检索明文m。

现在让我们考虑两个纯文本m1和m2以及相应的密文c1和c2。 由于FHE方案的目的是对加密数据执行计算，我们现在讨论当我们加或乘两个密文时将发生什么。

c1 c2 =(q1 q2)p 2(r1 r2) m1 m2.

解密c1 c2，需要得到m1 m2。 这是可能的条件

2(r1 r2) m1 m2 # p

被验证。 在这种情况下，我们有

c1 c2 mod p =2(r1 r2) m1 m2

可以通过计算c1 c2mod pmod2来检索m1 m2。由于我们选择r使得2r lt;p / 2，当c1和c2是“新鲜”密文时满足条件（1）。 相反，如果c 1是例如其他密文的总和，则不满足条件，并且不可能解密c 1 c 2。 当两个密文相加时，相同的现象发生得更加严重。 构建FHE方案需要通过将其保持在某一限度以确保加密来管理称为噪声的剩余随机部分[例如，2（r1 r2）]。

解决这个噪声问题的第一种方法称为引导（bootstrapping），用于Gentry的第一个FHE方案。 背后的想法是修改有些FHE方案，以便它可以同时运行自己的解密过程。 包括公钥对秘密密钥的加密，引导允许将给定密文的变换转换为对相同位加密但具有较低噪声的新密文。 不幸的是，引导意味着公钥的增长，并且用于变换密文的过程是非常重的，如在使用引导的FHEscheme的实现上公布的几个结果所示[17]。 因此，允许不用自举来评价多项式的获得方程是一个有趣的研究（即使这意味着限制我们能够管理的多项式的程度）。

最近，Brakerski et al。 （基于Brakerski和Vaikuntanathan [10]，[9]的工作）使用Aguilar等人介绍的张量积方法 [2]以一种新的替代方式，从根本上改进了该方案的性能。 基于这种方法和使用两个优化，Brakerski et al。 [8]提出了一个有些FHE方案（BGV），可以参数化计算有界度d的同态多元多项式，其中d可以虚拟选择为所需要的大。 Sincethe Bootstrapping技术在实践中很难实现，并且其在性能方面的兴趣不是显而易见的，由[8]的BGV方案所产生的解决方案似乎是本文撰写时间中最有希望的一个。

BGV方案概述

BGV是加密比特的非对称加密方案。 Likemost（有些）FHE计划，它是基于网格。 有两个版本的密码系统：一个处理整数向量[其安全性与学习错误（LWE）问题的硬度相关]，另一个具有整数多项式[其安全性与ring的硬度相关 - 学习错误（R）-LWE问题]。 简而言之， （R）-LWE问题]问题包括区分在Zq Zn＃q（分别在环A Zq / F（X）= n中）和（ai，lt;ai ，sgt; ei），其中ai和s从Zqn（或Aqn）均匀采样，ei根据高斯分布进行采样。对于（R）-LWE问题的更精确，我们引用读者[27]。 接下来，我们将关注BGV加密方案的多项式版本，这似乎更有前途的性能表现。

我们考虑多项式环A = Z [X] / F（X），其中F（X）是度数为d = 2k的循环多项式和奇数模量链q1 lt;g lt;qL及其对应的子循环Aqi = A / qiA 将具有整数系数的A的多项式映射到范围@ -qi / 2，qi / 2 @中。 实际上，Aqi中的元素将是由其系数的d向量表示的多项式。

基本加密功能

私钥Priv在A中采样。公钥Pub包括由噪声分量屏蔽的私钥：， 其中 然后从AN上的“离散”高斯分布（“离散”意味着我们从高斯分布和回合到最近的整数）采样e。 下面是一组与加密算法相关的主要功能的黑盒描述。 我们决定不包括确切的算法，以避免淹没技术描述中的重要问题。如果有兴趣，读者可以参考[8]和[18]获得精确的算法描述。

加密（Plain Text m，PublicKey Pub）：Ciphertext c

我们操作的整数需要每次加密1 b。 对于m！ {0,1}，所得到的密文c是从纯文本m，公钥Pub和随机种子（因为它是概率方案）导出的Aq L中的一对两个元素。 在下文中，在任何子字符Aqi中，密文可以被变换为一对两个元素。 在我们的实现中，每个密文携带其级别，即，指示其所在子环的信息。

解密（Ciphertext c PrivateKey Priv）：纯文本

解密函数是密文c！ Aqi和私钥，然后在范围中进行模数减少，最后进行奇偶校验测试以检索纯文本m。如在“某种完全同态加密”部分中给出的示例， 噪声必须在一定水平以下才能使解密正确。

水平切割操作

Rescale（Cipertext c）：Ciphertext cl

该函数转换密文 变成密文 所得到的密文具有降低的噪声

SwitchKey（增强Cipertext c）：密文c

两个密文的拉伸乘积导致“增强密文” 为了在中检索正则密文，我们基本上将c乘以公共矩阵（对于每个级别是不同的）。 然后我们调用Rescale函数来获取（具有低噪声）。

同形操作

Add（Ciphertext c1，Ciphertext c2）：Ciphertext csum

对于两个密文c1，c2当 和我们遵循这些步骤：

如果（例如）然后

次; （在这一点上我们有c1，c2在同一级别i1）

结束

做 （简单地通过将多项式的系数加上模qi1）

Mul（Ciphertext c1，Ciphertext c2）：Ciphertext cmul

对于两个密文c1，c2当 和我们遵循这些步骤：

如果（例如）

剩余内容已隐藏，支付完成后下载完整资料

资料编号：[137087]，资料为PDF文档或Word文档，PDF文档可免费转换为Word