信息论上安全的量子同态加密的局限性

摘要：

同态加密是一种加密的形式，这种形式能够使计算直接在加密数据上展开而不对数据进行解密。量子方法在委托计算环境中成功完成了相关的任务，这就提出了一个问题，量子技术能否可以用来实现理论上信息完全安全的同态加密。通过信息局部化的展开，我们了解到若要保持数据完全安全，那么此时完全确定的同态加密必然导致指数性爆炸的难度。

正文：

信息必须按照物理规律来表现和操作的观点带来了量子信息科学等新兴领域的繁荣发展。这种对信息处理方法的应用是多种多样的。它带来了从利用量子态提高效率的新算法和通讯协议到提高计量精度的技术等一系列的新发现。从历史上看密码学是量子信息处理第一个显示出的优于传统处理的领域之一。1984年，Bennett和Brassard为信息理论安全密钥分配引入了量子协议。虽然大多数的量子密码仍然是与量子密钥分布相似，但是随着量子协议的不断发现，该领域得到了很大的发展，量子协议增强了许多密码任务的安全性，包括数字签名、匿名通信、专用数据库查询和随机数的生成。密码系统的安全性依赖于计算难处理性，但量子算法提供了一种新的攻击密码系统的方式，这强调了信息理论安全密码学的重要性。不幸的是，并非我们所希望完成的都承认信息理论上安全的量子协议。而且事实上已经发现了许多不可行的定理，这些定理表明了量子理论本身不足以以完美的安全性去完成某些任务，如比特承诺和无提示传输。

近年来经典密码学最著名的成果之一是发现了用于完全同态计算的计算安全协议。同态加密方案允许以某种方式对数据进行加密，从而可以在不解密的情况下对数据执行某些操作。这允许用户向远程服务器提供加密数据以进行处理，而不必显示明文。这种同态加密方案的许多例子已经被熟知很多年了，但正是Gentry的开创性工作首次证明了一种完全的同态加密方案，这种方案允许对加密数据进行任意计算，而不局限于某种非通用操作。对加密数据进行通用计算的能力大大提高了同态加密的实用性，成为现代密码学中最活跃的领域之一。

经典的完全同态加密方案有一个显著的缺点，即它们的安全性依赖于计算假设。我们可以认为加密数据可由第三方进行操作，这必然排除了信息理论上的安全性。然而，经典的一次一密（纯文本位与完全随机的比特值异或）提供了一个即时的反例。任何比特翻转序列都必须通过解密步骤进行交换，因此表示可以直接在密文上执行的明文计算的非平凡集。尽管这似乎是一个相当微不足道的例子，但密码学界做了许多努力在寻找信息理论安全同态加密系统上，这支持了任意代数的操作（请参阅该领域的最新工作回顾），并尝试构造具有信息安全理论的完全同态经典加密方案。然而现有的同态加密方案只能达到近似的安全性，若要达到完全安全，则编码难度成倍上涨。

完全安全的盲计算量子协议的存在，以及最近的实验进展，都突出了量子密码技术在这一领域的发展可能性。作为加密的方式，盲量子计算和同态加密在许多方面都是相似的。这两种方式都设想了一个关于两方信息交流的情况，第一方Alice希望第二方Bob为她进行计算而不透露她的计算输入。然而，在盲计算中，Alice不仅指定了输入数据，还指定了要执行的计算，任务是利用Bob的资源来执行此计算，而不显示输入或程序。因此，当前完成此任务的协议是交互式的，需要在Alice和Bob之间进行多轮通信，这与同态加密的设置有很大的区别。

量子同态加密的思想出现于M. Liang,Quantum Inf. Proces. 12, 3675 (2013).中，它表明了一个完美的、通用的、量子同态方案不能用一次一密来构造，它提出了一个实现类似功能的交互式协议以及利用量子数据实现同态加密功能的其他加密方案。然而，这些都依赖辅助计算，因此需要Alice和Bob之间进行多轮交互，从而达到交互协议而不是简单的加密方案。量子同态加密方案确实存在于一个被称为玻色子散射的受限量子计算模型中，该模型提供有限的信息理论安全。这些方案的存在引发了一个问题，即量子技术是否可以被用来构造理论上安全的完全同态加密方案。在这里，我们通过证明量子力学不允许有效的信息理论上安全的完全同态加密完全隐藏明文来回答这个问题。为了实现这一点，我们首先将量子同态加密的概念形式化，然后通过信息局部化论证继续证明，完全隐藏Alice输入的任何此类方案都必须揭示所执行的计算，因此编码必须足够长以指定任何此类计算。对于完全同态加密方案，这意味着编码必须是指数长的，因此排除了有效的完全同态加密方案的存在，该方案完全隐藏了Alice的数据。

形式上，经典的同态加密方案由四个过程组成。第一种是密钥生成算法，它生成一个经典加密密钥、一个经典解密密钥，并可能生成一些附加的辅助密钥。第二种是使用加密密钥对输入进行加密的加密算法。第三种是使用解密密钥解密输出的解密算法。最后，给出了一种在不解密的情况下对密文进行计算的评估算法，该算法可以使用辅助密钥。对于任何允许的逻辑过程C，评估算法的结果应该是，在解密输出后，获得将C应用于未加密输入的结果。因此，完全同态加密方案是一种方案，其中C可以从所有经典电路集中自由选择。在这里，我们只考虑具有完全完整性的方案，其中评估运算符必须确定地实现所选电路。如果密文是独立于明文的密度算子，则同态加密方案具有完善的信息理论安全性。

我们将定义一个量子同态加密（QHE）方案，使用与经典情况类似的标准，并将其扩展到考虑协议内纠缠的可能性。QHE方案由四个部分组成：一个密钥生成协议，它产生一个用作加密密钥的量子态psi;_е；一个加密统一运算符U_e，它使用加密密钥态对输入态psi;_i进行加密，可能利用某些Ancilla系统，并在rho;_d状态下产生一个解密密钥；一个解密一元运算符U_d，使用密钥状态对加密状态进行解密；以及一组评估一元运算符U_c，这样在解密输出后，净效应相当于将量子电路C直接应用于初始输入状态。在这里，解密密钥是在应用加密单元时生成的。虽然这比生成相应的经典密钥的过程更为一般，但我们进行了这种概括，以允许加密密钥和解密密钥之间存在因果关系的可能性，通过无克隆定理，这可能会阻止它们同时存在。注意，我们没有指定辅助键。这是因为，在不丧失一般性的情况下，我们可以假定这个辅助密钥构成加密状态的一部分。基于该定义的加密评估解密序列如图所示。

图1：输入数据为psi;_i，输出为psi;_o的一般量子同态加密方案的示意图。状态psi;_e表示Alice密钥的初始状态，而U_e和U_d是Alice的加密和解密运算符。双方也被允许建立一个辅助系统，并获得一个共享的交互资源。Alice的解密密钥对应于将U_e应用到系统后保留的子系统。注意，没有对子系统的维数进行假设，在定理1的证明中使用的时间点T₁和T₂也显示出来。

正如我们现在证明的那样，对于这样一个方案进行确定性操作，有必要使加密状态的维数随着C可能的选择集基数的对数的增长而增长，因此不可能完全同态加密，除非编码的大小呈指数增长。为了证明这一点，我们首先证明了Griffiths的信息局部化定理的修正版本。

引理1（数据局部化）：假设S为在希尔伯特空间中表示为的偶量子系统，最初处于状态，其中和固定不变。假设rho;为U算符作用于S后的状态。如果系统B上的约化密度运算符独立于输入数据状态，对rho;取迹，那么存在一个单一的算符V使得：有，对于某些密度矩阵，独立于。

证明：为了简化符号，我们定义以及，以及用r表示的秩。我们将进一步划分希尔伯特空间：，这样的话，，表示的状态。

我们首先从条件独立于出发。这意味着当改变的值时，保持，那么也不会改变。我们考虑当只改变的值时对rho;的影响。假设的正交基为，j=1,2,hellip;,d_A1。d_A1是的维数。假设{}是的正交本征态，相应的本征值为p_k。

对于每一个态，有1le;jle;da，我们展开用U算符作用下系统的态：

将可能出现的复杂相吸收于上式所定义的，是的正交本征态，相应的本征值为p_k，等式右边的展开式Eq（1）是对的施密特扩张。对于任何固定的j都是正交的。因此我们得到.

现在考虑一下这样的情况，我们保持对和的输入不变,同时将的输入状态形式改为,其中jne;jrsquo;。在这样的情况下有：

因为上的输出约化密度运算符仍然是，等式（2）的右边应该是施密特展开式，施密特系数仍然是。因此必须已经归一化，并且这些状态对于k的不同值必须是正交的，由此我们得到

因此=0。

相似的，通过,并考虑到。因此当时，。以上的条件可以简单表示为.

因此{}组成了一个正交集合，可以将子空间和为具有正交基矢和使得，以及

，j=1,2,hellip;,d_A1 ,k=1,2,hellip;,r. (4)

对于一般输入状态，当,可得

. （5）

现在，使Vrsquo;:作一个等距变换有：

则让V成为Vrsquo;的任意推广，在上成为完整的统一体。并使

对于某些独立于的密度算符，正如引理所要求。

引理1表明，在任何具有完全信息论安全性的量子同态加密方案中，计算都必须发生在Alice那边。下面的定理将说明这种现象，表明加密状态必须包含足够的信息来识别以前应用于它的任何算符。

定理1. 设Q为一个量子同态加密方案，具有完善的信息理论安全性，其中包含加密算子U_e和解密算子U_d以及一组评价单元。假设是Bob在应用与量子线路C（Crsquo;）相对应的评估单元U_c（U_crsquo;）（即图1中的时间t2）后发送给Alice的状态。此时，若b与brsquo;执行不同的运算，则与必须是正交的。

证明：为了更直观地了解此过程，我们将从Alice与Bob两方识别加密、电路评估、和解密过程，正如图1所示那样，我们首先分析Alice和Bob联合系统的状态，在Alice将其编码的数据发送给Bob之后，这时在图1中标记为时间t1。设为Alice（Bob）子系统此时的状态。从这一节点起，所有的信息交流都从Bob传向Alice。Q在理论上是完全信息安全，则意味着独立于。根据引理1，存在一个单一算符V，对于合适的，使得：

现在，在Bob将消息发回给Alice之后再考虑这个系统。即图1中的时间t2。根据前面的分析，此时系统的状态可以写为

其中表示Bob的信息。一般来说，密度矩阵不能被假设为纯的，因为Bob可能发送了一条仍然处于纠缠态的信息给其系统。在这里，V仅作用于系统中Alice在收到Bob的信息之前所拥有的部分，而单位算符则作用于Bob的信息。

评估单元U_c实现特定的线路C意味着：

其中是与量子线路C相对应的一元算符，而只是辅助系统的一种状态。

使，则对于任意的C和，有：

状态以及算符是独立于C的，在M. A. Nielsen and I. L. Chuang, Phys. Rev. Lett. 79, 321 (1997)所述语言中，这对应于可编程量子门组，其中作为实现单一运算符的程序。无编程定理指出，对于一个可编程量子门组，要实现两个不同的幺正算符，程序状态必须是正交的。因此，如果和对应于应用两个非等效线路所对应的评估运算符后Bob返回的信息，则和必须是正交的。这个定理的直接结果是，对于理论上安全的完全信息同态加密方案，如果已知的输入状态被加密，并且应用了来自某个未知线路c的计算运算符，则总是可以从产生的加密状态中确定c。这反映了一次性程序获得的结果，类似的任务中要保护的信息是Bob的线路而不是Alice的输入。正如我们所证明的，这种情况严重损害了任何QHE编码的效率。

推论1. 假设Q是一个QHE方案，具有完善的信息理论安全性，对应于一组可允许的单一操作S，那么，以下陈述成立：

1. 应用与S中任意操作相对应的计算运算符后，存储加密状态所需的系统大小至少为比特。
2. 如果S包含n位上的可逆经典运算集，那么加密状态的大小在n中至少呈指数增长。
3. 如果S是一个n位的近似与isin;的通用集合，这就意味着中的每一个元素都可以近似为isin;的精度。那么加密信息的长度为。

证明：推论第一部分的证明直接来自定理1。与S中的运算符对应

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

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

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