Can homomorphic encryption be practical?
Can homomorphic encryption be practical?
复制标题
DOI：
10.1145/2046660.2046682
复制
发表时间：
2011-10
期刊：
影响因子：
--
通讯作者：
K. Lauter;M. Naehrig;V. Vaikuntanathan
中科院分区：
文献类型：
--
作者：
K. Lauter;M. Naehrig;V. Vaikuntanathan
将越来越多的数据存储和管理外包给云服务的前景给个人和企业带来了许多新的隐私问题。如果用户对他们发送到云的数据进行加密，那么隐私问题就可以得到满意的解决。如果加密方案是同态的，即使数据被加密，云仍然可以对数据执行有意义的计算。事实上，我们现在知道了一些完全同态加密方案的构造，它们允许对加密数据进行任意计算。在过去的两年里，人们提出并改进了完全同态加密的解决方案，但很难忽视房间里的大象，即效率--同态加密能否足够有效以实用？当然，似乎所有已知的全同态加密方案在实际应用之前还有很长的路要走。鉴于这种情况，我们的贡献是双重的。首先，我们展示了一些现实世界中的应用，在医疗，金融和广告领域，这只需要加密方案是“有点”同态。支持有限数量的同态运算的有点同态加密方案可以比全同态加密方案快得多，并且更紧凑。其次，我们展示了最近Brakerski和Vaikuntanathan的同态加密方案的概念验证实现，其安全性依赖于“带错误的环学习”（Ring LWE）问题。该方案是非常有效的，并具有合理的短密文。我们的未优化的实现在岩浆享有相当的效率，甚至优化的基于配对的计划具有相同的安全性和同态能力。我们还展示了一些特定于应用程序的加密方案的优化，最显着的是在密文中的不同消息编码之间转换的能力。
The prospect of outsourcing an increasing amount of data storage and management to cloud services raises many new privacy concerns for individuals and businesses alike. The privacy concerns can be satisfactorily addressed if users encrypt the data they send to the cloud. If the encryption scheme is homomorphic, the cloud can still perform meaningful computations on the data, even though it is encrypted. In fact, we now know a number of constructions of fully homomorphic encryption schemes that allow arbitrary computation on encrypted data. In the last two years, solutions for fully homomorphic encryption have been proposed and improved upon, but it is hard to ignore the elephant in the room, namely efficiency -- can homomorphic encryption ever be efficient enough to be practical? Certainly, it seems that all known fully homomorphic encryption schemes have a long way to go before they can be used in practice. Given this state of affairs, our contribution is two-fold. First, we exhibit a number of real-world applications, in the medical, financial, and the advertising domains, which require only that the encryption scheme is "somewhat" homomorphic. Somewhat homomorphic encryption schemes, which support a limited number of homomorphic operations, can be much faster, and more compact than fully homomorphic encryption schemes. Secondly, we show a proof-of-concept implementation of the recent somewhat homomorphic encryption scheme of Brakerski and Vaikuntanathan, whose security relies on the "ring learning with errors" (Ring LWE) problem. The scheme is very efficient, and has reasonably short ciphertexts. Our unoptimized implementation in magma enjoys comparable efficiency to even optimized pairing-based schemes with the same level of security and homomorphic capacity. We also show a number of application-specific optimizations to the encryption scheme, most notably the ability to convert between different message encodings in a ciphertext.