(57)【要約】【課題】【解決手段】例示的一実施形態において、暗号化機能を有する暗号化方式に従って暗号文Ｃとして暗号化されることになる情報Ｂを受信すること、および、Ｃを取得するために暗号化機能に従ってＢを暗号化することを含む、動作を実行するために、機械によって実行可能な命令のプログラムを有形に具体化する、コンピュータ読み取り可能記憶媒体であって、この方式は少なくとも１つの公開鍵Ａを使用し、Ｂ、Ｃ、およびＡは行列であり、暗号化機能は入力としてＡおよびＢを受信し、Ｃを【数１】2013524277.tif 000194として出力し、この式でＳはランダム行列であり、Ｘはエラー行列であり、ｐは整数であり、ｑは奇数の素数である。他の例示的実施形態では、暗号化方式は、入力として少なくとも１つの秘密鍵Ｔ（行列）およびＣを受信し、Ｂ＝Ｔ−１・（ＴＣＴｔ  ｍｏｄ  ｑ）・（Ｔｔ）−１  ｍｏｄ  ｐとしてＢを出力する、復号機能を含む。【選択図】  図８
2013524277.tif 000002
【特許請求の範囲】
【請求項１】
動作を実行するために機械によって実行可能な命令のプログラムを有形に具体化するコンピュータ読み取り可能記憶媒体であって、前記動作は、
暗号化機能を備える暗号化方式に従って暗号文Ｃとして暗号化されることになる情報Ｂを受信すること、および、
前記暗号文Ｃを取得するために前記暗号化方式の前記暗号化機能に従って前記情報Ｂを暗号化すること
を含み、
前記暗号化方式は少なくとも１つの秘密鍵Ｔに対応する少なくとも１つの公開鍵Ａを使用し、前記情報Ｂ、前記暗号文Ｃ、前記少なくとも１つの公開鍵Ａ、および前記少なくとも１つの秘密鍵Ｔは行列であり、
前記暗号化機能は、入力として前記少なくとも１つの公開鍵Ａおよび前記情報Ｂを受信し、前記暗号文Ｃを
【数１】
2013524277.tif 000158
として出力し、この式でＳはランダム行列であり、Ｘはエラー行列であり、ｐは整数であり、ｑは奇数の素数である、
コンピュータ読み取り可能記憶媒体。
【請求項２】
【数２】
2013524277.tif 000159
【数３】
2013524277.tif 000160
【数４】
2013524277.tif 000161
【数５】
2013524277.tif 000162
および
【数６】
2013524277.tif 000163
であり、この式でｎは安全性パラメータを示し、ｍ，ｑ＝ｐｏｌｙ（ｎ）であり、この式で
【数７】
2013524277.tif 000164
はエラー分布であり、βは、β＝１／ｐｏｌｙ（ｎ）によって得られるガウスのエラー・パラメータである、請求項１に記載のコンピュータ読み取り可能記憶媒体。
【請求項３】
前記暗号化方式が準同形であり、双一次形式の計算をサポートする、請求項１に記載のコンピュータ読み取り可能記憶媒体。
【請求項４】
ｐ＝２であり、前記情報Ｂが２進値の行列を備える、請求項１に記載のコンピュータ読み取り可能記憶媒体。
【請求項５】
ｃ＝ｃ（ｎ）＞０、ｑ＞２２０  ｐ２（ｃ＋４）３ｎ３ｃ＋４ｌｏｇ５ｎ、
【数８】
2013524277.tif 000165
および
【数９】
2013524277.tif 000166
である、請求項１に記載のコンピュータ読み取り可能記憶媒体。
【請求項６】
前記暗号化方式が、行列環
【数１０】
2013524277.tif 000167
上でいずれかの次数でｎｃの加法および１つの乗法をサポートする、請求項５に記載のコンピュータ読み取り可能記憶媒体。
【請求項７】
暗号化機能を備える暗号化方式に従って暗号文Ｃとして暗号化されることになる情報Ｂを記憶するように構成された、少なくとも１つの記憶媒体と、
前記暗号文Ｃを取得するために前記暗号化方式の前記暗号化機能に従って前記情報Ｂを暗号化するように構成された、少なくとも１つのプロセッサと、
備える、装置であって、
前記暗号化方式は少なくとも１つの秘密鍵Ｔに対応する少なくとも１つの公開鍵Ａを使用し、前記情報Ｂ、前記暗号文Ｃ、前記少なくとも１つの公開鍵Ａ、および前記少なくとも１つの秘密鍵Ｔは行列であり、
前記暗号化機能は入力として前記少なくとも１つの公開鍵Ａおよび前記情報Ｂを受信し、前記暗号文Ｃを
【数１１】
2013524277.tif 000168
として出力し、この式でＳはランダム行列であり、Ｘはエラー行列であり、ｐは整数であり、ｑは奇数の素数である、
装置。
【請求項８】
【数１２】
2013524277.tif 000169
および
【数１３】
2013524277.tif 000170
であり、この式でｎは安全性パラメータを示し、ｍ，ｑ＝ｐｏｌｙ（ｎ）であり、この式で
【数１４】
2013524277.tif 000171
はエラー分布であり、βは、β＝１／ｐｏｌｙ（ｎ）によって得られるガウスのエラー・パラメータである、請求項７に記載の装置。
【請求項９】
前記暗号化方式が準同形であり、双一次形式の計算をサポートする、請求項７に記載の装置。
【請求項１０】
ｐ＝２であり、前記情報Ｂが２進値の行列を備える、請求項７に記載の装置。
【請求項１１】
ｃ＝ｃ（ｎ）＞０、ｑ＞２２０  ｐ２（ｃ＋４）３ｎ３ｃ＋４ｌｏｇ５ｎ、
【数１５】
2013524277.tif 000172
および
【数１６】
2013524277.tif 000173
である、請求項７に記載の装置。
【請求項１２】
前記暗号化方式が、行列環
【数１７】
2013524277.tif 000174
上でいずれかの次数でｎｃの加法および１つの乗法をサポートする、請求項１１に記載の装置。
【請求項１３】
動作を実行するために機械によって実行可能な命令のプログラムを有形に具体化するコンピュータ読み取り可能記憶媒体であって、前記動作は、復号機能を備える暗号化方式に従って情報Ｂとして復号されることになる暗号文Ｃを受信すること、および、
前記情報Ｂを取得するために前記暗号化方式の前記復号機能に従って前記暗号文Ｃを復号すること
を含み、
前記暗号化方式は少なくとも１つの秘密鍵Ｔを使用し、前記情報Ｂ、前記暗号文Ｃ、および前記少なくとも１つの秘密鍵Ｔは行列であり、
前記復号機能は入力として前記少なくとも１つの秘密鍵Ｔおよび前記暗号文Ｃを受信し、Ｂ＝Ｔ−１・（ＴＣＴｔ  ｍｏｄ  ｑ）・（Ｔｔ）−１  ｍｏｄ  ｐに従って前記情報Ｂを出力し、この式でｐは整数であり、ｑは奇数の素数である、
コンピュータ読み取り可能記憶媒体。
【請求項１４】
【数１８】
2013524277.tif 000175
【数１９】
2013524277.tif 000176
および
【数２０】
2013524277.tif 000177
であり、この式でｎは安全性パラメータを示し、ｍ，ｑ＝ｐｏｌｙ（ｎ）であり、この式で
【数２１】
2013524277.tif 000178
はエラー分布であり、βは、β＝１／ｐｏｌｙ（ｎ）によって得られるガウスのエラー・パラメータである、請求項１３に記載のコンピュータ読み取り可能記憶媒体。
【請求項１５】
前記暗号化方式が準同形であり、双一次形式の計算をサポートする、請求項１３に記載のコンピュータ読み取り可能記憶媒体。
【請求項１６】
ｐ＝２であり、前記情報Ｂが２進値の行列を備える、請求項１３に記載のコンピュータ読み取り可能記憶媒体。
【請求項１７】
ｃ＝ｃ（ｎ）＞０、ｑ＞２２０  ｐ２（ｃ＋４）３ｎ３ｃ＋４ｌｏｇ５ｎ、
【数２２】
2013524277.tif 000179
および
【数２３】
2013524277.tif 000180
である、請求項１３に記載のコンピュータ読み取り可能記憶媒体。
【請求項１８】
前記暗号化方式が、行列環
【数２４】
2013524277.tif 000181
上でいずれかの次数でｎｃの加法および１つの乗法をサポートする、請求項１７に記載のコンピュータ読み取り可能記憶媒体。
【請求項１９】
復号機能を備える暗号化方式に従って情報Ｂとして復号されることになる暗号文Ｃを記憶するように構成された、少なくとも１つの記憶媒体と、
前記情報Ｂを取得するために前記暗号化方式の前記復号機能に従って前記暗号文Ｃを復号するように構成された、少なくとも１つのプロセッサと、
を備える、装置であって、
前記暗号化方式は少なくとも１つの秘密鍵Ｔを使用し、前記情報Ｂ、前記暗号文Ｃ、および前記少なくとも１つの秘密鍵Ｔは行列であり、
前記復号機能は入力として前記少なくとも１つの秘密鍵Ｔおよび前記暗号文Ｃを受信し、Ｂ＝Ｔ−１・（ＴＣＴｔ  ｍｏｄ  ｑ）・（Ｔｔ）−１  ｍｏｄ  ｐに従って前記情報Ｂを出力し、この式でｐは整数であり、ｑは奇数の素数である、
装置。
【請求項２０】
【数２５】
2013524277.tif 000182
および
【数２６】
2013524277.tif 000183
であり、この式でｎは安全性パラメータを示し、ｍ，ｑ＝ｐｏｌｙ（ｎ）であり、この式で
【数２７】
2013524277.tif 000184
はエラー分布であり、βは、β＝１／ｐｏｌｙ（ｎ）によって得られるガウスのエラー・パラメータである、請求項１９に記載の装置。
【請求項２１】
前記暗号化方式が準同形であり、双一次形式の計算をサポートする、請求項１９に記載の装置。
【請求項２２】
ｐ＝２であり、前記情報Ｂが２進値の行列を備える、請求項１９に記載の装置。
【請求項２３】
ｃ＝ｃ（ｎ）＞０、ｑ＞２２０  ｐ２（ｃ＋４）３ｎ３ｃ＋４ｌｏｇ５ｎ、
【数２８】
2013524277.tif 000185
および
【数２９】
2013524277.tif 000186
である、請求項１９に記載の装置。
【請求項２４】
前記暗号化方式が、行列環
【数３０】
2013524277.tif 000187
上でいずれかの次数でｎｃの加法および１つの乗法をサポートする、請求項２３に記載の装置。
【請求項２５】
動作を実行するために機械によって実行可能な命令のプログラムを有形に具体化するコンピュータ読み取り可能記憶媒体であって、前記動作は、
暗号化機能および復号機能を備える暗号化方式に従って暗号文Ｃとして暗号化されることになる情報Ｂを受信すること、および、
前記暗号文Ｃを取得するために前記暗号化方式の前記暗号化機能に従って前記情報Ｂを暗号化すること、
を含み、
前記暗号化方式は少なくとも１つの公開鍵Ａおよび前記少なくとも１つの秘密鍵Ａに対応する少なくとも１つの秘密鍵Ｔを使用し、前記情報Ｂ、前記暗号文Ｃ、前記少なくとも１つの公開鍵Ａ、および前記少なくとも１つの秘密鍵Ｔは行列であり、
【数３１】
2013524277.tif 000188
および
【数３２】
2013524277.tif 000189
であり、この式でｎは安全性パラメータを示し、ｍ，ｑ＝ｐｏｌｙ（ｎ）であり、ｑは奇数の素数であり、ｐは整数であり、ｑ＞ｐであり、
前記暗号化機能は入力としてＡおよびＢを受信し、前記暗号文Ｃを
【数３３】
2013524277.tif 000190
として出力し、この式でＳはランダム行列であって、
【数３４】
2013524277.tif 000191
であり、Ｘはエラー行列であって、
【数３５】
2013524277.tif 000192
であり、この式で
【数３６】
2013524277.tif 000193
はエラー分布であり、βは、β＝１／ｐｏｌｙ（ｎ）によって得られるガウスのエラー・パラメータであり、
前記復号機能は入力としてＴおよびＣを受信し、Ｂ＝Ｔ−１・（ＴＣＴｔ  ｍｏｄ  ｑ）・（Ｔｔ）−１  ｍｏｄ  ｐに従って前記情報Ｂを出力し、前記暗号化方式は準同形であり、双一次形式の計算をサポートする、
コンピュータ読み取り可能記憶媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明の例示的実施形態は、一般に暗号化および復号化のアルゴリズムに関し、より具体的には、双一次形式（bilinear
form）のための準同形（homomorphic）暗号化方式に関する。
【背景技術】
【０００２】
暗号化データに関する操作をサポートする暗号化方式（たとえば準同形暗号化）は、セキュアな計算にとって非常に有用である。
【０００３】
準同形暗号化方式とは、２つまたはそれ以上の暗号文に関して実行される１つまたは複数の演算（たとえば加法、乗法）が、復号された平文（すなわち暗号文の復号）に変換するものである。たとえば暗号化方式は、暗号文（Ｃ１＋Ｃ２）の合計の復号が、対応する平文（Ｂ１＋Ｂ２）（おそらくはある値を法とする）の合計をもたらす、すなわち
【数１】
2013524277.tif 000003
である場合、加法的に準同形であるものと言える。多くの公開鍵暗号方式は、暗号化データの加法または乗法のいずれかをサポートするが、両方を同時に取得することはより困難であるように思われる。
【０００４】
暗号化データに関する任意関数の計算は、たとえばＹａｏの「ｇａｒｂｌｅｄ  ｃｉｒｃｕｉｔ」技法［１６、１２］を使用して実施可能であるが、暗号文のサイズおよび復号の複雑さは、計算される回路内のゲート数と共に少なくとも線形に増加していくことが知られている。また、Ｓａｎｄｅｒ等［１５］は、任意回路の評価を可能にする技法について記述しているが、暗号文のサイズは回路深さと共に指数関数的に増加する。これらの方法はどちらも、「一般困難性仮定（general hardness assumptions）」（たとえば、２フロー紛失通信プロトコル（two-flow Oblivious-Transferprotocols）の存在など）のみを使用して実施可能である。
【０００５】
Ｂｏｎｅｈ、Ｇｏｈ、およびＮｉｓｓｉｍは、暗号文サイズを増加させることなしに、任意数の加法および１つの乗法を可能にする暗号化システムについて記述している［５］。この方式は、本明細書ではＢＧＮ暗号化システムと呼ばれる。ＢＧＮ暗号化システムの安全性は、双一次マップを許可するコンポジット・オーダー・グループにおけるサブグループ・メンバーシップ問題に基づいている。この暗号化システムは、２選言標準形（２ＤＮＦ）（disjunctive normal form）公式（またはより一般的には双一次形）を評価するための効率的なプロトコルを即時に示唆する。Ｂｏｎｅｈ等は、個人情報検索方式（ＰＩＲ）の効率性向上および投票プロトコルのための、ＢＧＮ暗号化システムの適用例について記述している。
【０００６】
さらに最近では、Ａｇｕｉｌａｒ  Ｍｅｌｃｈｏｒ、Ｇａｂｏｒｉｔ、およびＨｅｒｒａｎｚは、［２］において、いくつかの加法的準同形暗号化を加法および乗法の両方が可能な暗号化システムに変換するための「テンプレート」について記述している。彼らは、このテンプレートを使用してＢＧＮ暗号化システムとＫａｗａｃｈｉ等の暗号化システム［１１］とを組み合わせ、格子におけるサブグループ・メンバーシップ問題および固有最短ベクトル問題の両方の困難性に基づいて、２つの乗法および任意加法をサポートする、暗号化システムを取得する方法を示している。彼らは、無制限の加法深さを取得するために、Ａｇｕｉｌａｒ  Ｍｅｌｃｈｏｒ等の暗号化システム［１］と共にこのテンプレートを使用する方法を示しており、ここで、暗号文のサイズは加法深さと共に指数関数的に増加するが、加法はサイズの増加無しにサポートされる。（この最後の実現の安全性は、「差分ナップザック・ベクトル問題」と呼ばれる比較的自然に会得される困難性の仮定に基づいている。）
【０００７】
格子または一次符号から加法的準同形暗号化方式を構築できることが知られている。暗号文は、暗号文がまとめて操作（たとえば加法、乗法）されるにつれて増加する「エラー」を暗黙的に含む。したがって、結果として生じる暗号文は（たとえば個別に復号された場合）元の暗号文と同じ分布を有さず、いくつかの地点で、不正な復号を生じさせるのに十分な大きさのエラーとなる可能性がある。そのため、こうしたケースでは、準同形は時に「擬似準同形」または「有界準同形」と呼ばれる。
【０００８】
ごく最近では、Ｇｅｎｔｒｙが、イデアル格子において短ベクトルを見つける困難性に基づく安全性［８］を用いて、暗号文サイズを増加させることなく多項式的（polynomially）に多くの加法および乗法をサポートする、完全準同形暗号化システム［９］について記述している。
【先行技術文献】
【非特許文献】
【０００９】
【非特許文献１】C. Aguilar Melchor, G. Castagnos, andP.Gaborit. Lattice-based homomorphic encryption of vector spaces. In IEEEInternational Symposium on InformationTheory, ISIT’ 2008, pages 1858-1862,2008.
【非特許文献２】C. Aguilar Melchor, P. Gaborit, andH.Javier. Additive Homomorphic Encryption with t-OperandMultiplications.Technical Report 2008/378, IACR ePrint archive,2008.http://eprint.iacr.org/2008/378/.
【非特許文献３】M. Ajtai. Generating hard instances oftheshort basis problem. In ICALP,pages 1{9, 1999.
【非特許文献４】J. Alwen and C. Peikert. Generatingshorterbases for hard random lattices. In STACS,pages 75-86, 2009.
【非特許文献５】D. Boneh, E.-J. Goh, and K.Nissim.Evaluating 2-DNF formulas on ciphertexts. Pages 325-341, 2005.
【非特許文献６】Y. Dodis, S. Goldwasser, Y. T. Kalai,C.Peikert, and V. Vaikuntanathan. Public-key encryption schemes withauxiliaryinputs. In TCC, pages 361-381,2010.
【非特許文献７】W. Feller. An Introduction to ProbabilityTheory and Its Applications, Volume 1.Wiley, 1968.
【非特許文献８】C. Gentry. A fully homomorphic encryptionscheme. PhD thesis, Stanford University, 2009.http://crypto.stanford.edu/craig.
【非特許文献９】C. Gentry. Fully homomorphic encryptionusingideal lattices. In STOC ’09,pages 169-178. ACM, 2009.
【非特許文献１０】C. Gentry, C. Peikert, and V.Vaikuntanathan.Trapdoors for hard lattices and new cryptographic constructions.In STOC, pages 197-206, 2008.
【非特許文献１１】A. Kawachi, K. Tanaka, and K.Xagawa.Multi-bit Cryptosystems Based on Lattice Problems. In Public Key Cryptography(PKC ’07), volume 4450 of Lecture Notes in Computer Science,pages 315-329.Springer, 2007.
【非特許文献１２】Y. Lindell and B. Pinkas. A proof ofsecurityof yao’ sprotocol for two-party computation. J.Cryptology, 22(2), 2009.
【非特許文献１３】C. Peikert. Public-key cryptosystems fromtheworst-case shortest vector problem. In STOC’09, pages 333-342. ACM, 2009.
【非特許文献１４】O. Regev. On lattices, learning witherrors,random linear codes, and cryptography. J.ACM, 56(6), 2009. Preliminiaryversion in STOC ’ 05.
【非特許文献１５】T. Sander, A. Young, and M.Yung.Non-interactive CryptoComputing for NC1. In 40th AnnualSymposium on Foundations of Computer Science,pages 554-567. IEEE, 1999.
【非特許文献１６】A. C. Yao. Protocols for securecomputations(extended abstract). In 23rd AnnualSymposium on Foundations ofComputer Science - FOCS ’82, pages 160-164.IEEE, 1982.
【発明の概要】
【発明が解決しようとする課題】
【００１０】
この発明の目的は、暗号化および復号化のアルゴリズムに関し、より具体的には、双一次形式（bilinear
form）のための準同形（homomorphic）暗号化方式を提供することにある。
【課題を解決するための手段】
【００１１】
本発明の一例示的実施形態では、コンピュータ読み取り可能記憶媒体が、動作を実行するために機械によって実行可能な命令のプログラムを有形に具体化し、動作は、暗号化機能を備える暗号化方式に従って暗号文Ｃとして暗号化されることになる情報Ｂを受信すること、および、暗号文Ｃを取得するために暗号化方式の暗号化機能に従って情報Ｂを暗号化することを含み、暗号化方式は少なくとも１つの秘密鍵Ｔに対応する少なくとも１つの公開鍵Ａを使用し、情報Ｂ、暗号文Ｃ、少なくとも１つの公開鍵Ａ、および少なくとも１つの秘密鍵Ｔは行列であり、暗号化機能は入力として少なくとも１つの公開鍵Ａおよび情報Ｂを受信し、暗号文Ｃを
【数２】
2013524277.tif 000004
として出力し、この式でＳはランダム行列であり、Ｘはエラー行列であり、ｐは整数であり、ｑは奇数の素数である。
【００１２】
本発明の他の例示的実施形態では、装置が、暗号化機能を備える暗号化方式に従って暗号文Ｃとして暗号化されることになる情報Ｂを記憶するように構成された、少なくとも１つの記憶媒体と、暗号文Ｃを取得するために暗号化方式の暗号化機能に従って情報Ｂを暗号化するように構成された、少なくとも１つのプロセッサとを備え、暗号化方式は少なくとも１つの秘密鍵Ｔに対応する少なくとも１つの公開鍵Ａを使用し、情報Ｂ、暗号文Ｃ、少なくとも１つの公開鍵Ａ、および少なくとも１つの秘密鍵Ｔは行列であり、暗号化機能は入力として少なくとも１つの公開鍵Ａおよび情報Ｂを受信し、暗号文Ｃを
【数３】
2013524277.tif 000005
として出力し、この式でＳはランダム行列であり、Ｘはエラー行列であり、ｐは整数であり、ｑは奇数の素数である。
【００１３】
本発明の他の例示的実施形態では、コンピュータ読み取り可能記憶媒体が、動作を実行するために機械によって実行可能な命令のプログラムを有形に具体化し、動作は、復号機能を備える暗号化方式に従って情報Ｂとして復号されることになる暗号文Ｃを受信すること、および、情報Ｂを取得するために暗号化方式の復号機能に従って暗号文Ｃを復号することを含み、暗号化方式は少なくとも１つの秘密鍵Ｔを使用し、情報Ｂ、暗号文Ｃ、および少なくとも１つの秘密鍵Ｔは行列であり、復号機能は入力として少なくとも１つの秘密鍵Ｔおよび暗号文Ｃを受信し、Ｂ＝Ｔ−１・（ＴＣＴｔ  ｍｏｄ  ｑ）・（Ｔｔ）−１  ｍｏｄ  ｐに従って情報Ｂを出力し、この式でｐは整数であり、ｑは奇数の素数である。
【００１４】
本発明の他の例示的実施形態では、装置が、復号機能を備える暗号化方式に従って情報Ｂとして復号されることになる暗号文Ｃを記憶するように構成された、少なくとも１つの記憶媒体と、情報Ｂを取得するために暗号化方式の復号機能に従って暗号文Ｃを復号するように構成された、少なくとも１つのプロセッサとを備え、暗号化方式は少なくとも１つの秘密鍵Ｔを使用し、情報Ｂ、暗号文Ｃ、および少なくとも１つの秘密鍵Ｔは行列であり、復号機能は入力として少なくとも１つの秘密鍵Ｔおよび暗号文Ｃを受信し、Ｂ＝Ｔ−１・（ＴＣＴｔ  ｍｏｄ  ｑ）・（Ｔｔ）−１  ｍｏｄ  ｐに従って情報Ｂを出力し、この式でｐは整数であり、ｑは奇数の素数である。
【００１５】
本発明の他の例示的実施形態では、コンピュータ読み取り可能記憶媒体が、動作を実行するために機械によって実行可能な命令のプログラムを有形に具体化し、動作は、暗号化機能および復号機能を備える暗号化方式に従って暗号文Ｃとして暗号化されることになる情報Ｂを受信すること、および、暗号文Ｃを取得するために暗号化方式の暗号化機能に従って情報Ｂを暗号化することを含み、暗号化方式は少なくとも１つの公開鍵Ａおよび少なくとも１つの秘密鍵Ａに対応する少なくとも１つの秘密鍵Ｔを使用し、情報Ｂ、暗号文Ｃ、少なくとも１つの公開鍵Ａ、および少なくとも１つの秘密鍵Ｔは行列であり、
【数４】
2013524277.tif 000006
【数５】
2013524277.tif 000007
【数６】
2013524277.tif 000008
および
【数７】
2013524277.tif 000009
であり、この式でｎは安全性パラメータを示し、ｍ，ｑ＝ｐｏｌｙ（ｎ）であり、ｑは奇数の素数であり、ｐは整数であり、ｑ＞ｐであり、暗号化機能は入力としてＡおよびＢを受信し、暗号文Ｃを
【数８】
2013524277.tif 000010
として出力し、この式でＳはランダム行列であって、
【数９】
2013524277.tif 000011
であり、Ｘはエラー行列であって、
【数１０】
2013524277.tif 000012
であり、この式で
【数１１】
2013524277.tif 000013
はエラー分布であり、βは、β＝１／ｐｏｌｙ（ｎ）によって得られるガウスのエラー・パラメータであり、復号機能は入力としてＴおよびＣを受信し、Ｂ＝Ｔ−１・（ＴＣＴｔ  ｍｏｄ  ｑ）・（Ｔｔ）−１  ｍｏｄ  ｐに従って情報Ｂを出力し、暗号化方式は準同形であり、双一次形式の計算をサポートする。
【００１６】
本発明の実施形態の前述および他の態様は、添付の図面に関連して以下の発明を実施するための形態を読めば、より明らかとなろう。
【図面の簡単な説明】
【００１７】
【図１】本発明の例示的実施形態に従った、例示的暗号化動作／機能を示す図である。
【図２】本発明の例示的実施形態に従った、例示的復号動作／機能を示す図である。
【図３】本発明の例示的実施形態に従った、例示的鍵生成（ＫｅｙＧｅｎ）動作／機能を示す図である。
【図４】本発明の例示的実施形態に従った、例示的暗号文加法動作／機能を示す図である。
【図５】本発明の例示的実施形態に従った、例示的暗号文乗法動作／機能を示す図である。
【図６】本発明の例示的実施形態に従った、例示的「単純復号」動作／機能を示す図である。
【図７】本発明の様々な例示的実施形態が内部に実装可能なシステムを示すブロック図である。
【図８】本発明の例示的実施形態に従った、例示的方法の動作および例示的コンピュータ・プログラムの動作を示す、論理流れ図である。
【図９】本発明の例示的実施形態に従った、例示的方法の動作および例示的コンピュータ・プログラムの動作を示す、他の論理流れ図である。
【図１０】本発明の例示的実施形態に従った、例示的方法の動作および例示的コンピュータ・プログラムの動作を示す、他の論理流れ図である。
【図１１】本発明の例示的実施形態に従った、例示的方法の動作および例示的コンピュータ・プログラムの動作を示す、他の論理流れ図である。
【図１２】本発明の例示的実施形態に従った、例示的方法の動作および例示的コンピュータ・プログラムの動作を示す、他の論理流れ図である。
【発明を実施するための形態】
【００１８】
１  簡潔な概要
本発明の例示的実施形態は、Ｂｏｎｅｈ、Ｇｏｈ、およびＮｉｓｓｉｍ（ＢＧＮ）の暗号化システムと同様の、双一次形式の計算（たとえば、多項式的に多くの加法および１つの乗法）をサポートする、単純な公開鍵暗号化方式を構築する。安全性は、最悪のケースの格子問題と同様に困難であるものとして知られている、エラーでの習得（ＬＷＥ：learning with errors）問題の困難性に基づく。
【００１９】
例示的暗号システムのいくつかの特徴は、大規模メッセージ・スペースのサポート、公式プライバシを達成する容易な方法、ＢＧＮよりも良好なメッセージ対暗号文拡張比、および、２つの暗号化多項式を乗算する容易な方法を含む。またこの方式は、（より高いメッセージ対暗号文拡張比を犠牲にした）識別ベースであり、耐リーク性とすることができる。
【００２０】
本明細書における「Ｚ」への任意またはすべての言及（たとえば、
【数１２】
2013524277.tif 000014
）
は、すべての整数セットに対応するものと理解されたい。さらに、本明細書における、秘密、秘密鍵、またはトラップドア（trapdoor）は、（たとえば、公開鍵−公開鍵暗号化方式の場合におけるような）秘密鍵、またはその逆に対応するものと理解されたい。
【００２１】
本明細書で使用される用語は、本発明の様々な例示的実施形態を説明するためのものであり、本発明を制限することは意図されていない。本明細書で使用される場合、単数形「ａ」、「ａｎ」、および「ｔｈｅ」は、特にコンテキストが明確に指示していない限り、複数形も同様に含むことが意図される。「含む」または「含んでいる」あるいはその両方の用語は、本明細書で使用される場合、述べられた特徴、整数、ステップ、動作、要素、または構成要素、あるいはそれらすべての存在を指定するが、１つまたは複数の他の特徴、整数、ステップ、動作、要素、構成要素、またはそれらのグループ、あるいはそれらすべての存在または追加を排除するものではないことを、さらに理解されよう。
【００２２】
１．１  はじめに
本書では、加法的に準同形であり、加えて、１つの乗法もサポートする、例示的暗号化方式について説明する。例示的方式は、Ｇｅｎｔｒｙ、Ｐｅｉｋｅｒｔ、およびＶａｉｋｕｎｔａｎａｔｈａｎによって提案されたトラップドア関数［１０］（以下、ＧＰＶトラップドア関数と呼ぶ）に基づく。ＧＰＶトラップドア関数では、「公開鍵」は行列
【数１３】
2013524277.tif 000015
（パラメータｑ＞ｐおよびｍ＞ｎの場合）であり、対応するトラップドアはＴＡ＝０（ｍｏｄ  ｑ）のような小さいエントリを伴う最大階数整数行列
【数１４】
2013524277.tif 000016
である。例示的暗号化システムにおける公開鍵および秘密鍵は、ＧＰＶトラップドア関数の場合とまったく同一である。正方行列
【数１５】
2013524277.tif 000017
は、
Ｃ＝ＡＳ＋ｐＸ＋Ｂ  ｍｏｄ  ｑを設定することによって暗号化され、上式で、Ｓはランダム「係数行列」
【数１６】
2013524277.tif 000018
であり、Ｘは、Ｘのエントリがｑよりも大幅に小さいようなエントリ
【数１７】
2013524277.tif 000019
を伴う「ノイズ行列」である。暗号文行列を付加することが可能であり、単一の行列乗法Ｃ’＝Ｃ１・Ｃｔ２  ｍｏｄ  ｑもサポートされる。（Ｃ’はＣの転置である。）復号するためには以下のように設定する。
Ｂ＝Ｔ−１・（ＴＣＴｔ  ｍｏｄ  ｑ）・（Ｔｔ）−１  ｍｏｄ  ｐ
【００２３】
例示的方式の安全性は、エラーでの習得（ＬＷＥ）の困難性と等価である。この問題は、良く知られた「ノイズでのパリティ習得（learning parity with noise）」に関し、格子ベースの暗号化の研究では標準的になっている。この問題は、最初にＲｅｇｅｖ［１４］によって提案され、Ｒｅｇｅｖ［１４］およびＰｅｉｋｅｒｔ［１３］によって、整数格子における様々な問題の最悪のインスタンスと同じように困難であることが示された。ＬＷＥ問題が関連付けられたエラー分布に関係することが、簡潔に示されている。
【００２４】
１．２  寄与
おそらく、例示的方式と以前の研究との主な相違点は、基礎となる困難性仮定であろう。特に例示的方式は、単なる加法的準同形を超えたＬＷＥに基づいて最初に報告された暗号化システムである。また、例示的方式は非常に効率的であり、
【数１８】
2013524277.tif 000020
の時点でｍ２要素の行列を暗号化することが可能であり、復号には同等の時間を要する。
【００２５】
例示的方式とＢＧＮ暗号化システムとの１つの重要な相違点は、ＢＧＮ暗号化システムが、（復号時には、グループ要素ｇｍのみを回復し、その後、メッセージｍを検索する必要があるため）小さいスペースからのメッセージのみを暗号化できるという点である。例示的方式では、ｑがｐよりも十分に大きい限り、任意のｐについてＺｐ上で行列を暗号化することができる。関係する利点は、（ＢＧＮ暗号化システムは、Ｏ（ｌｏｇ  ｎ）ビットの平文をＯ（ｎ）の暗号文ビットに拡張するが）例示的方式は、大きな係数ｐを選択することによって、Ｏ（１）の暗号文拡張を有することができるようになることである。
【００２６】
例示的方式においてメッセージ・スペースを画定する係数ｐは、暗号化側（encryptor）によって動的に選択可能であり、同じ公開鍵／秘密鍵のペアを使用して、多くの異なるフィールド（または環）を法とするメッセージを暗号化／復号することができることに留意されたい。例示的方式は、暗号文ブラインド化（blinding）（すなわち、所与の暗号文が同じものを暗号化するランダムな暗号文に変換される）、およびモジュール・ブラインド化のより強力な特性もサポートしており、行列
【数１９】
2013524277.tif 000021
を暗号化する暗号文が与えられ、ｐの何らかの除数ｐ’が与えられた場合、ｐ’を法とするＢを暗号化するランダム暗号文を生成することができる。たとえば、元の平文行列が（たとえば
【数２０】
2013524277.tif 000022
で）ｎビット数を有する場合、Ｂ内のエントリの最下位ビット以外のすべてを消去するように暗号文をブラインド化することができる。
【００２７】
（標準的な）ブラインド化特性およびメッセージ・スペースの選択の柔軟性の１つの結果が、例示的システムが公式プライベートなセキュア計算のための非常に単純な手順を提供することである。すなわち、公式自体に関する（所与の入力に適用した結果以外の）あらゆることを秘密鍵の保持者から隠しながら、同時に、暗号文上の２ＤＮＦ公式（または一般的な双一次形式）を計算することは非常に容易である。
【００２８】
最後に、例示的方式は、ＬＷＥベースの暗号化システムが備えている柔軟性の多くを引き継ぐ。特に、Ｇｅｎｔｒｙ等［１０］の構築を使用して識別ベースとすることが可能であり、Ｄｏｄｉｓ等［６］の最近の結果を使用して耐リーク性とすることが可能である。これらの適用例は両方共、［１０］からの「二重Ｒｅｇｅｖ暗号化システム」を例示的暗号化システムの特殊なケースとして説明できる観察から得られる。
【００２９】
適用例
明らかに、例示的方式は、Ｂｏｎｅｈ等［５］の論文で考察された投票およびＰＩＲへの適用において、暫定的な代替として使用可能である。加えて例示的方式は、行列をネイティブに暗号化することから、バッチングから恩恵を受けることのできる適用例にとって、または効率的な線形代数が重要な場合に、好適である。バッチングのいくつかの例は、（その係数が）多項式または（そのビット表現が平文行列のエントリ内に符号化されることになる）大きな整数を乗じる（たとえば乗算する必要のある）、適用例を含む。セクション５．３では、ｍ×ｍ行列の単一の乗法を使用して、２つの次数（ｍ−１）多項式（または２つのｍビット整数）を乗じることが可能なように、その結果がそれらの積以外のいずれの入力に関してもリークしないように、これらを行列内に符号化できる方法が説明されている。
【００３０】
１．３  例示的方式の概要
例示的方式の構築の裏にある主な考えについて、以下で概略を説明する。例示的方式は、安全性パラメータｎおよび多項式的に大きなｍの場合、均一にランダムな行列
【数２１】
2013524277.tif 000023
が与えられると、ベクトルＡｓ＋ｘは擬似ランダムであること（均一な
【数２２】
2013524277.tif 000024
および「小さいエラー・ベクトル」
【数２３】
2013524277.tif 000025
の場合）を示す、ＬＷＥ問題決定の困難性に基づいている。ＬＷＥ問題決定の困難性は、格子ベースの暗号化システムの研究において、現在も標準的な仮定であり、この問題は、Ｒｅｇｅｖ［１４］およびＰｅｉｋｅｒｔ［１３］によって、いくつかの標準的な格子問題を最悪のケースで解決することと同様に困難であるものと示された。
【００３１】
例示的方式の公開鍵はランダム行列
【数２４】
2013524277.tif 000026
であり、秘密鍵は、Ｔ・Ａ＝０（ｍｏｄ  ｑ）を満たす小さいエントリを伴う「トラップドア行列」Ｔである。暗号化方式に関するメッセージ・スペースは、（行列の加法および乗法の演算による）ｐを法とする整数のｍ×ｍ行列の環である。この方式は、ｐがＬＷＥ係数ｑよりも十分に小さい限り、任意の環Ｚｐ上で動作することができる。さらなる詳細についてはセクション３を参照されたい。
【００３２】
行列
【数２５】
2013524277.tif 000027
を暗号化する場合、暗号化側は、ＬＷＥエラー分布からランダム行列
【数２６】
2013524277.tif 000028
および「小さいエラー行列」Ｘを選択する。その後、暗号文Ｃは
Ｃ＝Ａ・Ｓ＋ｐ・Ｘ＋Ｂ
となる。
【００３３】
暗号文が（低階数行列）＋（ｐで割り切れる小さいノイズ）＋（メッセージ）の形であることに留意されたい。暗号文の復号は、以下のように、暗号文に左側のトラップドア行列Ｔ（低階数行列を除去する）を乗じること、その後、ノイズを消去するためにｐを法とするＴ−１を乗じることを含む。
Ｂ＝Ｔ−１・（Ｔ・Ｃ  ｍｏｄ  ｑ）ｍｏｄ  ｐ
【００３４】
これは、Ｔ、Ｘ、およびＢがすべて小さいことで働くため、Ｔ・（ｐＸ＋Ｂ）内のすべてのエントリがｑ未満であり、これは（ｍｏｄ  ｑのみではなく）整数上で（Ｔ・Ｃ  ｍｏｄ  ｑ）がＴ・（ｐＸ＋Ｂ）に等しく、したがって、Ｔ・Ｂ  ｍｏｄ  ｐに等しいことを意味する。
【００３５】
いくつかの行列の暗号化の合計は、（たとえば、
【数２７】
2013524277.tif 000029
内の）すべてのエントリが小さいままである限り、これらの行列の合計に復号されることが容易にわかる。２つの行列の乗法の暗号化を取得するためには、以下のように設定する。
【数２８】
2013524277.tif 000030
【００３６】
これは、追加の交差項Ｓ’Ａｔを除き、Ｂ１Ｂｔ２の暗号化と同様に見える（また実際にはエラー行列Ｘは小さい）。この積暗号文（product ciphertext）を復号するためには、第１にＭ＝Ｔ・Ｃ・Ｔｔ  ｍｏｄ  ｑを設定し、結果としてＡＳおよびＳ’Ａｔの両方の項が消去され、その後Ｂ＝Ｔ−１・Ｍ・（Ｔｔ）−１  ｍｏｄ  ｐとなる。
【００３７】
これで、この方式が単一の乗法（たとえば、これのみ）をサポートし、さらに、トラップドアＴではもはや消去できない、Ｓ・Ａ・Ｓ’の形の交差項が存在する理由が明らかとなる。
【００３８】
２  前置き
表記法
スカラーは小文字（ａ、ｂ、…）で、ベクトルは太字の小文字
【数２９】
2013524277.tif 000031
で、および行列は太字の大文字
【数３０】
2013524277.tif 000032
で示す。ベクトルｖのユークリッド・ノルムは
【数３１】
2013524277.tif 000033
で、ベクトルまたは行列内の最大エントリは、それぞれ
【数３２】
2013524277.tif 000034
で示す。整数αを区間（−ｑ／２、＋ｑ／２）にマッピングする場合の演算（α  ｍｏｄ  ｑ）について考えてみる。
【００３９】
２．１  エラーでの習得（ＬＷＥ）
ＬＷＥ問題は、Ｒｅｇｅｖ［１４］によって「ノイズでのパリティ習得」の一般化として紹介された。正の整数ｎおよびｑ≧２、ベクトル
【数３３】
2013524277.tif 000035
および
Ｚｑ上の確率分布Ｘの場合、Ａｓ，Ｘを、均一にランダムなベクトル
【数３４】
2013524277.tif 000036
およびノイズ項
【数３５】
2013524277.tif 000037
を選択すること、および
【数３６】
2013524277.tif 000038
を出力することによって取得される分布とする。
【００４０】
定義１（ＬＷＥ）  整数ｑ＝ｑ（ｎ）およびＺｑ全体にわたるエラー分布
【数３７】
2013524277.tif 000039
の場合、エラーでの習得問題ＬＷＥｎ，ｍ，ｑ，Ｘは、Ａｓ，Ｘからｍの独立サンプルが与えられた場合（何らかの
【数３８】
2013524277.tif 000040
の場合）、顕著な確率でｓを出力するように定義される。
【００４１】
ＬＷＥ問題の決定変形はｄｉｓｔＬＷＥｎ，ｍ，ｑ，Ｘとして示され、
Ａｓ，Ｘ（均一にランダムな
【数３９】
2013524277.tif 000041
の場合）に従って選択されたｍのサンプルを、
【数４０】
2013524277.tif 000042
全体にわたる均一な分布に従って選択されたｍのサンプルから、（無視できない利点で）区別することである。
【００４２】
暗号化適用例について、最も関心が高いのは決定問題ｄｉｓｔＬＷＥである。Ｒｅｆｅｖ［１４］は、素数係数ｑの場合、パラメータｍにおける最高ｑ・ｐｏｌｙ（ｎ）因数までの損失で、ｄｉｓｔＬＷＥを最悪のケースのＬＷＥまで低減できることを示した。
【００４３】
時には、コンパクトな行列表記法を使用して、ＬＷＥ問題ＬＷＥｎ，ｍ，ｑ，Ｘについて説明するために便利であることがわかる場合がある。
（Ａ，Ａｓ＋ｘ）が与えられ、この式で
【数４１】
2013524277.tif 000043
が均一にランダムなである場合、
【数４２】
2013524277.tif 000044
はＬＷＥ秘密であり、
【数４３】
2013524277.tif 000045
はｓを発見する。同様の行列表記法が、決定バージョンｄｉｓｔＬＷＥにも使用される。
【００４４】
ガウス・エラー分布
【数４４】
2013524277.tif 000046
最も関心が高いのは、ＬＷＥおよびｄｉｓｔＬＷＥ問題であり、ここではＺｑ全体にわたるエラー分布Ｘがガウス分布から導出される。任意のβ＞０について、実数全体にわたるガウス分布の密度関数は、Ｄβ（ｘ）＝１／β・ｅｘｐ（−π（ｘ／β）２）によって与えられる。整数ｑ≧２の場合、
【数４５】
2013524277.tif 000047
を、
【数４６】
2013524277.tif 000048
を引き出すこと、および
【数４７】
2013524277.tif 000049
を出力することによって取得された、Ｚｑ上の分布として定義する。ＬＷＥｎ，ｍ，ｑ，βを、
【数４８】
2013524277.tif 000050
の省略形として書き込む。
【００４５】
ここには、（エラー分布
【数４９】
2013524277.tif 000051
に合わせられた）ガウス分布に関するいくつかの基本的事実があり、たとえば［７］を参照されたい。（以下では、圧倒的な確率とは、ｎで無視できるほどのδの確率１−δを意味する。）
【００４６】
事実１  β＞０および
【数５０】
2013524277.tif 000052
とし、ベクトルｘを
【数５１】
2013524277.tif 000053
として選択されるものとする。また、
【数５２】
2013524277.tif 000054
を任意ベクトルとし、
【数５３】
2013524277.tif 000055
とする。次に、圧倒的な確率で、
【数５４】
2013524277.tif 000056
とする。
【００４７】
事実２  
【数５５】
2013524277.tif 000057
を任意とする。分布
【数５６】
2013524277.tif 000058
および
【数５７】
2013524277.tif 000059
の間の統計上の距離は、最大でも｜ｙ｜／（βｑ）である。
【００４８】
ＬＷＥｎ，ｍ，ｑ，βの困難性に関する証拠は、
【数５８】
2013524277.tif 000060
である場合、任意の所望のｍ＝ｐｏｌｙ（ｎ）に対してＬＷＥｎ，ｍ，ｑ，βを解決するために、最悪のケースでｎ次元格子上のある問題の近似から
【数５９】
2013524277.tif 000061
因数内までの量子減少を与えた、Ｒｅｇｅｖ［１４］の結果に従うものである。
【００４９】
本明細書で使用される場合、相対的な属性「小さい」は、
【数６０】
2013524277.tif 000062
から引き出される。一般に「小さい」値または整数とは、ｑ・βまでのサイズである。同様に「大きい」値または整数とは、ｑ・βよりはるかに大きいものである。
【００５０】
２．２  トラップドア・サンプリング
例示的暗号化方式の基本は、最初にＡｊｔａｉ［３］によって構築され、後にＡｌｗｅｎおよびＰｅｉｋｅｒｔ［４］によって改良された、トラップドア・サンプリング・アルゴリズムである。トラップドア・サンプリング手順は、（ほぼ）均一にランダムな行列
【数６１】
2013524277.tif 000063
を、
【数６２】
2013524277.tif 000064
と共に生成し、結果として、（ａ）Ｔ・Ａ＝０（ｍｏｄ  ｑ）であり、（ｂ）Ｔは可逆であり、（ｃ）Ｔのエントリは小さい（たとえば、サイズＯ（ｎ  ｌｏｇ  ｑ））となる。
【００５１】
トラップドアＴを使用して、Ａに関連してＬＷＥ問題を解決することが可能であり、すなわち、ｙ＝Ａｓ＋ｘが与えられ、ここでｘが任意の「十分に短い」ベクトルである場合、これを使用してｓを回復することができる。これは、以下のように計算することで実行され、
Ｔｙ＝Ｔ（Ａｓ＋ｘ）＝ＴＡｓ＋Ｔｘ＝Ｔｘ（ｍｏｄ  ｑ）
上式で最後の等式は、Ｔの行が格子
【数６３】
2013524277.tif 000065
に属する結果として生じる。次に、Ｔおよびｘの両方が小さいエントリを含むため、ベクトルＴｘの各エントリはｑよりも小さく、Ｔｘ  ｍｏｄ  ｑはＴｘ自体である。最後に、Ｔ−１（これはＴが基底であり、最大階数を有するため、明確である）を乗じることでｘが得られる。その後、ＬＷＥ秘密ｓは、ガウス消去法によって回復可能である。ＡｌｗｅｎおよびＰｅｉｋｅｒｔ［４］の結果を以下に示す。
【００５２】
補題１（｜３，４｜）  入力１ｎ、正整数ｑ≧２、およびｐｏｌｙ（ｎ）−有界正整数ｍ≧８ｎ  ｌｏｇ  ｑで、以下のような行列
【数６４】
2013524277.tif 000066
を出力する、効率的なアルゴリズムＴｒａｐＳａｍｐｌｅが存在する。
・Ａは、統計的に
【数６５】
2013524277.tif 000067
全体にわたって均一に近い。
・Ｔの行は、格子
【数６６】
2013524277.tif 000068
の基底を形成する。
・Ｔ（および｜Ｔ｜∞）のすべての行のユークリッド・ノルムはＯ（ｎ  ｌｏｇ  ｑ）によって境界が定められる。（ＡｌｗｅｎおよびＰｅｉｋｅｒｔ［４］はＯ（・）内に隠された定数がわずか２０であるものと主張している。）
【００５３】
Ｔの行が格子
【数６７】
2013524277.tif 000069
全体にわたるため、ｄｅｔ（Ｔ）＝ｑｎとなり、ｑと互いに素な任意のｐについて、Ｔはｐを法として可逆であることがわかることに留意されたい。
【００５４】
３  例示的暗号化方式
ｎが安全性パラメータを示すものとする。システムの他のパラメータは３つの数ｍ，ｐ，ｑ＝ｐｏｌｙ（ｎ）（ｑ＞ｐの奇数の素数）であり、ガウス・エラー・パラメータはβ＝１／ｐｏｌｙ（ｎ）である。これらのパラメータの具体的な例示的インスタンス化については、セクション３．２を参照されたい。これらのパラメータについて、メッセージ・スペースはｍ×ｍ行列のセット、すなわち
【数６８】
2013524277.tif 000070
のセットである。公開鍵は行列
【数６９】
2013524277.tif 000071
であり、秘密鍵は行列
【数７０】
2013524277.tif 000072
であり、暗号文は行列
【数７１】
2013524277.tif 000073
である。
【００５５】
例示的暗号化方式は、（たとえば少なくとも）以下の３つのアルゴリズムを含む。
ＫｅｙＧｅｎ（１ｎ）：行列
【数７２】
2013524277.tif 000074
を、トラップドア行列
【数７３】
2013524277.tif 000075
と共に取得するために、補題１のトラップドア・サンプリング・アルゴリズムＴｒａｐＳａｍｐｌｅ
【数７４】
2013524277.tif 000076
を実行する。公開鍵はＡであり、秘密鍵はＴである。
【数７５】
2013524277.tif 000077
：ランダム行列
【数７６】
2013524277.tif 000078
（たとえば、均一にランダムな行列）および「エラー行列」
【数７７】
2013524277.tif 000079
を選択する。暗号文
【数７８】
2013524277.tif 000080
を出力する。（ここで、ｐＸは、行列Ｘの各エントリにｐを乗じることを意味する。）
【数７９】
2013524277.tif 000081
を設定し、
【数８０】
2013524277.tif 000082
を出力する。
【００５６】
復号作業を理解するために、Ｔ・Ａ＝０（ｍｏｄ  ｑ）、さらにはＴＣＴｔ＝Ｔ（ｐＸ＋Ｂ）Ｔｔ（ｍｏｄ  ｑ）を想起してみる。加えて、Ｔ（ｐＸ＋Ｂ）Ｔｔのすべてのエントリがｑよりも小さい場合、整数上での等式、Ｅ＝（ＴＣＴｔ  ｍｏｄ  ｑ）＝Ｔ（ｐＸ＋Ｂ）Ｔｔ、したがって、Ｔ−１Ｅ（Ｔｔ）−１＝Ｂ（ｍｏｄ  ｐ）も有する。これは、十分に小さいパラメータβを設定している限り、正しい復号を有し、結果として、高い確率でＴ（ｐＸ＋Ｂ）Ｔｔのすべてのエントリがｑ／２よりも小さくなることを意味する。
【００５７】
注釈１  復号時のＴｔおよび（Ｔｔ）−１による右乗法はここでは冗長であり、代わりに
【数８１】
2013524277.tif 000083
のみを計算することが可能であることに留意されたい。右乗法は、以下で説明するように、積暗号文を復号する必要がある。ＢＧＮ暗号化システムとは対照的に、例示的方式では、「標準暗号文」および「積暗号文」が同じスペース内にあり、どちらを復号するにも同じ復号手順を使用することができる。
【００５８】
また、修正済みトラップドアＴ’＝（Ｔ−１  ｍｏｄ  ｐ）・Ｔ（整数上の積）を使用することによって、Ｔ−１および（Ｔｔ）−１による乗法の必要をなくすように最適化することができる。Ｔ’Ａ＝０（ｍｏｄ  ｑ）を明確に有し、Ｔ’のエントリは（（Ｔ−１  ｍｏｄ  ｐ）内のすべてのエントリが絶対値のポストｐ／２にあるため）Ｔのそれよりもそれほど大きくない。
【００５９】
３．１  準同形演算
加法
それぞれＢ１、Ｂ２に復号する２つのＣ１、Ｃ２が与えられた場合、いずれのエントリ内にも「オーバフロー」がない限り、行列Ｃ＝Ｃ１＋Ｃ２  ｍｏｄ  ｑはＢ１＋Ｂ２  ｍｏｄ  ｐに復号することが容易に理解されよう。具体的に言えば、Ｃ１＝ＡＳ１＋ｐＸ１＋Ｂ１およびＣ１＝ＡＳ２＋ｐＸ２＋Ｂ２を有する場合、
Ｃ＝Ｃ１＋Ｃ２＝Ａ（Ｓ１＋Ｓ２）＋ｐ（Ｘ１＋Ｘ２）＋（Ｂ１＋Ｂ２）
となり、これは、Ｔ（ｐ（Ｘ１＋Ｘ２）＋Ｂ１＋Ｂ２）Ｔｔ内のすべてのエントリがｑ／２よりも小さい限り、Ｂ１＋Ｂ２として復号されることになる。正確なパラメータの例については、セクション３．２を参照されたい。
【００６０】
乗法
それぞれＢ１、Ｂ２を暗号化する２つのＣ１、Ｃ２が与えられた場合、積暗号文をＣ＝Ｃ１・Ｃｔ２  ｍｏｄ  ｑとして計算する。Ｃ１＝ＡＳ１＋ｐＸ１＋Ｂ１およびＣ２＝ＡＳ２＋ｐＸ２＋Ｂ２を有する場合、
【数８２】
2013524277.tif 000084
となる。
【００６１】
したがって、積暗号文はＡＳ＋ｐＸ＋Ｂ＋Ｓ’Ａｔの形を有する。
【００６２】
前述のように、ＴＣＴｔ＝Ｔ（ｐＸ＋Ｂ）Ｔｔ（ｍｏｄ  ｑ）であることがわかり、Ｔ（ｐＸ＋Ｂ）Ｔｔのすべてのエントリがｑ／２よりも小さい場合、整数上でＥ＝（ＴＣＴｔ  ｍｏｄ  ｑ）＝Ｔ（ｐＸ＋Ｂ）Ｔｔを有し、したがって、Ｔ−１Ｅ（Ｔｔ）−１＝Ｂ（ｍｏｄ  ｐ）となる。以下で、これを動作可能にする例示的パラメータについて論じる。
【００６３】
３．２  パラメータの設定
定理２  安全性パラメータｎ、パラメータｐ、および任意のｃ＝ｃ（ｎ）＞０を固定する。ｑ、ｍ、βを、以下のように設定する。
【数８３】
2013524277.tif 000085
【００６４】
次に、パラメータｐ、ｎ、ｍ、ｑ、βを伴う上記の例示的暗号化方式は、行列環
【数８４】
2013524277.tif 000086
上でのｎｃの加法および１つの乗法（任意の次数）をサポートする。
【００６５】
注釈３  定理２では、非定常ｃに関するｎｃの加法が可能であることに留意されたい。これが必要な可能性のある理由は、暗号文と大きい係数との線形組み合わせを採用するためである。具体的に言えば、暗号文行列Ｃ１、Ｃ２、…を有する場合、
【数８５】
2013524277.tif 000087
である限り、
【数８６】
2013524277.tif 000088
を準同形的に計算することができる。
【００６６】
４  拡張および適用
４．１  基礎となる環の動的選択
パラメータが固定されると、平文に関する基礎となる環を、暗号化側によって適応的に選択できることに留意されたい。すなわち暗号化側は、同じ公開鍵Ａおよび秘密鍵Ｔを用いて、基礎となる環を、任意のｒ≦ｐに対してＺｒとして選択する（これによって、暗号文をＣ＝ＡＳ＋ｒＸ＋Ｂとして計算する）ことが可能であり、復号側はそれに応じて復号することが可能である。
【００６７】
４．２  公式プライバシ
前述のように、この方式は、秘密鍵の保持者に対して「公式プライバシ」を保証していない。たとえば、暗号文行列Ｃが与えられた場合、復号側が、この暗号文が識別の暗号化にゼロ行列の暗号化を乗じることによって取得されたケースと、ゼロ行列の２つの暗号化を乗じることによって取得されたケースとを、区別できる場合がある。
【００６８】
この欠点は、標準的な技法によって修正可能である。第１に、定理２で指定されたようなｑから、ｑ’≧ｑ・２ω（ｌｏｇ  ｎ）へ切り換えることで、係数のサイズをいくらか増加させる。次に、ｐを法として何らかの平文行列を暗号化する暗号文行列Ｃ＊が与えられた場合、
【数８７】
2013524277.tif 000089
を設定することによって、これをブラインド化し、上式で、Ｓ、Ｓ’は、
【数８８】
2013524277.tif 000090
で均一であり、Ｘ＊の各エントリは、この方式で使用されるパラメータβよりも超多項式的に大きいβ’を備えた
【数８９】
2013524277.tif 000091
から選択される。
【００６９】
事実２を使用して、付加されたＸ＊内のノイズがこの暗号文の原点のすべてのトレースを「かき消す」ことを示すことができる。すなわち、結果として生じる暗号文は、Ｃ＝ＡＳ’１＋ｐＸ’＋Ｂ＋（Ｓ’２）ｔＡｔの形であり、この式で、Ｓ’１、Ｓ’２はランダム（たとえば均一にランダム）であり、Ｂは対応する平文であり、Ｘ’の分布はこの暗号文行列の出所とはほぼ無関係である。
【００７０】
たとえ暗号化された平文行列がより大きな環Ｚｐ’内で選択された場合であっても、ブラインド化手順で使用されるパラメータｐが元のｐ’を分割する限り、同じブラインド化技法が使用可能であることに留意されたい。
【００７１】
４．３  多項式および大きい整数の暗号化
多項式または大きい数を暗号化するために、これらの多項式または数値上で演算を実行するために例示的方式によって本来サポートされている行列演算を活用させるような方法で、それらを行列として符号化する。
【００７２】
まず多項式について考えると、２つの多項式の係数を２つの行列内に埋め込み、これらの行列の乗法によって、結果として生じる積多項式のすべての係数を生み出すような方法が良く知られている。たとえば、２つの多項式
【数９０】
2013524277.tif 000092
および
【数９１】
2013524277.tif 000093
の場合、
【数９２】
2013524277.tif 000094
を使用することができる。
【００７３】
上記の積行列は、単なる積多項式の係数ではないことを示すという点で、プライベートでないことに留意されたい。これは、行列の暗号化に、第１列および第１行、ならびにいずれの場所のランダム・エントリにもゼロを追加することによって、容易に修正することができる。また、この単純な埋め込みは、暗号文拡張率Ｏ（ｍ）を生じさせる（ｍ×ｍ行列を使用して次数（ｍ−１）多項式を暗号化する）という点で「無駄が多い」。より経済的な埋め込みも可能であろう。
【００７４】
整数乗法に移ると、２つのｍビット整数を乗じる明らかな方法は、何らかのｐ≧２２ｍについて、平文スペースを単にＺｐに設定することであるが、こうした大きい平文スペースでの作業は不都合な場合がある。したがって、小さい入力スペースで大きな整数乗法を実施するための方法を追及することが望ましい可能性がある。１つの可能性は、多項式に対して実行された技法と同じ技法を使用し、２進表現の整数
【数９３】
2013524277.tif 000095
を、ｘ＝２で評価された２進多項式
【数９４】
2013524277.tif 000096
とみなすことである。２つの整数、ａ、ｂが与えられた場合、何らかのｐ≧ｍについて、平文スペースＺｐ上で対応する多項式
【数９５】
2013524277.tif 000097
の２進係数を暗号化する。積多項式の係数を読み取った後、整数上で
【数９６】
2013524277.tif 000098
を計算する。
【００７５】
しかしながら、この解決策は、ａ、ｂに関する情報を、それらの整数積のみよりも多くリークすることから、プライベートではない。これをプライベートにするための１つの手法は、ランダム要素
【数９７】
2013524277.tif 000099
を、積行列の第１の行および列に追加し、結果として、
【数９８】
2013524277.tif 000100
とすることである。これによって秘密鍵保持者は、ａ・ｂ（ｍｏｄ  ｐ）を回復することが可能となる。これを異なるｐを用いて数回反復することで、中国剰余（Chinese remaindering）を使用してａ・ｂを完全に回復することができる。
【００７６】
４．４  ２から２の復号
例示的暗号化システムでは、２つの異なる公開鍵の下で２つの行列の暗号化を有する場合、これら２つの暗号文を乗算し、２つの平文行列の積に対応する「暗号文」を取得できることに留意されたい。その後、この「暗号文」は、２つの秘密鍵をまとめて引くことによって復号可能である。
【００７７】
より詳細に言えば、２つの公開鍵Ａ１、Ａ２および対応する２つの秘密鍵Ｔ１、Ｔ２を有し、両方のペアが同じ素数ｑを法として定義されているものと想定してみる。（また、わかりやすくするために、両方のペアが同じパラメータｎおよびｍを使用するものと仮定するが、この仮定は不要な場合がある。）次に、２つの暗号文
【数９９】
2013524277.tif 000101
および
【数１００】
2013524277.tif 000102
が与えられた場合、平文
【数１０１】
2013524277.tif 000103
に対応する「積暗号文」
【数１０２】
2013524277.tif 000104
を計算することができる。この平文は、Ｔ１およびＴ２の両方がわかっている場合、
【数１０３】
2013524277.tif 000105
を設定することによって、回復可能である。
【００７８】
４．５  識別ベースおよび耐リーク性のＢＧＮ型暗号化
次に、非限定的な例として、識別ベース暗号化および耐リーク性などのより「高度な機能」を得るために、単なる標準的な公開鍵暗号化を超えて、１乗法の準同形を拡張する方法が示される。これは、［１０］からの（異なる入力符号化を用いた）「２重Ｒｅｇｅｖ暗号化システム」を、（行列の特定の形についての）例示的暗号化方式の特殊なケースとしてみなすことができる、単なる観察から得られ、したがって、同じ準同形演算をサポートしている。ＩＢＥ（ランダム・オラクル・モデルにおける）は、Ｇｅｎｔｒｙ等が［１０］において、２重Ｒｅｇｅｖ鍵をマスタ鍵から導出する方法を示したことに直接付随し、耐リーク性は、Ｄｏｄｉｓ等が［６］において、２重Ｒｅｇｅｖ暗号化システムが耐リーク性であることを証明したことに付随している。
【００７９】
［１０］からの「２重Ｒｅｇｅｖ暗号化システム」を想起してみると、公開鍵は行列
【数１０４】
2013524277.tif 000106
であり、秘密鍵は２重内の１つのショート・ベクトル、すなわちショート
【数１０５】
2013524277.tif 000107
であることから、結果として
【数１０６】
2013524277.tif 000108
となる。さらに、
【数１０７】
2013524277.tif 000109
内の最終エントリは、常に−１である。
【００８０】
［１０］に記載されたような暗号化システムでは、ビットｂは、均一なベクトル
【数１０８】
2013524277.tif 000110
および小さいエラー・ベクトル
【数１０９】
2013524277.tif 000111
を選択し、その後、暗号文ベクトルの１つのエントリの「最上位ビット」内にビットｂを符号化すること、すなわち、
【数１１０】
2013524277.tif 000112
によって暗号化される。しかしながら、準同形を得るためには、
【数１１１】
2013524277.tif 000113
を設定して、最下位ビット内の入力を符号化する。この入力符号化により、２重Ｒｅｇｅｖ暗号化システムを例示的暗号化システムの特殊なケースとしてみなすことが可能であり、ここで公開鍵は同じ行列Ａであり、秘密鍵は最大階数行列ではない代わりに、階数−１行列である。行列Ｔ、Ｓ、Ｘ、Ｂは、以下のように定義される。
【数１１２】
2013524277.tif 000114
（すなわち、Ｔの最上行以外はすべてゼロであり、Ｓ、Ｘの右端列以外はすべてゼロであり、Ｂの右下の要素以外はすべてゼロである。）
【００８１】
意味論的安全性は、ＬＷＥに従うことが容易に示される。鍵は単なる２重Ｒｅｇｅｖ鍵であるため、［６］と同じ論証により、たとえ秘密鍵の部分的リークに直面しても依然としてセキュアであることを示す。また［１０］では、識別ベースの設定において、この秘密鍵が（ランダム・オラクル・モデルにおける）マスタ秘密鍵からどのように計算できるかも示された。
【００８２】
これらの選択肢では、ほとんどの「暗号文行列」はゼロであるため、暗号文として出力することが必要であるのはすべて、実際には１つのベクトル
【数１１３】
2013524277.tif 000115
これが暗黙的に、行列
【数１１４】
2013524277.tif 000116
を符号化する。その後、準同形演算が暗黙行列に適用され、すなわち、加法は単なる要素的にｑを法とする加法であり、２つのベクトルの乗法は外積演算である。
【００８３】
暗号文行列を復号するために、秘密鍵ベクトル
【数１１５】
2013524277.tif 000117
によって左右から乗算し、第１にｑを法とする結果を、次に２を法とする結果を減じる。平文行列Ｂの特殊な形により、これは、左側をＴで乗算し、右側をＴｔで乗算した後、結果の右下の要素のみを取ることと同じである。
【００８４】
行列Ｔはもはや逆数を有さないが、依然として隠されたビットｂを回復することができる。これは、
【数１１６】
2013524277.tif 000118
を有することから、逆数による乗算の必要なしに、単に、
【数１１７】
2013524277.tif 000119
を設定することで実行される。
【００８５】
２重暗号化システムではｕｍ＝−１であることを想起すると、この手順によって、実際には右側の解が与えられる。
【００８６】
４．６  単純な復号
前述のように、暗号文は以下に従って復号される。
Ｂ＝Ｔ−１・（ＴＣＴｔ  ｍｏｄ  ｑ）・（Ｔｔ）−１  ｍｏｄ  ｐ
【００８７】
その拡張の１つが、これに代わって「単純な」復号公式を使用することである。
Ｂ＝Ｔ−１・（ＴＣ  ｍｏｄ  ｑ）ｍｏｄ  ｐ
【００８８】
単純な復号は、暗号文が乗法の対象でない限り、復号するために十分正確で（たとえば十分に適切で）なければならない。
【００８９】
５  他の例示的実施形態
図１は、本発明の例示的実施形態に従った、例示的暗号化動作／機能を示す。図２は、本発明の例示的実施形態に従った、例示的復号動作／機能を示す。図３は、本発明の例示的実施形態に従った、例示的鍵生成（ＫｅｙＧｅｎ）動作／機能を示す。図４は、本発明の例示的実施形態に従った、例示的暗号文加法動作／機能（たとえば、ｉ暗号文、ｎｃ暗号文について）を示す。図５は、本発明の例示的実施形態に従った、例示的暗号文乗法動作／機能（たとえば、２つの暗号文Ｃ１およびＣ２について）を示す。図６は、本発明の例示的実施形態に従った、例示的「単純復号」動作／機能を示す。
【００９０】
図７は、ある例示的実施形態が内部に実装可能な２００を示すブロック図である。ある例示的実施形態では、システム２００に従って、図１〜図６に示された様々なブロックをまとめてまたは別個に実装可能である。システム２００は、ある実施形態では少なくとも１つのプロセッサ２０４を含むことが可能な、少なくとも１つの回路２０２を含むことができる。システム２００は、少なくとも１つのメモリ２０６（たとえば揮発性メモリ・デバイス）または少なくとも１つのストレージ２０８あるいはその両方を含むこともできる。ストレージ２０８は、不揮発性メモリ・デバイス（たとえばＥＥＰＲＯＭ、ＲＯＭ、ＰＲＯＭ、ＲＡＭ、ＤＲＡＭ、ＳＲＡＭ、フラッシュ、ファームウェア、プログラマブル論理など）、磁気ディスク・ドライブ、光ディスク・ドライブ、またはテープ・ドライブ、あるいはそれらすべてを、非限定的な例として含むことができる。ストレージ２０８は、内部ストレージ・デバイス、接続ストレージ・デバイス、またはネットワーク・アクセス可能ストレージ・デバイス、あるいはそれらすべてを、非限定的な例として備えることができる。システム２００は、メモリ２０６内にロードし、プロセッサ２０４または回路２０２あるいはその両方によって実行可能な、コード２１２（たとえばプログラム・コード）を含む、少なくとも１つのプログラム論理２１０を含むことができる。ある例示的実施形態では、コード２１２を含むプログラム論理２１０を、ストレージ２０８内に格納することができる。ある他の実施形態では、プログラム論理２１０は回路２０２内に実装可能である。したがって、図７は、プログラム論理２１０を他の要素とは別に示しているが、プログラム論理２１０は、メモリ２０６または回路２０２あるいはその両方内に実装可能である。
【００９１】
システム２００は、少なくとも１つの他のシステム、デバイス、または装置、あるいはそれらすべてと通信可能な、少なくとも１つの通信構成要素２１４を含むことができる。通信構成要素２１４は、情報の送受信を行うように構成されたトランシーバ、情報を送信するように構成された送信器、または情報を受信するように構成された受信器、あるいはそれらすべてを含むことができる。非限定的な例として、通信構成要素２１４は、モデムまたはネットワーク・カードを備えることができる。図７のシステム２００は、非限定的な例として、デスクトップ・コンピュータ、ポータブル・コンピュータ、またはサーバなどの、コンピュータまたはコンピュータ・システム内で具体化可能である。図７に示されたシステム２００の構成要素は、非限定的な例として、１つまたは複数の内部バス、接続、ワイヤ、または（プリント）回路基板、あるいはそれらすべてを使用して、まとめて接続または結合することができる。
【００９２】
本発明の例示的実施形態に従って、回路２０２、プロセッサ２０４、メモリ２０６、ストレージ２０８、プログラム論理２１０、または通信構成要素２１４、あるいはそれらすべてのうちの、１つまたは複数が、本明細書で考察される様々なアイテム（たとえば、行列、変数、等式、公式、動作、動作論理、論理）のうちの、１つまたは複数を格納することができることを理解されたい。非限定的な例として、上記で識別された構成要素のうちの１つまたは複数は、（たとえば暗号化される、復号の結果として生じる）情報Ｂ、または（たとえば復号される、暗号化の結果として生じる）暗号文Ｃ、あるいはその両方の、受信または格納、あるいはその両方を実行することができる。他の非限定的な例として、上記で識別された構成要素のうちの１つまたは複数は、本明細書で説明されるような暗号化機能または復号機能あるいはその両方の、受信または格納、あるいはその両方を実行することができる。
【００９３】
以下で、本発明の様々な非限定的な例示的実施形態について、さらに説明する。下記の例示的実施形態には、わかりやすくするために別々の番号が付けられている。この番号付けは、１つまたは複数の例示的実施形態の態様が、１つまたは複数の他の態様または例示的実施形態に関連して実施可能であるため、様々な例示的実施形態を完全に分離するものと解釈されるべきではない。
【００９４】
（１）  例示的一実施形態で、図８に示されるように、動作を実行するために機械によって実行可能な命令のプログラムを有形に具体化するコンピュータ読み取り可能記憶媒体であって、動作は、暗号化機能を備える暗号化方式に従って暗号文Ｃとして暗号化されることになる情報Ｂを受信すること（３０１）、および、暗号文Ｃを取得するために暗号化方式の暗号化機能に従って情報Ｂを暗号化すること（３０２）を含み、暗号化方式は少なくとも１つの秘密鍵Ｔに対応する少なくとも１つの公開鍵Ａを使用し、情報Ｂ、暗号文Ｃ、少なくとも１つの公開鍵Ａ、および少なくとも１つの秘密鍵Ｔは行列であり、暗号化機能は入力として少なくとも１つの公開鍵Ａおよび情報Ｂを受信し、暗号文Ｃを
【数１１８】
2013524277.tif 000120
として出力し、この式でＳはランダム行列であり、Ｘはエラー行列であり、ｐは整数であり、ｑは奇数の素数である。
【００９５】
前述のコンピュータ読み取り可能記憶媒体であって、
【数１１９】
2013524277.tif 000121
【数１２０】
2013524277.tif 000122
および
【数１２１】
2013524277.tif 000123
であり、ここでｎは安全性パラメータを示し、ｍ，ｑ＝ｐｏｌｙ（ｎ）であり、
【数１２２】
2013524277.tif 000124
はエラー分布であり、βは、β＝１／ｐｏｌｙ（ｎ）によって与えられるガウス・エラー・パラメータである。上記いずれかのようなコンピュータ読み取り可能記憶媒体であって、暗号化方式は準同形であり、双一次形式（たとえば、多項式的に多くの加法および１つの乗法）の計算をサポートする。上記いずれかのようなコンピュータ読み取り可能記憶媒体であって、ｐ＝２であり、情報Ｂは２進値の行列を備える。上記いずれかのようなコンピュータ読み取り可能記憶媒体であって、ｃ＝ｃ（ｎ）＞０、ｑ＞２２０ｐ２（ｃ＋４）３ｎ３ｃ＋４ｌｏｇ５ｎ、
【数１２３】
2013524277.tif 000125
および
【数１２４】
2013524277.tif 000126
である。上記いずれかのようなコンピュータ読み取り可能記憶媒体であって、暗号化方式は、行列環
【数１２５】
2013524277.tif 000127
上でいずれかの次数でｎｃの加法および１つの乗法をサポートする。
【００９６】
上記いずれかのようなコンピュータ読み取り可能記憶媒体であって、動作は、暗号文Ｃを出力することをさらに含む。上記いずれかのようなコンピュータ読み取り可能記憶媒体であって、ｐは、情報を含むある次数のスペースである。上記いずれかのようなコンピュータ読み取り可能記憶媒体であって、ｐはある次数のスペース、
【数１２６】
2013524277.tif 000128
および
【数１２７】
2013524277.tif 000129
である。上記いずれかのようなコンピュータ読み取り可能記憶媒体であって、暗号化方式は、秘密鍵の保持者が、復号機能の公式の知識をさらに取得することなしに暗号文を復号するよう構成されるように、公式プライベートなセキュアな計算をさらに実行可能にする。上記いずれかのようなコンピュータ読み取り可能記憶媒体であって、ｑ＞ｐである。上記いずれかのようなコンピュータ読み取り可能記憶媒体であって、暗号化方式は、任意数の加法を伴う対数乗法深さの回路のための準同形暗号化方式を備え、準同形暗号化方式の安全性は、エラーでの習得問題の困難性に基づく。上記いずれかのようなコンピュータ読み取り可能記憶媒体であって、Ｔ、Ｘ、およびＢ（のエントリ）が小さいため、Ｔ・（２Ｘ＋Ｂ）内のエントリはｑより少ない。上記いずれかのようなコンピュータ読み取り可能記憶媒体であって、暗号文Ｃのサイズは平文Ｂのサイズのおよそ（たとえば実質上）３倍である。
【００９７】
上記いずれかのようなコンピュータ読み取り可能記憶媒体であって、暗号化方式は鍵生成機能をさらに備え、鍵生成機能は、入力として１ｎ、ｑ、およびｍを受信し、少なくとも１つの公開鍵Ａおよび少なくとも１つの秘密鍵Ｔを出力する。上記いずれかのようなコンピュータ読み取り可能記憶媒体であって、鍵生成機能は、
入力１ｎ、正整数ｑ≧２、およびｐｏｌｙ（ｎ）で境界が定められた正整数ｍ≧８ｎ  ｌｏｇ  ｑ上で、行列
【数１２８】
2013524277.tif 000130
および
【数１２９】
2013524277.tif 000131
を出力する、トラップドア・サンプリング・アルゴリズムを実行することによって動作する。上記いずれかのようなコンピュータ読み取り可能記憶媒体であって、Ａは
【数１３０】
2013524277.tif 000132
上で統計的に均一に近く、Ｔの行は格子
【数１３１】
2013524277.tif 000133
の基底を形成し、Ｔの行のユークリッド・ノルムはＯ（ｎ  ｌｏｇ  ｑ）によって境界が定められる。上記いずれかのようなコンピュータ読み取り可能記憶媒体であって、Ｔ・Ａ＝０（ｍｏｄ  ｑ）であり、Ｔは可逆であり、Ｔのエントリは小さい。
【００９８】
上記いずれかのようなコンピュータ読み取り可能記憶媒体であって、暗号方式は復号機能をさらに備え、復号機能は、入力として少なくとも１つの秘密鍵Ｔおよび暗号文Ｃを受信し、Ｂ＝Ｔ−１・（ＴＣＴｔ  ｍｏｄ  ｑ）・（Ｔｔ）−１  ｍｏｄ  ｐに従って情報Ｂを出力する。上記いずれかのようなコンピュータ読み取り可能記憶媒体であって、
【数１３２】
2013524277.tif 000134
である。
【００９９】
上記いずれかのようなコンピュータ読み取り可能記憶媒体であって、本明細書で説明された本発明の例示的実施形態の１つまたは複数の追加の態様をさらに備える。
【０１００】
（２）  本発明の他の例示的実施形態で、暗号化機能を備える暗号化方式に従って暗号文Ｃとして暗号化されることになる情報Ｂを記憶するように構成された、少なくとも１つの記憶媒体と、暗号文Ｃを取得するために暗号化方式の暗号化機能に従って情報Ｂを暗号化するように構成された、少なくとも１つのプロセッサとを備える、装置であって、暗号化方式は少なくとも１つの秘密鍵Ｔに対応する少なくとも１つの公開鍵Ａを使用し、情報Ｂ、暗号文Ｃ、少なくとも１つの公開鍵Ａ、および少なくとも１つの秘密鍵Ｔは行列であり、暗号化機能は入力として少なくとも１つの公開鍵Ａおよび情報Ｂを受信し、暗号文Ｃを
【数１３３】
2013524277.tif 000135
として出力し、この式でＳはランダム行列であり、Ｘはエラー行列であり、ｐは整数であり、ｑは奇数の素数である。
【０１０１】
上記いずれかのような装置であって、本明細書で説明された本発明の例示的実施形態の１つまたは複数の追加の態様をさらに備える。
【０１０２】
（３）  本発明の他の例示的実施形態で、図８に示されるように、暗号化機能を備える暗号化方式に従って暗号文Ｃとして暗号化されることになる情報Ｂを、少なくとも１つのプロセッサによって受信すること（３０１）、および、暗号文Ｃを取得するために暗号化方式の暗号化機能に従って、情報Ｂを少なくとも１つのプロセッサによって暗号化すること（３０２）を含む、方法であって、暗号化方式は少なくとも１つの秘密鍵Ｔに対応する少なくとも１つの公開鍵Ａを使用し、情報Ｂ、暗号文Ｃ、少なくとも１つの公開鍵Ａ、および少なくとも１つの秘密鍵Ｔは行列であり、暗号化機能は入力として少なくとも１つの公開鍵Ａおよび情報Ｂを受信し、暗号文Ｃを
【数１３４】
2013524277.tif 000136
として出力し、この式でＳはランダム行列であり、Ｘはエラー行列であり、ｐは整数であり、ｑは奇数の素数である。
【０１０３】
上記いずれかのような方法であって、本明細書で説明された本発明の例示的実施形態の１つまたは複数の追加の態様をさらに備える。
【０１０４】
（４）  本発明の他の例示的実施形態で、暗号化機能を備える暗号化方式に従って暗号文Ｃとして暗号化されることになる情報Ｂを記憶するための手段と、暗号文Ｃを取得するために暗号化方式の暗号化機能に従って情報Ｂを暗号化するための手段とを備えた、装置であって、暗号化方式は少なくとも１つの秘密鍵Ｔに対応する少なくとも１つの公開鍵Ａを使用し、情報Ｂ、暗号文Ｃ、少なくとも１つの公開鍵Ａ、および少なくとも１つの秘密鍵Ｔは行列であり、暗号化機能は入力として少なくとも１つの公開鍵Ａおよび情報Ｂを受信し、暗号文Ｃを
【数１３５】
2013524277.tif 000137
として出力し、この式でＳはランダム行列であり、Ｘはエラー行列であり、ｐは整数であり、ｑは奇数の素数である。
【０１０５】
上記のような装置であって、記憶するための手段は少なくとも１つの記憶媒体、メモリ、またはメモリ媒体を備え、暗号化するための手段は、少なくとも１つのプロセッサ、少なくとも１つの回路、または少なくとも１つの集積回路を備える。上記いずれかのような装置であって、本明細書で説明された本発明の例示的実施形態の１つまたは複数の追加の態様をさらに備える。
【０１０６】
（５）  本発明の他の例示的実施形態で、暗号化機能を備える暗号化方式に従って暗号文Ｃとして暗号化されることになる情報Ｂを記憶するように構成された、記憶回路と、暗号文Ｃを取得するために暗号化方式の暗号化機能に従って情報Ｂを暗号化するように構成された、暗号化回路とを備える、装置であって、暗号化方式は少なくとも１つの秘密鍵Ｔに対応する少なくとも１つの公開鍵Ａを使用し、情報Ｂ、暗号文Ｃ、少なくとも１つの公開鍵Ａ、および少なくとも１つの秘密鍵Ｔは行列であり、暗号化機能は入力として少なくとも１つの公開鍵Ａおよび情報Ｂを受信し、暗号文Ｃを
【数１３６】
2013524277.tif 000138
として出力し、この式でＳはランダム行列であり、Ｘはエラー行列であり、ｐは整数であり、ｑは奇数の素数である。
【０１０７】
上記いずれかのような装置であって、本明細書で説明された本発明の例示的実施形態の１つまたは複数の追加の態様をさらに備える。
【０１０８】
（６）  本発明の他の例示的実施形態で、図９に示されるように、動作を実行するために機械によって実行可能な命令のプログラムを有形に具体化するコンピュータ読み取り可能記憶媒体であって、動作は、復号機能を備える暗号化方式に従って情報Ｂとして復号されることになる暗号文Ｃを受信すること（４０１）、および、情報Ｂを取得するために暗号化方式の復号機能に従って暗号文Ｃを復号すること（４０２）を含み、暗号化方式は少なくとも１つの秘密鍵Ｔを使用し、情報Ｂ、暗号文Ｃ、および少なくとも１つの秘密鍵Ｔは行列であり、復号機能は入力として少なくとも１つの秘密鍵Ｔおよび暗号文Ｃを受信し、Ｂ＝Ｔ−１・（ＴＣＴｔ  ｍｏｄ  ｑ）・（Ｔｔ）−１  ｍｏｄ  ｐに従って情報Ｂを出力し、この式でｐは整数であり、ｑは奇数の素数である。
【０１０９】
上記のようなコンピュータ読み取り可能記憶媒体であって、動作は、情報Ｂを出力することをさらに含む。上記いずれかのようなコンピュータ読み取り可能記憶媒体であって、少なくとも１つの秘密鍵Ｔが少なくとも１つの公開鍵Ａに対応する。上記いずれかのようなコンピュータ読み取り可能記憶媒体であって、少なくとも１つの秘密鍵Ｔは対称鍵である。上記いずれかのようなコンピュータ読み取り可能記憶媒体であって、本明細書で説明された本発明の例示的実施形態の１つまたは複数の追加の態様をさらに備える。
【０１１０】
（７）  本発明の他の例示的実施形態では、復号機能を備える暗号化方式に従って情報Ｂとして復号されることになる暗号文Ｃを記憶するように構成された、少なくとも１つの記憶媒体と、情報Ｂを取得するために暗号化方式の復号機能に従って暗号文Ｃを復号するように構成された、少なくとも１つのプロセッサとを備える、装置であって、暗号化方式は少なくとも１つの秘密鍵Ｔを使用し、情報Ｂ、暗号文Ｃ、および少なくとも１つの秘密鍵Ｔは行列であり、復号機能は入力として少なくとも１つの秘密鍵Ｔおよび暗号文Ｃを受信し、Ｂ＝Ｔ−１・（ＴＣＴｔ  ｍｏｄ  ｑ）・（Ｔｔ）−１  ｍｏｄ  ｐに従って情報Ｂを出力し、この式でｐは整数であり、ｑは奇数の素数である。
【０１１１】
上記いずれかのような装置であって、本明細書で説明された本発明の例示的実施形態の１つまたは複数の追加の態様をさらに備える。
【０１１２】
（８）  本発明の他の例示的実施形態で、図９に示されるように、復号機能を備える暗号化方式に従って情報Ｂとして復号されることになる暗号文Ｃを受信すること（４０１）、および、情報Ｂを取得するために暗号化方式の復号機能に従って暗号文Ｃを復号すること（４０２）を含む、方法であって、暗号化方式は少なくとも１つの秘密鍵Ｔを使用し、情報Ｂ、暗号文Ｃ、および少なくとも１つの秘密鍵Ｔは行列であり、復号機能は入力として少なくとも１つの秘密鍵Ｔおよび暗号文Ｃを受信し、Ｂ＝Ｔ−１・（ＴＣＴｔ  ｍｏｄ  ｑ）・（Ｔｔ）−１  ｍｏｄ  ｐに従って情報Ｂを出力し、この式でｐは整数であり、ｑは奇数の素数である。
【０１１３】
上記いずれかのような方法であって、本明細書で説明された本発明の例示的実施形態の１つまたは複数の追加の態様をさらに備える。
【０１１４】
（９）  本発明の他の例示的実施形態で、復号機能を備える暗号化方式に従って情報Ｂとして復号されることになる暗号文Ｃを記憶するための手段と、情報Ｂを取得するために暗号化方式の復号機能に従って暗号文Ｃを復号するための手段とを備える、装置であって、暗号化方式は少なくとも１つの秘密鍵Ｔを使用し、情報Ｂ、暗号文Ｃ、および少なくとも１つの秘密鍵Ｔは行列であり、復号機能は入力として少なくとも１つの秘密鍵Ｔおよび暗号文Ｃを受信し、Ｂ＝Ｔ−１・（ＴＣＴｔ  ｍｏｄ  ｑ）・（Ｔｔ）−１  ｍｏｄ  ｐに従って情報Ｂを出力し、この式でｐは整数であり、ｑは奇数の素数である。
【０１１５】
上記のような装置であって、記憶するための手段は少なくとも１つの記憶媒体、メモリ、またはメモリ媒体を備え、復号するための手段は、少なくとも１つのプロセッサ、少なくとも１つの回路、または少なくとも１つの集積回路を備える。上記いずれかのような装置であって、本明細書で説明された本発明の例示的実施形態の１つまたは複数の追加の態様をさらに備える。
【０１１６】
（１０）  本発明の他の例示的実施形態で、復号機能を備える暗号化方式に従って情報Ｂとして復号されることになる暗号文Ｃを記憶するように構成された、記憶回路と、情報Ｂを取得するために暗号化方式の復号機能に従って暗号文Ｃを復号するように構成された、復号回路とを備える、装置であって、暗号化方式は少なくとも１つの秘密鍵Ｔを使用し、情報Ｂ、暗号文Ｃ、および少なくとも１つの秘密鍵Ｔは行列であり、復号機能は入力として少なくとも１つの秘密鍵Ｔおよび暗号文Ｃを受信し、Ｂ＝Ｔ−１・（ＴＣＴｔ  ｍｏｄ  ｑ）・（Ｔｔ）−１  ｍｏｄ  ｐに従って情報Ｂを出力し、この式でｐは整数であり、ｑは奇数の素数である。
【０１１７】
上記いずれかのような装置であって、本明細書で説明された本発明の例示的実施形態の１つまたは複数の追加の態様をさらに備える。
【０１１８】
（１１）  本発明の他の例示的実施形態で、動作を実行するために機械によって実行可能な命令のプログラムを有形に具体化するコンピュータ読み取り可能記憶媒体であって、動作は、暗号化機能および復号機能を備える暗号化方式に従って暗号文Ｃとして暗号化されることになる情報Ｂを受信すること、および、暗号文Ｃを取得するために暗号化方式の暗号化機能に従って情報Ｂを暗号化することを含み、暗号化方式は少なくとも１つの公開鍵Ａおよび少なくとも１つの秘密鍵Ａに対応する少なくとも１つの秘密鍵Ｔを使用し、情報Ｂ、暗号文Ｃ、少なくとも１つの公開鍵Ａ、および少なくとも１つの秘密鍵Ｔは行列であり、
【数１３７】
2013524277.tif 000139
および
【数１３８】
2013524277.tif 000140
であり、この式でｎは安全性パラメータを示し、ｍ，ｑ＝ｐｏｌｙ（ｎ）であり、ｑは奇数の素数であり、ｐは整数であり、ｑ＞ｐであり、暗号化機能は入力としてＡおよびＢを受信し、暗号文Ｃを
【数１３９】
2013524277.tif 000141
として出力し、この式でＳはランダム行列であって、
【数１４０】
2013524277.tif 000142
であり、Ｘはエラー行列であって、
【数１４１】
2013524277.tif 000143
であり、この式で
【数１４２】
2013524277.tif 000144
はエラー分布であり、βは、β＝１／ｐｏｌｙ（ｎ）によって得られるガウスのエラー・パラメータであり、復号機能は入力としてＴおよびＣを受信し、Ｂ＝Ｔ−１・（ＴＣＴｔ  ｍｏｄ  ｑ）・（Ｔｔ）−１  ｍｏｄ  ｐに従って情報Ｂを出力し、暗号化方式は準同形であり、双一次形式の計算（たとえば、多項式的に多くの加法および１つの乗法）をサポートする。
【０１１９】
上記いずれかのようなコンピュータ読み取り可能記憶媒体であって、本明細書で説明された本発明の例示的実施形態の１つまたは複数の追加の態様をさらに備える。方法、装置、またはコンピュータ・プログラムであって、前述のコンピュータ読み取り可能記憶媒体に対応する。
【０１２０】
（１２）  本発明の他の例示的実施形態で、動作を実行するために機械によって実行可能な命令のプログラムを有形に具体化するコンピュータ読み取り可能記憶媒体であって、動作は、暗号化機能および復号機能を備える暗号化方式に従って第１の暗号文Ｃ１として暗号化されることになる第１の情報Ｂ１、および暗号化方式に従って第２の情報Ｂ２として復号されることになる第２の暗号文Ｃ２のうちの、少なくとも１つを受信すること、ならびに、第１の暗号文Ｃ１を取得するために暗号化方式の暗号化機能に従って第１の情報Ｂ１を暗号化すること、および第２の情報Ｂ２を取得するために暗号化方式の復号機能に従って第２の暗号文Ｃ２を復号することのうちの、少なくとも１つを含み、暗号化方式は、少なくとも１つの公開鍵Ａおよび少なくとも１つの公開鍵Ａに対応する少なくとも１つの秘密鍵Ｔを使用し、情報Ｂ、暗号文Ｃ、少なくとも１つの公開鍵Ａ、および少なくとも１つの秘密鍵Ｔは行列であり、暗号化機能は入力として少なくとも１つの公開鍵Ａおよび情報Ｂを受信し、暗号文Ｃを
【数１４３】
2013524277.tif 000145
として出力し、この式でＳはランダム行列であり、Ｘはエラー行列であり、ｐは整数であり、ｑは奇数の素数であり、復号機能は、入力として少なくとも１つの秘密鍵Ｔおよび暗号文Ｃを受信し、Ｂ＝Ｔ−１・（ＴＣＴｔ  ｍｏｄ  ｑ）・（Ｔｔ）−１  ｍｏｄ  ｐに従って情報Ｂを出力する。
【０１２１】
上記いずれかのようなコンピュータ読み取り可能記憶媒体であって、本明細書で説明された本発明の例示的実施形態の１つまたは複数の追加の態様をさらに備える。方法、装置、またはコンピュータ・プログラムであって、前述のコンピュータ読み取り可能記憶媒体に対応する。
【０１２２】
（１３）  本発明の他の例示的実施形態で、図１０に示されるように、動作を実行するために機械によって実行可能な命令のプログラムを有形に具体化するコンピュータ読み取り可能記憶媒体であって、動作は、暗号化機能および復号機能を備える暗号化方式に従って複数の暗号文Ｃｉとして暗号化されることになる複数の情報Ｂｉを受信すること（５０１）、それぞれの暗号文Ｃｉを取得するために暗号化方式の暗号化機能に従って複数の情報Ｂｉのそれぞれを暗号化すること（５０２）、２次多項式を
【数１４４】
2013524277.tif 000146
として暗号文Ｃｉに適用することによって結果の暗号文Ｃｐｏｌｙを計算することであって、合計は指数ｉおよびｊのサブセットを介する、計算すること（５０３）、ならびに、結果として生じる情報Ｂｐｏｌｙを取得するために暗号化方式の復号機能に従って結果の暗号文Ｃｐｏｌｙを復号すること（５０４）、を含み、暗号化方式は、少なくとも１つの秘密鍵Ｔに対応する少なくとも１つの公開鍵Ａを使用し、複数の情報Ｂｉ、暗号文Ｃｉ、少なくとも１つの公開鍵Ａ、および少なくとも１つの秘密鍵Ｔは行列であり、暗号化機能は入力として少なくとも１つの公開鍵Ａおよび情報Ｂを受信し、暗号文Ｃｉを
【数１４５】
2013524277.tif 000147
として出力し、この式でＳはランダム行列であり、Ｘはエラー行列であり、ｐは整数であり、ｑは奇数の素数であり、ｉは整数であり、ｊは整数であり、復号機能は、入力として少なくとも１つの秘密鍵Ｔおよび結果の暗号文Ｃｐｏｌｙを受信し、指数ｉおよびｊのサブセットを介する
【数１４６】
2013524277.tif 000148
に従って結果として生じる情報Ｂｐｏｌｙを出力する。
【０１２３】
上記いずれかのようなコンピュータ読み取り可能記憶媒体であって、本明細書で説明された本発明の例示的実施形態の１つまたは複数の追加の態様をさらに備える。方法、装置、またはコンピュータ・プログラムであって、前述のコンピュータ読み取り可能記憶媒体に対応する。
【０１２４】
（１４）  本発明の他の例示的実施形態で、動作を実行するために機械によって実行可能な命令のプログラムを有形に具体化するコンピュータ読み取り可能記憶媒体であって、動作は、復号機能を備える暗号化方式に従って情報Ｂとして復号されることになる暗号文Ｃを受信すること、および、情報Ｂを取得するために暗号化方式の復号機能に従って暗号文Ｃを復号することを含み、暗号化方式は少なくとも１つの秘密鍵Ｔを使用し、情報Ｂ、暗号文Ｃ、および少なくとも１つの秘密鍵Ｔは行列であり、復号機能は入力として少なくとも１つの秘密鍵Ｔおよび暗号文Ｃを受信し、Ｂ＝Ｔ−１・（ＴＣ  ｍｏｄ  ｑ）ｍｏｄ  ｐに従って情報Ｂを出力し、この式でｐは整数であり、ｑは奇数の素数である。
【０１２５】
上記いずれかのようなコンピュータ読み取り可能記憶媒体であって、本明細書で説明された本発明の例示的実施形態の１つまたは複数の追加の態様をさらに備える。方法、装置、またはコンピュータ・プログラムであって、前述のコンピュータ読み取り可能記憶媒体に対応する。
【０１２６】
（１５）  本発明の他の例示的実施形態では、復号機能を備える暗号化方式に従って情報Ｂとして復号されることになる暗号文Ｃを記憶するように構成された、少なくとも１つの記憶媒体と、情報Ｂを取得するために暗号化方式の復号機能に従って暗号文Ｃを復号するように構成された、少なくとも１つのプロセッサとを備える、装置であって、暗号化方式は少なくとも１つの秘密鍵Ｔを使用し、情報Ｂ、暗号文Ｃ、および少なくとも１つの秘密鍵Ｔは行列であり、復号機能は入力として少なくとも１つの秘密鍵Ｔおよび暗号文Ｃを受信し、Ｂ＝Ｔ−１・（ＴＣ  ｍｏｄ  ｑ）  ｍｏｄ  ｐに従って情報Ｂを出力し、この式でｐは整数であり、ｑは奇数の素数である。
【０１２７】
上記いずれかのような装置であって、本明細書で説明された本発明の例示的実施形態の１つまたは複数の追加の態様をさらに備える。
【０１２８】
（１６）  本発明の他の例示的実施形態で、図９に示されるように、復号機能を備える暗号化方式に従って情報Ｂとして復号されることになる暗号文Ｃを受信すること（６０１）、および、情報Ｂを取得するために暗号化方式の復号機能に従って暗号文Ｃを復号すること（６０２）を含む、方法であって、暗号化方式は少なくとも１つの秘密鍵Ｔを使用し、情報Ｂ、暗号文Ｃ、および少なくとも１つの秘密鍵Ｔは行列であり、復号機能は入力として少なくとも１つの秘密鍵Ｔおよび暗号文Ｃを受信し、Ｂ＝Ｔ−１・（ＴＣ  ｍｏｄ  ｑ）  ｍｏｄ  ｐに従って情報Ｂを出力し、この式でｐは整数であり、ｑは奇数の素数である。
【０１２９】
上記いずれかのような方法であって、本明細書で説明された本発明の例示的実施形態の１つまたは複数の追加の態様をさらに備える。
【０１３０】
（１７）  本発明の他の例示的実施形態で、復号機能を備える暗号化方式に従って情報Ｂとして復号されることになる暗号文Ｃを記憶するための手段と、情報Ｂを取得するために暗号化方式の復号機能に従って暗号文Ｃを復号するための手段とを備える、装置であって、暗号化方式は少なくとも１つの秘密鍵Ｔを使用し、情報Ｂ、暗号文Ｃ、および少なくとも１つの秘密鍵Ｔは行列であり、復号機能は入力として少なくとも１つの秘密鍵Ｔおよび暗号文Ｃを受信し、Ｂ＝Ｔ−１・（ＴＣ  ｍｏｄ  ｑ）  ｍｏｄ  ｐに従って情報Ｂを出力し、この式でｐは整数であり、ｑは奇数の素数である。
【０１３１】
上記のような装置であって、記憶するための手段は少なくとも１つの記憶媒体、メモリ、またはメモリ媒体を備え、復号するための手段は、少なくとも１つのプロセッサ、少なくとも１つの回路、または少なくとも１つの集積回路を備える。上記いずれかのような装置であって、本明細書で説明された本発明の例示的実施形態の１つまたは複数の追加の態様をさらに備える。
【０１３２】
（１８）  本発明の他の例示的実施形態で、復号機能を備える暗号化方式に従って情報Ｂとして復号されることになる暗号文Ｃを記憶するように構成された、記憶回路と、情報Ｂを取得するために暗号化方式の復号機能に従って暗号文Ｃを復号するように構成された、復号回路とを備える、装置であって、暗号化方式は少なくとも１つの秘密鍵Ｔを使用し、情報Ｂ、暗号文Ｃ、および少なくとも１つの秘密鍵Ｔは行列であり、復号機能は入力として少なくとも１つの秘密鍵Ｔおよび暗号文Ｃを受信し、Ｂ＝Ｔ−１・（ＴＣ  ｍｏｄ  ｑ）  ｍｏｄ  ｐに従って情報Ｂを出力し、この式でｐは整数であり、ｑは奇数の素数である。
【０１３３】
上記いずれかのような装置であって、本明細書で説明された本発明の例示的実施形態の１つまたは複数の追加の態様をさらに備える。
【０１３４】
（１９）  本発明の他の例示的実施形態で、動作を実行するために機械によって実行可能な命令のプログラムを有形に具体化するコンピュータ読み取り可能記憶媒体であって、動作は、暗号化機能および復号機能を備える暗号化方式に従って暗号文Ｃとして暗号化されることになる情報Ｂを受信すること、および、暗号文Ｃを取得するために暗号化方式の暗号化機能に従って情報Ｂを暗号化することを含み、暗号化方式は少なくとも１つの公開鍵Ａおよび少なくとも１つの秘密鍵Ａに対応する少なくとも１つの秘密鍵Ｔを使用し、情報Ｂ、暗号文Ｃ、少なくとも１つの公開鍵Ａ、および少なくとも１つの秘密鍵Ｔは行列であり、
【数１４７】
2013524277.tif 000149
および
【数１４８】
2013524277.tif 000150
であり、この式でｎは安全性パラメータを示し、ｍ，ｑ＝ｐｏｌｙ（ｎ）であり、ｑは奇数の素数であり、ｐは整数であり、ｑ＞ｐであり、暗号化機能は入力としてＡおよびＢを受信し、暗号文Ｃを
【数１４９】
2013524277.tif 000151
として出力し、この式でＳはランダム行列であって、
【数１５０】
2013524277.tif 000152
であり、Ｘはエラー行列であって、
【数１５１】
2013524277.tif 000153
であり、この式で
【数１５２】
2013524277.tif 000154
はエラー分布であり、βは、β＝１／ｐｏｌｙ（ｎ）によって得られるガウスのエラー・パラメータであり、復号機能は入力としてＴおよびＣを受信し、Ｂ＝Ｔ−１・（ＴＣ  ｍｏｄ  ｑ）  ｍｏｄ  ｐに従って情報Ｂを出力し、暗号化方式は準同形であり、多項式的に多くの加法をサポートする。
【０１３５】
上記いずれかのようなコンピュータ読み取り可能記憶媒体であって、本明細書で説明された本発明の例示的実施形態の１つまたは複数の追加の態様をさらに備える。方法、装置、またはコンピュータ・プログラムであって、前述のコンピュータ読み取り可能記憶媒体に対応する。
【０１３６】
（２０）  本発明の他の例示的実施形態で、動作を実行するために機械によって実行可能な命令のプログラムを有形に具体化するコンピュータ読み取り可能記憶媒体であって、動作は、暗号化機能および復号機能を備える暗号化方式に従って第１の暗号文Ｃ１として暗号化されることになる第１の情報Ｂ１、および暗号化方式に従って第２の情報Ｂ２として復号されることになる第２の暗号文Ｃ２のうちの、少なくとも１つを受信すること、ならびに、第１の暗号文Ｃ１を取得するために暗号化方式の暗号化機能に従って第１の情報Ｂ１を暗号化すること、および第２の情報Ｂ２を取得するために暗号化方式の復号機能に従って第２の暗号文Ｃ２を復号することのうちの、少なくとも１つを含み、暗号化方式は、少なくとも１つの公開鍵Ａおよび少なくとも１つのの公開鍵Ａに対応する少なくとも１つの秘密鍵Ｔを使用し、情報Ｂ、暗号文Ｃ、少なくとも１つの公開鍵Ａ、および少なくとも１つの秘密鍵Ｔは行列であり、暗号化機能は入力として少なくとも１つの公開鍵Ａおよび情報Ｂを受信し、暗号文Ｃを
【数１５３】
2013524277.tif 000155
として出力し、この式でＳはランダム行列であり、Ｘはエラー行列であり、ｐは整数であり、ｑは奇数の素数であり、復号機能は、入力として少なくとも１つの秘密鍵Ｔおよび暗号文Ｃを受信し、Ｂ＝Ｔ−１・（ＴＣ  ｍｏｄ  ｑ）  ｍｏｄ  ｐに従って情報Ｂを出力する。
【０１３７】
上記いずれかのようなコンピュータ読み取り可能記憶媒体であって、本明細書で説明された本発明の例示的実施形態の１つまたは複数の追加の態様をさらに備える。方法、装置、またはコンピュータ・プログラムであって、前述のコンピュータ読み取り可能記憶媒体に対応する。
【０１３８】
（２１）  本発明の他の例示的実施形態で、図１２に示されるように、動作を実行するために機械によって実行可能な命令のプログラムを有形に具体化するコンピュータ読み取り可能記憶媒体であって、動作は、暗号化機能および復号機能を備える暗号化方式に従って複数の暗号文Ｃｉとして暗号化されることになる複数の情報Ｂｉを受信すること（７０１）、それぞれの暗号文Ｃｉを取得するために暗号化方式の暗号化機能に従って複数の情報Ｂｉのそれぞれを暗号化すること（７０２）、合計を
【数１５４】
2013524277.tif 000156
として暗号文Ｃｉに適用することによって結果の暗号文Ｃｓｕｍを計算することであって、合計は指数ｉのサブセットを介する、計算すること（７０３）、ならびに、結果として生じる情報Ｂｓｕｍを取得するために暗号化方式の復号機能に従って結果の暗号文Ｃｓｕｍを復号すること（７０４）、を含み、暗号化方式は、少なくとも１つの秘密鍵Ｔに対応する少なくとも１つの公開鍵Ａを使用し、複数の情報Ｂｉ、暗号文Ｃｉ、少なくとも１つの公開鍵Ａ、および少なくとも１つの秘密鍵Ｔは行列であり、暗号化機能は入力として少なくとも１つの公開鍵Ａおよび情報Ｂを受信し、暗号文Ｃｉを
【数１５５】
2013524277.tif 000157
として出力し、この式でＳはランダム行列であり、Ｘはエラー行列であり、ｐは整数であり、ｑは奇数の素数であり、ｉは整数であり、ｊは整数であり、復号機能は、入力として少なくとも１つの秘密鍵Ｔおよび結果の暗号文Ｃｓｕｍを受信し、指数ｉのサブセットを介するＢｓｕｍ＝Ｔ−１・（ＴＣｓｕｍ  ｍｏｄ  ｑ）ｍｏｄ  ｐ＝ΣｉＢｉｍｏｄ  ｐに従って結果として生じる情報Ｂｓｕｍを出力する。
【０１３９】
上記いずれかのようなコンピュータ読み取り可能記憶媒体であって、本明細書で説明された本発明の例示的実施形態の１つまたは複数の追加の態様をさらに備える。方法、装置、またはコンピュータ・プログラムであって、前述のコンピュータ読み取り可能記憶媒体に対応する。
【０１４０】
本明細書で論じられる本発明の例示的実施形態は、動作を実行するために機械（あるいはコンピュータまたはプロセッサ）によって実行可能な命令のプログラム（たとえば、プログラム、コンピュータ・プログラム、プログラム・コード、プログラム命令）を有形に具体化する（たとえば記憶する）、（たとえば、機械によって、コンピュータによって、プロセッサによって）読み取り可能な、プログラム・ストレージ・デバイス（たとえば、少なくとも１つのメモリ、少なくとも１つのコンピュータ読み取り可能記憶媒体）と関連して実装可能である。動作は、本発明の例示的実施形態を使用する（たとえば実施する）ステップ、または方法のステップを含む。
【０１４１】
さらに、図８〜図１２に示されたブロックは、１つまたは複数の構成要素、回路、チップ、装置、プロセッサ、コンピュータ・プログラム、または機能ブロック、あるいはそれらすべてによって実行される、１つまたは複数の機能または動作あるいはその両方に対応するものとみなすことができる。上記のいずれかまたはすべてあるいはその両方は、本明細書で説明された本発明の例示的実施形態に従って動作を実行可能にする、任意の実施可能なソリューションまたは配置構成内に実装可能である。
【０１４２】
加えて、図８〜図１２に示されたブロックの配置構成は単なる例であり、非限定的であるものとみなすべきである。図８〜図１２に示されたブロックは、本発明の例示的実施形態のうちの１つまたは複数を実装するように、任意の（たとえば任意の好適な、実施可能な、または実現可能な、あるいはそれらすべての）順序で、または同時に（たとえば好適な、実施可能な、または実現可能なように、あるいはそれらすべてのように）、あるいはその両方で、実行可能な、１つまたは複数の機能または動作あるいはその両方に対応可能であることを理解されたい。加えて、本発明の１つまたは複数の他の例示的実施形態を実装するように、１つまたは複数の追加の機能、動作、またはステップ、あるいはそれらすべてを、図８〜図１２に示されたそれらに関連して使用することができる。
【０１４３】
すなわち、図８〜図１２に示された本発明の例示的実施形態は、任意の組み合わせ（たとえば、好適な、実施可能な、または実現可能な、あるいはそれらすべての任意の組み合わせ）で、１つまたは複数の他の態様に関連して使用、実装、または実施可能であり、図８〜図１２に示されたステップ、ブロック、動作、または機能、あるいはそれらすべてにのみ限定されるものではない。
【０１４４】
図８〜図１２の流れ図およびブロック図は、本発明の様々な例示的実施形態に従った、システム、方法、およびコンピュータ・プログラム製品の、可能な例示的実装のアーキテクチャ、機能性、および動作を示すものである。この点で、流れ図またはブロック図内の各ブロックは、指定された論理機能を実装するための１つまたは複数の実行可能命令を含む、コードのモジュール、セグメント、または一部を表すことができる。いくつかの代替の実装では、ブロック内に示された機能は、図に示された順序とは異なる順序で発生可能であることにも留意されたい。たとえば、連続して示される２つのブロックは、関連する機能性に応じて、実際にはほぼ同時に実行されるか、または時には逆の順序で実行されることが可能である。ブロック図または流れ図あるいはその両方の各ブロック、および、ブロック図または流れ図あるいはその両方におけるブロックの組み合わせは、非限定的な例として、指定された機能または行為を実行する特定用途向けハードウェアベースのシステム、あるいは、特定用途向けのハードウェアおよびコンピュータ命令の組み合わせによって実装可能であることにも留意されたい。
【０１４５】
さらに、本明細書で説明されたパラメータ、動作、および機能に使用される様々な名前は、これらのパラメータ、動作、および機能が任意の好適な名前によって識別可能な場合、いかなる点においても限定されることを意図するものではない。
【０１４６】
本明細書で説明された任意およびすべての手段またはステップならびに機能要素の対応する構造、材料、行為、および等価物は、具体的に請求された場合に他の請求要素と組み合わせて機能を実行するための、任意の構造、材料、または行為を含むことが意図される。本発明の例示的実施形態の説明は、例示および説明の目的で提示されており、本発明の開示された形を網羅するかまたはこれらに限定されることは意図されていない。当業者であれば、本発明の範囲および趣旨を逸脱することなく、多くの修正および変形が明らかとなろう。例示的実施形態は、本発明の例示的実施形態の原理および実際の適用例を最も良く説明するため、ならびに、他の当業者が、企図された特定用途に好適な様々な修正を伴う様々な例示的実施形態に関して本発明を理解できるようにするために、選択および説明されたものである。
【０１４７】
当業者であれば理解されるように、本発明の例示的実施形態の態様は、非限定的な例として、システム、方法、またはコンピュータ・プログラム製品として具体化することが可能である。したがって、本発明の例示的実施形態の態様は、非限定的な例として、全体がハードウェア実施形態、全体がソフトウェア実施形態（ファームウェア、常駐ソフトウェア、マイクロコードなどを含む）、あるいは、本明細書ではすべて一般に「回路」、「モジュール」、または「システム」と呼ばれるソフトウェアとハードウェアの態様を組み合わせた実施形態の、形を取ることができる。さらに、本発明の例示的実施形態の態様は、その上にコンピュータ読み取り可能プログラム・コードが具体化された、１つまたは複数のコンピュータ読み取り可能媒体内に具体化された、コンピュータ・プログラム製品の形を取ることができる。
【０１４８】
１つまたは複数のコンピュータ読み取り可能媒体の任意の組み合わせが使用可能である。コンピュータ読み取り可能媒体は、コンピュータ読み取り可能信号媒体またはコンピュータ読み取り可能記憶媒体とすることができる。非限定的な例として、コンピュータ読み取り可能記憶媒体は、電子、磁気、光、電磁、赤外線、または半導体のシステム、装置、またはデバイス、あるいはそれらの任意の好適な組み合わせのうちの、１つまたは複数を含むことができる。コンピュータ読み取り可能記憶媒体のさらに特定の非限定的な例は、１本または複数本のワイヤを有する電気接続、ポータブル・コンピュータ・ディスケット、ハード・ディスク、ランダム・アクセス・メモリ（ＲＡＭ）、読み取り専用メモリ（ＲＯＭ）、消去可能プログラマブル読み取り専用メモリ（ＥＰＲＯＭまたはフラッシュ・メモリ）、光ファイバ、ポータブル・コンパクト・ディスク読み取り専用メモリ（ＣＤ−ＲＯＭ）、光ストレージ・デバイス、磁気ストレージ・デバイス、または、それらの任意の好適な組み合わせを含む。本書との関連において、コンピュータ読み取り可能記憶媒体は、命令実行システム、装置、またはデバイス（たとえばコンピュータまたはプロセッサ）によって、あるいはそれらに関連して使用するための、プログラムを含むかまたは記憶するように構成／動作可能な、任意の有形媒体とすることができる。
【０１４９】
コンピュータ読み取り可能信号媒体は、たとえばベースバンド内に、または搬送波の一部として、内部にコンピュータ読み取り可能プログラム・コードが具体化された、伝搬データ信号を含むことができる。こうした伝搬信号は、電磁、光、またはそれらの任意の好適な組み合わせを含むがこれらに限定されない、任意の様々な形を取ることができる。コンピュータ読み取り可能信号媒体は、コンピュータ読み取り可能記憶媒体ではなく、命令実行システム、装置、またはデバイスによって、あるいはそれらに関連して使用するためのプログラムの通信、伝搬、または移送が可能な、任意のコンピュータ読み取り可能媒体とすることができる。
【０１５０】
コンピュータ読み取り可能媒体上に具体化されたプログラム・コードは、ワイヤレス、ワイヤライン、ワイヤード、光ファイバ・ケーブル、ＲＦ、またはそれらの任意の好適な組み合わせを含むがこれらに限定されない、任意の適切な媒体を使用して伝送することができる。
【０１５１】
本発明の例示的実施形態の態様に関する動作を実施するためのコンピュータ・プログラム・コードは、非限定的な例として、Ｊａｖａ、Ｓｍａｌｌｔａｌｋ、またはＣ＋＋などのオブジェクト指向プログラミング言語、および、「Ｃ」プログラミング言語または同様のプログラミング言語などの従来の手続き型プログラミング言語を含む、１つまたは複数のプログラミング言語の任意の組み合わせで作成可能である。プログラム・コードは、非限定的な例として、全体がユーザのコンピュータ上で、一部がユーザのコンピュータ上で、スタンドアロン型ソフトウェア・パッケージとして、一部がユーザのコンピュータ上および一部がリモート・コンピュータ上で、あるいは、全体がリモート・コンピュータまたはサーバ上で、実行可能である。後者のシナリオでは、リモート・コンピュータは、非限定的な例として、ローカル・エリア・ネットワーク（ＬＡＮ）またはワイド・エリア・ネットワーク（ＷＡＮ）を含む、任意のタイプのネットワークを介して、ユーザのコンピュータに接続することができるか、あるいは、（たとえば、インターネット・サービス・プロバイダを使用してインターネットを介して）外部コンピュータに接続することができる。
【０１５２】
本明細書では、本発明の様々な例示的実施形態に従った方法、装置（システム）、およびコンピュータ・プログラム製品の、流れ図またはブロック図あるいはその両方を参照しながら、本発明の例示的実施形態の態様について説明される。流れ図またはブロック図あるいはその両方の各ブロック、および流れ図またはブロック図あるいはその両方におけるブロックの組み合わせは、非限定的な例として、コンピュータ・プログラム命令によって実装可能であることを理解されよう。これらのコンピュータ・プログラム命令は、非限定的な例として、コンピュータまたは他のプログラマブル・データ処理装置のプロセッサを介して実行する命令が、流れ図またはブロック図あるいはその両方のブロック内に指定された機能／行為を実装するための手段を作成するように、機械を生成するために汎用コンピュータ、特定用途向けコンピュータ、または他のプログラマブル・データ処理装置のプロセッサに提供可能である。
【０１５３】
コンピュータ、他のプログラマブル・データ処理装置、または他のデバイスに、特定の様式で機能するよう指示可能な、これらのコンピュータ・プログラム命令は、コンピュータ読み取り可能媒体内に記憶された命令が、流れ図またはブロック図あるいはその両方のブロック内に指定された機能／行為を実装する命令を含む製品を製造するように、コンピュータ読み取り可能媒体内に記憶することも可能である。
【０１５４】
コンピュータ・プログラム命令は、コンピュータまたは他のプログラマブル装置上で実行する命令が、流れ図またはブロック図あるいはその両方のブロック内に指定された機能／行為（たとえば、本発明の例示的実施形態）を実装するためのプロセスを提供するような、コンピュータ実装プロセスを生成するために、一連の動作ステップを、コンピュータ、他のプログラマブル・データ処理装置、または他のデバイス上で実行させるために、コンピュータ、他のプログラマブル・データ処理装置、または他のデバイス上にロードすることも可能である。
【０１５５】
「接続された」、「結合された」、またはそれらの変形の用語のいずれの使用も、識別された要素間での、直接または間接的な、任意のこうした接続または結合を示すものと解釈されるべきである。非限定的な例として、１つまたは複数の中間要素が「結合された」要素間に存在可能である。識別された要素間の接続または結合は、非限定的な例として、説明された例示的実施形態に従い、物理的、電気的、磁気的、論理的、またはそれらの任意の好適な組み合わせとすることができる。非限定的な例として、接続または結合は、１つまたは複数のプリントされた電気接続、ワイヤ、ケーブル、媒体、またはそれらの任意の好適な組み合わせを含むことができる。
【０１５６】
一般に、本発明の様々な例示的実施形態は、ソフトウェア、ハードウェア、論理、特定用途向け回路、またはそれらの任意の組み合わせなどの、異なる媒体内で実装可能である。非限定的な例として、いくつかの態様はコンピューティング・デバイス上で実行可能なソフトウェア内に実装可能である一方で、他の態様はハードウェア内に実装可能である。
【０１５７】
前述の説明では、例示的かつ非限定的な例を用いて、本発明を実施するために発明者等によって現在企図されている最良の方法および装置の完全かつ有益な説明を提供してきた。しかしながら、当業者であれば、添付の図面および添付の特許請求の範囲に関連して前述の説明を読めば、これらに照らした修正および適合が明らかとなろう。しかしながら、すべてのこうした修正および同様の修正は、依然として本発明の例示的実施形態の教示の範囲内にあることになる。
【０１５８】
さらに、本発明の好ましい実施形態のいくつかの特徴は、対応する他の特徴を使用することなく、利益を得るために使用することができる。したがって前述の説明は、本発明の原理を限定するのではなく、単に例示するものとみなすことができる。
【図１】
2013524277.tif 000195
【図２】
2013524277.tif 000196
【図３】
2013524277.tif 000197
【図４】
2013524277.tif 000198
【図５】
2013524277.tif 000199
【図６】
2013524277.tif 000200
【図７】
2013524277.tif 000201
【図８】
2013524277.tif 000202
【図９】
2013524277.tif 000203
【図１０】
2013524277.tif 000204
【図１１】
2013524277.tif 000205
【図１２】
2013524277.tif 000206
2013524277.tif 000207
2013524277.tif 000208
2013524277.tif 000209
2013524277.tif 000210
2013524277.tif 000211
2013524277.tif 000212
2013524277.tif 000213
2013524277.tif 000214
【国際調査報告】
2013524277.tif 000215