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

摘要

When G and H are groups, f(x) is a function for obtaining the source of group G for x∈H, X₁ and X₂ are random variables having values in group G, x₁ is an observed value of the random variable X₁, and x₂ is an observed value of the random variable X₂, a calculation apparatus outputs τ₁ and τ₂ that correspond to a cryptogram (x), and a capability providing apparatus calculates f(τ₁) properly, using τ₁, with a probability higher than a certain probability and puts the result of the calculation as z₁, and calculates f(τ₂) properly, using τ₂, with a probability higher than a certain probability and puts the result of the calculation as z₂. The calculation apparatus then generates a calculation result u = f(x)^bx₁ from z₁, generates a calculation result v = f(x)^ax₂ from z₂, and outputs u^b'v^a' when the calculation results u and v satisfy a specific relationship.