International Association for Cryptologic Research

International Association
for Cryptologic Research


Paper: Searchable Index Schemes for Groups : Security vs. Efficiency

Hyun-A Park
Yu Jeong Lee
Dong Hoon Lee
Search ePrint
Search Google
Abstract: A secure index search protocol makes it possible to search for the index of encrypted documents using specified keywords without decrypting them. %An untrusted database manager learns nothing more %than the search result about the documents without revealing the %keyword. These days, personally portable devices of huge storage such as a USB are easily used and hence private and sensitive documents of a user may be securely kept in such personal devices. However, secret documents shared by groups are usually stored in database. In real organizations such as government offices or enterprises with many departments, a group search occurs more often. In this paper, we propose two search schemes for a hierarchical group under an untrusted server ; A security-centered search scheme(SSIS) and an optimized efficient search scheme(ESIS) for commercial business use. We define `correlation resistance' as privacy requirement over encrypted search system and prove that SSIS can meet the notion. Also, we experimented two our proposed schemes. In the first try, the performance of both schemes was not good to use for practical business use. It was not until examining the reason of this that we learned the efficient DB schema must be applied into the search system for good performance. However, it was hard to apply efficient DB schema into SSIS because of its data structure. Hence, we applied efficient DB schema into only ESIS. The experiments show that ESIS is approximately 200 times faster than SSIS, which implies that other existing schemes are also not practical because the data structure of them is similar to SSIS. ESIS achieves real practicabilty by loosening its security, but with at least extend. Therefore, in the near future, it's required to develop keyword search system over encrypted data which is secure and applicable to efficient DB schema. In addition, we learned a lesson that works about the efficiency must consider mutual interactive operation with application layer as well as computational efficiency of a proposing scheme.
  title={Searchable Index Schemes for Groups : Security vs. Efficiency},
  booktitle={IACR Eprint archive},
  keywords={group search, encrypted data, keyword,trapdoor, index string, index list, efficient DB schema, primary key, foreign key},
  note={ 13506 received 11 Jul 2006, last revised 11 Jul 2006, withdrawn 24 Dec 2006},
  author={Hyun-A Park and Yu Jeong Lee and Dong Hoon Lee},