Skip to main content

ϵKtelo: A framework for defining differentially private computations

Publication ,  Journal Article
Zhang, D; McKenna, R; Kotsogiannis, I; Bissias, G; Hay, M; Machanavajjhala, A; Miklau, G
Published in: ACM Transactions on Database Systems
February 1, 2020

The adoption of differential privacy is growing, but the complexity of designing private, efficient, and accurate algorithms is still high. We propose a novel programming framework and system, ϵktelo, for implementing both existing and new privacy algorithms. For the task of answering linear counting queries, we show that nearly all existing algorithms can be composed from operators, each conforming to one of a small number of operator classes. While past programming frameworks have helped to ensure the privacy of programs, the novelty of our framework is its significant support for authoring accurate and efficient (as well as private) programs. After describing the design and architecture of the ϵktelo system, we show that ϵktelo is expressive, allows for safer implementations through code reuse, and allows both privacy novices and experts to easily design algorithms. We provide a number of novel implementation techniques to support the generality and scalability of ϵktelo operators. These include methods to automatically compute lossless reductions of the data representation, implicit matrices that avoid materialized state but still support computations, and iterative inference implementations that generalize techniques from the privacy literature. We demonstrate the utility of ϵktelo by designing several new state-of-the-art algorithms, most of which result from simple re-combinations of operators defined in the framework. We study the accuracy and scalability of ϵktelo plans in a thorough empirical evaluation.

Duke Scholars

Published In

ACM Transactions on Database Systems

DOI

EISSN

1557-4644

ISSN

0362-5915

Publication Date

February 1, 2020

Volume

45

Issue

1

Related Subject Headings

  • Information Systems
  • 4609 Information systems
  • 4605 Data management and data science
  • 4009 Electronics, sensors and digital hardware
  • 0806 Information Systems
  • 0804 Data Format
 

Citation

APA
Chicago
ICMJE
MLA
NLM
Zhang, D., McKenna, R., Kotsogiannis, I., Bissias, G., Hay, M., Machanavajjhala, A., & Miklau, G. (2020). ϵKtelo: A framework for defining differentially private computations. ACM Transactions on Database Systems, 45(1). https://doi.org/10.1145/3362032
Zhang, D., R. McKenna, I. Kotsogiannis, G. Bissias, M. Hay, A. Machanavajjhala, and G. Miklau. “ϵKtelo: A framework for defining differentially private computations.” ACM Transactions on Database Systems 45, no. 1 (February 1, 2020). https://doi.org/10.1145/3362032.
Zhang D, McKenna R, Kotsogiannis I, Bissias G, Hay M, Machanavajjhala A, et al. ϵKtelo: A framework for defining differentially private computations. ACM Transactions on Database Systems. 2020 Feb 1;45(1).
Zhang, D., et al. “ϵKtelo: A framework for defining differentially private computations.” ACM Transactions on Database Systems, vol. 45, no. 1, Feb. 2020. Scopus, doi:10.1145/3362032.
Zhang D, McKenna R, Kotsogiannis I, Bissias G, Hay M, Machanavajjhala A, Miklau G. ϵKtelo: A framework for defining differentially private computations. ACM Transactions on Database Systems. 2020 Feb 1;45(1).

Published In

ACM Transactions on Database Systems

DOI

EISSN

1557-4644

ISSN

0362-5915

Publication Date

February 1, 2020

Volume

45

Issue

1

Related Subject Headings

  • Information Systems
  • 4609 Information systems
  • 4605 Data management and data science
  • 4009 Electronics, sensors and digital hardware
  • 0806 Information Systems
  • 0804 Data Format