Efficient private conjunctive query protocol over encrypted data

Tushar Kanti Saha*, Takeshi Koshiba

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review


Conjunctive queries play a key role in retrieving data from a database. In a database, a query containing many conditions in its predicate, connected by an “and/&/∧” operator, is called a conjunctive query. Retrieving the outcome of a conjunctive query from thousands of records is a heavy computational task. Private data access to an outsourced database is required to keep the database secure from adversaries; thus, private conjunctive queries (PCQs) are indispensable. Cheon, Kim, and Kim (CKK) proposed a PCQ protocol using search-and-compute circuits in which they used somewhat homomorphic encryption (SwHE) for their protocol security. As their protocol is far from being able to be used practically, we propose a practical batch private conjunctive query (BPCQ) protocol by applying a batch technique for processing conjunctive queries over an outsourced database, in which both database and queries are encoded in binary format. As a main technique in our protocol, we develop a new data-packing method to pack many data into a single polynomial with the batch technique. We further enhance the performances of the binary-encoded BPCQ protocol by replacing the binary encoding with N-ary encoding. Finally, we compare the performance to assess the results obtained by the binary-encoded BPCQ protocol and the N-ary-encoded BPCQ protocol.

Original languageEnglish
Article number2
Pages (from-to)1-28
Number of pages28
Issue number1
Publication statusPublished - 2021 Mar


  • Encrypted data
  • Homomorphic encryption
  • Packing method
  • Private conjunctive query

ASJC Scopus subject areas

  • Computational Theory and Mathematics
  • Computer Networks and Communications
  • Computer Science Applications
  • Software
  • Applied Mathematics


Dive into the research topics of 'Efficient private conjunctive query protocol over encrypted data'. Together they form a unique fingerprint.

Cite this