SUBSTITUTION CALCULATION SYSTEM, CALCULATION APPARATUS, CAPABILITY PROVIDING APPARATUS, SUBSTITUTION CALCULATION METHOD, CAPABILITY PROVIDING METHOD, PROGRAM, AND RECORDING MEDIUM

摘要

A computing apparatus outputs Ä 1 and Ä 2 corresponding to a ciphertext x, a capability providing apparatus uses Ä 1 to correctly compute f(Ä 1 ) with a probability greater than a certain probability and sets the result of the computation as z 1 , uses Ä 2 to correctly compute f(Ä 2 ) with a probability greater than a certain probability and sets the result of the computation as z 2 , the computing apparatus generates a computation result u = f(x) b x 1 from z 1 , generates a computation result v = f(x) a x 2 from z 2 , and outputs u b' v a' if the computation results u and v satisfy a particular relation, where G and H are groups, f(x) is a function for obtaining an element of the group G for x ˆˆ H, X 1 and X 2 are random variables having values in the group G, x 1 is a realization of the random variable X 1 , and x 2 is a realization of the random variable X 2 .