A registration apparatus generates shares by secret sharing of a character string with a plurality of modulus and sends the shares to a plurality of server apparatuses to be stored therein. A retrieval apparatus sends shares generated by secret sharing of a retrieval character string with the plurality of modulus to the plurality of server apparatuses. The plurality of server apparatuses execute a subroutine for shares of the each registration character string stored in a storage unit and for each of the plurality of modulus, reconstruct an execution result, and determine whether or not to return the shares of the registration character string stored in the storage unit as a retrieval result. A retrieval apparatus reconstructs shares returned from the plurality of server apparatuses and obtains a retrieval result in which the retrieval character string hits, from the reconstructed result by the Chinese remainder theorem.