There is provided an encrypted message search technique making it difficult to, at the time of searching for a message in a state of being encrypted, guess content of the search and a result of the search. There are included: an encrypted search secret key transmission step of a terminal generating an encrypted search secret key from a search secret key generated each time an update interval set in advance elapses and transmitting the encrypted search secret key to a server; a search secret key decryption step of the terminal decrypting the encrypted search secret key acquired from the server to obtain the search secret key; an encrypted message transmission step of the terminal transmitting an index set generated using information related to a message and a newest search secret key, and an encrypted message to the server; a query transmission step of the terminal transmitting a query set generated using a message search character string and the search secret key; and an encrypted message returning step of the server transmitting an encrypted message including elements of an index set corresponding to an element of the query set.