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

摘要

本发明利用进行正确的计算的概率低的计算装置进行函数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′。

主权项

一种代理计算系统，用于自订正技术，其特征在于，设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′。