Order-revealing encryption and the hardness of private learning

Mark Bun, Mark Zhandry

Research output: Chapter in Book/Report/Conference proceedingConference contribution

9 Scopus citations

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 (ε, δ)-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 orderrevealing 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.

Original languageEnglish (US)
Title of host publicationTheory of Cryptography - 13th International Conference, TCC 2016-A, Proceedings
EditorsEyal Kushilevitz, Tal Malkin
PublisherSpringer Verlag
Pages176-206
Number of pages31
ISBN (Print)9783662490952
DOIs
StatePublished - Jan 1 2016
Externally publishedYes
Event13th International Conference on Theory of Cryptography, TCC 2016 - Tel Aviv, Israel
Duration: Jan 10 2016Jan 13 2016

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume9562
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other13th International Conference on Theory of Cryptography, TCC 2016
CountryIsrael
CityTel Aviv
Period1/10/161/13/16

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

Keywords

  • Differential privacy
  • Learning theory
  • Order-revealing encryption

Fingerprint Dive into the research topics of 'Order-revealing encryption and the hardness of private learning'. Together they form a unique fingerprint.

  • Cite this

    Bun, M., & Zhandry, M. (2016). Order-revealing encryption and the hardness of private learning. In E. Kushilevitz, & T. Malkin (Eds.), Theory of Cryptography - 13th International Conference, TCC 2016-A, Proceedings (pp. 176-206). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 9562). Springer Verlag. https://doi.org/10.1007/978-3-662-49096-9_8