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

Abstract

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

Description

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

技术领域

本发明涉及秘密计算技术以及隐私(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_{b_c}”表示b_c以下标方式附加给a。

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

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

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

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

在沙米尔的秘密分散法中，首先，对于位数p的有限域Z_p上的秘密s，选择有限域Z_p上的t-1次多项式f(x)＝r_t-1x^t-1+…+r₁x¹+s。其中，各r_i是有限域Z_p上的随机值。此时，能够获得秘密s的份额[s]₁,…,[s]_n的每一个，作为例如作为[s]_i＝f(i)。在复原秘密s的情况下，使用不重复的任意的t个以上的份额进行多项式插值，求出多项式f(x)的常数项s。

<伪随机秘密分散>

伪随机秘密分散是使用伪随机函数，不经由通信而生成均匀随机数的份额的方法(例如，参照参考文献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}^α→Z_p是将秘密密钥和长度α的比特串作为输入，输出(大致)均匀的有限域Z_p上的随机数的函数。这里，K表示密钥空间。另外，考虑将沙米尔的秘密分散法中的份额在n台的各方(party)P₁,…,P_n中分别分散地持有的情况。此时，如下这样，由n方共享随机数r的份额[r]₁,…,[r]_n。

1.首先，事先在一部分的各方之间共享伪随机函数的密钥。具体而言，将A设为从n方中选择了n-t+1方的集合，由集合A中包含的n-t+1方全员共享密钥k_A∈K。相反，未包含在集合A中的t-1方不获得与密钥k_A有关的信息。同样地，对于所有能够设想的集合A，共享各自不同的密钥k_A。另外，对于所有的集合A，分别共享与各自对应的t次多项式f_A。其中，假设为满足f_A(0)＝1且f_A(i)＝0(P_i不包含在集合A中时)。

2.当需要随机数生成时，各方通过例如时间戳等公共地使用的值a来进行伪随机数生成。具体而言，当各方P_i包含在集合A_j中，具有密钥集合{k_{A_j}}时，计算各方P_i的[r]_i←Σ_jPRF(k_{A_j},a)·f_{A_j}(i)。其中，将J设为各方P_i所属的集合A的数，j为1以上J以下的各整数。

通过上述的处理，各方P_i可获得的份额[r]_i成为伪随机数r＝Σ_APRF(k_A,a)的份额。

<二项分布>

已知在L比特的均匀随机数r∈{0,1}^L中所包含的1的个数成为遵循二项分布Bin(L,1/2)的随机数。如果伪随机函数PRF：K×{0,1}^α→{0,1}^L具有足够的均匀性，则可以说伪随机数PRF(k,a)中所包含的1的个数也同样遵循二项分布Bin(L,1/2)。

[实施方式]

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

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

例如如图1所示，实施方式的秘密随机数生成系统100包括n(≥3)台的秘密计算装置1₁,…,1_n。在本实施方式中，秘密计算装置1₁,…,1_n分别连接至通信网9。通信网9是构成为所连接的各装置可相互通信的线路交换方式或分组交换方式的通信网，例如能够使用因特网或LAN(局域网(Local Area Network))、WAN(广域网(Wide Area Network))等。另外，各装置未必需要能够经由通信网9以在线方式进行通信。例如，也可以构成为将输入到秘密计算装置1₁,…,1_n的信息存储在磁带或USB存储器等便携式记录介质中，从该便携式记录介质以离线方式输入到秘密计算装置1₁,…,1_n。

例如如图2所示，实施方式的秘密随机数生成系统100中包含的秘密计算装置1_i(i＝1,…,n)具有参数存储部10、伪随机数生成部11、比特计数部12、随机数份额生成部13以及输出部14。该秘密计算装置1_i(i＝1,…,n)与其他秘密计算装置1_j(j＝1,…,n，其中，i≠j)一边进行协调，一边进行后述的各步骤的处理，由此实现本实施方式的秘密随机数生成方法。

秘密计算装置1_i例如是在具有中央运算处理装置(CPU：Central ProcessingUnit(中央处理单元))、主存储装置(RAM：Random Access Memory(随机存取存储器))等的公知或专用的计算机中读入特别的程序而构成的特别的装置。秘密计算装置1_i例如在中央运算处理装置的控制下执行各处理。输入到秘密计算装置1_i的数据或通过各处理所获得的数据例如保存在主存储装置中，保存在主存储装置中的数据根据需要被读出到中央运算处理装置，用于其他处理。秘密计算装置1_i的各处理部的至少一部分也可以由集成电路等硬件构成。秘密计算装置1_i具备的各存储部例如可以由RAM(Random Access Memory(随机存取存储器))等主存储装置、由硬盘、光盘或闪存(Flash Memory)那样的半导体存储元件构成的辅助存储装置、或者由关系数据库或密钥值存储(key value store)等中间件构成。

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

在参数存储部10中存储伪随机函数PRF:K×{0,1}^α→{0,1}^L、J个密钥{k_{A_1},…,k_{A_J}}和J个多项式{f_{A_1}(x),…,f_{A_J}(x)}。

在步骤S11中，伪随机数生成部11针对1以上且J以下的各整数j，使用存储在参数存储部10中的各密钥k_{A_j}和参数a，计算伪随机函数PRF(k_{A_j},a)。参数a例如是时间戳等在所有的秘密计算装置1₁,…,1_n之间能够公共地利用的参数。伪随机数生成部11将根据各密钥k_{A_j}计算出的伪随机数p_{A_j}输出到比特计数部12。

在步骤S12中，比特计数部12针对1以上且J以下的各整数j，求出各伪随机数p_{A_j}中包含的1的个数r_{A_j}。比特计数部12将根据各伪随机数p_{A_j}求出的1的个数r_{A_j}输出到随机数份额生成部13。

在步骤S13中，随机数份额生成部13计算1的个数r_{A_j}与多项式f_{A_j}(i)的输出的积和[r]_i←Σ_jr_{A_j}·f_{A_j}(i)。其中，i是秘密计算装置的编号。该[r]_i成为随机数r＝Σ_Ar_A的份额。随机数份额生成部13将随机数r的份额[r]_i输出到输出部14。

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

关于伪随机函数PRF(k_A,a)的输出即L比特的伪随机数p_A，其中包含的1的个数r_A遵循二项分布Bin(L,1/2)。同样地，通过在各方中共享的所有密钥k_A计算出的共计N＝(nCn-t+1)×L比特的随机数中所包括的1的个数r成为遵循二项分布Bin(N,1/2)。这里，nCn-t+1表示从不同的n个中选择不同的n-t+1个的组合的数。该1的个数r满足r＝Σ_Ar_A。另外，由于这些计算全部可以在本地计算，所以不需要各方间的通信。本发明是如下发明，即通过利用该性质，各方不相互进行通信地，求出遵循二项分布Bin(N,1/2)的随机数的份额[r]_i，并且作为整个系统，生成随机数r的隐匿值[r]。

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

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

[程序、记录介质]

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

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

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

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

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

Claims (4)

1.一种秘密随机数生成系统，是包括多个秘密计算装置、生成遵循二项分布的随机数的隐匿值的秘密随机数生成系统，其中，

所述秘密计算装置包括：

存储部，用于存储伪随机函数、和至少一组密钥以及多项式；

伪随机数生成部，使用各所述密钥计算所述伪随机函数，获得与各所述密钥对应的伪随机数；

比特计数部，对各所述伪随机数中包含的1的个数进行计数；以及

随机数份额生成部，获得所述1的个数与该1的个数对应的所述多项式的输出的积和，作为所述随机数的份额。

2.一种秘密计算装置，是在生成遵循二项分布的随机数的隐匿值的秘密随机数生成系统中使用的秘密计算装置，包括：

存储部，用于存储伪随机函数、和至少一组密钥以及多项式；

伪随机数生成部，使用各所述密钥计算所述伪随机函数，获得与各所述密钥对应的伪随机数；

比特计数部，对各所述伪随机数中包含的1的个数进行计数；以及

随机数份额生成部，获得所述1的个数与该1的个数对应的所述多项式的输出的积和，作为所述随机数的份额。

3.一种秘密随机数生成方法，是由生成遵循二项分布的随机数的隐匿值的秘密随机数生成系统执行的秘密随机数生成方法，其中，

在存储部中存储伪随机函数、和至少一组密钥以及多项式，

伪随机数生成部使用各所述密钥计算所述伪随机函数，获得与各所述密钥对应的伪随机数，

比特计数部对各所述伪随机数中包含的1的个数进行计数，

随机数份额生成部获得所述1的个数与该1的个数对应的所述多项式的输出的积和，作为所述随机数的份额。

4.一种程序，用于使计算机作为权利要求2所述的秘密计算装置发挥功能。

Images