秘密倒数计算系统、秘密归一化系统、它们的方法、秘密计算装置以及程序

技术领域

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

背景技术

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

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

近年来，基于秘密计算的高度的统计、机器学习的研究正在盛行。但是，这些运算的大部分包含超过秘密计算的擅长的加减乘法运算的、倒数、平方根、指数、对数等的计算。倒数的计算是计算机等中的基本运算之一，在各种情况下被利用。在非专利文献1中，公开了在秘密计算中计算倒数的方法。另外，在包含倒数的各种函数计算中，有时需要进行归一化以使数值收敛于某范围内的处理。在秘密计算中，通过最左比特(最高有效位(msb：mostsignificant bit))的移动进行数值的归一化。

现有技术文献

非专利文献

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

发明内容

发明要解决的课题

但是，在现有技术中，存在在秘密计算中进行归一化时的近似精度不充分的课题。

鉴于上述技术课题，本发明的目的在于提供一种能够高精度地进行归一化的秘密计算技术。

用于解决课题的手段

为了解决上述课题，本发明的第一方式的秘密倒数计算系统，是包括多个秘密计算装置，且将值a的分散值[a]作为输入，计算值a的倒数的分散值[1/a]的秘密倒数计算系统，其中，λ是值a的小数点位置，秘密计算装置包括：比特分解部，根据分散值[a]，生成值a的比特表现a

本发明的第二方式的秘密归一化系统，是包括多个秘密计算装置，对值a的分散值[a]进行归一化的秘密归一化系统，其中，λ是值a的小数点位置，秘密计算装置包括：比特分解部，根据分散值[a]，生成值a的比特表现a

发明效果

根据本发明，能够在秘密计算中以高精度进行归一化。

附图说明

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

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

图3是例示倒数计算部的功能结构的图。

图4是例示秘密倒数计算方法的处理过程的图。

图5是例示倒数计算部的处理过程的图。

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

具体实施方式

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

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

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

{·}是将比特·隐匿后而得的数据。例如，可以使用Z

λ表示小数点位置。设想在秘密计算中使用的环(ring)或域(field)的比特数|p|的一半左右。

关于[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的倒数的分散值[1/a]的秘密倒数计算系统以及方法。以下，对实施方式的秘密倒数计算系统所执行的倒数协议的概要进行说明。

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

倒数即是除法运算的显而易见的组成部分。除法运算作为在对明文(plaintext)的处理中利用频度高但处理慢的函数而被公知。在针对明文的倒数计算中，为了有效地进行计算，有时进行以下的归一化。将输入a的小数点位置的0.5(即，2

【数学式2】

在倒数中，在向作为标准的[0.5,1)的归一化中，通过8次多项式近似，成为21比特左右的精度。由于一般在单精度中需要23比特的精度，所以需要导入进一步提高精度的技术。通常，移动最左比特而归一化为[0.5,1)，但之后进一步地如果最左比特的下1比特为0(即如果值为[0.5,0.75))，则乘以1.5。于是，由于[0.5,0.75)向[0.75,1.125)移动，所以如果是[0.75,1)，则不进行任何动作，与此相匹配地，被归一化为[0.75,1.125)。[0.75,1.125)是比[0.5,1)窄的区间，所以在近似区间越窄精度越提高的插值多项式近似中是有效的技术。实际上，通过此技术，近似精度会超过23比特。另一方面，由于实施该技术所花费的处理成本是通信量λ(≒|p|/2)、循环数2左右，所以比增加1次实数乘法运算(通信量8/3*|p|、循环数3)更有效率。

以下表示用于以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]低σ的表现。

【数学式3】

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

【表1】

以下示出使用算法1计算秘密计算上的倒数的算法。在此，分为将作为计算对象的输入归一化为倒数计算用的算法(算法3)、和使用该算法计算倒数的算法(算法4)进行说明。

〔算法3：倒数用归一化协议〕

输入：[a]

输出：[b],[c](其中，b是将a的最左比特移动到小数点位置λ后，如果a的最左比特的下1比特的比特为0，则再乘以1.5后而得的值(即，如果将小数点位置设为λ+1，则将a归一化为[0.75,1.125)后而得的值)。c是归一化及其逆运算中使用的2的幂的数，满足b＝ac。)

1：通过比特分解得到[a]的比特表现{a

2：得到仅a的最左比特的位置为1的比特串{x

3：在2≤i<λ中，通过下式设定{y

【数学式4】

4：由下式设定{y

【数学式5】

{y

如果msb的下1比特的输入比特为1，则msb的上1比特的y

5：通过比特结合来将{y

c成为将a的msb移动到确定的位置、进而如果msb的下1比特的比特为0则乘以1.5后而得的值。应当注意，为小数点位置是1的定点。

6：计算[b]:＝[a][c]，输出[b],[c]。

〔算法4：倒数协议〕

输入：[a]

输出：[1/a]

1：通过算法3，得到将[a]归一化为[0.75,1.125)后而得的值[b]、为了归一化而进行乘法运算后而得的值[c]。

2：对[b]执行算法1，计算[b]的倒数。将结果设为[w]。

3：计算[w][c]。

在算法3的步骤2中执行的表示最左比特的标志串的生成，例如通过使用以下的算法，能够有效地进行。

〔算法5：msb标志串取得协议〕

输入：被进行比特表现的整数{a

输出：仅a的msb位置为1的比特串{x

1：在0≤i<λ-1中，设为{f

2：设为{f

3：在0≤i<λ-1情况下，设为{x

4：设为{x

<秘密倒数计算系统100>

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

实施方式的秘密倒数计算系统100所包含的秘密计算装置1

秘密计算装置1

参照图4，说明实施方式的秘密倒数计算系统100执行的秘密倒数计算方法的处理过程。

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

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

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

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

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

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

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

参照图5，详细说明倒数计算部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归一化后而得的值b。即，[x]:＝[b]。第一积和部161将[y']向第一加法部162输出。

在步骤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)]。

[变形例：秘密归一化系统]

实施方式的秘密倒数计算系统100构成为将用于倒数计算的归一化(算法3)和倒数计算(算法4)双方都执行。变形例的秘密归一化系统构成为仅执行用于秘密倒数计算系统100中的进行用于倒数计算的归一化(算法3)的部分。即，秘密归一化系统将值a的分散值[a]作为输入，输出将值a归一化为[0.75,1.125)而得的值b的分散值[b]、和归一化乘数c的分散值[c]。具体而言，变形例的秘密归一化系统中包含的秘密计算装置1

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

[程序、记录介质]

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

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

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

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

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