A user permission check system with less CPU throughput while ensuring non-repudiation is provided. In order to solve the above-described problem, in the present invention firstly, a MAC function that does not require a CPU to have high processing power is utilized. Additionally, a message is encrypted with a plurality of secret keys and the plurality of keys are distributed to a plurality of servers to make them have the keys in order to ensure validity of the message as a proof of non-repudiation. Subsequently, each server proves the validity of the message within its own range and the validity of the message is ensured by aggregating these individual results, thereby implementing the non-repudiation.