A storage count verification system is provided in which a client can verify the number of identical data items stored by a server without the server being notified of the results. A storage count verification system verifies whether a user device and a server device have identical data where search data requested by a user device is used to search data to be searched on a server device. The server device generates a public parameter for searching the data to be searched and transmits the generated public parameter to the user device. The user device is provided with a user generation unit for generating, on the basis of the public parameter received from the server device, a secret parameter that is for the search data and corresponds to the public parameter and a user encryption unit for encrypting the search data on the basis of the generated secret parameter.