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

摘要

不进行近似而生成遵循离散拉普拉斯分布的秘密随机数。秘密计算装置(1i)生成遵循参数α的离散拉普拉斯分布的随机数r的隐匿值[r]。比特串生成部(11)生成由遵循概率(1‑α)/(1+α)的伯努利分布的随机数比特b0的隐匿值[b0]、和分别遵循概率(1‑α)的伯努利分布的随机数比特b1,…,bN的隐匿值[b1],…,[bN]构成的隐匿值的列[b0],[b1],…,[bN]。绝对值决定部(12)获得随机数比特b0,b1,…,bN中从开头开始观察而最初被设定了1的位置L的隐匿值[L]。代码决定部(13)获得对隐匿值[L]乘以随机的代码s的隐匿值[s]而得到的结果[L·s]，作为随机数r的隐匿值[r]。

说明书

技术领域

本发明涉及秘密计算技术及隐私(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中，通过利用几何分布对离散拉普拉斯分布进行近似来进行噪声生成，由此存在隐私保护强度会比原来降低的问题。

本发明的目的在于，鉴于上述的技术课题，不进行近似而生成遵循离散拉普拉斯分布的秘密随机数。

用于解决课题的手段

为了解决上述课题，本发明的一方式的秘密随机数生成系统，是包括多个秘密计算装置、生成遵循参数α的离散拉普拉斯分布的随机数r的隐匿值[r]的秘密随机数生成系统，其中，将α设为大于0且小于1的数，将N为2以上的整数，秘密计算装置包括：比特串生成部，生成由遵循概率(1-α)/(1+α)的伯努利分布的随机数比特b

发明的效果

根据本发明，能够不进行近似而生成遵循离散拉普拉斯分布的秘密随机数。通过使用该秘密随机数进行计算结果的搅拌，能够提高秘密计算中的输出隐私的保护强度。

附图说明

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

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

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

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

具体实施方式

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

<秘密计算>

秘密计算是保持对数值进行加密或隐匿的状态下进行计算的技术(例如非专利文献1)。以下，将对某个值·进行了隐匿得到的值称为“隐匿值”，表示为[·]。在秘密计算中，能够计算隐匿值[a]、[b]的加法运算[a+b]、减法运算[a-b]以及乘法运算[a·b]。另外，特别是在a、b为真假值(1比特的值)的情况下，能够计算异或[a XOR b]、逻辑积[a AND b]以及逻辑和[a OR b]。

已知有利用以上的性质，通过秘密计算实现更复杂的处理的方法。以下示出这样的处理中在本发明中使用的处理。

《前缀逻辑和(Prefix-OR)》

如果使用逻辑和的计算，则对于作为比特串(a

《均匀随机数生成》

根据参考文献1、2，能够不知道原来的随机数r而生成均匀随机数r的隐匿值[r]。

〔参考文献1〕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.

〔参考文献2〕J.Bar-Ilan and D.Beaver,"Non-cryptographic fault-tolerantcomputing in constant number of rounds of interaction,"Proceedings of the 8thannual ACM Symposium on Principles of Distributed Computing,1989,pp.201-209.

《间隔测试(Interval test)》

根据参考文献3，对于某个值a的隐匿值[a]，能够获得对值a是否收敛在某一范围I内进行判定得到的隐匿比特的隐匿值[b]。此时，如果a∈I，则满足b＝1，否则满足b＝0。

〔参考文献3〕T.Nishide and K.Ohta,"Multiparty computation for interval,equality,and comparison without bit-decomposition protocol,"Public KeyCryptography,LNCS 4450,pp.343-360,2007.

<伯努利分布>

伯努利分布Ber(β)是以某一概率β产生1，以概率1－β产生0的分布。

<离散拉普拉斯分布>

假设为独立地被试行的随机变量B

[实施方式]

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

实施方式的秘密随机数生成系统由n(≥2)台的秘密计算装置协调，计算遵循离散拉普拉斯分布的随机的值的隐匿值。在本实施方式中，设想在位数p的有限域Z

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

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

秘密计算装置1

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

在参数存储部10中存储有预先确定的离散拉普拉斯分布DL(α)的参数α和足够大的自然数N。其中，α是大于0且小于1的数。

在步骤S11中，比特串生成部11生成遵循伯努利分布的随机数比特b

在步骤S111中，区间设定部111选择有限域Zp上的区间I＝[γ

在步骤S112中，随机数生成部112生成有限域Zp上的随机数r

在步骤S113中，间隔测试部113通过间隔测试(Interval test)判定r

在步骤S12中，绝对值决定部12获得随机数比特b

在步骤S121中，前缀逻辑和部121获得对隐匿值的列[b

在步骤S122中，比特反转总和部122计算[L]＝Σ

在步骤S13中，代码决定部13得到对位置L的隐匿值[L]乘以随机的代码s的隐匿值[s]后得到的结果[L·s]。乘法运算结果[L·s]能够通过执行以下的步骤S131～S132而获得。

在步骤S131中，代码生成部131通过计算[s]←

在步骤S132中，代码乘法运算部132对位置L的隐匿值[L]乘以代码s的隐匿值[s]。该乘法运算结果的隐匿值[L·s]成为遵循离散拉普拉斯分布DL(α)的随机数的隐匿值。代码乘法运算部132输出乘法结果的隐匿值[L·s]。

在步骤S14中，输出部14将乘法运算结果的隐匿值[L·s]作为遵循参数α的离散拉普拉斯分布DL(α)的随机数r的隐匿值[r]输出。

在本发明中，通过秘密计算遵循伯努利分布的随机数比特，实现遵循离散拉普拉斯分布的随机数的秘密计算。此时，不进行基于几何分布的近似，而直接生成基于离散拉普拉斯分布的随机数，由此避免了由于近似而产生的隐私保护强度的降低。这样，根据本发明，能够不进行近似地生成能够用于秘密计算结果的输出隐私保护等的遵循离散拉普拉斯分布的秘密随机数。在现有的方法中，一直需要利用几何分布的近似。

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

[程序、记录介质]

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

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

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

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

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