Information-Theoretically Secure and Highly E!icient Search and Row Retrieval

Shantanu Sharma, Yin Li, Sharad Mehrotra, Nisha Panwar, Komal Kumari, Swagnik Roychoudhury

Research output: Contribution to journalConference articlepeer-review


Information-theoretic or unconditional security provides the highest level of security - independent of the computational capability of an adversary. Secret-sharing techniques achieve information- theoretic security by splitting a secret into multiple parts (called shares) and storing the shares across non-colluding servers. How-ever, secret-sharing-based solutions suffer from high overheads due to multiple communication rounds among servers and/or information leakage due to access-patterns (i.e., the identity of rows satisfying a query) and volume (i.e., the number of rows satisfying a query). We propose S2, an information-theoretically secure approach that uses both additive and multiplicative secret-sharing, to efficiently support a large class of selection queries involving conjunctive, disjunctive, and range conditions. Two major contributions of S2 are: (i) a new search algorithm using additive shares based on fingerprints, which were developed for string-matching over cleartext; and (ii) two row retrieval algorithms: one is based on multiplicative shares and another is based on additive shares. !2 does not require communication among servers storing shares and does not reveal any information to an adversary based on access-patterns and volume.

Original languageEnglish (US)
Pages (from-to)2391-2403
Number of pages13
JournalProceedings of the VLDB Endowment
Issue number10
StatePublished - 2023
Externally publishedYes
Event49th International Conference on Very Large Data Bases, VLDB 2023 - Vancouver, Canada
Duration: Aug 28 2023Sep 1 2023

All Science Journal Classification (ASJC) codes

  • Computer Science (miscellaneous)
  • General Computer Science


Dive into the research topics of 'Information-Theoretically Secure and Highly E!icient Search and Row Retrieval'. Together they form a unique fingerprint.

Cite this