摘要

对于将计算卸载到潜在的不受信任的边缘服务器或云端的传感器设备来说，隐私和能源是首要关注因素。同态加密(HE)可以实现加密数据的卸载处理。HE卸载处理保留了数据的隐私性，但由于客户端设备和卸载服务器之间需要频繁的通信而受到限制。现有的客户端辅助加密计算系统都是针对卸载服务器上的性能进行优化，未能充分解决客户端成本问题，并排除了低资源（如物联网）设备的HE卸载。我们给大家介绍了不透明计算卸载(CHOCO)的客户端辅助HE，这是一个用于加密卸载处理的客户端优化系统。CHOCO引入了旋转冗余，这是一种算法优化，以最小化计算及通信成本。我们设计的客户端辅助HE通过加速加密操作实现不透明计算卸载（CHOCO-TACO），这是一个全面的客户端加密操作的架构加速器，可以减少大部分的时间和能源成本。我们的评估表明，CHOCO使客户端辅助HE卸载对于资源有限的客户是可行的。与现有的加密计算方案相比，CHOCO可减少高达2948倍的通信成本。在硬件的支持下，客户端的加密/解密速度快了1094倍，耗能少了648倍。在我们的大规模DNN(VGG16)的端到端实现中，CHOCO的能耗比局部(未加密)计算少了37%。

1.引言

产生数据的客户端设备在减小尺寸和能量存储能力[1]–[4]方面有着悠久的历史，致使了数以万亿计的微型设备诞生。随着客户端规模的缩小，传感器数据的计算复杂度也在不断提升，现在通常使用的是复杂的机器学习（ML）。由于总能量很少(可能没有电池)[1]-[4]、[6]、[7]，而且计算和内存受到限制，一个设备的局部处理能力从根本上说是有限的。

与局部计算相对应的是”推理即服务 “式卸载。一个服务器容纳了大量的DNN模型集合，并处理来自许多客户端的数据，却在不消耗客户端的内存和能源资源的条件下进行处理。这样的集中式模型易于演进，只需要在服务器上对模型进行一次更新，就可以避免将更新后的模型重新分布到庞大的处理客户端设备网络中。数据隐私是实现卸载计算这些好处的主要障碍：卸载将敏感的用户数据暴露在一个共享的、可能不受信任的卸载服务器上。

最近的工作为隐私保护计算提供了几种选择，包括可信执行环境(TEEs)[8]-[10]、差分隐私(DP)、多方计算(MPC)[11]-[13]和同态加密(HE)[14]-[17]。客户端辅助的混合HE-MPC协议最近在DNN推理方面取得了成功[18]-[21]，这是因为它们能够使用HE来保护用户数据，并对加密数据进行线性运算（如卷积）。HE-MPC混合协议混淆了线性运算的中间结果，并将其发送给客户端，客户端使用MPC应用非线性运算（如激活）。HE-MPC为保证客户端数据和模型数据的隐私，增加了MPC的客户端成本。如果一个应用只需要客户端的数据隐私，那么HE-MPC就没必要增加MPC的成本。

混合HE-MPC实现的隐私保护DNN推理显示出了可喜的结果，但基本上忽略了解决客户端增加的计算负担。现有的解决方案对HE-MPC参数进行了优化，以提高集中式模型服务器的性能和模型隐私性。系统选择大的密文大小(MB)，单次推理需要千兆字节的客户端与服务器通信。对于资源有限的客户端设备来说，参与这种方案是不可行的。

这项工作确定了全局计算和混合HEMPC之间的 “中间地带”，前者有相关的资源需求，无法使用集中管理的模型，后者为了模型的隐私，对客户端设备增加了高昂的计算和通信成本。我们提出了不透明计算卸载(CHOCO)的客户端辅助HE，这是一个能使客户端成本最小化的隐私保护计算系统。CHOCO针对的是不需要模型隐私，但需要严格的客户端数据隐私的应用。与HE-MPC相比，CHOCO降低了客户端成本的数量级，使资源受限的客户端设备享受到隐私保护ML的好处。

CHOCO是没有MPC的客户端辅助HE，在服务器上执行加密线性运算，在客户端执行明文非线性运算。CHOCO引入了旋转冗余，这是一种新的加密整序算法，可以最大限度地减少客户端通信和资源需求。此外，客户端辅助HE的一个独特的方面激发了CHOCO：在典型的HE方案中，加密和解密在每次计算中发生一次，但在客户端辅助HE中，加密和解密在关键路径上反复发生。我们定量地表明，加密和解密的时间和能量成本过高是客户端的主要瓶颈。我们提出了用于通过加速加密操作进行不透明计算卸载的客户端辅助HE（CHOCO-TACO），这是一个全面的硬件加速器，实现了所有这些HE加密基元，实质上消除了它们的时间成本。

我们对一个完整的硬件和软件实现的评估表明了，一个客户端优化系统对隐私保护计算的好处。与之前的7种HE或MPC方法相比，CHOCO降低了客户通信成本的数量级，改进幅度为14倍-2948倍。与软件相比，CHOCO-TACO的硬件加速将客户端的时间和能量提高了123.27倍，与HEAX相比提高了54.3倍，从而加速了硬件中部分（但不是全部）加密子操作。我们的实验结果表明，CHOCO使得客户端隐私保护DNN推理的性能与局部推理（使用TFLite）相当，有时甚至超过了局部推理的性能，同时避免了全局计算的限制。我们的主要贡献如下：

CHOCO，一个客户端优化的系统，用于实现资源受限设备的加密计算。
旋转冗余，是一种加密的整序算法，可以最大限度地减少客户端与服务器的通信。
CHOCO-TACO，客户端HE基元的专用硬件加速器。
一种客户端辅助隐私保护DNN推理的全硬件软件实现，与HE-MPC相比，客户端成本提高了一个数量级，执行性能与局部计算相当，同时享受模型集中化的好处。

2.背景与动机

CHOCO允许物联网设备将计算卸载到能力更强的服务器上，该服务器使用同态加密（HE）对加密数据进行计算。原始操作，被组成HE算法，大部分支持加密的单指令多数据（SIMD）计算。这些算法反过来被用来构建加密的HE应用，比如DNN推理。

A.同态加密

同态加密是一类允许对加密数据进行计算的加密方案。在HE中，对于一对可由操作⊕、操作⊕’的同态版本和加密/解密操作Enc()、Dec()操纵的消息m1和m2，应用于加密数据的同态操作产生的结果，就是在解密时等于应用于未加密数据的操作：

现代HE方案[22]、[23]都是基于环上差错学习问题（RLWE）的。这些方案将数千值的向量加密成一个大型多项式系数，通过模运算和加噪，隐藏向量的内容。表1中的HE操作对密码文本进行了操作，生成新密文，其中包含对输入逐元素应用的操作结果，如图1所示。每个操作都会给加密向量增加可预测的噪声量，有些操作（如乘法）会增加大量噪声，而有些操作（如加法）则增加少量噪声。HE计算的算术深度受到噪声增长的限制。一系列耗尽噪声预算的操作会使解密无法进行，数据无法恢复。为了避免超过噪声预算，系统必须安排加密操作以限制噪声增长。

HE可以刷新一个密文来消除累积的噪音，补充全部预算。全同态加密(FHE)通过 “Bootstrapping自助法”[24]，在不进行解密的情况下，以巨大的计算成本刷新噪声。相比之下，某些同态加密（SHE）[18]，[23]，[25]-[27]通过预先安排的解密和重新加密操作来刷新噪声。

CHOCO在SEAL[27]中使用了越来越实用的Brakerski/FanVercauteren（BFV）SHE方案[25]、[26]。表2总结了该方案的参数，这些参数决定了它的安全性、计算复杂性、噪声预算和密文大小：

通常情况下，多项式模数N，是2¹¹和2¹⁵之间的2次幂。一个新密文是两个各有N个元素的多项式(s=2)。对于一个给定的N，较小的系数模q可以提供更高的安全性，而噪声预算较小。一个实用的q值是数百位。直接对这么大的值进行操作，效率是很低的。HE方案使用残差数系统（RNS）[29]来表示使用k个较小互质模的数。SEAL使用60位残余模数，以适应64位机器字。

BFV支持明文模数t的整数运算。较大的t允许较大的数字，但有助于较小的噪声预算。参数选择取决于应用程序，必须允许足够大的明文值，同时保持足够的噪声增长预算。表3是CHOCO的参数和密文大小，单位是字节。

B.同态算法

表1中介绍的原始HE运算允许在大向量上执行SIMD运算。这些基本运算构成了支持卷积或矩阵乘法等计算。使用 HE 基元的算法有两种，这取决于输入如何被编码成密文。批处理算法，针对吞吐量进行了优化，将成千上万个输入的单个数据点编码成密文向量，并利用自然SIMD运算[16]，[30]。另外，针对延迟进行优化的打包算法，将单个输入的多个数据点编码为密文向量，并利用排序法对所需点进行适当的对齐和操作[14]，[18]。

C.同态应用

HE理论上支持任意函数（通过映射到多项式，计算成本极高[15]），然而，实际的HE应用直接使用HE基元，并且受到算术深度的限制。之前的工作已经确定了，使用深度神经网络（DNNs）的ML推理是HE的一个引人注目的用途，因为它的结构形式完全依赖于简单的线性代数。HE for ML的早期工作在加密数据上进行所有的计算[14]，[16]，[30]，只与数据源进行通信，接收初始输入并返回最终结果。遗憾的是，这些技术对大型复杂网络的适用性是有限的，因为它们修改了激活函数，跨多层的噪声增长很大，以及随后对非常大的参数选择的依赖性[15]。这直接导致密文大小达到多兆字节，使计算成本和通信成本都膨胀到不切实际的程度。

作为一种替代方案，最近的解决方案集中于客户端辅助HE[17]，[18]，[21]。在这些协议中，HE的自然线性代数能力被用于在卸载服务器上执行卷积和全连接层。然后征集客户端进行所有非线性激活和池操作。中间结果在层界处进行通信，计算继续来回进行，直到整个网络完成。

客户端辅助HE已被证实具有多种优势。通过避免修改激活函数，它们允许在预先训练的网络上进行隐私保护推理。此外，客户端辅助HE通过将数据发回客户端进行一些操作，定期刷新密文噪声预算。因此，客户端辅助HE不会限制DNN的深度，也不需要极其昂贵的HE参数设置。然而，这些好处是以增加客户端责任为代价的，特别是大量的解密和再加密操作。客户端成本是阻碍物联网设备采用客户端辅助HE的核心因素。CHOCO旨在通过加密算法优化和架构加速来打破这种参与障碍。

D.客户端感知优化的动机

客户端辅助的隐私保护计算给资源有限的物联网客户端设备带来了巨大的负担。客户端辅助模型固有的计算成本促使我们在客户端优化软件和硬件支持方面开展工作。

与客户端的交互用于刷新密文噪声预算，并在明文中计算（相对廉价的）非线性激活和池操作。为此，系统定期与客户端交换数据，对数据进行解密、最小化计算，并重新加密。这一过程对客户端责任有重要的净效应：大量加密和解密操作都在关键路径上。在软件中的这些加密操作计算成本极高，即使使用高度优化的商业化实现也是如此[27]。

我们使用我们的端到端软件的客户端辅助原型，来测量真实加密神经网络实现中加密和解密的成本。软件基线系统（我们将在第三章中详细描述）利用现有的服务器优化的加密算法[18]和[27]的默认参数选择。我们测量了使用的四个成熟DNN模型，每一个模型完成一次分类推理所需的时间（我们在第四章A部分中详细描述了我们的方法）。

图2显示了在客户端计算、在卸载上运行加密计算以及通信所花费的时间。随着模型大小的增加，通信和客户端计算成本也会增加。在卸载设备的加密计算成本始终非常耗时。在服务器优化加密算法[14]、[17]-[21]和硬件支持[31]-[33]方面，一个丰富而互补的工作线有望继续降低这些成本，但我们工作的目标不是优化卸载侧HE。相反，我们专注于降低客户端的时间成本（以及相应的能源成本）。通过之前的工作[34]初步解决了这一问题，我们对现实应用（如参数选择）和物联网设备（如低功耗）这一追求给予了特别关注。

客户端的计算成本主要是加密和解密的工作。图3显示了客户端在这些DNN推理计算过程中花费的时间明细。99%以上的客户端时间是HE操作，而不是ML操作（即非线性计算与量化）。该图还显示，现有的对数论变换（NTT）和二元乘法的硬件支持，如HEAX[31]中提供的支持，不足以降低加密成本。我们对SEAL中的加密和解密计算进行了分析，确定这些操作只占总运行时间的50%左右。我们通过在原来HEAX论文中报告的加速因子相应地缩放我们软件的运行时间，乐观地模拟了硬件支持对这两个子操作的好处。即使有HEAX和其他卸载侧加速器[31]-[33]的模块化优势，客户端所花费的加密和解密时间仍然在数量级上比ML计算占优势。加密和解密往往被认为是微不足道的一次性成本，但他们在客户端辅助模式中处于关键路径上，需要通过客户端优化的加密算法和全面的硬件支持进一步优化。在这项工作中，我们开发了这样的支持，使得客户端辅助的加密推理变得可行，并有利于资源受限的物联网客户端。

参考文献（一）

[1]H.-J. Chae, D. Yeager, J. Smith, and K. Fu, “Wirelessly powered sensor networks and computational rfifid,” 01 2013.

[2]A. Colin, E. Ruppel, and B. Lucia, “A reconfifigurable energy storage architecture for energy-harvesting devices,” SIGPLAN Not., vol. 53, no. 2, p. 767–781, Mar. 2018. [Online]. Available: https://doi.org/10.1145/3296957.3173210

[3]J. D. Garside, S. B. Furber, S. Temple, and J. V. Woods, “The amulet chips: Architectural development for asynchronous microprocessors,” in 2009 16th IEEE International Conference on Electronics, Circuits and Systems – (ICECS 2009), 2009, pp. 343–346.

[4]S. Liu, K. Pattabiraman, T. Moscibroda, and B. G. Zorn, “Flikker: Saving dram refresh-power through critical data partitioning,” SIGARCH Comput. Archit. News, vol. 39, no. 1, p. 213–224, Mar. 2011. [Online]. Available:https://doi.org/10.1145/1961295.1950391

[5]P. Sparks, “The route to a trillion devices: The outlook for iot investment to 2035,” arm, Tech. Rep., June 2017, https://community.arm.com/iot/b/internet-of-things/posts/white-paper-the-route-to-a-trillion-devices.

[6]N. Jackson and P. Dutta, “Permacam: A wireless camera sensor platform for multi-year indoor computer vision applications,” https://conix.io/wp-content/uploads/pubs/3113/jackson permacam conix 2020.pptx.pdf, Oct 2020.

[7] M. Nardello, H. Desai, D. Brunelli, and B. Lucia, “Camaroptera: A batteryless long-range remote visual sensing system,” in Proceedings of the 7th International Workshop on Energy Harvesting & EnergyNeutral Sensing Systems, ser. ENSsys’19. New York, NY, USA: Association for Computing Machinery, 2019, p. 8–14. [Online].

Available: https://doi.org/10.1145/3362053.3363491

[8] I. Corporation, Intel 64 and IA-32 Architectures Software Developer’s Manual, Nov 2020.

[9] J. Park, N. Kang, T. Kim, Y. Kwon, and J. Huh, “Nested enclave: Supporting fifine-grained hierarchical isolation with sgx,” in Proceedings of the ACM/IEEE 47th Annual International Symposium on Computer Architecture, ser. ISCA ’20. IEEE Press, 2020, p. 776–789. [Online]. Available:https://doi.org/10.1109/ISCA45697.2020.00069

[10] P. Subramanyan, R. Sinha, I. Lebedev, S. Devadas, and S. A. Seshia, “A formal foundation for secure remote execution of enclaves,” in Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security, ser. CCS ’17. New York, NY, USA: Association for Computing Machinery, 2017, p. 2435–2450. [Online]. Available: https://doi.org/10.1145/3133956.3134098

[11] A. Aggarwal, T. E. Carlson, R. Shokri, and S. Tople, “Soteria: In search of effificient neural networks for private inference,” 2020.

[12] M. S. Riazi, M. Samragh, H. Chen, K. Laine, K. Lauter, and F. Koushanfar, “XONN: Xnor-based oblivious deep neural network inference,” in 28th USENIX SecuritySymposium (USENIX Security

19). Santa Clara, CA: USENIX Association, Aug. 2019, pp. 1501–1518. [Online]. Available: https://www.usenix.org/conference/usenixsecurity19/presentation/riazi

[13] N. Chandran, D. Gupta, A. Rastogi, R. Sharma, and S. Tripathi, “Ezpc:Programmable, effificient, and scalable secure two-party computation for machine learning,” Cryptology ePrint Archive, Report 2017/1109, 2017,https://eprint.iacr.org/2017/1109.

[14] A. Brutzkus, O. Elisha, and R. Gilad-Bachrach, “Low latency privacy preserving inference,” in International Conference on Machine Learning, 2019.

[15] R. Dathathri, O. Saarikivi, H. Chen, K. Laine, K. Lauter, S. Maleki, and T. Musuvathi, M. Mytkowicz, “Chet: An optimizing compiler for fully-homomorphic neural-network inferencing,” in 40th ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI). ACM, June 2019.

[16] N. Dowlin, R. Gilad-Bachrach, K. Laine, K. Lauter, M. Naehrig, and J. Wernsing, “Cryptonets: applying neural networks to encrypted data with high throughput and accuracy,” in 33rd International Conference on Machine Learning (ICML). ACM, June 2016.

[17] F. Boemer, A. Costache, R. Cammarota, and C. Wierzynski, “nGraphHE2: A high-throughput framework for neural network inference on encrypted data,” Aug2019, arXiv:1908.04172v2.

[18]C. Juvekar, V. Vaikuntanathan, and A. Chandrakasan, “Gazelle: A low latency framework for secure neural network inference,” in Proceedings of the 27th USENIXConference on Security Symposium, ser. SEC’18. USA: USENIX Association, 2018, p. 1651–1668.

[19] P. Mishra, R. Lehmkuhl, A. Srinivasan, W. Zheng, and R. A. Popa, “Delphi: A cryptographic inference service for neural networks,” in 29th USENIX Security Symposium (USENIX Security 20). USENIX Association, Aug. 2020, pp. 2505–2522. [Online]. Available: https://www.usenix.org/conference/usenixsecurity20/presentation/mishra

[20] J. Liu, M. Juuti, Y. Lu, and N. Asokan, “Oblivious neural network predictions via minionn transformations,” in Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security, ser. CCS ’17. New York, NY, USA: Association for Computing Machinery, 2017, p. 619–631. [Online]. Available: https://doi.org/10.1145/3133956.3134056

[21] B. Reagen, W. Choi, Y. Ko, V. Lee, G.-Y. Wei, H.-H. S. Lee, and D. Brooks, “Cheetah: Optimizing and accelerating homomorphic encryption for privateinference,” 2020.

[22] J. Fan and F. Vercauteren, “Somewhat practical fully homomorphic encryption,” Cryptology ePrint Archive, Report 2012/144, 2012, https: //eprint.iacr.org/2012/144.

[23] J. H. Cheon, A. Kim, M. Kim, and Y. Song, “Homomorphic encryption for arithmetic of approximate numbers,” Cryptology ePrint Archive, Report 2016/421, 2016, https://eprint.iacr.org/2016/421.

[24] C. Gentry, “Fully homomorphic encryption using ideal lattices,” in Proceedings of the 41st Annual ACM Symposium on Theory of Computing, ser. STOC 41. New York, NY, USA: Association for Computing Machinery, 2009, pp. 169–178.

[25] Z. Brakerski, “Fully homomorphic encryption without modulus switching from classical gapsvp,” in Proceedings of the 32nd Annual Cryptology Conference onAdvances in Cryptology — CRYPTO 2012 – Volume 7417. Berlin, Heidelberg: Springer-Verlag, 2012, p. 868–886. [Online]. Available:https://doi.org/10.1007/978-3-642-32009-5 50

[26] J. Fan and F. Vercauteren, “Somewhat practical fully homomorphic encryption,” Cryptology ePrint Archive, Report 2012/144, 2012, https: //eprint.iacr.org/2012/144.

[27] “Microsoft SEAL (release 3.4),” https://github.com/Microsoft/SEAL, Oct 2019,microsoft Research, Redmond, WA.

[28] K. Laine, Simple Encrypted Arithmetic Library 2.3.1, Microsoft Research, 2017.

[29] J. C. Bajard, N. Meloni, and T. Plantard, “Effificient rns bases for cryptography,”07 2005.

[30] E. Hesamifard, H. Takabi, and M. Ghasemi, “Deep neural networksclassifification over encrypted data,” in Proceedings of the Ninth ACM Conference on Data and Application Security and Privacy, ser. CODASPY ’19. New York, NY, USA: Association for Computing Machinery, 2019, p. 97–108. [Online]. Available: https://doi.org/10.1145/3292006.3300044

[31] M. S. Riazi, K. Laine, B. Pelton, and W. Dai, “Heax: An architecture for computing on encrypted data,” in Proceedings of the Twenty-Fifth International Conference on Architectural Support for Programming Languages and Operating Systems, ser. ASPLOS ’20. New York, NY, USA: Association for Computing Machinery, 2020, p. 1295–1309. [Online]. Available: https://doi.org/10.1145/3373376.3378523

[32] F. Turan, S. S. Roy, and I. Verbauwhede, “Heaws: An accelerator forhomomorphic encryption on the amazon aws fpga,” IEEE Transactions on Computers, vol. 69, no. 8, pp. 1185–1196, 2020.

[33] S. S. Roy, F. Turan, K. Jarvinen, F. Vercauteren, and I. Verbauwhede, “Fpga-based high-performance parallel architecture for homomorphic computing on encrypted data,” Cryptology ePrint Archive, Report 2019/160, 2019,https://eprint.iacr.org/2019/160.

[34] A. Mert, E. Ozturk, and E. Savas, “Design and implementation ofencryption/decryption architectures for bfv homomorphic encryption scheme,” IEEE Transactions on Very Large Scale Integration (VLSI) Systems, vol. 28, no. 02, pp. 353–362, feb 2020.