秘密随机数生成系统、秘密计算装置、秘密随机数生成方法以及程序

摘要

不经由逐次的通信而生成基于二项分布的秘密随机数。秘密计算装置(1i)生成遵照二项分布的随机数r的份额[r]i。参数存储部(10)存储伪随机函数PRF、和至少一组密钥kA以及多项式fA。伪随机数生成部(11)使用各密钥kA计算伪随机函数PRF(kA,a)，或与各密钥kA对应的伪随机数pA。比特计数部(12)对各伪随机数pA中包含的1的个数rA进行计数。随机数份额生成部(13)得到1的个数rA与1的个数rA对应的多项式fA(i)的输出的积和，作为随机数r的份额[r]i。

说明书

技术领域

本发明涉及秘密计算技术以及隐私(privacy)保护技术。

背景技术

近来，在以个人信息为代表的隐私数据的应用需求提高的过程中，能够在保持将信息设为秘密的状态下进行各种计算的秘密计算技术正在受到关注。秘密计算是富有各种应用例的有用的技术(例如，参照非专利文献1)。但是，秘密计算保证了计算结果的正确性(合法性)，所以不能覆盖被称为“输出隐私”的计算结果的隐私。为了保护输出隐私，例如需要基于随机噪声的计算结果的搅拌等，在秘密计算中，这样的搅拌、进而随机噪声的生成也成为一个技术课题。

针对这样的课题，在非专利文献2中，公开了使用秘密计算，生成遵循二项分布的秘密的随机噪声的方法。由于遵循二项分布的噪声用于满足被称为差分隐私的输出隐私保护基准，所以非专利文献2可以说是在秘密计算中实现输出隐私保护的有用的技术。

现有技术文献

非专利文献

非专利文献1：桐淵直人，五十嵐大，濱田浩気，菊池亮，“プログラマブルな秘密計算ライブラリMEVAL3”，暗号と情報セキュリティシンポジウム(SCIS)，2018年(桐渊直人，五十岚大，滨田浩气，菊池亮，“可编程的秘密计算程序库MEVAL3”，密码和信息安全研讨会(SCIS)，2018年)

非专利文献2：C.Dwork,K,Kenthapadi,F.McSherry,I.Mironov,M.Naor,"Ourdata,ourselves:privacy via distributed noise generation",Advances inCryptology,EUROCRYPT,LNCS 4004,pp.486-503,2006.

发明内容

发明要解决的课题

但是，在非专利文献2中，存在在生成噪声时，需要与噪声的值域对应的通信量的课题。噪声的值域依赖于作为保护对象的计算结果的值域和保护强度而变得极大，因此为了对任意的计算实现充分的保护强度，需要相应多的通信量。从秘密计算的高速化的观点出发，削减该通信量成为大的课题。

本发明的目的在于，鉴于上述的技术课题，不经由逐次的通信而生成遵照二项分布的秘密随机数。

用于解决课题的手段

为了解决上述课题，本发明的一方式的秘密随机数生成系统，是包括多个秘密计算装置、生成遵循二项分布的随机数的隐匿值的秘密随机数生成系统，其中，秘密计算装置包括：存储部，用于存储伪随机函数、和至少一组密钥以及多项式；伪随机数生成部，使用各密钥计算伪随机函数，获得与各密钥对应的伪随机数；比特计数部，对各伪随机数中包含的1的个数进行计数；以及随机数份额生成部，获得1的个数与该1的个数对应的多项式的输出的积和，作为随机数的份额。

发明的效果

根据本发明，能够不经由逐次的通信而生成遵照二项分布的秘密随机数。通过使用该秘密随机数进行计算结果的搅拌，能够有效地保护秘密计算中的输出隐私。

附图说明

图1是例示秘密随机数生成系统的功能结构的图。

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

图3是例示秘密随机数生成方法的处理过程的图。

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

具体实施方式

在本说明书中，下标中的“_”(下划线)表示右侧的字符以下标方式附加给左侧的字符。即，“a

首先，对本发明中作为前提的现有技术进行说明。

<沙米尔(Shamir)的秘密分散法>

沙米尔秘密分散法是通过随机的多项式f将秘密的值s分散为n个片断，并且从任意的t个片断复原秘密的值s的方法(例如，参照参考文献1)。以下，将某个值分散后得到的一个片断称为“份额”，将所有的份额的集合称为“隐匿值”。某个值·的隐匿值表示为[·]，隐匿值[·]的第i个份额表示为[·]

〔参考文献1〕A.Shamir,"How to share a secret,"Communications of theACM,Vol.22,No.11,pp.612-613,1979.

在沙米尔的秘密分散法中，首先，对于位数p的有限域Z

<伪随机秘密分散>

伪随机秘密分散是使用伪随机函数，不经由通信而生成均匀随机数的份额的方法(例如，参照参考文献2)。

〔参考文献2〕R.Cramer,I.Damgard,and Y.Ishai,"Share conversion,pseudorandom secret-sharing and applications to secure computation,"Theory ofCryptography,LNCS 3378,pp.342-362,2005.

伪随机函数PRF：K×{0,1}

1.首先，事先在一部分的各方之间共享伪随机函数的密钥。具体而言，将A设为从n方中选择了n-t+1方的集合，由集合A中包含的n-t+1方全员共享密钥k

2.当需要随机数生成时，各方通过例如时间戳等公共地使用的值a来进行伪随机数生成。具体而言，当各方P

通过上述的处理，各方P

<二项分布>

已知在L比特的均匀随机数r∈{0,1}

[实施方式]

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

实施方式的秘密随机数生成系统由N(≥3)台的秘密计算装置协调，计算遵循二项分布的随机的值的隐匿值。在本实施方式中，设想使用基于沙米尔的秘密分散法的多方计算。

例如如图1所示，实施方式的秘密随机数生成系统100包括n(≥3)台的秘密计算装置1

例如如图2所示，实施方式的秘密随机数生成系统100中包含的秘密计算装置1

秘密计算装置1

以下，参考图3，说明实施方式的秘密随机数生成系统100执行的秘密随机数生成方法的处理过程。

在参数存储部10中存储伪随机函数PRF:K×{0,1}

在步骤S11中，伪随机数生成部11针对1以上且J以下的各整数j，使用存储在参数存储部10中的各密钥k

在步骤S12中，比特计数部12针对1以上且J以下的各整数j，求出各伪随机数p

在步骤S13中，随机数份额生成部13计算1的个数r

在步骤S14中，输出部14输出随机数r的份额[r]

关于伪随机函数PRF(k

在本发明中，基于伪随机秘密分散法，不需要秘密随机数生成中的逐次的通信。此时，通过变更生成均匀随机数的伪随机秘密分散法，使得能够生成遵循二项分布的随机数，从而与现有方法相比大幅削减了通信量。这样，根据本发明，能够不经由逐次的通信而生成能够用于秘密计算结果的输出隐私保护等的遵循二项分布的秘密随机数。在现有的方法中，一直是每当秘密随机数生成时，需要与噪声的值域N成比例的量的通信。

以上，对本发明的实施方式进行了说明，但具体的结构不限于这些实施方式，在不脱离本发明的主旨的范围内，即使有适当的设计变更等，当然也包含在本发明中。在实施方式中说明的各种处理不仅可以按照记载的顺序而以时序执行，也可以根据执行处理的装置的处理能力或需要并行地或个别地执行。

[程序、记录介质]

在通过计算机实现上述实施方式中说明的各装置中的各种处理功能的情况下，各装置应具有的功能的处理内容通过程序来记述。然后，通过将该程序读入到图4所示的计算机的存储部1020中，使控制部1010、输入部1030、输出部1040等动作，在计算机上实现上述各装置中的各种处理功能。

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

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

执行这种程序的计算机例如首先将存储在便携式记录介质中的程序或从服务器计算机转发的程序暂时保存在自己的存储装置中。然后，在执行处理时，该计算机读取保存在自己的存储装置中的程序，并按照读取的程序执行处理。另外，作为该程序的另一执行方式，计算机也可以从便携式存储介质直接读取程序，执行按照该程序的处理，并且，每当程序从服务器计算机转发到该计算机时也可以依次按照所接收的程序执行处理。此外，也可以构成为，不从服务器计算机向该计算机转发程序，而仅通过该执行指示和结果取得来实现处理功能，即通过所谓的ASP(Application Service Provider，应用服务提供商)型的服务来执行上述处理。另外，在本方式的程序中，设为包含作为供电子计算机的处理使用的信息的、遵照程序的信息(不是对计算机的直接指令，但具有规定计算机的处理的性质的数据等)。

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