代理计算系统、方法及代理计算委托装置

摘要

本发明利用进行正确的计算的概率低的计算装置进行函数f（x）的计算。设G、H为循环群，设f为将群H的元x映射到群G的函数，设X₁、X₂为在群G中具有数值的随机变量，设随机变量X₁的表现值为x₁，设随机变量X₂的表现值为x₂，整数计算部利用互素的两个自然数a、b，计算满足a′a＋b′b＝1的关系的整数a′、b′。第一可随机数化抽样器，可计算f（x）^bx₁，将其计算结果设为u。第一幂计算部计算u′＝u^a。第二可随机数化抽样器可计算f（x）^ax₂，将其计算结果设为v。第二幂计算部计算v′＝v^b。判定部判定是否为u′＝v′。最终计算部在判定为u′＝v′的情况下，计算u^b′v^a′。