TY - JOUR
T1 - Information-Theoretically Secure and Highly E!icient Search and Row Retrieval
AU - Sharma, Shantanu
AU - Li, Yin
AU - Mehrotra, Sharad
AU - Panwar, Nisha
AU - Kumari, Komal
AU - Roychoudhury, Swagnik
N1 - Publisher Copyright:
© owner/author(s). Publication rights licensed to the VLDB Endowment.
PY - 2023
Y1 - 2023
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=85172729794&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85172729794&partnerID=8YFLogxK
U2 - 10.14778/3603581.3603582
DO - 10.14778/3603581.3603582
M3 - Conference article
AN - SCOPUS:85172729794
SN - 2150-8097
VL - 16
SP - 2391
EP - 2403
JO - Proceedings of the VLDB Endowment
JF - Proceedings of the VLDB Endowment
IS - 10
T2 - 49th International Conference on Very Large Data Bases, VLDB 2023
Y2 - 28 August 2023 through 1 September 2023
ER -