秘密结合系统、方法、秘密计算装置以及程序

摘要

秘密结合系统是包含多个秘密计算装置的秘密结合系统，多个秘密计算装置包括向量结合部(11n)、第一置换计算部(12n)、第一置换应用部(13n)、第一向量生成部(14n)、第二向量生成部(15n)、比特反转部(16n)、第二置换计算部(17n)、第二置换应用部(18n)、第三向量生成部(19n)、逆置换应用部(110n)、向量分离部(111n)、第三置换应用部(112n)、属性值置换部(113n)以及第四向量生成部(114n)。

说明书

技术领域

本发明涉及秘密计算技术。本发明尤其涉及在保持隐匿性的状态下将2个表格结合的技术。

背景技术

在秘密计算技术领域中，寻求在保持隐匿性的状态下将2个表格结合的技术。

作为在保持隐匿性的状态下将2个表格结合的技术，已知例如非专利文献1所记载的技术。在非专利文献1中实现了存在键(key)重复的情况下的等结合(equalcombination)。

现有技术文献

非专利文献

非专利文献1：桐淵直人，五十嵐大，諸橋玄武，濱田浩気，“属性情報と履歴情報の秘匿統合分析に向けた秘密計算による高速な等結合アルゴリズムとその実装”，CSS2016，2016

发明内容

发明要解决的课题

本发明提供在不存在键重复的情况下比非专利文献1的技术更高速地在保持隐匿性的状态下将2个表格结合的秘密结合系统、方法、秘密计算装置以及程序。

用于解决课题的手段

基于本发明的一方式的秘密结合系统是包含多个秘密计算装置的秘密结合系统，F是任意的环，将α设为任意的向量，[α]是α被进行秘密分散后的份额，将β设为任意的置换，{{β}}是β被进行秘密分散后的份额，m

发明效果

通过使用逆置换，在不存在键重复的情况下能够比非专利文献1的技术更高速地在保持隐匿性的状态下将2个表格结合。

附图说明

图1是例示秘密结合系统的功能结构的图。

图2是例示秘密计算装置的功能结构的图。

图3是例示秘密结合方法的处理过程的图。

图4是表示计算机的功能结构例的图。

具体实施方式

以下，对本发明的实施方式进行详细说明。另外，对附图中具有相同的功能的结构部附加相同的编号，省略重复说明。

参照图1，对实施方式的秘密结合系统的结构例进行说明。秘密结合系统包含N(≥2)台秘密计算装置1

参照图2，对秘密结合系统所包含的秘密计算装置1

通过秘密计算装置1

另外，各步骤的处理通过秘密计算来进行。即，秘密计算装置1

秘密计算装置1

在以下的说明中，设α为任意的向量而[α]是α被进行秘密分散后的份额，设β为任意的置换而{{β}}是β被进行秘密分散后的份额。

参照图3，对实施方式的秘密结合系统所执行的秘密结合方法的处理过程进行说明。

以下说明的秘密结合系统将第一表格和第二表格秘密垂直结合。换言之，以下说明的秘密结合系统保持隐匿性、且得到关于第一表格以及第二表格的共同的键的、第一表格的属性值以及第二表格的属性值。

设m

第一表格具有m

[F]

第二表格有m

例如，设第一表格的记录数为3，由键的向量k

此外，设第二表格的记录数为4，由键的向量k

＜步骤S1＞

向量k

向量结合部11

更详细而言，向量结合部11

所生成的份额[k']被输出给第一置换计算部12

例如，设向量k

＜步骤S2＞

份额[k']被输入给第一置换计算部12

第一置换计算部12

更详细而言，第一置换计算部12

稳定排序是指同等的数据的排序前的顺序在排序后也被保存的情况。进行稳定排序的置换σ的份额{{σ}}的生成例如能够通过参考文献1的方法来实现。

〔参考文献1〕五十嵐大、濱田浩気、菊池亮、千田浩司、「超高速秘密計算ソートの設計と実装：秘密計算がスクリプト言語に並ぶ日」、CSS2017、2017

所生成的份额{{σ}}被输出给第一置换应用部13

例如，设向量k'＝(1,2,3,1,3,4,5)

[算式1]

另外，向量k'的各要素也可以是被进行比特分解后的要素。即，对于向量k'的各要素而言，该各要素也可以是用0,1的比特来表现的要素。

＜步骤S3＞

份额[k']以及份额{{σ}}被输入给第一置换应用部13

第一置换应用部13

更详细而言，第一置换应用部13

所生成的份额[σ(k')]被输出给第一向量生成部14

例如，设向量k'＝(1,2,3,1,3,4,5)

＜步骤S4＞

份额[σ(k')]被输入给第一向量生成部14

第一向量生成部14

另外，设若将向量的要素数设为M，则将向量的最先的要素称为第0个要素，将向量的下一个要素称为第1个要素，将向量的最后的要素称为第M-1个要素。

更详细而言，第一向量生成部14

所生成的份额[e]被输出给第二向量生成部15

例如，设向量σ(k')＝(1,1,2,3,3,4,5)

＜步骤S5＞

份额[e]被输入给第二向量生成部15

第二向量生成部15

更详细而言，第二向量生成部15

所生成的份额[e']被输出给比特反转部16

例如，设向量e＝(1,0,0,1,0,0,0)

＜步骤S6＞

份额[e']被输入给比特反转部16

比特反转部16

更详细而言，比特反转部16

所生成的份额[e”]被输出给第二置换计算部17

例如，设e'＝(1,1,0,1,1,0,0)

另外，在向量k'的各要素是被进行比特分解后的要素的情况下，e”的环也可以通过例如mod P变换而被变更。P是3以上的质数。mod P变换例如能够通过参考文献1的Scheme5所记载的方法实现。

＜步骤S7＞

份额[e”]被输入给第二置换计算部17

第二置换计算部17

更详细而言，第二置换计算部17

所生成的份额{{σ'}}被输出给第二置换应用部18

例如，设向量e”＝(0,0,1,0,0,1,1)

[算式2]

＜步骤S8＞

份额[e”]以及份额{{σ'}}被输入给第二置换应用部18

第二置换应用部18

更详细而言，第二置换应用部18

所生成的份额[σ'(e”)]被输出给第三向量生成部19

例如，设向量e”＝(0,0,1,0,0,1,1)

＜步骤S9＞

份额[σ'(e”)]被输入给第三向量生成部19

第三向量生成部19

更详细而言，第三向量生成部19

这里，i＝0,…,m

所生成的份额[x]被输出给逆置换应用部110

例如，设向量σ'(e”)＝(0,0,0,0,1,1,1)

＜步骤S10＞

份额[x]、份额{{σ}}以及份额{{σ'}}被输入给逆置换应用部110

逆置换应用部110

更详细而言，逆置换应用部110

所生成的份额[σ

例如，设向量x＝(1,1,2,2,0,0,0)

＜步骤S111＞

份额[σ

向量分离部111

更详细而言，向量分离部111

所生成的份额[s

例如，设向量σ

向量s

＜步骤S12＞

份额[s

第三置换应用部112

更详细而言，第三置换应用部112

置换π

所生成的份额[π

例如，设向量s

[算式3]

在该情况下，成为向量τ

＜步骤S13＞

份额[v

属性值置换部113

更详细而言，属性值置换部113

所生成的份额[v'

例如，设第一表格的属性z1的向量v

＜步骤S14＞

向量τ

第四向量生成部114

更详细而言，第四向量生成部114

例如，设向量τ

由于向量s

在上述的例子中，向量τ

同样，在上述的例子中，向量τ

因此，通过在(τ

此外，能够将第二表格的键“1”的记录的属性z1'的属性值“2”作为向量v”

换言之，向量v”

此外，向量v”

这样，可以说，向量v”

根据该实施方式，能够在保持隐匿性的状态下得到关于第一表格以及第二表格的共同的键的、第一表格的属性值以及第二表格的属性值。

[变形例]

另外，也可以将x设为2以上的正整数，键的属性是x个属性的复合键。在该情况下，例如也可以如以下那样进行步骤S1的处理。

设第一表格的键为k

在该情况下，在步骤S1的处理中，对于各i(其中，i＝0,…,x-1)将k

这里，由于k'

[算式4]

若将这样排列后的表现视为矩阵，将该矩阵的各行视为1记录的键的比特表现，则得到(1,2,3,1,3,4,5)这样的键的比特表现的向量。也可以将该向量用作在步骤S2以后使用的k'。这样，在复合键的情况下也能够进行处理。

就复合键而言，设键的重复是指从全部键属性的值的组合的角度来看是否重复，若只是各个属性的值重复则不视为重复。例如，组合(1,0)和(1,1)不重复。

以上，对本发明的实施方式进行了说明，但是不言而喻，具体的结构不限于这些实施方式，即使在不脱离本发明的宗旨的范围内存在适当设计的变更等，也包含于本发明。

在实施方式中说明过的各种处理不仅可以基于记载的顺序按时间序列执行，也可以根据执行处理的装置的处理能力或者根据需要来并行地或者单独地执行。

[程序、记录介质]

上述的各种处理能够通过在图4所示的计算机的记录部2020中读入使上述方法的各步骤执行的程序，使控制部2010、输入部2030、输出部2040等进行操作来实施。

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

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

执行这样的程序的计算机例如首先将记录在便携式记录介质中的程序或者从服务器计算机转发的程序暂时储存在自身的存储装置中。然后，在执行处理时，该计算机读取自身的存储装置所储存的程序，执行基于所读取的程序的处理。此外，作为该程序的其他执行方式，也可以是，计算机从便携式记录介质直接读取程序，执行基于该程序的处理，进一步，还可以是，每当该计算机被从服务器计算机转发程序时，依次执行基于所接受的程序的处理。此外，也可以设为通过不进行从服务器计算机向该计算机的程序的转发而仅通过其执行指示和结果获取来实现处理功能的、所谓ASP(应用服务提供商(Application ServiceProvider))型的服务而执行上述的处理的结构。另外，设在本方式中的程序中包含用于基于电子计算机的处理的信息且近似等效于程序的信息(不是对于计算机的直接的指令，但是是具有对计算机的处理进行规定的性质的数据等)。

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