Provable secure dual-server public key encryption with keyword search
Kaibin Huang, Raylin Tso · 2017
In public key encryption with keyword search (PEKS) framework, see Figure 1(a), the cloud server stores index Iwand verifies the equivalence whether w = w' or not on receiving a keyword search request through a trapdoor Tw'. Aside from the traditional secrecy concerns over index, a new threat called inner keyword guessing attack which addressed the secrecy of trapdoors against off-line brute force attacks, was indicated by Chen et al. First, the index Iwis publicly computable; second, the domain of keywords is not big enough to resist brute force attacks; and third, the cloud server can verify the equivalence between keywords of index and trapdoors by itself. As a curious server, on input a trapdoor Tw', the server can keep computing index with different keywords w and tests the equivalence by itself until finding the keyword w' hidden in the trapdoors. That is, the secrecy of trapdoors can be easily broken. Furthermore, the `hacked trapdoor' can be utilized to test all the index in the database, which indirectly impacts the secrecy of index. Chen et al. propose a dual-server PEKS (DS-PEKS) syntax to deal with this issue. There are a front server and a back server in their architecture (see Figure 1(b)) and the keyword search test is done by the co-operation of two servers. Assume that these two servers do not collude, the DS-PEKS scheme will be secure against off-line inner keyword guessing attacks (although that the on-line inner keyword guessing attacks still work). However, several flaws occur in Chen et al.'s works so that the secrecy of index and trapdoors are not well-protected even against outside adversaries. In this work, we propose a new DS-PEKS construction based on the Cramer Shoup encryption, whose index and trapdoors are provably indistinguishable against chosen keyword attacks based on the IND-CCA2 security of the Cramer Shoup encryption without random oracle model.