Paper 2015/417

Order-Revealing Encryption and the Hardness of Private Learning

Mark Bun and Mark Zhandry

Abstract

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 $(\epsilon, \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.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Preprint. MINOR revision.
Keywords
differential privacyorder-revealing encryption
Contact author(s)
mbun @ seas harvard edu
History
2015-05-05: received
Short URL
https://ia.cr/2015/417
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2015/417,
      author = {Mark Bun and Mark Zhandry},
      title = {Order-Revealing Encryption and the Hardness of Private Learning},
      howpublished = {Cryptology ePrint Archive, Paper 2015/417},
      year = {2015},
      note = {\url{https://eprint.iacr.org/2015/417}},
      url = {https://eprint.iacr.org/2015/417}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.