秘密并行处理装置、秘密并行处理方法、程序

技术领域

本发明涉及一边保持计算结果的正当性一边通过秘密分散对数据进行保 密且进行数据处理的秘密并行处理装置、秘密并行处理方法、程序。

背景技术

作为以往的保持正当性的秘密计算方法，例如存在非专利文献1。

现有技术文献

非专利文献

非专利文献1：五十嵐大，濱田浩気，菊池亮，千田浩司，「非常に高效 率なn＞＝2k-1のmaliciousモデル上秘密分散ベース秘密計算」，SCIS2013 (暗号と情報セキュリティシンポジウム)暗号プロトコルセッション (3C3-2)

发明内容

发明要解决的课题

在上述的现有技术中，存在安全性参数κ(即篡改成功率为1/2^κ左右)、 表示处理的规模的参数C中的通信量成为O(κC)比特而通信成本大的课题。 因此在本发明中，其目的在于提供能够在秘密并行处理中削减通信量的秘密 并行处理装置。

用于解决课题的手段

本发明的秘密并行处理装置包含随机化部、计算部、正当性证明部。

随机化部取得作为输入串的非随机化序列，输出将该非随机化序列和由 公开值构成的虚拟记录(dummyrecord)串结合并进行随机置换处理后的随 机化序列、和对所利用的随机置换数据进行了保密后的已保密随机置换数据。 计算部取得非随机化序列、随机化序列、虚拟记录串，对它们实施规定的函 数，使用实施该函数的处理中的计算过程的数据来生成各序列的输出校验和。 正当性证明部取得各序列的输出校验和与已保密随机置换数据，对各序列的 输出校验和进行评价，输出是否对非随机化序列正确地实施了规定的函数的 最终验证结果。

发明效果

根据本发明的秘密并行处理装置，能够在秘密并行处理中削减通信量。

附图说明

图1是表示实施例1的秘密并行处理装置的结构的框图。

图2是表示实施例1的秘密并行处理装置的动作的流程图。

图3是表示实施例1的秘密并行处理装置的随机化部的结构的框图。

图4是表示实施例1的秘密并行处理装置的随机化部的动作的流程图。

图5是表示实施例1的秘密并行处理装置的计算部的结构的框图。

图6是表示实施例1的秘密并行处理装置的计算部的动作的流程图。

图7是表示实施例1的秘密并行处理装置的正当性证明部的结构的框图。

图8是表示实施例1的秘密并行处理装置的正当性证明部的动作的流程 图。

具体实施方式

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

【实施例1】

＜记法＞

以下，说明在本说明书中共同使用的记法。

将明文空间设为R。

对于函数f：R→R′，将f^N：R^N→R′^N设为f的并行执行、即

f^N(a₀，……，a_N-1)＝(f(a₀)，……，f(a_N-1))。

对于环R，将0_R设为R的零元。

将X设为任意的集合，将m以及m′设为任意的整数。对于X^m的元x， 将i设为任意的整数，将第i个要素记载为x_i。

对于x∈X^m、y∈X^m′，将结合

(x₀，……，x_m-1，y₀，……，y_m′-1)∈X^m+m′

记载为x||y。

对于x∈(X^m)^N、y∈(X^m′)^N，将垂直结合

(x₀||y₀，……，x_N-1||y_N-1)

记载为x||_Vy。

[x]是将值x通过秘密分散进行了保密后的值，此外对于集合X，将[X] 设为对X的元进行了保密后的值的集合。

＜秘密并行处理装置的概要＞

以下，参照图1，说明本实施例的秘密并行处理装置的概要。图1是表 示本实施例的秘密并行处理装置1的结构的框图。如图1所示，本实施例的 秘密并行处理装置1是包含随机化部11、计算部12、正当性证明部13的结 构。输入串(称为非随机化序列)被输入至随机化部11、计算部12。正当性 证明部13输出最终验证结果。秘密并行处理装置1中，由多台构成组，通过 以组来执行以下的处理，从而实现秘密并行处理。

＜秘密并行处理方法的概要＞

以下，参照图2，说明本实施例的秘密并行处理方法的概要。图2是表 示本实施例的秘密并行处理装置1的动作的流程图。如图2所示，本实施例 的秘密并行处理方法被分为随机化步骤(步骤S11，计划1)、计算步骤(步 骤S12，计划2)、正当性证明步骤(步骤S13，计划3)这三个步骤而按顺序 进行。设为随机化部11执行随机化步骤，计算部12执行计算步骤，正当性 证明部13执行正当性证明步骤。

随机化部11取得作为输入串的非随机化序列，输出将非随机化序列和由 公开值构成的虚拟记录串结合并进行了随机置换处理后的随机化序列、和对 所利用的随机置换数据进行了保密后的已保密随机置换数据(S11)。另外， 公开值是在组内的全部装置中公开的值。此外，置换数据例如是各要素为0 至N-1的不同的数那样的N要素的串，表示N要素的数据的置换的方法。若 例示，对(a_0，a_1，a_2)的N＝3的数据以置换数据(2，1，0)来置换是， 将a_0向第2个，将a_1向第1个，将a_2向第0个移动而设为(a_2，a_1， a_0)。将通过随机数而生成的随机的置换数据称为随机置换数据。被保密的 随机置换数据是指，例如在参考非专利文献2的方法中，组内的k装置的组 (若组的装置数设为n，则存在_nC_k种)分别共享了共计_nC_k个随机置换数据 的该随机置换数据的集合，在执行置换时使用这些全部置换数据按顺序进行 置换。在这样的被保密的随机置换数据中，无论看哪个n-k装置的组，都存 在至少一个没有被共享的随机置换数据，所以整体的置换被保密。

计算部12取得非随机化序列、随机化序列、虚拟记录串，对它们实施规 定的函数，使用实施该函数的处理中的计算过程的数据来生成各序列的输出 校验和(S12)。正当性证明部13取得各序列的输出校验和与已保密随机置换 数据，对各序列的输出校验和进行评价，输出是否对非随机化序列正确地实 施了规定的函数的最终验证结果(S13)。

＜随机化部11＞

以下，参照图3、图4说明随机化部11、以及随机化部11执行的随机化 步骤(S11，计划1)的细节。图3是表示本实施例的秘密并行处理装置1的 随机化部11的结构的框图。图4是表示本实施例的秘密并行处理装置1的随 机化部11的动作的流程图。如图3所示，随机化部11包含虚拟记录串制成 部111、虚拟记录保密部112、结合部113、随机置换部114。

在计划1中，追加虚拟记录串，进行ν次具有正当性的随机置换处理。 参数ν是ν＝┌κ/logN┐程度的整数。另外，关于公开值的分散，执行秘密并 行处理的组内的各装置制成自己的份额(share)作为随机数分量固定即可， 是离线处理。另外，具有正当性的随机置换处理是任意的。例如存在参考非 专利文献1中记载的具有正当性的随机置换处理、参考非专利文献1的不具 有正当性的随机置换处理、在参考非专利文献2的随机置换处理中组合了前 述的非专利文献1的变换方法的随机置换处理等。

(参考非专利文献1)S.Laur,J.Willemson,andB.Zhang.Round-efficient obliviousdatabasemanipulation.InX.Lai,J.Zhou,andH.Lieds.,ISC,Vol.7001 ofLectureNotesinComputerScience,pp.262-277.Springer,2011.

(参考非专利文献2)濱田浩気，五十嵐大，千田浩司，高橋克巳，「3 パーティ秘匿関数計算のランダム置換プロトコル」，情報処理学会シンポジ ウム論文集，2010年10月12日，2010卷，第9号，pp561-566

此外，为了将公开值x具有正当性而通过秘密分散保密为某n个，组内 的各装置进行以下的处理即可。还能够应用于任何秘密分散。

1)在秘密分散中通常生成随机数，但将该随机数全部设为0等常数。

2)将输入设为x，将随机数设为上述的常数而通过秘密分散算法得到n 个份额。

3)仅输出n个中自己的分配额的份额。

由于x为公开值，上述能够无通信地仅在组内的各装置中执行。无通信 的处理作为秘密计算而具有正当性是众所周知的，因此上述的保密具有正当 性。

在计划1中使用的参数、输入、输出如以下所示。

参数：应计算的m输入μ输出函数F(将m、μ分别设为应计算的输出 函数F的输入数、输出数)、记录数N、所插入的虚拟记录数|D|、随机化 序列数ν∈E(E为任意的自然数的集合)

输入：非随机化序列[A]∈([R]^m)^N

输出：已保密随机置换数据[π₀]，……，[π_ν-1]∈[Π^N+|D|]随机化序 列[B₀]＝[π₀(A||D)]，……，[B_ν-1]＝[π_ν-1(A||D)]∈([R]^μ)^N+|D|、 虚拟记录串D∈(R^m)^|D|，其中，Π表示已保密随机置换数据的集合。

＜步骤S111＞

虚拟记录串制成部111制成由公开值构成的虚拟记录串D∈(R^m)^|D|并进行输出(S111)。内容在F^|D|的定义域内是任意的。

＜步骤S112＞

虚拟记录保密部112将虚拟记录串D以具有正当性的方法来保密，取得 已保密虚拟记录串[D]∈([R]^m)^|D|(S112)。

＜步骤S113＞

结合部113对输入(非随机化序列[A])结合已保密的虚拟记录串[D]， 取得结合结果[A||D]：＝[A]||[D](S113)。

以下的步骤S114关于满足i＜ν的全部i执行。

＜步骤S114＞

随机置换部114对结合结果[A||D]实施具有正当性的随机置换处理， 取得随机化序列[B_i]：＝[π_i(A||D)]，输出该随机化序列和所利用的已保 密随机置换数据[π_i]∈[Π](S114)。

＜计算部12＞

以下，参照图5、图6说明计算部12、以及计算部12执行的计算步骤(S12， 计划2)的细节。图5是表示本实施例的秘密并行处理装置1的计算部12的 结构的框图。图6是表示本实施例的秘密并行处理装置1的计算部12的动作 的流程图。如图5所示，计算部12包含校验和初始值定义部121、函数计算 部122、校验和更新部123、函数处理后序列定义部124、函数处理后虚拟记 录保密部125、输出校验和生成部126。

在计划2中，通过非随机化序列、随机化序列、虚拟记录串这三个序列 并行计算期望的函数F。此时，输出全部作为校验和而保存。

在计划2中使用的参数、输入、输出如以下所示。

参数：应计算的m输入μ输出函数F、记录数N、所插入的虚拟记录数| D|、随机化序列数ν∈E(E为任意的自然数的集合)

输入：非随机化序列[A]∈([R]^m)^N、随机化序列[B₀]，……，[B_ν-1] ∈([R]^μ)^N+|D|、虚拟记录串D∈(R^m)^|D|

输出：输出[F^N(A)]∈([R]^μ)^N、ν+2个校验和[C_A]，[C_B0]，……， [C_Bν-1]，[C_D]

＜步骤S121＞

校验和初始值定义部121将非随机化序列、随机化序列、虚拟记录串的 校验和的初始值分别定义为[C_A]：＝0→∈([R]⁰)^N，[C_B0]：＝0→∈([R] ⁰)^N+|D|，……，[C_Bν-1]：＝0→∈([R]⁰)^N+|D|，[C_D]：＝0→∈([R]⁰)^|D|(S121)。其中0→为空矢量。

＜步骤S122＞

函数计算部122对非随机化序列[A]、随机化序列[B₀]，……，[B_ν-1] 的ν+1序列实施semi-honest的秘密计算，对虚拟记录串D实施明文的计算， 将期望的函数F按每个子协议f_i：[R]^mi→[R]^μi来计算，输出[F^N(A)] ∈([R]^μ)^N(S122)。其中m_i、μ_i分别是子协议f_i的输入数、输出数。

＜步骤S123＞

校验和更新部123按前述的每个子协议f_i：[R]^mi→[R]^μi来更新校验 和(S123)。

＜步骤S124＞

函数处理后序列定义部124将对子协议f_i的ν+2序列的各输出定义为函 数处理后非随机化序列[A′]∈([R]^μi)^N、函数处理后随机化序列[B′₀]，……， [B′_ν-1]∈([R]^μi)^N+|D|、函数处理后虚拟记录串D′∈(R^μi)^|D|(S124)。

＜步骤S125＞

函数处理后虚拟记录保密部125将函数处理后虚拟记录串D′以具有正当 性的方法来保密，取得已保密函数处理后虚拟记录串[D′](S125)。

＜步骤S126＞

输出校验和生成部126将非随机化序列的校验和[C_A]和函数处理后非 随机化序列[A′]进行垂直结合而生成非随机化序列的输出校验和([C_A]： ＝[C_A]||_V[A′])并进行输出(S126)。输出校验和生成部126关于满足i ＜ν的全部i，将随机化序列的校验和[C_Bi]和函数处理后随机化序列[B′_i] 进行垂直结合而生成随机化序列的输出校验和([C_Bi]：＝[C_Bi]||_V[B′_i]) 并进行输出(S126)。输出校验和生成部126将虚拟记录串的校验和[C_D]和 已保密函数处理后虚拟记录串[D′]进行垂直结合而生成虚拟记录串的输出 校验和([C_D]：＝[C_D]||_V[D′])并进行输出(S126)。

＜正当性证明部13＞

以下，参照图7、图8说明正当性证明部13以及正当性证明部13执行 的正当性证明步骤(S13，计划3)的细节。图7是表示本实施例的秘密并行 处理装置1的正当性证明部13的结构的框图。图8是表示本实施例的秘密并 行处理装置1的正当性证明部13的动作的流程图。如图7所示，正当性证明 部13包含第一数据接收信号发送接收部130、随机置换公开部131、差分值 计算部132、垂直分割部133、随机数方差值生成部134、积和部135、第二 数据接收信号发送接收部136、积和值公开部137、验证结果发送接收部138、 最终验证结果输出部139。

在计划3中基于在计算步骤中保存的校验和来验证正当性。记号SYNC 表示发送将接收到至该时刻为止的全部应接收的数据的情况传达给组内的其 他全部装置的信号且接收来自组内的其他全部装置的该信号的处理。直至能 够确认SYNC为止不进行后续的处理从而保证非同步网络中的安全性。

在计划3中使用的参数、输入、输出如以下所示。

参数：应计算的m输入μ输出函数F、记录数N、所插入的虚拟记录数| D|、随机化序列数ν∈E(E为任意的自然数的集合)、分割单位σ∈E

输入：输出校验和[C_A]，[C_B0]，……，[C_Bν-1]，[C_D]、已保密随机置 换数据[π₀]，……，[π_ν-1]∈[Π^N+|D|]

输出：若存在篡改则为表示存在篡改的最终验证结果┴，若不存在篡改则 为表示没有篡改的最终验证结果┬

＜步骤S130＞

第一数据接收信号发送接收部130执行前述的SYNC处理(S130)。具 体而言，第一数据接收信号发送接收部130将传达接收到至步骤S130为止应 接收的全部数据的信号即数据接收信号发送给组内的其他全部装置，此外接 收来自组内的其他全部装置的该信号(S130)。

以下的步骤S131至步骤S135关于满足i＜ν的全部i执行。

＜步骤S131＞

随机置换公开部131对已保密随机置换数据[π_i]进行公开，取得其解码 值π_i(S131)。

＜步骤S132＞

差分值计算部132计算从随机化序列的输出校验和[C_Bi]扣除了非随机 化序列的输出校验和[C_A]与虚拟记录串的输出校验和[C_D]的结合([C_A] ||[C_D])的差分值[ζ_i](S132)。即，差分值计算部132计算差分值[ζ_i]： ＝[C_Bi]-([C_A]||[C_D])∈([R]^M)^N+|D|(S132)。另外M设为[C_A] (或[C_Bi]，哪个都一样)的每一个记录的要素数。

＜步骤S133＞

垂直分割部133将差分值[ζ_i]的各记录按每个分割单位σ要素进行垂直 分割(S133)。垂直分割部133取得M′＝┌M/σ┐个([R]^σ)^N+|D|的要素。 另外在最后的分割时显现尾数的情况下，垂直分割部133将不满足σ要素的 部分进行0填充。垂直分割部133取得差分分割值[ζ′_i]∈([R]^σ)^(N+|D|)M′(S133)。

＜步骤S134＞

随机数方差值生成部134生成随机数的方差值[ρ_i]∈([R]^σ)^(N+|D|)M′(S134)。

＜步骤S135＞

积和部135基于差分方差值和随机数的方差值，通过积和协议来计算积 和值

【数1】

$\left[\phi \right]=\underset{i<v}{\Sigma }\left[{\rho }_i\right]\left[{\zeta }_i^{\prime }\right]$

(S135)。

＜步骤S136＞

第二数据接收信号发送接收部136执行SYNC处理(S136)。具体而言， 第二数据接收信号发送接收部136将传达接收到至步骤S136为止应接收的全 部数据的信号即数据接收信号发送给组内的其他全部装置，此外接收来自组 内的其他全部装置的该信号(S136)。

＜步骤S137＞

积和值公开部137将积和值进行公开而取得其解码值

＜步骤S138＞

验证结果发送接收部138确认积和值的解码值将若为真则成为┬， 若为伪则成为┴的验证结果发送给组内的其他全部装置，从组内的其他全部装 置接收验证结果(S138)。

＜步骤S139＞

最终验证结果输出部139输出若在来自组内的其他全部装置的验证结果 中存在┴则成为┴，若非如此则成为┬的最终验证结果(S139)。

根据本实施例的秘密并行处理装置1，在秘密并行处理中能够削减通信 量。具体而言，在进行数据并行数N的计算时能够设为通信量O(┌κ/logN┐C) 比特，关于通信量，与以往方法相比改善logN。

＜本发明的要点＞

为了保证以往处理结果的正当性，使用了作为代数的结构的体的性质。 但是在该方针中安全性参数κ大致与体的比特长成为同程度。在本发明中能 够使用随机置换处理将数据并行数N编入安全性强度。虚拟记录的内容是什 么都可以，但没有虚拟记录就无法达成安全性的点也是要点。

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

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

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

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

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

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