%0 Conference Proceedings
%T Simple Storage-Saving Structure for Volume-Hiding Encrypted Multi-maps
%+ The Chinese University of Hong Kong [Hong Kong] (CUHK)
%A Wang, Jiafan
%A Chow, Sherman
%Z Part 2: Cryptology I
%< avec comité de lecture
%( Lecture Notes in Computer Science
%B 35th IFIP Annual Conference on Data and Applications Security and Privacy (DBSec)
%C Calgary, AB, Canada
%Y Ken Barker
%Y Kambiz Ghazinour
%I Springer International Publishing
%3 Data and Applications Security and Privacy XXXV
%V LNCS-12840
%P 63-83
%8 2021-07-19
%D 2021
%R 10.1007/978-3-030-81242-3_4
%K Volume hiding
%K Encrypted multi-maps
%K Consistent hashing
%K Structured encryption
%K Dynamic symmetric searchable encryption
%Z Computer Science [cs]Conference papers
%X Severe consequences in volume leakage (subject to the conditions required by specific attacks) stimulate a new research direction (Eurocrypt 2019) of volume-hiding structured encryption ($$\mathsf {STE}$$STE), particularly encrypted multi-maps ($$\mathsf {EMM}$$EMM), in which all queries should share the same (as the largest) response size unless the scheme is lossy. Meanwhile, note that the responses are originated from the actual ciphertexts outsourced to the server. Conventional wisdom suggests that the ciphertexts (to be accessed by the server while answering a query) should also contain many dummy results to make a query look uniform with others. Supporting updates is also natural; however, attaching dummy results to a query also complicates the operation and leakage of updates, which excludes many advanced data structures, e.g., cuckoo hashing (CCS 2019). This paper proposes a space-efficient $$\mathsf {EMM}$$EMM without storing any dummy ciphertext, which is volume hiding against passive adversaries (SP 2021) and compatible with dynamic extensions. Its crux structure is a hash ring, which is famous for load balancing but rarely appears in any $$\mathsf {STE}$$STE. Efficiency-wise, our scheme beats the state-of-the-art (Eurocrypt 2019, CCS 2019), maintaining the necessary communication overhead and downsizing the server storage to be linear in the number of values in the $$\mathsf {EMM}$$EMM, while ruling out any data loss due to truncations or differential privacy.
%G English
%Z TC 11
%Z WG 11.3
%2 https://inria.hal.science/hal-03677024/document
%2 https://inria.hal.science/hal-03677024/file/513274_1_En_4_Chapter.pdf
%L hal-03677024
%U https://inria.hal.science/hal-03677024
%~ IFIP-LNCS
%~ IFIP
%~ IFIP-TC
%~ IFIP-WG
%~ IFIP-TC11
%~ IFIP-WG11-3
%~ IFIP-DBSEC
%~ IFIP-LNCS-12840