Efficient private conjunctive query protocol over encrypted data

Tushar Kanti Saha*, Takeshi Koshiba


研究成果: Article査読


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.

出版ステータスPublished - 2021 3月

ASJC Scopus subject areas

  • 計算理論と計算数学
  • コンピュータ ネットワークおよび通信
  • コンピュータ サイエンスの応用
  • ソフトウェア
  • 応用数学


「Efficient private conjunctive query protocol over encrypted data」の研究トピックを掘り下げます。これらがまとまってユニークなフィンガープリントを構成します。