Patent ID: 7974405

Claim:
A method of calculating a value of a given function by using an apparatus including a plurality of computers, comprising: an input process; an ElGamal cipher text preparation process; a sequential substitution reencryption process; and a result output process, characterized in that the input process comprises an information input step of inputting to the plurality of computers information on a circuit including a plurality of gates and the information, and a dispersion input step of inputting to each of the computers each one of plural pieces of partial data which are obtained by dispersing input data of the given function into plural pieces by the number of the computers, the ElGamal cipher text preparation process comprises an ElGamal cipher text preparation step in which at least one of the computers generates a set of ElGamal cipher texts corresponding to inputs of the gates of the circuit that realizes the given function, the sequential substitution reencryption process comprises a step of allowing each of the computers to perform a substitution reencryption process one after another, and the substitution reencryption process comprises a cipher text obtaining step of allowing the computer in turn to receive the set of ElGamal cipher texts from the computer in the previous turn, a cipher text substitution and reencryption step of changing an order of the set of ElGamal cipher texts received in the cipher text obtaining step for substitution and subjecting those cipher texts to reencryption, a step of disclosing the data generated in the cipher text substitution and reencryption step to at least the computer in next order, and a step of stopping the sequential substitution reencryption process when all of the computers have performed the sequential substitution reencryption process, and the result output process comprises a partial decryption step of deciphering or partially deciphering a part of the cipher texts generated in the cipher text substitution and reencryption step, a decryption step of deciphering a cipher text that enciphers data corresponding to the input to the circuit in the cipher texts generated in the cipher text substitution and reencryption step, and an evaluation step of evaluating an output of the circuit by using the data deciphered in the decryption step and the data partially deciphered in the partial decryption step.