International Association
for Cryptologic Research

Data outsourcing is a solution aimed at addressing the security and reliability issues of data storage by ensuring professional handling of the data. The growing use of outsourcing is causing concern among users due to the lack of assurance regarding the security and reliability of data stored on servers. To address these issues, some attempts have been made to implement Secret Sharing-based Data Outsourcing (SSDO) schemes. The low efficiency of these schemes led researchers to use an index server (IS). However, IS are susceptible to frequency analysis. Bucket-Chain $B^+Tree$ ($BCB^+Tree$) was proposed to tackle the frequency analysis in the current Index Server Secret Sharing-based Data Outsourcing (ISSDO) schemes. Nevertheless, this scheme works very well when the data is discrete with a limited range. Otherwise, the scheme's efficiency declines significantly as it has to store one index in each bucket and the number of buckets rises significantly, rendering the use of an IS useless. In this paper, a new data structure is proposed to store the indexes in IS to mitigate this efficiency concern. Briefly, the domain of values is divided into several segments, and indexes of values in each segment are stored inside a $Shard$. Additionally, a data outsourcing scheme has been presented based on the proposed data structure. It can withstand collaboration from up to $k-1$ dishonest servers even if they have access to the IS.