WO2022079890A1

WO2022079890A1 - 秘密シフトシステム、秘密シフト装置、秘密シフト方法、プログラム

Info

Publication number: WO2022079890A1
Application number: PCT/JP2020/039077
Authority: WO
Inventors: 大五十嵐
Original assignee: Nippon Telegraph and Telephone Corp
Current assignee: NTT Inc
Priority date: 2020-10-16
Filing date: 2020-10-16
Publication date: 2022-04-21
Anticipated expiration: 2023-04-16
Also published as: EP4210028A1; JP7485067B2; EP4210028A4; JPWO2022079890A1; AU2020472387B2; CN116324934B; US20230379151A1; AU2020472387A9; EP4210028B1; CN116324934A; AU2020472387A1

Abstract

シフト対象となる数値とシフト量を入力として左シフトを行うプロトコルを用いて、高速にビットシフト演算を行う秘密計算技術を提供する。数値aのシェア[[a]]Pとシフト量ρのシェア<<ρ>>Qから、数値aをρビットシフトして得られる数値sのシェア[[s]]Pを計算する秘密シフトシステムであって、シェア<<ρ>>pを計算するモジュラス変換手段と、シェア[[f0]]2, …, [[fL]]2を計算する第１フラグ計算手段と、シェア<<f1>>p, …, <<fL>>pを計算する第２フラグ計算手段と、シェア<<ρ'>>pを計算するシフト量計算手段と、シェア[[b]]Pを計算する左シフト手段と、シェア[[c0]]P, …,[[cd-1]]Pを計算する右シフト手段と、シェア[[f0]]P, …, [[fL]]Pを計算する第３フラグ計算手段と、シェア[[s]]Pを計算するシフト値計算手段とを含む。

Description

秘密シフトシステム、秘密シフト装置、秘密シフト方法、プログラム

　本発明は、秘密計算技術に関し、特に秘密計算においてビットシフト演算を行う技術に関する。

　秘密計算とは、暗号化された数値を復元することなく指定された演算の結果を得る方法のことである（例えば参考非特許文献１参照）。参考非特許文献１の方法では、数値を復元することのできる複数の情報を3つの秘密計算装置に分散するという暗号化を行い、数値を復元することなく、加減算、定数和、乗算、定数倍、論理演算（否定、論理積、論理和、排他的論理和）、データ形式変換（整数、二進数）の結果を3つの秘密計算装置に分散された状態、すなわち暗号化されたまま保持させることができる。一般に、分散数は3に限らずW（Wは3以上の所定の定数）とすることができ、W個の秘密計算装置による協調計算によって秘密計算を実現するプロトコルはマルチパーティプロトコルと呼ばれる。

（参考非特許文献１：千田浩司, 濱田浩気, 五十嵐大, 高橋克巳, “軽量検証可能３パーティ秘匿関数計算の再考,” In CSS，2010．）
　従来、浮動小数点演算を行う秘密計算のプロトコルや実装に関する文献として、非特許文献１や非特許文献２がある。浮動小数点演算を行うために必要となるビットシフト演算は、2進数のビットパターンを左右にずらす演算であり、コンピュータ処理では基本的な演算の一つである。

天田拓磨, 奈良成泰, 西出隆志, 吉浦裕,"通信量を削減した浮動小数点演算のためのマルチパーティ計算,"情報処理学会論文誌, Vol.60, No.9, pp.1433-1447, 2019. Randmets, J., "Programming Languages for Secure Multi-party Computation Application Development," PhD thesis. University of Tartu, 2017.

　しかし、ビットシフト演算を秘密計算で実行する場合、左右のシフト方向とシフト量を秘匿しながら演算するため計算コストが大きいという問題がある。

　そこで本発明は、シフト対象となる数値とシフト量を入力として左シフトを行うプロトコルを用いて、高速にビットシフト演算を行う秘密計算技術を提供することを目的とする。

　本発明の一態様は、Pを素数、pを素数Pのビット数、Qを剰余環の位数、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とシフト量ρのシェア<<ρ>>^p（ただし、0≦ρ≦M, 数値aをMビット左シフトして得られる数値2^Maはオーバーフローしないものとする）から、数値aをρビット右シフトして得られる数値sのシェア[[s]]^P（ただし、s=a/2^ρ）を計算する秘密シフトシステムであって、シェア<<ρ>>^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を計算するシフト値計算手段と、を含む。

　本発明によれば、シフト対象となる数値とシフト量を秘匿したまま高速にシフト演算を行うことが可能となる。

秘密シフトシステム１０の構成を示すブロック図である。秘密シフト装置１００_iの構成を示すブロック図である。秘密シフトシステム１０の動作を示すフローチャートである。秘密シフトシステム２０の構成を示すブロック図である。秘密シフト装置２００_iの構成を示すブロック図である。秘密シフトシステム２０の動作を示すフローチャートである。秘密シフトシステム３０の構成を示すブロック図である。秘密シフト装置３００_iの構成を示すブロック図である。秘密シフトシステム３０の動作を示すフローチャートである。本発明の実施形態における各装置を実現するコンピュータの機能構成の一例を示す図である。

　以下、本発明の実施形態について、詳細に説明する。なお、同じ機能を有する構成部には同じ番号を付し、重複説明を省略する。

　各実施形態の説明に先立って、この明細書における表記方法について説明する。

　^（キャレット）は上付き添字を表す。例えば、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を秘密分散の分散数（つまり、秘密計算のパーティ数）とする。例えば、n=3とするとよい。

　[[x]]^yはmod y 要素xを(k, n)-秘密分散したシェアを表す。秘密分散の方法として、例えば、Shamir秘密分散や複製秘密分散を用いることができる。以下、mod y 要素xを(k, n)-複製秘密分散したシェアを<<x>>^yで表す。(k, n)-複製秘密分散は(k, n)-秘密分散であることから、(k, n)-秘密分散したシェアに適用できるプロトコルは(k, n)-複製秘密分散したシェアにも適用することができる。なお、シェアを<<x>>^yと表すときは、複製秘密分散の性質を利用していることを意味する。また、特に(k, k)-複製秘密分散は(k, k)-加法的秘密分散と呼ばれる。以下、mod y 要素xを(k, k)-加法的秘密分散したシェアを<x>^yで表す。

　[[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はそれぞれ仮数部、指数部を表す）を浮動小数点(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
　具体的には、参考非特許文献２に記載の方法がある。

（参考非特許文献２：Kikuchi, R., Ikarashi, D., Matsuda, T., Hamada, K. and Chida, K., “Efficient Bit-Decomposition and Modulus-Conversion Protocols with an Honest Majority,” 23rd Australasian Conference on Information Security and Privacy(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）
　具体的には、参考非特許文献２に記載の方法がある。

［mod 2 → mod q 変換］
入力：数値xのシェア[[x]]²（数値xのシェア<<x>>²）
出力：数値xのシェア[[x]]^q（数値xのシェア<<x>>^q）
　具体的には、参考非特許文献２に記載の方法がある。

［シフト量公開右シフト］
入力：数値xのシェア[[x]]^q、シフト量ρ
出力：数値xをρビット右シフトして得られる数値のシェア[[x/2^ρ]]^q
　具体的には、参考非特許文献３に記載の方法がある。

（参考非特許文献３：三品気吹, 五十嵐大, 濱田浩気, 菊池亮, “高精度かつ高効率な秘密ロジスティック回帰の設計と実装,”CSS2018, 2018.）
［一括シフト量公開右シフト］
入力：数値xのシェア[[x]]^q、シフト量ρ₀, …, ρ_m-1
出力：数値xをρ₀ビット, …, ρ_m-1ビット右シフトして得られる数値のシェア[[x/2^ρ_0]]^q, …, [[x/2^ρ_m-1]]^q
　具体的には、参考非特許文献４に記載の方法がある。

（参考非特許文献４：五十嵐大, “M op/sを超える秘密計算上の初等関数群,”SCIS2020, 2020.）
　なお、自明な方法として、シフト量公開右シフトの繰り返しで、一括シフト量公開右シフトを構成することもできる。

［商転移を使うモジュラス変換］
入力：数値xのシェア<<x>>^q
出力：数値xのシェア<<x>>^r
　具体的には、参考非特許文献２に記載の方法がある。

［ビット分解］
入力：数値xのシェア[[x]]^q
パラメータ：入力される数値の最大ビット数M
出力：数値xのシェア[[x]]^{2^M}
　具体的には、参考非特許文献２に記載の方法がある。

《本発明の秘密計算プロトコル》
　続いて、本発明の秘密計算プロトコルについて説明する。

［乗法的ローテーション（シフト量秘匿左シフト）］
入力：数値aのシェア[[a]]^P, ローテーション量（シフト量）ρ(≧0)のシェア<<ρ>>^p
出力：数値aをρビット左シフトして得られる数値のシェア[[2^ρa]]^P
　出力となるシェアは乗算や指数関数計算のプロトコル等を用いることで計算することもできるが、ランダム置換（参考非特許文献５参照）の考えを用いた方法で計算することもできる。具体例として、n=3の場合について説明する。

（参考非特許文献５：五十嵐大, 濱田浩気, 菊池亮, 千田浩司, “インターネット環境レスポンス1秒の統計処理を目指した,秘密計算基数ソートの改良,” SCIS2014, 2014.）
（ラウンド1）
step1：シェア[[a]]^Pを、パーティ0、パーティ1がシェアを持つ(k, k)-加法的秘密分散<a>^Pに変換する。

step2：パーティ0、パーティ1は乱数r₀₁を共有しておく。また、パーティ1、パーティ2は乱数r₁₂を共有しておく。

step3：パーティ0は、b₀=2^{(<<ρ>>^p)_01}<a>^P ₀-r₀₁を計算し、b₀をパーティ2に送る。

　ここで、<<ρ>>^p ₀₁はシェア<<ρ>>^pに関してパーティ0、パーティ1が保持するシェアを表す。また、<a>^P ₀はシェア<a>^Pに関してパーティ0が保持するシェアを表す。

step4：パーティ1はb₁=2^{(<<ρ>>^p)_12}(2^{(<<ρ>>^p)_01}<a>^P ₁+r₀₁)-r₁₂を計算し、b₁をパーティ0に送る。

　ここで、<<ρ>>^p ₁₂はシェア<<ρ>>^pに関してパーティ1、パーティ2が保持するシェアを表す。また、<a>^P ₁はシェア<a>^Pに関してパーティ1が保持するシェアを表す。

（ラウンド2）
step5：パーティ0は<c>^P ₀=2^{(<<ρ>>^p)_20}b₁を計算する。

　ここで、<<ρ>>^p ₂₀はシェア<<ρ>>^pに関してパーティ2、パーティ0が保持するシェアを表す。

step6：パーティ2は<c>^P ₂=2^{(<<ρ>>^p)_20}(2^{(<<ρ>>^p)_12}b₀+r₁₂)を計算する。

（ラウンド3）
step7：シェア<c>^Pを(k, n)-秘密分散のシェア[[c]]^Pに変換する。

　ここで、c=2^ρaが成り立っている。

［シフト量秘匿右シフト］
入力：数値aのシェア[[a]]^P, シフト量ρのシェア<<ρ>>^p
パラメータ：シフト量の上限値M
　ただし、0≦ρ≦M, 数値aをMビット左シフトして得られる数値2^Maはオーバーフローしないものとする。

出力：数値aをρビット右シフトして得られる数値のシェア[[a/2^ρ]]^P
step1：<<M-ρ>>^pを計算する.
step2：乗法的ローテーションを用いて、数値aをM-ρビット左シフトして得られる数値のシェア[[2^M-ρa]]^Pを計算する。

step3：シフト量公開右シフトを用いて、数値2^M-ρaをMビット右シフトして得られる数値のシェア[[a/2^ρ]]^P=[[2^M-ρa/2^M]]^Pを計算する。

［シフト量秘匿シフト（その１）］
入力：数値aのシェア[[a]]^P、シフト量ρのシェア<<ρ>>^Q（ただし、ρ≧0の場合は左シフト、ρ<0の場合は右シフトを表すものとする）
パラメータ：入力される数値のMSB(Most Significant Bit)位置のとりうる上限値M
出力：数値aをρビットシフトして得られる数値sのシェア[[s]]^P
　ここで、s=2^ρaが成り立つ。

step1：モジュラス変換を用いて、シェア<<ρ>>^pを計算する。モジュラス変換には、例えば、先述の商転移を使うモジュラス変換を用いることができる。

step2：大小比較により、[[f_L]]²=[[(ρ≧0)]]²を計算する。

step3：mod 2 → mod p 変換を用いて、<<f_L>>^pを計算する。

step4：<<ρ’>>^p=<<ρ>>^p+M-M<<f_L>>^pを計算する。

step5：乗法的ローテーションを用いて、[[b]]^P=[[2^ρ’a]]^Pを計算する。

step6：シフト量公開右シフトを用いて、[[c]]^P=[[2^ρ’a/2^M]]^Pを計算する。

step7：mod 2 → mod P 変換を用いて、[[f_L]]^Pを計算する。

step8：[[s]]^P=[[c]]^P+([[b]]^P-[[c]]^P)[[f_L]]^Pを計算する。

　この式は選択ゲートになっており、ρ<0の場合はs=c、ρ≧0の場合はs=bとなる。

［シフト量秘匿シフト（その２）］
入力：数値aのシェア[[a]]^P、シフト量ρのシェア<<ρ>>^Q（ただし、ρ≧0の場合は左シフト、ρ<0の場合は右シフトを表すものとする）
パラメータ：入力される数値のMSB位置のとりうる上限値M、シェアが許容するMSB位置の上限値M’
出力：数値aをρビットシフトして得られる数値sのシェア[[s]]^P
　ここで、s=2^ρaが成り立つ。

step1：u=M’-M+1, d=ceiling(((M-1)/u)_Re)を計算する。

　ここで、uは一回のシフト量秘匿右シフトでカバーできる右シフト量（具体的には、1からM’-Mビットの範囲の量）、dは1からM-1ビットの範囲の右シフトをするのに必要なシフト量秘匿右シフトの実行回数である。

step2：モジュラス変換を用いて、シェア<<ρ>>^pを計算する。モジュラス変換には、例えば、先述の商転移を使うモジュラス変換を用いることができる。

step3：大小比較により、[[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のことを推移的フラグという。

step4：mod 2 → mod p 変換を用いて、<<f₁>>^p, <<f₂>>^p, …, <<f_d-1>>^p, <<f_L>>^pを計算する。

　本ステップでは、<<f₀>>^pの計算は不要である。

step5：<<ρ’>>^p=<<ρ>>^p+M-1-u(Σ_1≦i<d<<f_i>>^p)+((d-1)u-M+1)<<f_L>>^pを計算する。

step6：乗法的ローテーションを用いて、[[b]]^P=[[2^ρ’a]]^Pを計算する。

step7：一括シフト量公開右シフトを用いて、[[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を計算する。

step8：mod 2 → mod P 変換を用いて、[[f₀]]^P, [[f₁]]^P, …, [[f_d-1]]^P, [[f_L]]^Pを計算する。

　本ステップでは、[[f₀]]^pの計算は必要である。

step9：[[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₁ならばc₁、…、f_Lならばs=bとなる。

［シフト量秘匿シフト（その３）］
入力：数値aのシェア[[a]]^P、シフト量ρのシェア<<ρ>>^Q（ただし、ρ≧0の場合は左シフト、ρ<0の場合は右シフトを表すものとする）
パラメータ：入力される数値のMSB位置のとりうる上限値M、シェアが許容するMSB位置の上限値M’
出力：数値aをρビットシフトして得られる数値sのシェア[[s]]^P
　ここで、s=2^ρaが成り立つ。

step1：uをu≦M’-M+1を満たす整数とする。また、[R, R’]を分割した右シフトでカバーする右シフト量の範囲とし、dをd≧ceiling(((R’-R+1)/u)_Re)を満たす整数とする。

　以下、{}_Lは、-Rより大きいシフト量を考慮しなくてよい場合（例えば、右シフトであると分かっている場合）、当該括弧で囲んだ部分の計算を省略できることを表す。また、{}₀は、-R’より小さいシフト量を考慮しなくてよい場合（例えば、右シフト量がシフト量秘匿シフト（その１）が適用できる値よりは大きいが極端に大きい値ではないと分かっている場合）、当該括弧で囲んだ部分の計算を省略できることを表す。

step3：大小比較により、{[[f₀]]²=[[(ρ≧-R’)]]²,}₀ [[f₁]]²=[[(ρ≧-R’+u)]]², …, [[f_d-1]]²=[[(ρ≧-R’+(d-1)u)]]²{, [[f_L]]²=[[(ρ≧-R+1)]]²}_Lを計算する。

step4：mod 2 → mod p 変換を用いて、<<f₁>>^p, <<f₂>>^p, …, <<f_d-1>>^p{, <<f_L>>^p}_Lを計算する。

step5：<<ρ’>>^p=<<ρ>>^p+R’-u(Σ_1≦i<d<<f_i>>^p){+((d-1)u-R’)<<f_L>>^p}_Lを計算する。

step7：一括シフト量公開右シフトを用いて、{[[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を計算する。

step8：mod 2 → mod P 変換を用いて、{[[f₀]]^P,}₀[[f₁]]^P, …, [[f_d-1]]^P{, [[f_L]]^P}_Lを計算する。

step9：[[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を計算する。

　なお、R=1, R’=M-1, u=M’-M+1, d=ceiling(((R’-R+1)/u)_Re)とすると、シフト量秘匿シフト（その３）はシフト量秘匿シフト（その２）となる。このことから、シフト量秘匿シフト（その３）はシフト量秘匿シフト（その２）を一般化したプロトコルである。

＜第１実施形態＞
　以下、図１～図３を参照して秘密シフトシステム１０について説明する。図１は、秘密シフトシステム１０の構成を示すブロック図である。秘密シフトシステム１０は、W個（Wは3以上の所定の整数）の秘密シフト装置１００₁、…、１００_Wを含む。秘密シフト装置１００₁、…、１００_Wは、ネットワーク８００に接続しており、相互に通信可能である。ネットワーク８００は、例えば、インターネットなどの通信網あるいは同報通信路などでよい。図２は、秘密シフト装置１００_i(1≦i≦W)の構成を示すブロック図である。図３は、秘密シフトシステム１０の動作を示すフローチャートである。

　図２に示すように秘密シフト装置１００_iは、シフト量計算部１４０_iと、左シフト部１５０_iと、右シフト部１６０_iと、記録部１９０_iを含む。記録部１９０_iを除く秘密シフト装置１００_iの各構成部は、秘密計算で必要とされる演算、つまり、＜技術的背景＞で説明したプロトコルのうち、各構成部の機能を実現するうえで必要になる演算を実行できるように構成されている。本発明において個々の演算を実現するための具体的な機能構成は、例えば参考非特許文献１～５のそれぞれで開示されるアルゴリズムを実行できるような構成で十分であり、これらは従来的構成であるから詳細な説明については省略する。また、記録部１９０_iは、秘密シフト装置１００_iの処理に必要な情報を記録する構成部である。例えば、後述するシフト量の上限値Mを記録しておく。

　W個の秘密シフト装置１００_iによる協調計算によって、秘密シフトシステム１０はマルチパーティプロトコルであるシフト量秘匿右シフトの秘密計算を実現する。よって、秘密シフトシステム１０のシフト量計算手段１４０（図示していない）はシフト量計算部１４０₁、…、１４０_Wで構成され、左シフト手段１５０（図示していない）は左シフト部１５０₁、…、１５０_Wで構成され、右シフト手段１６０（図示していない）は右シフト部１６０₁、…、１６０_Wで構成される。

　Pを素数、pを素数Pのビット数、Mをシフト量の上限値とし、秘密シフトシステム１０は、数値aのシェア[[a]]^Pとシフト量ρのシェア<<ρ>>^p（ただし、0≦ρ≦M, 数値aをMビット左シフトして得られる数値2^Maはオーバーフローしないものとする）から、数値aをρビット右シフトして得られる数値sのシェア[[s]]^P（ただし、s=a/2^ρ）を計算する。以下、図３に従い秘密シフトシステム１０の動作について説明する。

　Ｓ１４０において、シフト量計算手段１４０は、シェア<<ρ>>^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を計算する。右シフト手段１６０は、例えば、シフト量公開右シフトを実行できるように構成されていればよい。

　本発明の実施形態によれば、シフト対象となる数値とシフト量を秘匿したまま高速に右シフト演算を行うことが可能となる。

＜第２実施形態＞
　以下、図４～図６を参照して秘密シフトシステム２０について説明する。図４は、秘密シフトシステム２０の構成を示すブロック図である。秘密シフトシステム２０は、W個（Wは3以上の所定の整数）の秘密シフト装置２００₁、…、２００_Wを含む。秘密シフト装置２００₁、…、２００_Wは、ネットワーク８００に接続しており、相互に通信可能である。ネットワーク８００は、例えば、インターネットなどの通信網あるいは同報通信路などでよい。図５は、秘密シフト装置２００_i(1≦i≦W)の構成を示すブロック図である。図６は、秘密シフトシステム２０の動作を示すフローチャートである。

　図５に示すように秘密シフト装置２００_iは、モジュラス変換部２１０_iと、第１フラグ計算部２２０_iと、第２フラグ計算部２３０_iと、シフト量計算部２４０_iと、左シフト部２５０_iと、右シフト部２６０_iと、第３フラグ計算部２７０_iと、シフト値計算部２８０_iと、記録部２９０_iを含む。記録部２９０_iを除く秘密シフト装置２００_iの各構成部は、秘密計算で必要とされる演算、つまり、＜技術的背景＞で説明したプロトコルのうち、各構成部の機能を実現するうえで必要になる演算を実行できるように構成されている。本発明において個々の演算を実現するための具体的な機能構成は、例えば参考非特許文献１～５のそれぞれで開示されるアルゴリズムを実行できるような構成で十分であり、これらは従来的構成であるから詳細な説明については省略する。また、記録部２９０_iは、秘密シフト装置２００_iの処理に必要な情報を記録する構成部である。例えば、後述する入力される数値のMSB位置の上限値Mを記録しておく。

　W個の秘密シフト装置２００_iによる協調計算によって、秘密シフトシステム２０はマルチパーティプロトコルであるシフト量秘匿シフト（その１）の秘密計算を実現する。よって、秘密シフトシステム２０のモジュラス変換手段２１０（図示していない）はモジュラス変換部２１０₁、…、２１０_Wで構成され、第１フラグ計算手段２２０（図示していない）は第１フラグ計算部２２０₁、…、２２０_Wで構成され、第２フラグ計算手段２３０（図示していない）は第２フラグ計算部２３０₁、…、２３０_Wで構成され、シフト量計算手段２４０（図示していない）はシフト量計算部２４０₁、…、２４０_Wで構成され、左シフト手段２５０（図示していない）は左シフト部２５０₁、…、２５０_Wで構成され、右シフト手段２６０（図示していない）は右シフト部２６０₁、…、２６０_Wで構成され、第３フラグ計算手段２７０（図示していない）は第３フラグ計算部２７０₁、…、２７０_Wで構成され、シフト値計算手段２８０（図示していない）はシフト値計算部２８０₁、…、２８０_Wで構成される。

　Pを素数、pを素数Pのビット数、Mを入力される数値のMSB位置の上限値とし、秘密シフトシステム２０は、数値aのシェア[[a]]^Pとシフト量ρのシェア<<ρ>>^Q（ただし、ρ≧0の場合は左シフト、ρ<0の場合は右シフトを表すものとする）から、数値aをρビットシフトして得られる数値sのシェア[[s]]^P（ただし、s=2^ρa）を計算する。以下、図６に従い秘密シフトシステム２０の動作について説明する。

　Ｓ２１０において、モジュラス変換手段２１０は、シェア<<ρ>>^Qから、シェア<<ρ>>^pを計算する。モジュラス変換手段２１０は、例えば、モジュラス変換を実行できるように構成されていればよい。

　Ｓ２２０において、第１フラグ計算手段２２０は、シェア<<ρ>>^Qから、シェア[[f_L]]²=[[(ρ≧0)]]²を計算する。第１フラグ計算手段２２０は、例えば、シェア<<ρ>>^Qからシェア<<(ρ≧0)>>^Qを計算し、モジュラス変換を用いてシェア<<(ρ≧0)>>^Qからシェア<<(ρ≧0)>>²を計算し、シェア<<(ρ≧0)>>²をシェア[[f_L]]²=[[(ρ≧0)]]²に変換できるように構成されていればよい。なお、シェア<<ρ>>^Qの代わりにシェア<<ρ>>^pを用いてもよい。

　Ｓ２３０において、第２フラグ計算手段２３０は、Ｓ２２０で計算したシェア[[f_L]]²から、シェア<<f_L>>^pを計算する。第２フラグ計算手段２３０は、例えば、mod 2 → mod 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を計算する。第３フラグ計算手段２７０は、例えば、mod 2 →mod P変換を実行できるように構成されていればよい。

　Ｓ２８０において、シフト値計算手段２８０は、Ｓ２５０で計算したシェア[[b]]^PとＳ２６０で計算したシェア[[c]]^PとＳ２７０で計算したシェア[[f_L]]^Pから、シェア[[s]]^P=[[c]]^P+([[b]]^P-[[c]]^P)[[f_L]]^Pを計算する。

　本発明の実施形態によれば、シフト対象となる数値とシフト量を秘匿したまま高速にシフト演算を行うことが可能となる。特に、右シフトできる量に制限があるものの、高速にシフト演算を行うことが可能となる。

＜第３実施形態＞
　以下、図７～図９を参照して秘密シフトシステム３０について説明する。図７は、秘密シフトシステム３０の構成を示すブロック図である。秘密シフトシステム３０は、W個（Wは3以上の所定の整数）の秘密シフト装置３００₁、…、３００_Wを含む。秘密シフト装置３００₁、…、３００_Wは、ネットワーク８００に接続しており、相互に通信可能である。ネットワーク８００は、例えば、インターネットなどの通信網あるいは同報通信路などでよい。図８は、秘密シフト装置３００_i(1≦i≦W)の構成を示すブロック図である。図９は、秘密シフトシステム３０の動作を示すフローチャートである。

　図８に示すように秘密シフト装置３００_iは、モジュラス変換部３１０_iと、第１フラグ計算部３２０_iと、第２フラグ計算部３３０_iと、シフト量計算部３４０_iと、左シフト部３５０_iと、右シフト部３６０_iと、第３フラグ計算部３７０_iと、シフト値計算部３８０_iと、記録部３９０_iを含む。記録部３９０_iを除く秘密シフト装置３００_iの各構成部は、秘密計算で必要とされる演算、つまり、＜技術的背景＞で説明したプロトコルのうち、各構成部の機能を実現するうえで必要になる演算を実行できるように構成されている。本発明において個々の演算を実現するための具体的な機能構成は、例えば参考非特許文献１～５のそれぞれで開示されるアルゴリズムを実行できるような構成で十分であり、これらは従来的構成であるから詳細な説明については省略する。また、記録部３９０_iは、秘密シフト装置３００_iの処理に必要な情報を記録する構成部である。例えば、後述する入力される数値のMSB位置の上限値M（以下、第１上限値という）やシェアが許容するMSB位置の上限値M’（以下、第２上限値という）を記録しておく。

　W個の秘密シフト装置３００_iによる協調計算によって、秘密シフトシステム３０はマルチパーティプロトコルであるシフト量秘匿シフト（その２）の秘密計算を実現する。よって、秘密シフトシステム３０のモジュラス変換手段３１０（図示していない）はモジュラス変換部３１０₁、…、３１０_Wで構成され、第１フラグ計算手段３２０（図示していない）は第１フラグ計算部３２０₁、…、３２０_Wで構成され、第２フラグ計算手段３３０（図示していない）は第２フラグ計算部３３０₁、…、３３０_Wで構成され、シフト量計算手段３４０（図示していない）はシフト量計算部３４０₁、…、３４０_Wで構成され、左シフト手段３５０（図示していない）は左シフト部３５０₁、…、３５０_Wで構成され、右シフト手段３６０（図示していない）は右シフト部３６０₁、…、３６０_Wで構成され、第３フラグ計算手段３７０（図示していない）は第３フラグ計算部３７０₁、…、３７０_Wで構成され、シフト値計算手段３８０（図示していない）はシフト値計算部３８０₁、…、３８０_Wで構成される。

　Pを素数、pを素数Pのビット数、Qを剰余環の位数、Mを入力される数値のMSB位置のとりうる上限値、M’をシェアが許容するMSB位置の上限値とし、秘密シフトシステム３０は、数値aのシェア[[a]]^Pとシフト量ρのシェア<<ρ>>^Q（ただし、ρ≧0の場合は左シフト、ρ<0の場合は右シフトを表すものとする）から、数値aをρビットシフトして得られる数値sのシェア[[s]]^P（ただし、s=2^ρa）を計算する。以下、図９に従い秘密シフトシステム３０の動作について説明する。

　Ｓ３１０において、モジュラス変換手段３１０は、シェア<<ρ>>^Qから、シェア<<ρ>>^pを計算する。モジュラス変換手段３１０は、例えば、モジュラス変換を実行できるように構成されていればよい。

　Ｓ３２０において、第１フラグ計算手段３２０は、シェア<<ρ>>^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)]]²を計算する。第１フラグ計算手段３２０は、例えば、シェア<<ρ>>^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)]]²に変換できるように構成されていればよい。なお、シェア<<ρ>>^Qの代わりにシェア<<ρ>>^pを用いてもよい。また、数値uと数値dは、第１フラグ計算手段３２０が第１上限値Mと第２上限値M’とから計算するものであってもよいし、数値uと数値dは、予め記録部３９０_iに記録しておくのでもよい。

　Ｓ３３０において、第２フラグ計算手段３３０は、Ｓ３２０で計算したシェア[[f₁]]², [[f₂]]², …, [[f_d-1]]², [[f_L]]²から、シェア<<f₁>>^p, <<f₂>>^p, …, <<f_d-1>>^p, <<f_L>>^pを計算する。第２フラグ計算手段３３０は、例えば、mod 2 → mod p 変換を実行できるように構成されていればよい。

　Ｓ３４０において、シフト量計算手段３４０は、Ｓ３１０で計算したシェア<<ρ>>^pとＳ３３０で計算したシェア<<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を計算する。

　Ｓ３５０において、左シフト手段３５０は、シェア[[a]]^PとＳ３４０で計算したシェア<<ρ’>>^pから、シェア[[b]]^P=[[2^ρ’a]]^Pを計算する。左シフト手段３５０は、例えば、シフト量秘匿左シフトを実行できるように構成されていればよい。

　Ｓ３６０において、右シフト手段３６０は、Ｓ３５０で計算したシェア[[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を計算する。右シフト手段３６０は、例えば、一括シフト量公開右シフトを実行できるように構成されていればよい。

　Ｓ３７０において、第３フラグ計算手段３７０は、Ｓ３２０で計算したシェア[[f₀]]², [[f₁]]², …, [[f_d-1]]², [[f_L]]²から、シェア[[f₀]]^P, [[f₁]]^P, …, [[f_d-1]]^P, [[f_L]]^Pを計算する。第３フラグ計算手段３７０は、例えば、mod 2 →mod 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を計算する。

　本発明の実施形態によれば、シフト対象となる数値とシフト量を秘匿したまま高速にシフト演算を行うことが可能となる。特に、右シフトできる量に制限がない形で、高速にシフト演算を行うことが可能となる。

＜第４実施形態＞
　以下、図７～図９を参照して秘密シフトシステム４０について説明する。図７は、秘密シフトシステム４０の構成を示すブロック図である。秘密シフトシステム４０は、W個（Wは3以上の所定の整数）の秘密シフト装置４００₁、…、４００_Wを含む。秘密シフト装置４００₁、…、４００_Wは、ネットワーク８００に接続しており、相互に通信可能である。ネットワーク８００は、例えば、インターネットなどの通信網あるいは同報通信路などでよい。図８は、秘密シフト装置４００_i(1≦i≦W)の構成を示すブロック図である。図９は、秘密シフトシステム４０の動作を示すフローチャートである。

　図８に示すように秘密シフト装置４００_iは、モジュラス変換部４１０_iと、第１フラグ計算部４２０_iと、第２フラグ計算部４３０_iと、シフト量計算部４４０_iと、左シフト部４５０_iと、右シフト部４６０_iと、第３フラグ計算部４７０_iと、シフト値計算部４８０_iと、記録部４９０_iを含む。記録部４９０_iを除く秘密シフト装置４００_iの各構成部は、秘密計算で必要とされる演算、つまり、＜技術的背景＞で説明したプロトコルのうち、各構成部の機能を実現するうえで必要になる演算を実行できるように構成されている。本発明において個々の演算を実現するための具体的な機能構成は、例えば参考非特許文献１～５のそれぞれで開示されるアルゴリズムを実行できるような構成で十分であり、これらは従来的構成であるから詳細な説明については省略する。また、記録部４９０_iは、秘密シフト装置４００_iの処理に必要な情報を記録する構成部である。例えば、後述する入力される数値のMSB位置の上限値M（以下、第１上限値という）やシェアが許容するMSB位置の上限値M’（以下、第２上限値という）を記録しておく。例えば、後述する、分割した右シフトでカバーする右シフト量の範囲[R, R’]を記録しておく。

　W個の秘密シフト装置４００_iによる協調計算によって、秘密シフトシステム４０はマルチパーティプロトコルであるシフト量秘匿シフト（その３）の秘密計算を実現する。よって、秘密シフトシステム４０のモジュラス変換手段４１０（図示していない）はモジュラス変換部４１０₁、…、４１０_Wで構成され、第１フラグ計算手段４２０（図示していない）は第１フラグ計算部４２０₁、…、４２０_Wで構成され、第２フラグ計算手段４３０（図示していない）は第２フラグ計算部４３０₁、…、４３０_Wで構成され、シフト量計算手段４４０（図示していない）はシフト量計算部４４０₁、…、４４０_Wで構成され、左シフト手段４５０（図示していない）は左シフト部４５０₁、…、４５０_Wで構成され、右シフト手段４６０（図示していない）は右シフト部４６０₁、…、４６０_Wで構成され、第３フラグ計算手段４７０（図示していない）は第３フラグ計算部４７０₁、…、４７０_Wで構成され、シフト値計算手段４８０（図示していない）はシフト値計算部４８０₁、…、４８０_Wで構成される。

　Pを素数、pを素数Pのビット数、Qを剰余環の位数、Mを入力される数値のMSB位置のとりうる上限値、M’をシェアが許容するMSB位置の上限値、[R, R’]を分割した右シフトでカバーする右シフト量の範囲とし、秘密シフトシステム４０は、数値aのシェア[[a]]^Pとシフト量ρのシェア<<ρ>>^Q（ただし、ρ≧0の場合は左シフト、ρ<0の場合は右シフトを表すものとする）から、数値aをρビットシフトして得られる数値sのシェア[[s]]^P（ただし、s=2^ρa）を計算する。以下、図９に従い秘密シフトシステム４０の動作について説明する。

　Ｓ４１０において、モジュラス変換手段４１０は、シェア<<ρ>>^Qから、シェア<<ρ>>^pを計算する。モジュラス変換手段４１０は、例えば、モジュラス変換を実行できるように構成されていればよい。

　Ｓ４２０において、第１フラグ計算手段４２０は、シェア<<ρ>>^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)]]²を計算する。第１フラグ計算手段４２０は、例えば、シェア<<ρ>>^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は、予め記録部４９０_iに記録しておくのでよい。

　Ｓ４３０において、第２フラグ計算手段４３０は、Ｓ４２０で計算したシェア[[f₁]]², [[f₂]]², …, [[f_d-1]]², [[f_L]]²から、シェア<<f₁>>^p, <<f₂>>^p, …, <<f_d-1>>^p, <<f_L>>^pを計算する。第２フラグ計算手段４３０は、例えば、mod 2 → mod 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を計算する。第３フラグ計算手段４７０は、例えば、mod 2 →mod 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を計算する。

（変形例）
　シフト量秘匿シフト（その３）は、＜技術的背景＞で説明した通り、-Rより大きいシフト量を考慮しなくてよい場合や、-R’より小さいシフト量を考慮しなくてよい場合には、一部の計算を省略することができる。そこで、これら２つのいずれかに該当する場合は、秘密シフトシステム４０を一部の計算を省略するように構成することができる。

＜補記＞
　図１０は、上述の各装置を実現するコンピュータの機能構成の一例を示す図である。上述の各装置における処理は、記録部２０２０に、コンピュータを上述の各装置として機能させるためのプログラムを読み込ませ、制御部２０１０、入力部２０３０、出力部２０４０などに動作させることで実施できる。

　本発明の装置は、例えば単一のハードウェアエンティティとして、キーボードなどが接続可能な入力部、液晶ディスプレイなどが接続可能な出力部、ハードウェアエンティティの外部に通信可能な通信装置（例えば通信ケーブル）が接続可能な通信部、ＣＰＵ（Central Processing Unit、キャッシュメモリやレジスタなどを備えていてもよい）、メモリであるＲＡＭやＲＯＭ、ハードディスクである外部記憶装置並びにこれらの入力部、出力部、通信部、ＣＰＵ、ＲＡＭ、ＲＯＭ、外部記憶装置の間のデータのやり取りが可能なように接続するバスを有している。また必要に応じて、ハードウェアエンティティに、ＣＤ－ＲＯＭなどの記録媒体を読み書きできる装置（ドライブ）などを設けることとしてもよい。このようなハードウェア資源を備えた物理的実体としては、汎用コンピュータなどがある。

　ハードウェアエンティティの外部記憶装置には、上述の機能を実現するために必要となるプログラムおよびこのプログラムの処理において必要となるデータなどが記憶されている（外部記憶装置に限らず、例えばプログラムを読み出し専用記憶装置であるＲＯＭに記憶させておくこととしてもよい）。また、これらのプログラムの処理によって得られるデータなどは、ＲＡＭや外部記憶装置などに適宜に記憶される。

　ハードウェアエンティティでは、外部記憶装置（あるいはＲＯＭなど）に記憶された各プログラムとこの各プログラムの処理に必要なデータが必要に応じてメモリに読み込まれて、適宜にＣＰＵで解釈実行・処理される。その結果、ＣＰＵが所定の機能（上記、…部、…手段などと表した各構成部）を実現する。

　本発明は上述の実施形態に限定されるものではなく、本発明の趣旨を逸脱しない範囲で適宜変更が可能である。また、上記実施形態において説明した処理は、記載の順に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されるとしてもよい。

　既述のように、上記実施形態において説明したハードウェアエンティティ（本発明の装置）における処理機能をコンピュータによって実現する場合、ハードウェアエンティティが有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、上記ハードウェアエンティティにおける処理機能がコンピュータ上で実現される。

　この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。具体的には、例えば、磁気記録装置として、ハードディスク装置、フレキシブルディスク、磁気テープ等を、光ディスクとして、ＤＶＤ（Digital Versatile Disc）、ＤＶＤ－ＲＡＭ（Random Access Memory）、ＣＤ－ＲＯＭ（Compact Disc Read Only Memory）、ＣＤ－Ｒ（Recordable）／ＲＷ（ReWritable）等を、光磁気記録媒体として、ＭＯ（Magneto-Optical disc）等を、半導体メモリとしてＥＥＰ－ＲＯＭ（Electronically Erasable and Programmable-Read Only Memory）等を用いることができる。

　また、このプログラムの流通は、例えば、そのプログラムを記録したＤＶＤ、ＣＤ－ＲＯＭ等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。

　このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。そして、処理の実行時、このコンピュータは、自己の記憶装置に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。また、このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。また、サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるＡＳＰ（Application Service Provider）型のサービスによって、上述の処理を実行する構成としてもよい。なお、本形態におけるプログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるもの（コンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータ等）を含むものとする。

　また、この形態では、コンピュータ上で所定のプログラムを実行させることにより、ハードウェアエンティティを構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。

　上述の本発明の実施形態の記載は、例証と記載の目的で提示されたものである。網羅的であるという意思はなく、開示された厳密な形式に発明を限定する意思もない。変形やバリエーションは上述の教示から可能である。実施形態は、本発明の原理の最も良い例証を提供するために、そして、この分野の当業者が、熟考された実際の使用に適するように本発明を色々な実施形態で、また、色々な変形を付加して利用できるようにするために、選ばれて表現されたものである。すべてのそのような変形やバリエーションは、公正に合法的に公平に与えられる幅にしたがって解釈された添付の請求項によって定められた本発明のスコープ内である。

Claims

　Pを素数、pを素数Pのビット数、Qを剰余環の位数、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のビット数、Qを剰余環の位数、Mを入力される数値のMSB位置のとりうる上限値、M’をシェアが許容するMSB位置の上限値、[R, R’]を分割した右シフトでカバーする右シフト量の範囲とし、
　数値aのシェア[[a]]^Pとシフト量ρのシェア<<ρ>>^Q（ただし、ρ≧0の場合は左シフト、ρ<0の場合は右シフトを表すものとする）から、数値aをρビットシフトして得られる数値sのシェア[[s]]^P（ただし、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を計算するシフト値計算部と、
　を含む秘密シフト装置。
　Pを素数、pを素数Pのビット数、Qを剰余環の位数、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とシフト量ρのシェア<<ρ>>^p（ただし、0≦ρ≦M, 数値aをMビット左シフトして得られる数値2^Maはオーバーフローしないものとする）から、数値aをρビット右シフトして得られる数値sのシェア[[s]]^P（ただし、s=a/2^ρ）を計算する秘密シフトシステムであって、
　シェア<<ρ>>^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を計算するシフト値計算手段と、
　を含む秘密シフトシステム。
　請求項２に記載の秘密シフト装置としてコンピュータを機能させるためのプログラム。