代理计算系统、方法、委托装置、程序及其记录介质的制作方法
专利名称：代理计算系统、方法、委托装置、程序及其记录介质的制作方法
技术领域：
本发明涉及计算机的计算技术。特别涉及利用使其他计算机进行的计算结果进行计算的技术。
背景技术：
委托装置利用委托于不一定进行正确的计算的计算装置的计算结果进行函数f的计算，该技术在非专利文献I中有所记载。非专利文献I记载的自订正器通过多次委托于计算装置进行计算，且采用其计算结果的多数决定，进行函数f的计算(例如，参照非专 利文献I)。现有技术文献非专利文献非专利文献I M. Blum, M. Lub y, and R. Rub inf eld, “Self — Testing/Correctingwith Applications to Numerical Problems”，STOC 1990,pp.73 — 83.
发明内容
发明要解决的课题但是，存在如下课题，S卩，为了非专利文献I的自订正器正常地动作，计算装置需要以一定以上的概率进行正确的计算，利用进行正确的计算的概率低的计算装置进行函数f的计算的技术不得而知。用于解决课题的手段本发明第一方式的代理计算系统设G、H为循环群，设f为将群H的元χ映射到群G的函数，设XpX2为在群G中具有数值的随机变量，设随机变量X1的表现值为X1,设随机变量X2的表现值为X2，包含整数计算部，利用互素的两个自然数a、b，计算满足a' a + b' b=I的关系的整数a,、b,;第一可随机数化抽样器，能够计算f (X)bX1，将其计算结果设为U ;第一幂计算部,计算U' = Ua ;第二可随机数化抽样器,能够计算f (X) aX2,将其计算结果设为V ;第二幂计算部，计算V' = Vb ;判定部，判定是否为u' =V';最终计算部,在判定为U' =V'的情况下，计算Ub' Va/。本发明第二方式的代理计算系统设G、H及F为循环群，设映射Θ :GXH —F为双同态同态映射，设g为群G的元，设h为群H的元，设Ke为群G的位数，设Kh为群H的位数，设μ g为群G的生成元,设μ h为群H的生成元,设V = θ ( μ g，μ 8)，设k为自然数的安全参数，设K = 2k，委托装置包含第一随机数生成部，生成O以上不足Ke的整数的随机数Γι ;第二随机数生成部，生成O以上不足Kh的整数的随机数r2 ;第一输入信息计算部，计算第一输入信息gl= μ ,g;第二输入信息计算部，计算第二输入信息4= μ f ;第一列表信息计算部，利用从计算装置接收到的Z1 e F，计算Z1 v_&2 ;第一列表存储部，对由随机数r2和计算出的Z1 构成的信息组(r2，Z1 V—rw)进行存储；第三随机数生成部，生成O以上不足K的整数的均匀随机数即Cl1 ;第四随机数生成部，生成O以上不足Ke的整数的均匀随机数即r4 ;第五随机数生成部，生成O以上不足&的整数的均匀随机数即r5 ;第三输入信息计算部，计算第三输入信息g2= μ/4gdl;第四输入信息计算部，计算第四输入信息h2= yhr5；第二列表信息计算部，利用从计算装置接收到的Z2 e F，计算Z2 ;第二列表存储部，对由C^r5和计算出的、产构成的信息组(dpivh v_rtri)进行存储；第一判定部，设从第一列表存储部读入的信息组的第一成分为S1，设第二成分为W1，且设从第二列表存储部读入的信息组的第一成分为t2，设第二成分为S2，设第三成分为W2，判定这些信息组是否满足(W1) ' Ct2S2S1-1) = W2的关系,在满足其关系的情况下,将S1代入O，将W1代入V ,;第六随机数生成部，生成O以上不足Ke的整数的均匀随机数即r6 ;第七随机数生成部，生成O以上不足Kh的整数的均匀随机数即r7 ;第五输入信息计算部，计算第五输入信息g3 = gr6 ;第六输入信息计算部，计算第六输入信息h3 = yhr70h ;第三列表信息计算部，利用从计算装置接收到的Z3 e F，计算Z3 V' 第三列表存储部，对由&和计算出的& γ' 构成的信息组(r6，z3 V ' 进行存储；第八随机数生成部，生成O以上不足K的整数的均匀随机数即d2 ;第九随机数生成部，生成O以上不足Ke的整数的均匀随机数即r9 ;第十随机数生成部，生成O以上不足Kh的整数的均匀随机数即r1(l ;第七输入信息计算部，计算第七输入信息g4 = μ gr9 ;第八输入信息计算部，计算第八输入信息h4 = μ hrl° σ hd2 ;第四列表信息 计算部，利用从计算装置接收到的Z4 e F，计算Z4 V ' -r9r10 ;第四列表存储部，对由d2、r9和计算出的Z4 V ' —.Η)构成的信息组(d2，rg，Z4 γ ' -aw)进行存储；第二判定部，设从第三列表存储部读入的信息组的第一成分为S3，设第二成分为W3，且设从第四列表存储部读入的信息组的第一成分为U，设第二成分为S4，设第三成分为W4，判定这些信息组是否满足(W3) aU4S4S,) = W4的关系，在满足其关系的情况下，将(W3) a (巧-1)输出。计算装置包含第一输出信息计算部，可利用从委托装置接收到的^及h，计算Θ (gl，4)，将其计算结果设为Z1而输出；第二输出信息计算部，可利用从委托装置接收到的g2&h2，计算Θ (g2，h2)，将其计算结果设为Z2而输出；第三输出信息计算部，可利用从委托装置接收到的&及匕，计算Θ (g3，h3)，将其计算结果设为Z3而输出；以及第四输出信息计算部，可利用从委托装置接收到的g4&h4,计算Θ (g4, h4),将其计算结果设为Z4而输出。发明的效果能够利用进行正确的计算的概率低的计算装置进行函数f的计算。
图I是第一实施方式 第三实施方式的代理计算系统的例子的功能方框图。图2是第一实施方式 第三实施方式的委托装置及计算装置的例子的功能方框图。图3是第一实施方式 第三实施方式的抽样器的例子的功能方框图。图4是第一实施方式 第三实施方式的第一可随机数化抽样器及第二可随机数化抽样器的例子的功能方框图。图5是第一实施方式 第三实施方式的第一可随机数化抽样器及第二可随机数化抽样器的另一例的功能方框图。图6是第一实施方式 第三实施方式的代理计算方法的例子的流程图。图7是表示步骤S3的例子的流程图。
图8是表示步骤S6的例子的流程图。图9是表不步骤S3的另一例的流程图。图10是表示步骤S6的另一例的流程图。图11是第四实施方式 第十实施方式的代理计算系统的例子的功能方框图。图12是第四实施方式 第十实施方式的委托装置的例子的功能方框图。图13是第四实施方式 第十实施方式的委托装置的例子的功能方框图。图14是第四实施方式 第十实施方式的计算装置的例子的功能方框图。图15是第四实施方式 第十实施方式的代理计算方法的例子的流程图。 图16是第四实施方式 第十实施方式的代理计算方法的例子的流程图。图17是代理计算系统的变形例的功能方框图。
具体实施例方式下面，对本发明的代理计算系统、代理计算方法的实施方式进行详细说明。第一实施方式 第二实施方式是利用委托装置I委托于计算装置2的计算结果来计算f (X)的实施方式。[第一实施方式]如图I所示，第一实施方式的代理计算系统包含委托装置I及计算装置2，利用委托装置I委托于计算装置2的计算结果，来计算f U)。如图2所示，委托装置I例如包含自然数存储部11、整数计算部12、第一幂计算部13、第一列表存储部14、判定部15、第二幂计算部16、第二列表存储部17、控制部18及最终计算部19。计算装置2例如包含第一可随机数化抽样器21及第二可随机数化抽样器22。在第一实施方式中，第一可随机数化抽样器21及第二可随机数化抽样器22对应于计算装置2。设G、H为循环群，设函数f :H — G为将群H的元χ映射到群G的函数，设群G、H的生成元分别为μ8、μ h，设Xp X2为在群G中具有数值的随机变量，设随机变量X1的表现值为X1，设随机变量X2的表现值为X2。在自然数存储部11存储有多个互素的两个自然数a、b的组(a，b)。当设I为不足群G的位数的两个自然数的组且互素的自然数的集合时，可认为在自然数存储部11存储有与I的子集S对应的自然数a、b的组(a，b)。整数计算部12从存储于自然数存储部11的多个自然数的组(a，b)中随机地读入一个自然数的组(a，b)，利用其读入的自然数的组(a，b)，计算满足a' a + b' b = I的关系的整数a'、b'(步骤SI)。由于自然数a、b互素，因此必定存在满足a' a + b/ b =I的关系的整数a,、b,。自然数的组(a，b)的信息发送到第一幂计算部13、第二幂计算部16、第一可随机数化抽样器21及第二可随机数化抽样器22。自然数的组(a'，b,)的信息发送到最终计算部19。控制部18设为t = I (步骤S2)。第一可随机数化抽样器21可计算f (x) bX1，利用χ及b进行计算，将其计算结果设为u (步骤S3)。计算结果u发送到第一幂计算部13。在该申请中，可计算的意思是可按不能忽略的概率以上的概率进行计算。不能忽略的概率是在将安全参数k的广义单调函数即多项式设为多项式F (k)时I / F (k)以上的概率。在此，计算f (X)bX1是对定义为f (χ)\的式的值进行计算。如果能够最终地计算式f (X)bX1的值，则不论计算过程中的计算方法。这关于该申请中出现的其他式的计算也同样。第一幂计算部13计算u' = Ua (步骤S4)。计算结果u和基于其计算结果计算出的u'的组U，u')存储于第一列表存储部14。判定部15判定是否在存储于第一列表存储部14的组(u，u')及存储于第二列表存储部17的组(V，V )中存在成为u' =Y '的组(步骤S5)。假如在第二列表存储部17中未存储有组(V，V')，则不进行该步骤S5的处理，而是进行下一步骤S6的处理。在存在成为u' =V'的组的情况下,进入步骤12。在不存在成为u' =V'的组的情况下,进入步骤S6。第二可随机数化抽样器22可计算f (X) aX2，利用χ及a进行计算，将其计算结果设为V (步骤S6)。计算结果V发送到第二幂计算部16。第二幂计算部16计算V' = Vb (步骤S7)。计算结果V和基于其计算结果计算出的V'的组(V, Y1 )存储于第二列表存储部17。判定部15判定是否在存储于第一列表存储部14的组(u，u')及存储于第二列表存储部17的组(V, V')中存在成为u' =V'的组(步骤S8)。在存在成为u' =V'的组的情况下，进入步骤12。在不存在成为u' =Y'的组情况下，进入步骤S9。控制部18判定是否为t = T (步骤S9)。T为预定的自然数。如果t = T，则将表示不能进行计算的信息例如符号“丄”输出(步骤SI I )，然后结束处理。在不是t = T的情况下，控制部18仅将t加1，即设为t = t + I (步骤S10)，然后返回到步骤S3。表示不能进行计算的信息(在该例子中，符号“丄”)的意思是指计算装置2正确地进行计算的可靠性低于用T规定的基准。换言之，意思是指不能通过T次的重复来进行正确的运算。最终计算部19在判定为u' =V'的情况下,利用与其u'及V'对应的u及V,计算ub' Va/，且将其输出(步骤S12)。成为计算出的ub' va/ =f(x)。关于成为ub' Va/=f (X)的理由，后面进行描述。《关于成为Ub'va/ =f(x)的理由》设X为在群G中具有数值的随机变量。关于w e G，每当某计算装置接收请求时都根据随机变量R抽取样本f并回复《V的抽样器称为关于w具有误差X的抽样器(sampler)。关于w e G，将每当某计算装置接收自然数a的输入时都根据随机变量X抽取样本χ'并回复WaX'的抽样器称为关于w具有误差X的可随机数化抽样器(randomizablesampler)。可随机数化抽样器如果用作a = I，则作为抽样器发挥功能。上述实施方式的代理计算系统在构成输入χ而输出f (χ)的代理计算系统时，使用关于f (x)具有误差X1的第一可随机数化抽样器21、关于f (χ)具有误差X2的第二可随机数化抽样器22。发明者发现，u' = N'成立即ua = Vb成立的理由是第一可随机数化抽样器21正确地计算出U = f (X) bX1,且第二可随机数化抽样器22正确地计算出V = f (X) aX2,进而X1及X2为群G的单位元eg的可能性非常高。在此，省略其证明。在第一可随机数化抽样器21正确地计算出u = f (X)bX1、第二可随机数化抽样器22正确地计算出v = f (χ) aX2,且X1及X2为群G的单位元eg时,成为ub/ va/ = (f (χ)bXl)b/ (f (x)ax2)a/ =(f (x)beg)b/ (f (x)aeg)a/ = f (x)bb/ egb/ f (x)aa/ ega/
=f (X) (bbI +aa, )= f (x)。关于(q1; q2) e I，关于i = 1、2,分别用Jii (q1; q2) = Qi来定义函数π it)另外，设为L = min (# π 1 (S), # π 2 (S))。# 为集合 的位数。在群G为循环群及不易进行位数的计算的群时，上述代理计算系统输出“丄”以外时的输出不是f (x)的概率在可忽略的程度的误差范围内最高可期待T2L / #S程度。如果L / #3为可忽略的量且T为多项式级程度的量，则上述代理计算系统就以压倒性的概率输出f U)。在L / #S达到可忽略的量那样的S的例子中，存在例如S ={(l，d) I de[2，I G I — I]}。另外，如图2中的虚线所示，也可以在计算装置2上设置抽样器23。抽样器23设X3为在群G中具有数值的随机变量、设随机变量X3的表现值为X3，从而可计算f (x) X3，如果a = 1，则代替第二可随机数化抽样器22，将其计算结果设为上述V，如果b = 1，则代替第一可随机数化抽样器21，将其计算结果设为上述U。通常，抽样器的计算量比可随机数化抽样器小。在a = l、b = I时，通过抽样器23代替第一可随机数化抽样器21、第二可随机数化抽样器22进行计算，能够减小计算装置2
的计算量。[第二实施方式]第二实施方式的代理计算系统是将第一可随机数化抽样器21及第二可随机数化抽样器22的一个例子具体化而成的系统，换言之，是将步骤S3及步骤S6的一个例子具体化而成的系统。下面，以与第一实施方式不同的部分为中心进行说明，关于共同的部分，省略重复说明。如图3所示，第二实施方式的第一可随机数化抽样器21例如包含第一随机数生成部110、第一输入信息计算部111、第一输出信息计算部24及第一计算部112。另外，如图3所示，第二实施方式的第二可随机数化抽样器22例如包含第二随机数生成部113、第二输入信息计算部114、第二输出信息计算部25及第二计算部115。在第二实施方式中，第一随机数生成部110、第一输入信息计算部111、第一计算部112、第二随机数生成部113、第二输入信息计算部114及第二计算部115包含在委托装置I中。另外，第一输出信息计算部24及第二输出信息计算部25包含在计算装置2中。在第二实施方式中，第一输出信息计算部24及第二输出信息计算部25与计算装置2对应。第二实施方式的函数f设为同态映射(準同型写像)。另外，设群H的生成元为yh，设群H的位数为Kh,设V = f ( μ h)0步骤S3由图7例示的步骤S31 步骤S34构成。第一随机数生成部110生成O以上不足Kh的整数的均匀随机数Γι(步骤S31)。生成的随机数发送到第一输入信息计算部111。第一输入信息计算部111计算第一输入信息μ hrlxb (步骤S32)。计算出的第一输入信息μ J1Xb发送到第一输出信息计算部24。第一输出信息计算部24利用第一输入信息μ J1Xb进行计算，将其计算结果设为第一输出信息Z1 (步骤S33)。计算出的第一输出信息Z1发送到第一计算部112。第一输出信息计算部24可计算f ( μ hrlxb)0第一输出信息计算部24的计算结果有时是f (μJ1Xb)，有时不是f UhW在此，411的右上角的1'1是1'1的意思。这样，在该申请中，在设α为第一字符、β为第二字符、Y为数字并表述为α 的情况下，该β Y的意思是β Y，S卩，β的下标Y。
第一计算部112计算Z1 V _ri，将其计算结果设为u(步骤S34)。计算结果u发送到第一幂计算部13。在此，u = Z1 V n = f (x) bX10即，Z1 V μ成为关于f (χ)具有误差X1的可随机数化抽样器。关于其理由，后面进行描述。步骤S6由图8例示的步骤S61 步骤S64构成。第二随机数生成部113生成O以上不足Kh的整数的均匀随机数r2(步骤S61)。生成的随机数r2发送到第二输入信息计算部114。第二输入信息计算部114计算第二输入信息4!；^步骤562)。计算出的第二输入信息μ hr2xa发送到第二输出信息计算部25。第二输出信息计算部25利用第二输入信息μ J2Xa进行计算，将其计算结果设为第二输出信息Z2 (步骤S63)。计算出的第二输出信息Z2发送到第二计算部115。第二输出信息计算部25可计算f ( μ hrtxa)。第二输出信息计算部25的计算结果有时是f (μJ2Xa),有时不是f (UhrV)0第二计算部115计算Z2 V 将其计算结果设为V (步骤S64)。计算结果V发送到第二幂计算部16。在此，成为￥ = 2^— = €(1)12。S卩，Z2 V —成为关于f (χ)具有误差X2的可随机数化抽样器。关于其理由，后面进行描述。在第二实施方式中，也可以在a = Ub=I时，通过抽样器23代替第一可随机数化抽样器21或第二可随机数化抽样器22而计算u或V的值，来消减计算量。如图4所不,第二实施方式的抽样器23例如包含第三随机数生成部116、第三输入信息计算部117、第三输出信息计算部26、第三计算部118。第三随机数生成部116、第三输入信息计算部117及第三计算部118包含在委托装置I中。第三输出信息计算部26包含在计算装置2中。如果a = I、b = 1，则抽样器23的各部代替第一可随机数化抽样器21、第二可随机数化抽样器22，进行下面的处理。第三随机数生成部116生成O以上不足Kh的整数的随机数r3。生成的随机数r3发送到第三输入信息计算部117。第三输入信息计算部117计算第三输入信息Xlr3。计算出的第三输入信息Xlr3发送到第三输出信息计算部26。第三输出信息计算部26利用第三输入信息V3进行计算，将其计算结果设为第三输出信息z3。计算出的第三输出信息Z3发送到第三计算部118。第三输出信息计算部26可计算f (χΛ)。第三输出信息计算部26的计算结果有时是f (ΧΛ)，有时不是f (Xr3)0第三计算部118计算z31/l:3,如果是a = I，则将其计算结果设为V,如果是b = I,则将其计算结果设为U。计算结果V发送到第二幂计算部16。计算结果u发送到第一幂计算部13。在此,成为u = V = Z31"3 = f (X)X30 S卩，z31/l:3成为关于f (χ)具有误差X3的抽样器。Ζ31/λ成为关于f (χ)具有误差X3的抽样器。其理由，后面进行描述。在难以进行ζ31/ 的计算即Z3的方根的计算的情况下，也可以如下那样计算u及/或V。第三计算部118将随机数1*3和基于其随机数1*3计算出的23的组依次设为(Ci1, ^)，(α2, β2)，…，(απ，βω),…，且将其存储于未图示的存储部。m为自然数。第三计算部118如果Ct1, α 2,…，α ^的最小公倍数达到I，则也可以将Y1, y 2,…，Yni设为整数,计
算成为 Y1Q1+ Y2Q2 H-----h Y111Ct ^ = I 的 Y1, Y2,…，Y 利用该 Y1, Y2, Ym, if
算IIi = = β/1 β /2…β mYm，将其计算结果设为u及/或V。这样，通过将利用随机数干扰χ的信息发送到计算装置2，能够将成为函数f的值的计算对象的X eH相对于对委托装置I和计算装置2之间的通信进行拦截的第 三者及计算装置2保密。《关于Z1V ' Z2 V -2成为关于f (χ)分别具有误差Xp X2的可随机数化抽样器的
理由》设c为自然数、R及R'为随机数，将计算装置2利用μ 进行计算的计算结果设为Β( μ hW即，当将计算装置2返送到委托装置I的计算结果设为z时，z = Β( μ hExc)),将在群G中具有数值的随机变量X定义为X = B ( μ hK' )f ( yhE/ ) '这时，成为ZV-K = B (μ hExc) f ( μ h) = Xf (μ hExc) f ( μ h) = Xf ( μ h) Ef(x)cf ( μ h) = f (X) CX。即，ZV-^成为关于f (χ)具有误差X的可随机数化抽样器。在上述展开式中，利用X= B (yhK, )f (yhE/ 广1 = B UhVOf (μΛ。)—1，且B (UhV) = Xf (μ AcO这种性质。该性质基于函数f为同态映射、R及R'为随机数。因此，当考虑a、b为自然数、I^r2为随机数时，同样,Z1 v_r\z2 v ^r2成为关于f(x)分别具有误差XpX2的可随机数化抽样器。《关于Z31"3成为关于f(χ)具有误差X3的抽样器的理由》设R及R'为随机数，将计算装置2利用Xk进行计算的计算结果设为B (Χκ) (ΒΡ,当将计算装置2返送到委托装置I的计算结果设为z时，z=B (χκ))，将在群G中具有数值的随机变量X定义为X = B (xE) 1/Ef (χ)'这时,成为ζ1/κ = B (xK) 1/K = Xf (χ) = f (χ) X。SP, z1 zκ 成为关于 f (χ)具有误差X的抽样器。在上述展开式中，利用X = B (xE) 1/Ef (Xk)'B (xE) 1/E = Xf (χκ)这种性质。该性质基于R及V为随机数。因此，当考虑r3为随机数时，ζ1/κ成为关于f (χ)具有误差X3的可随机数化抽样器。[第三实施方式]第三实施方式的代理计算系统是将第一可随机数化抽样器21及第二可随机数化抽样器22的另一例具体化而成的系统，换言之，是将步骤S3及步骤S6的另一例具体化而成的系统。具体而言，是将H = GXG且函数f相对于EIGamal密码的解码函数即密钥s及密文(Cl，c2)为f Cc1, C2) = C1C2-3时的第一可随机数化抽样器21及第二可随机数化抽样器22的例子具体化而成的系统。下面，以与第一实施方式不同的部分为中心进行说明，关于共同的部分，省略重复说明。如图5所示，第三实施方式的第一可随机数化抽样器21例如包含第四随机数生成部119、第五随机数生成部120、第四输入信息计算部121、第五输入信息计算部122、第四输出信息计算部27及第四计算部123。如图5所示，第二可随机数化抽样器22例如包含第六随机数生成部124、第七随机数生成部125、第六输入信息计算部126、第七输入信息计算部
127、第五输出信息计算部28及第五计算部128。第四随机数生成部119、第五随机数生成部120、第四输入信息计算部121、第五输入信息计算部122、第四计算部123、第六随机数生成部124、第七随机数生成部125、第六输入信息计算部126、第七输入信息计算部127、第五输出信息计算部28及第五计算部128包含在委托装置I中。第四输出信息计算部27及第五输出信息计算部28包含在计算装置2中。在第三实施方式中，第四输出信息计算部27及第五输出信息计算部28与计算装置2对应。 在第三实施方式中，χ = (C1, c2)，f (C1, C2)为从直积群GXG向G的同态映射，设群G的生成元为μ g，设群G的位数为Ke，委托装置I和计算装置2事前得知的是相对于相同的密钥s的密文(V，ff) e H和将其密文解码后的解码文f (V，W) = Y e G。第三实施方式的步骤S3由图9例示的步骤S3P 步骤S36,构成。第四随机数生成部119生成O以上不足Ke的整数的均匀随机数r4 (步骤S31')。生成的随机数r4发送到第四输入信息计算部121、第五输入信息计算部122及第四计算部123。第五随机数生成部120生成O以上不足Ke的整数的均匀随机数r5 (步骤S32')。生成的随机数r5发送到第四输入信息计算部121及第四计算部123。第四输入信息计算部121计算第四输入信息C1bVrtU /5 (步骤S33')。计算出的第四输入信息C1bVrtU /5发送到第四输出信息计算部27。第五输入信息计算部122计算第五输入信息C2bWrt (步骤S34')。计算出的第五输入信息C2bWrt发送到第四输出信息计算部27。第四输出信息计算部27利用第四输入信息C1bVrt μ /5及第五输入信息C2bWrt进行计算。将其计算结果设为第四输出信息Z4 (步骤S35')。第四输出信息计算部27可计算f Cc1bVr4U gr5,c2bffr4)0第四输出信息计算部27的计算结果有时是 Mc1bVrtU /5，C2bWrt),有时不是 f (C1bVrtU /5，c2bffr4)0第四计算部123计算ζ/Μμ:5，将其计算结果设为u (步骤S36')。计算结果u发送到第一幂计算部13。在此，成为11 = 2/_^/5 = € (CljC2)bX10即，z4Y_rtyg_r5成为关于f (Cl，C2)具有误差X1的可随机数化抽样器。关于其理由，后面进行描述。第三实施方式的步骤S6由图10例示的步骤S6P 步骤S66,构成。第六随机数生成部124生成O以上不足Ke的整数的均匀随机数r6 (步骤S61')。生成的随机数r6发送到第六输入信息计算部126、第七输入信息计算部127及第五计算部
128。第七随机数生成部125生成O以上不足Ke的整数的均匀随机数r7 (步骤S62')。生成的随机数r7发送到第六输入信息计算部126及第五计算部128。第六输入信息计算部126计算第六输入信息C1aVrf μ/7 (步骤S63')。计算出的第六输入信息C1aVrf μ ；7发送到第五输出信息计算部28。第七输入信息计算部127计算第七输入信息C2aWrf (步骤S64')。计算出的第七输入信息C2aWrf发送到第五输出信息计算部28。第五输出信息计算部28利用上述第六输入信息C1aVrf^ /7及上述第七输入信息C2aWrfi进行计算，将其计算结果设为第五输出信息Z5 (步骤S65')。计算出的第五输出信息Z5发送到第五计算部128。第五输出信息计算部28可计算f Cc1aVr6 μ/7, C2aWr6 )0第五输出信息计算部28的计算结果有时是 Mc1aVrV /7，C2aWrfi)，有时不是 f (C1aVrfi μ /7，c2ar6)。第五计算部128计算Z5Y_rfyg_'将其计算结果设为V (步骤S66')。计算结果V发送到第二幂计算部16。在此，成为￥ = 2/_1^广=€ (cl, c2)ax20即，zfVj7成为关于f (Cl，C2)具有误差X2的可随机数化抽样器。关于其理由，后面进行描述。 《关于z4Y—rtU /5、ζ5Υ_Λμ 成为关于f Cc1, C2)分别具有误差的可随机数化抽样器的理由》设为c为自然数、RpR2J/及V为随机数，将计算装置2利用(^>/2及C2cWki进行计算的计算结果设为B (C1cVei μ gE2, C2cWei)(即，当将计算装置2返送到委托装置I的计算结果为z时，为z = B Cc1cVei μ/2, c2f))，将在群G中具有数值的随机变量X定义为X = B (νΕ1/ μ8Ε2/ ,ffE1/ )f (νΕ1/ μ8Ε2/ ,ffE1/ )'这时，zY_K1μ g-R2 = B Cc1cVei μ :，C2cWki)Υ_Κ1 μ 广=Xf Cc1cVei μ :，C2cWki)Υ_Κ1 μ ,=Xf Cc1, C2) cf (V, ff) E1f ( μ g，eg) Κ2Υ_Κ1 μ ；Ε2 = Xf Cc1, C2) cYei μ gK2Y_K1 μ ；Ε2 = f Cc1, C2)I。即，ζΓΕ1 μ ；Ε2成为关于f (χ)具有误差X的可随机数化抽样器。另外，eg设为群G的单位元。在上述展开式中，利用X= B (Vk1' UgE2/ ,ffE1/ )f (VE1/ UgE2/ , ffE1 / ) = B(C1cVei μ gE2, C2cWei) f (C1cVei μ gE2, C2cWei),且 B (C1cVei μ gK2，c2cffE1) = Xf (C1cVei μ gK2，C2cWei)这种性质。该性质基于RpRyR/及R2'为随机数。因此，当考虑a、b为自然数、r4、r5、r6&r7为随机数时，同样，Z4Y - r4 U g_r5、Z5Fr6 μ/7成为关于f Cc1, C2)分别具有误差XpX2的可随机数化抽样器。[第一实施方式 第三实施方式的变形例等]随机变量Xp X2及X3既可以相同，也可以不同。通过第一随机数生成部110、第二随机数生成部113、第三随机数生成部116、第四随机数生成部119、第五随机数生成部120、第六随机数生成部124及第七随机数生成部125分别生成均匀随机数，代理计算系统的安全性最高。但是，在要求的安全性的水平没有那么高的情况下，第一随机数生成部110、第二随机数生成部113、第三随机数生成部116、第四随机数生成部119、第五随机数生成部120、第六随机数生成部124及第七随机数生成部125也可以分别生成不是均匀随机数的随机数。在上述的例子中，各调用一次第一可随机数化抽样器21、第二可随机数化抽样器22，但为了减少委托装置I和计算装置2之间的通信次数，也可以对同一 a、b多次调用第一可随机数化抽样器21、第二可随机数化抽样器22，委托装置I通过一次通信就能够取得多个 U、V0第一可随机数化抽样器21、第二可随机数化抽样器22及抽样器23的各部既可以配置于委托装置1，也可以配置于计算装置2。即，既可以如第一实施方式那样将各部全部配置于计算装置2，也可以如第二实施方式及第三实施方式那样分开配置于委托装置I及计算装置2。委托装置I的各部间的数据交换既可以直接进行，也可以经由未图示的存储部来进行。同样，计算装置2的各部间的数据交换既可以直接进行，也可以经由未图示的存储部来进行。委托装置I及计算装置2可分别由计算机来实现。在这种情况下，该装置应有的各功能的处理内容通过程序来记述。而且，通过由计算机执行该程序，这些装置的各处理功能在计算机上实现。记述有该处理内容的程序能够 记录于计算机可读取的记录介质。另外，在该方式中，通过在计算机上执行规定的程序，构成这些装置，但也可以硬件地实现这些处理内容的至少一部分。[第四实施方式]第四实施方式 第十实施方式是利用委托装置I'委托于计算装置2,的计算结果来计算Θ (g，h)的实施方式。如图11所示，第四实施方式的代理计算系统包含委托装置I'及计算装置2'，利用委托装置P委托于计算装置2'的计算结果，计算双同态映射Θ (g，h)。在此，设G、H及F为循环群，设映射Θ :GXH —F为双同态映射，设g为群G的元，设h为群H的元，设Ke为群G的位数，设Kh为群H的位数，设μ8为群G的生成元，设UhS群H的生成元，设V = θ ( μ g，μ g)，设k为I以上的整数的安全参数，设K = 2k。双同态映射的意思是相对于两个输入都为同态的映射。在该例子中，映射Θ (g,h)相对于群G的元g为同态，且相对于群H的元h为同态。在委托装置I'和计算装置2'之间确立有通信路径，委托装置Γ及计算装置2'可双向地通信。该通信路径也可以不必秘密地保持，第三者可拦截在该通信路径流通的信息。委托装置I'向不可靠的计算装置2'发送由随机数干扰后的信息，计算装置2'利用该干扰后的信息，按照一定的算法进行计算，然后将其计算结果回复到委托装置I,。通过重复向该计算装置2'的信息的收发，委托装置I'最终地计算Θ (g，h)。委托装置I'首先通过步骤S 11' 步骤S 125'(图15)的处理，计算与Θ (g，yh)同等的信息(σ，V ')，利用与其Θ (g，yh)同等的信息(σ，V ')，通过步骤S21' 步骤S225'的处理,计算Θ (g, μ)。委托装置I'例如包含图12及图13例示的第一随机数生成部11'、第二随机数生成部12'、第一输入信息计算部13'、第二输入信息计算部14'、第一列表信息计算部15'、第一列表存储部16'、接收部17'、发送部18'、第四随机数生成部21'、第五随机数生成部22'、第三输入信息计算部23'、第四输入信息计算部24’、第二列表信息计算部25'、第二列表存储部26'、第三随机数生成部27'、第一判定部28'、第六随机数生成部31'、第七随机数生成部32'、第五输入信息计算部33'、第六输入信息计算部34'、第三列表信息计算部35'、第三列表存储部36'、第九随机数生成部41'、第十随机数生成部42'、第七输入信息计算部43'、第八输入信息计算部44'、第四列表信息计算部45'、第四列表计算部46'、第八随机数生成部47'及第二判定部48'。如图14所示，计算装置2'例如包含接收部51'、发送部52'、第一输出信息计算部53'、第二输出信息计算部54'、第三输出信息计算部55'及第四输出信息计算部56'。<步骤 Sll'(图 15)>第一随机数生成部11'生成O以上不足Ke的整数的均匀随机数Γι(步骤Sll')。生成的随机数A发送到第一输入信息计算部13'及第一列表信息计算部15'。< 步骤 S12' >第二随机数生成部12'生成O以上不足Kh的整数的均匀随机数r2(步骤S12')。生成的随机数r2发送到第二输入信息计算部14'、第一列表信息计算部15'及第一列表 存储部W。< 步骤 S13' >第一输入信息计算部13'计算第一输入信息gl= Ugrlg (步骤S13')。计算出的&发送到发送部18'。在此，μ8的右上角的rl是Γι的意思。这样，在该申请中，在设α为第一字符、β为第二字符、Y为数字而表述为α 的情况下，该β Y的意思是β Y，S卩，β的下标Y。另外，计算gl = μ grlg是计算用μ grlg这种式定义的gl的值。如果能够最终地计算式μ的值，则不论计算过程中的计算方法。这关于该申请中出现的其他式的计算也同样。< 步骤 S14' >第二输入信息计算部14'计算第二输入信息Ii1= yhr2 (步骤S14')。计算出的Ii1发送到发送部18'。< 步骤 S15' >发送部18'将第一输入信息&及第二输入信息Ii1发送到计算装置2'(步骤S15/ )。< 步骤 S16' >计算装置2'的接收部51'(图14)接收第一输入信息gl及第二输入信息Ill (步骤 S16')。< 步骤 S17' >第一输出信息计算部53 ^利用第一输入信息gl及第二输入信息Ii1进行计算，将其计算结果设为第一输出信息Z1 (步骤S17' )。Z1发送到发送部52'。第一输出信息计算部53'可计算Θ (gphP。第一输出信息计算部53'的计算结果有时是Θ化1，111)，有时不是0 (gphP。在该申请中，可计算的意思是可按不能忽略的概率进行计算。不能忽略的概率是在设安全参数k的广义单调增加函数的多项式为多项式f(k)时的I / f (k)以上的概率。< 步骤 S18' >发送部52'将第一输出信息Z1发送到委托装置I'(步骤S18')。< 步骤 S19' >委托装置I'的接收部17'(图12)接收第一输出信息Z1 (步骤S19')。接收到的第一输出信息Z1发送到第一列表信息计算部15'。在此，第一输出信息Z1设为群F的
J Li ο<步骤 SllO' >第一列表信息计算部15 '利用随机数Γι、随机数r2及第一输出信息Z1,计算Z1V^1r2 (步骤SllO')。计算出的Z1Vilrt发送到第一列表存储部16'。<步骤 Slll' >由随机数1*2和21 v_—构成的信息组(r2，Z1 V _—)追加于列表L115在该例子中，在第一列表存储部16'存储信息组(r2，Z1 v_&2)(步骤Slll')。<步骤 SI 12' > 第三随机数生成部27'生成O以上不足K的整数的均匀随机数即屯(步骤S112')。生成的随机数Cl1发送到第三输入信息计算部23'及第二列表存储部26'。<步骤 SI 13' >第四随机数生成部2Γ生成O以上不足Ke的整数的均匀随机数即r4 (步骤S113')。生成的随机数r4发送到第三输入信息计算部23'及第二列表信息计算部25'。<步骤 SI 14' >第五随机数生成部22'生成O以上不足&的整数的均匀随机数即1*5 (步骤S114')。生成的随机数r5发送到第四输入信息计算部24'、第二列表信息计算部25'及第二列表存储部26'。<步骤 SI 15' >第三输入信息计算部23'计算第三输入信息g2= μ gr4gdl (步骤S115')。计算出的第三输入信息g2发送到发送部18，。<步骤 SI 16' >第四输入信息计算部24'计算第四输入信息h2= yhr5 (步骤S116')。计算出的第四输入信息h2发送到发送部18'。<步骤 SI 17' >发送部18'将第三输入信息&及第四输入信息匕发送到计算装置2'(步骤S117/ )。<步骤 SI 18' >计算装置2'的接收部51'(图14)接收第三输入信息g2及第四输入信息匕(步骤 S118')。<步骤 SI 19' >第二输出信息计算部54'利用第三输入信息g2及第四输入信息h2进行计算，将其计算结果设为第二输出信息Z2 (步骤S119' )。Z2发送到发送部52'。第二输出信息计算部54'可计算Θ (g2，h2)。第二输出信息计算部54'的计算结果有时是Θ (&汕2)，有时不是0 (g2，h2)。< 步骤 S120' >发送部52'将第二输出信息Z2发送到委托装置I'(步骤S120')。< 步骤 S121' >委托装置Γ的接收部17'(图12)接收第二输出信息Z2 (步骤S121')。接收到的第二输出信息Z2发送到第二列表信息计算部25'。在此，第二输出信息Z2设为群F的
J Li ο< 步骤 S122' >第二列表信息计算部25'利用随机数r4、随机数1*5及第二输出信息22，计算z2v-r4r5 (步骤S122')。计算出的Z2 V 发送到第二列表存储部26'。<步骤 S123' >由随机数Cl1、随机数r5和Z2 V 构成的信息组(屯，r5，Z2 v ^4r5)追加于列表L2。在该例子中，在第二列表存储部26'存储信息组(dpivhvi5)(步骤S123')。< 步骤 S124' > 第一判定部28'在设从第一列表存储部16'读入的信息组的第一成分为S1、第二成分为W1，且设从第二列表存储部26'读入的信息组的第一成分为t2、第二成分为S2、第三成分为W2时,判定这些信息组是否满足(W1)八Ct2S2S1-1) = W2的关系(步骤S124')。第一判定部28'在第一列表存储部16'及第二列表存储部26'存储有多个信息组的情况下，判定由存储于第一列表存储部16'的信息组(r2，Z1V^lr2)和存储于第二列表存储部26'的信息组((11，1'5，22〃_1^5)构成的所有的信息对是否满足上述关系。当然，关于已判定了是否满足上述关系的信息对，也可以省略其判定处理。< 步骤 S125' >第一判定部28'在满足上述关系的情况下，将S1代入Ojfw1代入V'(步骤S125/ )。在此,成为 V ' 1/0 = W/7。= Θ (g, μ h)。关于成为 V ' 1/0 = Θ (g, μ h)的理由，后面进行描述。在不满足上述关系的情况下，返回到步骤Sll'。<步骤 S21'(图 16)>第六随机数生成部3Γ生成O以上不足Ke的整数的均匀随机数即1*6 (步骤S21')。生成的随机数r6发送到第五输入信息计算部33'、第三列表信息计算部35'及第三列表存储部36'。< 步骤 S22' >第七随机数生成部32'生成O以上不足&的整数的均匀随机数即1> (步骤S22')。生成的随机数r7发送到第六输入信息计算部34'及第三列表信息计算部35'。< 步骤 S23' >第五输入信息计算部33'计算第五输入信息g3= μ/6 (步骤S23')。计算出的g3发送到发送部18'。< 步骤 S24' >第六输入信息计算部34'计算第六输入信息h3= yhrt°h (步骤S24')。计算出的匕发送到发送部18'。< 步骤 S25' >发送部18'将第五输入信息&及第六输入信息匕发送到计算装置2'(步骤S25/ )。< 步骤 S26' >计算装置2'的接收部51'(图14)接收第五输入信息g3及第六输入信息匕(步骤 S26')。< 步骤 S27' >第三输出信息计算部55'利用第五输入信息g3及第六输入信息h3进行计算，将其计算结果设为第三输出信息Z3 (步骤S27' )。Z3发送到发送部52'。第三输出信息计算部55'可计算Θ (g3，h3)。第三输出信息计算部55'的计算结果有时是Θ (&，4)，有时不是0 (g3，h3)。〈步骤S28' >发送部52'将第三输出信息Z3发送到委托装置I'(步骤S28')。< 步骤 S29' > 委托装置Γ的接收部17'(图13)接收第三输出信息Z3 (步骤S29')。接收到的第三输出信息Z3发送到第三列表信息计算部35'。在此，第三输出信息Z3设为群F的
J Li ο< 步骤 S210' >第三列表信息计算部35 '利用随机数r6、随机数r7及第三输出信息z3，计算Z3V' (步骤S210')。计算出的Z3V 发送到第三列表存储部36'。<步骤 S211' >由随机数1*6和23一 _.7构成的信息组(r6，Z3V ' _rflr7)追加于列表L3。在该例子中，在第三列表存储部36'存储信息组(r6，Z3V'(步骤S211' χ< 步骤 S212' >第八随机数生成部47'生成O以上不足K的整数的均匀随机数即(12 (步骤S212')。生成的随机数d2发送到第八输入信息计算部44及第四列表存储部46'。< 步骤 S213' >第九随机数生成部4Γ生成O以上不足Ke的整数的均匀随机数即1*9 (步骤S213')。生成的随机数r9发送到第七输入信息计算部43'、第四列表信息计算部45'及第四列表存储部46'。< 步骤 S214' >第十随机数生成部42'生成O以上不足&的整数的均匀随机数即r1(l (步骤S214')。生成的随机数r1(l发送到第八输入信息计算部44'、第四列表信息计算部45'及第四列表存储部46'。< 步骤 S215' >第七输入信息计算部43'计算第七输入信息g4 = # (步骤S215')。计算出的第七输入信息g4发送到发送部18'。< 步骤 S216' >第八输入信息计算部44'计算第八输入信息h4= yhrt°°hd2(步骤S216')。计算出的第八输入信息h4发送到发送部18'。< 步骤 S217' >发送部18'将第七输入信息&及第八输入信息114发送到计算装置2'(步骤S217/ )。< 步骤 S218' >
计算装置2'的接收部51'(图14)接收第七输入信息g4及第八输入信息匕(步骤 S218')。< 步骤 S219' >第四输出信息计算部56'利用第七输入信息g4及第八输入信息h4进行计算，将其计算结果设为第四输出信息Z4 (步骤S219' )。Z4发送到发送部52'。第四输出信息计算部56'可计算Θ (g4，h4)。第四输出信息计算部56'的计算结果有时是Θ (g4，h4)，有时不是Θ (g4，h4)。< 步骤 S220' >发送部52'将第四输出信息Z4发送到委托装置I'(步骤S220')。
< 步骤 S221' >委托装置Γ的接收部17'(图12)接收第四输出信息Z4 (步骤S221)。接收到的第四输出信息Z4发送到第四列表信息计算部45'。在此，第四输出信息Z4设为群F的
J Li ο< 步骤 S222' >第四列表信息计算部45'利用随机数r9、随机数r1(l及第四输出信息24，计算z4v ^ (步骤S222')。计算出的Z4 V' 发送到第四列表存储部46'。< 步骤 S223' >由随机数(12、随机数1*9和2^ ' __°构成的信息组(d2，r9，z4v '追加于列表L4。在该例子中，在第四列表存储部46'存储信息组(d2，r9，Z4Viltl)(步骤S223')。< 步骤 S224' >第二判定部48'在设从第三列表存储部36'读入的信息组的第一成分为S3、第二成分为W3，且设从第四列表存储部46'读入的信息组的第一成分为U、第二成分为S4、第三成分为W4时,判定这些信息组是否满足(W3)八Ct4S4S3-1) = W4的关系(步骤S224')。第二判定部48'在第三列表存储部36'及第四列表存储部46'存储有多个信息组的情况下，判定由存储于第三列表存储部36'的信息组(r6，z3v' 和存储于第四列表存储部46'的信息组(d2，r9，Z4V' —&1(ι)构成的所有的信息对是否满足上述关系。当然，关于已判定了是否满足上述关系的信息对，也可以省略其判定处理。< 步骤 S225' >第二判定部48,在满足上述关系的情况下，将(W3) a (O输出(步骤S225')。在此，成为(W3)八(Si1) = Θ (g，h)。关于成为(W3)八(S3 + 1) = Θ (g，h)的理由，后面进行描述。在不满足上述关系的情况下，返回到步骤S21'。在难以进行(W3)八(Si1)的计算即W3的方根的计算的情况下，可如下那样容易地计算Θ (g，h)。第二判定部48'重复进行步骤S21' 步骤S224'的处理，将满足(W3)八Ct4S4S3-1)= W4 的关系的 W3 和 S3 的组(w3, S3)依次设为(a !,S1), ( α 2，S2), ···, ( a m, Sm), ···,并将其存储于存储部410'。m为自然数。第二判定部48'如果发现与S1成为互素的Sm，则设L1和L2为整数，计算成为L1S1 + L2Sm = I的L1及L2,利用该L1及L2,计算a α成为 W= Θ (g，h) (L1S1 + L2S2)= Θ (g，h)。另外，第二判定部 48'如果 S1, S2,…，Sm的最小公倍数为1，则也可以设L1, L2, ···, Lm为整数,计算成为L1S1 + L2S2 H-----l· LmSm =I的 L1, L2, ···, Lni，利用该 L1, L2,…，Lni，计算 Ct α 尸…α成为 α 广1 a 2L2…α，= θ
(g，h) (Llsl + L2S2+---+LmSm)= Θ (g，h)。假设有能够拦截委托装置I'和计算装置2'之间的通信的攻击者M，也可通过用仅委托装置P得知的随机数(例如，I^r2)对在委托装置I'及计算装置2'之间进行通信的信息进行干扰来对攻击者M保密。另外，在委托装置I'及计算装置2'之间进行通信的信息由仅委托装置I'得知的rl、r2等随机数进行干扰，因此计算装置2'当然不能得知委托装置I'将要最终计算的Θ (g，h),连其输 入即g及h也不能得知。因此，计算装置2'不需要为可靠的计算机，就能够缓和用于计算双同态映射的系统的构成必要条件。另外，可靠的计算机通常价格高，在运用上需要费用，但由于不需要计算装置2'为可靠的计算机，因此能够消减用于计算双同态映射的系统的构筑及运用的成本。《关于成为V'1/0 = Θ (g，μ h)的理由》首先,对叫做可随机化抽样器(randomizable sampler)的随机变量Sx (d)进行说明。与w e F有关的误差X的可随机化抽样器即随机变量Sx (d)为Sx (d) = WdX0 d为自然数。在此，当设Rp R2, R1'及R2'为随机数、设计算装置利用gV gK1及μ hE2进行计算的计算结果为B (gdygE1, μ；2)(当将计算装置返送到委托装置的计算结果设为Z时，为ζ=B (gVgE1, μ hK2))，且将在群F中具有数值的随机变量X定义为X = B (μ/ μ / 2)17 r 2 θ ( μ gK, ^ μ h) ―1 时，Sx (d) = ζ α ζΚ2) V -K1 成为与 θ (g, μ h)有关的误差 χ 的可随机化抽样器。原因是，sx(d) = z(1/K2) V—K1 = B (gdygK1，yhK2)1/K2e ( μ g, yh)-E1 = ΧΘ(gdy gE1, μ h) θ ( μ gE1, μ h) = X Θ (gd, μ h) θ (μ gE1, μ h) θ (μ gE1, μ h) - 1 = Θ (g,μ h) dX。在上述展开式中，利用X= B (μ / \ μ / 2)1/r 2Θ (μ/ S μ hr = B (gd μ gE1,yhE2)1/E2e (gVgE1, μ。—1，且B (gVgE1, μhE2) 1 /E2 = X Θ (gVgE1, μh)这种性质。该性质基于&、民、R/及R2'为随机数。在此，发明者发现，将Sx (I)的表现值表述为Θ (g，μ,)1^，且将Sx (d)的表现值表述为Θ (g，yh)dx2，成为Sx (I)的表现值的d次方=Sx (d)的表现值即(Θ (g, yh)SOd= Θ (g, μ h) dX2的理由在X1及X2为群F的单位元6{时的可能性非常高。在此，省略其证明。在X1为群F的单位元ef时,成为Sx (I)的表现值=Θ (g, μ h) 1X1 = Θ (g,μ h)。上述实施方式的代理计算系统利用该可随机化抽样器的性质。步骤Sll' 步骤Slll'的处理与Sx (I)的表现值Θ (g, U1^1X1的计算对应。实际上，不计算Sx(I)的表现值自身，但当利用通过同处理而得到的(r2，Zl V ^2Mfz1V -1:11:2进行I / r2次方时，成为(Zlv-My/e = "、-n，且成为&(1)的表现值θ (g，yh) 1X1O同样，步骤S112' 步骤S123'的处理与Sx (Cl1)的表现值Θ (g，yh)dlx2的计算对应。另夕卜，步骤S124'的处理与是否SSx (I)的表现值的(I1次方=Sx Cd1)即(Θ (g，= θ (g, μ h) dlX2的判定对应。理由是，步骤S124使用的判定条件(W1) A Ct2S2S1-1)为(wl ) A ( t2S2Si ~ 1 ) = W2^ ( W]1/Sl ) t2 =
W2lis2O ( Zjl7r2V"11 ) dl = Z21/r5V_r40 ( Θ ( g, Ph ) 1Xi ) dl = Θ ( g，Ph ) dlX2^Sx
(I)的表现值的(I1次方=Sx Cd1)的表现值。在此，由定义可知，S1 = I^w1 = Z1 V ^rlr2^t2
_ I___ τ — r4r5
一屯、S2 — r5、W2 — Z2 V ο另外，步骤S125'的σ及V'与Θ (g，yh)对应。理由是，如上所述，在Sx (I)的表现值的(I1次方=Sx Cd1)的表现值时，为V ' 1/0 = W117"1 = Z11 / r2 V ^rl = Θ (g,μ h) 1X1 = Θ (g, μ h)。
《关于成为(W3)- (S3-1) = θ (g，h)的理由》当设R1, R2, R/及R2'为随机数、设计算装置利用gK1&hdyhK2进行计算的计算结果为B (gE1, hdyhE2)(当将计算装置返送到委托装置的计算结果设为ζ时，为ζ = B (gE1,hS,2))，且将在群F中具有数值的随机变量X定义为X = B Cgr μ / 2)' /r 1 Θ (g，μ/2) —1时，Sx (d)=z(1/K1) V' —K2成为与Θ (g，h)有关的误差X的可随机化抽样器。理由是，SX(d)=z(1/K1) V' —K2 = B (gK1，hdyhK2)1/K10 (g, yh)-R2 = ΧΘ (g、hdμ hE2) Θ (g, μ hE2) = X Θ (g、hd) Θ (g, μ hE2) Θ (g, μ hE2) = Θ (g，h) dX。在上述展开式中，利用X= B (gr2)1/κ, (g, μ / 2K1 = B W)1/Ε1Θ (g'hSf)-1，且 B (gK1，hVhK2)1/K1 = X0 (g、hVhK2)这种性质。该性质基于 R1,R2, R1'及V为随机数。在此，发明者发现，将Sx (I)的表现值表述SSx (I)= Θ (gd)、，将Sx (d)的表现值表述为Sx (d)= Θ (g, h) dX2,成为Sx (I)的表现值的d次方=Sx (d)即(Θ (g,h) 1X1) d = Θ (g，h) dX2的理由在X1及X2为群F的单位元ef时的可能性非常高。在此,省略其证明。在X1为群F的单位元ef时,成为Sx (I)的表现值=Θ (g^)^! = Θ (g，h)。上述实施方式的代理计算系统利用该可随机化抽样器的性质。步骤S21' 步骤S211'的处理与Sx (I)的表现值Θ (g，h) 1X1的计算对应。实际上，不计算Sx (I)的表现值自身，但当利用通过同处理而得到的(r6，Z3V ' _rf。将Z3V'—―进行丄/^次方时’成为匕一 -r6r7)1/r6 = z31/r6v/ _〃，且成为Sx (I)的表现值Θ (gd)、。同样，步骤S212, 步骤S223,的处理与Sx (d2)的表现值Θ (g,h)d2x2的计算对应。另外，步骤S224'的处理与是否为Sx (I)的表现值的d2次方=Sx (d2)的表现值即(Θ (g, h)^)112 = Θ (g，h) d2X2的判定对应。理由是，步骤S224'使用的判定条件(W3 ) A ( ttS4S3_1 ) = W4 为(W3 ) Λ ( t4S4S3 _1 ) = W4^ ( W〗1
/s3 \ t4 I /s4^ V / I /r6, t -r7 \ d2 I /r9 / -TIOaa / a / i \ I \ d2 r\ ( ^
)=W4 o I V J = Z4 V ^ (Θ (g, hi X1) = Θ (g,
h ) d2X2OSx ( I )的表现值的d2次方=Sx (d2)的表现值。在此，由定义可知，s3 = r6、W3
=Z3V ' —r6r7、t4 = d2、S4 = r9> W4 = Z4V ' ^r9rl0o另外，步骤S225,的(W3)八(sf1)与Θ (g，h)对应。理由是，如上所述，在Sx (I)的表现值的 d2 次方=Sx (d2)的表现值时，为(W3) a (s3-i) = (Z3 V ' ^r6r7) Cr6-1)=
z31/r6v' -r7= Θ (g, h) 1X1 = Θ (g，h)。[第五实施方式]
第五实施方式的代理计算系统在步骤S13'、步骤SllO'及步骤Slll'上与第四实施方式的代理计算系统不同，其他部分与第四实施方式的代理计算系统同样。下面，以与第四实施方式不同的部分为中心进行说明。第一输入信息计算部13'对不是由gl = μ grlg定义而是由gl = grl定义的第一输入信息进行计算(步骤S13')。第一列表信息计算部15'不是利用Z1 V 而是利用随机数Γι及随机数r2来计算rir2，且将其计算结果发送到第一列表存储部16'(步骤SllO')。在第一列表存储部16'不是存储信息组(r2，Z1 v _&2)，而是存储由计算出的和从计算装置2'接收到的21 e F构成的信息组(rir2，Zl)(步骤Slll')。 在第四实施方式的步骤SllO'中，需要进行Z1 V ^1r2这种群F的幂运算，但在第五实施方式的步骤SllO'中，进行的是rir2的计算，幂运算的次数减少一次。这样，通过减少 幂运算的次数，能够增大运算的效率。另外，如果在群G、群H中难以进行非自明方根(非自明χ务根，nontrivial root)的计算,贝U安全性不会比第四实施方式低。[第六实施方式]第六实施方式的代理计算系统在步骤S24'、步骤S210'及步骤S211'上与第四实施方式的代理计算系统不同，其他部分与第四实施方式的代理计算系统同样。下面，以与第四实施方式不同的部分为中心进行说明。第六输入信息计算部34'对不是由h3 = μ f ° h定义而是由h3 = hr7定义的第六输入信息h3进行计算(步骤S24')。第三列表信息计算部35'不是利用Z3 V ' 而是利用随机数r6及随机数r7来计算r6r7 (步骤S210')。在第三列表存储部36'不是存储信息组(r6，Z3 V' _—，而是存储由计算出的r6r7和从计算装置2'接收到的23 e F构成的信息组(r6r7，z3)(步骤S211')。在第四实施方式的步骤S210'中，需要进行z3v' _&7这种群F的幂运算，但在第六实施方式的步骤S210'中，进行的是r6r7的计算，幂运算的次数减少一次。这样，通过减少幂运算的次数，能够增大运算的效率。如果在群G、群H中难以进行非自明方根的计算，则安全性不会比第四实施方式低。[第七实施方式]第七实施方式的代理计算系统在步骤S125'及步骤S214'上与第四实施方式的代理计算系统不同，其他部分与第四实施方式的代理计算系统同样。下面，以与第四实施方式不同的部分为中心进行说明。第一判定部28'在满足上述关系的情况下，将tlS2代入σ，将W2代入V '(步骤S125/ )。第十随机数生成部42'利用随机数r9，计算一ι^1，并设为r1(l (步骤S214')。这样，通过变更V'的定义并将σ设为对于计算装置2'来说难以推测的随机数，来增大安全性。另外，通过利用随机数r9计算随机数r1(l，能够减少生成随机数的次数。也认为第八输入信息h4 = yhrl0ohd2的杂乱性因由随机数r9规定随机数r1(l而下降，且安全性受损，但第八输入信息h4= Uhlrlt^hd2不仅由随机数r1(l干扰，而且进一步由σ干扰，因此安全性不会受损。另外，在第七实施方式中，也可以如下那样进一步将步骤S22'及步骤S21T变更。第七随机数生成部32'利用随机数r6计算一 re—1，并设为r7 (步骤S22')。
在第三列表存储部36'存储由I和上述计算出的Z3 V ' 构成的信息组(1，Z3V ' _r6r7)(步骤 S211')。这样，通过利用随机数r6计算随机数r7，能够减少生成随机数的次数。如果在群G、群H中难以进行非自明方根的计算，则安全性不会比第四实施方式低。[第八实施方式]第八实施方式的代理计算系统在步骤S113'上与第四实施方式的代理计算系统不同，其他部分与第四实施方式的代理计算系统同样。下面，以与第四实施方式不同的部分为中心进行说明。首先，在步骤S113'之前，第五随机数生成部22'生成随机数r5 (步骤S114')。第四随机数生成部21'利用随机数r5计算一 ι^1，并设为r4 (步骤S113')。这样，通过利用随机数r5计算随机数r4，能够减少生成随机数的次数。关于群H的任意元h，如果难以计算成为g e G且Θ (g，h)= V的值，则安全性不会比第四实施方式低。[第九实施方式]第九实施方式的代理计算系统在委托装置Γ进一步包含图12虚线所示的事前计算部29'上，且在步骤S115'上与第四实施方式的代理计算系统不同，其他部分与第四实施方式的代理计算系统同样。下面，以与第四实施方式不同的部分为中心进行说明。事前计算部29'利用第三随机数生成部27'生成的(I1，计算gdl。该处理在步骤S112,之后且在步骤S115'之前进行。第三输入信息计算部23'利用事前计算出的gdl，进行g2 = μ ；4gdl的计算(步骤S115/ )。在步骤S114'中不满足判定条件的情况下，重复进行步骤Sll' 步骤S123'的处理，但在该重复处理中，再次利用事前计算出的gdl。即，第三随机数生成部27'不生成随机数Cl1，第三输入信息计算部23'利用事前计算出的gdl，进行g2 = μ ；4gdl的计算。由此，能够减少生成随机数Cl1的次数，能够迅速地进行g2 = μ ；4gdl的计算。[第十实施方式]第十实施方式的代理计算系统在委托装置Γ进一步包含图13虚线所示的事前计算部49'上且在步骤S216'上与第四实施方式的代理计算系统不同，其他部分与第四实施方式的代理计算系统同样。下面，以与第四实施方式不同的部分为中心进行说明。事前计算部49'利用第八随机数生成部47'生成的d2，计算hd2。该处理在步骤S212/之后且在步骤S216'之前进行。第八输入信息计算部44'利用事前计算出的hd2，进行第八输入信息h4 =的计算(步骤sn6')。在步骤S214'中不满足判定条件的情况下，重复进行步骤S21' 步骤S223'的处理，但在该重复处理中，再次利用事前计算出的hd2。即，第八随机数生成部47'不生成随机数d2，第八输入信息计算部44'利用事前计算出的hd2，进行h4= yhrt°°hd2的计算。由此，能够减少生成随机数d2的次数，能够迅速地进行h4 = μ hrl0ohd2的计算。[第四实施方式 第十实施方式的变形例等]通过第一随机数生成部1Γ、第二随机数生成部12'、第三随机数生成部27'、第四随机数生成部21'、第五随机数生成部22'、第六随机数生成部3Γ、第七随机数生成部32'、第八随机数生成部47'、第九随机数生成部41'及第十随机数生成部42'分别生成均匀随机数，代理计算系统的安全性最高。但是，在要求的安全性的水平不那么高的情况下，第一随机数生成部11'、第二随机数生成部12'、第三随机数生成部27'、第四随机数生成部21'、第五随机数生成部22'、第六随机数生成部31'、第七随机数生成部32'、第八随机数生成部47'、第九随机数生成部41'及第十随机数生成部42'也可以不分别生成均匀随机数，而是生成随机数。 每当在列表L1、列表L2追加信息组时，都可以进行第一判定部28'的处理。例如，在第二列表存储部26'存储有信息组(C^ivz2Vi5)的情况下，也可以在步骤Slll'之后进行步骤S124'的处理。同样，每当在列表L3、列表L4追加信息组时，都可以进行第二判定部48'的处理。第四实施方式 第十实施方式可相互组合。既可以直接进行委托装置Γ的各部间的数据交换，也可以经由未图示的存储部来进行。同样，既可以直接进行计算装置2'的各部间的数据交换，也可以经由未图示的存储部来进行。委托装置I'及计算装置2'分别可由计算机来实现。在这种情况下，该装置应有的各功能的处理内容通过程序来记述。而且，通过由计算机执行该程序，该装置的各处理功能在计算机上实现。记述有该处理内容的程序可记录于计算机可读取的记录介质。另外，在该方式中，通过在计算机上执行规定的程序，来构成这些装置，但也可以硬件地实现这些处理内容中的至少一部分。另外，也可以将第一实施方式 第三实施方式和第四实施方式 第十实施方式组合。例如，如图17所示，第一实施方式 第三实施方式的计算装置2具备第四实施方式 第十实施方式的委托装置P ，包含该委托装置P的计算装置2也可以与第四实施方式 第十实施方式所述的同样地，利用计算装置2,，进行函数f的计算。具体而言，计算装置2为了计算需要计算的函数f (X)，利用计算装置2'计算对应的映射Θ (g，h)的值。与函数f (X)对应的映射Θ (g，h)是对被赋予的函数f及X输出与函数f (X)的值相同的值的映射Θ (g，h)。关于某元he H,在存在f (χ) = Θ (X，h)这种关系的情况下，与f (χ)对应的映射Θ成为Θ (x，h)。例如，在参考文献I记载的Boneh — Franklin方式的基于ID密码中，将某一定的ID相关的解码函数设为f。在该方式的基于ID密码中，由形成椭圆曲线的点的有限群G、H和对τ :GXH —F构成。将Q设为G的元。将基于ID密码的密钥发行中心的密钥设为S，将公开密钥设为P = sQ。基于ID密码的公共参数为群G、H的记述、对τ的记述、Q及P。〔参考文献 l〕Dan Boneh, Matt Franklin, “Identity — Based Encryption fromthe weil Pairing”，CRYPTO 2001，LNCS 2139, pp. 213 - 229, 2001.密钥的发行如下那样进行。密钥发行中心就对应于ID而规定的H的元Qid而言，计算Pid = sQid并通知给ID的保持者。Pid为ID的保持者的密钥。此时,解码函数f :G — F由 f (X) = τ (X，Pid)定义。密文的作成、密文的解码如下那样进行。为了将明文m关于某ID加密，生成随机数r，计算(Q'm (十)H ( τ (Ρ% QID)))，将此设为密文(C1, C2)。为了解码，通过对密文(C1,C2)计算C2 (十)H (f (C1)),得到明文。其中，在此，H为哈希函数，(+)为逻辑异或。在这种Boneh — Franklin方式的基于ID密码中，与函数f (X)对应的映射Θ利用例如对τ来定义。SP, f (X)= τ (x，PID)。计算装置2为IC卡及便携电话，难以进行秘密信息的提取，但在限定计算能力的 情况下，这样将委托装置及计算装置多重组合是有有益的。本发明不局限于上述的实施方式，在不脱离本发明精神的的范围内，可适当变更。
权利要求
1.ー种代理计算系统，其特征在干， 设G、H为循环群，设f为将群H的元X映射到群G的函数，设X1. X2为在群G中具有数值的随机变量，设随机变量X1的表现值为X1，设随机变量X2的表现值为x2， 所述代理计算系统包含 整数计算部，利用互素的两个自然数a、b，计算满足a' a + b' b = I的关系的整数a,ヽ b,； 第一可随机数化抽样器，能够计算f (X) bX1，并将其计算结果设为U ； 第一幂计算部，计算U' =Ua; 第二可随机数化抽样器，能够计算f (x) aX2,并将其计算结果设为V ; 第二幂计算部,计算V' =Vb; 判定部，判定是否为u, =V,;以及 最終计算部，在判定为U'=ゲ的情况下，计算Ub' Va/。
2.如权利要求I所述的代理计算系统，其特征在干， 还包含抽样器，所述抽样器能够计算f (X)X3，如果a = 1，则代替所述第二可随机数化抽样器，将其计算结果设为所述V，如果b = 1，则代替所述第一可随机数化抽样器，将其计算结果设为所述U，其中设X3为在群G中具有数值的随机变量，设随机变量X3的表现值为Λ3 °
3.如权利要求I所述的代理计算系统，其特征在干， 设所述f为同态映射，设群H的生成元为μ h，设群H的位数为Kh，设V =f (yh)， 所述第一可随机数化抽样器包含生成O以上不足Kh的整数的随机数Γι的第一随机数生成部、计算第一输入信息UhlrlXb的第一输入信息计算部、能够利用所述第一输入信息μ hrlxb计算f ( μ J1Xb)且将其计算结果设为第一输出信息Z1的第一输出信息计算部、计算Z1V-1并将其计算结果设为所述U的第一计算部， 所述第二可随机数化抽样器包含生成O以上不足Kh的整数的随机数r2的第二随机数生成部、计算第二输入信息Uhlr2Xa的第二输入信息计算部、能够利用所述第二输入信息μ hr2Xa计算f ( μ J2Xa)且将其计算结果设为第二输出信息Z2的第二输出信息计算部、计算Z2V^2并将其计算结果设为所述V的第二计算部。
4.如权利要求3所述的代理计算系统，其特征在干， 还包含抽样器，所述抽样器包含生成O以上不足Kh的整数的随机数r3的第三随机数生成部；计算第三输入信息f3的第三输入信息计算部；能够利用所述第三输入信息f3计算f (Xlr3)且将其计算结果设为第三输出信息Z3的第三输出信息计算部；以及第三计算部，所述第三计算部计算z31/l3，如果a = 1，则代替所述第二可随机数化抽样器，将其计算结果设为所述V，如果b = 1，则代替所述第一可随机数化抽样器，将其计算结果设为所述U。
5.如权利要求I所述的代理计算系统，其特征在干， 设群H = GX G，设所述f为同态映射，设群G的生成元为μ g，设群G的位数为Ke，设X= Cc1, c2)，设(V，W)为群 H 的元，设 f (V,ff) = Y， 所述第一可随机数化抽样器包含生成O以上不足Ke的整数的随机数r4的第四随机数生成部、生成O以上不足Ke的整数的随机数r5的第五随机数生成部、计算第四输入信息C1bVr4 μ /5的第四输入信息计算部、计算第五输入信息C2bWrt的第五输入信息计算部、能够利用所述第四输入信息C1W /5及所述第五输入信息C2bWrt计算f (C1bVr4U/5, C2bWr4)且将其计算结果设为第四输出信息Z4的第四输出信息计算部、计算z4Y—1:4 μ g_ri并将其计算结果设为所述u的第四计算部， 所述第二可随机数化抽样器包含生成O以上不足Ke的整数的随机数r6的第六随机数生成部、生成O以上不足Ke的整数的随机数r7的第七随机数生成部、计算第六输入信息C1aVr6 μ /7的第六输入信息计算部、计算第七输入信息C2aWrf的第七输入信息计算部、能够利用所述第六输入信息C1aViV 及所述第七输入信息C2aWrf计算f (C1aVr6U/7, C2aWr6)且将其计算结果设为第五输出信息Z5的第五输出信息计算部、计算Z5Frii μ 并将其计算结果设为所述V的第五计算部。
6.ー种代理计算方法，其特征在干， 设G、H为循环群，设f为将群H的元X映射到群G的函数，设X1. X2为在群G中具有数值的随机变量，设随机变量X1的表现值为X1，设随机变量X2的表现值为x2， 所述代理计算方法包含 整数计算步骤，整数计算部利用互素的两个自然数a、b，计算满足a' a + b' b = l的关系的整数a'、b'； 第一可随机数化抽样步骤，第一可随机数化抽样器能够计算f (X)bX1，并将其计算结果设为u ； 第一幂计算步骤,第一幂计算部计算U' = Ua ; 第二可随机数化抽样步骤，第二可随机数化抽样器能够计算f (X)aX2，并将其计算结果设为V ; 第二幂计算步骤,第二幂计算部计算V' = Vb ; 判定步骤，判定部判定是否为u' =Y';以及 最终计算步骤，最終计算部在判定为U'=ゲ的情况下，计算Ub' V-。
7.一种委托装置，其特征在干， 设G、H为循环群，设f为将群H的元X映射到群G的函数，设X1. X2为在群G中具有数值的随机变量，设随机变量X1的表现值为X1，设随机变量X2的表现值为x2， 所述委托装置包含 整数计算部，利用互素的两个自然数a、b，计算满足a' a + b' b = I的关系的整数a,ヽ b,； 第一幂计算部，利用能够计算f (χ)\的第一可随机数化抽样器的计算结果u，计算Ui =ua; 第二幂计算部，利用能够计算f (X) aX2的第二可随机数化抽样器的计算结果V，计算V1 = Vb ； 判定部，判定是否为u, =V,;以及 最終计算部，在判定为u' = Y'的情况下，计算Ub' Va /。
8.—种代理计算系统，利用委托装置委托于计算装置的计算结果，计算Θ (g，h)，其特征在干， 设G、H及F为循环群，设映射Θ :GXH —F为双同态映射，设g为群G的元，设h为群H的元，设Ke为群G的位数，设Kh为群H的位数，设μ g为群G的生成元，设μ h为群H的生成元,设V = Θ ( μ g, μ g),设k为自然数的安全參数,设K = 2k, 所述委托装置包含 第一随机数生成部，生成O以上不足Ke的整数的随机数Γι ； 第二随机数生成部，生成O以上不足Kh的整数的随机数r2 ； 第一输入信息计算部，计算第一输入信息A = μ grlg ; 第二输入信息计算部，计算第二输入信息h = Uhr2； 第一列表信息计算部，利用从所述计算装置接收到的Z1 e F，计算Z1 V -rlr2 ； 第一列表存储部，对由所述随机数r2和所述计算出的Z1 v-&2构成的信息组(r2，Z1 V^rlr2)进行存储； 第三随机数生成部，生成O以上不足K的整数的均匀随机数即Cl1 ； 第四随机数生成部，生成O以上不足Ke的整数的均匀随机数即r4 ； 第五随机数生成部，生成O以上不足Kh的整数的均匀随机数即r5 ； 第三输入信息计算部，计算第三输入信息g2 = μ gr4gdl ； 第四输入信息计算部，计算第四输入信息h2= yhr5； 第二列表信息计算部，利用从所述计算装置接收到的Z2 e F，计算Z2 V -； 第二列表存储部，对由所述Cl1、所述1*5和所述计算出的z2v_rtri构成的信息组(も，r5,z2v_riri)进行存储； 第一判定部，设从所述第一列表存储部读入的信息组的第一成分为S1，设第二成分为W1，且设从所述第二列表存储部读入的信息组的第一成分为t2，设第二成分为S2，设第三成分为W2,判定这些信息组是否满足(W1)へCt2S2S1-1) = W2的关系,在满足该关系的情况下，将S1代入σ，将W1代入V ,； 第六随机数生成部，生成O以上不足Ke的整数的均匀随机数即r6 ； 第七随机数生成部，生成O以上不足Kh的整数的均匀随机数即r7 ； 第五输入信息计算部，计算第五输入信息g3 = gr6 ; 第六输入信息计算部，计算第六输入信息h3 = μ J7I ; 第三列表信息计算部，利用从所述计算装置接收到的Z3 e F，计算Z3 V ' ； 第三列表存储部，对由所述1"6和所述计算出的Z3V ' 构成的信息组(re，Z3V' _rf,进行存储； 第八随机数生成部，生成O以上不足K的整数的均匀随机数即d2 ； 第九随机数生成部，生成O以上不足Ke的整数的均匀随机数即r9 ； 第十随机数生成部，生成O以上不足Kh的整数的均匀随机数即r1(l ； 第七输入信息计算部，计算第七输入信息g4= μ/9； 第八输入信息计算部，计算第八输入信息h4 = μ hrl0ohd2 ； 第四列表信息计算部，利用从所述计算装置接收到的Z4 e F，计算Z4 V ' -r9r10 ； 第四列表存储部，对由所述d2、所述r9和所述计算出的Z4 V，-r9r10构成的信息组(d2，r9, z4 V ^进行存储；以及 第二判定部，设从所述第三列表存储部读入的信息组的第一成分为s3，设第二成分为W3，且设从所述第四列表存储部读入的信息组的第一成分为t4，设第二成分为S4，设第三成 分为W4,判定这些信息组是否满足(W3)へCt4S4S3-1) = W4的关系,在满足该关系的情况下，将(W3)へCs3-1)输出， 所述计算装置包含 第一输出信息计算部，能够利用从所述委托装置接收到的gl及hi，计算Θ (Sph1)，将其计算结果设为所述Z1而输出； 第二输出信息计算部，能够利用从所述委托装置接收到的g2及h2，计算Θ (g2，h2)，将其计算结果设为所述Z2而输出； 第三输出信息计算部，能够利用从所述委托装置接收到的g3及h3，计算Θ (g3，h3)，将其计算结果设为所述Z3而输出；以及 第四输出信息计算部，能够利用从所述委托装置接收到的g4及h4，计算Θ (g4，h4)，将其计算结果设为所述Z4而输出。
9.如权利要求8所述的代理计算系统，其特征在干， 所述第一输入信息计算部计算第一输入信息gl = grl, 所述第一列表信息计算部利用所述^及所述r2，计算rir2， 在所述第一列表存储部存储由所述计算出的^r2和从所述计算装置接收到的Z1 e F构成的信息组(Ar2, Z1X
10.如权利要求8或9所述的代理计算系统，其特征在干， 所述第六输入信息计算部计算第六输入信息h3 = hr7, 所述第三列表信息计算部利用所述r6及所述r7，计算r6r7， 在所述第三列表存储部存储由所述计算出的r6r7和从所述计算装置接收到的Z3 e F构成的信息组(r6r7, z3)。
11.如权利要求8 10中的任一项所述的代理计算系统，其特征在干， 所述第一判定部在满足所述关系的情况下，将tlS2代入0，将《2代入V'， 所述第十随机数生成部利用所述r9，计算ー iV1，并设为r1(l。
12.如权利要求11所述的代理计算系统，其特征在干， 所述第七随机数生成部利用所述r6，计算ー IV1，并设为r7， 在所述第三列表存储部存储由I和所述计算出的Z3 V ' 构成的信息组(I，Z3 V ' -r6r7、
13.如权利要求8 12中的任一项所述的代理计算系统，其特征在干， 所述第四随机数生成部利用所述r5，计算ー r,，并设为r4。
14.如权利要求8 13中的任一项所述的代理计算系统，其特征在干， 还包含利用所述Cl1计算gdl的事前计算部， 所述第三输入信息计算部利用所述事前计算出的gdl，进行所述g2的计算。
15.如权利要求8 14中的任一项所述的代理计算系统，其特征在干， 还包含利用所述d2计算hd2的事前计算部， 所述第八输入信息计算部利用所述事前计算出的hd2，进行所述h4的计算。
16.ー种代理计算方法，利用委托装置委托于计算装置的计算结果，计算Θ (g，h)，其特征在干， 设G、H及F为循环群，设映射Θ :GXH —F为双同态映射，设g为群G的元，设h为群H的元，设Ke为群G的位数，设Kh为群H的位数，设μ g为群G的生成元，设μ h为群H的生成元，设V = Θ ( μ g, μ g),设k为整数的安全參数,设K = 2k, 所述代理计算方法包含 第一随机数生成步骤，所述委托装置的第一随机数生成部生成O以上不足Ke的整数的随机数巧； 第二随机数生成步骤，所述委托装置的第二随机数生成部生成O以上不足Kh的整数的随机数r2 ； 第一输入信息计算步骤，所述委托装置的第一输入信息计算部计算第一输入信息gl =μ grlg ； 第二输入信息计算步骤，所述委托装置的第二输入信息计算部计算第二输入信息h =.11 r2V- h ； 第一输出信息计算步骤，所述计算装置的第一输出信息计算部能够利用从所述委托装置接收到的gl及hi，计算Θ (gl，hi)，将其计算结果设为所述Z1而输出； 第一列表信息计算步骤，所述委托装置的第一列表信息计算部利用从所述计算装置接收到的Z1 e F，计算Zlv_&2; 在所述委托装置的第一列表存储部存储由所述随机数r2和所述计算出的Z1 V 构成的信息组(r2，Zlv_—)的步骤； 第三随机数生成步骤，所述委托装置的第三随机数生成部生成O以上不足K的整数的均匀随机数即Cl1 ； 四随机数生成步骤，所述委托装置的第四随机数生成部生成O以上不足Ke的整数的均匀随机数即r4; 第五随机数生成步骤，所述委托装置的第五随机数生成部生成O以上不足Kh的整数的均匀随机数即r5; 第三输入信息计算步骤，所述委托装置的第三输入信息计算部计算第三输入信息g2 =μ gr4gdl ； 第四输入信息计算步骤，所述委托装置的第四输入信息计算部计算第四输入信息h2 =yhr5 ； 第二输出信息计算步骤，所述计算装置的第二输出信息计算部能够利用从所述委托装置接收到的g2及h2，计算Θ (g2，h2)，将其计算结果设为所述22而输出； 第二列表信息计算步骤，所述委托装置的第二列表信息计算部利用从所述计算装置接收到的z2 e F，计算z2v_rtrf; 在所述委托装置的第二列表存储部存储由所述Cl1、所述r5和所述计算出的Z2 V _*5构成的信息组(も，r5, z2y-lil5)的步骤； 第一判定步骤，所述委托装置的第一判定部设从所述第一列表存储部读入的信息组的第一成分为S1、第二成分为W1,且设从所述第二列表存储部读入的信息组的第一成分为t2、第二成分为S2、第三成分为W2,判定这些信息组是否满足(W1)へCt2S2S1-1) = W2的关系,在满足该关系的情况下，将S1代入O，将W1代入V '； 第六随机数生成步骤，所述委托装置的第六随机数生成部生成O以上不足Ke的整数的均匀随机数即r6 ； 第七随机数生成步骤，所述委托装置的第七随机数生成部生成O以上不足Kh的整数的均匀随机数即r7; 第五输入信息计算步骤，所述委托装置的第五输入信息计算部计算第五输入信息g3 =r6 . 第六输入信息计算步骤，所述委托装置的第六输入信息计算部计算第六输入信息h3 =yhr70h； 第三输出信息计算步骤，所述计算装置的第三输出信息计算部能够利用从所述委托装置接收到的g3及h3，计算θ (g3，h3)，将其计算结果设为所述23而输出； 第三列表信息计算步骤，所述委托装置的第三列表信息计算部利用从所述计算装置接收到的Z3 e F，计算Z3 V' -rfr7 ； 在所述委托装置的第三列表存储部存储由所述r6和所述计算出的Z3 V ' 构成的信息组(r6，Z3 V' _*7)的步骤； 第八随机数生成步骤，所述委托装置的第八随机数生成部生成O以上不足K的整数的均匀随机数即d2 ； 第九随机数生成步骤，所述委托装置的第九随机数生成部生成O以上不足Ke的整数的均匀随机数即r9 ； 第十随机数生成步骤，所述委托装置的第十随机数生成部生成O以上不足Kh的整数的均匀随机数即r1(l; 第七输入信息计算步骤，所述委托装置的第七输入信息计算部计算第七输入信息g4 =μ/9 ; 第八输入信息计算步骤，所述委托装置的第八输入信息计算部计算第八输入信息h4 =yhrl0°hd2； 第四输出信息计算步骤，所述计算装置的第四输出信息计算部能够利用从所述委托装置接收到的g4及h4，计算Θ (g4，h4)，将其计算结果设为所述24而输出； 第四列表信息计算步骤，所述委托装置的第四列表信息计算部利用从所述计算装置接收到的Z4 e F，计算Z4 V' -9rl° ； 在所述委托装置的第四列表存储部存储由所述(12、所述1*9和所述计算出的Z4 V ' -r9r10构成的信息组(d2，r9, z4 V ' -r9r10)的步骤；以及 第二判定步骤，所述委托装置的第二判定部设从所述第三列表存储部读入的信息组的第一成分为S3、第二成分为W3，且设从所述第四列表存储部读入的信息组的第一成分为t4、第二成分为S4、第三成分为W4,判定这些信息组是否满足(W3)へCt4S4S3-1) = W4的关系,在满足其关系的情况下，将(W3)へ(S3-1)输出。
17.ー种代理计算系统的委托装置，所述代理计算系统利用委托装置委托于计算装置的计算结果，计算Θ (g，h),其特征在于， 设G、H及F为循环群，设映射Θ :GXH —F为双同态映射，设g为群G的元，设h为群H的元，设Ke为群G的位数，设Kh为群H的位数，设μ g为群G的生成元，设μ h为群H的生成元,设V = θ ( μ g, μ g),设k为自然数的安全參数,设K = 2k, 所述委托装置包含 第一随机数生成部，生成O以上不足Ke的整数的随机数Γι ； 第二随机数生成部，生成O以上不足Kh的整数的随机数r2 ；第一输入信息计算部，计算第一输入信息A = μ grlg ； 第二输入信息计算部，计算第二输入信息hi = yhr2； 第一列表信息计算部，利用从所述计算装置接收到的Z1 e F，计算Z1 V _m2 ； 第一列表存储部，对由所述随机数r2和所述计算出的Z1 v-&2构成的信息组(r2，Z1 V^rlr2)进行存储； 第三随机数生成部，生成O以上不足K的整数的均匀随机数即Cl1 ； 第四随机数生成部，生成O以上不足Ke的整数的均匀随机数即r4 ； 第五随机数生成部，生成O以上不足Kh的整数的均匀随机数即r5 ； 第三输入信息计算部，计算第三输入信息g2 = μ gr4gdl ； 第四输入信息计算部，计算第四输入信息h2= yhr5； 第二列表信息计算部，利用从所述计算装置接收到的Z2 e F，计算Z2 ； 第二列表存储部，对由所述Cl1、所述1*5和所述计算出的z2v_rtri构成的信息组(も，r5,z2v_riri)进行存储； 第一判定部，设从所述第一列表存储部读入的信息组的第一成分为S1，设第二成分为W1，设从所述第二列表存储部读入的信息组的第一成分为t2，设第二成分为S2，设第三成分为W2,判定这些信息组是否满足(W1)へCt2S2S1-1) = W2的关系,在满足该关系的情况下,将S1代入σ，将W1代入V ,； 第六随机数生成部，生成O以上不足Ke的整数的均匀随机数即r6 ； 第七随机数生成部，生成O以上不足Kh的整数的均匀随机数即r7 ； 第五输入信息计算部，计算第五输入信息g3 = gr6 ; 第六输入信息计算部，计算第六输入信息h3 = μ J7I ; 第三列表信息计算部，利用从所述计算装置接收到的Z3 e F，计算Z3 V ' ； 第三列表存储部，对由所述1"6和所述计算出的Z3V ' 构成的信息组(re，Z3V' _rf,进行存储； 第八随机数生成部，生成O以上不足K的整数的均匀随机数即d2 ； 第九随机数生成部，生成O以上不足Ke的整数的均匀随机数即r9 ； 第十随机数生成部，生成O以上不足Kh的整数的均匀随机数即r1(l ； 第七输入信息计算部，计算第七输入信息g4= μ/9； 第八输入信息计算部，计算第八输入信息h4 = μ hrl0ohd2 ； 第四列表信息计算部，利用从所述计算装置接收到的Z4 e F，计算Z4 V ' -9rl0 ； 第四列表存储部，对由所述d2、所述r9和所述计算出的Z4 V，-r9r10构成的信息组(d2，r9, z4 V ^进行存储；以及 第二判定部，设从所述第三列表存储部读入的信息组的第一成分为s3，设第二成分为W3，设从所述第四列表存储部读入的信息组的第一成分为t4，设第二成分为S4，设第三成分为W4,判定这些信息组是否满足(W3)へCt4S4S3-1) = W4的关系,在满足该关系的情况下,将(W3)へ(S3ベ)输出。
18.—种程序，用于使计算机作为权利要求7或权利要求17的委托装置的各部发挥功倉^:。
19.一种计算机可读取的记录介质，记录有权利要求18的委托装置程序。
全文摘要
本发明利用进行正确的计算的概率低的计算装置进行函数f(x)的计算。设G、H为循环群，设f为将群H的元x映射到群G的函数，设X1、X2为在群G中具有数值的随机变量，设随机变量X1的表现值为x1，设随机变量X2的表现值为x2，整数计算部利用互素的两个自然数a、b，计算满足a′a＋b′b＝1的关系的整数a′、b′。第一可随机数化抽样器，可计算f(x)bx1，将其计算结果设为u。第一幂计算部计算u′＝ua。第二可随机数化抽样器可计算f(x)ax2，将其计算结果设为v。第二幂计算部计算v′＝vb。判定部判定是否为u′＝v′。最终计算部在判定为u′＝v′的情况下，计算ub′va′。
文档编号G09C1/00GK102687184SQ201180005420
公开日2012年9月19日 申请日期2011年1月11日 优先权日2010年1月12日
发明者小林铁太郎, 山本刚 申请人:日本电信电话株式会社
技术领域：
本发明涉及计算机的计算技术。特别涉及利用使其他计算机进行的计算结果进行计算的技术。
背景技术：
委托装置利用委托于不一定进行正确的计算的计算装置的计算结果进行函数f的计算，该技术在非专利文献I中有所记载。非专利文献I记载的自订正器通过多次委托于计算装置进行计算，且采用其计算结果的多数决定，进行函数f的计算(例如，参照非专 利文献I)。现有技术文献非专利文献非专利文献I M. Blum, M. Lub y, and R. Rub inf eld, “Self — Testing/Correctingwith Applications to Numerical Problems”，STOC 1990,pp.73 — 83.
发明内容
发明要解决的课题但是，存在如下课题，S卩，为了非专利文献I的自订正器正常地动作，计算装置需要以一定以上的概率进行正确的计算，利用进行正确的计算的概率低的计算装置进行函数f的计算的技术不得而知。用于解决课题的手段本发明第一方式的代理计算系统设G、H为循环群，设f为将群H的元χ映射到群G的函数，设XpX2为在群G中具有数值的随机变量，设随机变量X1的表现值为X1,设随机变量X2的表现值为X2，包含整数计算部，利用互素的两个自然数a、b，计算满足a' a + b' b=I的关系的整数a,、b,;第一可随机数化抽样器，能够计算f (X)bX1，将其计算结果设为U ;第一幂计算部,计算U' = Ua ;第二可随机数化抽样器,能够计算f (X) aX2,将其计算结果设为V ;第二幂计算部，计算V' = Vb ;判定部，判定是否为u' =V';最终计算部,在判定为U' =V'的情况下，计算Ub' Va/。本发明第二方式的代理计算系统设G、H及F为循环群，设映射Θ :GXH —F为双同态同态映射，设g为群G的元，设h为群H的元，设Ke为群G的位数，设Kh为群H的位数，设μ g为群G的生成元,设μ h为群H的生成元,设V = θ ( μ g，μ 8)，设k为自然数的安全参数，设K = 2k，委托装置包含第一随机数生成部，生成O以上不足Ke的整数的随机数Γι ;第二随机数生成部，生成O以上不足Kh的整数的随机数r2 ;第一输入信息计算部，计算第一输入信息gl= μ ,g;第二输入信息计算部，计算第二输入信息4= μ f ;第一列表信息计算部，利用从计算装置接收到的Z1 e F，计算Z1 v_&2 ;第一列表存储部，对由随机数r2和计算出的Z1 构成的信息组(r2，Z1 V—rw)进行存储；第三随机数生成部，生成O以上不足K的整数的均匀随机数即Cl1 ;第四随机数生成部，生成O以上不足Ke的整数的均匀随机数即r4 ;第五随机数生成部，生成O以上不足&的整数的均匀随机数即r5 ;第三输入信息计算部，计算第三输入信息g2= μ/4gdl;第四输入信息计算部，计算第四输入信息h2= yhr5；第二列表信息计算部，利用从计算装置接收到的Z2 e F，计算Z2 ;第二列表存储部，对由C^r5和计算出的、产构成的信息组(dpivh v_rtri)进行存储；第一判定部，设从第一列表存储部读入的信息组的第一成分为S1，设第二成分为W1，且设从第二列表存储部读入的信息组的第一成分为t2，设第二成分为S2，设第三成分为W2，判定这些信息组是否满足(W1) ' Ct2S2S1-1) = W2的关系,在满足其关系的情况下,将S1代入O，将W1代入V ,;第六随机数生成部，生成O以上不足Ke的整数的均匀随机数即r6 ;第七随机数生成部，生成O以上不足Kh的整数的均匀随机数即r7 ;第五输入信息计算部，计算第五输入信息g3 = gr6 ;第六输入信息计算部，计算第六输入信息h3 = yhr70h ;第三列表信息计算部，利用从计算装置接收到的Z3 e F，计算Z3 V' 第三列表存储部，对由&和计算出的& γ' 构成的信息组(r6，z3 V ' 进行存储；第八随机数生成部，生成O以上不足K的整数的均匀随机数即d2 ;第九随机数生成部，生成O以上不足Ke的整数的均匀随机数即r9 ;第十随机数生成部，生成O以上不足Kh的整数的均匀随机数即r1(l ;第七输入信息计算部，计算第七输入信息g4 = μ gr9 ;第八输入信息计算部，计算第八输入信息h4 = μ hrl° σ hd2 ;第四列表信息 计算部，利用从计算装置接收到的Z4 e F，计算Z4 V ' -r9r10 ;第四列表存储部，对由d2、r9和计算出的Z4 V ' —.Η)构成的信息组(d2，rg，Z4 γ ' -aw)进行存储；第二判定部，设从第三列表存储部读入的信息组的第一成分为S3，设第二成分为W3，且设从第四列表存储部读入的信息组的第一成分为U，设第二成分为S4，设第三成分为W4，判定这些信息组是否满足(W3) aU4S4S,) = W4的关系，在满足其关系的情况下，将(W3) a (巧-1)输出。计算装置包含第一输出信息计算部，可利用从委托装置接收到的^及h，计算Θ (gl，4)，将其计算结果设为Z1而输出；第二输出信息计算部，可利用从委托装置接收到的g2&h2，计算Θ (g2，h2)，将其计算结果设为Z2而输出；第三输出信息计算部，可利用从委托装置接收到的&及匕，计算Θ (g3，h3)，将其计算结果设为Z3而输出；以及第四输出信息计算部，可利用从委托装置接收到的g4&h4,计算Θ (g4, h4),将其计算结果设为Z4而输出。发明的效果能够利用进行正确的计算的概率低的计算装置进行函数f的计算。
图I是第一实施方式 第三实施方式的代理计算系统的例子的功能方框图。图2是第一实施方式 第三实施方式的委托装置及计算装置的例子的功能方框图。图3是第一实施方式 第三实施方式的抽样器的例子的功能方框图。图4是第一实施方式 第三实施方式的第一可随机数化抽样器及第二可随机数化抽样器的例子的功能方框图。图5是第一实施方式 第三实施方式的第一可随机数化抽样器及第二可随机数化抽样器的另一例的功能方框图。图6是第一实施方式 第三实施方式的代理计算方法的例子的流程图。图7是表示步骤S3的例子的流程图。
图8是表示步骤S6的例子的流程图。图9是表不步骤S3的另一例的流程图。图10是表示步骤S6的另一例的流程图。图11是第四实施方式 第十实施方式的代理计算系统的例子的功能方框图。图12是第四实施方式 第十实施方式的委托装置的例子的功能方框图。图13是第四实施方式 第十实施方式的委托装置的例子的功能方框图。图14是第四实施方式 第十实施方式的计算装置的例子的功能方框图。图15是第四实施方式 第十实施方式的代理计算方法的例子的流程图。 图16是第四实施方式 第十实施方式的代理计算方法的例子的流程图。图17是代理计算系统的变形例的功能方框图。
具体实施例方式下面，对本发明的代理计算系统、代理计算方法的实施方式进行详细说明。第一实施方式 第二实施方式是利用委托装置I委托于计算装置2的计算结果来计算f (X)的实施方式。[第一实施方式]如图I所示，第一实施方式的代理计算系统包含委托装置I及计算装置2，利用委托装置I委托于计算装置2的计算结果，来计算f U)。如图2所示，委托装置I例如包含自然数存储部11、整数计算部12、第一幂计算部13、第一列表存储部14、判定部15、第二幂计算部16、第二列表存储部17、控制部18及最终计算部19。计算装置2例如包含第一可随机数化抽样器21及第二可随机数化抽样器22。在第一实施方式中，第一可随机数化抽样器21及第二可随机数化抽样器22对应于计算装置2。设G、H为循环群，设函数f :H — G为将群H的元χ映射到群G的函数，设群G、H的生成元分别为μ8、μ h，设Xp X2为在群G中具有数值的随机变量，设随机变量X1的表现值为X1，设随机变量X2的表现值为X2。在自然数存储部11存储有多个互素的两个自然数a、b的组(a，b)。当设I为不足群G的位数的两个自然数的组且互素的自然数的集合时，可认为在自然数存储部11存储有与I的子集S对应的自然数a、b的组(a，b)。整数计算部12从存储于自然数存储部11的多个自然数的组(a，b)中随机地读入一个自然数的组(a，b)，利用其读入的自然数的组(a，b)，计算满足a' a + b' b = I的关系的整数a'、b'(步骤SI)。由于自然数a、b互素，因此必定存在满足a' a + b/ b =I的关系的整数a,、b,。自然数的组(a，b)的信息发送到第一幂计算部13、第二幂计算部16、第一可随机数化抽样器21及第二可随机数化抽样器22。自然数的组(a'，b,)的信息发送到最终计算部19。控制部18设为t = I (步骤S2)。第一可随机数化抽样器21可计算f (x) bX1，利用χ及b进行计算，将其计算结果设为u (步骤S3)。计算结果u发送到第一幂计算部13。在该申请中，可计算的意思是可按不能忽略的概率以上的概率进行计算。不能忽略的概率是在将安全参数k的广义单调函数即多项式设为多项式F (k)时I / F (k)以上的概率。在此，计算f (X)bX1是对定义为f (χ)\的式的值进行计算。如果能够最终地计算式f (X)bX1的值，则不论计算过程中的计算方法。这关于该申请中出现的其他式的计算也同样。第一幂计算部13计算u' = Ua (步骤S4)。计算结果u和基于其计算结果计算出的u'的组U，u')存储于第一列表存储部14。判定部15判定是否在存储于第一列表存储部14的组(u，u')及存储于第二列表存储部17的组(V，V )中存在成为u' =Y '的组(步骤S5)。假如在第二列表存储部17中未存储有组(V，V')，则不进行该步骤S5的处理，而是进行下一步骤S6的处理。在存在成为u' =V'的组的情况下,进入步骤12。在不存在成为u' =V'的组的情况下,进入步骤S6。第二可随机数化抽样器22可计算f (X) aX2，利用χ及a进行计算，将其计算结果设为V (步骤S6)。计算结果V发送到第二幂计算部16。第二幂计算部16计算V' = Vb (步骤S7)。计算结果V和基于其计算结果计算出的V'的组(V, Y1 )存储于第二列表存储部17。判定部15判定是否在存储于第一列表存储部14的组(u，u')及存储于第二列表存储部17的组(V, V')中存在成为u' =V'的组(步骤S8)。在存在成为u' =V'的组的情况下，进入步骤12。在不存在成为u' =Y'的组情况下，进入步骤S9。控制部18判定是否为t = T (步骤S9)。T为预定的自然数。如果t = T，则将表示不能进行计算的信息例如符号“丄”输出(步骤SI I )，然后结束处理。在不是t = T的情况下，控制部18仅将t加1，即设为t = t + I (步骤S10)，然后返回到步骤S3。表示不能进行计算的信息(在该例子中，符号“丄”)的意思是指计算装置2正确地进行计算的可靠性低于用T规定的基准。换言之，意思是指不能通过T次的重复来进行正确的运算。最终计算部19在判定为u' =V'的情况下,利用与其u'及V'对应的u及V,计算ub' Va/，且将其输出(步骤S12)。成为计算出的ub' va/ =f(x)。关于成为ub' Va/=f (X)的理由，后面进行描述。《关于成为Ub'va/ =f(x)的理由》设X为在群G中具有数值的随机变量。关于w e G，每当某计算装置接收请求时都根据随机变量R抽取样本f并回复《V的抽样器称为关于w具有误差X的抽样器(sampler)。关于w e G，将每当某计算装置接收自然数a的输入时都根据随机变量X抽取样本χ'并回复WaX'的抽样器称为关于w具有误差X的可随机数化抽样器(randomizablesampler)。可随机数化抽样器如果用作a = I，则作为抽样器发挥功能。上述实施方式的代理计算系统在构成输入χ而输出f (χ)的代理计算系统时，使用关于f (x)具有误差X1的第一可随机数化抽样器21、关于f (χ)具有误差X2的第二可随机数化抽样器22。发明者发现，u' = N'成立即ua = Vb成立的理由是第一可随机数化抽样器21正确地计算出U = f (X) bX1,且第二可随机数化抽样器22正确地计算出V = f (X) aX2,进而X1及X2为群G的单位元eg的可能性非常高。在此，省略其证明。在第一可随机数化抽样器21正确地计算出u = f (X)bX1、第二可随机数化抽样器22正确地计算出v = f (χ) aX2,且X1及X2为群G的单位元eg时,成为ub/ va/ = (f (χ)bXl)b/ (f (x)ax2)a/ =(f (x)beg)b/ (f (x)aeg)a/ = f (x)bb/ egb/ f (x)aa/ ega/
=f (X) (bbI +aa, )= f (x)。关于(q1; q2) e I，关于i = 1、2,分别用Jii (q1; q2) = Qi来定义函数π it)另外，设为L = min (# π 1 (S), # π 2 (S))。# 为集合 的位数。在群G为循环群及不易进行位数的计算的群时，上述代理计算系统输出“丄”以外时的输出不是f (x)的概率在可忽略的程度的误差范围内最高可期待T2L / #S程度。如果L / #3为可忽略的量且T为多项式级程度的量，则上述代理计算系统就以压倒性的概率输出f U)。在L / #S达到可忽略的量那样的S的例子中，存在例如S ={(l，d) I de[2，I G I — I]}。另外，如图2中的虚线所示，也可以在计算装置2上设置抽样器23。抽样器23设X3为在群G中具有数值的随机变量、设随机变量X3的表现值为X3，从而可计算f (x) X3，如果a = 1，则代替第二可随机数化抽样器22，将其计算结果设为上述V，如果b = 1，则代替第一可随机数化抽样器21，将其计算结果设为上述U。通常，抽样器的计算量比可随机数化抽样器小。在a = l、b = I时，通过抽样器23代替第一可随机数化抽样器21、第二可随机数化抽样器22进行计算，能够减小计算装置2
的计算量。[第二实施方式]第二实施方式的代理计算系统是将第一可随机数化抽样器21及第二可随机数化抽样器22的一个例子具体化而成的系统，换言之，是将步骤S3及步骤S6的一个例子具体化而成的系统。下面，以与第一实施方式不同的部分为中心进行说明，关于共同的部分，省略重复说明。如图3所示，第二实施方式的第一可随机数化抽样器21例如包含第一随机数生成部110、第一输入信息计算部111、第一输出信息计算部24及第一计算部112。另外，如图3所示，第二实施方式的第二可随机数化抽样器22例如包含第二随机数生成部113、第二输入信息计算部114、第二输出信息计算部25及第二计算部115。在第二实施方式中，第一随机数生成部110、第一输入信息计算部111、第一计算部112、第二随机数生成部113、第二输入信息计算部114及第二计算部115包含在委托装置I中。另外，第一输出信息计算部24及第二输出信息计算部25包含在计算装置2中。在第二实施方式中，第一输出信息计算部24及第二输出信息计算部25与计算装置2对应。第二实施方式的函数f设为同态映射(準同型写像)。另外，设群H的生成元为yh，设群H的位数为Kh,设V = f ( μ h)0步骤S3由图7例示的步骤S31 步骤S34构成。第一随机数生成部110生成O以上不足Kh的整数的均匀随机数Γι(步骤S31)。生成的随机数发送到第一输入信息计算部111。第一输入信息计算部111计算第一输入信息μ hrlxb (步骤S32)。计算出的第一输入信息μ J1Xb发送到第一输出信息计算部24。第一输出信息计算部24利用第一输入信息μ J1Xb进行计算，将其计算结果设为第一输出信息Z1 (步骤S33)。计算出的第一输出信息Z1发送到第一计算部112。第一输出信息计算部24可计算f ( μ hrlxb)0第一输出信息计算部24的计算结果有时是f (μJ1Xb)，有时不是f UhW在此，411的右上角的1'1是1'1的意思。这样，在该申请中，在设α为第一字符、β为第二字符、Y为数字并表述为α 的情况下，该β Y的意思是β Y，S卩，β的下标Y。
第一计算部112计算Z1 V _ri，将其计算结果设为u(步骤S34)。计算结果u发送到第一幂计算部13。在此，u = Z1 V n = f (x) bX10即，Z1 V μ成为关于f (χ)具有误差X1的可随机数化抽样器。关于其理由，后面进行描述。步骤S6由图8例示的步骤S61 步骤S64构成。第二随机数生成部113生成O以上不足Kh的整数的均匀随机数r2(步骤S61)。生成的随机数r2发送到第二输入信息计算部114。第二输入信息计算部114计算第二输入信息4!；^步骤562)。计算出的第二输入信息μ hr2xa发送到第二输出信息计算部25。第二输出信息计算部25利用第二输入信息μ J2Xa进行计算，将其计算结果设为第二输出信息Z2 (步骤S63)。计算出的第二输出信息Z2发送到第二计算部115。第二输出信息计算部25可计算f ( μ hrtxa)。第二输出信息计算部25的计算结果有时是f (μJ2Xa),有时不是f (UhrV)0第二计算部115计算Z2 V 将其计算结果设为V (步骤S64)。计算结果V发送到第二幂计算部16。在此，成为￥ = 2^— = €(1)12。S卩，Z2 V —成为关于f (χ)具有误差X2的可随机数化抽样器。关于其理由，后面进行描述。在第二实施方式中，也可以在a = Ub=I时，通过抽样器23代替第一可随机数化抽样器21或第二可随机数化抽样器22而计算u或V的值，来消减计算量。如图4所不,第二实施方式的抽样器23例如包含第三随机数生成部116、第三输入信息计算部117、第三输出信息计算部26、第三计算部118。第三随机数生成部116、第三输入信息计算部117及第三计算部118包含在委托装置I中。第三输出信息计算部26包含在计算装置2中。如果a = I、b = 1，则抽样器23的各部代替第一可随机数化抽样器21、第二可随机数化抽样器22，进行下面的处理。第三随机数生成部116生成O以上不足Kh的整数的随机数r3。生成的随机数r3发送到第三输入信息计算部117。第三输入信息计算部117计算第三输入信息Xlr3。计算出的第三输入信息Xlr3发送到第三输出信息计算部26。第三输出信息计算部26利用第三输入信息V3进行计算，将其计算结果设为第三输出信息z3。计算出的第三输出信息Z3发送到第三计算部118。第三输出信息计算部26可计算f (χΛ)。第三输出信息计算部26的计算结果有时是f (ΧΛ)，有时不是f (Xr3)0第三计算部118计算z31/l:3,如果是a = I，则将其计算结果设为V,如果是b = I,则将其计算结果设为U。计算结果V发送到第二幂计算部16。计算结果u发送到第一幂计算部13。在此,成为u = V = Z31"3 = f (X)X30 S卩，z31/l:3成为关于f (χ)具有误差X3的抽样器。Ζ31/λ成为关于f (χ)具有误差X3的抽样器。其理由，后面进行描述。在难以进行ζ31/ 的计算即Z3的方根的计算的情况下，也可以如下那样计算u及/或V。第三计算部118将随机数1*3和基于其随机数1*3计算出的23的组依次设为(Ci1, ^)，(α2, β2)，…，(απ，βω),…，且将其存储于未图示的存储部。m为自然数。第三计算部118如果Ct1, α 2,…，α ^的最小公倍数达到I，则也可以将Y1, y 2,…，Yni设为整数,计
算成为 Y1Q1+ Y2Q2 H-----h Y111Ct ^ = I 的 Y1, Y2,…，Y 利用该 Y1, Y2, Ym, if
算IIi = = β/1 β /2…β mYm，将其计算结果设为u及/或V。这样，通过将利用随机数干扰χ的信息发送到计算装置2，能够将成为函数f的值的计算对象的X eH相对于对委托装置I和计算装置2之间的通信进行拦截的第 三者及计算装置2保密。《关于Z1V ' Z2 V -2成为关于f (χ)分别具有误差Xp X2的可随机数化抽样器的
理由》设c为自然数、R及R'为随机数，将计算装置2利用μ 进行计算的计算结果设为Β( μ hW即，当将计算装置2返送到委托装置I的计算结果设为z时，z = Β( μ hExc)),将在群G中具有数值的随机变量X定义为X = B ( μ hK' )f ( yhE/ ) '这时，成为ZV-K = B (μ hExc) f ( μ h) = Xf (μ hExc) f ( μ h) = Xf ( μ h) Ef(x)cf ( μ h) = f (X) CX。即，ZV-^成为关于f (χ)具有误差X的可随机数化抽样器。在上述展开式中，利用X= B (yhK, )f (yhE/ 广1 = B UhVOf (μΛ。)—1，且B (UhV) = Xf (μ AcO这种性质。该性质基于函数f为同态映射、R及R'为随机数。因此，当考虑a、b为自然数、I^r2为随机数时，同样,Z1 v_r\z2 v ^r2成为关于f(x)分别具有误差XpX2的可随机数化抽样器。《关于Z31"3成为关于f(χ)具有误差X3的抽样器的理由》设R及R'为随机数，将计算装置2利用Xk进行计算的计算结果设为B (Χκ) (ΒΡ,当将计算装置2返送到委托装置I的计算结果设为z时，z=B (χκ))，将在群G中具有数值的随机变量X定义为X = B (xE) 1/Ef (χ)'这时,成为ζ1/κ = B (xK) 1/K = Xf (χ) = f (χ) X。SP, z1 zκ 成为关于 f (χ)具有误差X的抽样器。在上述展开式中，利用X = B (xE) 1/Ef (Xk)'B (xE) 1/E = Xf (χκ)这种性质。该性质基于R及V为随机数。因此，当考虑r3为随机数时，ζ1/κ成为关于f (χ)具有误差X3的可随机数化抽样器。[第三实施方式]第三实施方式的代理计算系统是将第一可随机数化抽样器21及第二可随机数化抽样器22的另一例具体化而成的系统，换言之，是将步骤S3及步骤S6的另一例具体化而成的系统。具体而言，是将H = GXG且函数f相对于EIGamal密码的解码函数即密钥s及密文(Cl，c2)为f Cc1, C2) = C1C2-3时的第一可随机数化抽样器21及第二可随机数化抽样器22的例子具体化而成的系统。下面，以与第一实施方式不同的部分为中心进行说明，关于共同的部分，省略重复说明。如图5所示，第三实施方式的第一可随机数化抽样器21例如包含第四随机数生成部119、第五随机数生成部120、第四输入信息计算部121、第五输入信息计算部122、第四输出信息计算部27及第四计算部123。如图5所示，第二可随机数化抽样器22例如包含第六随机数生成部124、第七随机数生成部125、第六输入信息计算部126、第七输入信息计算部
127、第五输出信息计算部28及第五计算部128。第四随机数生成部119、第五随机数生成部120、第四输入信息计算部121、第五输入信息计算部122、第四计算部123、第六随机数生成部124、第七随机数生成部125、第六输入信息计算部126、第七输入信息计算部127、第五输出信息计算部28及第五计算部128包含在委托装置I中。第四输出信息计算部27及第五输出信息计算部28包含在计算装置2中。在第三实施方式中，第四输出信息计算部27及第五输出信息计算部28与计算装置2对应。 在第三实施方式中，χ = (C1, c2)，f (C1, C2)为从直积群GXG向G的同态映射，设群G的生成元为μ g，设群G的位数为Ke，委托装置I和计算装置2事前得知的是相对于相同的密钥s的密文(V，ff) e H和将其密文解码后的解码文f (V，W) = Y e G。第三实施方式的步骤S3由图9例示的步骤S3P 步骤S36,构成。第四随机数生成部119生成O以上不足Ke的整数的均匀随机数r4 (步骤S31')。生成的随机数r4发送到第四输入信息计算部121、第五输入信息计算部122及第四计算部123。第五随机数生成部120生成O以上不足Ke的整数的均匀随机数r5 (步骤S32')。生成的随机数r5发送到第四输入信息计算部121及第四计算部123。第四输入信息计算部121计算第四输入信息C1bVrtU /5 (步骤S33')。计算出的第四输入信息C1bVrtU /5发送到第四输出信息计算部27。第五输入信息计算部122计算第五输入信息C2bWrt (步骤S34')。计算出的第五输入信息C2bWrt发送到第四输出信息计算部27。第四输出信息计算部27利用第四输入信息C1bVrt μ /5及第五输入信息C2bWrt进行计算。将其计算结果设为第四输出信息Z4 (步骤S35')。第四输出信息计算部27可计算f Cc1bVr4U gr5,c2bffr4)0第四输出信息计算部27的计算结果有时是 Mc1bVrtU /5，C2bWrt),有时不是 f (C1bVrtU /5，c2bffr4)0第四计算部123计算ζ/Μμ:5，将其计算结果设为u (步骤S36')。计算结果u发送到第一幂计算部13。在此，成为11 = 2/_^/5 = € (CljC2)bX10即，z4Y_rtyg_r5成为关于f (Cl，C2)具有误差X1的可随机数化抽样器。关于其理由，后面进行描述。第三实施方式的步骤S6由图10例示的步骤S6P 步骤S66,构成。第六随机数生成部124生成O以上不足Ke的整数的均匀随机数r6 (步骤S61')。生成的随机数r6发送到第六输入信息计算部126、第七输入信息计算部127及第五计算部
128。第七随机数生成部125生成O以上不足Ke的整数的均匀随机数r7 (步骤S62')。生成的随机数r7发送到第六输入信息计算部126及第五计算部128。第六输入信息计算部126计算第六输入信息C1aVrf μ/7 (步骤S63')。计算出的第六输入信息C1aVrf μ ；7发送到第五输出信息计算部28。第七输入信息计算部127计算第七输入信息C2aWrf (步骤S64')。计算出的第七输入信息C2aWrf发送到第五输出信息计算部28。第五输出信息计算部28利用上述第六输入信息C1aVrf^ /7及上述第七输入信息C2aWrfi进行计算，将其计算结果设为第五输出信息Z5 (步骤S65')。计算出的第五输出信息Z5发送到第五计算部128。第五输出信息计算部28可计算f Cc1aVr6 μ/7, C2aWr6 )0第五输出信息计算部28的计算结果有时是 Mc1aVrV /7，C2aWrfi)，有时不是 f (C1aVrfi μ /7，c2ar6)。第五计算部128计算Z5Y_rfyg_'将其计算结果设为V (步骤S66')。计算结果V发送到第二幂计算部16。在此，成为￥ = 2/_1^广=€ (cl, c2)ax20即，zfVj7成为关于f (Cl，C2)具有误差X2的可随机数化抽样器。关于其理由，后面进行描述。 《关于z4Y—rtU /5、ζ5Υ_Λμ 成为关于f Cc1, C2)分别具有误差的可随机数化抽样器的理由》设为c为自然数、RpR2J/及V为随机数，将计算装置2利用(^>/2及C2cWki进行计算的计算结果设为B (C1cVei μ gE2, C2cWei)(即，当将计算装置2返送到委托装置I的计算结果为z时，为z = B Cc1cVei μ/2, c2f))，将在群G中具有数值的随机变量X定义为X = B (νΕ1/ μ8Ε2/ ,ffE1/ )f (νΕ1/ μ8Ε2/ ,ffE1/ )'这时，zY_K1μ g-R2 = B Cc1cVei μ :，C2cWki)Υ_Κ1 μ 广=Xf Cc1cVei μ :，C2cWki)Υ_Κ1 μ ,=Xf Cc1, C2) cf (V, ff) E1f ( μ g，eg) Κ2Υ_Κ1 μ ；Ε2 = Xf Cc1, C2) cYei μ gK2Y_K1 μ ；Ε2 = f Cc1, C2)I。即，ζΓΕ1 μ ；Ε2成为关于f (χ)具有误差X的可随机数化抽样器。另外，eg设为群G的单位元。在上述展开式中，利用X= B (Vk1' UgE2/ ,ffE1/ )f (VE1/ UgE2/ , ffE1 / ) = B(C1cVei μ gE2, C2cWei) f (C1cVei μ gE2, C2cWei),且 B (C1cVei μ gK2，c2cffE1) = Xf (C1cVei μ gK2，C2cWei)这种性质。该性质基于RpRyR/及R2'为随机数。因此，当考虑a、b为自然数、r4、r5、r6&r7为随机数时，同样，Z4Y - r4 U g_r5、Z5Fr6 μ/7成为关于f Cc1, C2)分别具有误差XpX2的可随机数化抽样器。[第一实施方式 第三实施方式的变形例等]随机变量Xp X2及X3既可以相同，也可以不同。通过第一随机数生成部110、第二随机数生成部113、第三随机数生成部116、第四随机数生成部119、第五随机数生成部120、第六随机数生成部124及第七随机数生成部125分别生成均匀随机数，代理计算系统的安全性最高。但是，在要求的安全性的水平没有那么高的情况下，第一随机数生成部110、第二随机数生成部113、第三随机数生成部116、第四随机数生成部119、第五随机数生成部120、第六随机数生成部124及第七随机数生成部125也可以分别生成不是均匀随机数的随机数。在上述的例子中，各调用一次第一可随机数化抽样器21、第二可随机数化抽样器22，但为了减少委托装置I和计算装置2之间的通信次数，也可以对同一 a、b多次调用第一可随机数化抽样器21、第二可随机数化抽样器22，委托装置I通过一次通信就能够取得多个 U、V0第一可随机数化抽样器21、第二可随机数化抽样器22及抽样器23的各部既可以配置于委托装置1，也可以配置于计算装置2。即，既可以如第一实施方式那样将各部全部配置于计算装置2，也可以如第二实施方式及第三实施方式那样分开配置于委托装置I及计算装置2。委托装置I的各部间的数据交换既可以直接进行，也可以经由未图示的存储部来进行。同样，计算装置2的各部间的数据交换既可以直接进行，也可以经由未图示的存储部来进行。委托装置I及计算装置2可分别由计算机来实现。在这种情况下，该装置应有的各功能的处理内容通过程序来记述。而且，通过由计算机执行该程序，这些装置的各处理功能在计算机上实现。记述有该处理内容的程序能够 记录于计算机可读取的记录介质。另外，在该方式中，通过在计算机上执行规定的程序，构成这些装置，但也可以硬件地实现这些处理内容的至少一部分。[第四实施方式]第四实施方式 第十实施方式是利用委托装置I'委托于计算装置2,的计算结果来计算Θ (g，h)的实施方式。如图11所示，第四实施方式的代理计算系统包含委托装置I'及计算装置2'，利用委托装置P委托于计算装置2'的计算结果，计算双同态映射Θ (g，h)。在此，设G、H及F为循环群，设映射Θ :GXH —F为双同态映射，设g为群G的元，设h为群H的元，设Ke为群G的位数，设Kh为群H的位数，设μ8为群G的生成元，设UhS群H的生成元，设V = θ ( μ g，μ g)，设k为I以上的整数的安全参数，设K = 2k。双同态映射的意思是相对于两个输入都为同态的映射。在该例子中，映射Θ (g,h)相对于群G的元g为同态，且相对于群H的元h为同态。在委托装置I'和计算装置2'之间确立有通信路径，委托装置Γ及计算装置2'可双向地通信。该通信路径也可以不必秘密地保持，第三者可拦截在该通信路径流通的信息。委托装置I'向不可靠的计算装置2'发送由随机数干扰后的信息，计算装置2'利用该干扰后的信息，按照一定的算法进行计算，然后将其计算结果回复到委托装置I,。通过重复向该计算装置2'的信息的收发，委托装置I'最终地计算Θ (g，h)。委托装置I'首先通过步骤S 11' 步骤S 125'(图15)的处理，计算与Θ (g，yh)同等的信息(σ，V ')，利用与其Θ (g，yh)同等的信息(σ，V ')，通过步骤S21' 步骤S225'的处理,计算Θ (g, μ)。委托装置I'例如包含图12及图13例示的第一随机数生成部11'、第二随机数生成部12'、第一输入信息计算部13'、第二输入信息计算部14'、第一列表信息计算部15'、第一列表存储部16'、接收部17'、发送部18'、第四随机数生成部21'、第五随机数生成部22'、第三输入信息计算部23'、第四输入信息计算部24’、第二列表信息计算部25'、第二列表存储部26'、第三随机数生成部27'、第一判定部28'、第六随机数生成部31'、第七随机数生成部32'、第五输入信息计算部33'、第六输入信息计算部34'、第三列表信息计算部35'、第三列表存储部36'、第九随机数生成部41'、第十随机数生成部42'、第七输入信息计算部43'、第八输入信息计算部44'、第四列表信息计算部45'、第四列表计算部46'、第八随机数生成部47'及第二判定部48'。如图14所示，计算装置2'例如包含接收部51'、发送部52'、第一输出信息计算部53'、第二输出信息计算部54'、第三输出信息计算部55'及第四输出信息计算部56'。<步骤 Sll'(图 15)>第一随机数生成部11'生成O以上不足Ke的整数的均匀随机数Γι(步骤Sll')。生成的随机数A发送到第一输入信息计算部13'及第一列表信息计算部15'。< 步骤 S12' >第二随机数生成部12'生成O以上不足Kh的整数的均匀随机数r2(步骤S12')。生成的随机数r2发送到第二输入信息计算部14'、第一列表信息计算部15'及第一列表 存储部W。< 步骤 S13' >第一输入信息计算部13'计算第一输入信息gl= Ugrlg (步骤S13')。计算出的&发送到发送部18'。在此，μ8的右上角的rl是Γι的意思。这样，在该申请中，在设α为第一字符、β为第二字符、Y为数字而表述为α 的情况下，该β Y的意思是β Y，S卩，β的下标Y。另外，计算gl = μ grlg是计算用μ grlg这种式定义的gl的值。如果能够最终地计算式μ的值，则不论计算过程中的计算方法。这关于该申请中出现的其他式的计算也同样。< 步骤 S14' >第二输入信息计算部14'计算第二输入信息Ii1= yhr2 (步骤S14')。计算出的Ii1发送到发送部18'。< 步骤 S15' >发送部18'将第一输入信息&及第二输入信息Ii1发送到计算装置2'(步骤S15/ )。< 步骤 S16' >计算装置2'的接收部51'(图14)接收第一输入信息gl及第二输入信息Ill (步骤 S16')。< 步骤 S17' >第一输出信息计算部53 ^利用第一输入信息gl及第二输入信息Ii1进行计算，将其计算结果设为第一输出信息Z1 (步骤S17' )。Z1发送到发送部52'。第一输出信息计算部53'可计算Θ (gphP。第一输出信息计算部53'的计算结果有时是Θ化1，111)，有时不是0 (gphP。在该申请中，可计算的意思是可按不能忽略的概率进行计算。不能忽略的概率是在设安全参数k的广义单调增加函数的多项式为多项式f(k)时的I / f (k)以上的概率。< 步骤 S18' >发送部52'将第一输出信息Z1发送到委托装置I'(步骤S18')。< 步骤 S19' >委托装置I'的接收部17'(图12)接收第一输出信息Z1 (步骤S19')。接收到的第一输出信息Z1发送到第一列表信息计算部15'。在此，第一输出信息Z1设为群F的
J Li ο<步骤 SllO' >第一列表信息计算部15 '利用随机数Γι、随机数r2及第一输出信息Z1,计算Z1V^1r2 (步骤SllO')。计算出的Z1Vilrt发送到第一列表存储部16'。<步骤 Slll' >由随机数1*2和21 v_—构成的信息组(r2，Z1 V _—)追加于列表L115在该例子中，在第一列表存储部16'存储信息组(r2，Z1 v_&2)(步骤Slll')。<步骤 SI 12' > 第三随机数生成部27'生成O以上不足K的整数的均匀随机数即屯(步骤S112')。生成的随机数Cl1发送到第三输入信息计算部23'及第二列表存储部26'。<步骤 SI 13' >第四随机数生成部2Γ生成O以上不足Ke的整数的均匀随机数即r4 (步骤S113')。生成的随机数r4发送到第三输入信息计算部23'及第二列表信息计算部25'。<步骤 SI 14' >第五随机数生成部22'生成O以上不足&的整数的均匀随机数即1*5 (步骤S114')。生成的随机数r5发送到第四输入信息计算部24'、第二列表信息计算部25'及第二列表存储部26'。<步骤 SI 15' >第三输入信息计算部23'计算第三输入信息g2= μ gr4gdl (步骤S115')。计算出的第三输入信息g2发送到发送部18，。<步骤 SI 16' >第四输入信息计算部24'计算第四输入信息h2= yhr5 (步骤S116')。计算出的第四输入信息h2发送到发送部18'。<步骤 SI 17' >发送部18'将第三输入信息&及第四输入信息匕发送到计算装置2'(步骤S117/ )。<步骤 SI 18' >计算装置2'的接收部51'(图14)接收第三输入信息g2及第四输入信息匕(步骤 S118')。<步骤 SI 19' >第二输出信息计算部54'利用第三输入信息g2及第四输入信息h2进行计算，将其计算结果设为第二输出信息Z2 (步骤S119' )。Z2发送到发送部52'。第二输出信息计算部54'可计算Θ (g2，h2)。第二输出信息计算部54'的计算结果有时是Θ (&汕2)，有时不是0 (g2，h2)。< 步骤 S120' >发送部52'将第二输出信息Z2发送到委托装置I'(步骤S120')。< 步骤 S121' >委托装置Γ的接收部17'(图12)接收第二输出信息Z2 (步骤S121')。接收到的第二输出信息Z2发送到第二列表信息计算部25'。在此，第二输出信息Z2设为群F的
J Li ο< 步骤 S122' >第二列表信息计算部25'利用随机数r4、随机数1*5及第二输出信息22，计算z2v-r4r5 (步骤S122')。计算出的Z2 V 发送到第二列表存储部26'。<步骤 S123' >由随机数Cl1、随机数r5和Z2 V 构成的信息组(屯，r5，Z2 v ^4r5)追加于列表L2。在该例子中，在第二列表存储部26'存储信息组(dpivhvi5)(步骤S123')。< 步骤 S124' > 第一判定部28'在设从第一列表存储部16'读入的信息组的第一成分为S1、第二成分为W1，且设从第二列表存储部26'读入的信息组的第一成分为t2、第二成分为S2、第三成分为W2时,判定这些信息组是否满足(W1)八Ct2S2S1-1) = W2的关系(步骤S124')。第一判定部28'在第一列表存储部16'及第二列表存储部26'存储有多个信息组的情况下，判定由存储于第一列表存储部16'的信息组(r2，Z1V^lr2)和存储于第二列表存储部26'的信息组((11，1'5，22〃_1^5)构成的所有的信息对是否满足上述关系。当然，关于已判定了是否满足上述关系的信息对，也可以省略其判定处理。< 步骤 S125' >第一判定部28'在满足上述关系的情况下，将S1代入Ojfw1代入V'(步骤S125/ )。在此,成为 V ' 1/0 = W/7。= Θ (g, μ h)。关于成为 V ' 1/0 = Θ (g, μ h)的理由，后面进行描述。在不满足上述关系的情况下，返回到步骤Sll'。<步骤 S21'(图 16)>第六随机数生成部3Γ生成O以上不足Ke的整数的均匀随机数即1*6 (步骤S21')。生成的随机数r6发送到第五输入信息计算部33'、第三列表信息计算部35'及第三列表存储部36'。< 步骤 S22' >第七随机数生成部32'生成O以上不足&的整数的均匀随机数即1> (步骤S22')。生成的随机数r7发送到第六输入信息计算部34'及第三列表信息计算部35'。< 步骤 S23' >第五输入信息计算部33'计算第五输入信息g3= μ/6 (步骤S23')。计算出的g3发送到发送部18'。< 步骤 S24' >第六输入信息计算部34'计算第六输入信息h3= yhrt°h (步骤S24')。计算出的匕发送到发送部18'。< 步骤 S25' >发送部18'将第五输入信息&及第六输入信息匕发送到计算装置2'(步骤S25/ )。< 步骤 S26' >计算装置2'的接收部51'(图14)接收第五输入信息g3及第六输入信息匕(步骤 S26')。< 步骤 S27' >第三输出信息计算部55'利用第五输入信息g3及第六输入信息h3进行计算，将其计算结果设为第三输出信息Z3 (步骤S27' )。Z3发送到发送部52'。第三输出信息计算部55'可计算Θ (g3，h3)。第三输出信息计算部55'的计算结果有时是Θ (&，4)，有时不是0 (g3，h3)。〈步骤S28' >发送部52'将第三输出信息Z3发送到委托装置I'(步骤S28')。< 步骤 S29' > 委托装置Γ的接收部17'(图13)接收第三输出信息Z3 (步骤S29')。接收到的第三输出信息Z3发送到第三列表信息计算部35'。在此，第三输出信息Z3设为群F的
J Li ο< 步骤 S210' >第三列表信息计算部35 '利用随机数r6、随机数r7及第三输出信息z3，计算Z3V' (步骤S210')。计算出的Z3V 发送到第三列表存储部36'。<步骤 S211' >由随机数1*6和23一 _.7构成的信息组(r6，Z3V ' _rflr7)追加于列表L3。在该例子中，在第三列表存储部36'存储信息组(r6，Z3V'(步骤S211' χ< 步骤 S212' >第八随机数生成部47'生成O以上不足K的整数的均匀随机数即(12 (步骤S212')。生成的随机数d2发送到第八输入信息计算部44及第四列表存储部46'。< 步骤 S213' >第九随机数生成部4Γ生成O以上不足Ke的整数的均匀随机数即1*9 (步骤S213')。生成的随机数r9发送到第七输入信息计算部43'、第四列表信息计算部45'及第四列表存储部46'。< 步骤 S214' >第十随机数生成部42'生成O以上不足&的整数的均匀随机数即r1(l (步骤S214')。生成的随机数r1(l发送到第八输入信息计算部44'、第四列表信息计算部45'及第四列表存储部46'。< 步骤 S215' >第七输入信息计算部43'计算第七输入信息g4 = # (步骤S215')。计算出的第七输入信息g4发送到发送部18'。< 步骤 S216' >第八输入信息计算部44'计算第八输入信息h4= yhrt°°hd2(步骤S216')。计算出的第八输入信息h4发送到发送部18'。< 步骤 S217' >发送部18'将第七输入信息&及第八输入信息114发送到计算装置2'(步骤S217/ )。< 步骤 S218' >
计算装置2'的接收部51'(图14)接收第七输入信息g4及第八输入信息匕(步骤 S218')。< 步骤 S219' >第四输出信息计算部56'利用第七输入信息g4及第八输入信息h4进行计算，将其计算结果设为第四输出信息Z4 (步骤S219' )。Z4发送到发送部52'。第四输出信息计算部56'可计算Θ (g4，h4)。第四输出信息计算部56'的计算结果有时是Θ (g4，h4)，有时不是Θ (g4，h4)。< 步骤 S220' >发送部52'将第四输出信息Z4发送到委托装置I'(步骤S220')。
< 步骤 S221' >委托装置Γ的接收部17'(图12)接收第四输出信息Z4 (步骤S221)。接收到的第四输出信息Z4发送到第四列表信息计算部45'。在此，第四输出信息Z4设为群F的
J Li ο< 步骤 S222' >第四列表信息计算部45'利用随机数r9、随机数r1(l及第四输出信息24，计算z4v ^ (步骤S222')。计算出的Z4 V' 发送到第四列表存储部46'。< 步骤 S223' >由随机数(12、随机数1*9和2^ ' __°构成的信息组(d2，r9，z4v '追加于列表L4。在该例子中，在第四列表存储部46'存储信息组(d2，r9，Z4Viltl)(步骤S223')。< 步骤 S224' >第二判定部48'在设从第三列表存储部36'读入的信息组的第一成分为S3、第二成分为W3，且设从第四列表存储部46'读入的信息组的第一成分为U、第二成分为S4、第三成分为W4时,判定这些信息组是否满足(W3)八Ct4S4S3-1) = W4的关系(步骤S224')。第二判定部48'在第三列表存储部36'及第四列表存储部46'存储有多个信息组的情况下，判定由存储于第三列表存储部36'的信息组(r6，z3v' 和存储于第四列表存储部46'的信息组(d2，r9，Z4V' —&1(ι)构成的所有的信息对是否满足上述关系。当然，关于已判定了是否满足上述关系的信息对，也可以省略其判定处理。< 步骤 S225' >第二判定部48,在满足上述关系的情况下，将(W3) a (O输出(步骤S225')。在此，成为(W3)八(Si1) = Θ (g，h)。关于成为(W3)八(S3 + 1) = Θ (g，h)的理由，后面进行描述。在不满足上述关系的情况下，返回到步骤S21'。在难以进行(W3)八(Si1)的计算即W3的方根的计算的情况下，可如下那样容易地计算Θ (g，h)。第二判定部48'重复进行步骤S21' 步骤S224'的处理，将满足(W3)八Ct4S4S3-1)= W4 的关系的 W3 和 S3 的组(w3, S3)依次设为(a !,S1), ( α 2，S2), ···, ( a m, Sm), ···,并将其存储于存储部410'。m为自然数。第二判定部48'如果发现与S1成为互素的Sm，则设L1和L2为整数，计算成为L1S1 + L2Sm = I的L1及L2,利用该L1及L2,计算a α成为 W= Θ (g，h) (L1S1 + L2S2)= Θ (g，h)。另外，第二判定部 48'如果 S1, S2,…，Sm的最小公倍数为1，则也可以设L1, L2, ···, Lm为整数,计算成为L1S1 + L2S2 H-----l· LmSm =I的 L1, L2, ···, Lni，利用该 L1, L2,…，Lni，计算 Ct α 尸…α成为 α 广1 a 2L2…α，= θ
(g，h) (Llsl + L2S2+---+LmSm)= Θ (g，h)。假设有能够拦截委托装置I'和计算装置2'之间的通信的攻击者M，也可通过用仅委托装置P得知的随机数(例如，I^r2)对在委托装置I'及计算装置2'之间进行通信的信息进行干扰来对攻击者M保密。另外，在委托装置I'及计算装置2'之间进行通信的信息由仅委托装置I'得知的rl、r2等随机数进行干扰，因此计算装置2'当然不能得知委托装置I'将要最终计算的Θ (g，h),连其输 入即g及h也不能得知。因此，计算装置2'不需要为可靠的计算机，就能够缓和用于计算双同态映射的系统的构成必要条件。另外，可靠的计算机通常价格高，在运用上需要费用，但由于不需要计算装置2'为可靠的计算机，因此能够消减用于计算双同态映射的系统的构筑及运用的成本。《关于成为V'1/0 = Θ (g，μ h)的理由》首先,对叫做可随机化抽样器(randomizable sampler)的随机变量Sx (d)进行说明。与w e F有关的误差X的可随机化抽样器即随机变量Sx (d)为Sx (d) = WdX0 d为自然数。在此，当设Rp R2, R1'及R2'为随机数、设计算装置利用gV gK1及μ hE2进行计算的计算结果为B (gdygE1, μ；2)(当将计算装置返送到委托装置的计算结果设为Z时，为ζ=B (gVgE1, μ hK2))，且将在群F中具有数值的随机变量X定义为X = B (μ/ μ / 2)17 r 2 θ ( μ gK, ^ μ h) ―1 时，Sx (d) = ζ α ζΚ2) V -K1 成为与 θ (g, μ h)有关的误差 χ 的可随机化抽样器。原因是，sx(d) = z(1/K2) V—K1 = B (gdygK1，yhK2)1/K2e ( μ g, yh)-E1 = ΧΘ(gdy gE1, μ h) θ ( μ gE1, μ h) = X Θ (gd, μ h) θ (μ gE1, μ h) θ (μ gE1, μ h) - 1 = Θ (g,μ h) dX。在上述展开式中，利用X= B (μ / \ μ / 2)1/r 2Θ (μ/ S μ hr = B (gd μ gE1,yhE2)1/E2e (gVgE1, μ。—1，且B (gVgE1, μhE2) 1 /E2 = X Θ (gVgE1, μh)这种性质。该性质基于&、民、R/及R2'为随机数。在此，发明者发现，将Sx (I)的表现值表述为Θ (g，μ,)1^，且将Sx (d)的表现值表述为Θ (g，yh)dx2，成为Sx (I)的表现值的d次方=Sx (d)的表现值即(Θ (g, yh)SOd= Θ (g, μ h) dX2的理由在X1及X2为群F的单位元6{时的可能性非常高。在此，省略其证明。在X1为群F的单位元ef时,成为Sx (I)的表现值=Θ (g, μ h) 1X1 = Θ (g,μ h)。上述实施方式的代理计算系统利用该可随机化抽样器的性质。步骤Sll' 步骤Slll'的处理与Sx (I)的表现值Θ (g, U1^1X1的计算对应。实际上，不计算Sx(I)的表现值自身，但当利用通过同处理而得到的(r2，Zl V ^2Mfz1V -1:11:2进行I / r2次方时，成为(Zlv-My/e = "、-n，且成为&(1)的表现值θ (g，yh) 1X1O同样，步骤S112' 步骤S123'的处理与Sx (Cl1)的表现值Θ (g，yh)dlx2的计算对应。另夕卜，步骤S124'的处理与是否SSx (I)的表现值的(I1次方=Sx Cd1)即(Θ (g，= θ (g, μ h) dlX2的判定对应。理由是，步骤S124使用的判定条件(W1) A Ct2S2S1-1)为(wl ) A ( t2S2Si ~ 1 ) = W2^ ( W]1/Sl ) t2 =
W2lis2O ( Zjl7r2V"11 ) dl = Z21/r5V_r40 ( Θ ( g, Ph ) 1Xi ) dl = Θ ( g，Ph ) dlX2^Sx
(I)的表现值的(I1次方=Sx Cd1)的表现值。在此，由定义可知，S1 = I^w1 = Z1 V ^rlr2^t2
_ I___ τ — r4r5
一屯、S2 — r5、W2 — Z2 V ο另外，步骤S125'的σ及V'与Θ (g，yh)对应。理由是，如上所述，在Sx (I)的表现值的(I1次方=Sx Cd1)的表现值时，为V ' 1/0 = W117"1 = Z11 / r2 V ^rl = Θ (g,μ h) 1X1 = Θ (g, μ h)。
《关于成为(W3)- (S3-1) = θ (g，h)的理由》当设R1, R2, R/及R2'为随机数、设计算装置利用gK1&hdyhK2进行计算的计算结果为B (gE1, hdyhE2)(当将计算装置返送到委托装置的计算结果设为ζ时，为ζ = B (gE1,hS,2))，且将在群F中具有数值的随机变量X定义为X = B Cgr μ / 2)' /r 1 Θ (g，μ/2) —1时，Sx (d)=z(1/K1) V' —K2成为与Θ (g，h)有关的误差X的可随机化抽样器。理由是，SX(d)=z(1/K1) V' —K2 = B (gK1，hdyhK2)1/K10 (g, yh)-R2 = ΧΘ (g、hdμ hE2) Θ (g, μ hE2) = X Θ (g、hd) Θ (g, μ hE2) Θ (g, μ hE2) = Θ (g，h) dX。在上述展开式中，利用X= B (gr2)1/κ, (g, μ / 2K1 = B W)1/Ε1Θ (g'hSf)-1，且 B (gK1，hVhK2)1/K1 = X0 (g、hVhK2)这种性质。该性质基于 R1,R2, R1'及V为随机数。在此，发明者发现，将Sx (I)的表现值表述SSx (I)= Θ (gd)、，将Sx (d)的表现值表述为Sx (d)= Θ (g, h) dX2,成为Sx (I)的表现值的d次方=Sx (d)即(Θ (g,h) 1X1) d = Θ (g，h) dX2的理由在X1及X2为群F的单位元ef时的可能性非常高。在此,省略其证明。在X1为群F的单位元ef时,成为Sx (I)的表现值=Θ (g^)^! = Θ (g，h)。上述实施方式的代理计算系统利用该可随机化抽样器的性质。步骤S21' 步骤S211'的处理与Sx (I)的表现值Θ (g，h) 1X1的计算对应。实际上，不计算Sx (I)的表现值自身，但当利用通过同处理而得到的(r6，Z3V ' _rf。将Z3V'—―进行丄/^次方时’成为匕一 -r6r7)1/r6 = z31/r6v/ _〃，且成为Sx (I)的表现值Θ (gd)、。同样，步骤S212, 步骤S223,的处理与Sx (d2)的表现值Θ (g,h)d2x2的计算对应。另外，步骤S224'的处理与是否为Sx (I)的表现值的d2次方=Sx (d2)的表现值即(Θ (g, h)^)112 = Θ (g，h) d2X2的判定对应。理由是，步骤S224'使用的判定条件(W3 ) A ( ttS4S3_1 ) = W4 为(W3 ) Λ ( t4S4S3 _1 ) = W4^ ( W〗1
/s3 \ t4 I /s4^ V / I /r6, t -r7 \ d2 I /r9 / -TIOaa / a / i \ I \ d2 r\ ( ^
)=W4 o I V J = Z4 V ^ (Θ (g, hi X1) = Θ (g,
h ) d2X2OSx ( I )的表现值的d2次方=Sx (d2)的表现值。在此，由定义可知，s3 = r6、W3
=Z3V ' —r6r7、t4 = d2、S4 = r9> W4 = Z4V ' ^r9rl0o另外，步骤S225,的(W3)八(sf1)与Θ (g，h)对应。理由是，如上所述，在Sx (I)的表现值的 d2 次方=Sx (d2)的表现值时，为(W3) a (s3-i) = (Z3 V ' ^r6r7) Cr6-1)=
z31/r6v' -r7= Θ (g, h) 1X1 = Θ (g，h)。[第五实施方式]
第五实施方式的代理计算系统在步骤S13'、步骤SllO'及步骤Slll'上与第四实施方式的代理计算系统不同，其他部分与第四实施方式的代理计算系统同样。下面，以与第四实施方式不同的部分为中心进行说明。第一输入信息计算部13'对不是由gl = μ grlg定义而是由gl = grl定义的第一输入信息进行计算(步骤S13')。第一列表信息计算部15'不是利用Z1 V 而是利用随机数Γι及随机数r2来计算rir2，且将其计算结果发送到第一列表存储部16'(步骤SllO')。在第一列表存储部16'不是存储信息组(r2，Z1 v _&2)，而是存储由计算出的和从计算装置2'接收到的21 e F构成的信息组(rir2，Zl)(步骤Slll')。 在第四实施方式的步骤SllO'中，需要进行Z1 V ^1r2这种群F的幂运算，但在第五实施方式的步骤SllO'中，进行的是rir2的计算，幂运算的次数减少一次。这样，通过减少 幂运算的次数，能够增大运算的效率。另外，如果在群G、群H中难以进行非自明方根(非自明χ务根，nontrivial root)的计算,贝U安全性不会比第四实施方式低。[第六实施方式]第六实施方式的代理计算系统在步骤S24'、步骤S210'及步骤S211'上与第四实施方式的代理计算系统不同，其他部分与第四实施方式的代理计算系统同样。下面，以与第四实施方式不同的部分为中心进行说明。第六输入信息计算部34'对不是由h3 = μ f ° h定义而是由h3 = hr7定义的第六输入信息h3进行计算(步骤S24')。第三列表信息计算部35'不是利用Z3 V ' 而是利用随机数r6及随机数r7来计算r6r7 (步骤S210')。在第三列表存储部36'不是存储信息组(r6，Z3 V' _—，而是存储由计算出的r6r7和从计算装置2'接收到的23 e F构成的信息组(r6r7，z3)(步骤S211')。在第四实施方式的步骤S210'中，需要进行z3v' _&7这种群F的幂运算，但在第六实施方式的步骤S210'中，进行的是r6r7的计算，幂运算的次数减少一次。这样，通过减少幂运算的次数，能够增大运算的效率。如果在群G、群H中难以进行非自明方根的计算，则安全性不会比第四实施方式低。[第七实施方式]第七实施方式的代理计算系统在步骤S125'及步骤S214'上与第四实施方式的代理计算系统不同，其他部分与第四实施方式的代理计算系统同样。下面，以与第四实施方式不同的部分为中心进行说明。第一判定部28'在满足上述关系的情况下，将tlS2代入σ，将W2代入V '(步骤S125/ )。第十随机数生成部42'利用随机数r9，计算一ι^1，并设为r1(l (步骤S214')。这样，通过变更V'的定义并将σ设为对于计算装置2'来说难以推测的随机数，来增大安全性。另外，通过利用随机数r9计算随机数r1(l，能够减少生成随机数的次数。也认为第八输入信息h4 = yhrl0ohd2的杂乱性因由随机数r9规定随机数r1(l而下降，且安全性受损，但第八输入信息h4= Uhlrlt^hd2不仅由随机数r1(l干扰，而且进一步由σ干扰，因此安全性不会受损。另外，在第七实施方式中，也可以如下那样进一步将步骤S22'及步骤S21T变更。第七随机数生成部32'利用随机数r6计算一 re—1，并设为r7 (步骤S22')。
在第三列表存储部36'存储由I和上述计算出的Z3 V ' 构成的信息组(1，Z3V ' _r6r7)(步骤 S211')。这样，通过利用随机数r6计算随机数r7，能够减少生成随机数的次数。如果在群G、群H中难以进行非自明方根的计算，则安全性不会比第四实施方式低。[第八实施方式]第八实施方式的代理计算系统在步骤S113'上与第四实施方式的代理计算系统不同，其他部分与第四实施方式的代理计算系统同样。下面，以与第四实施方式不同的部分为中心进行说明。首先，在步骤S113'之前，第五随机数生成部22'生成随机数r5 (步骤S114')。第四随机数生成部21'利用随机数r5计算一 ι^1，并设为r4 (步骤S113')。这样，通过利用随机数r5计算随机数r4，能够减少生成随机数的次数。关于群H的任意元h，如果难以计算成为g e G且Θ (g，h)= V的值，则安全性不会比第四实施方式低。[第九实施方式]第九实施方式的代理计算系统在委托装置Γ进一步包含图12虚线所示的事前计算部29'上，且在步骤S115'上与第四实施方式的代理计算系统不同，其他部分与第四实施方式的代理计算系统同样。下面，以与第四实施方式不同的部分为中心进行说明。事前计算部29'利用第三随机数生成部27'生成的(I1，计算gdl。该处理在步骤S112,之后且在步骤S115'之前进行。第三输入信息计算部23'利用事前计算出的gdl，进行g2 = μ ；4gdl的计算(步骤S115/ )。在步骤S114'中不满足判定条件的情况下，重复进行步骤Sll' 步骤S123'的处理，但在该重复处理中，再次利用事前计算出的gdl。即，第三随机数生成部27'不生成随机数Cl1，第三输入信息计算部23'利用事前计算出的gdl，进行g2 = μ ；4gdl的计算。由此，能够减少生成随机数Cl1的次数，能够迅速地进行g2 = μ ；4gdl的计算。[第十实施方式]第十实施方式的代理计算系统在委托装置Γ进一步包含图13虚线所示的事前计算部49'上且在步骤S216'上与第四实施方式的代理计算系统不同，其他部分与第四实施方式的代理计算系统同样。下面，以与第四实施方式不同的部分为中心进行说明。事前计算部49'利用第八随机数生成部47'生成的d2，计算hd2。该处理在步骤S212/之后且在步骤S216'之前进行。第八输入信息计算部44'利用事前计算出的hd2，进行第八输入信息h4 =的计算(步骤sn6')。在步骤S214'中不满足判定条件的情况下，重复进行步骤S21' 步骤S223'的处理，但在该重复处理中，再次利用事前计算出的hd2。即，第八随机数生成部47'不生成随机数d2，第八输入信息计算部44'利用事前计算出的hd2，进行h4= yhrt°°hd2的计算。由此，能够减少生成随机数d2的次数，能够迅速地进行h4 = μ hrl0ohd2的计算。[第四实施方式 第十实施方式的变形例等]通过第一随机数生成部1Γ、第二随机数生成部12'、第三随机数生成部27'、第四随机数生成部21'、第五随机数生成部22'、第六随机数生成部3Γ、第七随机数生成部32'、第八随机数生成部47'、第九随机数生成部41'及第十随机数生成部42'分别生成均匀随机数，代理计算系统的安全性最高。但是，在要求的安全性的水平不那么高的情况下，第一随机数生成部11'、第二随机数生成部12'、第三随机数生成部27'、第四随机数生成部21'、第五随机数生成部22'、第六随机数生成部31'、第七随机数生成部32'、第八随机数生成部47'、第九随机数生成部41'及第十随机数生成部42'也可以不分别生成均匀随机数，而是生成随机数。 每当在列表L1、列表L2追加信息组时，都可以进行第一判定部28'的处理。例如，在第二列表存储部26'存储有信息组(C^ivz2Vi5)的情况下，也可以在步骤Slll'之后进行步骤S124'的处理。同样，每当在列表L3、列表L4追加信息组时，都可以进行第二判定部48'的处理。第四实施方式 第十实施方式可相互组合。既可以直接进行委托装置Γ的各部间的数据交换，也可以经由未图示的存储部来进行。同样，既可以直接进行计算装置2'的各部间的数据交换，也可以经由未图示的存储部来进行。委托装置I'及计算装置2'分别可由计算机来实现。在这种情况下，该装置应有的各功能的处理内容通过程序来记述。而且，通过由计算机执行该程序，该装置的各处理功能在计算机上实现。记述有该处理内容的程序可记录于计算机可读取的记录介质。另外，在该方式中，通过在计算机上执行规定的程序，来构成这些装置，但也可以硬件地实现这些处理内容中的至少一部分。另外，也可以将第一实施方式 第三实施方式和第四实施方式 第十实施方式组合。例如，如图17所示，第一实施方式 第三实施方式的计算装置2具备第四实施方式 第十实施方式的委托装置P ，包含该委托装置P的计算装置2也可以与第四实施方式 第十实施方式所述的同样地，利用计算装置2,，进行函数f的计算。具体而言，计算装置2为了计算需要计算的函数f (X)，利用计算装置2'计算对应的映射Θ (g，h)的值。与函数f (X)对应的映射Θ (g，h)是对被赋予的函数f及X输出与函数f (X)的值相同的值的映射Θ (g，h)。关于某元he H,在存在f (χ) = Θ (X，h)这种关系的情况下，与f (χ)对应的映射Θ成为Θ (x，h)。例如，在参考文献I记载的Boneh — Franklin方式的基于ID密码中，将某一定的ID相关的解码函数设为f。在该方式的基于ID密码中，由形成椭圆曲线的点的有限群G、H和对τ :GXH —F构成。将Q设为G的元。将基于ID密码的密钥发行中心的密钥设为S，将公开密钥设为P = sQ。基于ID密码的公共参数为群G、H的记述、对τ的记述、Q及P。〔参考文献 l〕Dan Boneh, Matt Franklin, “Identity — Based Encryption fromthe weil Pairing”，CRYPTO 2001，LNCS 2139, pp. 213 - 229, 2001.密钥的发行如下那样进行。密钥发行中心就对应于ID而规定的H的元Qid而言，计算Pid = sQid并通知给ID的保持者。Pid为ID的保持者的密钥。此时,解码函数f :G — F由 f (X) = τ (X，Pid)定义。密文的作成、密文的解码如下那样进行。为了将明文m关于某ID加密，生成随机数r，计算(Q'm (十)H ( τ (Ρ% QID)))，将此设为密文(C1, C2)。为了解码，通过对密文(C1,C2)计算C2 (十)H (f (C1)),得到明文。其中，在此，H为哈希函数，(+)为逻辑异或。在这种Boneh — Franklin方式的基于ID密码中，与函数f (X)对应的映射Θ利用例如对τ来定义。SP, f (X)= τ (x，PID)。计算装置2为IC卡及便携电话，难以进行秘密信息的提取，但在限定计算能力的 情况下，这样将委托装置及计算装置多重组合是有有益的。本发明不局限于上述的实施方式，在不脱离本发明精神的的范围内，可适当变更。
权利要求
1.ー种代理计算系统，其特征在干， 设G、H为循环群，设f为将群H的元X映射到群G的函数，设X1. X2为在群G中具有数值的随机变量，设随机变量X1的表现值为X1，设随机变量X2的表现值为x2， 所述代理计算系统包含 整数计算部，利用互素的两个自然数a、b，计算满足a' a + b' b = I的关系的整数a,ヽ b,； 第一可随机数化抽样器，能够计算f (X) bX1，并将其计算结果设为U ； 第一幂计算部，计算U' =Ua; 第二可随机数化抽样器，能够计算f (x) aX2,并将其计算结果设为V ; 第二幂计算部,计算V' =Vb; 判定部，判定是否为u, =V,;以及 最終计算部，在判定为U'=ゲ的情况下，计算Ub' Va/。
2.如权利要求I所述的代理计算系统，其特征在干， 还包含抽样器，所述抽样器能够计算f (X)X3，如果a = 1，则代替所述第二可随机数化抽样器，将其计算结果设为所述V，如果b = 1，则代替所述第一可随机数化抽样器，将其计算结果设为所述U，其中设X3为在群G中具有数值的随机变量，设随机变量X3的表现值为Λ3 °
3.如权利要求I所述的代理计算系统，其特征在干， 设所述f为同态映射，设群H的生成元为μ h，设群H的位数为Kh，设V =f (yh)， 所述第一可随机数化抽样器包含生成O以上不足Kh的整数的随机数Γι的第一随机数生成部、计算第一输入信息UhlrlXb的第一输入信息计算部、能够利用所述第一输入信息μ hrlxb计算f ( μ J1Xb)且将其计算结果设为第一输出信息Z1的第一输出信息计算部、计算Z1V-1并将其计算结果设为所述U的第一计算部， 所述第二可随机数化抽样器包含生成O以上不足Kh的整数的随机数r2的第二随机数生成部、计算第二输入信息Uhlr2Xa的第二输入信息计算部、能够利用所述第二输入信息μ hr2Xa计算f ( μ J2Xa)且将其计算结果设为第二输出信息Z2的第二输出信息计算部、计算Z2V^2并将其计算结果设为所述V的第二计算部。
4.如权利要求3所述的代理计算系统，其特征在干， 还包含抽样器，所述抽样器包含生成O以上不足Kh的整数的随机数r3的第三随机数生成部；计算第三输入信息f3的第三输入信息计算部；能够利用所述第三输入信息f3计算f (Xlr3)且将其计算结果设为第三输出信息Z3的第三输出信息计算部；以及第三计算部，所述第三计算部计算z31/l3，如果a = 1，则代替所述第二可随机数化抽样器，将其计算结果设为所述V，如果b = 1，则代替所述第一可随机数化抽样器，将其计算结果设为所述U。
5.如权利要求I所述的代理计算系统，其特征在干， 设群H = GX G，设所述f为同态映射，设群G的生成元为μ g，设群G的位数为Ke，设X= Cc1, c2)，设(V，W)为群 H 的元，设 f (V,ff) = Y， 所述第一可随机数化抽样器包含生成O以上不足Ke的整数的随机数r4的第四随机数生成部、生成O以上不足Ke的整数的随机数r5的第五随机数生成部、计算第四输入信息C1bVr4 μ /5的第四输入信息计算部、计算第五输入信息C2bWrt的第五输入信息计算部、能够利用所述第四输入信息C1W /5及所述第五输入信息C2bWrt计算f (C1bVr4U/5, C2bWr4)且将其计算结果设为第四输出信息Z4的第四输出信息计算部、计算z4Y—1:4 μ g_ri并将其计算结果设为所述u的第四计算部， 所述第二可随机数化抽样器包含生成O以上不足Ke的整数的随机数r6的第六随机数生成部、生成O以上不足Ke的整数的随机数r7的第七随机数生成部、计算第六输入信息C1aVr6 μ /7的第六输入信息计算部、计算第七输入信息C2aWrf的第七输入信息计算部、能够利用所述第六输入信息C1aViV 及所述第七输入信息C2aWrf计算f (C1aVr6U/7, C2aWr6)且将其计算结果设为第五输出信息Z5的第五输出信息计算部、计算Z5Frii μ 并将其计算结果设为所述V的第五计算部。
6.ー种代理计算方法，其特征在干， 设G、H为循环群，设f为将群H的元X映射到群G的函数，设X1. X2为在群G中具有数值的随机变量，设随机变量X1的表现值为X1，设随机变量X2的表现值为x2， 所述代理计算方法包含 整数计算步骤，整数计算部利用互素的两个自然数a、b，计算满足a' a + b' b = l的关系的整数a'、b'； 第一可随机数化抽样步骤，第一可随机数化抽样器能够计算f (X)bX1，并将其计算结果设为u ； 第一幂计算步骤,第一幂计算部计算U' = Ua ; 第二可随机数化抽样步骤，第二可随机数化抽样器能够计算f (X)aX2，并将其计算结果设为V ; 第二幂计算步骤,第二幂计算部计算V' = Vb ; 判定步骤，判定部判定是否为u' =Y';以及 最终计算步骤，最終计算部在判定为U'=ゲ的情况下，计算Ub' V-。
7.一种委托装置，其特征在干， 设G、H为循环群，设f为将群H的元X映射到群G的函数，设X1. X2为在群G中具有数值的随机变量，设随机变量X1的表现值为X1，设随机变量X2的表现值为x2， 所述委托装置包含 整数计算部，利用互素的两个自然数a、b，计算满足a' a + b' b = I的关系的整数a,ヽ b,； 第一幂计算部，利用能够计算f (χ)\的第一可随机数化抽样器的计算结果u，计算Ui =ua; 第二幂计算部，利用能够计算f (X) aX2的第二可随机数化抽样器的计算结果V，计算V1 = Vb ； 判定部，判定是否为u, =V,;以及 最終计算部，在判定为u' = Y'的情况下，计算Ub' Va /。
8.—种代理计算系统，利用委托装置委托于计算装置的计算结果，计算Θ (g，h)，其特征在干， 设G、H及F为循环群，设映射Θ :GXH —F为双同态映射，设g为群G的元，设h为群H的元，设Ke为群G的位数，设Kh为群H的位数，设μ g为群G的生成元，设μ h为群H的生成元,设V = Θ ( μ g, μ g),设k为自然数的安全參数,设K = 2k, 所述委托装置包含 第一随机数生成部，生成O以上不足Ke的整数的随机数Γι ； 第二随机数生成部，生成O以上不足Kh的整数的随机数r2 ； 第一输入信息计算部，计算第一输入信息A = μ grlg ; 第二输入信息计算部，计算第二输入信息h = Uhr2； 第一列表信息计算部，利用从所述计算装置接收到的Z1 e F，计算Z1 V -rlr2 ； 第一列表存储部，对由所述随机数r2和所述计算出的Z1 v-&2构成的信息组(r2，Z1 V^rlr2)进行存储； 第三随机数生成部，生成O以上不足K的整数的均匀随机数即Cl1 ； 第四随机数生成部，生成O以上不足Ke的整数的均匀随机数即r4 ； 第五随机数生成部，生成O以上不足Kh的整数的均匀随机数即r5 ； 第三输入信息计算部，计算第三输入信息g2 = μ gr4gdl ； 第四输入信息计算部，计算第四输入信息h2= yhr5； 第二列表信息计算部，利用从所述计算装置接收到的Z2 e F，计算Z2 V -； 第二列表存储部，对由所述Cl1、所述1*5和所述计算出的z2v_rtri构成的信息组(も，r5,z2v_riri)进行存储； 第一判定部，设从所述第一列表存储部读入的信息组的第一成分为S1，设第二成分为W1，且设从所述第二列表存储部读入的信息组的第一成分为t2，设第二成分为S2，设第三成分为W2,判定这些信息组是否满足(W1)へCt2S2S1-1) = W2的关系,在满足该关系的情况下，将S1代入σ，将W1代入V ,； 第六随机数生成部，生成O以上不足Ke的整数的均匀随机数即r6 ； 第七随机数生成部，生成O以上不足Kh的整数的均匀随机数即r7 ； 第五输入信息计算部，计算第五输入信息g3 = gr6 ; 第六输入信息计算部，计算第六输入信息h3 = μ J7I ; 第三列表信息计算部，利用从所述计算装置接收到的Z3 e F，计算Z3 V ' ； 第三列表存储部，对由所述1"6和所述计算出的Z3V ' 构成的信息组(re，Z3V' _rf,进行存储； 第八随机数生成部，生成O以上不足K的整数的均匀随机数即d2 ； 第九随机数生成部，生成O以上不足Ke的整数的均匀随机数即r9 ； 第十随机数生成部，生成O以上不足Kh的整数的均匀随机数即r1(l ； 第七输入信息计算部，计算第七输入信息g4= μ/9； 第八输入信息计算部，计算第八输入信息h4 = μ hrl0ohd2 ； 第四列表信息计算部，利用从所述计算装置接收到的Z4 e F，计算Z4 V ' -r9r10 ； 第四列表存储部，对由所述d2、所述r9和所述计算出的Z4 V，-r9r10构成的信息组(d2，r9, z4 V ^进行存储；以及 第二判定部，设从所述第三列表存储部读入的信息组的第一成分为s3，设第二成分为W3，且设从所述第四列表存储部读入的信息组的第一成分为t4，设第二成分为S4，设第三成 分为W4,判定这些信息组是否满足(W3)へCt4S4S3-1) = W4的关系,在满足该关系的情况下，将(W3)へCs3-1)输出， 所述计算装置包含 第一输出信息计算部，能够利用从所述委托装置接收到的gl及hi，计算Θ (Sph1)，将其计算结果设为所述Z1而输出； 第二输出信息计算部，能够利用从所述委托装置接收到的g2及h2，计算Θ (g2，h2)，将其计算结果设为所述Z2而输出； 第三输出信息计算部，能够利用从所述委托装置接收到的g3及h3，计算Θ (g3，h3)，将其计算结果设为所述Z3而输出；以及 第四输出信息计算部，能够利用从所述委托装置接收到的g4及h4，计算Θ (g4，h4)，将其计算结果设为所述Z4而输出。
9.如权利要求8所述的代理计算系统，其特征在干， 所述第一输入信息计算部计算第一输入信息gl = grl, 所述第一列表信息计算部利用所述^及所述r2，计算rir2， 在所述第一列表存储部存储由所述计算出的^r2和从所述计算装置接收到的Z1 e F构成的信息组(Ar2, Z1X
10.如权利要求8或9所述的代理计算系统，其特征在干， 所述第六输入信息计算部计算第六输入信息h3 = hr7, 所述第三列表信息计算部利用所述r6及所述r7，计算r6r7， 在所述第三列表存储部存储由所述计算出的r6r7和从所述计算装置接收到的Z3 e F构成的信息组(r6r7, z3)。
11.如权利要求8 10中的任一项所述的代理计算系统，其特征在干， 所述第一判定部在满足所述关系的情况下，将tlS2代入0，将《2代入V'， 所述第十随机数生成部利用所述r9，计算ー iV1，并设为r1(l。
12.如权利要求11所述的代理计算系统，其特征在干， 所述第七随机数生成部利用所述r6，计算ー IV1，并设为r7， 在所述第三列表存储部存储由I和所述计算出的Z3 V ' 构成的信息组(I，Z3 V ' -r6r7、
13.如权利要求8 12中的任一项所述的代理计算系统，其特征在干， 所述第四随机数生成部利用所述r5，计算ー r,，并设为r4。
14.如权利要求8 13中的任一项所述的代理计算系统，其特征在干， 还包含利用所述Cl1计算gdl的事前计算部， 所述第三输入信息计算部利用所述事前计算出的gdl，进行所述g2的计算。
15.如权利要求8 14中的任一项所述的代理计算系统，其特征在干， 还包含利用所述d2计算hd2的事前计算部， 所述第八输入信息计算部利用所述事前计算出的hd2，进行所述h4的计算。
16.ー种代理计算方法，利用委托装置委托于计算装置的计算结果，计算Θ (g，h)，其特征在干， 设G、H及F为循环群，设映射Θ :GXH —F为双同态映射，设g为群G的元，设h为群H的元，设Ke为群G的位数，设Kh为群H的位数，设μ g为群G的生成元，设μ h为群H的生成元，设V = Θ ( μ g, μ g),设k为整数的安全參数,设K = 2k, 所述代理计算方法包含 第一随机数生成步骤，所述委托装置的第一随机数生成部生成O以上不足Ke的整数的随机数巧； 第二随机数生成步骤，所述委托装置的第二随机数生成部生成O以上不足Kh的整数的随机数r2 ； 第一输入信息计算步骤，所述委托装置的第一输入信息计算部计算第一输入信息gl =μ grlg ； 第二输入信息计算步骤，所述委托装置的第二输入信息计算部计算第二输入信息h =.11 r2V- h ； 第一输出信息计算步骤，所述计算装置的第一输出信息计算部能够利用从所述委托装置接收到的gl及hi，计算Θ (gl，hi)，将其计算结果设为所述Z1而输出； 第一列表信息计算步骤，所述委托装置的第一列表信息计算部利用从所述计算装置接收到的Z1 e F，计算Zlv_&2; 在所述委托装置的第一列表存储部存储由所述随机数r2和所述计算出的Z1 V 构成的信息组(r2，Zlv_—)的步骤； 第三随机数生成步骤，所述委托装置的第三随机数生成部生成O以上不足K的整数的均匀随机数即Cl1 ； 四随机数生成步骤，所述委托装置的第四随机数生成部生成O以上不足Ke的整数的均匀随机数即r4; 第五随机数生成步骤，所述委托装置的第五随机数生成部生成O以上不足Kh的整数的均匀随机数即r5; 第三输入信息计算步骤，所述委托装置的第三输入信息计算部计算第三输入信息g2 =μ gr4gdl ； 第四输入信息计算步骤，所述委托装置的第四输入信息计算部计算第四输入信息h2 =yhr5 ； 第二输出信息计算步骤，所述计算装置的第二输出信息计算部能够利用从所述委托装置接收到的g2及h2，计算Θ (g2，h2)，将其计算结果设为所述22而输出； 第二列表信息计算步骤，所述委托装置的第二列表信息计算部利用从所述计算装置接收到的z2 e F，计算z2v_rtrf; 在所述委托装置的第二列表存储部存储由所述Cl1、所述r5和所述计算出的Z2 V _*5构成的信息组(も，r5, z2y-lil5)的步骤； 第一判定步骤，所述委托装置的第一判定部设从所述第一列表存储部读入的信息组的第一成分为S1、第二成分为W1,且设从所述第二列表存储部读入的信息组的第一成分为t2、第二成分为S2、第三成分为W2,判定这些信息组是否满足(W1)へCt2S2S1-1) = W2的关系,在满足该关系的情况下，将S1代入O，将W1代入V '； 第六随机数生成步骤，所述委托装置的第六随机数生成部生成O以上不足Ke的整数的均匀随机数即r6 ； 第七随机数生成步骤，所述委托装置的第七随机数生成部生成O以上不足Kh的整数的均匀随机数即r7; 第五输入信息计算步骤，所述委托装置的第五输入信息计算部计算第五输入信息g3 =r6 . 第六输入信息计算步骤，所述委托装置的第六输入信息计算部计算第六输入信息h3 =yhr70h； 第三输出信息计算步骤，所述计算装置的第三输出信息计算部能够利用从所述委托装置接收到的g3及h3，计算θ (g3，h3)，将其计算结果设为所述23而输出； 第三列表信息计算步骤，所述委托装置的第三列表信息计算部利用从所述计算装置接收到的Z3 e F，计算Z3 V' -rfr7 ； 在所述委托装置的第三列表存储部存储由所述r6和所述计算出的Z3 V ' 构成的信息组(r6，Z3 V' _*7)的步骤； 第八随机数生成步骤，所述委托装置的第八随机数生成部生成O以上不足K的整数的均匀随机数即d2 ； 第九随机数生成步骤，所述委托装置的第九随机数生成部生成O以上不足Ke的整数的均匀随机数即r9 ； 第十随机数生成步骤，所述委托装置的第十随机数生成部生成O以上不足Kh的整数的均匀随机数即r1(l; 第七输入信息计算步骤，所述委托装置的第七输入信息计算部计算第七输入信息g4 =μ/9 ; 第八输入信息计算步骤，所述委托装置的第八输入信息计算部计算第八输入信息h4 =yhrl0°hd2； 第四输出信息计算步骤，所述计算装置的第四输出信息计算部能够利用从所述委托装置接收到的g4及h4，计算Θ (g4，h4)，将其计算结果设为所述24而输出； 第四列表信息计算步骤，所述委托装置的第四列表信息计算部利用从所述计算装置接收到的Z4 e F，计算Z4 V' -9rl° ； 在所述委托装置的第四列表存储部存储由所述(12、所述1*9和所述计算出的Z4 V ' -r9r10构成的信息组(d2，r9, z4 V ' -r9r10)的步骤；以及 第二判定步骤，所述委托装置的第二判定部设从所述第三列表存储部读入的信息组的第一成分为S3、第二成分为W3，且设从所述第四列表存储部读入的信息组的第一成分为t4、第二成分为S4、第三成分为W4,判定这些信息组是否满足(W3)へCt4S4S3-1) = W4的关系,在满足其关系的情况下，将(W3)へ(S3-1)输出。
17.ー种代理计算系统的委托装置，所述代理计算系统利用委托装置委托于计算装置的计算结果，计算Θ (g，h),其特征在于， 设G、H及F为循环群，设映射Θ :GXH —F为双同态映射，设g为群G的元，设h为群H的元，设Ke为群G的位数，设Kh为群H的位数，设μ g为群G的生成元，设μ h为群H的生成元,设V = θ ( μ g, μ g),设k为自然数的安全參数,设K = 2k, 所述委托装置包含 第一随机数生成部，生成O以上不足Ke的整数的随机数Γι ； 第二随机数生成部，生成O以上不足Kh的整数的随机数r2 ；第一输入信息计算部，计算第一输入信息A = μ grlg ； 第二输入信息计算部，计算第二输入信息hi = yhr2； 第一列表信息计算部，利用从所述计算装置接收到的Z1 e F，计算Z1 V _m2 ； 第一列表存储部，对由所述随机数r2和所述计算出的Z1 v-&2构成的信息组(r2，Z1 V^rlr2)进行存储； 第三随机数生成部，生成O以上不足K的整数的均匀随机数即Cl1 ； 第四随机数生成部，生成O以上不足Ke的整数的均匀随机数即r4 ； 第五随机数生成部，生成O以上不足Kh的整数的均匀随机数即r5 ； 第三输入信息计算部，计算第三输入信息g2 = μ gr4gdl ； 第四输入信息计算部，计算第四输入信息h2= yhr5； 第二列表信息计算部，利用从所述计算装置接收到的Z2 e F，计算Z2 ； 第二列表存储部，对由所述Cl1、所述1*5和所述计算出的z2v_rtri构成的信息组(も，r5,z2v_riri)进行存储； 第一判定部，设从所述第一列表存储部读入的信息组的第一成分为S1，设第二成分为W1，设从所述第二列表存储部读入的信息组的第一成分为t2，设第二成分为S2，设第三成分为W2,判定这些信息组是否满足(W1)へCt2S2S1-1) = W2的关系,在满足该关系的情况下,将S1代入σ，将W1代入V ,； 第六随机数生成部，生成O以上不足Ke的整数的均匀随机数即r6 ； 第七随机数生成部，生成O以上不足Kh的整数的均匀随机数即r7 ； 第五输入信息计算部，计算第五输入信息g3 = gr6 ; 第六输入信息计算部，计算第六输入信息h3 = μ J7I ; 第三列表信息计算部，利用从所述计算装置接收到的Z3 e F，计算Z3 V ' ； 第三列表存储部，对由所述1"6和所述计算出的Z3V ' 构成的信息组(re，Z3V' _rf,进行存储； 第八随机数生成部，生成O以上不足K的整数的均匀随机数即d2 ； 第九随机数生成部，生成O以上不足Ke的整数的均匀随机数即r9 ； 第十随机数生成部，生成O以上不足Kh的整数的均匀随机数即r1(l ； 第七输入信息计算部，计算第七输入信息g4= μ/9； 第八输入信息计算部，计算第八输入信息h4 = μ hrl0ohd2 ； 第四列表信息计算部，利用从所述计算装置接收到的Z4 e F，计算Z4 V ' -9rl0 ； 第四列表存储部，对由所述d2、所述r9和所述计算出的Z4 V，-r9r10构成的信息组(d2，r9, z4 V ^进行存储；以及 第二判定部，设从所述第三列表存储部读入的信息组的第一成分为s3，设第二成分为W3，设从所述第四列表存储部读入的信息组的第一成分为t4，设第二成分为S4，设第三成分为W4,判定这些信息组是否满足(W3)へCt4S4S3-1) = W4的关系,在满足该关系的情况下,将(W3)へ(S3ベ)输出。
18.—种程序，用于使计算机作为权利要求7或权利要求17的委托装置的各部发挥功倉^:。
19.一种计算机可读取的记录介质，记录有权利要求18的委托装置程序。
全文摘要
本发明利用进行正确的计算的概率低的计算装置进行函数f(x)的计算。设G、H为循环群，设f为将群H的元x映射到群G的函数，设X1、X2为在群G中具有数值的随机变量，设随机变量X1的表现值为x1，设随机变量X2的表现值为x2，整数计算部利用互素的两个自然数a、b，计算满足a′a＋b′b＝1的关系的整数a′、b′。第一可随机数化抽样器，可计算f(x)bx1，将其计算结果设为u。第一幂计算部计算u′＝ua。第二可随机数化抽样器可计算f(x)ax2，将其计算结果设为v。第二幂计算部计算v′＝vb。判定部判定是否为u′＝v′。最终计算部在判定为u′＝v′的情况下，计算ub′va′。
文档编号G09C1/00GK102687184SQ201180005420
公开日2012年9月19日 申请日期2011年1月11日 优先权日2010年1月12日
发明者小林铁太郎, 山本刚 申请人:日本电信电话株式会社
最新回复(0)