Order-Revealing Encryption and the Hardness of Private Learning
Order-Revealing Encryption and the Hardness of Private Learning
复制标题
揭示秩序的加密和私人学习的难度
DOI：
--
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
Mark Zhandry
中科院分区：
文献类型：
--
作者：
Mark Bun;Mark Zhandry
顺序揭示加密方案给出了一个公开的过程，通过该过程可以比较两个密文以揭示其底层明文的顺序。我们展示了如何使用顺序揭示加密来将计算效率高的PAC学习与高效的$$\varepalent，\delta $$-差分私人PAC学习分开。也就是说，我们构建了一个概念类，是有效的PAC学习，但每一个有效的学习者未能区别私人。这回答了Kasiviswanathan等人FOCS '08，SIAM J. Comput. '11.
为了证明我们的结果，我们给出了一个通用的转换，从一个顺序揭示加密方案到一个强正确的比较，这使得一致的比较密文没有得到任何消息的有效加密。我们认为，这一建设可能是独立的利益。
An order-revealing encryption scheme gives a public procedure by which two ciphertexts can be compared to reveal the ordering of their underlying plaintexts. We show how to use order-revealing encryption to separate computationally efficient PAC learning from efficient $$\varepsilon , \delta $$-differentially private PAC learning. That is, we construct a concept class that is efficiently PAC learnable, but for which every efficient learner fails to be differentially private. This answers a question of Kasiviswanathan et al. FOCS '08, SIAM J. Comput. '11.
To prove our result, we give a generic transformation from an order-revealing encryption scheme into one with strongly correct comparison, which enables the consistent comparison of ciphertexts that are not obtained as the valid encryption of any message. We believe this construction may be of independent interest.