Abstract
Outsourcing encrypted data to cloud servers that has become a prevalent trend among Internet users to date. There is a long list of advantages on data outsourcing, such as the reduction cost of local data management. How to securely operate encrypted data (remotely), however, is the top-rank concern over data owner. Liang et al. proposed a novel encrypted cloud-based data share and search system without loss of privacy. The system allows users to flexibly search and share encrypted data as well as updating keyword field. However, the search complexity of the system is of extreme inefficiency, <inline-formula><tex-math notation="LaTeX">O(n d)</tex-math> <mml:math><mml:mrow><mml:mi>O</mml:mi><mml:mo>(</mml:mo><mml:mi>n</mml:mi><mml:mi>d</mml:mi><mml:mo>)</mml:mo></mml:mrow></mml:math><inline-graphic xlink:href="chen-ieq1-3004988.gif"/> </inline-formula>, where <inline-formula><tex-math notation="LaTeX">d</tex-math> <mml:math><mml:mi>d</mml:mi></mml:math><inline-graphic xlink:href="chen-ieq2-3004988.gif"/> </inline-formula> is the total number of system files and <inline-formula><tex-math notation="LaTeX">n</tex-math> <mml:math><mml:mi>n</mml:mi></mml:math><inline-graphic xlink:href="chen-ieq3-3004988.gif"/> </inline-formula> is the size of query formula. This article, for the first time, leverages the "oblivious cross search" technology in public key searchable encryption context to reduce the search complexity to only <inline-formula><tex-math notation="LaTeX">O(nf(w))</tex-math> <mml:math><mml:mrow><mml:mi>O</mml:mi><mml:mo>(</mml:mo><mml:mi>n</mml:mi><mml:mi>f</mml:mi><mml:mo>(</mml:mo><mml:mi>w</mml:mi><mml:mo>)</mml:mo><mml:mo>)</mml:mo></mml:mrow></mml:math><inline-graphic xlink:href="chen-ieq4-3004988.gif"/> </inline-formula>, where <inline-formula><tex-math notation="LaTeX">f(w)</tex-math> <mml:math><mml:mrow><mml:mi>f</mml:mi><mml:mo>(</mml:mo><mml:mi>w</mml:mi><mml:mo>)</mml:mo></mml:mrow></mml:math><inline-graphic xlink:href="chen-ieq5-3004988.gif"/> </inline-formula> is the number of files embedded with the "least frequent keyword" <inline-formula><tex-math notation="LaTeX">w</tex-math> <mml:math><mml:mi>w</mml:mi></mml:math><inline-graphic xlink:href="chen-ieq6-3004988.gif"/> </inline-formula>. The new scheme maintains efficient encrypted data share and keyword field update as well. This article further revisits the security models for payload security, keyword privacy and search token privacy (i.e., search pattern privacy) and meanwhile, presents security and efficiency analysis for the new scheme.