元素复制装置、元素复制方法、以及程序

摘要

针对h＝2,……,M，获得将在第一集合中包含的复制源的元素a(f(h))变为元素a(f(h))‑a(f(h‑1))并将在第一集合中包含的复制源以外的元素变为零而获得的、包含多个元素a

说明书

技术领域

本发明涉及有效地复制在集合中包含的元素的技术。

背景技术

作为不复原被隐匿的数值就获得特定的运算结果的方法，有被称为秘密计算的方法(例如，参照非专利文献1等)。在非专利文献1的方法中，进行将数值的片断分散到三个秘密计算装置的隐匿化，通过由三个秘密计算装置进行协调计算，以不恢复数值，将加减运算、常数和、乘法运算、常数倍、逻辑运算(逻辑非、逻辑与、逻辑或、异或)、数据格式转换(整数、二进制数)等运算结果分散给三个秘密计算装置的状态，即以维持隐匿化的状态保持。

作为按照表格将这些元素映射到秘密计算上的方法，有非专利文献2的方法。在非专利文献2的方法中，在秘密计算上实现了将被隐匿化的表格的元素(值)复制到同一列内的映射。

现有技术文献

非专利文献1：千田浩司,濱田浩気,五十嵐大,高橋克巳,“軽量検証可能3パーティ秘匿関数計算の再考,”In CSS,2010.

非专利文献2：濱田浩気,五十嵐大,千田浩司,“秘匿計算上の一括写像アルゴリズム,”電子情報通信学会論文誌,A,基礎·境界,Vol.96,No.4,pp.157-165,apr 2013.

发明内容

发明要解决的课题

但是，在现有技术中，若将进行元素的复制的列的大小设为N，则为了将元素复制到同一列，需要O(N)次、O(log N)级的乘法运算。这不仅是在秘密计算上将被隐匿化的表的元素复制到同一列内的情况，只要是将包含被排序后的N个元素的集合的元素作为同一集合内的元素而复制的情况就相同。

本发明的课题在于降低对包含被排序后的元素的集合的元素进行复制的情况下的运算成本。

用于解决课题的方案

为了解决上述课题，针对h＝2,……,M，获得将第一集合中包含的复制源的元素a(f(h))变为a(f(h))-a(f(h-1))，并将第一集合中包含的复制源以外的元素变为零而获得的、包含元素a₅(1)、……、a₅(N)的集合即第二集合或第二集合的密文，利用第二集合或第二集合的密文，获得包含第1个元素b(1)＝a₅(1)与第i＝2,……,N个元素b(i)＝b(i-1)+a₅(i)的集合即第三集合或第三集合的密文。

其中，第一集合是包含被排序的多个元素a(1)、……、a(N)的集合。由多个元素a(1)、……、a(N)组成的集合包含多个复制源的元素a(f(1)),……,a(f(M))。顺序在复制源的元素a(f(h))之前且顺序最接近复制源的元素a(f(h))的复制源的元素a(f(h-1))的加法逆元为-a(f(h-1))。第二集合的第1个元素是a₅(1)，第二集合的第i＝2,……,N个集合是a₅(i)。

发明效果

在本发明中，通过运算量小的加法运算就能够复制集合的元素，因此能够降低在复制包含被排序后的元素的集合的元素的情况下的运算成本。

附图说明

图1是用于例示实施方式的秘密计算系统的结构的模块图。

图2A是用于例示第一实施方式及其变形例的元素复制装置的结构的模块图。图2B是用于例示第一实施方式及其变形例的事先计算的处理的流程图。图2C是用于例示第一实施方式及其变形例的元素复制的处理的流程图。

图3A是用于例示第二实施方式及其变形例的元素复制装置的结构的模块图。图3B是用于例示第二实施方式的分类部的结构的模块图。

图4A是用于例示第二实施方式及其变形例的元素复制的处理的流程图。图4B是用于例示图4A的步骤S214以及S214’的处理的流程图。图4C是用于例示图4B的步骤S2143的处理的流程图。

具体实施方式

以下说明本发明的实施方式。

[概要]

首先，说明各实施方式的概要。

在各实施方式中，获得对h＝2,……,M将在第一集合中包含的复制源的元素a(f(h))变为元素a(f(h))-a(f(h-1))并将在第一集合中包含的复制源以外的元素变为零而获得的、包含多个元素a₅(1),……,a₅(N)的集合即第二集合或第二集合的密文，利用第二集合或第二集合的密文，获得包含第一个元素b(1)＝a₅(1)与第i＝2,……,N个元素b(i)＝b(i-1)+a₅(i)的集合即第三集合或第三集合的密文。

这里，第三集合成为如下的集合：按照某种顺序，将第一集合中包含的“复制源的元素”复制成顺序在该元素后面且在下一个复制源的元素之前的所有的“不是复制源的元素”，将“最后的复制源的元素”复制成在其后的所有的“不是复制源的元素”。通过预先计算将在第一集合中包含的复制源的元素a(f(h))变为元素a(f(h))-a(f(h-1))并将复制源以外的元素变为零而获得的第二集合或其密文，能够根据累加性加法运算计算上述的第三集合或其密文。加法运算的运算量与现有技术中利用的乘法等的乘法运算相比非常小。因此，能够将复制包含被排序后的元素的集合的元素的情况下的运算成本降低到比现有技术更低。

另外，“第一集合”表示包含被排序后的多个元素a(1),…….a(N)(其中，N是2以上的整数，例如是3以上的整数)的集合。第一集合可以是由N个元素a(1),…….a(N)组成的N维向量，也可以是由在N+Λ维向量(其中，Λ是1以上的整数)中包含的N个元素a(1),…….a(N)组成的集合，也可以是由在具有N个以上的元素的矩阵中包含的N个元素a(1),…….a(N)组成的集合，也可以是除此之外的集合。多个元素a(1),…….a(N)之间决定了顺序(也就是说，多个元素a(1),…….a(N)被排序)。该顺序可以是预先决定的，也可以是在每次进行处理时决定的。该顺序的决定方法不存在限定，只要是不同的元素对应不同的顺序则可以决定任意的顺序。例如，当第一集合是将第1,……,N元素分别设为a(1),……,a(N)的N维向量(a(1),……,a(N))的情况下，可以对元素a(n)关联第n个(其中，n∈{1,……,N})顺序，也可以对元素a(n)关联第N-n+1个顺序。

由这些多个元素a(1),…….a(N)组成的集合{a(1),…….a(N)}包含多个复制源的元素a(f(1)),……,a(f(M))(其中，2≤M≤N，例如M<N)。“复制源的元素”表示成为复制源的元素即被复制的元素。各元素a(n)(其中，n∈{1,……,N})或者是复制源的元素a(f(m))(其中，m∈{1,……,M})，又或者不是复制源的元素。换言之，例如复制源的元素a(f(1)),……,a(f(M))维持元素a(1),…….a(N)的顺序关系。即，对复制源的元素a(f(1)),……,a(f(M))关联按照元素a(1),…….a(N)的顺序的顺序。例如，当N＝10、M＝4，元素a(1),…….a(10)的顺序分别是第1、……、第10，且复制源的元素是a(1)、a(4)、a(5)、a(9)的情况下，集合{a(1),a(4),a(5),a(9)}内的复制源的元素a(1)、a(4)、a(5)、a(9)的顺序分别是第1、2、3、4。此外，将顺序在复制源的元素a(f(h))(其中，h∈{2,……,M})之前且顺序最接近复制源的元素a(f(h))的复制源的元素表示为a(f(h-1))。换言之，仅由复制源的元素组成的集合内的顺序将复制源的元素a(f(h))的前一个的复制源的元素表示为a(f(h-1))。

对各元素至少定义了加法运算，将该加法运算表示为“+”。此外，对各元素至少定义了加法逆元，元素ν的加法逆元表现为“-ν”。即，上述的a(f(h))-a(f(h-1))表示元素a(f(h))与加法逆元素-a(f(h-1))的加法运算，b(i-1)+a₅(i)表示元素b(i-1)与元素a₅(i)的加法运算。加法运算的例子是加法、异或、对于加法结果θ的以整数P作为模的余运算θmod>5(i)是元素b(i-1)与元素a₅(i)的加法值。此外，将加法单位元表示为“零”或者“0”。此外，将加法生成元表示为“1”。

本方式中的“α的密文”意味着在能够进行秘密计算的方法中隐匿α而获得的信息。公知的秘密共享和加密等是隐匿化的例子，其中，公知的线性秘密共享或同态型密码等是“能够进行秘密计算的隐匿化方法”的例子。在这些方式中，例如在定义了α₁与α₂之间的二元运算Ο，且α₁Οα₂＝α₃成立的情况下，利用α₁的密文E(α₁)与α₂的密文E(α₂)能够计算α₃的密文E(α₃)＝E(α₁)ΟE(α₂)。同样地，在对α₁定义了一元运算Ο，且Οα₁＝α₃成立的情况下，利用α₁的密文E(α₁)能够计算α₃的密文E(α₃)＝ΟE(α₁)。不需要为了这些计算而恢复密文E(α₁)或E(α₂)。对基于秘密计算的隐匿化、恢复、加法、减法、乘法、逻辑运算，能够利用例如在非专利文献1或非专利文献2中公开的公知技术。对基于密码计算的随机置换，例如能够利用在非专利文献2或参考文献1(Sven>

另外，当根据作为包含复制源的元素a(f(1)),……,a(f(M))的集合的第五集合或第五集合的密文，事先获得作为包含所述的元素a(f(h))-a(f(h-1))的集合的第四集合或第四集合的密文的情况下，第一运算部也可以利用该第四集合或第四集合的密文，获得第二集合或第二集合的密文(事先计算方式)。例如，在事先获得了第四集合或第四集合的密文，且该第四集合是将在包含被进行了沿着元素a(1),……,a(N)的顺序的排序的复制源的元素a(f(1)),……,a(f(M))的第六集合中包含的复制源的元素a(f(h))变为a(f(h))-a(f(h-1))的集合的情况下，第一运算部也可以利用该第四集合或第四集合的密文，获得第二集合或第二集合的密文。由此，能够进一步降低运算成本。该方式适用于第一集合或第一集合的密文根据第五集合或第五集合的密文、或者第六集合或第六集合的密文(以下称为“第五集合等”)而获得的情况，也就是说适用于第五集合等比第一集合或第一集合的密文先获得的情况(例如，非专利文献2的方式)。

除此之外的情况下，第一运算部也可以利用第一集合或第一集合的密文获得第二集合或第二集合的密文(事后计算方式)。例如，第一运算部也可以利用第一集合或第一集合的密文，获得以是否为复制源作为分类条件而进行第一集合中包含的元素a(1),……,a(N)的稳定分类而得到的、包含元素a(1),……,a(N)且元素a(f(1)),……,a(f(M))的顺序连续的集合即第七集合或者第七集合的密文，利用第七集合或第七集合的密文，针对h＝2,……,M，得到将第七集合中包含的复制源的元素a(f(h))变为a(f(h))-a(f(h-1))的集合即第八集合或第八集合的密文，利用第八集合或第八集合的密文，得到将第八集合的元素进行分类并将复制源以外的元素变为零而得到的集合即第二集合或第二集合的密文。

此时，第一运算部利用第一集合的密文，通过秘密计算而获得第七集合的密文，得到包含根据元素a(1),……,a(N)的稳定分类对表示元素a(1),……,a(N)各自的顺序的元素p(a(1)),……,p(a(N))进行分类而得到的元素的集合即第九集合的密文，利用第七集合的密文，通过秘密计算而得到第八集合的密文，利用第八集合的密文以及第九集合的密文，通过秘密计算，得到维持第八集合的元素和第九集合的元素的对应关系且随机置换了第八集合的元素的顺序以及第九集合的元素的顺序而得到的、分别与重新排列了第八集合的元素的顺序的集合即第十集合以及重新排列了第九集合的元素的顺序的集合即第十一集合对应的、第十集合的密文以及第十一集合的密文，利用第十一集合的密文的恢复结果以及第十集合的密文，获得对第十集合的元素进行分类而将复制源以外的元素变为零而获得的集合即第二集合的密文。

在此，第八集合的密文虽然各元素的内容被隐匿，但与复制源的元素对应的a(f(h))-a(f(h-1))的密文的顺序连续。因此，如果第九集合的密文被回复，且表示与复制源的元素对应的a(f(h))-a(f(h-1))的密文的顺序的元素被回复，则有关第一集合的哪一个元素是复制源的元素的信息有所泄漏。对此，如果如上述那样通过秘密计算进行随机置换后得到表示顺序的元素，则不会泄漏这样的信息。

另外，在各实施方式中，在获得“第二集合密文”以及“第三集合的密文”的情况下，第一运算部通过秘密计算而获得第二集合的密文，第二运算部利用第二集合的密文，通过秘密计算而获得第三集合的密文。

以下，参照附图详细说明各实施方式。

在各实施方式中，将某信息α的密文记为“α”。例如，通过秘密共享而隐匿化的“α”是秘密共享的片断(分享(share))，通过加密而隐匿化后的“α”是密码文。将向量β的第s元素记为β(s)，将对向量β的各元素β(s)进行隐匿化后的向量整体记为“β”，称为向量β的密文“β”。

此外，在各实施方式中，说明将以元素a(1),……,a(N)作为第一、……第N元素的N维的向量a设为第一集合，将以元素a₅(1),……,a₅(N)作为第一、……第N元素的N维的向量a₅设为第二集合，将以元素b(1),……,b(N)作为第一、……第N元素的N维的向量b设为第三集合的例子。这些N维向量的各元素作为第一、……第N元素分别被排序。以下，例示N＝10、M＝4的情况下的向量a、a₅、以及b。

[数1]

$a=\left(\begin{array}{c}w\\ *\\ *\\ x\\ y\\ *\\ *\\ *\\ z\\ *\end{array}\right),a_5=\left(\begin{array}{c}w\\ 0\\ 0\\ x-w\\ y-x\\ 0\\ 0\\ 0\\ z-y\\ 0\end{array}\right),b=\left(\begin{array}{c}w\\ w\\ w\\ x\\ y\\ y\\ y\\ y\\ z\\ z\end{array}\right)---\left(1\right)$

其中，作为向量a的第一、第四、第五、第九元素即w、x、y、z分别为复制源的元素，其他的元素*是并非复制源的元素。另外“*”表示任意的元素。此外，在本例中2≤M<N，但即使2≤M≤N也能进行本实施方式的处理。

[第一实施方式]

在本方式中，说明所述事先计算方式的具体例。

<结构例>

如图1例示，本方式的秘密计算系统1具有一个以上的元素复制装置11-1～K。其中，在通过秘密共享而进行隐匿化的情况下K是2以上的整数，在通过加密而进行隐匿计算的情况下K是1以上的整数。如图2A例示，本方式的元素复制装置11-k(其中，k∈{1,……,K}具有存储部111-k、加法逆元运算部113-k、输入信息运算部114-k(第一运算部)、累加运算部115-(第二运算部)、以及控制部116-k。如图2B例示，本方式的输入信息运算部114-k具有复制源控制部1141-k、复制源信息生成部1142-k以及乘法运算部1143-k。另外，元素复制装置11-k例如是通过在具有CPU(中央处理单元)等处理器(硬件/处理器)、RAM(随机存取存储器)、ROM(只读存储器)等存储器等的通用或专用计算机中写读入规定的程序而构成的装置，基于控制部116-k的控制而执行各处理。该计算机可以具有一个处理器和存储器，也可以具有多个处理器和存储器。该程序可以安装在计算机中，也可以预先记录在ROM等中。此外，也可以利用不使用程序就实现处理功能的电子电路来构成一部分或所有的处理部，而不是利用如CPU那样通过读取程序而实现功能结构的电子电路(circuitry)。此外，构成一个装置的电子电路也可以包含多个CPU。

<事先计算>

在本方式中，设并不是向量a(第一集合)被输入到元素复制装置11-k，而是仅由复制源的元素a(f(1)),……,a(f(M))组成的向量d₁的密文[d₁](第五集合的密文或第六集合的密文)被输入到元素复制装置11-k，并被存储在存储部111-k中。另外，向量d₁的各元素a(f(1)),……,a(f(M))是被进行了按照向量a的元素a(1),……,a(N)的顺序的排序后的向量。本方式的例子的情况下，向量d₁的第j元素d₁(j)是d₁(j)＝a(f(j))(其中，j∈{1,……,M})。另外，事先决定了向量a的大小N以及元素a(1),……,a(N)的顺序(在本方式中，a(1),……,a(N)是N维向量的第一、……、第N元素)。

如图2B所示，加法逆元运算部113-k(图2A)从存储部111-k提取向量d₁的密文[d₁]，通过秘密计算，获得将在向量d₁中包含的复制源的元素a(f(h))变为a(f(h))-a(f(h-1))(其中，h∈{2,……,M})，将复制源的元素a(f(1))维持原样的向量d₂(第四集合)的密文[d₂]。即，向量d₂的元素d₂(h)(其中，h∈{2,……,M})是元素d₂(h)＝d₁(h)-d₁(h-1)，向量d₂(1)是d₂(1)＝d₁(1)(步骤S113)。加法逆元运算部113-k输出向量d₂的密文[d₂]，向量d₂的密文[d₂]被存储在存储部111-k(步骤S111)。另外，在式(1)中例示的向量a的情况下，向量a、d₁、d₂的关系成为如下。

[数2]

$a=\left(\begin{array}{c}w\\ *\\ *\\ x\\ y\\ *\\ *\\ *\\ z\\ *\end{array}\right),d_1=\left(\begin{array}{c}w\\ x\\ y\\ z\end{array}\right),d_2=\left(\begin{array}{c}w\\ x-w\\ y-x\\ z-y\end{array}\right)$

<元素复制>

利用图2C说明本方式的元素复制的处理。输入信息运算部114-k从存储部111-k提取向量d₂(第四集合)的密文[d₂]。输入信息运算部114-k利用向量d₂的密文[d₂]，通过秘密计算，针对h＝2,……,M，获得将向量a的复制源的元素a(f(h))变为元素a(f(h))-a(f(h-1))且将复制源以外的元素变为零而获得的、将元素a₅(1),……,a₅(N)设为第一、……N元素的N维的向量即向量a₅(第二集合)的密文[a₅]。在本方式的例子中，预先决定了向量a的元素a(1),……,a(N)的顺序，还决定各复制源的元素a(f(h))的顺序(在向量a中的位置)。输入信息运算部114-k据此获得并输出在向量a的各复制源的元素a(f(h))的位置上配置元素a(f(h))-a(f(h-1))，且在其他的位置配置了零的N维的向量即a₅的密文[a₅](步骤S114)。

累加运算部115-k利用向量a₅(第二集合)的密文[a₅]，通过秘密计算，获得并输出第一元素为b(1)＝a₅(1)且第i＝2,……,N元素为b(i)＝b(i-1)+a₅(i)的N维向量即向量b(第三集合)的密文[b](步骤S115)。累加运算部115-k例如首先进行获得b(1)＝a₅(1)的密文[b(1)]的秘密计算，此后，一边将i从i＝2起逐一增加，一边针对各i＝2,……,N进行获得b(i)＝b(i-1)+a₅(i)的密文[b(i)]的秘密计算，从而获得向量b的密文[b]。

例如，当式(1)例示的向量a的情况下，上述的向量a₅、b的关系成为如以下那样。

[数3]

$a_5=\left(\begin{array}{c}w\\ 0\\ 0\\ x-w\\ y-x\\ 0\\ 0\\ 0\\ z-y\\ 0\end{array}\right),b=\left(\begin{array}{c}w\\ w\\ w\\ x\\ y\\ y\\ y\\ y\\ z\\ z\end{array}\right)$

[第一实施方式的变形例1]

在第一实施方式中，示出了如下的例子：被进行了沿着向量a的元素a(1),……,a(N)的顺序的排列的向量d₁的密文[d₁]被输入到元素复制装置11-k，且被存储在存储部111-k。在变形例中，说明如下情况下的处理：仅由复制源的元素a(f(1)),……,a(f(M))组成但这些没有成为沿着向量a的元素a(1),……,a(N)的顺序的顺序的向量d的密文[d]被输入到元素复制装置11-k，且被存储在存储部111-k。

本变形例的秘密计算系统1’的元素复制装置11’-k对第一实施方式的元素复制装置11’-k追加了分类部112’-k(图1以及图2A)。分类部112’-k从存储部111-k提取向量d的密文[d]，并通过秘密计算对向量d的密文[d]进行分类，获得并输出被进行了沿着向量a的元素a(1),……,a(N)的顺序的排序的向量d₁的密文[d₁](图2B/步骤S112’)。向量d₁的密文[d₁]被输入到加法逆元运算部113-k。此外如在第一实施方式中说明那样。例如，在式(1)例示的向量a的情况下，向量a、d、d₁、d₂的关系成为如以下那样。

[数4]

$a=\left(\begin{array}{c}w\\ *\\ *\\ x\\ y\\ *\\ *\\ *\\ z\\ *\end{array}\right),d=\left(\begin{array}{c}x\\ z\\ y\\ w\end{array}\right),d_1=\left(\begin{array}{c}w\\ x\\ y\\ z\end{array}\right),d_2=\left(\begin{array}{c}w\\ x-w\\ y-x\\ z-y\end{array}\right)$

[第一实施方式的变形例2]

在第一实施方式以及第一实施方式的变形例1中，以向量的密文作为处理对象进行了秘密计算。但是，针对可以公开的向量，也可以代替将向量的密文作为处理对象的情况而以作为明文的向量作为处理对象，代替进行秘密计算的情况而进行对于作为明文的向量的运算。例如，当可以公开向量d的情况下，可以由分类部112’-k对向量d进行分类而获得向量d₁。例如，在可以公开向量d₁的情况下，也可以由加法逆元运算部113-k利用向量d₂计算向量d₁，输入信息运算部114-k直接利用向量d₂。此外，例如也可以由加法逆元运算部113-k利用向量d₂计算向量a₅。也可以由累加运算部115-k利用向量a₅计算向量b。此外，也可以对运算结果的向量进行隐匿化而输出。

[第二实施方式]

在本方式中，说明所述的事后计算方式的具体例。

<结构>

如图1例示那样，本方式的秘密计算系统2具有一个以上的元素复制装置12-1～K。如图3A例示那样，本方式的元素复制装置21-k(其中，k∈{1,……,K})具有存储部211-k、顺序信息生成部212-k、输入信息运算部214-k(第一运算部)、累加运算部115-k(第二运算部)、以及控制部116-k。输入信息运算部214-k具有稳定分类部2141-k、加法逆元运算部2142-k、分类部2143-k、以及乘法运算部2144-k。如图3B例示那样，分类部2143-k具有随机置换部2143a-k、恢复部2143b-k、以及顺序恢复部2143c-k。另外，累加运算部115-k与在第一实施方式中说明的相同。元素复制装置21-k例如是通过对通用或专用的计算机读入规定的程序而构成的装置，基于控制部216-k的控制执行各处理。

<元素复制>

利用图4A说明本方式的元素复制的处理。

作为前提，设向量a(第一集合)的密文[a]、以及表示向量a的元素a(1),……,a(N)是否为复制源的元素的向量c的密文[c]被输入到元素复制装置21-k，并被存储在存储部211-k。另外，向量c的第n元素是其中，在a(n)是复制源的元素时在不是复制源的元素时例如，当式(1)例示的向量a的情况下，向量a、c的关系成为以下那样。

[数5]

$a=\left(\begin{array}{c}w\\ *\\ *\\ x\\ y\\ *\\ *\\ *\\ z\\ *\end{array}\right),c=\left(\begin{array}{c}1\\ 0\\ 0\\ 1\\ 1\\ 0\\ 0\\ 0\\ 1\\ 0\end{array}\right)$

首先，顺序信息生成部212-k(图3A)生成成为向量a的各元素a(n)(其中，n∈{1,……,N})的顺序(位置)的标记的向量p的密文[p]而输出(步骤S212)。向量p只要是由互相不同的N个元素p(a(n))(其中，n∈{1,……,N})(例如，预先决定的元素)组成的N维向量即可，例如只要设为p(a(n))＝n-1(其中，n∈{1,……,N}即可。向量p的密文[p]存储在存储部211-k。例如，当向量a是式(1)例示的向量，且p(a(n))＝n-1的情况下，向量a、c、p的关系成为如以下那样。

[数6]

$a=\left(\begin{array}{c}w\\ *\\ *\\ x\\ y\\ *\\ *\\ *\\ z\\ *\end{array}\right),c=\left(\begin{array}{c}1\\ 0\\ 0\\ 1\\ 1\\ 0\\ 0\\ 0\\ 1\\ 0\end{array}\right),p=\left(\begin{array}{c}0\\ 1\\ 2\\ 3\\ 4\\ 5\\ 6\\ 7\\ 8\\ 9\end{array}\right)$

输入信息运算部214-k从存储部211-k提取向量a(第一集合)的密文[a]、向量p的密文[p]、以及向量c的密文[c]，通过秘密计算而获得并输出向量a₅(第二集合)的密文[a₅]。(步骤S214)。

《步骤S214的细节》

利用图4B说明步骤S214的细节。

在本方式中，首先，稳定分类部2141-k从存储部211-k提取向量a的密文[a]与向量p的密文[p]。稳定分类部2141-k利用所提取的向量a的密文[a]以及向量p的密文[p]，通过秘密计算，获得并输出向量a₁(第七集合)的密文[a₁]以及向量p₁(第九集合)的密文[p₁]，该向量a₁是作为是否为复制源的分类条件而进行了在向量a中包含的元素a(1),……,a(N)的稳定分类而获得的向量，向量p₁由根据该元素a(1),……,a(N)的稳定分类而对向量p的元素p(a(1)),……,p(a(n))进行分类而获得的元素组成(步骤S2141)。其中，向量a₁成为仅包含元素a(1),……,a(N)，且复制源的元素a(f(1)),……,a(f(M))的顺序连续的向量。即，向量a₁仅包含元素a(1),……,a(N)且向量a₁的第η,……,η+M-1元素是复制源的元素a(f(1)),……,a(f(M))且除此之外的元素是并非复制源的元素。其中，η是1以上且N+1-M以下的整数。此外，“第η元素”意味着第η个元素。例如，可以是向量a₁的第1、……、M元素为复制源的元素a(f(1)),……,a(f(M))且除此之外的元素是并非复制源的元素，也可以是向量a₁的第N-M+1,……,N元素是复制源的元素a(f(1)),……,a(f(M))且除此之外的元素是并非复制源的元素。该稳定分类在维持向量a的元素a(n)与向量p的元素p(a(n))的对应而进行。换言之，保持元素a(n)与元素p(a(n))的对应关系。例如，当通过该稳定分类，元素a(n)成为向量a₁的第n’个(其中，n是1以上且N以下的整数)的元素的情况下，处于与元素a(n)对应的元素p(a(n))成为向量p₁的第n’个元素的关系。只是，这是在明文中的元素的顺序，不限定为被隐匿的要素一定是该顺序。例如，当向量a是式(1)例示的向量，且p(a(n))＝n-1，且向量a₁的第一、……、M元素是复制源的元素a(f(1)),……,a(f(M))，且除此之外的要素不是复制源的要素的情况下，向量a₁、p₁的关系成为如以下那样。

[数7]

$a_1=\left(\begin{array}{c}w\\ x\\ y\\ z\\ *\\ *\\ *\\ *\\ *\\ *\end{array}\right),p_1=\left(\begin{array}{c}0\\ 3\\ 4\\ 8\\ 1\\ 2\\ 5\\ 6\\ 7\\ 9\end{array}\right)---\left(2\right)$

加法逆元运算部2142-k利用向量a₁(第七集合)的密文[a₁]，通过秘密计算，获得并输出将在向量a₁中包含的元素a₁(1)、a₁(2)、……、a₁(N)变为元素a₂(1)＝a₁(1)、a₂(2)＝a₁(2)-a₁(1)、……、a₂(N)＝a₁(N)-a₁(N-1)的N维的向量即向量a₂(第八集合)的密文[a₂](步骤S2142)。例如，当为式(2)例示的向量a₂的情况下，向量p₁、a₁、a₂的关系成为如以下那样。

[数8]

$p_1=\left(\begin{array}{c}0\\ 3\\ 4\\ 8\\ 1\\ 2\\ 5\\ 6\\ 7\\ 9\end{array}\right),a_1=\left(\begin{array}{c}w\\ x\\ y\\ z\\ *\\ *\\ *\\ *\\ *\\ *\end{array}\right),a_2=\left(\begin{array}{c}w\\ x-w\\ y-x\\ z-y\\ *\\ *\\ *\\ *\\ *\\ *\end{array}\right)---\left(3\right)$

分类部2143-k利用向量a₂(第八集合)的密文[a₂]以及向量p₁(第九集合)的密文[p₁]，通过秘密计算，获得并输出将向量a₂的元素进行分类而得到的N维的向量即向量a₄的密文[a₄](步骤S2143)。其中，向量a₄、向量a₂的元素的顺序是重新排列为与向量a的元素的顺序对应的原来的顺序而得到的向量。即，向量a₄是将向量a₂的元素a(f(h))-a(f(h-1))变为向量a的复制源的元素a(f(h))的顺序，将向量a₂的元素a(f(1))变为向量a的复制源的元素a(f(1))的顺序，将向量a₂的其他的元素返回到与其对应的向量a的原来的顺序而获得的向量。

《步骤S2143的细节》

利用图4C说明步骤S2143的细节。

分类部2143-k的随机置换部2143a-k利用向量a₂(第八集合)的密文[a₂]以及向量p₁(第九集合)的密文[p₁]，通过秘密计算，获得并输出与N维的向量a₃(第十集合)以及N维的向量p₃(第十一集合)分别对应的向量a₃的密文[a₃]以及向量p₃的密文[p₃]，其中N维的向量a₃(第十集合)以及N维的向量p₃(第十一集合)是维持向量a₂的元素a₂(n)与向量p₁的元素p₁(n)的对应关系(其中，n∈[1,……,N])，并随机置换向量a₂的元素a₂(1)、……、a₂(N)的顺序以及向量p₁的元素p₁(1)、……、p₂(N)而得到的(步骤S2143a)。其中，向量a₃是重新排列了向量a₂的元素a₂(1)、……、a₂(N)的顺序的向量，向量p₃是重新排列了向量p₁的元素p₁(1)、……、p₁(N)的顺序的向量。换言之，随机置换部2143a-k利用向量a₂(第八集合)的密文[a₂]以及向量p₁(第九集合)的密文[p₁]，通过秘密计算，获得并输出向量a₃的密文[a₃]以及向量p₃的密文[p₃]。向量a₃是重新排列了向量a₂的元素a₂(1)、……、a₂(N)的顺序而得到的向量，向量p₃是重新排列了向量p₁的元素p₁(1)、……、p₂(N)的顺序而得到的向量。在该处理中维持a₂(n)与元素p₁(n)的对应关系。例如，当通过该随机置换而元素a₂(n)成为向量a₃的第n’个元素的情况下，处于元素p₁(n)成为向量p₃的第n’个元素。只是，这是在明文中的元素的顺序，不限定为被隐匿的元素一定成为该顺序。当为式(3)例示的向量p₁、a₂的情况下，向量p₃、a₃的关系例如成为如以下那样。

[数9]

$p_3=\left(\begin{array}{c}4\\ 0\\ 2\\ 1\\ 6\\ 3\\ 7\\ 5\\ 9\\ 8\end{array}\right),a_3=\left(\begin{array}{c}y-x\\ w\\ *\\ *\\ *\\ x-w\\ *\\ *\\ *\\ z-y\end{array}\right)---\left(4\right)$

恢复部2143b-k根据向量p₃的密文[p₃]恢复向量p₃而输出(步骤s2143b)。

顺序恢复部2143c-k利用向量a₃的密文[a₃]，通过秘密计算，获得并输出将向量a₃的元素按照向量p₃进行分类而得到的N维的向量即向量a₄的密文[a₄](步骤S2143c)。向量a₄是将向量a₃的元素重新排列为与向量a的元素的顺序对应的原来的顺序而得到的向量。该顺序能够根据向量p₃的元素判断(参照式(4))。即，通过将向量p₃的元素的顺序重新排列为向量p的元素的顺序的分类，重新排列向量a₃的元素而得到的N维的向量是向量a₄。当为式(4)例示的向量p₃、a₃的情况下，向量a₄例如成为如以下那样(《步骤S2143的细节》的说明结束)。

[数10]

$a_4=\left(\begin{array}{c}w\\ *\\ *\\ x-w\\ y-x\\ *\\ *\\ *\\ z-y\\ *\end{array}\right)---\left(5\right)$

乘法运算部2144-k利用向量a₄的密文[a₄]以及向量c的加密文[c]，通过秘密计算，获得并输出以向量a₄的元素a₄(n)与向量c的元素c(n)的乘法运算结果(例如，乘法结果或乘法结果的余数)作为元素a₅(n)(其中，n∈[1,……,N])而得到的向量a₅(第二集合)的密文[a₅](步骤S2144)。另外，元素a₄(n)是向量a₄的第n个元素，元素c(n)是向量c的第n个元素，元素a₅(n)是向量a₅的第n个元素。该处理用于获得将向量a₄的不是复制源的元素变为零的向量a₅的密文[a₅]的处理。例如，当为与式(1)例示的向量a对应的向量c、以及式(5)例示的向量a₄的情况下，向量a₄、c、a₅的关系成为如以下那样(《步骤S214的细节》的说明结束)。

[数11]

$a_4=\left(\begin{array}{c}w\\ *\\ *\\ x-w\\ y-x\\ *\\ *\\ *\\ z-y\\ *\end{array}\right),c=\left(\begin{array}{c}1\\ 0\\ 0\\ 1\\ 1\\ 0\\ 0\\ 0\\ 1\\ 0\end{array}\right),a_5=\left(\begin{array}{c}w\\ 0\\ 0\\ x-w\\ y-x\\ 0\\ 0\\ 0\\ z-y\\ 0\end{array}\right)---\left(6\right)$

向量a₅的密文[a₅]被输入到累加运算部115-k，被执行在第一实施方式中说明过的处理，获得向量b的密文[b]。例如，当为式(6)的向量a₅的情况下，向量a₅、b的关系成为如以下那样。

[数12]

$a_5=\left(\begin{array}{c}w\\ 0\\ 0\\ x-w\\ y-x\\ 0\\ 0\\ 0\\ z-y\\ 0\end{array}\right),b=\left(\begin{array}{c}w\\ w\\ w\\ x\\ y\\ y\\ y\\ y\\ z\\ z\end{array}\right)$

[第二实施方式的变形例1]

在第二实施方式中，分类部2143-k通过秘密计算进行包含随机置换的分类。在本变形例中，代替此，通过秘密计算进行不包含随机置换的分类。除此之外，与第二实施方式相同。

本变形例的秘密计算系统2’的元素复制装置21’-k的输入信息运算部214-k代替第二实施方式的分类部2143-k而具有分类部2143’-k(图3A)。分类部2143’-k利用向量a₂(第八集合)的密文[a₂]以及向量p₁(第九集合)的密文[p₁]，通过秘密计算，获得并输出对向量a₂的元素进行分类而得到的N维的向量即向量a₄的密文[a₄](步骤S2143’)。只是，不同于步骤S2143，分类部2143’-k不执行所述的步骤S2143a、S2143b，而是利用向量p₁的密文[p₁]，获得并输出向量a₄的密文[a₄]。分类部2143’-k可以利用根据向量p₁的密文[p₁]而恢复的向量p₁，通过秘密计算而获得向量a₄的密文[a₄]，也可以不恢复向量p₁的密文[p₁]，通过秘密计算而获得向量a₄的密文[a₄]。

[第二实施方式的变形例2]

在第二实施方式以及第二实施方式的变形例1中，以向量的密文作为处理对象进行了秘密计算。但是，针对可以公开的向量，代替以向量的密文作为处理对象的情况，而是以作为明文的向量作为处理对象，代替进行秘密计算的情况，而是进行对于作为明文的向量的运算。例如，顺序信息生成部212-k可以输出向量p，稳定分类部2141-k也可以进行向量a、p的稳定分类而获得向量a₁、p₁而输出，加法逆元运算部2142-k也可以根据向量a₁而获得向量a₂而输出，分类部2143-k或2143’-k也可以利用向量a₂、p₁获得向量a₄而输出，乘法运算部2144-k也可以利用向量向量a₄、c获得向量a₅而输出。

[特征]

如以上那样，通过预先将复制源的元素置换为该复制源的元素与其前一个复制源的元素的加法逆元之间的加法运算结果(例如减法结果)，能够将复制的处理以作为非常简单的运算的加法运算(例如加法)实现较多的处理。其结果，能够比以往降低运算成本。另外，根据向量a₄或密文[a₄]获得向量a₅或密文[a₅]需要一阶乘法等乘法运算，但其阶数不依赖于N。尤其如第一实施方式那样能够对复制源的元素进行事先处理的情况下，元素复制时的复制所需的计算仅成为Ο(N)次加法运算。

[变形例等]

另外，本发明并不限定于上述的实施方式。例如，上述的各种处理不仅按照记载时序地执行，可以根据执行处理的装置的处理能力或者根据需要而并行地或者单独执行。此外，在不脱离本发明的宗旨的范围内，当然可以适当进行变更。

在通过计算机来实现上述的结构的情况下，通过程序来记录各装置应具有的功能的处理内容。通过由计算机来执行该程序，在计算机上实现上述处理功能。该记录了处理内容的程序能够预先记录在能够由计算机读取的记录介质中。能够由计算机读取的记录介质的例子是非暂时性的(non-transitory)记录介质。这样的记录介质的例子是磁记录装置、光盘、光磁记录介质、半导体存储器等。

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

执行这样的程序的计算机例如首先将记录在可移动记录介质中的程序或者从服务器计算机转发的程序临时存储在自己的存储装置中。在执行处理时，该计算机读取在自己的记录装置中存储的程序，按照所读取的程序执行处理。作为该程序的其他的执行方式，也可以设为由计算机从可移动记录介质直接读取程序，并执行按照该程序的处理，进而，也可以设为在每次从服务器计算机向该计算机转发程序时，依次执行按照所接受的程序的处理。也可以设为如下的结构：不进行程序从服务器计算机向该计算机的转发，而是通过由仅其执行指示与结果取得来实现处理功能的、所谓的ASP(Application Service Provider)型的服务来执行上述的处理。

在上述实施方式中，在计算机中执行规定的程序而实现了本装置的处理功能，但这些处理功能的至少一部分也可以通过硬件来实现。

产业上的可利用性。

本发明例如能够用于表计算领域等，尤其能够用于进行将被隐匿化的表的一部分元素保持隐匿化的状态而直接复制的计算的软件领域(加密技术领域)等。例如，在加密技术领域中利用的集合的元素复制处理(表计算处理等)中能够利用本发明。

标号说明

秘密计算系统1、1’、2、2’

元素复制装置11-k、11’-k、21-k、21’-k