(57)【要約】【課題】暗号文の次数増加の問題を解決し、計算量やデータサイズの削減を図る。【解決手段】依頼装置は、秘密値ｓを保持し、１以上Ｎ（Ｎ：相異なる大きな素数ｐ，ｑの積）未満の整数の中から適当な値ｒ，ａ1，ａ2，ｄ1，ｄ2，ｄ3，ｋを選び、ａ0＝ｓ−ｋｐ−ａ1−ａ2  mod Ｎを計算し、Ｃ＝ｆs,r（Ｘ）＝Σi=02ａiｒiＸi（ｉ＝０，１，２）と、Ｒ（Ｘ）＝ｄ3ｒ3Ｘ3＋ｄ2ｒ2Ｘ2＋ｄ1ｒＸ−（ｄ1＋ｄ2＋ｄ3）を計算し、暗号文の組（Ｃ，Ｒ）を関数演算装置へ送信する。関数演算装置は、秘密の関数ｇ（Ｙ）を保持し、ｇ（Ｙ）に暗号文Ｃを代入して関数ｈ（Ｘ）を生成し、deg（Ｒ（Ｘ））＞deg（Ｓ（Ｘ））となるようなＳ（Ｘ）＝ｈ（Ｘ）modＲ（Ｘ）を計算し、復号装置へ送信する。復号装置は、Ｓ（ｒ-1） mod ｐ＝ｇ（ｓ）を計算し、復号文ｇ（ｓ）を得る。【選択図】図３
2005196055.tif 000002
【特許請求の範囲】
【請求項１】
秘密値ｓを保持し、
（１）１以上Ｎ（Ｎは、相異なる大きな素数ｐ，ｑの積）未満の整数の中から適当な値ｒ，ａ1，ａ2，ｋを選ぶ手順と、
（２）ａ0＝ｓ−ｋｐ−ａ1−ａ2  mod Ｎ  を計算する手順と、
（３）Ｃ＝ｆs,r（Ｘ）＝Σi=02ａiｒiＸiを計算する手順と、
（４）暗号文Ｃを出力する手順と、を有することを特徴とする依頼装置における暗号文生成方法。
【請求項２】
請求項１に記載の依頼装置における暗号文生成方法において、
（５）１以上Ｎ（Ｎは、相異なる大きな素数ｐ，ｑの積）未満の整数の中から適当な値ｄ1，ｄ2，ｄ3を選ぶ手順と、
（６）Ｒ（Ｘ）＝ｄ3ｒ3Ｘ3＋ｄ2ｒ2Ｘ2＋ｄ1ｒＸ−（ｄ1＋ｄ2＋ｄ3）を計算する手順と、
（７）暗号文の組（Ｃ，Ｒ）を出力する手順と、を有することを特徴とする依頼装置における暗号文生成方法。
【請求項３】
請求項２に記載の依頼装置における暗号文生成方法で生成された暗号文の組（Ｃ，Ｒ）を受け取り、
秘密の関数ｇ（Ｙ）を保持し、
（１）ｇ（Ｙ）に暗号文Ｃを代入して関数ｈ（Ｘ）を生成する手順と、
（２）deg（次数）（Ｒ（Ｘ））＞deg（Ｓ（Ｘ））となるような
Ｓ（Ｘ）＝ｈ（Ｘ）  mod  Ｒ（Ｘ）を計算する手順と、
（３）暗号文Ｃを処理したＳ（Ｘ）を出力する手順と、を有することを特徴とする関数演算装置における暗号文処理方法。
【請求項４】
請求項３に記載の関数演算装置における暗号文処理方法で生成された暗号文Ｃを処理したＳ（Ｘ）を受け取り、
依頼装置の暗号文生成方法における暗号文Ｃの生成に用いた、１以上Ｎ（Ｎは、相異なる大きな素数ｐ，ｑの積）未満の整数の中から選ばれた適当な値ｒとｐを保持し、
（１）Ｓ（ｒ-1） mod ｐ＝ｇ（ｓ）を計算する手順と、
（２）復号文ｇ（ｓ）を出力する手順と、を有することを特徴とする復号装置における復号方法。
【請求項５】
秘密値ｓを保持する手段と、
１以上Ｎ（Ｎは、相異なる大きな素数ｐ，ｑの積）未満の整数の中から適当な値ｒ，ａ1，ａ2，ｋを選ぶ手段と、
ａ0＝ｓ−ｋｐ−ａ1−ａ2  mod Ｎ を計算する手段と、
Ｃ＝ｆs,r（Ｘ）＝Σi=02ａiｒiＸiを計算する手段と、
暗号文Ｃを出力する手段と、を備えたことを特徴とする依頼装置。
【請求項６】
請求項５に記載の依頼装置において、
１以上Ｎ（Ｎは、相異なる大きな素数ｐ，ｑの積）未満の整数の中から適当な値ｄ1，ｄ2，ｄ3を選ぶ手段と、
Ｒ（Ｘ）＝ｄ3ｒ3Ｘ3＋ｄ2ｒ2Ｘ2＋ｄ1ｒＸ−（ｄ1＋ｄ2＋ｄ3）を計算する手段と、
暗号文の組（Ｃ，Ｒ）を出力する手段と、を備えたことを特徴とする依頼装置。
【請求項７】
請求項６に記載の依頼装置で生成された暗号文の組（Ｃ，Ｒ）を受け取る手段と、
秘密の関数ｇ（Ｙ）を保持する手段と、
ｇ（Ｙ）に暗号文Ｃを代入して関数ｈ（Ｘ）を生成する手段と、
deg（次数）（Ｒ（Ｘ））＞deg（Ｓ（Ｘ））となるような
Ｓ（Ｘ）＝ｈ（Ｘ）  mod  Ｒ（Ｘ）を計算する手段と、
暗号文Ｃを処理したＳ（Ｘ）を出力する手段と、を備えたことを特徴とする関数演算装置。
【請求項８】
請求項７に記載の関数演算装置で生成された暗号文Ｃを処理したＳ（Ｘ）を受け取る手段と、
依頼装置の暗号文生成方法における暗号文Ｃの生成に用いた、１以上Ｎ（Ｎは、相異なる大きな素数ｐ，ｑの積）未満の整数の中から選ばれた適当な値ｒとｐを保持する手段と、
Ｓ（ｒ-1） mod ｐ＝ｇ（ｓ）を 計算する手段と、
復号文ｇ（ｓ）を出力する手段と、を備えたことを特徴とする復号装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、情報セキュリティ技術の基盤となる暗号アルゴリズムに関し、特に従来の暗号アルゴリズムを拡張して効率良く計算ができる暗号処理方法、及び装置に関する。
【背景技術】
【０００２】
従来の暗号処理方法及び装置を図１、図２を参照して説明する。
外部機関装置４０では、素数生成部４１でｐ，ｑを相異なる大きな素数を生成し(s41)、合成数生成部４２でＮをＮ＝ｐｑなる合成数を計算する(s42)。合成数Ｎは合成数記憶部４３に記憶させると共に公開する。
暗号装置５０では、秘密鍵生成部５１で０以上Ｎ未満でかつＮと互いに素な整数から秘密鍵ｒを選択し(s51)、秘密鍵記憶部５２に記憶し(s52)、秘密鍵ｒを復号装置６０と共有する。
【０００３】
平文選択部５３で０以上Ｎ未満の整数である平文Ｍを選択し(s53)、秘密鍵ｒを用いて、以下の処理により暗号文を生成する。
１．パラメータ決定部５４でパラメータρを決定する(s54)。
２．整数選択部５５で０以上Ｎ未満の整数の中からρ個の適当な値ａi（ｉ＝１，・・・，ρ）を選ぶ(s55)。
【数１】
2005196055.tif 000003
ここで、多項式ｆM、r（Ｘ）の各項の係数ａiｒi（ｉ＝０，・・・，ρ）はＮで割った余（０≦ａi ｒi＜Ｎ）に変換されるものとする。
復号装置６０では、復号部６１で共有している秘密鍵ｒ（秘密鍵記憶部６２）を用いてｆM、r（ｒ-1） mod Ｎ＝Ｍを計算すれば良い。すると、任意の平文Ｍ1，Ｍ2から上記で述べた暗号処理を行い、得られた暗号文を
【数２】
2005196055.tif 000004
即ち、Ｍ1，Ｍ2を知ることなく、Ｍ1Ｍ2のみ得ることが可能となる。（非特許文献  １参照）
なお、上記方法は（特許文献１）にも記載されており、この文献では当該暗号処理方法を用いた様々な応用技術が例示されている。
【非特許文献１】千田，“素因数分解問題に基づいた環準同型暗号とその応用”，信学技報  Vol.103，No．315，pp.53−60，電子情報通信学会，2003年９月．
【特許文献１】特願２００３−３１９２５１
【発明の開示】
【発明が解決しようとする課題】
【０００４】
従来の非特許文献１や特許文献１、更に文献：(J. Domingo-Ferrer, “A provably secure additive and multiplicative privacy homomorphism, ”A. H. Chan and V.Gligor (Eds.), 5th Information Security Conference 2002 (ISC2002), LNCS 2433, Springer-Verlag, pp. 471-483, 2002.)による暗号処理方法では、暗号文同士を乗算した場合、一般に暗号文のサイズが増大する。
【数３】
2005196055.tif 000005
の次数をそれぞれｄ1，ｄ2とすれば、Ｃ1Ｃ2＝ｇ（Ｘ）はｄ1＋ｄ2次の多項式となる。同様にＣ1eはｅｄ1次の多項式となる。
本発明によって解決しようとする課題は、上記に挙げた暗号文の次数増加の問題を解決することであり、これにより計算量やデータサイズの削減が期待でき、更に例えば（特許文献１）で記載されている応用技術が効率良く処理できるようになることから、この問題を解決することには十分意味があると考えられる。
【課題を解決するための手段】
【０００５】
例えば（非特許文献１）による暗号処理方法において、本発明では、１以上Ｎ未満の適当な値ｄ1，ｄ2，ｄ3を選び、
Ｒ（Ｘ）＝ｄ3ｒ3Ｘ3＋ｄ2ｒ2Ｘ2＋ｄ1ｒＸ−（ｄ1＋ｄ2＋ｄ3）を公開し（ここで、多項式Ｒ（Ｘ）の各項の係数ｄ3ｒ3，ｄ2ｒ2，ｄ1ｒ，ｄ1＋ｄ2＋ｄ3はＮで割った余に変換されるものとする。）、暗号文Ｃ1，Ｃ2を乗算する際には、乗算結果Ｃ1Ｃ2をＲで割った余りに置き換えてやることで、上記問題を解決する。そしてこの操作により、暗号文を乗算の回数に関係なく２次以下の多項式に抑えることができる。また前記置き換え処理はＣ1Ｃ2を
【数４】
2005196055.tif 000006
となるようなＳ（Ｘ）に置き換えることを意味し、Ｍ1Ｍ2＝Ｃ1Ｃ2（ｒ-1） mod Ｎ、Ｒ（ｒ-1）＝０ mod Ｎであることを考えれば、明らかにＳ（ｒ-1）＝Ｍ1Ｍ2 mod Ｎが成り立つ。但し、Ｒから秘密鍵ｒを容易に求めることができれば、結果的に平文が容易に求まり当該暗号処理方法の安全性は損なわれてしまう。しかし、Ｒ，Ｎ，ρが与えられても、ｐ，ｑを知ること無く容易にｒを求められるかどうかは自明では無く、本発明では、このｒを求める問題の困難性を安全性の拠り所としている。また（非特許文献１）の暗号化処理を次のように変形してやれば、更に計算量、通信サイズの効率化、及び平文に対する秘匿性の向上が期待できる。
１．０以上Ｎ未満の整数の中から適当な値ａ1，ａ2，ｋを選ぶ。
２．ａ0＝Ｍ−ｐｋ−ａ1−ａ2  mod  Ｎを計算する。
３．Ｃ＝ｆM,r（Ｘ）＝ａ2ｒ2Ｘ2＋ａ1ｒＸ＋ａ0を計算し、暗号文とする。
復号処理は、秘密鍵ｒを用いてｆM,r（ｒ-1）mod ｐを計算すれば良い。
【発明の効果】
【０００６】
本発明によれば、（特許文献１）に記載された全実施例において、処理効率を上げることが期待でき、（特許文献１）の方法では、計算量、メモリサイズの観点から処理が困難とされていた、多項式表現された暗号文に対するべき乗剰余演算が、非常に効率よく計算できるようになる。
【発明を実施するための最良の形態】
【０００７】
ここでは本発明の実施の形態として、秘密の値を保有する依頼装置が、関数演算処理を行う関数演算装置に対して当該秘密の値を明かすことなく、関数処理結果を受け取る方法について詳細に説明する。
【実施例１】
【０００８】
実施例１を図３を参照して説明する。
今、依頼装置１０は０以上ｐ未満の秘密の整数値ｓを所有しているものとする。ここで相異なる大きな素数ｐ，ｑの積Ｎ＝ｐｑは、ＲＳＡ暗号で用いられているような、素因数分解困難な合成数とし、依頼装置１０及び関数演算装置２０は予めＮが与えられているものとする。
一方、関数演算装置２０は秘密の関数ｇ（Ｙ）＝Ｙe＋Ｙ＋ｃを所有し、ｇを依頼装置に対して知られたくないものとする。ここでｅ，ｃは適当な整数とする。また、ここではｇを具体的に与えたが、勿論この関数に限定されるわけではなく、任意の多項式関数としても良い。
【０００９】
次に具体的な処理について説明する。
依頼装置１０は、秘密値ｓに対して以下の処理を行う。なお、以降では、多項式の各項の係数は全てＮで割った余に変換されるものとする。
１．１以上Ｎ未満の整数の中から適当な値ｒ，ａ1，ａ2，ｄ1，ｄ2，ｄ3，ｋを選ぶ。
２．ａ0＝ｓ−ｋｐ−ａ1−ａ2   mod Ｎを計算する。
【数５】
2005196055.tif 000007
４．Ｒ（Ｘ）＝ｄ3ｒ3Ｘ3＋ｄ2ｒ2Ｘ2＋ｄ1ｒＸ−（ｄ1＋ｄ2＋ｄ3）を計算する。
５．（Ｃ，Ｒ）を暗号文の組とし、これを関数演算装置に送信する。
ここで、明らかにｆs,r（ｒ-1） mod  ｐ＝ｓ、Ｒ（ｒ-1）＝０ mod Ｎが成り立つ。
暗号文（Ｃ，Ｒ）を受け取った関数演算装置２０は、ｇ（Ｙ）に暗号文Ｃを代入し、Ｓ（Ｘ）＝ｇ（ｆs,r（Ｘ））modＲ（Ｘ）を計算し、これを復号装置３０に返送する。そして復号装置３０は、Ｓ（ｒ-1） mod  pを計算することで、Ｓ（ｒ-1） mod  p＝ｇ（ｓ）を得ることができる。
【００１０】
結局、本発明の主要部分は、ｈ（Ｘ）＝ｇ（ｆs,r（Ｘ））をＲ（Ｘ）で割った余りに変換する処理、即ちｈ（Ｘ）＝Ｑ（Ｘ）Ｒ（Ｘ）＋Ｓ（Ｘ）とした時、ｈ（Ｘ）をＳ（Ｘ）に変換する処理はｈ（ｒ-1）＝Ｓ（ｒ-1）＝ｓ  modｐとなり、復号結果を変えることは無いという性質を利用していることであり、多項式ｇ（Ｘ）の次数ｅが大きい程処理効率が悪化する（非特許文献１）の問題点を解決する技術となる。
以降Ｓ（Ｘ）＝ｇ（ｆs,r（Ｘ）） mod Ｒ（Ｘ）の具体的な計算方法として２進計算
法を用いた場合について説明する。
【数６】
2005196055.tif 000008
２．ｚa＝ｚ2 mod Ｒ（Ｘ）を計算し、ｚ←ｚaとする。
３．ｂiが１であれば  ｚb＝ｙｚ  mod Ｒ（Ｘ）を計算し、ｚ←ｚbとする。
４．ｉ＝０であれば、ｚ←ｚ＋ｙ＋ｃ  modＲ（Ｘ）を計算し、Ｓ（Ｘ）＝ｚ＝（ｆs,r（Ｘ））e＋ｆs,r（Ｘ）＋ｃとして終了する。そうでなければ、ｉ←ｉ−１として２．に戻る。
【００１１】
これにより、（非特許文献１）では、（ｆs,r（Ｘ））eは最大で２ｅ次の多項式となるのに対し、上記処理では高々２次とできる。すると例えば、暗号、署名などで良く処理されるような、非常に大きなべきに対するべき乗剰余演算は（非特許文献１）では計算量、メモリサイズ的に不可能といえるが、上記処理では高々２次多項式同士の乗算をlog Ｎ回程度行えば済むため、十分実用範囲での処理といえる。また復号処理は、Ｓ（ｒ-1）を計算すれば、Ｓ（ｒ-1）＝ｓe＋ｓ＋ｃ  mod pを得ることができる。これにより、ｓを関数演算装置に知られること無く、かつ関数ｇを知ること無く、ｇ（ｓ）を得ることができる。
【実施例２】
【００１２】
次に実施例１の拡張として、有理数を扱う場合の例を図４を参照して説明する。
今、依頼装置１０は０以上ｐ未満の秘密の有理数値ｓ／ｔ，ｕ／ｖを所有しているものとする。ここで相異なる大きな素数ｐ，ｑの積Ｎ＝ｐｑは、ＲＳＡ暗号で用いられているような、素因数分解困難な合成数とし、依頼装置１０及び関数演算装置２０は予めＮが与えられているものとする。一方、関数演算装置２０は秘密の関数ｇ（Ｙ，Ｚ）＝Ｙ2＋ＹＺ＋１を所有し、ｇを依頼装置１０に対して知られたくないものとする。また、ここではｇを具体的に与えたが、勿論この関数に限定されるわけではなく、任意の多項式関数として良い。
【００１３】
次に具体的な処理について説明する。
依頼装置１０は、秘密値ｓ／ｔ，ｕ／ｖに対して実施例１と同様の暗号化処理を行う。そして、
【数７】
2005196055.tif 000009
Ｒ（Ｘ）＝ｄ3ｒ3Ｘ3＋ｄ2ｒ2Ｘ2＋ｄ1ｒＸ−（ｄ1＋ｄ2＋ｄ3）
を得る。ここで
ａs,0＝ｓ−ｋsｐ−ａs,1−ａs,2   mod Ｎ，
ａt,0＝ｔ−ｋtｐ−ａt,1−ａt,2   mod Ｎ，
ａu,0＝ｕ−ｋuｐ−ａu,1−ａu,2   mod Ｎ，
ａv,0＝ｖ−ｋvｐ−ａv,1−ａv,2   mod Ｎ
とし、ａs,i，ａt,i，ａu,i，ａv,i（ｉ＝１，２），ｒ，ｄj（ｊ＝１，２，３），ｋs，ｋt，ｋu，ｋvは１以上Ｎ未満の整数の中から適当に選んだ値とする。なお、実施例１と同様に、多項式の各項の係数は全てＮで割った余に変換されるものとする。
暗号文（Ｃs，Ｃt，Ｃu，Ｃv，Ｒ）を受け取った関数演算装置２０は
【数８】
2005196055.tif 000010
を計算し、これを復号装置３０に返送する。
【００１４】
ここで、上記Ｓ（Ｘ）の具体的な計算方法を示す。
まず、Ｙ2＝（Ｃs／Ｃt）2の計算は、Ｃs2，Ｃt2各々を計算すれば良く、この計算結果をそれぞれＣ1，Ｃ2とする。次に、ＹＺ＝（Ｃs／Ｃt）×（Ｃu／Ｃv）の計算はＣsＣu，ＣtＣvを各々計算すれば良く、この計算結果をそれぞれＣ3，Ｃ4とする。すると、
【数９】
2005196055.tif 000011
であるから、通分することで、分子部分Ｓ1（Ｘ）＝Ｃ1Ｃ4＋Ｃ2Ｃ3＋Ｃ2Ｃ4 mod Ｒ（Ｘ）及び分母部分Ｓ2（Ｘ）＝Ｃ2Ｃ4 modＲ（Ｘ）を得ることができる。復号装置３０は、このＳ1（Ｘ），Ｓ2（Ｘ）を受け取り、それぞれＳ1（ｒ-1），Ｓ2（ｒ-1）を計算すれば、
Ｓ1（ｒ-1）＝ｓ2ｔｖ＋ｔ2ｓｕ＋ｔ3ｖ  mod ｐ，
Ｓ2（ｒ-1）＝ｔ3ｖ  mod ｐ
が成り立ち、
【数１０】
2005196055.tif 000012
を得ることができる。これにより、ｓ，ｔ，ｕ，ｖを関数演算装置に知られること無く、且つ関数ｇを知ること無く、ｇ（（ｓ／ｔ），（ｕ／ｖ））を得ることができる。
【００１５】
以上、発明の実施の形態例について述べたが、これは例えば、ｇとして暗号文を復号する関数とすれば、ｇには秘密鍵が含まれているため依頼装置にそれを明かしたくなく、一方で依頼装置は復号結果を関数演算装置に知られたくない場合に有効である。また、本発明の実施例は、基本的に（特許文献１）で記載された実施例と同様であり、当該文献の実施例に対して処理効率を上げる技術を提供している。
【図面の簡単な説明】
【００１６】
【図１】従来のセキュリティ装置の処理とセキュリティ装置における外部機関装置及び復号装置を示す図。
【図２】従来のセキュリティ装置における暗号装置を示す図。
【図３】本発明の暗号処理装置（実施例１）を示す図。
【図４】本発明の暗号処理装置（実施例２）を示す図。
【符号の説明】
【００１７】
１０    依頼装置
２０    関数演算装置
３０    復号装置
【図１】
2005196055.tif 000013
【図２】
2005196055.tif 000014
【図３】
2005196055.tif 000015
【図４】
2005196055.tif 000016