Multi-Adjustable Join Schemes With Adaptive Indistinguishably Security
Mojtaba Rafiee · IEEE Transactions on Dependable and Secure Computing · 2023
A multi-adjustable join ($\rm{M-Adjoin}$) scheme [Khazaei-Rafiee, IEEE TDSC 2020], a generalization of$\rm{Adjoin}$scheme [Popa-Zeldovich, MIT CSAIL TR 2012], is a symmetric-key primitive that enables a user to securely outsource his database to an external server, and later to issue join queries for a list of columns. In [Rafiee-Khazaei, IEEE TDSC 2021], based on the previously defined security notions for$\rm{Adjoin}$[Mironov-Segev-Shahaf, TCC 2017], several security notions for$\rm{M-Adjoin}$were proposed and their relationships were investigated. Constructing an$\rm{M-Adjoin}$with indistinguishability security against adaptive adversary has remained a challenging problem so far. In this paper, we introduce two$\rm{M-Adjoin}$constructions to achieve this strong security notion in the random oracle model. We prove the security of our constructions under Decisional Diffie-Hellman assumption in$\mathbb {G}_{1}$(DDH1) in the bilinear groups. Compared with previous constructions, despite having a higher security level, the computation and storage overheads do not increase.