秘密指数函数计算系统、秘密指数函数计算方法、秘密计算装置以及程序

摘要

在秘密计算中快速计算指数函数。秘密指数函数计算系统(100)将[a]作为输入，计算[exp(a)]。最小值减法部(11)计算[a']:＝[a]‑μ。比特分解部(12)根据[a']，生成a'的高位u比特的比特表现[a'

说明书

技术领域

本发明涉及在秘密计算中计算指数函数的技术。

背景技术

所谓秘密计算，是在保持将数据隐匿的状态下计算任意的函数的加密技术。期待，有效利用该特征，从而对于系统运用者和数据使用者而言都不泄漏数据的数据利用的方式。已知在秘密计算中存在几种方式，其中，使秘密分散成为构成要素的方式的数据的处理单位小，能够进行高速的处理。

所谓秘密分散，是将秘密信息变换为被称为份额的几个片断的方法。例如，存在被称为(k，n)阈值法的秘密分散，其从秘密的信息生成n个份额，能够从k个以上的份额恢复秘密，从少于k个的份额的情况下不会泄露秘密的信息。秘密分散的具体构成方法已知有Shamir(萨莫尔)秘密分散、复制秘密分散等。在本说明书中，将通过秘密分散而分散的值的一个片断称为“份额”。另外，将所有的份额的集合整体称为“分散值”。

近年来，基于秘密计算的高度的统计、机器学习的研究正在盛行。但是，这些运算的大部分包含超过秘密计算的擅长的加减乘法运算的、倒数、平方根、指数、对数等的计算。指数函数的计算是计算机等中的基本的运算之一，在各种情况下被利用。在非专利文献1中，公开了在秘密计算中计算指数函数的方法。

现有技术文献

非专利文献

非专利文献1：五十嵐大、“秘密計算AIの実装に向けた秘密実数演算群の設計と実装-O(|p|)ビット通信量O(1)ラウンドの実数向け右シフト-”、CSS2019、2019年

发明内容

发明要解决的课题

但是，非专利文献1所公开的方法存在计算成本大的课题。

鉴于上述的技术课题，本发明的目的在于提供一种能够高速地计算指数函数的秘密计算技术。

用于解决课题的手段

为了解决上述课题，本发明的一方式的秘密指数函数计算系统，包括多个秘密计算装置，将值a的分散值[a]作为输入，计算值a的指数函数的输出的分散值[exp(a)]，其中，μ是值a可取的最小值，t是规定的整数，u是值a的小数点以下比t比特高位的比特数，秘密计算装置包括：最小值减法部，求出从分散值[a]中减去最小值μ而得的值a'的分散值[a']；比特分解部，根据分散值[a']，生成值a'的高位u比特的比特表现a'

发明效果

根据本发明，能够在秘密计算中高速地计算指数函数。

附图说明

图1是例示秘密指数函数计算系统的功能结构的图。

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

图3是例示选择积部(selective product unit)的功能结构的图。

图4是例示指数函数计算部的功能结构的图。

图5是例示秘密指数函数计算方法的处理过程的图。

图6是例示选择积部的处理过程的图。

图7是例示指数函数计算部的处理过程的图。

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

具体实施方式

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

在本说明书中，使用以下的记法。

[·]是将数值·隐匿后而得的数据。例如，能够使用Shamir秘密分散、复制秘密分散等的分散值。

关于[a？b:c]，如果a＝1，则[a？b:c]表示b，如果a＝0，则[a？b:c]表示c。

【数学式1】

分别表示逻辑非(NOT)、逻辑积(AND)、逻辑和(OR)、逻辑异或(XOR)。

通过针对环上的整数确定公开的小数点位置，能够视为定点(fixed-point)的实数。在本发明中，将这样在环上表示的定点的实数简单标记为实数。

下标中的“_”(下划线)表示右侧的字符以下标方式附于左侧的字符。例如，“a

[实施方式：秘密指数函数计算系统]

本发明的实施方式是如下的秘密指数函数计算系统和方法，用于将值a的分散值[a]作为输入，在保持将值a隐匿的状态下计算值a的指数函数的输出的分散值[exp(a)]。下面将说明由实施方式的秘密指数函数计算系统所执行的指数函数协议的概要。

以往，在秘密计算中，超过加减乘法运算的倒数、平方根、指数函数、对数函数等初等函数组的处理成本大，没有安装。在本发明中，为了解决这些课题，使用能够高效且统一地近似于秘密计算上的初等函数组的算法，能够高效地计算指数函数。该近似方法通过用单一的方法仅改变参数就能够对包含指数函数的主要的初等函数进行近似。而且，该近似方法是在单精度(23比特)中3次量的实数乘法运算的通信量/循环数，是理论上最佳的效率。

指数函数是在逻辑回归、深层学习等机器学习的各种方法中，作为sigmoid函数或softmax函数等的组成部分而使用，另外在统计中也在费歇尔(Fisher)的正确检验等中使用的重要的函数。由于泰勒展开的收敛快，因此指数函数通过泰勒展开来计算是合适的。

【数学式2】

然而，很明显，如果x大，则上式的收敛慢，因此直接的输入不能适用。由于指数函数在输入上具有加法性，所以如下述地加法性地分解x，计算下式即可。

(1)所设想的输入的最小值μ

(2)x-μ的小数点以下t比特以上的高位u比特x

(3)x-μ的比x

【数学式3】

expx＝expμexp2

这里，expμ是公开值。exp2

以下示出用于以8次多项式对秘密计算上的初等函数组进行近似的算法。

〔算法1：基于8次多项式的函数近似协议〕

输入：[x]∈[L,R)

参数：a,b,c,d,f,g,H,i,j,k,l,m,n,o,p,q,α,β,γ,δ,ζ

输出：对应于目标函数func的[func(x)]

1：通过积和(sum of products)来计算[y']:＝[x(δx+a-i)-j]，通过右移位来降低小数点位置。

2：计算[y]:＝[y'+(ix+j)]。

3：通过积和来计算[z']:＝[y(ζy+b-k)+(c-l)x-m]，通过右移位来降低小数点位置。

4：计算[z]:＝[z'+(ky+lx+m)]。

5：通过积和来计算[w'/γ]:＝[z(αz+d-n/γ)+(βx+f-o/γ)y+(g-p)x+(H-q)/γ]，同时进行基于γ的乘法运算和小数点位置的下降，得到[w']。

6：输出[w]:＝[w'+(nz+oy+px+q)]。

在算法1的步骤1、3中执行的小数点位置的下降，例如能够通过使用非专利文献1中所公开的除数公开除法运算(public divisor division)来有效地进行。

在算法1的步骤5中执行的公开值乘法运算(public value multiplication)和小数点位置的下降的同时执行，例如能够通过使用以下的算法来有效地进行。

〔算法2：从右移位起，不增大处理成本而同时进行公开值乘法运算〕

输入：[x]、乘数m、移位量σ

输出：移位后的[mx]

1：计算公开值2

2：通过公开值除法运算计算下式。其中，[mx]视为与[x]相比而小数点位置低σ的表现。

【数学式4】

在算法1中使用的参数L,R,a,b,c,d,f,g,H,i,j,k,l,m,n,o,p,q,α,β,γ,δ,ζ根据进行近似的函数func来被设定。在对本发明中作为对象的指数函数进行近似时，例如如下表那样设定各参数即可。另外，e

【表1】

以下示出使用算法1计算秘密计算上的指数函数的算法。

〔算法3：指数函数协议〕

输入：[a]

输出：[exp(a)]

参数：t:＝-1

1：计算[a']:＝[a]-μ。

2：通过比特分解而取出小数点以下比t比特高位的比特，进行mod p变换，得到[a'

3：在各0≤i

4：以[a'

5：在各0≤i

【数学式5】

6：计算关于各i的[ε'

7：计算下式。这是低位比特部分表示的数。

【数学式6】

8：对[a'

9：计算并输出[w][f'][ε']exp(μ)。在exp(μ)的计算中使用算法2。

在算法3的步骤4中执行的参照二进制的公开表的幂是如下的处理：执行多个根据秘密的真值(truth value)从由公开值构成的二进制的表中对值进行参照并选择的操作，并将各个参照结果相乘。参照二进制的公开表的幂，例如能够通过使用以下的算法而有效地进行。

〔算法4：参照二进制的公开表的幂〕

输入：乘数m

输出：

【数学式7】

1：将n

2：对于每个i∈{0,2,…,n

3：计算[c

4：置为m'

5：计算[a

6：通过实数乘法运算计算下式。但是，如果n是奇数，则不进行最后的右移位。

【数学式8】

7：如果n是奇数，则通过[c

在算法4的步骤7中执行的选择性公开乘法运算，例如通过使用以下的算法，能够有效地进行。

〔算法5：基于选择性公开乘数的针对所要求的右移位值的乘法运算〕

输入：[a]、乘数m

输出：如果c＝1，则为[m

1：计算[m

2：通过if-then-else门，输出[c？m

在算法5的步骤1中执行的公开值乘法运算，例如通过将算法2和以下的算法组合，能够有效地进行。

〔算法6：在多个除数中的右移位/除数公开除法运算〕

输入：[a]、除数d

输出：[a/d

1：求出[a]的商[q]。

2：使用商[q]，通过右移位/除数公开除法运算，计算并输出针对各个i的[a/d

在算法6的步骤1中求出的商能够通过商转移有效地求出(参照参考文献1)。

《参考文献1》Ryo Kikuchi,Dai Ikarashi,Takahiro Matsuda,Koki Hamada,andKoji Chida,"Efficient bit-decomposition and modulus-conversion protocols withan honest majority,"Proceedings of Information Security and Privacy-23rdAustralasian Conference(ACISP 2018),pp.64-82,July 11-13,2018.

<秘密指数函数计算系统100>

实施方式的秘密指数函数计算系统100是执行上述指数函数协议的信息处理系统。如图1所示，秘密指数函数计算系统100包括N(≥3)台秘密计算装置1

例如，如图2所示，实施方式的秘密指数函数计算系统100中包括的秘密计算装置1

秘密计算装置1

将参考图5说明由实施方式的秘密指数函数计算系统100执行的秘密指数函数计算方法的处理过程。

在步骤S11中，各秘密计算装置1

在步骤S12－1中，各秘密计算装置1

在步骤S13中，各秘密计算装置1

在步骤S14中，各秘密计算装置1

在步骤S15中，各秘密计算装置1

【数学式9】

在步骤S16中，各秘密计算装置1

在步骤S17中，各秘密计算装置1

参照图6，详细说明选择积部13执行的处理过程。

以下，将n

在步骤S131中，选择积部13的条件整合部131计算将值a'

在步骤S132中，选择积部13的表变换部132作为m'

在步骤S133中，选择积部13的公开值乘法部133计算[a'

在步骤S134中，选择积部13的实数乘法部134计算将分散值[a"

【数学式10】

在步骤S135中，当u为奇数时，选择积部13的选择乘法部135将若a'

参照图7，详细说明指数函数计算部16执行的处理过程。

在参数存储部160中存储有用于以8次多项式对指数函数进行近似的参数a,b,c,d,f,g,H,i,j,k,l,m,n,o,p,q,α,β,γ,δ,ζ。各参数是根据进行近似的函数而预先确定的，在对指数函数进行近似的情况下，设定表1所例示的值即可。

在步骤S161中，指数函数计算部16的第一积和部161通过积和来计算[y']:＝[x(δx+a-i)-j]，并且通过右移位来降低小数点位置。其中，x为表示值a的低位比特部分的数a'

在步骤S162中，指数函数计算部16的第一加法部162计算[y]:＝[y'+(ix+j)]。第一加法部162将[y]输出到第二积和部163。

在步骤S163中，指数函数计算部16的第二积和部163通过积和来计算[z']:＝[y(ζy+b-k)+(c-l)x-m]，通过右移位来降低小数点位置。第二积和部163将[z']输出到第二加法部164。

在步骤S164中，指数函数计算部16的第二加法部164计算[z]:＝[z'+(ky+lx+m)]。第二加法部164将[z]输出到第三积和部165。

在步骤S165中，指数函数计算部16的第三积和部165通过积和来计算[w'/γ]:＝[z(αz+d-n/γ)+(βx+f-o/γ)y+(g-p)x+(H-q)/γ]。第三积和部165将[w′/γ]输出到公开值乘法部166。

在步骤S166中，指数函数计算部16的公开值乘法部166计算[w']:＝[w'/γ]*γ。公开值乘法部166向第三加法部167输出[w']。

在步骤S167中，指数函数计算部16的第三加法部167计算[w]:＝[w'+(nz+oy+px+q)]。

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

[程序、记录介质]

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

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

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

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

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