Syntax-driven private evaluation of quantified membership queries

Aggelos Kiayias, Antonina Mitrofanova

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

3 Citations (Scopus)

Abstract

Membership queries are basic predicate operations that apply to data-sets. Quantifications of such queries express global properties between datasets, including subset inclusion and disjointness. These operations are basic tools in set-theoretic data-mining procedures such as frequent-itemset-mining. In this work we formalize a family of such queries syntactically and we consider how they can be evaluated in a privacy-preserving fashion. We present a syntax-driven compiler that produces a protocol for each query and we show that semantically such queries correspond to basic set operation predicates between datasets. Using our compiler and based on the fact that it is syntax-driven, two parties can generate various privacy-preserving protocols with different complexity behavior that allow them to efficiently and securely evaluate the predicate of interest without sharing information about the datasets they possess. Our compiler sheds new light on the complexity of privacy-preserving evaluation of predicates such as disjointness and subset-inclusion and achieves substantial complexity improvements compared to previous works in terms of round as well as communication complexity. In particular, among others, we present protocols for both predicates that require one-round of interaction and have communication less than the size of the universe, while previously the only one round protocols known had communication proportional to the size of the universe.

Original languageEnglish (US)
Title of host publicationApplied Cryptography and Network Security - 4th International Conference, ACNS 2006, Proceedings
PublisherSpringer Verlag
Pages470-485
Number of pages16
ISBN (Print)3540347038, 9783540347033
DOIs
StatePublished - Jan 1 2006
Event4th International Conference on Applied Cryptography and Network Security, ACNS 2006 - Singapore, Singapore
Duration: Jun 6 2006Jun 9 2006

Publication series

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

Other

Other4th International Conference on Applied Cryptography and Network Security, ACNS 2006
CountrySingapore
CitySingapore
Period6/6/066/9/06

Fingerprint

Predicate
Query
Privacy Preserving
Compiler
Communication
Evaluation
Inclusion
Data mining
Frequent Itemsets
Subset
Communication Complexity
Information Sharing
Quantification
Mining
Data Mining
Express
Directly proportional
Syntax
Evaluate
Interaction

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

Cite this

Kiayias, A., & Mitrofanova, A. (2006). Syntax-driven private evaluation of quantified membership queries. In Applied Cryptography and Network Security - 4th International Conference, ACNS 2006, Proceedings (pp. 470-485). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 3989 LNCS). Springer Verlag. https://doi.org/10.1007/11767480_33
Kiayias, Aggelos ; Mitrofanova, Antonina. / Syntax-driven private evaluation of quantified membership queries. Applied Cryptography and Network Security - 4th International Conference, ACNS 2006, Proceedings. Springer Verlag, 2006. pp. 470-485 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).
@inproceedings{62e5a1c628e74f8d97203b0f5911e644,
title = "Syntax-driven private evaluation of quantified membership queries",
abstract = "Membership queries are basic predicate operations that apply to data-sets. Quantifications of such queries express global properties between datasets, including subset inclusion and disjointness. These operations are basic tools in set-theoretic data-mining procedures such as frequent-itemset-mining. In this work we formalize a family of such queries syntactically and we consider how they can be evaluated in a privacy-preserving fashion. We present a syntax-driven compiler that produces a protocol for each query and we show that semantically such queries correspond to basic set operation predicates between datasets. Using our compiler and based on the fact that it is syntax-driven, two parties can generate various privacy-preserving protocols with different complexity behavior that allow them to efficiently and securely evaluate the predicate of interest without sharing information about the datasets they possess. Our compiler sheds new light on the complexity of privacy-preserving evaluation of predicates such as disjointness and subset-inclusion and achieves substantial complexity improvements compared to previous works in terms of round as well as communication complexity. In particular, among others, we present protocols for both predicates that require one-round of interaction and have communication less than the size of the universe, while previously the only one round protocols known had communication proportional to the size of the universe.",
author = "Aggelos Kiayias and Antonina Mitrofanova",
year = "2006",
month = "1",
day = "1",
doi = "10.1007/11767480_33",
language = "English (US)",
isbn = "3540347038",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Verlag",
pages = "470--485",
booktitle = "Applied Cryptography and Network Security - 4th International Conference, ACNS 2006, Proceedings",
address = "Germany",

}

Kiayias, A & Mitrofanova, A 2006, Syntax-driven private evaluation of quantified membership queries. in Applied Cryptography and Network Security - 4th International Conference, ACNS 2006, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 3989 LNCS, Springer Verlag, pp. 470-485, 4th International Conference on Applied Cryptography and Network Security, ACNS 2006, Singapore, Singapore, 6/6/06. https://doi.org/10.1007/11767480_33

Syntax-driven private evaluation of quantified membership queries. / Kiayias, Aggelos; Mitrofanova, Antonina.

Applied Cryptography and Network Security - 4th International Conference, ACNS 2006, Proceedings. Springer Verlag, 2006. p. 470-485 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 3989 LNCS).

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

TY - GEN

T1 - Syntax-driven private evaluation of quantified membership queries

AU - Kiayias, Aggelos

AU - Mitrofanova, Antonina

PY - 2006/1/1

Y1 - 2006/1/1

N2 - Membership queries are basic predicate operations that apply to data-sets. Quantifications of such queries express global properties between datasets, including subset inclusion and disjointness. These operations are basic tools in set-theoretic data-mining procedures such as frequent-itemset-mining. In this work we formalize a family of such queries syntactically and we consider how they can be evaluated in a privacy-preserving fashion. We present a syntax-driven compiler that produces a protocol for each query and we show that semantically such queries correspond to basic set operation predicates between datasets. Using our compiler and based on the fact that it is syntax-driven, two parties can generate various privacy-preserving protocols with different complexity behavior that allow them to efficiently and securely evaluate the predicate of interest without sharing information about the datasets they possess. Our compiler sheds new light on the complexity of privacy-preserving evaluation of predicates such as disjointness and subset-inclusion and achieves substantial complexity improvements compared to previous works in terms of round as well as communication complexity. In particular, among others, we present protocols for both predicates that require one-round of interaction and have communication less than the size of the universe, while previously the only one round protocols known had communication proportional to the size of the universe.

AB - Membership queries are basic predicate operations that apply to data-sets. Quantifications of such queries express global properties between datasets, including subset inclusion and disjointness. These operations are basic tools in set-theoretic data-mining procedures such as frequent-itemset-mining. In this work we formalize a family of such queries syntactically and we consider how they can be evaluated in a privacy-preserving fashion. We present a syntax-driven compiler that produces a protocol for each query and we show that semantically such queries correspond to basic set operation predicates between datasets. Using our compiler and based on the fact that it is syntax-driven, two parties can generate various privacy-preserving protocols with different complexity behavior that allow them to efficiently and securely evaluate the predicate of interest without sharing information about the datasets they possess. Our compiler sheds new light on the complexity of privacy-preserving evaluation of predicates such as disjointness and subset-inclusion and achieves substantial complexity improvements compared to previous works in terms of round as well as communication complexity. In particular, among others, we present protocols for both predicates that require one-round of interaction and have communication less than the size of the universe, while previously the only one round protocols known had communication proportional to the size of the universe.

UR - http://www.scopus.com/inward/record.url?scp=33746660642&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=33746660642&partnerID=8YFLogxK

U2 - 10.1007/11767480_33

DO - 10.1007/11767480_33

M3 - Conference contribution

SN - 3540347038

SN - 9783540347033

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 470

EP - 485

BT - Applied Cryptography and Network Security - 4th International Conference, ACNS 2006, Proceedings

PB - Springer Verlag

ER -

Kiayias A, Mitrofanova A. Syntax-driven private evaluation of quantified membership queries. In Applied Cryptography and Network Security - 4th International Conference, ACNS 2006, Proceedings. Springer Verlag. 2006. p. 470-485. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). https://doi.org/10.1007/11767480_33