8---王育齐

ISSN 1673-9418 CODEN JKYTA8 Journal of Frontiers of Computer Science and Technology 1673-9418/2016/10(11)-1571-06 doi: 10.3778/j.issn.1673-9418.1606032 E-mail: fcst@vip.163.com http://www.ceaj.org Tel: +86-10-89056056 * 1,2+ 1 王育齐, 佘堃 1. 电子科技大学信息与软件工程学院, 成都 610054 2. 闽南师范大学计算机学院, 福建漳州 363000 Universal Quantum Homomorphic Encryption Framework WANG Yuqi 1,2+, SHE Kun 1 1. School of Information and Software Engineering, University of Electronic Science and Technology of China, Chengdu 610054, China 2. College of Computer, Minnan Normal University, Zhangzhou, Fujian 363000, China + Corresponding author: E-mail: paiter_w@126.com WANG Yuqi, SHE Kun. Universal quantum homomorphic encryption framework. Journal of Frontiers of Computer Science and Technology, 2016, 10(11): 1571-1576. Abstract: Through studying quantum homomorphic encryption, this paper proposes a general construction method for quantum homomorphic operator, thus sets up a universal construction framework for quantum homomorphic encryption scheme. Compared with existing quantum homomorphic encryption schemes, the schemes constructed by the universal construction framework according to the binary and ternary quantum unitary transformations, are more feasible. This paper analyzes the security of the universal framework from two respects. One is the security of quantum encryption scheme. The other is the security of the secret key. In the universal construction framework, the symmetric quantum encryption scheme is used and the evaluation algorithm is dependent on the secret key in the process of constructing the corresponding quantum homomorphic operator. As a result, the universal construction framework is a kind of weak symmetric quantum homomorphic encryption framework. Finally, it is generalized to the case of the quantum public key encryption. * The National Natural Science Foundation of China under Grant Nos. 61272175, 61572109 ( 国家自然科学基金 ); the Program of Education Department of Fujian Province under Grant No. JA15321 ( 福建省教育厅项目 ); the Key Technology Support Program of Sichuan Province under Grant No. 2015GZ0102 ( 四川省科技支撑计划 ). Received 2016-05, Accepted 2016-07. CNKI 网络优先出版 : 2016-07-14, http://www.cnki.net/kcms/detail/11.5602.tp.20160714.1616.014.html

1572 Journal of Frontiers of Computer Science and Technology 计算机科学与探索 2016, 10(11) Key words: quantum homomorphic encryption; quantum homomorphic operator; quantum delegated computation; symmetric quantum encryption; quantum cryptography 研究了量子同态加密, 提出了一种通用的构造量子同态加密算子的方法, 进而建立了构造量子同态加 密方案的一种通用框架 ; 通过二值和三值量子态的酉变换, 利用该框架构造了相应的量子同态加密方案, 与现 有文献的构造方案相比, 利用该框架构造的量子同态加密方案更具有普遍性 ; 通过安全性分析, 该框架的安全 性是基于加密算法的安全性和密钥的安全性 由于该框架采用了对称量子加密算法, 导致构造量子同态算子 时需要加密密钥, 从而该框架是一种弱的对称量子同态加密框架 最后, 该框架被推广到了量子公钥加密的情形 量子同态加密 ; 量子同态算子 ; 量子代理计算 ; 对称量子加密 ; 量子密码 A TP393.04 1 在一个分布式开放环境中, 假定用户拥有一些 私密的量子态数据, 比如在线购物记录 信用卡消费 记录等 局限于用户的计算能力 ( 比如昂贵的量子 计算机 ), 用户能否将自己的计算任务安全地委托给 第三方 ( 拥有量子计算机 ) 进行? 回答是肯定的, 盲 量子计算 (blind quantum computation,bqc) [1-10] 和量子 同态加密 (quantum homomorphic encryption,qhe) [11-18] 就可以很好地完成用户委托的量子计算 本文将采 用 QHE 的方式实现用户的委托计算, 进而推导出通 用的 QHE 框架 [11] 首先,Rohde 等人基于量子漫步 (quantum walks), 提出了第一个受限的 QHE 方案 ;Liang [12] 首次给出了 QHE 和 QFHE 的定义, 并且基于量子一次一密 (quantum one-time pad,qotp), 构造了信息理论安全的对 称 QHE 方案 ; 随后, 基于通用量子线路 (universal quantum circuit,uqc),liang 又提出了一个量子全同态加 密 (quantum full homomorphic encryption,qfhe) 方 案 [13] 在该方案中, 评估函数独立于加密密钥, 而解 密密钥则是通过一个迭代过程, 从加密密钥中计算 [14] 出来的 ; 最近,Liang 等人基于量子容错结构 (quantum fault-tolerant construction), 提出了两个 QFHE 方 案, 其中一个是使用了量子纠错码和辅助量子态的 对称 QFHE 方案, 另外一个则是非对称的 QFHE, 它 需要一个交互过程协助完成 [15] Tan 等人利用算子子群的中心化子, 提出了一 个私钥的 QHE 方案, 该方案可以在加密的量子数据 上执行一大类的量子计算任务, 而且是信息理论安 [16] 全的 ;Ouyang 等人针对任意经典和量子的线路, 只 要这些线路包含不超过一固定数目的 non-clifford 门, 他们构造了基于这些线路的 QHE 方案 ;Broadbent [17] 等人基于低复杂度的 T-Gates 构成的线路, 提出了 [18] 两个 QHE 方案 ; 最近,Wang 等人基于三值量子门, 结合三值量子门的拟合, 提出了对称的三值 QHE 方 案, 该方案采用了对称加密方式 以上这些研究都是基于某些特定的量子逻辑 门, 构造了相应的 QHE 方案 本文结合 QHE 的基本 定义和以上的研究成果, 提出了构造量子同态算子 (quantum homomorphic operator,qho) 的一般性方 法, 进而建立了设计 QHE 方案的通用框架 通过二 值和三值的两个例子, 证明了该框架的正确性, 与现 有文献相比, 方案更具有普适性 通过安全性分析, 本文框架是一个弱的对称 QHE 框架 弱 是指 QHE 中的加密算法, 在三值量子态中还没有对应的信息 理论安全的加密算法 2 一个 QHE 方案由四部分构成 [12] : 密钥产生算法 加密算法 解密算法和评估算法 和一般的量子加 密算法相比,QHE 多了一个评估算法 该算法的作 用是构造相应的量子同态算子, 并在加密数据上执 行这些同态算子 当用户对其输出执行解密操作 时, 将得到相应操作在明文态上执行的结果 对于一个 QHE 方案来说, 该四部分是相互独立

王育齐等 : 通用的量子同态加密框架 1573 的, 对其进行替换 ( 主要是加解密算法 ), 不影响 QHE 的执行 因此设计一个 QHE 方案, 主要有两个问题要解决 :(1) 设计加解密算法 ;(2) 设计可以构造同态算子的评估函数 重点在于第二个问题, 即根据用户指定的操作, 如何构造一个在用户加密数据上可以执行的同态算子, 是设计 QHE 方案的关键性问题 同态算子是根据用户想要在明文执行的操作, 由评估函数构造出来的, 可以在用户加密数据上执行, 而且执行过程不需要解密过程, 从而确保了用户数据的私密性 ; 当用户对评估函数的输出结果进行解密时, 将得到自己想要在明文上执行操作的结果, 确保了委托计算的正确性 ; 根据加密方式, 若为量子私钥加密 ( 即对称量子加密 ), 则假定代理方是诚信的, 因为评估函数的执行需要加密密钥 ( 即解密密钥 ), 所以在这种情况下称其为弱的 QHE 若为量子公钥加密 ( 即非对称量子加密 ), 则评估函数是独立于解密密钥的 相对于前者, 后者的适用范围更广, 且数据私密性保护得更好 3 QHE 3.1 假定 ρ c 和 σ m 是密文和明文的量子态表示形式, KeyGen A 是密钥产生算法,Encrypt A 是加密算法, Decrypt A 是解密算法,Eualuate A 是评估算法,U Δ 是一组可允许执行的量子操作集合, 存在一个 U U Δ, 密钥 k {KeyGen Δ }, 则有 ρ c = Encrypt A (σ m,k) 和 σ m = Decrypt A (ρ c,k) Evaluate A 的描述如下 : 根据用户指定的酉变换 U 和密钥 k, 评估函数计算出一个在用户加密数据上可执行的同态算子 U, 在这个计算过程中没有执行 Decrypt A 算法, 而且假定了 Evaluate A 的执行方 ( 也叫代理 ) 是诚信的 在量子逻辑线路中, 所有的逻辑门都是可逆的, 这一点不同于经典逻辑门 因此, 对于评估函数的输出结果, 结合对称加密和量子逻辑门可逆性的特点, 将 QHE 方案表述为 : U ρ c = Encrypt A (Uσ m,k) (1) 该式说明, 同态算子 U 作用在量子密文态 ρ c 上的结果 ( 记为 U ρ c ), 等价于对原始操作 U 作用在量 子明文态 σ m 上的结果 ( 记为 Uσ m ) 进行加密 所以 说, 用户只要对评估函数的输出进行解密, 即可得到 原始操作 U 作用在量子明文态 σ m 上的结果, 即 : Uσ m = Decrypt A (U ρ c,k) (2) 而且从式 (1) 还可以推导出关于同态算子 U 的公 式, 即 : U = Encrypt A(Uσ m,k) Encrypt A (σ m,k) (3) 对于式 (3), 在同态算子 U 的计算过程中, 有如 下几点说明 :(1) 代理方需要知道用户的加密密钥 ; (2) 没有调用解密过程 Decrypt A ;(3) 假定代理方是诚 信的 ;(4) 加密算子都是酉矩阵, 注意矩阵运算规 则 基于前三点, 在量子同态算子的构造过程中, 用 户数据的私密性得到了很好的保护, 而且代理方会 正确执行用户的委托计算, 满足 QHE 的定义 ( 请参照 文献 [12,19-20]) 通过式 (3), 可以根据用户指定的量子操作 ( 也 叫酉变换, 该变换作用于量子明文态 ), 构造出作用 于量子密文态的同态算子 ( 也是一种酉变换 ), 使得 用户只需解压评估函数的输出态, 就可以得到指定 操作在量子明文态上的结果 评估函数不仅实现了 用户委托的量子计算, 而且完成了针对用户指定量 子酉变换的 QHE 方案的设计 综上所述, 把式 (3) 称为构造量子同态操作的一 般性方法 ( 即评估函数的设计 ), 进而建立起设计 QHE 方案的通用框架 当然, 该框架可以推广至量 子公钥加密体系, 如下列 3 个等式所示 : U Encrypt A (σ m,pk) = Encrypt A (Uσ m,pk) (4) Uσ m = Decrypt A (U ρ c,sk) (5) U = Encrypt A(Uσ m,pk) Encrypt A (σ m,pk) (6) 其中,pk 和 sk 分别代表量子公钥加密体系中的公钥 和私钥 从式 (6) 可以得到, 推广后的非对称的 QHE 框架中, 计算量子同态算子的过程只需要加密密钥 而不需要解密密钥, 而且是独立于解密过程的 它 不再需要假定代理方是诚信的, 扩大了 QHE 方案的 适用范围 相比较于式 (3) 的对称 QHE 框架, 式 (6) 的非对称 QHE 框架, 具有更高的安全性和更广阔的 适用范围

1574 Journal of Frontiers of Computer Science and Technology 计算机科学与探索 2016, 10(11) 3.2 依据该框架 ( 参照式 (3)), 以二值和三值量子态 为例, 来说明该框架在二值和三值情况下, 由该框架 推导出的 QHE 方案与现有文献提出的是等价的 (1) 二值量子态情况 在二值情况下, 酉矩阵 σ x σ y σ z 是 3 个泡利 矩阵的分量 假定加密过程为 {X α Z β α,β {0,1} n }, [21] 该方案是信息理论安全的, 其中 X α = n α(i) i = 1σ x 和 Z β = n i = 1σ z β(i), 解密过程为加密过程的逆过程, 即为 (X α Z β ) = Z β X α, 上标 表示矩阵的共轭转置 量 子态的加密过程表示为 ψ c = U k φ m = X α Z β φ m, 解 密过程表示为 ψ m = U k ψ c = U k X α Z β φ m = Z β X α X α Z β φ m = φ m 若用户指定的操作为单量子比特旋转门 R y (θ) = e -iθσ y 2, 则相应的同态算子为 R y (θ ), 满足 R y (θ )X α Z β = X α Z β R y (θ) (7) 结合等式 (7), 利用等式 (3), 可以推导出 : R y (θ )X α Z β (X α Z β ) = X α Z β R y (θ)(x α Z β ) R y (θ ) = X α Z β R y (θ)z β X α 因为是单量子比特旋转门, 所以 α,β {0,1} 这 与文献 [12] 中构造出的关于 R y (θ) 旋转门的同态算子 ( 注意文献中 θ =(-) α + β θ) 是等价的 例如, 当 α = 1,β = 0 和 θ = π 时, 若用户数据为量 子明文态 1 = æ 0 è1 ö ø, 指定操作为 R y (π) = æ è 0-1 1 0 ö ø 和加 密算符 U k 为 X 1 Z 0 = æ 0 1ö 时, 则有 R è1 0ø y (θ ) = æ 0 1ö è-1 0 ø = R y (-π), 正好和文献 [12] 中的 θ =(-) α + β θ = -θ 是一致 的 此时, 有 (X 1 Z 0 ) R y (-π)x 1 Z 0 0 = R y (π) 0 成立, 即 用户解密评估函数的输出态后就可以得到指定操作 在明文态上的结果, 满足 QHE 的定义 (2) 三值量子态 在三值情况下, 量子态 0 1 和 2 称为基态, 分别表示为 (1,0,0) T (0,1,0) T 和 (0,0,1) T, 上标 T 代 表的是对行向量的转置 酉矩阵 X H 和 Z 都是三 值的量子酉门, 且每个门都有 3 种不同的形式, 加密 算法为 {X α H β Z δ α,β,δ {0,1,2} n }, 其中 X α = n i = 1X (α(i)), H β = n i = 1H (β(i)) 和 Z δ = n i = 1Z (δ(i)) ( 具体参照文献 [18]), 加解密的过程请参照二值情况 例如, 假定用户数据为单量子比特 0 = æ 1 ö ç 00, 用 è ø 户指定的操作为三值旋转门 R (01) y (π) = æ 0 0-1ö ç0 1 0, 加 è1 0 0 ø 密算子 U k 为 X (2) H (0) Z (1) = 1 æ1-1 0 ö ç 2 ç 0 0 2, 则根据式 è1 1 0 ø (3), 构造出的同态算子为 R (01) y = 1 æ 1-2 -1ö 2 ç 2 0 2, ç è -1-2 1 ø 这与文献 [18] 中构造出的同态加密算子是一致的 显然, 有 (X (2) H (0) Z (1) ) R (01) y X (2) H (0) Z (1) 0 = R y (01)(π) 0 成立, 即用户只要解密评估函数的输出就可得到指定操作 作用在量子明文态上的结果, 满足 QHE 的定义 4 对于一个 QHE 方案来说, 它的安全性可以从两 个方面进行分析 首先是加密算法的安全性 在该 框架中, 由于采用了对称加密算法, 导致评估函数在 计算相应的量子同态操作时, 一个是要假定代理方 是诚信的, 另外还需要加密密钥, 这就导致数据有泄 密的可能性 ( 因为加解密密钥是一样的 ) 就对称加 密算法本身来说, 二值情况下, 文献 [21] 提供一个信 息理论安全的量子一次一密方案 但是在三值情况 下, 目前还没有一个信息理论安全的对称量子加密 方案 当该模型推广至量子公钥加密体系下时, 代 理方是否诚信和可能的数据泄密就不存在了, 这无 疑会提高 QHE 方案的安全性和适用范围 最后, 分析该框架中的密钥安全性 首先, 该框 架中的加解密密钥都是只使用一次的, 类似于一次 一密方案 密钥串的获取可以通过文献 [22] 中介绍 的基于重发机制的量子密钥分发协议得到, 而且分 发过程是无条件安全的 其次, 基于量子测不准原 理和量子不可克隆原理, 任何强行测量未知量子态 的做法, 都只能得到一些随机的量子比特串, 而非私 密信息 最后, 只要密钥的拥有者不泄露密钥的任 何私密信息的话, 任何窃听者都将无法获得有效的

王育齐等 : 通用的量子同态加密框架 1575 私密信息 另外, 由评估函数构造的量子同态算子 ( 只有代理方知道 ) 作用于用户加密数据, 相当于二次加密, 这无疑增加了窃听者获取有效信息的难度 综上所述, 本文构造的 QHE 框架在二值量子态下是信息理论安全的, 但在三值量子态下, 却是弱安全性的 主要原因是在三值情况下缺乏信息理论安全的对称量子加密方案 但当将其推广至量子公钥加密体系下后, 该框架将能够获得信息理论安全的 QHE 方案 5 QHE 方案可以实现委托的量子计算, 主要是指代理方可以构造出基于用户加密密钥和指定操作的同态算子, 使其作用在用户加密数据上 当用户对评估函数的输出结果进行解密时, 用户将得到原始操作在明文态上执行的效果 这个过程中没有执行数据解密操作, 保护了数据的私密性, 实现了用户的委托计算 本文通过构造基于用户加密密钥和指定操作 ( 一种酉变换 ) 的量子同态算子的一般性方法, 提出了一种设计对称 QHE 方案的通用框架, 并将其推广到量子公钥加密的情况 通过二值和三值量子态酉变换, 构造了相应的同态操作, 验证了对称 QHE 框架的正确性 通过对加密算法本身和密钥源的安全性进行分析, 该框架是一种弱的对称 QHE 框架 但将其推广后, 则是一种信息理论安全的非对称 QHE 框架 寻找量子公钥加密算法和优化评估函数, 设计高效安全的 QHE 或 QFHE 方案, 将是下一阶段研究的主要目标 References: [1] Barz S, Kashefi E, Broadbent A, et al. Demonstration of blind quantum computing[j]. Science, 2012, 335(6066): 303-308. [2] Barz S, Fitzsimons J F, Kashefi E, et al. Experimental verification of quantum computation[j]. Nature Physics, 2013, 9 (11): 727-731. [3] Giovannetti V, Maccone L, Morimae T, et al. Efficient universal blind quantum computation[j]. Physical Review Letters, 2013, 111(23): 230501. [4] Mantri A, Pérez-Delgado C A, Fitzsimons J F. Optimal blind quantum computation[j]. Physical Review Letters, 2013, 111(23): 230502. [5] Fitzsimons J F, Kashe E. Unconditionally verifiable blind computation[eb/ol]. [2016-04- 15]. http://arxiv.org/abs/1203. 5217. [6] Morimae T, Fujii K. Blind quantum computation protocol in which Alice only makes measurements[j]. Physical Review A, 2013, 87: 050301. [7] Fisher K A G, Broadbent A, Shalm L K, et al. Quantum computing on encrypted data[j]. Nature Communications, 2014, 5: 3074. [8] Broadbent A, Fitzsimons J, Kashefi E. Universal blind quantum computation[c]//proceeding of the 50th Annual IEEE Symposium on Foundations of Computer Science, Atlanta, USA, Oct 25-27, 2009. Piscataway, USA: IEEE, 2009: 517-526. [9] Arrighi P, Salvail L. Blind quantum computation[j]. International Journal of Quantum Information, 2006, 4(5): 883-898. [10] Sueki T, Koshiba T, Morimae T. Ancilla- driven universal blind quantum computation[j]. Physical Review A, 2013, 87: 060301. [11] Rohde P P, Fitzsimons J F, Gilchrist A. Quantum walks with encrypted data[j]. Physical Review Letters, 2012, 109: 150501. [12] Liang Min. Symmetric quantum fully homomorphic encryption with perfect security[j]. Quantum Information Processing, 2013, 12(12): 3675-3687. [13] Liang Min. Quantum fully homomorphic encryption scheme based on universal quantum circuit[j]. Quantum Information Processing, 2014, 14(8): 2749-2759. [14] Liang Min, Yang Li. Quantum fully homomorphic encryption scheme based on quantum fault- tolerant construction [EB/OL]. [2016-04-15]. http://arxiv.org/abs/1503.04061v1. [15] Tan S H, Kettlewell J A, Ouyang Y K, et al. A quantum approach to homomorphic encryption[j]. Scientific Reports, 2016, 6: 33467. [16] Ouyang Y K, Tan S H, Fitzsimons J F. Quantum homomorphic encryption from quantum codes[eb/ol]. [2016-04-15]. http://arxiv.org/abs/1508.00938v2. [17] Broadbent A, Jeffery S. Quantum homomorphic encryption for circuits of low t- gate complexity[c]//lncs 9216: Proceedings of the 35th Annual Cryptology Conference, Santa Barbara, USA, Aug 16-20, 2015. Berlin, Heidelberg: Springer,

1576 Journal of Frontiers of Computer Science and Technology 计算机科学与探索 2016, 10(11) 2015: 609-629. [18] Wang Yuqi, She Kun, Luo Qinbing, et al. Symmetric weak ternary quantum homomorphic encryption schemes[j]. Modern Physics Letters B, 2016, 30(7): 1650076. [19] Gentry C. Computing arbitrary functions of encrypted data [J]. Communications of the ACM, 2010, 53(3): 97-105. [20] Gentry C, Halevi S. Implementing gentry s fully-homomorphic encryption scheme[c]//lncs 6632: Proceedings of the 30th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Tallinn, Estonia, May 15-19, 2011. Berlin, Heidelberg: Springer, 2011: 129-148. [21] Boykin P O, Roychowdhury V. Optimal encryption of quantum bits[j]. Physical Review A, 2003, 67: 042317. [22] Wang Yuqi, She Kun. Quantum key distribution protocol based on retransmission mechanism[j]. Computer Engineering and Design, 2015, 36(11): 2938-2942. [22] 王育齐, 佘堃. 基于重发机制的量子密钥分发协议 [J]. 计 算机工程与设计, 2015, 36(11): 2938-2942. WANG Yuqi was born in 1976. He is a Ph.D. candidate at School of Information and Software Engineering, University of Electronic Science and Technology of China, and a lecturer at College of Computer, Minnan Normal University. His research interests include quantum information processing and quantum cryptogram. 王育齐 (1976 ), 男, 甘肃西和人, 电子科技大学信息与软件工程学院博士研究生, 闽南师范大学计算机学院讲师, 主要研究领域为量子信息处理, 量子密码 SHE Kun was born in 1967. He received the Ph.D. degree from University of Electronic Science and Technology of China in 2006. Now he is a professor and Ph.D. supervisor at School of Information and Software Engineering, University of Electronic Science and Technology of China. His research interests include information security, cloud computing and quantum cryptogram. 佘堃 (1967 ), 男, 四川成都人,2006 年于电子科技大学获得博士学位, 现为电子科技大学信息与软件工程学院教授 博士生导师, 主要研究领域为信息安全, 云计算, 量子密码