TY - GEN
T1 - Order-revealing encryption and the hardness of private learning
AU - Bun, Mark
AU - Zhandry, Mark
N1 - Funding Information:
M. Bun?Supported by an NDSEG fellowship and NSF grant CNS-1237235. M. Zhandry?Work done while the author was a graduate student at Stanford University. Supported by the DARPA PROCEED program.
Publisher Copyright:
© International Association for Cryptologic Research 2016.
PY - 2016
Y1 - 2016
N2 - 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.
AB - 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.
KW - Differential privacy
KW - Learning theory
KW - Order-revealing encryption
UR - http://www.scopus.com/inward/record.url?scp=84952690452&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84952690452&partnerID=8YFLogxK
U2 - 10.1007/978-3-662-49096-9_8
DO - 10.1007/978-3-662-49096-9_8
M3 - Conference contribution
AN - SCOPUS:84952690452
SN - 9783662490952
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 176
EP - 206
BT - Theory of Cryptography - 13th International Conference, TCC 2016-A, Proceedings
A2 - Kushilevitz, Eyal
A2 - Malkin, Tal
PB - Springer Verlag
T2 - 13th International Conference on Theory of Cryptography, TCC 2016
Y2 - 10 January 2016 through 13 January 2016
ER -