A data search server stores a system ciphertext including a data ciphertext and a keyword ciphertext in each category-specific DB unit for each data category, and stores each category-determination secret key being associated with each category-specific DB unit. A search request receiving unit receives from a data search terminal a search request including a search trapdoor and an index tag. A data searching unit searches for a category-determination secret key with which the index tag is decrypted to the same value as a key-determination value. Using the search trapdoor, the data searching unit performs a search of a Public-key Encryption with Keyword Search scheme on system ciphertexts in a category-specific DB unit associated with this category-determination secret key. A search result transmitting unit transmits to the data search terminal a data ciphertext included in a system ciphertext which has been found as a hit in the search.