秘密分散系统、秘密分散装置、秘密分散方法、秘密分类方法、秘密分散程序

摘要

本发明的秘密分散系统由N个秘密分散装置构成。本发明的秘密分散系统具有片断置换部件和再分散部件。片断置换部件选择小于N的数目的秘密分散装置，且在被选择的秘密分散装置之间生成{1，…，K}→{1，…，K}的双向单射π，并将由被选择的秘密分散装置记录的片断aπ(k)i设为第k个片断（其中，i是表示被选择的秘密分散装置的标号）。再分散部件利用与通过片断置换部件置换后的数值对应的片断进行再分散化，从而求出新的片断。

说明书

技术领域

本发明涉及加密应用技术，特别涉及无需透漏输入数据就进行函数计算 的秘密分散系统、秘密分散装置、秘密分散方法、秘密分类方法、秘密分散 程序。

背景技术

作为无需复原被加密的数值就获得特定的运算结果的方法，有被称为秘 密计算的方法（例如，非专利文献1中记载的方法）。在非专利文献1的方法 中，将数值的片断分散到三个秘密计算装置，无需复原数值，就能够将加减 运算、常数之和、乘法运算、常数倍、逻辑运算（逻辑否、逻辑与、逻辑或、 逻辑异或）、数据格式变换（整数、二进制数）的结果分散保持在三个秘密计 算装置中。

现有技术文献

非专利文献

非专利文献1：千田浩司，五十嵐大，高橋克巳，“効率的な3パーティ 秘匿関数計算の提案とその運用モデルの考察”，第48回情報処理学会研究 報告，CSEC，pp.1-7,2010,3月

发明内容

发明要解决的课题

但是，以往技术存在隐藏了数据的对应关系的情况下无法随机置换多个 数据的课题。本发明的目的在于，提供一种输出无法与被输入的多个数据相 对应的数据的秘密计算技术。

用于解决课题的手段

本发明涉及秘密分散，一般来说，在(k,n)秘密分散中，秘密分散系统具 有两个参数k、n，将想要保密的值分割为n个，在其中收集小于k个也不会 泄露与原来值有关的信息，但如果收集k个以上则能够复原原来的值。本发 明的秘密分散系统由N个秘密分散装置R₁、……、R_N构成。这里，将N设 为3以上的整数，将n设为1以上且N以下的整数，将M设为1以上的整数， 将m设为1以上且M以下的整数，将K设为2以上的整数，将k设为1以 上且K以下的整数，将数值A₁⁽¹⁾、……、A_K⁽¹⁾、……、A₁^(M)、……、A_K^(M)设为由各秘密分散装置分散记录片断的K×M个数值，将数值A_k⁽¹⁾、……、 A_k^(M)设为相关联的第k个数值组，将a_kn^(m)设为由第n个秘密分散装置记录的 数值A_k^(m)的片断。本发明的秘密分散系统具有选择部件、片断置换部件以及 再分散部件。选择部件选择2以上且小于N的数目的秘密分散装置。片断置 换部件在被选择的秘密分散装置之间生成{1，…，K}→{1，…，K}的双向单 射π，将被选择的秘密分散装置R_i（其中，i是表示被选择的秘密分散装置的 标号）记录的相关联的第π(k)个数值组的片断a_π(k)i⁽¹⁾、……、a_π(k)i^(M)设为分 别相关联的第k个数值组的片断。再分散部件利用与由所述片断置换部件置 换后的数值A_π(k)⁽¹⁾、……、A_π(k)^(M)对应的片断a_π(k)i⁽¹⁾、……、a_π(k)i^(M)进行再分 散化后求出新的片断b_k1⁽¹⁾、……、b_kN⁽¹⁾、……、b_k1^(M)、……、b_kN^(M)（以下， 将其称为“再分散化”）。另外，在维持相关联的数值组的对应关系的情况下 进行数值组的再分散化时，利用相同的双向单射π而置换相关联的数值组的 各数值的片断即可。

此外，本发明的秘密分散系统还可以具有初始信息分散部件、初始乘法 运算部件、确认分散部件、确认乘法运算部件、篡改检测部件。初始信息分 散部件通过秘密计算而求出秘密分散装置R₁、……、R_N均不知道的K个数 值P₁、……、P_K各自的片断p_1n、……、p_Kn，并将其记录在秘密分散装置R_n。 初始乘法运算部件，在秘密分散装置R₁、……、R_N中，通过秘密计算而求出 S_k=P_k×A_k⁽¹⁾的数值S_k的片断(s_k31,s_k12)、(s_k12,s_k23)、(s_k23,s_k31)，并将其分散记录 在秘密分散装置R₁、……、R_N中。确认分散部件针对k=1～K，通过秘密计算 而生成Q_k=P_π(k)的数值Q_k的片断q_k1、……、q_kN，并将其分散记录在秘密分 散装置R₁、……、R_N中。确认乘法运算部件在秘密分散装置R₁、……、R_N中通过秘密计算而求出T_k=Q_k×B_k⁽¹⁾的数值T_k的片断t_k1、……、t_kN，并将其分 散记录在秘密分散装置R₁、……、R_N中。篡改检测部件针对k=1～K，确认 T_k=S_π(k)的情况。

例如，如果是由三个秘密分散装置构成的情况，则将第k个相关联的数 值组的第m个数值A_k^(m)=a_kαβ^(m)+a_kβγ^(m)+a_kγα^(m)（其中，(α,β,γ)为（1,2,3）和(2,3,1) 和(3,1,2)的任一个组合）的三个片断设为(a_kγα^(m),a_kαβ^(m))和(a_kαβ^(m),a_kβγ^(m))和 (a_kβγ^(m),a_kγα^(m))。当秘密分散装置作为第1秘密分散装置而被选择时，将记录的 片断设为a_k1^(m)=(a_k31^(m),a_k12^(m))，当作为第2秘密分散装置而被选择时，将记录 的片断设为a_k2^(m)=(a_k12^(m),a_k23^(m))，当作为第3秘密分散装置而被选择时，记录 的片断设为a_k3^(m)=(a_k23^(m),a_k31^(m))。然后，各秘密分散装置具有片断置换部、第 1随机数生成部、第2随机数生成部、第1计算部、第2计算部、第3计算 部、片断更新部即可。在作为第1秘密分散装置或者第2秘密分散装置而被 选择时，片断置换部生成{1，…，K}→{1，…，K}的双向单射π，将第π(k) 个相关联的数值组的各数值的片断设为第k个相关联的数值组的各数值的片 断。当为第1秘密分散装置时，第1随机数生成部为了相关联的第k个数值 组的片断的再分散化，生成作为随机的值的b_k31⁽¹⁾、……、b_k31^(M)，并将其发 送给第3秘密分散装置。当为第2秘密分散装置时，第2随机数生成部为了 相关联的第k个数值组的片断的再分散化，生成作为随机的值的b_k23⁽¹⁾、……、 b_k23^(M)，并将其发送给第3秘密分散装置。当为第1秘密分散装置时，第1计 算部为了相关联的第k个数值组的片断的再分散化，针对m=1～M计算 x_k^(m)=b_k31^(m)-a_π(k)31^(m)，并将x_k⁽¹⁾、……、x_k^(M)发送给第2秘密分散装置。当为 第2秘密分散装置时，第2计算部为了相关联的第k个数值组的片断的再分 散化，针对m=1～M计算y_k^(m)=b_k23^(m)-a_π(k)23^(m)，并将y_k⁽¹⁾、……、y_k^(M)发送给 第1秘密分散装置。当为第1秘密分散装置或者第2秘密分散装置时，第3 计算部为了相关联的第k个数值组的片断的再分散化，针对m=1～M，计算 b_k12^(m)=a_π(k)12^(m)_-x_k^(m)-y_k^(m)。在为第1秘密分散装置时片断更新部将 (b_k31^(m),b_k12^(m))设为片断b_k1^(m)，当为第2秘密分散装置时片断更新部将 (b_k12^(m),b_k23^(m))设为片断b_k2^(m)，当为第3秘密分散装置时将(b_k23^(m),b_k31^(m))设为 片断b_k3^(m)。另外，在所有的秘密分散装置的片断置换部中，构成秘密分散系 统的片断置换部件。此外，在第1随机数生成部、第2随机数生成部、第1 计算部、第2计算部、第3计算部、片断置换部中，构成秘密分散系统的再 分散部件。

发明效果

根据本发明的秘密分散系统，未被片断置换部选择的秘密分散装置由于 不知道向单射π，因此不知道数值A₁⁽¹⁾、……、A_k⁽¹⁾、……、A₁^(M)、……、 A_K^(M)和数值B₁⁽¹⁾、……、B_k⁽¹⁾、……、B₁^(M)_、……、B_K^(M)之间的对应关系。 通过利用本发明，不增加比较次数就能够在秘密计算上实现快速分类等基于 比较的分类算法。

附图说明

图1是表示实施例1、2的秘密分散系统的功能结构例的图

图2是表示实施例1的秘密分散系统中的秘密分散的处理流程的图。

图3是表示本发明的秘密分散系统中的数值的分类的处理流程的图。

图4是表示快速分类的算法的图。

图5是表示实施例2的秘密分散系统中的秘密分散的处理流程的图。

图6是表示实施例3、4、的秘密分散系统的功能结构例的图。

图7是表示实施例3、4的再分散部的详细的结构的例子的图。

图8是表示实施例3的秘密分散系统中的秘密分散的处理流程的图。

图9是表示实施例4的篡改检测部的详细的结构的图。

图10是表示实施例4的秘密分散系统中秘密分散的处理流程的图。

具体实施方式

以下，详细说明本发明的实施方式。另外，对具有相同功能的结构部赋 予相同标号，省略重复说明。

【实施例1】

在用于解决课题的部件中，将数值A₁⁽¹⁾、……、A_K⁽¹⁾、……、A₁^(M)、…… A_K^(M)设为由各秘密分散装置分散片断而记录的K×M个数值，将数值 A_k⁽¹⁾、……、A_k^(M)设为相关联的第k个数值组，将a_kn^(m)设为由第n个秘密分 散装置记录的数值A_k^(m)的片断，从而进行说明。在本实施例中，首先为了有 助于本发明的理解，说明M=1的情况，此后说明M不限定于1的情况。此 外，在M=1的情况下的说明中，将A_k⁽¹⁾表现为A_k，将a_kn⁽¹⁾表现为a_kn。

[限定改组（shuffle）]

图1表示实施例1的秘密分散系统的功能结构例。图2表示实施例1的 秘密分散系统中的秘密分散的处理流程。本实施例的秘密分散系统由连接到 网络1000上的N个（N是3以上的整数，n是1以上N以下的整数）秘密分 散装置100₁、……100_N和选择部件105构成。这里，将A₁、……A_K设为由 各秘密分散装置100_n分散片断后记录的K个数值（K是2以上的整数），将 数值A_k设为第k个数值（k是1以上K以下的整数）、将a_kn设为由秘密分散 装置100_n记录的第k个片断。另外，数值A₁、……A_K是想要隐藏的数值组， 例如是成为分类的对象的数值组。作为成为分类的对象的数值组，例如可想 到数值A_k表示各个人的年收入的数值组。选择部件105可以配置在任意的秘 密分散装置的内部，也可以是单独的装置。

本实施例的秘密分散系统具有选择部件、片断置换部件、再分散部件。 此外，秘密分散装置100_n至少具有片断置换部110_n、再分散部120_n以及记录 部190_n。记录部190_n记录片断a_1n、……、a_Kn等。此外，记录部190_n还记录 与自己记录的片断a_kn是数值A_k的第几个片断有关的信息。

选择部件105选择小于N的数目的秘密分散装置（S105）。例如，如果 是在N个片断中收集到N’个就能够复原数值的秘密分散，则片断置换部件只 要选择N’个以上且小于N的秘密分散装置即可。

片断置换部件至少包含片断置换部110₁、……、110_N。此外，在被选择 部件105选择的秘密分散装置100_i（其中，i是表示被选择的秘密分散装置的 标号）的片断置换部110_i之间生成{1，……，K}→{1，……，K}的双向单射 π，并将由所选择的秘密分散装置100_i的记录部190_i记录的片断a_π(k)i设为第 k个片断（S110）。双向单射π也可以是将1～K简单地随机排列的。另外，期 望双向单射π一样是随机排列的，例如利用Fisher-Yates shuffle（参考文献1： Richard Durstenfeld,“Algorithm235:Random permutation”,Communications of  the ACM archive,Volume7,Issue7,1964）等而生成即可。此外，双向单射π 也可以在被选择的秘密分散装置100_i之间生成，也可以由被选择的秘密分散 装置100_i中的一个秘密分散装置生成，从而在被选择的秘密分散装置100_i之 间共享。

再分散部件至少包含再分散部120₁、……、120_N。再分散部件利用与由 片断置换部件置换的数值A_π(k)对应的片断a_π(k)i（被置换为第k个）再分散化 后求出新的片断b_k1、……、b_kN，从而设为数值B_k的片断（S120）。即，成立 A_π(k)=B_k的关系，但未被选择的秘密分散装置不知道双向单射π，因此不知道 A_π(k)=B_k。另外，各秘密分散装置100_n的记录部190_n不仅记录片断b_kn，还记 录用于表示自己记录的第k个片断即片断b_kn是数值B_k的片断的信息。此外， 将数值B₁、……、B_K设为新的数值A₁、……、A_K，并变更由片断置换部件 选择的秘密分散装置的组合，就能够重复该处理（S111、S112）。

根据本发明的秘密分散系统，在被限定的秘密分散装置之间改组片断。 从而，未被片断置换部选择的秘密分散装置由于不知道双向单射π，因此不 知道数值A₁、……、A_K和数值B₁、……、B_K的对应。即，如果希望设为从 特定的秘密分散装置是无法知道数值A₁、……、A_K和数值B₁、……、B_K的 对应的状态，则只要预先决定要选择的秘密分散装置，以便片断置换部不选 择该秘密分散装置即可。此外，一边变更由片断置换部选择的秘密分散装置 一边重复该处理，并设为存在未选择所有的秘密分散装置的情况的状态，则 所有的秘密分散能够获得无法与数值A₁、……、A_K对应的数值B₁、……、 B_K。

[再分散]

在上述的限定改组的说明中，未对再分散详细进行说明。这里，说明再 分散的方法。作为再分散的方法，利用参考文献2（Amir Herzberg,Stanislaw  Jarecki,Hugo Krawczyk,and Moti Yung,“Proactive secret sharing or:How to  cope with perpetual leakage”,In Don Coppersmith,editor,CRYPTO1995, volume963of LNCS,pages339-352.Springer,1995.）的3.3节所示的更新方法、 以及参考文献3（Haiyun Luo and Songwu Lu,“Ubiquitous and robust  authentication services for ad hoc wireless networks”,In UCLA-CSD-TR-200030, 2000）的6.1节所示的再生成方法。在由选择部件105选择的秘密计算装置 之间利用参考文献2的更新方法而生成新的片断，此后，利用参考文献3的 再生成方法生成选择部件105未选择的秘密计算装置的新的片断。

如下表示将参考文献2的更新方法应用于本发明的算法。假设选择部件 105选择了N’个秘密分散装置。然后，设i和j是表示被选择的秘密分散装置 的标号（从1～N中选择的N’个数目中的任一个），且j≠i。此外，设值z₁、……、 z_N是预先决定的值，且被所有的秘密分散装置之间共享。

（1）所有的秘密分散装置100_i生成N’-1个随机数u_i,1’、u_i,2’、……、u_i,N’-1。

（2）所有的秘密分散装置100_i决定Z_i(z):=0+u_i,1z+u_i,2z²+…+u_i,N’-1z^N’-1。

（3）所有的秘密分散装置100_i对被选择的其他的秘密分散装置100_j(有 N’-1个)的所有秘密分散装置100_j分别发送Z_i(z_j)的值。

（4）所有的秘密分散装置100_i将从被选择的其他的秘密分散装置100_j(有 N’-1个)获取的所有的Z_j(z_i)之和设为Z(z_i)，利用被置换的片断a_π(k)i而求出 b_ki=a_π(k)i+Z(z_i)。

接着，如下表示将参考文献3的再生成方法应用于本发明的算法。假设 h是表示未被选择的秘密分散装置的标号（1～N中未被选择的N-N’个数目中 的任一个）。此外，设L_j(z)=(z-z_j)/(z_i-z_j)，且L_i(z)对于所有j的L_j(z)的积。

（5）所有的秘密分散装置100_i对满足i<j的j、以及未被选择的秘密分 散装置100_h的所有的组合，生成随机数v_i,j^(h)。

（6）所有的秘密分散装置100_i对秘密分散装置100_j发送v_i,j^(h)。

（7）所有的秘密分散装置100_i针对所有未被选择的秘密分散装置100_h， 将满足j<i的所有的随机数v_i,j^(h)之和设为V^(h+)，将满足i<j的所有随机数v_i,j^(h)之和设为V^(h-1)，将如下求出w_hi，并对秘密分散装置100_h发送值w_hi。

w_hi=b_kiL_i(z_h)+V^(h+)-V^(h-)

（8）所有的秘密分散装置100_h将接收到的所有的值w_hi之和设为新的片 断b_kh。

如上所述，在（1）～（4）的处理中，所有被选择的秘密分散装置记录新 的片断。在（5）～（8）的处理中，所有未被选择的秘密分散装置记录新的片 断。

另外，如果同时进行（3）和（6）的处理，则能够实现处理的高速化。 具体来说，首先进行（1）、（2）、（5）的处理，然后将（3）和（6）同时进行， 然后进行（4）、（7）、（8）的处理即可。

[分类]

图3表示实施例1的秘密分散系统中的数值的分类的处理流程。通过上 述的方法，获得无法与初始的数值A₁、……、A_K对应的新的数值A₁、……、 A_K（S101）。在还进行分类时，秘密分散装置100_n还具有比较部210_n和交换 部220_n。比较部210₁、……210_N选择两个数值，且通过秘密计算而比较该两 个数值的大小（S210）。

交换部220₁、……、220_N基于各个比较部210₁、……210_N中的比较结果， 更换0组或1组或者多组的数值的片断（S220）。然后，在对于所有数值的分 类处理结束为止，重复步骤S210和S220（比较、交换、组合的变更等必要 的处理）即可（S211、S212）。

步骤S210的比较结果所有的秘密分散装置的下一个处理所需的信息，因 此是所有的秘密分散装置要知道的信息。但是，通过步骤S101由所有的秘密 分散装置对无法与初始的数值A₁、……、A_K对应的新的A₁、……、A_K进行 处理，因此不会漏掉与初始的数值A₁、……、A_K有关的信息。此外，比较结 果又是可根据分类的输出这样的公开信息而计算的信息。因此，在本实施例 的协议整体来看，公开比较结果并非是过于泄露信息。

另外，更具体来说，对分类的部分（步骤S210、S220、S211、S212）应 用图4所示的快速分类的算法即可。此时，也在隐藏A[i]和A[j]的值的情况 下进行比较A[i]和A[j]的处理，并公开比较结果。当该方法的情况下，比较 次数与原来的快速分类相同，平均为O(N·logN)次。此外，除此之外，对能 够由数值的大小比较的处理和更换排列的两个要素的处理构成的分类算法也 能够应用本实施例。

这样，如果利用本实施例的秘密分散系统，则不增加比较次数，通过秘 密计算就能够实现由比较和要素的更换构成的分类算法。

[限定改组的变形例]

接着，说明将M不限定于1的情况。设M是1以上的整数，且m是1 以上M以下的整数。A⁽¹⁾、……、A^(M)是分别持有K个要素的矢量，设 A^(m)=(A₁^(m),…,A_K^(m))。此外，设矢量A⁽¹⁾、……、A^(M)的各要素相关联。换言 之，设A_k⁽¹⁾、……、A_k^(M)为相关联的第k个数值组。在本变形例中，在维持 相关联的数值组的对应关系的状态下对数值组进行限定改组。此外，设a_kn^(m)为秘密分散装置100_n记录的数值A_k^(m)的片断。另外，上述的限定改组相当于 M=1的情况，因此以下的说明是更一般的限定改组。

秘密分散系统的结构与图1相同，秘密分散的处理流程与图2相同。秘 密分散装置100_n至少包含片断置换部110_n、再分散部120_n以及记录部190_n。 其中，各结构部及其处理如下。

记录部190_n记录片断a_1n⁽¹⁾、……、a_Kn⁽¹⁾、……、a_1n^(M)、……、a_Kn^(M)等。 此外，记录部190_n还记录与自己记录的片断a_kn是数值A_k的第几个片断有关 的信息。

选择部件105选择小于N的数目的秘密分散装置（S105）。例如，如果 是收集N个片断中的N’个片断就能够复原数值的秘密分散，则片断置换部件 只要选择N’个以上且小于N的秘密分散装置即可。该处理与限定改组中的处 理相同。

片断置换部件至少包含片断置换部110₁、……、110_N。然后，被选择部 件105选择的秘密分散装置100_i（其中，i是表示被选择的秘密分散装置的标 号）的片断置换部110_i之间生成{1，…，K}→{1，…，K}的双向单射π，并 将由所选择的秘密分散装置100_i的记录部190_i记录的片断a_π(k)i⁽¹⁾、……、a_π(k)i^(M)设为相关联的第k个数值组的片断（S110）。

再分散部件至少包含再分散部120₁、……、120_N。再分散部件利用与由 片断置换部件置换的数值A_π(k)⁽¹⁾、……、A_π(k)^(M)对应的片断a_π(k)i⁽¹⁾、……、a _π(k)i^(M)（被置换为第k个）再分散化后求出新的片断b_k1⁽¹⁾、……、b_kN^(M)、……、 b_k1^(M)、……、b_kN^(M)，从而设为数值B_k⁽¹⁾、……、B_k^(M)的片断（S120）。即， 成立A_π(k)^(m)=B_k^(m)的关系，但未被选择的秘密分散装置不知道双向单射π，因 此不知道A_π(k)^(m)=B_k^(m)。另外，各秘密分散装置100_n的记录部190_n不仅记录 片断b_kn^(m)，还记录用于表示自己记录的第k个片断即片断b_kn^(m)是数值B_k^(m)的片断的信息。此外，将数值B₁⁽¹⁾、……、B_K⁽¹⁾、……、B₁^(M)、……、B_K^(M)设为新的数值A₁⁽¹⁾、……、A_K⁽¹⁾、……、A₁^(M)、……、A_K^(M)，并变更由片断 置换部件选择的秘密分散装置的组合，就能够重复该处理（S111、S112）。

这样，只要利用维持了矢量的各要素的对应关系的限定改组，就能够例 如根据表格形式的数据的秘密分散，以各行作为一个要素（相关联的数值组） 而进行列方向的随机置换。

【实施例2】

[限定改组]

图1也表示实施例2的秘密分散系统的结构。另外，本实施例的秘密分 散装置100_n还具有由虚线表示的结构部。图5表示实施例2的秘密分散系统 中的秘密分散的处理流程。本实施例的秘密分散系统由连接到网络1000上的 N个（N是3以上的整数，n是1以上且N以下的整数）秘密分散装置 100₁、……、100_N和选择部件105构成。这里，将A₁、……、A_K设为由各秘 密分散装置100_n分散记录片断的K个数值（K为2以上的整数），将数值A_k设为第k个数值（k为1以上且K以下的整数），将a_kn设为由秘密分散装置 100_n记录的数值A_k的片断。

本实施例的秘密分散系统包含选择部件105、初始信息分散部件、初始 乘法运算部件、片断置换部件、再分散部件、确认分散部件、确认乘法运算 部件、篡改检测部件。此外，秘密分散装置100_n具有初始信息分散部130_n、 初始乘法运算部件140_n、片断置换部110_n、再分散部120_n、确认分散部150_n、 确认乘法运算部160_n、篡改检测部170_n、记录部190_n。记录部190_n记录片断 a_1n、……、a_Kn等。此外，记录部190_n还记录与自己记录的片断a_kn是数值A_k的第几个片断有关的信息。

选择部件105与实施例1相同。初始信息分散部件由初始信息分散部 130₁、……、130_N构成。此外，被选择部件105选择的秘密计算装置100_i的 初始信息分散部130_i通过秘密计算，求出秘密分散装置100₁、……、100_N均 不知道的K个数值P₁、……、P_K各自的片断p_11’、……、p_K1’、……、p_1n’、……、 p_Kn’、……、p_1N’、……、p_KN，并在秘密分散装置100_n中记录片断p_1n’、……、 p_Kn（S130）。具体来说，从被选择部件105选择的秘密分散装置选定两个以 上的秘密分散装置。然后，基于被选定的秘密分散装置所生成的值，生成哪 个装置都不知道的值的片断即可。例如，选定两个秘密分散装置100_i、100_j（其中，i≠j），且分散记录由秘密分散装置100_i生成的数值的片断、以及由 秘密分散装置100_j生成的数值的片断。然后，只要通过秘密计算而求出该两 个数值之和，并分散记录片断，以便不知道结果，则能够分散记录所有的秘 密分散装置不知道的数值的片断。在该例子中，选定的秘密计算装置是两个， 但也可以是两个以上。

初始乘法运算部件由初始乘法运算部140₁、……、140_N构成。初始乘法 运算部140₁、……、140_N通过秘密计算而求出S_k=P_k×A_k的数值S_k的片断 s_k1、……、s_kN，并分散记录在秘密分散装置100₁、……、100_N（S140）。

片断置换部件和再分散部件与实施例1相同。确认分散部件由确认分散 部150₁、……、150_N构成。确认分散部150₁、……、150_N针对k=1～K通过 秘密计算生成Q_k=P_π(k)的数值Q_k的片断q_k1、……、q_kN，并分散记录在秘密 分散装置100₁、……、100_N（S150）。具体来说，基于在步骤S130中选定的 秘密分散装置生成的值，生成哪个装置都不知道的值的其他的片断。例如， 分散记录在步骤S130中选定的秘密分散装置100_i为了数值P_π(k)而生成的数值 的其他的片断（新的片断）、以及在步骤S130中选定的秘密分散装置100_j为 了数值P_π(k)而生成的数值的其他的片断（新的片断）。然后，通过秘密计算而 求出该两个数值之和，并分散记录片断，以便不知道其结果，则能够分散记 录Q_k=P_π(k)且所有的秘密分散装置不知道的数值的片断。在该例子中，将选定 的秘密计算装置设为2，但与步骤S130相同，也可以是2以上。

确认乘法运算部件由确认乘法运算部160₁、……、160_N构成。确认乘法 运算部160₁、……、160_N通过秘密计算而求出T_k=Q_k×B_k的数值T_k的片断 t_k1、……、t_kN，并分散记录秘密分散装置100₁、……、100_N（S160）。

篡改检测部件由篡改检测部170₁、……、170_N构成。篡改检测部 170₁、……、170_N针对k=1～K确认T_k=S_π(k)的情况（S170）。在t_kn≠s_π(k)n的情 况下，设有篡改并异常结束。此外，只要将数值B₁、……B_K设为新的数值 A₁、……、A_K，并变更片断置换部件中选择的秘密分散装置的组合，就能够 重复该处理（S111、S112）。

根据实施例2的秘密分散系统，可获得与实施例1的秘密分散装置相同 的效果，且还能够确认在隐藏数值A₁、……、A_K与数值B₁、……B_K的对应 关系的处理过程中，不存在对其他的秘密分散装置发送篡改后的值的不正当 的情况。另外，在还进行分类的情况下，秘密分散装置100_n还具有比较部210_n和交换部220_n。具体的分类的处理与实施例1相同。

【实施例3】

在实施例1、2中，将秘密分散装置的数目设为N（N为3以上的整数）。 在实施例3中，构成秘密分散系统的秘密分散装置的数目限定为3，并更具 体地进行说明。

[限定改组]

图6表示实施例3的秘密分散系统的功能结构例。图7表示实施例3的 再分散部的详细的结构的例子。图8表示实施例3的秘密分散系统中的秘密 分散的处理流程。本实施例的秘密分散系统由连接到网络1000上的三个秘密 分散装置100_α、100_β、100_γ和选择部件105构成。这里，将K个数值的第k 个数值设为Ａ_k=ａ_kαβ+ａ_kβγ+ａ_kγα（其中，K是2以上的整数，k是1以上且K 以下的整数，（α,β,γ）是(1,2,3)、(2,3,1)、(3,1,2)中的任一个），该三个片 断设为(α_kγα,α_kαβ)、(α_kαβ,α_kβγ)、(α_kβγ,α_kγα）。另外，选择部件105可以配置在任 一个秘密分散装置的内部，也可以是单独的装置。

本实施例的秘密分散系统具有选择部件105和片断置换部件以及再分散 部件。各秘密分散装置100_n具有片断置换部110_n、再分散部120_n、以及记录 部190_n（其中，n是α、β、γ中的任一个）。记录部190_n记录数值A₁、……、 A_K的片断等。

选择部件105选择两个秘密分散装置。然后，将被选择部件105选择的 秘密分散装置的一个设为第1秘密分散装置100₁，将另一个设为第2秘密分 散装置100₂，将未被选择的秘密分散装置设为第3秘密分散装置100₃（S105）。 这里，将第1秘密分散装置100₁记录的第k个片断设为a_k1=(a_k31,a_k12)，将第2 秘密分散装置100₂记录的第k个片断设为a_k2=(a_k12,a_k23)，将第3秘密分散装 置100₃记录的第k个片断设为a_k3=(a_k23,a_k31)。

片断置换部件至少包含片断置换部110_α、100_β、100_γ。片断置换部件在 第1秘密分散装置100₁或者第2秘密分散装置100₂中生成{1，…，K}→{1，…， K}的双向单射π，将由第1秘密分散装置100₁记录的片断a_π(k)1设为第k个 片断，将第2秘密分散装置100₂记录的片断a_π(k)2设为第k个片断（S110）。 如在实施例1中说明那样，双向单射π可以是将1～K简单随机排列的。另外， 双向单射π期望是同样随机排列的，例如利用Fisher-Yates shuffle等生成即 可。

再分散部件至少包含再分散部120_α、120_β、120_γ。如图7所示那样，再 分散部120_n具有第1随机数生成部121_n、第2随机数生成部122_n、第1计算 部123_n、第2计算部124_n、第3计算部125_n、片断更新部126_n。

第1秘密分散装置100₁的第1随机数生成部121₁为了第k个片断的再分 散化，生成作为随机的数值的b_k31，并将其发送给第3秘密分散装置100₃（S121）。第2秘密分散装置100₂的第2随机数生成部122₂为了第k个片断 的再分散化，生成作为随机的值的b_k23，并将其发送给第3秘密分散装置100₃（S122）。第1秘密分散装置100₁的第1计算部123₁为了第k个片断的再分 散化，计算x_k=b_k31-a_π(k)31，并将其发送给第2秘密分散装置100₂（S123）。

第2秘密分散装置100₂的第2计算部124₂为了第k个片断的再分散化， 计算y_k=b_k23-a_π(k)23，并将其发送给第1秘密分散装置100₁（S124）。第1秘密 分散装置100₁的第3计算部125₁和第2秘密分散装置100₂的第3计算部125₂为了第k个片断的再分散化，分别计算b_k12=a_π(k)12-x_k-y_k（S125）。第1秘密分 散装置100₁的片断更新部126₁将(b_k31,b_k12)设为片断b_k1，第2秘密分散装置 100₂的片断更新部126₂将(b_k12,b_k23)设为片断b_k2，第3秘密分散装置100₃的片 断更新部126₃将(b_k23,b_k31)设为片断b_k3（S126）。另外，各秘密分散装置100_n的记录部190_n不仅记录片断b_kn，还记录用于表示自己记录的第k个片断即片 断b_kn是数值B_k的片断的信息。与实施例1相同，片断b_k1、b_k2、b_k3是数值 B_k的片断。即，步骤S121～S126相当于步骤S120。

此外，若将数值B₁、……B_K设为新的数值A₁、……、A_K，并变更在片 断置换部件中选择的秘密分散装置的组合，则能够重复该处理（S111、S112）。 然后，一边变更片断置换部选择的秘密分散装置一边重复该处理，并设为存 在未选择所有的秘密分散装置的情况的状态，则所有的秘密分散能够获得无 法与数值A₁、……、A_K相关联的数值B₁、……、B_K。在本实施例中，如果 将片断置换部件选择的秘密分散装置选择为{100_α,100_β}、{100_β，100_γ}、 {100_γ,100_α}，则能够成为未选择所有的秘密分散装置的状态。

从而，实施例3的秘密分散系统能够获得与实施例1相同的效果。另外， 当还进行分类的情况下，秘密分散装置100_n还具有比较部210_n和交换部220_n。 具体的分类的处理与实施例1相同。

[限定改组的变形例]

设M为1以上的整数，m为1以上且M以下的整数。A⁽¹⁾、……、A^(M)是分别持有K个要素的矢量，设A^(m)=(A₁^(m),…,A_K^(m))。此外，设矢量A⁽¹⁾、……、 A^(M)的各要素相关联。换言之，设A_k⁽¹⁾、……、A_k^(M)为相关联的第k个数值 组。在本变形例中，在维持相关联的数值组的对应关系的状态下对数值组进 行限定改组。此外，设数值A_k^(m)=a_kαβ^(m)+a_kγα^(m)+a_kγα^(m)（其中，k是1以上且K 以下的整数、m是1以上且M以下的整数，（α,β,γ）是(1,2,3)、(2,3,1)、 (3,1,2)中的任一个），将三个片断设为(a_kγα^(m),a_kαβ^(m))、(a_kαβ^(m),a_kβγ^(m))、 (a_kβγ^(m),a_kγα^(m))。另外，上述的限定改组相当于M=1的情况，因此以下的说明 是更一般的限定改组。

秘密分散系统的功能结构例与图6相同，再分散部的详细的结构例与图 7相同，秘密分散的处理流程与图8相同。秘密分散系统具有选择部件105、 片断置换部件和再分散部件。秘密分散装置100_n至少具有片断置换部110_n、 再分散部120_n以及记录部190_n（其中，n是α、β、γ中的任一个）。其中， 各结构部及其处理如下。

记录部190_n记录片断a_1n⁽¹⁾、……、a_Kn⁽¹⁾、……、a_1n^(M)、……、a_Kn^(M)等。 此外，记录部190_n还记录与自己记录的片断a_kn是数值A_k的第几个片断有关 的信息。

选择部件105选择两个秘密分散装置。然后，将被选择部件105选择的 秘密分散装置的一个设为第1秘密分散装置100₁，将另一个设为第2秘密分 散装置100₂，将未被选择的秘密分散装置设为第3秘密分散装置100₃（S105）。 这里，将第1秘密分散装置100₁记录的数值A_k^(m)的片断设为 a_k1^(m)=(a_k31^(m),a_k12^(m))，将第2秘密分散装置100₂记录的数值A_k^(m)的片断设为 a_k2^(m)=(a_k12^(m),a_k23^(m))，将第3秘密分散装置100₃记录的数值A_k^(m)的片断设为 a_k3^(m)=(a_k23^(m),a_k31^(m))。

片断置换部件至少包含片断置换部110_α、110_β、110_γ。片断置换部件在 第1秘密分散装置100₁或者第2秘密分散装置100₂中生成{1，…，K}→{1，…， K}的双向单射π，将由第1秘密分散装置100₁记录的片断a_π(k)1⁽¹⁾、……、a_π(k)1^(M)设为对应的第k个数值组的片断，将第2秘密分散装置100₂记录的片断 a_π(k)2⁽¹⁾……、a_π(k)2^(M)设为对应的第k个数值组的片断（S110）。

再分散部件至少包含再分散部120_α、120_β、120_γ。如图7所示那样，再 分散部120_n具有第1随机数生成部121_n、第2随机数生成部122_n、第1计算 部123_n、第2计算部124_n、第3计算部125_n、片断更新部126_n。

第1秘密分散装置100₁的第1随机数生成部121₁为了第k个数值组的片 断的再分散化，生成作为随机的值的b_k31⁽¹⁾、……、b_k31^(M)，并将其发送给第3 秘密分散装置100₃（S121）。第2秘密分散装置100₂的第2随机数生成部122₂为了对应的第k个数值组的片断的再分散化，生成作为随机的值的 b_k23⁽¹⁾、……、b_k23^(M)，并将其发送给第3秘密分散装置100₃（S122）。第1秘 密分散装置100₁的第1计算部123₁为了对应的第k个数值组的片断的再分散 化，针对m=1～M，计算x_k^(m)=b_k31^(m)-a_π(k)31^(m)，并将x_k⁽¹⁾、……、x_k^(M)发送给 第2秘密分散装置100₂（S123）。

第2秘密分散装置100₂的第2计算部124₂为了相关联的第k个数值组的 片断的再分散化，针对m=1～M计算y_k^(m)=b_k23^(m)-a_π(k)23^(m)，并将y_k⁽¹⁾、……、 y_k^(M)发送给第1秘密分散装置100₁（S124）。第1秘密分散装置100₁的第3 计算部125₁和第2秘密分散装置100₂的第3计算部125₂为了相关联的第k 个数值组的片断的再分散化，分别针对m=1～M计算b_k12^(m)=a_π(k)12^(m)-x_k^(m)-y_k^(m)（S125）。第1秘密分散装置100₁的片断更新部126₁将(b_k31^(m),b_k12^(m))设为片 断b_k1^(m)，第2秘密分散装置100₂的片断更新部126₂将(b_k12^(m),b_k23^(m))设为片断 b_k2^(m)，第3秘密分散装置100₃的片断更新部126₃将(b_k23^(m),b_k31^(m))设为片断b_k3^(m)（S126）。另外，各秘密分散装置100_n的记录部190_n不仅记录片断b_kn^(m)，还 记录用于表示自己记录的第k个片断即片断b_kn^(m)是数值B_k^(m)的片断的信息。 与实施例1相同，片断b_k1^(m)、b_k2^(m)、b_k3^(m)是数值B_k^(m)的片断。即，步骤 S121～S126相当于步骤S120。

此外，如果将数值B₁⁽¹⁾、……、B_K⁽¹⁾、……、B₁^(M)、……、B_K^(M)设为新 的数值A₁⁽¹⁾、……、A_K⁽¹⁾、……、A₁^(M)、……、A_K^(M)，且变更在片断置换部 件中选择的秘密分散装置的组合，则能够重复该处理（S111、S112）。

这样，如果维持矢量的各要素的对应关系的状态下利用限定改组，则能 够根据表格形式的数据的秘密分散，将各行设为一个要素（相关联的数值组） 而进行列方向的随机置换。

【实施例4】

在实施例4中也将构成秘密分散系统的秘密分散装置的数目设为3，并 更具体进行说明。在实施例4中，说明与实施例2一样具有不正当检测功能 的例子。

[限定改组]

图6还表示实施例4的秘密分散系统的结构。另外，本实施例的秘密分 散装置100_n还具有由虚线表示的结构部。图9表示篡改检测部的详细的结构。 图10表示实施例4的秘密分散系统中的秘密分散的处理流程。本实施例的秘 密分散系统由连接到网络1000上的三个秘密分散装置100_α、100_β、100_γ以及 选择部件105构成。这里，将K个数值的第k个设为数值A_k=a_kαβ+a_βγ+a_kγα（其 中，K为2以上的整数，k为1以上且K以下的整数，（α,β,γ）是(1,2,3)、 (2,3,1)、(3,1,2)中的任一个），并将其三个片断设为(a_kγα,a_kαβ)、(a_kαβ,a_kβγ)、 (a_kβγ,a_kγα)。

本实施例的秘密分散系统具有选择部件105、初始信息分散部件、初始 乘法运算部件、片断置换部件、再分散部件、确认分散部件、确认乘法运算 部件、篡改检测部件。秘密分散装置100_n具有初始信息分散部130_n、初始乘 法运算部140_n、片断置换部110_n、再分散部120_n、确认分散部150_n、确认乘 法运算部160_n、篡改检测部170_n、记录部190_n（其中，n是α、β、γ中的 任一个）。记录部190_n记录数值A₁、……、A_K的片断等。

选择部件105选择两个秘密分散装置。然后，将被选择部件105选择的 秘密分散装置的一个设为第1秘密分散装置100₁，将另一个设为第2秘密分 散装置100₂，将未被选择的秘密分散装置设为第3秘密分散装置100₃（S105）。 这里，将第1秘密分散装置100₁记录的第k个片断设为a_k1=(a_k31,a_k12)，将第2 秘密分散装置100₂记录的第k个片断设为a_k2=(a_k12,a_k23)，将第3秘密分散装 置100₃记录的第k个片断设为a_k3=(a_k23,a_k31)。

初始信息分散部件由初始信息分散部130_α、130_β、130_γ构成。初始信息 分散部130_α、130_β、130_γ通过秘密计算求出秘密分散装置100_α、100_β、100_γ的哪一个都不知道的K个数值P₁、……、P_K各自的片断p_kn，并将其记录在 秘密分散装置100_n（S130）。例如，在第1秘密分散装置100₁中生成K个随 机的值R⁽¹⁾₁、……、R⁽¹⁾_K，在第2秘密分散装置100₂中生成K个随机的值 R⁽²⁾₁、……、R⁽²⁾_K。此外，在秘密分散装置100₁、100₂、100₃中将R⁽¹⁾_k的片断 (r⁽¹⁾_k31,r⁽¹⁾_k12)、(r⁽¹⁾_k12,r⁽¹⁾_k23)、(r⁽¹⁾_k23,r⁽¹⁾_k31)、以及R⁽²⁾_k的片断(r⁽²⁾_k31,r⁽²⁾_k12)、 (r⁽²⁾_k12,r⁽²⁾_k23)、(r⁽²⁾_k23,r⁽²⁾_k31)秘密分散而记录。此后，在秘密分散装置100₁、100₂、 100₃中，通过秘密计算而求出P_k=R⁽¹⁾_k+R⁽²⁾_k的数值P_k的片断(p_k31,p_k12)、 (p_k12,p_k23)、(p_k23,p_k31)，并将其分散记录在秘密分散装置100₁、100₂、100₃中。 通过这样的处理，能够分散记录所有的秘密分散装置100_α、100_β、100_γ不知 道的数值的片断。

初始乘法运算部件由初始乘法运算部140_α、140_β、140_γ构成。初始乘法 运算部140_α、140_β、140_γ通过秘密计算而求出S_k=P_k×A_k的数值S_k的片断 (s_kγα,s_kαβ)、(s_kαβ,s_kβγ)、(s_kβγ,s_kγα)，并将其分散记录在秘密分散装置100_α、100_β、 100_γ（S140）。

片断置换部件和再分散部件与实施例3相同。通过片断置换部件和再分 散部件，对秘密分散装置100_α、100_β、100_γ记录片断b_k1、b_k2、b_k3作为数值 B_k的片断。确认分散部件由确认分散部150_α、150_β、150_γ构成。确认分散部 150_α、150_β、150_γ针对k=1～K通过秘密计算而生成Q_k=P_π(k)的数值Q_k的片断 (q_kγα,q_kαβ)、(q_kαβ,q_kβγ)、(q_kβγ,q_kγα)，并将其分散记录在秘密分散装置100_α、100_β、 100_γ（S150）。例如，将在步骤S130中由第1秘密分散装置100₁生成的数值 R⁽¹⁾_π(k)的其他片断(r’⁽¹⁾_π(k)31,r’⁽¹⁾_π(k)12)、(r’⁽¹⁾_π(k)12,r’⁽¹⁾_π(k)23)、(r’⁽¹⁾_π(k)23,r’⁽¹⁾_π(k)31)、以 及由第2秘密分散装置100₂生成的数值R⁽²⁾_π(k)的其他的片断(r’⁽²⁾_π(k)31,r’⁽²⁾_π(k)12)、 (r’⁽²⁾_π(k)12,r’⁽²⁾_π(k)23)、(r’⁽²⁾_π(k)23,r’⁽²⁾_π(k)31)秘密分散而记录。此后，在秘密分散装置 100₁、100₂、100₃中，利用其他的片断并通过积极计算而求出Q_k=R⁽¹⁾_π(k)+R⁽²⁾_π(k)的数值Q_k的片断(q_k31,q_k12)、(q_k12,q_k23)、(q_k23,q_k31)，并将其分散记录在秘密分 散装置100₁、100₂、100₃中。通过这样的处理，能够分散记录满足Q_k=P_π(k)而且所有的秘密计算装置100_α、100_β、100_γ不知道的数值的片断。

确认乘法运算部件由确认乘法运算部160_α、160_β、160_γ构成。确认乘法 运算部160_α、160_β、160_γ通过秘密计算而求出T_k=Q_k×B_k的数值T_k的片断 (t_kγα,t_kαβ)、(t_kαβ,t_kβγ)、(t_kβγ,t_kγα)，并将其分散记录在秘密分散装置100_α、100_β、 100_γ（S160）。

篡改检测部件由篡改检测部170_α、170_β、170_γ构成。此外，如图9所示， 篡改检测部170_n具有第3随机数生成部171_n、第4随机数生成部172_n、第4 计算部173_n、第5计算部174_n、第1确认部175_n、第6计算部176_n、第7计 算部177_n、第2确认部178_n。篡改检测部件根据秘密分散装置100_α、100_β、 100_γ作为第1秘密分散装置100₁、第2秘密分散装置100₂、第3秘密分散装 置100₃中的哪一个装置来工作，如下进行处理。

第1秘密分散装置100₁的第3随机数生成部171₁生成作为随机的值的 u_k,并将其发送给第2秘密分散装置100₂（S171）。第2秘密分散装置100₂的 第4随机数生成部172₂生成作为随机的值的v_k，并将其发送给第1秘密分散 装置100₁（S172）。第2秘密分散装置100₁的第4计算部173₁计算 d_k=s_π(k)12-t_k12-u_k-v_k，并将其发送给第3秘密分散装置100₃（S173）。

第2秘密分散装置100₂的第5计算部174₂计算e_k=s_π(k)12-t_k12-u_k-v_k，并将 其发送给第3秘密分散装置100₃（S174）。第3秘密分散装置100₃的第1确 认部175₃确认d_k=e_k的情况，如果相异则中止处理（S175）。

第1秘密分散装置100₁的第6计算部176₁计算f_k=s_π(k)31-t_k31+u_k，并将其 发送给第3秘密分散装置100₃（S176）。第2秘密分散装置100₂的第7计算 部177₂计算g_k=s_π(k)23-t_k23+v_k，并将其发送给第3秘密分散装置100₃（S177）。 第3秘密分散装置100₃的第2确认部178₃确认f_k+g_k+d_k=0的情况，如果相异 则中止处理（S178）。此外，如果将数值B₁、……、B_K设为新的数值A₁、……、 A_K，并变更在片断置换部件中选择的秘密分散装置的组合，则能够重复该处 理（S111、S112）。

根据实施例4的秘密分散系统，可获得与实施例3的秘密分散装置相同 的效果，且还能够确认在隐藏数值A₁、……、A_K与数值B₁、……B_K的对应 关系的处理过程中，不存在对其他的秘密分散装置发送篡改后的值的不正当 的情况。另外，在还进行分类的情况下，秘密分散装置100_n还具有比较部210_n和交换部220_n。具体的分类的处理与实施例1相同。

[秘密计算]

在上述的说明中，以对秘密计算不限定为一个方法作为前提，具体例并 未表示。以下表示实施例3、4的秘密分散系统的各结构不能够利用的基本秘 密计算的具体例。另外，在以下的说明中，将由秘密分散装置100_α、100_β、 100_γ分散记录的数值A的片断设为(a_γα,a_αβ)、(a_αβ,a_βγ)、(a_βγ,a_γα)，将数值B的片 断设为(b_γα,b_αβ)、(b_αβ,b_βγ)、(b_βγ,b_γα)，将数值C的片断设为(c_γα,c_αβ)、(c_αβ,c_βγ)、 (c_βγ,c_γα)。

数值A的秘密分散

（1）生成随机数a_αβ、a_βγ。

（2）计算a_γα=A-a_αβ-a_βγ，将片断设为(a_γα,a_αβ)、(a_αβ,a_βγ)、(a_βγ,a_γα)，并分散 记录在秘密分散装置100_α、100_β、100_γ。

数值A的复原

（1）秘密分散装置100_α对秘密分散装置100_β发送a_γα，并对秘密分散装 置100_γ发送a_αβ。秘密分散装置100_β对秘密分散装置100_γ发送a_αβ，并对秘密 分散装置100_α发送a_βγ。秘密分散装置100_γ对秘密分散装置100_α发送a_βγ，并 对秘密分散装置100_β发送a_γα。

（2）如果从秘密分散装置100_β接收的a_βγ和从秘密分散装置100_γ接收的 a_βγ一致，则秘密分散装置100_α计算a_αβ+a_βγ+a_γα而复原数值A。如果从秘密分 散装置100_γ接收的a_γα和从秘密分散装置100_α接收的a_γα一致，则秘密分散装 置100_β计算a_αβ+a_βγ+a_γα而复原数值A。如果从秘密分散装置100_α接收的a_αβ和从秘密分散装置100_β接收的a_αβ一致，则秘密分散装置100_γ计算a_αβ+a_βγ+a_γα而复原数值A。

C=A+B的秘密计算

（1）秘密分散装置100_α计算并记录(c_γα,c_αβ)=(a_γα+b_γα,a_αβ+b_αβ)，秘密分散 装置100_β计算并记录(c_αβ,c_βγ)=(a_αβ+b_αβ,a_βγ+b_βγ)，秘密分散装置100_γ计算并记录 (c_βγ,c_γα)=(a_βγ+b_βγ,a_γα+b_γα)。

C=A+S的秘密计算（其中，S是已知的常数）

（1）秘密分散装置100_α计算并记录(c_γα,c_αβ)=(a_γα+S,a_αβ)，秘密分散装置 100_γ计算并记录(c_βγ,c_γα)=(a_βγ,a_γα+S)。秘密分散装置100_β不存在处理。

C=AS的秘密计算（其中，S是已知的常数）

（1）秘密分散装置100_α计算并记录(c_γα,c_αβ)=(a_γαS,a_αβS)，秘密分散装置 100_β计算并记录(c_αβ,c_βγ)=(a_αβS,a_βγS)，秘密分散装置100_γ计算并记录 (c_βγ,c_γα)=(a_βγS,a_γαS)。

C=AB的秘密计算

（1）秘密分散装置100_α生成随机数如r₁、r₂、c_γα，并计算 c_αβ=(a_γα+a_αβ)(b_γα+b_αβ)-r₁-r₂-c_γα。然后，秘密分散装置100_α对秘密分散装置100_β发送(r₁,c_αβ)，对秘密分散装置100_γ发送(r₂,c_γα)。

（2）秘密分散装置100_β计算y=a_αβb_ββ+a_βγb_αβ+r₁，并将其发送给秘密分散 装置100_γ。

（3）秘密分散装置100_γ计算z=a_βγb_γα+a_γαb_βγ+r₂，并将其发送给秘密分散 装置100_α。

（4）秘密分散装置100_β和秘密分散装置100_γ分别计算c_βγ=y+z+a_βγb_βγ。

（5）秘密分散装置100_α记录(c_γα,c_αβ)，秘密分散装置100_β记录(c_αβ,c_βγ)， 秘密分散装置100_γ记录(c_βγ,c_γα)。

[程序、记录介质]

上述的各种处理不仅根据记载而时序地执行，也可以根据执行处理的装 置的处理能力或者需要而并列地或者单独执行。此外，在不脱离本发明的宗 旨的范围内能够适当进行变更是理所当然的。

此外，当通过计算机来实现上述的结构的情况下，通过程序来记载各装 置应有的功能的处理内容。此外，通过由计算机来执行该程序，能够在计算 机上实现上述处理功能。

记载了该处理内容的程序能够预先记录在计算机中能够读取的记录介质 中。作为计算机中能够读取的记录介质，例如可以是磁记录装置、光盘、光 磁记录介质、半导体存储器等。

此外，该程序例如通过销售、转让、出借记录了该程序的DVD、CD-ROM 等可移动记录介质等而流通。此外，将该程序预先存储在服务器计算机的存 储装置中，并经由网络，从服务器计算机向其他的计算机转发该程序，从而 流通该程序。

执行这样的程序的计算机例如先将记录在可移动记录介质中的程序或者 从服务器计算机转发的程序暂时存储在机子的存储装置中。然后，在执行处 理时，该计算机读取在自己的记录介质中存储的程序，并按照所读取的程序 而执行处理。此外，作为该程序的其他的执行方式，也可以由计算机从可移 动记录介质直接读取程序，并执行基于该程序的处理，并每次进一步从服务 器计算机向该计算机转发程序时，依次执行基于接受到的程序的处理。此外， 也可以通过不进行从服务器计算机向该计算机的程序转发，仅通过其执行指 示和结果获取而实现处理功能的、所谓的ASP（应用服务供应商）型的服务， 执行上述的处理。另外，假设本方式中的程序中包含用于电子计算机的处理 的信息即基于程序的信息（并非是对于计算机的直接的指令，但具有用于计 算机的处理的性质的数据等）。

此外，在该方式中，通过在计算机上执行规定的程序，构成本装置，但 这些处理内容的至少一部分也可以通过硬件来实现。