CN116324934A - 秘密移位系统、秘密移位装置、秘密移位方法、程序 - Google Patents

Abstract

提供了秘密计算技术，其使用将成为移位对象的数值和移位量作为输入而进行左移位的协议，高速地进行移位运算。秘密移位系统根据数值a的份额[[a]]^P和移位量ρ的份额<<ρ>>^Q，计算对数值a进行ρ位移位而得到的数值s的份额[[s]]^P，其包括：模数转换单元，计算份额<<ρ>>^p；第一标志计算单元，计算份额[[f₀]]²,…,[[f_L]]²；第二标志计算单元，计算份额<<f₁>>^p,…,<<f_L>>^p；移位量计算单元，计算份额<<ρ’>>^p；左移位单元，计算份额[[b]]^P；右移位单元，计算份额[[c₀]]^P,…,[[c_d‑1]]^P；第三标志计算单元，计算份额[[f₀]]^P,…,[[f_L]]^P；以及移位值计算单元，计算份额[[s]]^P。

Description

秘密移位系统、秘密移位装置、秘密移位方法、程序

技术领域

本发明涉及秘密计算技术，尤其涉及在秘密计算中进行位移位(bitshift)运算的技术。

背景技术

秘密计算是指不复原被加密的数值而得到指定的运算的结果的方法(例如参照参考非专利文献1)。在参考非专利文献1的方法中，进行将能够复原数值的多个信息分散到3个秘密计算装置的加密，不复原数值，就能够将加减运算、常数和、乘法、常数倍、逻辑运算(否定、逻辑与、逻辑和、异或)、数据形式转换(整数、二进制)的结果以分散到3个秘密计算装置的状态、即加密的状态进行保持。通常，分散数不限于3而能够设为W(W为3以上的规定的常数)，通过基于W个秘密计算装置的协调计算来实现秘密计算的协议被称为多分协议。

(参考非专利文献1：千田浩司,濱田浩気,五十嵐大,高橋克巳,“軽量検証可能3パーティ秘匿関数計算の再考,”In CSS，2010.)

以往，作为与进行浮点运算(floating point computation)的秘密计算的协议或安装相关的文献，存在非专利文献1、非专利文献2。进行浮点运算所需的位移位运算是将二进数的位图案向左右移位的运算，在计算机处理中是基本的运算之一。

现有技术文献

非专利文献

非专利文献1：天田拓磨,奈良成泰,西出隆志,吉浦裕,“通信量を削減した浮動小数点演算のためのマルチパーティ計算,”情報処理学会論文誌,Vol.60,No.9,pp.1433-1447,2019。

非专利文献2：Randmets,J.,“Programming Languages for Secure Multi-partyComputation Application Development,”PhD thesis.University of Tartu,2017。

发明内容

发明要解决的课题

但是，在通过秘密计算执行位移位运算的情况下，由于一边隐匿左右的移位方向和移位量一边进行运算，因此存在计算成本大的问题。

因此，本发明的目的在于提供秘密计算技术，其使用将作为移位对象的数值和移位量作为输入而进行左移位的协议，高速地进行位移位运算。

用于解决课题的手段

本发明的一方式涉及的秘密移位系统中，设P为素数，设p为素数P的阶，设Q为剩余环(factor ring)的阶，设M为输入的数值的MSB位置可取的上限值，设M’为份额容许的MSB位置的上限值，设[R,R’]为以分割后的右移位覆盖的右移位量的范围，该秘密移位系统由3个以上的秘密移位装置构成，从数值a的份额[[a]]^P和移位量ρ的份额<<ρ>>^Q(其中，ρ≧0时设为表示左移位，ρ<0时设为表示右移位)，计算对数值a进行ρ位移位而得到的数值s的份额[[s]]^P(其中，s＝2^ρa)，所述秘密移位系统包括：模数转换单元，从份额<<ρ>>^Q，计算份额<<ρ>>^p；第一标志计算单元，将u设为满足u≦M’-M+1的整数，将d设为满足d≧ceiling(((R’-R+1)/u)_Re)的整数，从份额<<ρ>>^Q或份额<<ρ>>^p、范围[R,R’]、数值u和数值d，计算份额[[f₀]]²＝[[(ρ≧-R’)]]²,[[f₁]]²＝[[(ρ≧-R’+u)]]²,…,[[f_d-1]]²＝[[(ρ≧-R’+(d-1)u)]]²,[[f_L]]²＝[[(ρ≧-R+1)]]²；第二标志计算单元，从份额[[f₁]]²,[[f₂]]²,…,[[f_d-1]]²,[[f_L]]²，计算份额<<f₁>>^p,<<f₂>>^p,…,<<f_d-1>>^p,<<f_L>>^p；移位量计算单元，从份额<<ρ>>^p、份额<<f₁>>^p,<<f₂>>^p,…,<<f_d-1>>^p,<<f_L>>^p、范围的上限值R’、数值u和数值d，计算<<ρ’>>^p＝<<ρ>>^p+R’-u(Σ_1≦i<d<<f_i>>^p)+((d-1)u-R’)<<f_L>>^p；左移位单元，从份额[[a]]^P和份额<<ρ’>>^p，计算份额[[b]]^P＝[[2^ρ’a]]^P；右移位单元，从份额[[b]]^P、范围的上限值R’、数值u和数值d，计算份额[[c₀]]^P＝[[2^ρ’a/2^R’]]^P,[[c₁]]^P＝[[2^ρ’a/(2^R’-u)]]^P,…,[[c_d-1]]^P＝[[2^ρ’a/(2^R’-(d-1)u)]]^P；第三标志计算装置，从份额[[f₀]]²,[[f₁]]²,…,[[f_d-1]]²,[[f_L]]²，计算份额[[f₀]]^P,[[f₁]]^P,…,[[f_d-1]]^P,[[f_L]]^P；以及移位值计算单元，从份额[[b]]^P、份额[[c₀]]^P,[[c₁]]^P,…,[[c_d-1]]^P和份额[[f₀]]^P,[[f₁]]^P,…,[[f_d-1]]^P,[[f_L]]^P，计算份额[[s]]^P＝[[c₀]]^P[[f₀]]^P+([[c₁]]^P-[[c₀]]^P)[[f₁]]^P+…+([[c_d-1]]^P-[[c_d-2]]^P)[[f_d-1]]^P+([[b]]^P-[[c_d-1]]^P)[[f_L]]^P。

本发明的一方式涉及的秘密移位系统中，设P为素数，设p为素数P的阶，设M为移位量的上限值，该秘密移位系统由3个以上的秘密移位装置构成，从数值a的份额[[a]]^P和移位量ρ的份额<<ρ>>^Q(其中，0≦ρ≦M,对数值a进行M位左移位而得到的数值2^Ma不溢出(overflow))，计算对数值a进行ρ位移位而得到的数值s的份额[[s]]^P(其中，s＝2^ρa)，所述秘密移位系统包括：移位量计算单元，从份额<<ρ>>^p和上限值M，计算份额<<M-ρ>>^p；左移位单元，从份额[[a]]^P和份额<<M-ρ>>^p，计算份额[[b]]^P＝[[2^M-ρa]]^P；以及右移位单元，从份额[[b]]^P和上限值M，计算份额[s]]^P＝[[2^M-ρa/2^M]]^P。

本发明的一方式涉及的秘密移位系统中，设P为素数，设p为素数P的阶，设Q为剩余环的阶，设M为输入的数值的MSB位置可取的上限值，该秘密移位系统由3个以上的秘密移位装置构成，从数值a的份额[[a]]^P和移位量ρ的份额<<ρ>>^Q(其中，ρ≧0时设为表示左移位，ρ<0时设为表示右移位)，计算对数值a进行ρ位移位而得到的数值s的份额[[s]]^P(其中，s＝2^ρa)，所述秘密移位系统包括：模数转换单元，从份额<<ρ>>^Q，计算份额<<ρ>>^p；第一标志计算单元，从份额<<ρ>>^Q或份额<<ρ>>^p，计算份额[[f_L]]²＝[[(ρ≧0)]]²；第二标志计算单元，从份额[[f_L]]²，计算<<f_L>>^p；移位量计算单元，从份额<<ρ>>^p、份额<<f_L>>^p和上限值M，计算份额<<ρ’>>^p＝<<ρ>>^p+M-M<<f_L>>^p；左移位单元，从份额[[a]]^P和份额<<ρ’>>^p，计算份额[[b]]^P＝[[2^ρ’a]]^P；右移位单元，从份额[[b]]^P和上限值M，计算份额[[c]]^P＝[[2^ρ’a/2^M]]^P；第三标志计算装置，从份额[[f_L]]²，计算份额[[f_L]]^P；以及移位值计算单元，从份额[[b]]^P、份额[[c]]^P和份额[[f_L]]^P，计算份额[[s]]^P＝[[c]]^P+([[b]]^P-[[c]]^P)[[f_L]]^P。

发明效果

根据本发明，能够在隐匿了作为移位对象的数值和移位量的状态下高速地进行移位运算。

附图说明

图1是表示秘密移位系统10的结构的框图。

图2是表示秘密移位装置100_i的结构的框图。

图3是表示秘密移位系统10的动作的流程图。

图4是表示秘密移位系统20的结构的框图。

图5是表示秘密移位装置200_i的结构的框图。

图6是表示秘密移位系统20的动作的流程图。

图7是表示秘密移位系统30的结构的框图。

图8是表示秘密移位装置300_i的结构的框图。

图9是表示秘密移位系统30的动作的流程图。

图10是示出实现本发明的实施方式中的各装置的计算机的功能结构的一个例子的图。

具体实施方式

以下，详细地说明本发明的实施方式。此外，对具有相同功能的结构部标注相同的编号，并省略重复说明。

在说明各实施方式之前，对该说明书中的记载方法进行说明。

^(脱字号(caret))表示上标。例如，x^{y^z}表示y^z相对于x的上标，x_y^z表示y^z相对于x的下标。另外，_(下划线)表示下标。例如，x^y_z表示y_z相对于x的上标，x_{y_z}表示y_z相对于x的下标。

另外，对于某字符x的^x、～x这样的上标的“^”、“～”本来应记载在“x”的正上，但由于说明书的记载表述的限制，记载为^x、～x。

<技术背景>

本发明的各实施方式中的秘密计算使用现有的秘密计算上的协议来构建。在此，首先对记法进行说明。

《记法》

设P为素数。例如，梅森素数P＝2⁶¹-1即可。设p为素数P的阶。此外，有时也表示为p＝|P|。当P是梅森素数时，p成为素数。例如，如果设P＝2⁶¹-1，则p＝61。另外，设Q为剩余环的阶。阶Q作为素数P或其阶p使用。另外，阶Q能够用于浮点的指数部。在将阶Q用于浮点的指数部的情况下，例如能够使Q＝2¹³-1。

将k设为秘密分散的阈值。例如，设k＝2即可。此外，将n设为秘密分散的分散数(即，秘密计算的方(parties)数)。例如，设n＝3即可。

[[x]]^y表示将mod y要素x进行了(k,n)-秘密分散的份额。作为秘密分散的方法，例如能够使用Shamir秘密分散或复制秘密分散。以下，用<<x>>^y表示对mod y要素x进行了(k,n)-复制秘密分散的份额。由于(k,n)-复制秘密分散是(k,n)-秘密分散，所以能够适用于进行了(k,n)-秘密分散的份额的协议也能够使用于进行了(k,n)-复制秘密分散的份额。此外，在将份额表示为<<x>>^y时，意味着利用复制秘密分散的性质。另外，尤其将(k,k)-复制秘密分散被称为(k,k)-加法秘密分散。以下，以<x>^y表示对mod y要素x进行(k,k)-加法秘密分散的份额。

[[x]]^{2^m}表示将[[x]]²形式的份额排列m个后的份额。此外，有时也将[[x]]^{2^m}视为数值的位表现。

x≒y表示x与y作为计算机上的实数相等。即，表示x与y之差在一定的误差范围内。

对于2个数a、d，a/d表示舍去小数点以下的整数除法运算的值。因此，基于2的幂数的整数除法运算与右移位等价。另外，对于2个数a、d，(a/d)_Re表示实数除法运算的值。

相对于数a，ceiling(a)表示a以上的最小整数。

(prop)表示在命题prop成立的情况下取1为值、在不成立的情况下取0为值。例如，(1>0)成为1。

将浮点数2^ba(其中，a、b分别表示尾数部(mantissa part)、指数部(exponentpart))表示为浮点数(a,b)。另外，将m个浮点数2^b_0a₀,2^b_1a₁,…,2^b_m-1a_m-1(其中，a_i,b_i(0≦i<m)分别表示尾数部、指数部)表示为浮点数矢量(^→a,^→b)(其中，^→a＝(a₀,a₁,…,a_m-1),^→b＝(b₀,b₁,…,b_m-1))。有时也将矢量^→a＝(a₀,a₁,…,a_m-1)的长度m表示为|^→a|。

《现有的秘密计算协议》

首先，对本发明中使用的现有的秘密计算协议进行说明。对于加减运算、常数和、乘法运算、常数倍、逻辑运算(否定、逻辑与、逻辑或、异或)、数据形式转换(整数、二进制数)、指数函数的计算，使用现有的协议。其他本发明中使用的现有的协议，使用以下的协议。

[从(k,n)-秘密分散(复制秘密分散)向(k,k)-加法秘密分散的转换]

输入：数值x的份额[[x]]^y(数值x的份额<<x>>^y)

输出：数值x的份额<x>^y

具体而言，有参考非专利文献2中记载的方法。

(参考非专利文献2：Kikuchi,R.,Ikarashi,D.,Matsuda,T.,Hamada,K.andChida,K.,“Efficient Bit-Decomposition and Modulus-Conversion Protocols withan Honest Majority,”23rd Australasian Conference on Information Security andPrivacy(ACISP 2018),Lecture Notes in Computer Science,Vol.10946,Springer,pp.64-82,2018.)

[从(k,k)-加法秘密分散向(k,n)-秘密分散(复制秘密分散)的转换]

输入：数值x的份额<x>^y

输出：数值x的份额[[x]]^y(数值x的份额<<x>>^y)

具体而言，有参考非专利文献2中记载的方法。

[mod 2→mod q转换]

输入：数值x的份额[[x]]²(数值x的份额<<x>>²)

输出：数值x的份额[[x]]^q(数值x的份额<<x>>^q)

具体而言，有参考非专利文献2中记载的方法。

[移位量公开右移位(Shift Amount Disclosure Right Shift)]

输入：数值x的份额[[x]]^q、移位量ρ

输出：使数值x向ρ位右移位而得到的数值的份额[[x/2^ρ]]^q

具体而言，有参考非专利文献3中记载的方法。

(参考非专利文献3：三品気吹,五十嵐大,濱田浩気,菊池亮,“高精度かつ高効率な秘密ロジスティック回帰の設計と実装,”CSS2018,2018.)

[总括移位量公开右移位(Batch Shift Amount Disclosure Right Shift)]

输入：数值x的份额[[x]]^q、移位量ρ₀,…,ρ_m-1

输出：使数值x向ρ₀位,…,ρ_m-1位右移位而得到的数值的份额[[x/2^ρ_0]]^q,…,[[x/2^ρ_m-1]]^q

具体而言，有参考非专利文献4中记载的方法。

(参考非专利文献4：五十嵐大,“M op/sを超える秘密計算上の初等関数群,”SCIS2020,2020.)

另外，作为显而易见的方法，也能够以移位量公开右移位的反复，构成总括移位量公开右移位。

[使用商迁移(Quotient Transfer)的模数转换]

输入：数值x的份额<<x>>^q

输出：数值x的份额<<x>>^r

具体而言，有参考非专利文献2中记载的方法。

[位分解]

输入：数值x的份额[[x]]^q

参数：输入的数值的最大位数M

输出：数值x的份额[[x]]^{2^M}

具体而言，有参考非专利文献2中记载的方法。

《本发明的秘密计算协议》

接着，对本发明的秘密计算协议进行说明。

[乘法的循环(Multiplicative Rotation)(移位量隐匿左移位)]

输入：数值a的份额[[a]]^P、循环量(移位量)ρ(≧0)的份额<<ρ>>^p

输出：使数值a进行ρ位左移位而得到的数值的份额[[2^ρa]]^P

作为输出的份额也可以通过使用乘法或指数函数计算的协议等来计算，但也可以通过使用随机置换(参照参照非专利文献5)的考虑的方法来计算。作为具体例，对n＝3的情况进行说明。

(参考非专利文献5：五十嵐大,濱田浩気,菊池亮,千田浩司,“インターネット環境レスポンス1秒の統計処理を目指した,秘密計算基数ソートの改良,”SCIS2014,2014.)

(环(Round)1)

step(步骤)1：份额[[a]]^P转换为方0、方1所具有份额的(k,k)-加法秘密分散<a>^P。

step(步骤)2：方0、方1共有随机数r₀₁。此外，方1、方2共有随机数r₁₂。

step(步骤)3：方0计算b₀＝2^{(<<ρ>>^p)_01}<a>^P ₀-r₀₁，并将b₀发送到方2。

在此，<<ρ>>^p ₀₁表示关于份额<<ρ>>^p而方0、方1所保持的份额。另外，<a>^P ₀关于份额<a>^P而方0保持的份额。

step(步骤)4：方1计算2^{(<<ρ>>^p)_12}(2^{(<<ρ>>^p)_01}<a>^P ₁+r₀₁)-r₁₂，并将b₁传送到方0。

在此，<<ρ>>^p ₁₂表示关于份额<<ρ>>^p而方1、方2所保持的份额。此外，<a>^P ₁表示关于份额<a>^P而方1所保持的份额。

(环2)

step(步骤)5：方0计算<c>^P ₀＝2^{(<<ρ>>^p)_20}b₁。

在此，<<ρ>>^p ₂₀表示关于<<ρ>>^p而方2、方0所保持的份额。

step(步骤)6：方2计算<c>^P ₂＝2^{(<<ρ>>^p)_20}(2^{(<<ρ>>^p)_12}b₀+r₁₂)。

(圆3)

step(步骤)7：将份额<c>^P转换为(k,n)-秘密分散的份额[[c]]^P。

在此，c＝2^ρa成立。

[移位量隐匿右移位]

输入：数值a的份额[[a]]^P，移位量ρ的份额<<ρ>>^p

参数：移位量的上限值M

其中，设0≦ρ≦M，对数值a进行M位左移位而得到的数值2^Ma不溢出。

输出：将数值a进行ρ位右移位而得到的数值的份额[[a/2^ρ]]^P

step(步骤)1：计算<<M-ρ>>^p

step(步骤)2：使用乘法的循环，计算使数值a进行M-ρ位左移位而得到的数值的份额[[2^M-ρa]]^P。

step(步骤)3：使用移位量公开右移位，计算使数值2^M-ρa进行M位右移位而得到的数值的份额[[a/2^ρ]]^P＝[[2^M-ρa/2^M]]^P。

[移位量隐匿移位(其1)]

输入：数值a的份额[[a]]^P、移位量ρ的份额<<ρ>>^Q(其中，ρ≧0时表示左移位，ρ<0时表示右移位)

参数：输入数值的MSB(Most Significant Bit)位置可取的上限值M

输出：对数值a进行ρ位移位而得到的数值s的份额[[s]]^P

在此，s＝2^ρa成立。

step(步骤)1：使用模数转换，计算份额<<ρ>>^p。在模数转换中，例如，能够使用上述的使用商迁移(quotient transition)的模数转换。

step(步骤)2：通过大小比较，计算[[f_L]]²＝[[(ρ≧0)]]²。

step(步骤)3：利用mod 2→mod p转换，计算<<f_L>>^p。

step(步骤)4：计算<<ρ’>>^p＝<<ρ>>^p+M-M<<f_L>>^p。

step(步骤)5：使用乘法的循环计算[[b]]^P＝[[2^ρ’a]]^P。

step(步骤)6：使用移位量公开右移位来计算[[c]]^P＝[[2^ρ’a/2^M]]^P。

step(步骤)7：使用mod 2→mod P转换来计算[[f_L]]^P。

step(步骤)8：计算[[s]]^P＝[[c]]^P+([[b]]^P-[[c]]^P)[[f_L]]^P。

该式子成为选择门，在ρ<0的情况下成为s＝c，在ρ≧0的情况下成为s＝b。

[移位量隐匿移位(其2)]

输入：数值a的份额[[a]]^P、移位量ρ的份额<<ρ>>^Q(其中，ρ≧0时表示左移位，ρ<0时表示右移位)

参数：输入数值的MSB位置可取的上限值M、份额允许的MSB位置的上限值M’

输出：对数值a进行ρ位移位而得到的数值s的份额[[s]]^P

在此，s＝2^ρa成立。

step(步骤)1:计算u＝M’-M+1,d＝ceiling(((M-1)/u)_Re)。

这里，u是能够用一次移位量隐匿右移位覆盖的右移位量(具体而言，从1到M’-M位的范围的量)，d是进行从1到M-1位的范围的右移位所需的移位量隐匿右移位的执行次数。

step(步骤)2：使用模数转换，计算份额<<ρ>>^p。对于模数转换，例如，能够使用上述的商迁移的模数转换。

step(步骤)3：通过大小比较，计算[[f₀]]²＝[[(ρ≧-M+1)]]²,[[f₁]]²＝[[(ρ≧-M+1+u)]]²,…,[[f_d-1]]²＝[[(ρ≧-M+1+(d-1)u)]]²,[[f_L]]²＝[[(ρ≧0)]]²。

在此，若是f_L则f_d-1成立,若是f_d-1则f_d-2,…成立。将具有这样性质的f₀,f₁,…,f_d-1,f_L称为推移标志(transitive flags)。

step(步骤)4：使用mod 2→mod p转换，计算<<f₁>>^p,<<f₂>>^p,…,<<f_d-1>>^p,<<f_L>>^p。

在本步骤中，不需要计算<<f₀>>^p。

step(步骤)5：计算<<ρ’>>^p＝<<ρ>>^p+M-1-u(Σ_1≦i<d<<f_i>>^p)+((d-1)u-M+1)<<f_L>>^p。

step(步骤)6：使用乘法的循环，计算[[b]]^P＝[[2^ρ’a]]^P。

step(步骤)7：使用总括移位量公开右移位，计算[[c₀]]^P＝[[2^ρ’a/2^M-1]]^P,[[c₁]]^P＝[[2^ρ’a/(2^M-1-u)]]^P,…,[[c_d-1]]^P＝[[2^ρ’a/(2^M-1-(d-1)u)]]^P。

step(步骤)8：使用mod 2→mod P转换，计算[[f₀]]^P,[[f₁]]^P,…,[[f_d-1]]^P,[[f_L]]^P。

在本步骤中，需要计算[[f₀]]^p。

step(步骤)9：计算[[s]]^P＝[[c₀]]^P[[f₀]]^P+([[c₁]]^P-[[c₀]]^P)[[f₁]]^P+…+([[c_d-1]]^P-[[c_d-2]]^P)[[f_d-1]]^P+([[b]]^P-[[c_d-1]]^P)[[f_L]]^P。

该式成为相对于推移的标志f₀,f₁,…,f_d-1,f_L的选择门，如果f₀,f₁,…,f_d-1,f_L全部为0则s＝0，如果是f₀则成为s＝c₀，如果是f_L则成为s＝b。

[移位量隐匿移位(其3)]

输入：数值a的份额[[a]]^P、移位量ρ的份额<<ρ>>^Q(其中，ρ≧0时表示左移位，ρ<0时表示右移位)

参数：输入数值的MSB位置可取的上限值M、份额允许的MSB位置的上限值M’

输出：对数值a进行ρ位移位而得到的数值s的份额[[s]]^P

在此，s＝2^ρa成立。

step(步骤)1：将u设为满足u≦M’-M+1的整数。另外，将[R,R’]设为以分割后的右移位所覆盖的右移位量的范围，将d设为满足d≧ceiling(((R’-R+1)/u)_Re)的整数。

以下，{}_L表示也可以不考虑比-R大的移位量的情况(例如，已知是右移位的情况)下，能够省略由该括号包围的部分的计算。此外，{}₀表示可以不考虑比-R’小的移位量的情况(例如，可知在右移位量大于移位量隐匿移位(其1)能够应用的值但不是极端大的值的情况下)，能够省略由该括号包围的部分的计算。

step(步骤)2：使用模数转换，计算<<ρ>>^p。对于模数转换，例如，能够使用上述的商迁移的模数转换。

step(步骤)3：通过大小比较，计算{[[f₀]]²＝[[(ρ≧-R’)]]²,}₀[[f₁]]²＝[[(ρ≧-R’+u)]]²,…,[[f_d-1]]²＝[[(ρ≧-R’+(d-1)u)]]²{,[[f_L]]²＝[[(ρ≧-R+1)]]²}_L。

在此，若是f_L则f_d-1成立，若是f_d-1则f_d-2,…成立。将具有这样的性质的f₀,f₁,…,f_d-1,f_L称为推移标志。

step(步骤)4：使用mod 2→mod p转换，计算<<f₁>>^p,<<f₂>>^p,…,<<f_d-1>>^p{,<<f_L>>^p}_L。

step(步骤)5：计算<<ρ’>>^p＝<<ρ>>^p+R’-u(Σ_1≦i<d<<f_i>>^p){+((d-1)u-R’)<<f_L>>^p}_L。

step(步骤)6：使用乘法的循环，计算[[b]]^P＝[[2^ρ’a]]^P。

step(步骤)7:使用总括移位量公开右移位，计算{[[c₀]]^P＝[[2^ρ’a/2^R’]]^P,}₀[[c₁]]^P＝[[2^ρ’a/(2^R’-u)]]^P,…,[[c_d-1]]^P＝[[2^ρ’a/(2^R’-(d-1)u)]]^P。

step(步骤)8：使用mod 2→mod P转换，计算{[[f₀]]^P,}₀[[f₁]]^P,…,[[f_d-1]]^P{,[[f_L]]^P}_L。

step(步骤)9：计算[[s]]^P＝{[[c₀]]^P[[f₀]]^P+(}₀[[c₁]]^P{-[[c₀]]^P)}₀[[f₁]]^P+…+([[c_d-1]]^P-[[c_d-2]]^P)[[f_d-1]]^P{+([[b]]^P-[[c_d-1]]^P)[[f_L]]^P}_L。

该式成为相对于推移的标志f₀,f₁,…,f_d-1,f_L的选择门，如果是f₀,f₁,…,f_d-1,f_L则全部成为0，如果是f₀则成为s＝c₀，如果是f₁则成为c₁、…，如果是f_L则s＝b。

另外，如果设R＝1,R’＝M-1,u＝M’-M+1,d＝ceiling(((R’-R+1)/u)_Re)，则移位量隐匿移位(其3)成为移位量隐匿移位(其2)。因此，移位量隐匿移位(其3)是将移位量隐匿移位(其2)一般化的协议。

<第一实施方式>

以下，参照图1～图3对秘密移位系统10进行说明。图1是示出秘密移位系统10的结构的框图。秘密移位系统10包括W个(W为3以上的规定的整数)秘密移位装置100₁、…、100_W。秘密移位装置100₁、…、100_W与网络800连接，能够相互进行通信。网络800例如可以是因特网等通信网络或广播通信路径等。图2是表示秘密移位装置100_i(1≦i≦W)的结构的框图。图3是表示秘密移位系统10的动作的流程图。

如图2所示，秘密移位装置100_i包括移位量计算部140_i、左移位部150_i、右移位部160_i、记录部190_i。除了记录部190_i以外的秘密移位装置100_i的各结构部构成为能够执行秘密计算所需的运算、即<技术背景>中说明的协议中的、在实现各结构部的功能上所需的运算。在本发明中，用于实现各个运算的具体的功能结构在例如可执行参考非专利文献1～5的各个非专利文献中公开的算法的结构中是充分的，这些是现有的结构，因此省略详细的说明。此外，记录部190_i是记录秘密移位装置100_i的处理所需的信息的结构部。例如，记录后述的移位量的上限值M。

通过由W个秘密移位装置100_i进行的协调计算，秘密移位系统10实现作为多方协议的移位量隐匿右移位的秘密计算。因此，秘密移位系统10的移位量计算单元140(未图示)由移位量计算部140₁、…、140_W构成，左移位单元150(未图示)由左移位部150₁、…、150_W构成，右移位单元160(未图示)由右移位部160₁、…、160_W构成。

将P设为素数，将p设为素数P的阶，将M设为移位量的上限值，秘密移位系统10从数值a的份额[[a]]^P和移位量ρ的份额<<ρ>>^p(其中，0≦ρ≦M，将数值a进行M位左移位而得到的数值2^Ma不溢出)，计算将数值a进行ρ位右移位而得到的数值s的份额[[s]]^P(其中，s＝a/2^ρ)。以下，根据图3对秘密移位系统10的动作进行说明。

在S140中，移位量计算单元140根据份额<<ρ>>^p和上限值M，计算份额<<M-ρ>>^p。

在S150中，左移位单元150根据由份额[[a]]^P和由S140计算的份额<<M-ρ>>^p，计算份额[[b]]^P＝[[2^M-ρa]]^P。左移位单元150例如构成为能够执行移位量隐匿左移位即可。

在S160中，右移位单元160根据由S150计算的份量[[b]]^P和上限值M，计算份量[[s]]^P＝[[2^M-ρa/2^M]]^P。右移位单元160例如构成为能够执行移位量公开右移位即可。

根据本发明的实施方式，能够在隐匿了成为移位对象的数值和移位量的状态下高速地进行右移位运算。

<第二实施方式>

以下，参照图4～图6对秘密移位系统20进行说明。图4是表示秘密移位系统20的结构的框图。秘密移位系统20包括W个(W为3以上的规定的整数)秘密移位装置200₁、…、200_W。秘密移位装置200₁、…、200_W与网络800连接，能够相互进行通信。网络800例如可以是因特网等通信网络或广播通信路径等。图5是表示秘密移位装置200_i(1≦i≦W)的结构的框图。图6是表示秘密移位系统20的动作的流程图。

如图5所示，秘密移位装置200_i包括模数转换部210_i、第一标志计算部220_i、第二标志计算部230_i、移位量计算部240_i、左移位部250_i、右移位部260_i、第三标志计算部270_i、移位值计算部280_i和记录部290_i。除了记录部290_i以外的秘密移位装置200_i的各结构部构成为能够执行秘密计算所需的运算、即<技术背景>中说明的协议中的、在实现各结构部的功能上所需的运算。在本发明中，用于实现各个运算的具体的功能结构在例如可执行参考非专利文献1～5的各个非专利文献中公开的算法的结构中是充分的，这些是现有的结构，因此省略详细的说明。此外，记录部290_i是记录秘密移位装置200_i的处理所需的信息的结构部。例如，记录后述的输入的数值的MSB位置的上限值M。

通过由W个秘密移位装置200_i进行的协调计算，秘密移位系统20实现作为多方协议的移位量隐匿移位(其1)的秘密计算。因此，秘密移位系统20的模数转换单元210(未图示)由模数转换部210₁、…、210_W构成，第一标志计算单元220(未图示)由第一标志计算部220₁、…、220_W构成，第二标志计算单元230(未图示)由第二标志计算部230₁、…、230_W构成，移位量计算单元240(未图示)由移位量计算部240₁、…、240_W构成，左移位单元250(未图示)由左移位部250₁、…、250_W构成，右移位单元260(未图示)由右移位部260₁、…、260_W构成，第三标志计算单元270(未图示)由第三标志计算部270₁、…、270_W构成，移位值计算单元280(未图示)由移位值计算单元280₁、…、280_W构成。

将P设为素数，将p设为素数P的阶，将M设为输入的数值的MSB位置的上限值，秘密移位系统20根据数值a的份额[[a]]^P和移位量ρ的份额<<ρ>>^Q(其中ρ≧0时设为表示左移位，ρ<0时设为表示右移位)，计算将数值a进行ρ位移位而得到的数值s份额[[s]]^P(其中，s＝2^ρa)。以下，根据图6对秘密移位系统20的动作进行说明。

在S210中，模转换单元210根据份额<<ρ>>^Q，计算份额<<ρ>>^p。模数转换单元210例如构成为能执行模数转换即可。

在S220中，第一标志计算单元220根据份额<<ρ>>^Q，计算份额[[f_L]]²＝[[(ρ≧0)]]²。第一标志计算单元220构成为例如根据份额<<ρ>>^Q，计算份额<<(ρ≧0)>>^Q，使用模数转换，根据份额<<(ρ≧0)>>^Q，计算份额<<(ρ≧0)>>²，并且将份额<<(ρ≧0)>>²转换为份额[[f_L]]²＝[[(ρ≧0)]]²即可。此外，也可以代替份额<<ρ>>^Q，而使用份额<<ρ>>^p。

在S230中，第二标志计算单元230根据由S220计算出的份额[[f_L]]²，计算<<f_L>>^p。第二标志计算单元230例如构成为能执行mod 2→mod p转换即可。

在S240中，移位量计算单元240根据由S210计算的份额<<ρ>>^p、由S230计算的份额<<f_L>>^p和上限值M，计算份额<<ρ’>>^p＝<<ρ>>^p+M-M<<f_L>>^p。

在S250中，左移位单元250根据份额[[a]]^P和由S240计算的份额<<ρ’>>^p，计算份额[[b]]^P＝[[2^ρ’a]]^P。左移位单元250例如构成为能够执行移位量隐匿左移位即可。

在S260中，右移位单元260根据由S250计算的份额[[b]]^P和上限值M，计算份额[[c]]^P＝[[2^ρ’a/2^M]]^P。右移位单元260例如构成为能够执行移位量公开右移位即可。

在S270中，第三标志计算单元270根据由S220计算的份额[[f_L]]²，计算份额[[f_L]]^P。第三标志计算单元270例如构成为能够执行mod 2→mod P转换即可。

在S280中，移位值计算单元280根据由S250计算的份额[[b]]^P、由S260计算的份额[[c]]^P和由P270计算的份额[[f_L]]^P，计算份额[[s]]^P＝[[c]]^P+([[b]]^P-[[c]]^P)[[f_L]]^P。

根据本发明的实施方式，能够在隐匿了作为移位对象的数值和移位量的状态下高速地进行移位运算。尤其是，虽然能够右移位的量有限制，但能够高速地进行移位运算。

<第三实施方式>

以下，参照图7～图9对秘密移位系统30进行说明。图7是表示秘密移位系统30的结构的框图。秘密移位系统30包括W个(W为3以上的规定整数)秘密移位装置300₁、…、300_W。秘密移位装置300₁、…、300_W与网络800连接，能够相互进行通信。网络800例如可以是因特网等通信网络或广播通信路径等。图8是表示秘密移位装置300_i(1≦i≦W)的结构的框图。图9是表示秘密移位系统30的动作的流程图。

如图8所示，秘密移位装置300_i包括模数转换部310_i、第一标志计算部320_i、第二标志计算部330_i、移位量计算部340_i、左移位部350_i、右移位部360_i、第三标志计算部370_i、移位值计算部380_i、记录部390_i。除了记录部390_i以外的秘密移位装置300_i的各结构部被构成为能够执行秘密计算所需的运算、即<技术背景>中说明的协议中的、在实现各结构部的功能上所需的运算。在本发明中，用于实现各个运算的具体的功能结构在例如可执行参考非专利文献1～5的各个非专利文献中公开的算法的结构中是充分的，这些是现有的结构，因此省略详细的说明。此外，记录部390_i是记录秘密移位装置300_i的处理所需的信息的结构部。例如，记录后述的输入的数值的MSB位置的上限值M(以下，称为第一上限值)或发明容许的MSB位置的上限值M’(以下，称为第二上限值)。

通过由W个秘密移位装置300_i进行的协调计算，秘密移位系统30实现作为多方协议的移位量隐匿移位(其2)的秘密计算。因此，秘密移位系统30的模数转换单元310(未图示)由模数转换部310₁、…、310_W构成，第一标记计算单元320(未图示)由第一标记计算部320₁、…、320_W构成，第二标记计算单元330(未图示)由第二标记计算部330₁、…、330_W构成，移位量计算单元340(未图示)由移位量计算部340₁、…、340_W构成，左移位单元350(未图示)由左移位部350₁、…、350_W构成，右移位单元360(未图示)由右移位部360₁、…、360_W构成，第三标记计算单元370(未图示)由第三标记计算部370₁、…、370_W构成，移位值计算单元380_i(未图示)由移位值计算部380₁、…、380_W构成。

将P设为素数，将p设为素数P的阶，将Q设为剩余环的阶，将M设为输入的数值的MSB位置可取的上限值，将M’设为份额允许的MSB位置的上限值，秘密移位系统30根据数值a的份额[[a]]^P和移位量ρ的份额<<ρ>>^Q(其中，ρ≧0时设为表示左移位，ρ<0时设为表示右移位)，计算将数值a进行ρ位移位而得到的数值s的份额[[s]]^P(其中，s＝a/2^ρ)。以下，根据图9对秘密移位系统30的动作进行说明。

在S310中，模转换单元310根据份额<<ρ>>^Q，计算份额<<ρ>>^p。模数转换单元310例如构成为能执行模数转换即可。

在S320中，第一标志计算单元320根据份额<<ρ>>^Q、第一上限值M、数值u＝M’-M+1和数值d＝ceiling(((M-1)/u)_Re)，计算份额[[f₀]]²＝[[(ρ≧-M+1)]]²,[[f₁]]²＝[[(ρ≧-M+1+u)]]²,…,[[f_d-1]]²＝[[(ρ≧-M+1+(d-1)u)]]²,[[f_L]]²＝[[(ρ≧0)]]²。第一标志计算单元320例如构成为根据份额<<ρ>>^Q，计算份额<<(ρ≧-M+1)>>^Q,<<(ρ≧-M+1+u)>>^Q,…,<<(ρ≧-M+1+(d-1)u)>>^Q,<<(ρ≧0)>>^Q，并使用模数转换，根据份额<<(ρ≧-M+1)>>^Q,<<(ρ≧-M+1+u)>>^Q,…,<<(ρ≧-M+1+(d-1)u)>>^Q,<<(ρ≧0)>>^Q，计算<<(ρ≧-M+1)>>²,<<(ρ≧-M+1+u)>>²,…,<<(ρ≧-M+1+(d-1)u)>>²,<<(ρ≧0)>>²，将份额<<(ρ≧-M+1)>>²,<<(ρ≧-M+1+u)>>²,…,<<(ρ≧-M+1+(d-1)u)>>²,<<(ρ≧0)>>²转换为份额[[f₀]]²＝[[(ρ≧-M+1)]]²,[[f₁]]²＝[[(ρ≧-M+1+u)]]²,…,[[f_d-1]]²＝[[(ρ≧-M+1+(d-1)u)]]²,[[f_L]]²＝[[(ρ≧0)]]²即可。另外，数值u和数值d可以是第一标志计算单元320根据第一上限值M和第二上限值M’而进行计算，数值u和数值d也可以预先记录在记录部390_i中。

在S330中，第二标志计算单元330根据由S320计算的份额[[f₁]]²,[[f₂]]²,…,[[f_d-1]]²,[[f_L]]²，计算<<f₁>>^p,<<f₂>>^p,…,<<f_d-1>>^p,<<f_L>>^p。第二标志计算单元330例如构成为能执行mod 2→mod p转换即可。

在S340中，移位量计算单元340计算由S310计算的份额<<ρ>>^p、由S330计算的份额<<f₁>>^p,<<f₂>>^p,…,<<f_d-1>>^p,<<f_L>>^p、第一上限值M、数值u和数值d，计算<<ρ’>>^p＝<<ρ>>^p+M-1-u(Σ_1≦i<d<<f_i>>^p)+((d-1)u-M+1)<<f_L>>^p。

在S350中，左移位单元350根据份额[[a]]^P和由S340计算的份额<<ρ’>>^p，计算份额[[b]]^P＝[[2^ρ’a]]^P。左移位单元350例如构成为能够执行移位量隐匿左移位即可。

在S360中，右移位单元360根据由S350计算的份额[[b]]^P、第一上限值M、数值u和数值d，计算份额[[c₀]]^P＝[[2^ρ’a/2^M-1]]^P,[[c₁]]^P＝[[2^ρ’a/(2^M-1-u)]]^P,…,[[c_d-1]]^P＝[[2^ρ’a/(2^M-1-(d-1)u)]]^P。右移位单元360例如构成为能够执行总括移位量公开右移位即可。

在S370中，第三标志计算单元370根据由S320计算的份额[[f₀]]²,[[f₁]]²,…,[[f_d-1]]²,[[f_L]]²，计算份额[[f₀]]^P,[[f₁]]^P,…,[[f_d-1]]^P,[[f_L]]^P。第三标记计算单元370例如构成为能执行mod 2→mod P转换即可。

在S380中，移位值计算单元380根据由S350计算的份额[[b]]^P、由S360计算的份额[[c₀]]^P,[[c₁]]^P,…,[[c_d-1]]^P和由S370计算的份额[[f₀]]^P,[[f₁]]^P,…,[[f_d-1]]^P,计算份额[[s]]^P＝[[c₀]]^P[[f₀]]^P+([[c₁]]^P-[[c₀]]^P)[[f₁]]^P+…+([[c_d-1]]^P-[[c_d-2]]^P)[[f_d-1]]^P+([[b]]^P-[[c_d-1]]^P)[[f_L]]^P。

根据本发明的实施方式，能够在隐匿了作为移位对象的数值和移位量的状态下高速地进行移位运算。尤其是，能够以对能右移位的量没有限制的方式，高速地进行移位运算。

<第四实施方式>

以下，参照图7～图9对秘密移位系统40进行说明。图7是表示秘密移位系统40的结构的框图。秘密移位系统40包括W个(W为3以上的规定的整数)秘密移位装置400₁、…、400_W。秘密移位装置400₁、…、400_W与网络800连接，能够相互进行通信。网络800例如可以是因特网等通信网络或广播通信路径等。图8是表示秘密移位装置400_i(1≦i≦W)的结构的框图。图9是表示秘密移位系统40的动作的流程图。

如图8所示，秘密移位装置400_i包括模数转换部410_i、第一标志计算部420_i、第二标志计算部430_i、移位量计算部440_i、左移位部450_i、右移位部460_i、第三标志计算部470_i、移位值计算部480_i、记录部490_i。除了记录部490_i以外的秘密移位装置400_i的各结构部构成为能够执行秘密计算所需的运算、即<技术背景>中说明的协议中的、在实现各结构部的功能上所需的运算。在本发明中，用于实现各个运算的具体的功能结构在例如可执行参考非专利文献1～5的各个非专利文献中公开的算法的结构中是充分的，这些是现有的结构，因此省略详细的说明。此外，记录部490_i是记录秘密移位装置400_i的处理所需的信息的结构部。例如，记录后述的输入的数值的MSB位置的上限值M(以下，称为第一上限值)或份额容许的MSB位置的上限值M’(以下，称为第二上限值)。例如，记录后述的由分割的右移位覆盖的右移位量的范围[R,R’]。

通过由W个秘密移位装置400_i进行的协调计算，秘密移位系统40实现作为多方协议的移位量隐匿移位(其3)的秘密计算。因此，秘密移位系统40的模数转换单元410(未图示)由模数转换部410₁、…、410_W构成，第一标记计算单元420(未图示)由第一标记计算部420₁、…、420_W构成，第二标记计算单元430(未图示)由第二标记计算部430₁、…、430_W构成，移位量计算单元440(未图示)由移位量计算部440₁、…、440_W构成，左移位单元450(未图示)由左移位部450₁、…、450_W构成，右移位单元460(未图示)由右移位部460₁、…、460_W构成，第三标记计算单元470(未图示)由第三标记计算部470₁、…、470_W构成，移位值计算单元480(未图示)由移位值计算单元480₁、…、480_W构成。

将P设为素数，将p设为素数P的阶，将Q设为剩余环的阶，将M设为输入的数值的MSB位置可取的上限值，将M’设为份额允许的MSB位置的上限值，将[R,R’]设为以分割后的右移位覆盖的右移位量的范围，秘密移位系统40根据数值a的份额[[a]]^P和移位量ρ的份额<<ρ>>^Q(其中，ρ≧0时设为表示左移位，ρ<0时设为表示右移位)，计算将数值a进行ρ位移位而得到的数值s的份额[[s]]^P(其中，s＝a/2^ρ)。以下，根据图9对秘密移位系统40的动作进行说明。

在S410中，模数转换单元410根据份额<<ρ>>^Q，计算份额<<ρ>>^p。模数转换单元410例如构成为能够执行模数转换即可。

在S420中，第一标志计算单元420根据份额<<ρ>>^Q、范围[R,R’]、数值u(u是满足u≦M’-M+1的整数)和数值d(d是满足d≧ceiling(((R’-R+1)/u)_Re)的整数)，计算份额[[f₀]]²＝[[(ρ≧-R’)]]²,[[f₁]]²＝[[(ρ≧-R’+u)]]²,…,[[f_d-1]]²＝[[(ρ≧-R’+(d-1)u)]]²,[[f_L]]²＝[[(ρ≧-R+1)]]²。第一标志计算单元420例如根据份额<<ρ>>^Q，计算份额<<(ρ≧-R’)>>^Q,<<(ρ≧-R’+u)>>^Q,…,<<(ρ≧-R’+(d-1)u)>>^Q,<<(ρ≧-R+1)>>^Q，并使用模数转换，根据份额<<(ρ≧-R’)>>^Q,<<(ρ≧-R’+u)>>^Q,…,<<(ρ≧-R’+(d-1)u)>>^Q,<<(ρ≧-R+1)>>^Q，计算份额<<(ρ≧-R’)>>²,<<(ρ≧-R’+u)>>²,…,<<(ρ≧-R’+(d-1)u)>>²,<<(ρ≧-R+1)>>²，将份额<<(ρ≧-R’)>>²,<<(ρ≧-R’+u)>>²,…,<<(ρ≧-R’+(d-1)u)>>²,<<(ρ≧-R+1)>>²转换为份额[[f₀]]²＝[[(ρ≧-R’)]]²,[[f₁]]²＝[[(ρ≧-R’+u)]]²,…,[[f_d-1]]²＝[[(ρ≧-R’+(d-1)u)]]²,[[f_L]]²＝[[(ρ≧-R+1)]]²即可。另外，也可以代替份额<<ρ>>^Q，而使用份额<<ρ>>^p。并且，数值u和数值d也可以预先记录在记录部490_i中。

在S430中，第二标志计算单元430根据由S420计算的份额[[f₁]]²,[[f₂]]²,…,[[f_d-1]]²,[[f_L]]²，计算份额<<f₁>>^p,<<f₂>>^p,…,<<f_d-1>>^p,<<f_L>>^p。第二标志计算单元430例如构成为能执行mod 2→mod p转换即可。

在S440中，移位量计算单元440根据由S410计算的份额<<ρ>>^p、由S430计算的份额<<f₁>>^p,<<f₂>>^p,…,<<f_d-1>>^p,<<f_L>>^p、范围的上限值R’、数值u和数值d，计算份额<<ρ’>>^p＝<<ρ>>^p+R’-u(Σ_1≦i<d<<f_i>>^p)+((d-1)u-R’)<<f_L>>^p。

在S450中，左移位单元450根据由份额[[a]]^P和由S440计算的份额<<ρ’>>^p，计算份额[[b]]^P＝[[2^ρ’a]]^P。左移位单元450例如构成为能够执行移位量隐匿左移位即可。

在S460中，右移位单元460根据由S450计算的份额[[b]]^P、范围的上限值R’、数值u和数值d，计算份额[[c₀]]^P＝[[2^ρ’a/2^R’]]^P,[[c₁]]^P＝[[2^ρ’a/(2^R’-u)]]^P,…,[[c_d-1]]^P＝[[2^ρ’a/(2^R’-(d-1)u)]]^P。右移位单元460例如构成为能够执行总括移位量公开右移位即可。

在S470中，第三标志计算单元470根据由S420计算的份额[[f₀]]²,[[f₁]]²,…,[[f_d-1]]²,[[f_L]]²，计算份额[[f₀]]^P,[[f₁]]^P,…,[[f_d-1]]^P,[[f_L]]^P。第三标记计算单元470例如构成为能够执行mod 2→mod P转换即可。

在S480中，移位值计算单元480根据由S450计算的份额[[b]]^P、由S460计算的份额[[c₀]]^P,[[c₁]]^P,…,[[c_d-1]]^P和由S470计算的份额[[f₀]]^P,[[f₁]]^P,…,[[f_d-1]]^P,[[f_L]]^P，计算份额[[s]]^P＝[[c₀]]^P[[f₀]]^P+([[c₁]]^P-[[c₀]]^P)[[f₁]]^P+…+([[c_d-1]]^P-[[c_d-2]]^P)[[f_d-1]]^P+([[b]]^P-[[c_d-1]]^P)[[f_L]]^P。

(变形例)

如在<技术背景>中所说明的那样，移位量隐匿移位(其3)在也可以不考虑比-R大的移位量的情况、也可以不考虑比-R’小的移位量的情况下，能够省略一部分计算。因此，在相当于这两个中的任一个的情况下，能够省略一部分计算地构成秘密移位系统40。

根据本发明的实施方式，能够在隐匿了成为移位对象的数值和移位量的状态下高速地进行移位运算。尤其是，能够以对能够右移位的量没有限制的方式，高速地进行移位运算。

<补记>

图10是表示实现上述各装置的计算机的功能结构的一个例子的图。上述的各装置中的处理能够通过向记录部220读入用于使计算机作为上述的各装置发挥功能的程序并使控制部2010、输入部2030、输出部2040等进行动作来实施。

本发明的装置例如作为单一的硬件实体，具有：能连接键盘等的输入部、能连接液晶显示器等的输出部、能连接能够对硬件实体的外部进行通信的通信装置(例如通信电缆)的通信部、CPU(也可以具有中央处理单元(Central Processing Unit)、闪存或寄存器等)、作为存储器的RAM(随机存取存储器)或ROM(只读存储器)、作为硬盘的外部存储装置、以及进行连接以在这些输入部、输出部、通信部、CPU、RAM、ROM、外部存储装置之间进行数据交换的总线。另外，根据需要，在硬件实体中也可以设置能够读写CD－ROM等的记录介质的装置(驱动器)等。作为具有这样的硬件资源的物理的实体，有通用计算机等。

在硬件实体的外部存储装置中，存储了用于实现上述的功能所需要的程序以及在该程序的处理中所需要的数据等(不限于外部存储装置，例如也可以预先读出程序，使其存储在作为专用存储装置的ROM)。而且，通过这些程序的处理所得到的数据等，被适当地存储在RAM或外部存储装置等中。

在硬件实体中，在外部存储装置(或者ROM等)所存储的各程序和该各程序的处理所需要的数据根据需要被读入到存储器，适当地在CPU中进行解释执行/处理。其结果，CPU实现规定的功能(作为上述、…部、…单元等表示的各构成要件)。

本发明不限于上述的实施方式，在不脱离本发明的宗旨的范围内能够进行适当变更。上述实施方式中说明的处理不仅按照记载的顺序按时序被执行，也可以根据执行处理的装置的处理能力或者根据需要并行或者单独地被执行。

如已述那样，在通过计算机实现上述实施方式中说明的硬件实体(本发明的装置)中的处理功能的情况下，硬件实体应该具有的功能性的处理内容通过程序被记述。然后，通过在计算机上执行该程序，在计算机上实现上述硬件实体中的处理功能。

记述了该处理内容的程序，能够被预先记录在计算机可读取的记录介质中。作为由计算机可读取的记录介质，例如磁记录装置、光盘、光磁记录介质、半导体存储器等什么样的装置都可以。具体地说，例如，作为磁记录装置，可以使用硬盘装置、软盘、磁带等，作为光盘，可以使用DVD(Digital Versatile Disc，数字通用光盘)、DVD－RAM(Random AccessMemory，随机存取存储器)、CD－ROM(Compact Disc Read Only Memory，压缩光盘只读存储器)、CD－R(Recordable，可记录)/RW(ReWritable，可改写)等，作为光磁记录介质，可以使用MO(Magneto-Optical disc，磁光盘)等，作为半导体存储器，可以使用EEP－ROM(Electronically Erasable and Programmable-Read Only Memory，电可擦可编程只读存储器)等。

而且，例如通过贩卖、转让、出租记录了该程序的DVD、CD－ROM等可便携式记录介质等来进行该程序的流通。进而，也可以将该程序预先存储在服务器计算机的存储装置中，经由网络，将该程序通过从服务器计算机转发到其它计算机，使该程序流通。

首先，执行这样的程序的计算机例如将从记录于便携式记录介质的程序或者服务器计算机转发而来的程序临时储存于自己的存储装置。接着，在执行处理时，该计算机读取储存于自己的存储装置的程序，并根据读取到的程序而执行处理。此外，作为该程序的其他执行形态，也可以设为计算机从便携式记录介质直接读取程序，执行按照该程序的处理，进一步也可以设为每当该计算机被从服务器计算机转发来程序，则该计算机依次执行按照接受到的程序的处理。此外，也可以设为如下结构：不从服务器计算机进行程序向该计算机的转发，则仅通过其执行指示和结果获取而实现处理功能，即通过所谓的ASP(ApplicationService Provider，应用服务提供商)型的服务，而执行上述的处理。另外，假设在本方式中的程序包括用于电子计算机的处理而提供的、与程序等效的信息(并非对于计算机的直接的指令，但具有规定计算机的处理的性质的数据等)。

而且，在该方式中，通过在计算机上执行规定的程序而构成硬件实体，但也可以将这些处理内容的至少一部分由硬件实现。

上述的本发明的实施方式的记载是以例证和记载为目的进行提示的。没有穷举的意思，也没有将发明限定于公开的严密形式的意思。变形和变化可以根据上述的教导而进行。实施方式是为了提供本发明的原理的最佳的例证，并且为了该领域的技术人员对本发明以各种实施方式且附加各种变形进行利用，以适合深思熟虑的实际的使用而选择并表现的方式。所有这样的变形或变化都在由附加的权利要求书所确定的本发明的范围内，所述附加权利要求书是按照公正合法公平给出的范围被解释的。

Claims (6)

1.一种秘密移位系统，设P为素数，设p为素数P的阶，设Q为剩余环的阶，设M为输入的数值的MSB位置可取的上限值，设M’为份额容许的MSB位置的上限值，设[R,R’]为以分割后的右移位覆盖的右移位量的范围，

该秘密移位系统由3个以上的秘密移位装置构成，从数值a的份额[[a]]^P和移位量ρ的份额<<ρ>>^Q，计算对数值a进行ρ位移位而得到的数值s的份额[[s]]^P，其中，ρ≧0时设为表示左移位，ρ<0时设为表示右移位，s＝2^ρa，

所述秘密移位系统包括：

模数转换单元，从份额<<ρ>>^Q，计算份额<<ρ>>^p；

第一标志计算单元，将u设为满足u≦M’-M+1的整数，将d设为满足d≧ceiling(((R’-R+1)/u)_Re)的整数，

从份额<<ρ>>^Q或份额<<ρ>>^p、范围[R,R’]、数值u和数值d，计算份额[[f₀]]²＝[[(ρ≧-R’)]]²,[[f₁]]²＝[[(ρ≧-R’+u)]]²,…,[[f_d-1]]²＝[[(ρ≧-R’+(d-1)u)]]²,[[f_L]]²＝[[(ρ≧-R+1)]]²；

第二标志计算单元，从份额[[f₁]]²,[[f₂]]²,…,[[f_d-1]]²,[[f_L]]²，计算份额<<f₁>>^p,<<f₂>>^p,…,<<f_d-1>>^p,<<f_L>>^p；

移位量计算单元，从份额<<ρ>>^p、份额<<f₁>>^p,<<f₂>>^p,…,<<f_d-1>>^p,<<f_L>>^p、范围的上限值R’、数值u和数值d，计算<<ρ’>>^p＝<<ρ>>^p+R’-u(Σ_1≦i<d<<f_i>>^p)+((d-1)u-R’)<<f_L>>^p；

左移位单元，从份额[[a]]^P和份额<<ρ’>>^p，计算份额[[b]]^P＝[[2^ρ’a]]^P；

右移位单元，从份额[[b]]^P、范围的上限值R’、数值u和数值d，计算份额[[c₀]]^P＝[[2^ρ’a/2^R’]]^P,[[c₁]]^P＝[[2^ρ’a/(2^R’-u)]]^P,…,[[c_d-1]]^P＝[[2^ρ’a/(2^R’-(d-1)u)]]^P；

第三标志计算装置，从份额[[f₀]]²,[[f₁]]²,…,[[f_d-1]]²,[[f_L]]²，计算份额[[f₀]]^P,[[f₁]]^P,…,[[f_d-1]]^P,[[f_L]]^P；以及

移位值计算单元，从份额[[b]]^P、份额[[c₀]]^P,[[c₁]]^P,…,[[c_d-1]]^P和份额[[f₀]]^P,[[f₁]]^P,…,[[f_d-1]]^P,[[f_L]]^P，计算份额[[s]]^P＝[[c₀]]^P[[f₀]]^P+([[c₁]]^P-[[c₀]]^P)[[f₁]]^P+…+([[c_d-1]]^P-[[c_d-2]]^P)[[f_d-1]]^P+([[b]]^P-[[c_d-1]]^P)[[f_L]]^P。

2.一种秘密移位装置，该秘密移位装置是秘密移位系统中的秘密移位装置，设P为素数，设p为素数P的阶，设Q为剩余环的阶，设M为输入的数值的MSB位置可取的上限值，设M’为份额容许的MSB位置的上限值，设[R,R’]为以分割后的右移位覆盖的右移位量的范围，

从数值a的份额[[a]]^P和移位量ρ的份额<<ρ>>^Q，计算对数值a进行ρ位移位而得到的数值s的份额[[s]]^P，其中，ρ≧0时设为表示左移位，ρ<0时设为表示右移位，s＝2^ρa，该秘密移位系统由3个以上的秘密移位装置构成，

所述秘密移位装置包括：

模数转换部，从份额<<ρ>>^Q，计算份额<<ρ>>^p；

第一标志计算部，将u设为满足u≦M’-M+1的整数，将d设为满足d≧ceiling(((R’-R+1)/u)_Re)的整数，

从份额<<ρ>>^Q或份额<<ρ>>^p、范围[R,R’]、数值u和数值d，计算份额[[f₀]]²＝[[(ρ≧-R’)]]²,[[f₁]]²＝[[(ρ≧-R’+u)]]²,…,[[f_d-1]]²＝[[(ρ≧-R’+(d-1)u)]]²,[[f_L]]²＝[[(ρ≧-R+1)]]²；

第二标志计算部，从份额[[f₁]]²,[[f₂]]²,…,[[f_d-1]]²,[[f_L]]²，计算份额<<f₁>>^p,<<f₂>>^p,…,<<f_d-1>>^p,<<f_L>>^p；

移位量计算部，从份额<<ρ>>^p、份额<<f₁>>^p,<<f₂>>^p,…,<<f_d-1>>^p,<<f_L>>^p、范围的上限值R’、数值u和数值d，计算<<ρ’>>^p＝<<ρ>>^p+R’-u(Σ_1≦i<d<<f_i>>^p)+((d-1)u-R’)<<f_L>>^p；

左移位部，从份额[[a]]^P和份额<<ρ’>>^p，计算份额[[b]]^P＝[[2^ρ’a]]^P；

右移位部，从份额[[b]]^P、范围的上限值R’、数值u和数值d，计算份额[[c₀]]^P＝[[2^ρ’a/2^R’]]^P,[[c₁]]^P＝[[2^ρ’a/(2^R’-u)]]^P,…,[[c_d-1]]^P＝[[2^ρ’a/(2^R’-(d-1)u)]]^P；

第三标志计算部，从份额[[f₀]]²,[[f₁]]²,…,[[f_d-1]]²,[[f_L]]²，计算份额[[f₀]]^P,[[f₁]]^P,…,[[f_d-1]]^P,[[f_L]]^P；以及

移位值计算部，从份额[[b]]^P、份额[[c₀]]^P,[[c₁]]^P,…,[[c_d-1]]^P和份额[[f₀]]^P,[[f₁]]^P,…,[[f_d-1]]^P,[[f_L]]^P，计算份额[[s]]^P＝[[c₀]]^P[[f₀]]^P+([[c₁]]^P-[[c₀]]^P)[[f₁]]^P+…+([[c_d-1]]^P-[[c_d-2]]^P)[[f_d-1]]^P+([[b]]^P-[[c_d-1]]^P)[[f_L]]^P。

3.一种秘密移位方法，设P为素数，设p为素数P的阶，设Q为剩余环的阶，设M为输入的数值的MSB位置可取的上限值，设M’为份额容许的MSB位置的上限值，设[R,R’]为以分割后的右移位覆盖的右移位量的范围，由3个以上的秘密移位装置构成的该秘密移位系统从数值a的份额[[a]]^P和移位量ρ的份额<<ρ>>^Q，计算对数值a进行ρ位移位而得到的数值s的份额[[s]]^P，其中，ρ≧0时设为表示左移位，ρ<0时设为表示右移位，s＝2^ρa，

所述秘密移位方法包括：

模数转换步骤，所述秘密移位系统从份额<<ρ>>^Q，计算份额<<ρ>>^p；

第一标志计算步骤，将u设为满足u≦M’-M+1的整数，将d设为满足d≧ceiling(((R’-R+1)/u)_Re)的整数，所述秘密移位系统从份额<<ρ>>^Q或份额<<ρ>>^p、范围[R,R’]、数值u和数值d，计算份额[[f₀]]²＝[[(ρ≧-R’)]]²,[[f₁]]²＝[[(ρ≧-R’+u)]]²,…,[[f_d-1]]²＝[[(ρ≧-R’+(d-1)u)]]²,[[f_L]]²＝[[(ρ≧-R+1)]]²；

第二标志计算步骤，所述秘密移位系统从份额[[f₁]]²,[[f₂]]²,…,[[f_d-1]]²,[[f_L]]²，计算份额<<f₁>>^p,<<f₂>>^p,…,<<f_d-1>>^p,<<f_L>>^p；

移位量计算步骤，所述秘密移位系统从份额<<ρ>>^p、份额<<f₁>>^p,<<f₂>>^p,…,<<f_d-1>>^p,<<f_L>>^p、范围的上限值R’、数值u和数值d，计算<<ρ’>>^p＝<<ρ>>^p+R’-u(Σ_1≦i<d<<f_i>>^p)+((d-1)u-R’)<<f_L>>^p；

左移位步骤，所述秘密移位系统从份额[[a]]^P和份额<<ρ’>>^p，计算份额[[b]]^P＝[[2^ρ’a]]^P；

右移位步骤，所述秘密移位系统从份额[[b]]^P、范围的上限值R’、数值u和数值d，计算份额[[c₀]]^P＝[[2^ρ’a/2^R’]]^P,[[c₁]]^P＝[[2^ρ’a/(2^R’-u)]]^P,…,[[c_d-1]]^P＝[[2^ρ’a/(2^R’-(d-1)u)]]^P；

第三标志计算步骤，所述秘密移位系统从份额[[f₀]]²,[[f₁]]²,…,[[f_d-1]]²,[[f_L]]²，计算份额[[f₀]]^P,[[f₁]]^P,…,[[f_d-1]]^P,[[f_L]]^P；以及

移位值计算步骤，所述秘密移位系统从份额[[b]]^P、份额[[c₀]]^P,[[c₁]]^P,…,[[c_d-1]]^P和份额[[f₀]]^P,[[f₁]]^P,…,[[f_d-1]]^P,[[f_L]]^P，计算份额[[s]]^P＝[[c₀]]^P[[f₀]]^P+([[c₁]]^P-[[c₀]]^P)[[f₁]]^P+…+([[c_d-1]]^P-[[c_d-2]]^P)[[f_d-1]]^P+([[b]]^P-[[c_d-1]]^P)[[f_L]]^P。

4.一种秘密移位系统，设P为素数，设p为素数P的阶，设M为移位量的上限值，

该秘密移位系统由3个以上的秘密移位装置构成，从数值a的份额[[a]]^P和移位量ρ的份额<<ρ>>^Q，计算对数值a进行ρ位移位而得到的数值s的份额[[s]]^P，其中，0≦ρ≦M,对数值a进行M位左移位而得到的数值2^Ma不溢出，s＝2^ρa，

所述秘密移位系统包括：

移位量计算单元，从份额<<ρ>>^p和上限值M，计算份额<<M-ρ>>^p；

左移位单元，从份额[[a]]^P和份额<<M-ρ>>^p，计算份额[[b]]^P＝[[2^M-ρa]]^P；以及

右移位单元，从份额[[b]]^P和上限值M，计算份额[s]]^P＝[[2^M-ρa/2^M]]^P。

5.一种秘密移位系统，设P为素数，设p为素数P的阶，设Q为剩余环的阶，设M为输入的数值的MSB位置可取的上限值，

该秘密移位系统由3个以上的秘密移位装置构成，从数值a的份额[[a]]^P和移位量ρ的份额<<ρ>>^Q，计算对数值a进行ρ位移位而得到的数值s的份额[[s]]^P，其中，ρ≧0时设为表示左移位，ρ<0时设为表示右移位，s＝2^ρa，

所述秘密移位系统包括：

模数转换单元，从份额<<ρ>>^Q，计算份额<<ρ>>^p；

第一标志计算单元，从份额<<ρ>>^Q或份额<<ρ>>^p，计算份额[[f_L]]²＝[[(ρ≧0)]]²；

第二标志计算单元，从份额[[f_L]]²，计算<<f_L>>^p；

移位量计算单元，从份额<<ρ>>^p、份额<<f_L>>^p和上限值M，计算份额<<ρ’>>^p＝<<ρ>>^p+M-M<<f_L>>^p；

左移位单元，从份额[[a]]^P和份额<<ρ’>>^p，计算份额[[b]]^P＝[[2^ρ’a]]^P；

右移位单元，从份额[[b]]^P和上限值M，计算份额[[c]]^P＝[[2^ρ’a/2^M]]^P；

第三标志计算装置，从份额[[f_L]]²，计算份额[[f_L]]^P；以及

移位值计算单元，从份额[[b]]^P、份额[[c]]^P和份额[[f_L]]^P，计算份额[[s]]^P＝[[c]]^P+([[b]]^P-[[c]]^P)[[f_L]]^P。

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

Images