暗号処理システム、暗号処理方法、暗号処理プログラム及び鍵生成装置
【課題】公開パラメータやマスター秘密鍵のサイズを小さくするとともに、ユーザへ与える秘密鍵の生成の処理や暗号化の処理にかかる時間を短くすることを目的とする。
【解決手段】鍵生成装置１００は、各行各列に少なくとも１つは０以外の値を有する疎行列を用いて、公開パラメータやマスター秘密鍵となる基底Ｂと基底Ｂ＊とを生成する。暗号化装置２００は、基底Ｂにおけるベクトルであって、所定の情報を埋め込んだベクトルを暗号ベクトルとして生成し、復号装置３００は、基底Ｂ＊における所定のベクトルを鍵ベクトルとして、暗号ベクトルと鍵ベクトルとについてペアリング演算を行い暗号ベクトルを復号する。
【解決手段】鍵生成装置１００は、各行各列に少なくとも１つは０以外の値を有する疎行列を用いて、公開パラメータやマスター秘密鍵となる基底Ｂと基底Ｂ＊とを生成する。暗号化装置２００は、基底Ｂにおけるベクトルであって、所定の情報を埋め込んだベクトルを暗号ベクトルとして生成し、復号装置３００は、基底Ｂ＊における所定のベクトルを鍵ベクトルとして、暗号ベクトルと鍵ベクトルとについてペアリング演算を行い暗号ベクトルを復号する。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、内積暗号（Ｉｎｎｅｒ−Ｐｒｏｄｕｃｔ Ｅｎｃｒｙｐｔｉｏｎ，ＩＰＥ）に関するものである。
【背景技術】
【０００２】
非特許文献１３，１６，１７には内積暗号についての記載がある。
非特許文献１３，１６，１７に記載された内積暗号では、公開パラメータやマスター秘密鍵は、ベクトル空間の基底で与えられる。
【先行技術文献】
【非特許文献】
【０００３】
【非特許文献１】Ａｂｄａｌｌａ，Ｍ．， Ｋｉｌｔｚ， Ｅ．， Ｎｅｖｅｎ，Ｇ．： Ｇｅｎｅｒａｌｉｚｅｄ ｋｅｙ ｄｅｌｅｇａｔｉｏｎ ｆｏｒ ｈｉｅｒａｒｃｈｉｃａｌ ｉｄｅｎｔｉｔｙ−ｂａｓｅｄ ｅｎｃｒｙｐｔｉｏｎ． ＥＳＯＲＩＣＳ’０７， ＬＮＣＳ ４７３４， ｐｐ． １３９−１５４． Ｓｐｒｉｎｇｅｒ， （２００７）
【非特許文献２】Ａｔｔｒａｐａｄｕｎｇ， Ｎ．， Ｌｉｂｅｒｔ， Ｂ．： Ｆｕｎｃｔｉｏｎａｌ ｅｎｃｒｙｐｔｉｏｎ ｆｏｒ ｉｎｎｅｒ ｐｒｏｄｕｃｔ： Ａｃｈｉｅｖｉｎｇ ｃｏｎｓｔａｎｔ−ｓｉｚｅ ｃｉｐｈｅｒｔｅｘｔｓ ｗｉｔｈ ａｄａｐｔｉｖｅ ｓｅｃｕｒｉｔｙ ｏｒ ｓｕｐｐｏｒｔ ｆｏｒ ｎｅｇａｔｉｏｎ． ＰＫＣ ２０１０． ＬＮＣＳ， ｖｏｌ． ６０５６， ｐｐ． ３８４−４０２． Ｓｐｒｉｎｇｅｒ Ｈｅｉｄｅｌｂｅｒｇ （２０１０）
【非特許文献３】Ａｔｔｒａｐａｄｕｎｇ， Ｎ．， Ｌｉｂｅｒｔ， Ｂ．， Ｄｅ Ｐａｎａｆｉｅｕ， Ｅ．： Ｅｘｐｒｅｓｓｉｖｅ ｋｅｙ−ｐｏｌｉｃｙ ａｔｔｒｉｂｕｔｅ−ｂａｓｅｄ ｅｎｃｒｙｐｔｉｏｎ ｗｉｔｈ ｃｏｎｓｔａｎｔ−ｓｉｚｅ ｃｉｐｈｅｒｔｅｘｔｓ． ＰＫＣ ２０１１． ＬＮＣＳ， ｖｏｌ． ６５７１， ｐｐ． ９０−１０８． Ｓｐｒｉｎｇｅｒ Ｈｅｉｄｅｌｂｅｒｇ （２０１１）
【非特許文献４】Ｂｅｔｈｅｎｃｏｕｒｔ， Ｊ．， Ｓａｈａｉ， Ａ．，Ｗａｔｅｒｓ， Ｂ．： Ｃｉｐｈｅｒｔｅｘｔ−ｐｏｌｉｃｙ ａｔｔｒｉｂｕｔｅ−ｂａｓｅｄ ｅｎｃｒｙｐｔｉｏｎ． Ｉｎ：２００７ ＩＥＥＥ Ｓｙｍｐｏｓｉｕｍ ｏｎ Ｓｅｃｕｒｉｔｙ ａｎｄ Ｐｒｉｖａｃｙ， ｐｐ． ３２１−３３４． ＩＥＥＥ Ｐｒｅｓｓ （２００７）
【非特許文献５】Ｂｏｎｅｈ， Ｄ．， Ｈａｍｂｕｒｇ， Ｍ．： Ｇｅｎｅｒａｌｉｚｅｄ ｉｄｅｎｔｉｔｙ ｂａｓｅｄ ａｎｄ ｂｒｏａｄｃａｓｔ ｅｎｃｒｙｐｔｉｏｎ ｓｃｈｅｍｅ． Ｉｎ：Ｐｉｅｐｒｚｙｋ， Ｊ． （ｅｄ．） ＡＳＩＡＣＲＹＰＴ ２００８． ＬＮＣＳ， ｖｏｌ． ５３５０， ｐｐ． ４５５−４７０． Ｓｐｒｉｎｇｅｒ Ｈｅｉｄｅｌｂｅｒｇ （２００８）
【非特許文献６】Ｄｅｌｅｒａｂｌｅｅ， Ｃ．： Ｉｄｅｎｔｉｔｙ−ｂａｓｅｄ ｂｒｏａｄｃａｓｔ ｅｎｃｒｙｐｔｉｏｎ ｗｉｔｈ ｃｏｎｓｔａｎｔ ｓｉｚｅ ｃｉｐｈｅｒｔｅｘｔｓ ａｎｄ ｐｒｉｖａｔｅ ｋｅｙｓ． Ｉｎ： ＡＳＩＡＣＲＹＰＴ ２００７， ＬＮＣＳ， ｐｐ． ２００−２１５． Ｓｐｒｉｎｇｅｒ−Ｖｅｒｌａｇ （２００７）
【非特許文献７】Ｅｍｕｒａ， Ｋ．， Ｍｉｙａｊｉ， Ａ．， Ｎｏｍｕｒａ， Ａ．， Ｏｍｏｔｅ， Ｋ．， Ｓｏｓｈｉ， Ｍ．： Ａ ｃｉｐｈｅｒｔｅｘｔ−ｐｏｌｉｃｙ ａｔｔｒｉｂｕｔｅ−ｂａｓｅｄ ｅｎｃｒｙｐｔｉｏｎ ｓｃｈｅｍｅ ｗｉｔｈ ｃｏｎｓｔａｎｔ ｃｉｐｈｅｒｔｅｘｔ ｌｅｎｇｔｈ． Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ＩＳＰＥＣ ２００９， ＬＮＣＳ， ｐｐ． １３−２３． Ｓｐｒｉｎｇｅｒ−Ｖｅｒｌａｇ （２００９）
【非特許文献８】Ｇｅｎｔｒｙ， Ｃ．， Ｗａｔｅｒｓ， Ｂ．： Ａｄａｐｔｉｖｅ ｓｅｃｕｒｉｔｙ ｉｎ ｂｒｏａｄｃａｓｔ ｅｎｃｒｙｐｔｉｏｎ ｓｙｓｔｅｍｓ （ｗｉｔｈ ｓｈｏｒｔ ｃｉｐｈｅｒｔｅｘｔｓ）． Ｉｎ： Ｊｏｕｘ， Ａ． （ｅｄ．） ＥＵＲＯＣＲＹＰＴ ２００９． ＬＮＣＳ， ｖｏｌ． ５４７９， ｐｐ． １７１−１８８． Ｓｐｒｉｎｇｅｒ Ｈｅｉｄｅｌｂｅｒｇ （２００９）
【非特許文献９】Ｇｏｙａｌ， Ｖ．， Ｐａｎｄｅｙ， Ｏ．， Ｓａｈａｉ， Ａ．， Ｗａｔｅｒｓ， Ｂ．： Ａｔｔｒｉｂｕｔｅ−ｂａｓｅｄ ｅｎｃｒｙｐｔｉｏｎ ｆｏｒ ｆｉｎｅ−ｇｒａｉｎｅｄ ａｃｃｅｓｓ ｃｏｎｔｒｏｌ ｏｆ ｅｎｃｒｙｐｔｅｄ ｄａｔａ． Ｉｎ： ＡＣＭ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｃｏｍｐｕｔｅｒ ａｎｄ Ｃｏｍｍｕｎｉｃａｔｉｏｎ Ｓｅｃｕｒｉｔｙ ２００６， ｐｐ． ８９−９８， ＡＣＭ （２００６）
【非特許文献１０】Ｈｅｒｒａｎｚ， Ｊ．， Ｌａｇｕｉｌｌａｕｍｉｅ， Ｆ．， Ｒａｆｏｌｓ， Ｃ．： Ｃｏｎｓｔａｎｔ ｓｉｚｅ ｃｉｐｈｅｒｔｅｘｔｓ ｉｎ ｔｈｅｒｅｓｈｏｌｄ ａｔｔｒｉｂｕｔｅ−ｂａｓｅｄ ｅｎｃｒｙｐｔｉｏｎ， Ｉｎ Ｎｇｕｙｅｎ， Ｐ．Ｑ．， Ｐｏｉｎｔｃｈｅｖａｌ， Ｄ． （ｅｄｓ．） ＰＫＣ ２０１０． ＬＮＣＳ， ｖｏｌ． ６０５６， ｐｐ． １９−３４． Ｓｐｒｉｎｇｅｒ Ｈｅｉｄｅｌｂｅｒｇ （２０１０）
【非特許文献１１】Ｋａｔｚ， Ｊ．， Ｓａｈａｉ， Ａ．， Ｗａｔｅｒｓ， Ｂ．： Ｐｒｅｄｉｃａｔｅ ｅｎｃｒｙｐｔｉｏｎ ｓｕｐｐｏｒｔｉｎｇ ｄｉｓｊｕｎｃｔｉｏｎｓ， ｐｏｌｙｎｏｍｉａｌ ｅｑｕａｔｉｏｎｓ， ａｎｄ ｉｎｎｅｒ ｐｒｏｄｕｃｔｓ． Ｉｎ： Ｓｍａｒｔ， Ｎ．Ｐ． （ｅｄ．） ＥＵＲＯＣＲＹＰＴ ２００８． ＬＮＣＳ， ｖｏｌ． ４９６５， ｐｐ． １４６−１６２． Ｓｐｒｉｎｇｅｒ Ｈｅｉｄｅｌｂｅｒｇ （２００８）
【非特許文献１２】Ｌｅｗｋｏ， Ａ．， Ｓａｈａｉ， Ａ．， Ｗａｔｅｒｓ， Ｂ．： Ｒｅｖｏｃａｔｉｏｎ ｓｙｓｔｅｍｓ ｗｉｔｈ ｖｅｒｙ ｓｍａｌｌ ｐｒｉｖａｔｅ ｋｅｙｓ， Ｉｎ ＩＥＥＥ Ｓｙｍｐｏｓｉｕｍ ｏｎ Ｓｅｃｕｒｉｔｙ ａｎｄ Ｐｒｉｖａｃｙ ２０１０ （２０１０）
【非特許文献１３】Ｌｅｗｋｏ， Ａ．， Ｏｋａｍｏｔｏ， Ｔ．， Ｓａｈａｉ， Ａ．， Ｔａｋａｓｈｉｍａ， Ｋ．， Ｗａｔｅｒｓ， Ｂ．： Ｆｕｌｌｙ ｓｅｃｕｒｅ ｆｕｎｃｔｉｏｎａｌ ｅｎｃｒｙｐｔｉｏｎ： Ａｔｔｒｉｂｕｔｅ−ｂａｓｅｄ ｅｎｃｒｙｐｔｉｏｎ ａｎｄ （ｈｉｅｒａｒｃｈｉｃａｌ） ｉｎｎｅｒ ｐｒｏｄｕｃｔ ｅｎｃｒｙｐｔｉｏｎ， ＥＵＲＯＣＲＹＰＴ ２０１０． ＬＮＣＳ， Ｓｐｒｉｎｇｅｒ Ｈｅｉｄｅｌｂｅｒｇ （２０１０） Ｆｕｌｌ ｖｅｒｓｉｏｎ ｉｓ ａｖａｉｌａｂｌｅ ａｔ ｈｔｔｐ：／／ｅｐｒｉｎｔ．ｉａｃｒ．ｏｒｇ／２０１０／１１０
【非特許文献１４】Ｌｅｗｋｏ， Ａ．Ｂ．， Ｗａｔｅｒｓ， Ｂ．： Ｎｅｗ ｔｅｃｈｎｉｑｕｅｓ ｆｏｒ ｄｕａｌ ｓｙｓｔｅｍ ｅｎｃｒｙｐｔｉｏｎ ａｎｄ ｆｕｌｌｙ ｓｅｃｕｒｅ ＨＩＢＥ ｗｉｔｈ ｓｈｏｒｔ ｃｉｐｈｅｒｔｅｘｔｓ． Ｉｎ： Ｍｉｃｃｉａｎｃｉｏ， Ｄ． （ｅｄ．） ＴＣＣ ２０１０． ＬＮＣＳ， ｖｏｌ． ５９７８， ｐｐ． ４５５−４７９． Ｓｐｒｉｎｇｅｒ Ｈｅｉｄｅｌｂｅｒｇ （２０１０）
【非特許文献１５】Ｏｋａｍｏｔｏ， Ｔ．， Ｔａｋａｓｈｉｍａ， Ｋ．： Ｈｏｍｏｍｏｒｐｈｉｃ ｅｎｃｒｙｐｔｉｏｎ ａｎｄ ｓｉｇｎａｔｕｒｅｓ ｆｒｏｍ ｖｅｃｔｏｒ ｄｅｃｏｍｐｏｓｉｔｉｏｎ． Ｉｎ： Ｇａｌｂｒａｉｔｈ， Ｓ．Ｄ．， Ｐａｔｅｒｓｏｎ， Ｋ．Ｇ． （ｅｄｓ．） Ｐａｉｒｉｎｇ ２００８． ＬＮＣＳ， ｖｏｌ． ５２０９， ｐｐ． ５７−７４， Ｓｐｒｉｎｇｅｒ Ｈｅｉｄｅｌｂｅｒｇ （２００８）
【非特許文献１６】Ｏｋａｍｏｔｏ， Ｔ．， Ｔａｋａｓｈｉｍａ， Ｋ．： Ｈｉｅｒａｒｃｈｉｃａｌ ｐｒｅｄｉｃａｔｅ ｅｎｃｒｙｐｔｉｏｎ ｆｏｒ ｉｎｎｅｒ−ｐｒｏｄｕｃｔｓ， Ｉｎ： Ｍａｔｓｕｉ， Ｍ． （ｅｄ．） ＡＳＩＡＣＲＹＰＴ ２００９． ＬＮＣＳ， ｖｏｌ． ５９１２， ｐｐ． ２１４−２３１． Ｓｐｒｉｎｇｅｒ Ｈｅｉｄｅｌｂｅｒｇ （２００９）
【非特許文献１７】Ｏｋａｍｏｔｏ， Ｔ．， Ｔａｋａｓｈｉｍａ， Ｋ．： Ｆｕｌｌｙ ｓｅｃｕｒｅ ｆｕｎｃｔｉｏｎａｌ ｅｎｃｒｙｐｔｉｏｎ ｗｉｔｈ ｇｅｎｅｒａｌ ｒｅｌａｔｉｏｎｓ ｆｒｏｍ ｔｈｅ ｄｅｃｉｓｉｏｎａｌ ｌｉｎｅａｒ ａｓｓｕｍｐｔｉｏｎ． Ｉｎ： Ｒａｂｉｎ， Ｔ． （ｅｄ．） ＣＲＹＰＴＯ ２０１０． ＬＮＣＳ， ｖｏｌ． ６２２３， ｐｐ． １９１−２０８． Ｓｐｒｉｎｇｅｒ Ｈｅｉｄｅｌｂｅｒｇ （２０１０）． Ｆｕｌｌ ｖｅｒｓｉｏｎ ｉｓ ａｖａｉｌａｂｌｅ ａｔ ｈｔｔｐ：／／ｅｐｒｉｎｔ．ｉａｃｒ．ｏｒｇ／２０１０／５６３
【非特許文献１８】Ｓａｈａｉ， Ａ．， Ｗａｔｅｒｓ， Ｂ．： Ｆｕｚｚｙ ｉｄｅｎｔｉｔｙ−ｂａｓｅｄ ｅｎｃｒｙｐｔｉｏｎ． Ｉｎ： Ｃｒａｍｅｒ， Ｒ． （ｅｄ．） ＥＵＲＯＣＲＹＰＴ ２００５． ＬＮＣＳ， ｖｏｌ． ３４９４， ｐｐ． ４５７−４７３． Ｓｐｒｉｎｇｅｒ Ｈｅｉｄｅｌｂｅｒｇ （２００５）
【非特許文献１９】Ｓａｋａｉ， Ｒ．， Ｆｕｒｕｋａｗａ， Ｊ．： Ｉｄｅｎｔｉｔｙ−ｂａｓｅｄ ｂｒｏａｄｃａｓｔ ｅｎｃｒｙｐｔｉｏｎ， ＩＡＣＲ ｅＰｒｉｎｔ Ａｒｃｈｉｖｅ： Ｒｅｐｏｒｔ ２００７／２１７ ｈｔｔｐ：／／ｅｐｒｉｎｔ．ｉａｃｒ．ｏｒｇ／２００７／２１７ （２００７）．
【非特許文献２０】Ｗａｔｅｒｓ， Ｂ．： Ｄｕａｌ ｓｙｓｔｅｍ ｅｎｃｒｙｐｔｉｏｎ： ｒｅａｌｉｚｉｎｇ ｆｕｌｌｙ ｓｅｃｕｒｅ ＩＢＥ ａｎｄ ＨＩＢＥ ｕｎｄｅｒ ｓｉｍｐｌｅ ａｓｓｕｍｐｔｉｏｎｓ． Ｉｎ： Ｈａｌｅｖｉ， Ｓ． （ｅｄ．） ＣＲＹＰＴＯ ２００９． ＬＮＣＳ， ｖｏｌ． ５６７７， ｐｐ． ６１９−６３６． Ｓｐｒｉｎｇｅｒ Ｈｅｉｄｅｌｂｅｒｇ （２００９）
【発明の概要】
【発明が解決しようとする課題】
【０００４】
非特許文献１３，１６，１７に記載された内積暗号では、内積暗号に用いるベクトルの長さをＮとすると、公開パラメータやマスター秘密鍵のサイズはＮ２に比例し、ユーザへ与える秘密鍵の生成や暗号化の処理にＮ２に比例する時間がかかる。
この発明は、公開パラメータやマスター秘密鍵のサイズを小さくするとともに、ユーザへ与える秘密鍵の生成の処理や暗号化の処理にかかる時間を短くすることを目的とする。
【課題を解決するための手段】
【０００５】
この発明に係る暗号処理システムは、
各行各列に少なくとも１つは０以外の値を有する疎行列を用いて所定の基底Ａを変形して生成された基底Ｂと基底Ｂ＊を利用し、暗号処理を行う暗号処理システムであり、
前記基底Ｂにおけるベクトルであって、所定の情報を埋め込んだベクトルを暗号ベクトルとして生成する暗号化装置と、
前記基底Ｂ＊における所定のベクトルを鍵ベクトルとして、前記暗号化装置が生成した暗号ベクトルと前記鍵ベクトルとについて、ペアリング演算を行い前記暗号ベクトルを復号して前記所定の情報に関する情報を抽出する復号装置と
を備えることを特徴とする。
【発明の効果】
【０００６】
この発明に係る暗号処理システムでは、公開パラメータやマスター秘密鍵となる基底Ｂと基底Ｂ＊とを生成するために用いる行列に疎行列を用いる。これにより、公開パラメータやマスター秘密鍵のサイズが小さくなるとともに、ユーザへ与える秘密鍵の生成の処理や暗号化の処理にかかる時間が短くなる。
【図面の簡単な説明】
【０００７】
【図１】零内積暗号方式と非零内積暗号方式とを実行する暗号処理システム１０の構成図。
【図２】ランダムな線形変換Ｘの特別な形式の説明図。
【図３】実施の形態２に係る鍵生成装置１００の構成図。
【図４】実施の形態２に係る暗号化装置２００の構成図。
【図５】実施の形態２に係る復号装置３００の構成図。
【図６】実施の形態２に係るＳｅｔｕｐアルゴリズムの処理を示すフローチャート。
【図７】実施の形態２に係るＫｅｙＧｅｎアルゴリズムの処理を示すフローチャート。
【図８】実施の形態２に係るＥｎｃアルゴリズムの処理を示すフローチャート。
【図９】実施の形態２に係るＤｅｃアルゴリズムの処理を示すフローチャート。
【図１０】実施の形態３に係るＳｅｔｕｐアルゴリズムの処理を示すフローチャート。
【図１１】実施の形態３に係るＫｅｙＧｅｎアルゴリズムの処理を示すフローチャート。
【図１２】実施の形態３に係るＥｎｃアルゴリズムの処理を示すフローチャート。
【図１３】実施の形態３に係るＤｅｃアルゴリズムの処理を示すフローチャート。
【図１４】実施の形態４に係るＳｅｔｕｐアルゴリズムの処理を示すフローチャート。
【図１５】実施の形態４に係るＫｅｙＧｅｎアルゴリズムの処理を示すフローチャート。
【図１６】実施の形態４に係るＥｎｃアルゴリズムの処理を示すフローチャート。
【図１７】実施の形態４に係るＤｅｃアルゴリズムの処理を示すフローチャート。
【図１８】実施の形態５に係るＳｅｔｕｐアルゴリズムの処理を示すフローチャート。
【図１９】実施の形態５に係るＫｅｙＧｅｎアルゴリズムの処理を示すフローチャート。
【図２０】実施の形態５に係るＥｎｃアルゴリズムの処理を示すフローチャート。
【図２１】実施の形態５に係るＤｅｃアルゴリズムの処理を示すフローチャート。
【図２２】実施の形態２−４で説明した非零内積暗号方式及び零内積暗号方式と、非特許文献２に記載された非零内積暗号方式及び零内積暗号方式とを比較した図。
【図２３】鍵生成装置１００、暗号化装置２００、復号装置３００、鍵委譲装置４００のハードウェア構成の一例を示す図。
【発明を実施するための形態】
【０００８】
以下、図に基づき、発明の実施の形態を説明する。
以下の説明において、処理装置は後述するＣＰＵ９１１等である。記憶装置は後述するＲＯＭ９１３、ＲＡＭ９１４、磁気ディスク９２０等である。通信装置は後述する通信ボード９１５等である。入力装置は後述するキーボード９０２、通信ボード９１５等である。出力装置は後述するＲＡＭ９１４、磁気ディスク９２０、通信ボード９１５、ＬＣＤ９０１等である。つまり、処理装置、記憶装置、通信装置、入力装置、出力装置はハードウェアである。
【０００９】
以下の説明における記法について説明する。
Ａがランダムな変数または分布であるとき、数１０１は、Ａの分布に従いＡからｙをランダムに選択することを表す。つまり、数１０１において、ｙは乱数である。
【数１０１】
Ａが集合であるとき、数１０２は、Ａからｙを一様に選択することを表す。つまり、数１０２において、ｙは一様乱数である。
【数１０２】
ベクトル表記は、位数ｑの有限体Ｆｑにおけるベクトル表示を表す。例えば、数１０３である。
【数１０３】
数１０４は、数１０５に示す２つのベクトルｘ→とｖ→との数１０６に示す内積を表す。
【数１０４】
【数１０５】
【数１０６】
ＸＴは、行列Ｘの転置行列を表す。
ｂｉ（ｉ＝１，．．．，ｎ）が空間Ｖのベクトルの要素であるとき、つまり、数１０７であるとき、数１０８は、数１０９によって生成される部分空間を表す。
【数１０７】
【数１０８】
【数１０９】
数１１０に示す基底Ｂと基底Ｂ＊とに対して、数１１１である。
【数１１０】
【数１１１】
ｊ＝１，．．．，ｎのｎ個のベクトルに対して、ｅ→ｊは、数１１２に示す標準基底ベクトルを示す。
【数１１２】
ＧＬ（ｎ，Ｆｑ）は、有限体Ｆｑにおける次数ｎの一般線形群を表す。
【００１０】
また、以下の説明において、ベクトルを意味する“→”が下付き文字又は上付き文字に付されている場合、この“→”は下付き文字又は上付き文字に上付きで付されていることを意味する。同様に、基底Ｂ＊における“＊”が下付き文字又は上付き文字に付されている場合、この“＊”は下付き文字又は上付き文字に上付きで付されていることを意味する。また、同様に、空間Ｖｔにおけるｔが下付き文字又は上付き文字に付されている場合、この“ｔ”は下付き文字又は上付き文字に下付きで付されていることを意味する。
【００１１】
また、以下の説明において、暗号処理とは、暗号化処理、復号処理、鍵生成処理を含むものである。
【００１２】
実施の形態１．
この実施の形態では、内積暗号を実現する基礎となる概念と、内積暗号の構成とについて説明する。
第１に、内積暗号の概念を説明する。
第２に、内積暗号を実現するための空間である双対ペアリングベクトル空間（Ｄｕａｌ Ｐａｉｒｉｎｇ Ｖｅｃｔｏｒ Ｓｐａｃｅｓ，ＤＰＶＳ）を説明する。
第３に、以下の実施の形態で説明する内積暗号方式の基本構成を説明する。
第４に、以下の実施の形態で説明する内積暗号方式を実行する暗号処理システム１０の基本構成を説明する。
第５に、以下の実施の形態で説明する内積暗号方式の基本的な考え方を説明する。
【００１３】
＜第１．内積暗号の概念＞
まず、関数型暗号（Ｆｕｎｃｔｉｏｎａｌ Ｅｎｃｒｙｐｔｉｏｎ）について説明する。
関数型暗号は、進歩した暗号の概念である。また、関数型暗号は、公開鍵暗号（Ｐｕｂｌｉｃ−Ｋｅｙ Ｅｎｃｒｙｐｔｉｏｎ，ＰＫＥ）やＩＤベース暗号（Ｉｄｅｎｔｉｔｙ−Ｂａｓｅｄ Ｅｎｃｒｙｐｔｉｏｎ，ＩＢＥ）の一般化である。関数型暗号システムでは、暗号文を特定するパラメータｙにパラメータｘが適切に関連付けられているなら、受信者はパラメータｘに対応する秘密鍵を用いて暗号文を復号できる。つまり、復号には、ある関係Ｒ（（ｘ，ｙ）に対して成立する関係Ｒ）に対してＲ（ｘ，ｙ）＝１ことが必要である。
【００１４】
内積暗号は、関数型暗号の一種である。
内積暗号には、零内積暗号（Ｚｅｒｏ Ｉｎｎｅｒ Ｐｒｏｄｕｃｔ Ｅｎｃｒｙｐｔｉｏｎ，ＺＩＰＥ）と、非零内積暗号（Ｎｏｎ−ｚｅｒｏ Ｉｎｎｅｒ Ｐｒｏｄｕｃｔ Ｅｎｃｒｙｐｔｉｏｎ，ＮＩＰＥ）とがある。
【００１５】
零内積暗号では、ベクトルｘ→に対して暗号化された暗号文は、ｘ→・ｙ→＝０であるベクトルｙ→と関連付けられた秘密鍵で復号することができる。つまり、ｘ→・ｙ→＝０である場合に限り、ＲＺＩＰＥ（ｘ→，ｙ→）＝１であることが必要である。
【００１６】
非零内積暗号では、ベクトルｘ→に対して暗号化された暗号文は、ｘ→・ｙ→≠０であるベクトルｙ→と関連付けられた秘密鍵で復号することができる。つまり、ｘ→・ｙ→≠０である場合に限り、ＲＮＩＰＥ（ｘ→，ｙ→）＝１であることが必要である。
【００１７】
＜第２．双対ペアリングベクトル空間＞
まず、対称双線形ペアリング群（Ｓｙｍｍｅｔｒｉｃ Ｂｉｌｉｎｅａｒ Ｐａｉｒｉｎｇ Ｇｒｏｕｐｓ）について説明する。
対称双線形ペアリング群（ｑ，Ｇ，ＧＴ，ｇ，ｅ）は、素数ｑと、位数ｑの巡回加法群Ｇと、位数ｑの巡回乗法群ＧＴと、要素ｇ≠０∈Ｇと、多項式時間で計算可能な非退化双線形ペアリング（Ｎｏｎｄｅｇｅｎｅｒａｔｅ Ｂｉｌｉｎｅａｒ Ｐａｉｒｉｎｇ）ｅ：Ｇ×Ｇ→ＧＴとの組である。非退化双線形ペアリングは、ｅ（ｓｇ，ｔｇ）＝ｅ（ｇ，ｇ）ｓｔであり、ｅ（ｇ，ｇ）≠１である。
以下の説明において、Ｇｂｐｇを、１λを入力として、セキュリティパラメータをλとする双線形ペアリング群のパラメータｐａｒａｍＧ：＝（ｑ，Ｇ，ＧＴ，ｇ，ｅ）の値を出力するアルゴリズムとする。
【００１８】
次に、双対ペアリングベクトル空間について説明する。
双対ペアリングベクトル空間（ｑ，Ｖ，ＧＴ，Ａ，ｅ）は、対称双線形ペアリング群（ｐａｒａｍＧ：＝（ｑ，Ｇ，ＧＴ，ｇ，ｅ））の直積によって構成することができる。双対ペアリングベクトル空間（ｑ，Ｖ，ＧＴ，Ａ，ｅ）は、素数ｑ、数１１３に示す有限体Ｆｑ上のＮ次元ベクトル空間Ｖ、位数ｑの巡回群ＧＴ、空間Ｖの標準基底Ａ：＝（ａ１，．．．，ａＮ）の組であり、以下の演算（１）（２）を有する。ここで、ａｉは、数１１４に示す通りである。
【数１１３】
【数１１４】
【００１９】
演算（１）：非退化双線形ペアリング
空間Ｖにおけるペアリングは、数１１５によって定義される。
【数１１５】
これは、非退化双線形である。つまり、ｅ（ｓｘ，ｔｙ）＝ｅ（ｘ，ｙ）ｓｔであり、全てのｙ∈Ｖに対して、ｅ（ｘ，ｙ）＝１の場合、ｘ＝０である。また、全てのｉとｊとに対して、ｅ（ａｉ，ａｊ）＝ｅ（ｇ，ｇ）δｉ，ｊである（このδｉ，ｊはδｉ，ｊを意味する）。ここで、ｉ＝ｊであれば、δｉ，ｊ＝１であり、ｉ≠ｊであれば、δｉ，ｊ＝０である。また、ｅ（ｇ，ｇ）≠１∈ＧＴである。
【００２０】
演算（２）：標準写像
数１１６に示す空間Ｖにおける線形変換φｉ，ｊは、数１１７によって容易に実現することができる。
【数１１６】
【数１１７】
ここで、線形変換φｉ，ｊを標準写像と呼ぶ。
【００２１】
以下の説明において、Ｇｄｐｖｓを、１λ（λ∈自然数）、Ｎ∈自然数を入力として、セキュリティパラメータがλであり、Ｎ次元の空間Ｖとする双対ペアリングベクトル空間のパラメータｐａｒａｍＶ：＝（ｑ，Ｖ，ＧＴ，Ａ，ｅ）の値を出力するアルゴリズムとする。
【００２２】
なお、ここでは、上述した対称双線形ペアリング群により、双対ペアリングベクトル空間を構成した場合について説明する。非対称双線形ペアリング群により双対ペアリングベクトル空間を構成することも可能である。以下の説明を、非対称双線形ペアリング群により双対ペアリングベクトル空間を構成した場合に応用することは容易である。
【００２３】
＜第３．内積暗号方式の基本構成＞
まず、零内積暗号方式について説明する。
零内積暗号方式における関係ＲＺＩＰＥは、ベクトルｘ→∈Ｆｎｑ＼｛０→｝と、ベクトルｖ→∈Ｆｎｑ＼｛０→｝とにおいて定義される。そして、ｘ→・ｖ→＝０である場合に限り、関係ＲＺＩＰＥ（ｘ→，ｖ→）：＝１である。
同様に、非零内積暗号方式における関係ＲＮＩＰＥは、ベクトルｘ→∈Ｆｎｑ＼｛０→｝と、ベクトルｖ→∈Ｆｎｑ＼｛０→｝とにおいて定義される。そして、ｘ→・ｖ→≠０である場合に限り、関係ＲＮＩＰＥ（ｘ→，ｖ→）：＝１である。
【００２４】
零内積暗号方式と非零内積暗号方式とは、Ｓｅｔｕｐ、ＫｅｙＧｅｎ、Ｅｎｃ、Ｄｅｃの４つのアルゴリズムを備える。
（Ｓｅｔｕｐ）
Ｓｅｔｕｐアルゴリズムは、セキュリティパラメータλが入力され、公開パラメータｐｋと、マスター秘密鍵ｓｋとを出力する確率的アルゴリズムである。
（ＫｅｙＧｅｎ）
ＫｅｙＧｅｎアルゴリズムは、ベクトルｖ→と、公開パラメータｐｋと、マスター秘密鍵ｓｋとを入力として、復号鍵ｓｋｖ→を出力する確率的アルゴリズムである。
（Ｅｎｃ）
Ｅｎｃアルゴリズムは、メッセージｍと、ベクトルｘ→と、公開パラメータｐｋとを入力として、暗号文ｃｔｘ→を出力する確率的アルゴリズムである。
（Ｄｅｃ）
Ｄｅｃアルゴリズムは、ベクトルｘ→の下で暗号化された暗号文ｃｔｘ→と、ベクトルｖ→に対する復号鍵ｓｋｖ→と、公開パラメータｐｋとを入力として、メッセージｍ、又は、識別情報⊥を出力するアルゴリズムである。識別情報⊥は、復号できなかったことを示す情報である。
【００２５】
＜第４．暗号処理システム１０の基本構成＞
図１は、零内積暗号方式と非零内積暗号方式とを実行する暗号処理システム１０の構成図である。
鍵生成装置１００は、セキュリティパラメータλを入力としてＳｅｔｕｐアルゴリズムを実行して、公開パラメータｐｋとマスター秘密鍵ｓｋとを生成する。そして、鍵生成装置１００は、生成した公開パラメータｐｋを公開する。また、鍵生成装置１００は、ベクトルｖ→を入力としてＫｅｙＧｅｎアルゴリズムを実行して、復号鍵ｓｋｖ→を生成して復号装置３００へ秘密裡に配布する。
暗号化装置２００は、メッセージｍと、ベクトルｘ→と、公開パラメータｐｋとを入力としてＥｎｃアルゴリズムを実行して、暗号文ｃｔｘ→を生成する。暗号化装置２００は、生成した暗号文ｃｔｘ→を復号装置３００へ送信する。
復号装置３００は、公開パラメータｐｋと、復号鍵ｓｋｖ→と、暗号文ｃｔｘ→とを入力としてＤｅｃアルゴリズムを実行して、メッセージｍ’（＝ｍ）又は識別情報⊥を出力する。
【００２６】
＜第５．暗号方式の基本的な考え方＞
双対ペアリングベクトル空間を暗号処理に適用した典型的なアプリケーションでは、双対基底（又は正規直交基底）のペアである基底Ｂと基底Ｂ＊とが生成される。基底Ｂと基底Ｂ＊とは、ＧＬ（Ｎ，Ｆｑ）から一様に選択された、完全にランダムな線形変換Ｘ（基底変換行列）を用いて生成される。特に、基底Ｂと基底Ｂ＊とは、それぞれ、線形変換Ｘと、（Ｘ−１）Ｔとにより、標準基底Ａを変換して生成される。なお、Ｎは、ｓｐａｎ＜Ｂ＞とｓｐａｎ＜Ｂ＊＞との次元数である。
そして、双対ペアリングベクトル空間を暗号処理に適用した典型的なアプリケーションでは、基底Ｂの一部（Ｂ＾という）が公開パラメータとして用いられ、これに対応する基底Ｂ＊の一部（Ｂ＾＊という）が秘密鍵又はトラップドアとして用いられる。
【００２７】
以下の実施の形態で説明する内積暗号では、上述した完全にランダムな線形変換Ｘに代えて、Ｘ∈ＧＬ（Ｎ，Ｆｑ）であるランダムな線形変換Ｘの特別な形式を用いる。この特別な形式の線形変換Ｘにより、暗号文又は秘密鍵のサイズを小さくすることができるとともに、処理に時間のかかるペアリング演算の数を減らすことができる。
【００２８】
図２は、特別な形式の線形変換Ｘの説明図である。
図２（ａ）は、完全にランダムな線形変換Ｘを示し、図２（ｂ）は、特別な形式の線形変換Ｘを示す。図２（ａ）（ｂ）において、四角が示す部分は成分の値が０以外の乱数であることを示し、図２（ｂ）において、空白部分は成分の値が０であることを示している。また、図２（ｂ）において、斜線が入れられた四角が示す部分は成分の値が同じ値であることを示す。なお、ここでは、Ｎ＝５としている。
図２（ａ）に示すように、従来の線形変換Ｘは、Ｎ２（ここでは、５２＝２５）のサイズであった。これに対して、図２（ｂ）に示すように、以下の実施の形態で説明する内積暗号で用いる線形変換Ｘ（以下、新しい線形変換Ｘ）は、Ｎ＋１（ここでは、５＋１＝６）のサイズである。
【００２９】
上述したように、基底Ｂと基底Ｂ＊とは、線形変換Ｘを用いて標準基底Ａを変換して生成される。そのため、基底Ｂと基底Ｂ＊とのサイズは、線形変換Ｘのサイズに比例する。また、上述したように、基底Ｂと基底Ｂ＊とは、その一部が公開パラメータと秘密鍵にされる。したがって、公開パラメータと秘密鍵とのサイズは、線形変換Ｘのサイズに比例する。つまり、従来の線形変換Ｘを用いた場合、公開パラメータと秘密鍵とのサイズは、Ｎ２に比例する。これに対して、新しい線形変換Ｘを用いた場合、公開パラメータと秘密鍵とのサイズは、Ｎ＋１に比例する。
その結果、従来の線形変換Ｘを用いた場合、ユーザ鍵の生成の処理や暗号化の処理にＮ２に比例した時間がかかっていた。これに対して、新しい線形変換Ｘを用いた場合、ユーザ鍵の生成の処理や暗号化の処理にＮ＋１に比例した時間になる。つまり、新しい線形変換Ｘを用いた場合、計算時間が、Ｎのオーダーになる。
【００３０】
次に、非零内積暗号方式を例として、定数サイズの暗号文と効率的な復号を実現する具体的な方法について説明する。
なお、暗号文のサイズを説明する場合、ベクトルの記述は暗号文の一部に含めないものとする。復号鍵のサイズを説明する場合も同様に、ベクトルの記述は暗号文の一部に含めないものとする。
【００３１】
以下の実施の形態で説明する非零内積暗号方式を簡略化したものを用いて説明する。
簡略化した非零内積暗号方式における暗号文は、２つのベクトル要素（ｃ０，ｃ１）∈Ｇ５×Ｇｎと、ｃ３∈ＧＴとからなる。秘密鍵は、２つのベクトル要素ｋ＊０，ｋ＊１∈Ｇ５×Ｇｎからなる。なお、（ｃ０，ｃ１）∈Ｇ５×Ｇｎとは、ｃ０がＧの５個の要素であり、ｃ１がＧのｎ個の要素であることを意味する。同様に、ｋ＊０，ｋ＊１∈Ｇ５×Ｇｎとは、ｋ＊０がＧの５個の要素であり、ｋ＊１がＧのｎ個の要素であることを意味する。
そのため、暗号文のサイズを定数サイズにするには、ｃ１∈Ｇｎをｎについての定数サイズに圧縮する必要がある。
【００３２】
数１１８に示す特別な線形変換Ｘを用いる。
【数１１８】
ここで、μ，μ’１，．．．，μ’ｎは有限体Ｆｑから一様に選択された値であり、線形変換Ｘにおける空白は定数値０∈Ｆｑであることを示す。定数値０とは、値が０に固定されていることを意味する。つまり、μ，μ’１，．．．，μ’ｎは０も取り得る一様乱数であるのに対して、線形変換Ｘにおける空白は値が０に固定されている。また、Ｈ（ｎ，Ｆｑ）とは、有限体Ｆｑを要素とするｎ次元の行列の集合を意味する。
【００３３】
システムパラメータ又はＤＰＶＳの公開基底は、数１１９に示す基底Ｂである。
【数１１９】
【００３４】
ｘ→：＝（ｘ１，．．．，ｘｎ）に関連付けられた暗号文を、数１２０に示す暗号文ｃ１とする。
【数１２０】
ここで、ωは有限体Ｆｑから一様に選択された値である。
【００３５】
すると、暗号文ｃ１は、数１２１に示す２つのグループの要素Ｃ１，Ｃ２と、ベクトルｘ→とに圧縮できる。
【数１２１】
暗号文ｃ１は、（ｘ１Ｃ１，．．．，ｘｎ−１Ｃ１，Ｃ２）によって得られるためである。なお、ｉ＝１，．．．，ｎ−１の各ｉについて、ｘｉＣ１＝ｘｉωμｇである。
したがって、暗号文（ベクトルｘ→を除いた部分）は、２つのグループの要素とすることができ、ｎについての定数サイズとなる。
【００３６】
Ｂ＊：＝（ｂ＊ｉ）を、Ｂ：＝（ｂｉ）の双対正規直交基底とし、基底Ｂ＊を、簡略化した非零内積暗号方式におけるマスター秘密鍵であるとする。（ｃ０，ｋ＊０，ｃ３）を、ｅ（ｃ０，ｋ＊０）＝ｇＴζ・ｇＴωδであり、ｃ３：＝ｇＴζｍ∈ＧＴであると規定する。また、ベクトルｖ→に対する秘密鍵を、ｋ＊１：＝（δｖ→）Ｂ＊＝δ（ｖ１ｂ＊１＋・・・＋ｖｎｂ＊ｎ）のように設定する。
基底Ｂと基底Ｂ＊との双対正規直交性により、ｅ（ｃ１，ｋ＊１）＝ｇＴωδ（ｘ→・ｖ→）が成立する。そのため、復号者は、ｘ→・ｖ→≠０である場合に限り、ｇＴωδを計算できる。つまり、復号者は、数１２２によりメッセージｍを得ることができる。
【数１２２】
【００３７】
暗号文ｃ１は、（ｘ１Ｃ１，．．．，ｘｎ−１Ｃ１，Ｃ２）∈Ｇｎとして表され、秘密鍵ｋ＊１は、（Ｋ１，．．．，Ｋｎ）のｎ組に分解される。そのため、ｅ（ｃ１，ｋ＊１）の値は、数１２３である。
【数１２３】
【００３８】
つまり、ｅ（ｃ１，ｋ＊１）を計算するには、Ｇにおけるｎ−１個のスカラー乗法と、２つのペアリング演算とで十分である。すなわち、復号には、少ない数（定数）のペアリング演算だけが必要となる。一般に、ペアリング演算は、処理時間がかかる演算であるため、ペアリング演算の数を減らすことにより、処理全体としての処理時間を短くすることができる。
【００３９】
なお、簡略化した非零内積暗号方式では、暗号文ｃ１はベクトルｘ→が設定される基底ベクトル（実際の符号化部）のみを備え、秘密鍵ｋ＊１はベクトルｖ→が設定される基底ベクトル（実際の符号化部）のみを備えた。
以下の実施の形態で説明する非零内積暗号方式では、安全性を高めるため、暗号文ｃ１と秘密鍵ｋ＊１とに、実際の符号化部に加え、秘匿部と、秘密鍵ランダム化部と、暗号文ランダム化部とのための基底ベクトルを加える。
そのため、線形変換Ｘを数１２４のように拡張する。
【数１２４】
ここで、各Ｘｉ，ｊは、数１１８に示すＸ∈Ｈ（ｎ，Ｆｑ）である。そして、ベクトル空間は、４つの直交する部分空間で構成される。つまり、ベクトル空間は、符号化部と、秘匿部と、秘密鍵ランダム化部と、暗号文ランダム化部とのための４つの直交する部分空間で構成される。
【００４０】
実施の形態２．
実施の形態２では、暗号文のサイズを定数サイズとした非零内積暗号方式について説明する。
【００４１】
図３は、実施の形態２に係る鍵生成装置１００の構成図である。図４は、実施の形態２に係る暗号化装置２００の構成図である。図５は、実施の形態２に係る復号装置３００の構成図である。
図６と図７とは、実施の形態２に係る鍵生成装置１００の動作を示すフローチャートである。なお、図６は、実施の形態２に係るＳｅｔｕｐアルゴリズムの処理を示すフローチャートであり、図７は、実施の形態２に係るＫｅｙＧｅｎアルゴリズムの処理を示すフローチャートである。図８は、実施の形態２に係る暗号化装置２００の動作を示すフローチャートであり、実施の形態２に係るＥｎｃアルゴリズムの処理を示すフローチャートである。図９は、実施の形態２に係る復号装置３００の動作を示すフローチャートであり、実施の形態２に係るＤｅｃアルゴリズムの処理を示すフローチャートである。
【００４２】
なお、以下の説明において、入力されるベクトルｘ→：＝（ｘ１，．．．，ｘｎ）は、Ｌ＝１，．．．，ｎ−１の各整数ＬについてｘＬ≠０であり、入力されるベクトルｖ→：＝（ｖ１，．．．，ｖｎ）は、ｖｎ≠０であるとする。
【００４３】
鍵生成装置１００について説明する。
図３に示すように、鍵生成装置１００は、マスター鍵生成部１１０、マスター鍵記憶部１２０、情報入力部１３０、復号鍵生成部１４０、鍵配布部１５０を備える。マスター鍵生成部１１０は、空間生成部１１１、行列生成部１１２、基底生成部１１３、鍵生成部１１４を備える。復号鍵生成部１４０は、乱数生成部１４１、鍵要素生成部１４２を備える。
【００４４】
図６に基づき、Ｓｅｔｕｐアルゴリズムの処理について説明する。
（Ｓ１０１：空間生成ステップ）
空間生成部１１１は、セキュリティパラメータ１λを入力として、処理装置によりＧｂｐｇを実行して、対称双線形ペアリング群のパラメータｐａｒａｍＧ：＝（ｑ，Ｇ，ＧＴ，ｇ，ｅ）を生成する。
さらに、空間生成部１１１は、Ｎ０：＝５、Ｎ１：＝４ｎを設定する。そして、空間生成部１１１は、ｔ＝０，１の各ｔについて、セキュリティパラメータ１λと、Ｎｔと、対称双線形ペアリング群のパラメータｐａｒａｍＧとを入力として、処理装置によりＧｄｐｖｓを実行して、双対ペアリングベクトル空間のパラメータｐａｒａｍＶｔ：＝（ｑ，Ｖｔ，ＧＴ，Ａｔ，ｅ）を生成する。
【００４５】
（Ｓ１０２：線形変換生成ステップ）
行列生成部１１２は、数１２５に示すように、処理装置により線形変換Ｘ０を生成する。
【数１２５】
なお、数１２５における（χ０，ｉ，ｊ）ｉ，ｊ＝１，．．．，５は、行列χ０，ｉ，ｊの添え字ｉ，ｊに関する行列という意味という意味である。
また、行列生成部１１２は、数１２６に示すように、処理装置により線形変換Ｘ１を生成する。
【数１２６】
数１２６におけるＬ（Ｎ，Ｆｑ）は、数１２７に示す通りである。
【数１２７】
なお、以下、｛μｉ，ｊ，μ’ｉ，ｊ，Ｌ｝ｉ，ｊ＝１，．．．，４；Ｌ＝１，．．．，ｎは、線形変換Ｘ１における定数値０以外の要素を示す。
【００４６】
（Ｓ１０３：基底Ｂ生成ステップ）
基底生成部１１３は、数１２８に示すように、処理装置により基底Ｂ０と変数Ｂｉ，ｊと変数Ｂ’ｉ，ｊ，Ｌとを生成する。
【数１２８】
また、基底生成部１１３は、数１２９に示すように、処理装置により基底Ｂ＊０と基底Ｂ＊１とを生成する。
【数１２９】
【００４７】
（Ｓ１０４：基底Ｂ＾生成ステップ）
鍵生成部１１４は、数１３０に示すように、処理装置により基底Ｂ＾０と、基底Ｂ＾＊０と、基底Ｂ＾＊１とを生成する。
【数１３０】
【００４８】
（Ｓ１０５：マスター鍵生成ステップ）
鍵生成部１１４は、処理装置により公開パラメータｐｋ：＝（１λ，ｐａｒａｍｎ，Ｂ＾０，｛Ｂｉ，ｊ，Ｂ’ｉ，ｊ，Ｌ｝ｉ＝１，４；ｊ＝１，．．．，４；Ｌ＝１，．．．，ｎ）とし、マスター秘密鍵ｓｋ：＝｛Ｂ＾＊ｔ｝ｔ＝０，１とする。そして、鍵生成部１１４は、公開パラメータｐｋと、マスター秘密鍵ｓｋとをマスター鍵記憶部１２０に記憶する。
なお、ｐａｒａｍｎ：＝（｛ｐａｒａｍＶｔ｝ｔ＝０，１，ｇＴ）である。
【００４９】
つまり、Ｓ１０１からＳ１０５において、鍵生成装置１００は、数１３１に示すアルゴリズムＧ（１）ｏｂを用いた、数１３２に示すＳｅｔｕｐアルゴリズムを実行して、公開パラメータｐｋとマスター秘密鍵ｓｋとを生成する。
【数１３１】
【数１３２】
なお、公開パラメータは、例えば、ネットワークを介して公開され、暗号化装置２００や復号装置３００が取得可能な状態にされる。
【００５０】
Ｓ１０３では、基底Ｂ１を生成せず、代わりに変数Ｂｉ，ｊを生成した。基底Ｂ１を生成するのであれば、数１３３のようになる。
【数１３３】
数１３３の行列における空白部分は成分の値が０∈Ｇであることを示している。基底Ｂ１は、基底Ｂ＊１の正規直交基底である。つまり、ｅ（ｂ１，ｉ，ｂ＊１，ｊ）＝ｇＴであり、１≦ｉ≠ｊ≦４ｎの整数ｉ，ｊに対して、ｅ（ｂ１，ｉ，ｂ＊１，ｊ）＝１である。
【００５１】
図７に基づき、ＫｅｙＧｅｎアルゴリズムの処理について説明する。
（Ｓ１１１：情報入力ステップ）
情報入力部１３０は、ベクトルｖ→を入力装置により入力する。
【００５２】
（Ｓ１１２：乱数生成ステップ）
乱数生成部１４１は、数１３４に示すように、処理装置により乱数を生成する。
【数１３４】
【００５３】
（Ｓ１１３：要素ｋ＊０生成ステップ）
鍵要素生成部１４２は、数１３５に示すように、処理装置により復号鍵ｓｋｖ→の要素である要素ｋ＊０を生成する。
【数１３５】
なお、上述したように、数１１０に示す基底Ｂと基底Ｂ＊とに対して、数１１１である。したがって、数１３５は、基底Ｂ＊０の基底ベクトルｂ＊０，１の係数としてδを設定し、基底ベクトルｂ＊０，２の係数として０を設定し、基底ベクトルｂ＊０，３の係数として１を設定し、基底ベクトルｂ＊０，４の係数としてφ０を設定し、基底ベクトルｂ＊０，５の係数として０を設定することを意味する。
【００５４】
（Ｓ１１４：要素ｋ＊１生成ステップ）
鍵要素生成部１４２は、数１３６に示すように、処理装置により復号鍵ｓｋｖ→の要素である要素ｋ＊１を生成する。
【数１３６】
数１３６は、数１３５と同様に、基底Ｂ＊１の基底ベクトルｂ＊１，１，．．．，ｂ＊１，ｎの係数としてδｖ１，．．．，δｖｎを設定し、基底ベクトルｂ＊１，ｎ＋１，．．．，ｂ＊１，２ｎの係数として０を設定し、基底ベクトルｂ＊１，２ｎ＋１，．．．，ｂ＊１，３ｎの係数としてφ１ｖ１，．．．，φ１ｖｎを設定し、基底ベクトルｂ＊１，３ｎ＋１，．．．，ｂ＊１，４ｎの係数として０を設定することを意味する。
【００５５】
（Ｓ１１５：鍵配布ステップ）
鍵配布部１５０は、Ｓ１１１で入力したベクトルｖ→と、Ｓ１１３で生成した要素ｋ＊０と、Ｓ１１４で生成した要素ｋ＊１とを要素とする復号鍵ｓｋｖ→を、例えば通信装置によりネットワークを介して秘密裡に復号装置３００へ配布する。もちろん、復号鍵ｓｋｖ→は、他の方法により復号装置３００へ配布されてもよい。
【００５６】
つまり、Ｓ１１１からＳ１１４において、鍵生成装置１００は、数１３７に示すＫｅｙＧｅｎアルゴリズムを実行して、復号鍵ｓｋｖ→を生成する。そして、Ｓ１１５において、鍵生成装置１００は、生成された復号鍵ｓｋｖ→を復号装置３００へ配布する。
【数１３７】
【００５７】
暗号化装置２００について説明する。
図４に示すように、暗号化装置２００は、公開パラメータ取得部２１０、情報入力部２２０、暗号文生成部２３０、データ送信部２４０を備える。暗号文生成部２３０は、乱数生成部２３１、暗号要素生成部２３２を備える。
【００５８】
図８に基づき、Ｅｎｃアルゴリズムの処理について説明する。
（Ｓ１２１：公開パラメータ取得ステップ）
公開パラメータ取得部２１０は、例えば、通信装置によりネットワークを介して、鍵生成装置１００が生成した公開パラメータｐｋを取得する。
【００５９】
（Ｓ１２２：情報入力ステップ）
情報入力部２２０は、ベクトルｘ→を入力装置により入力する。
また、情報入力部２２０は、メッセージｍを入力装置により入力する。
【００６０】
（Ｓ１２３：乱数生成ステップ）
乱数生成部２３１は、数１３８に示すように、処理装置により乱数を生成する。
【数１３８】
【００６１】
（Ｓ１２４：要素ｃ０生成ステップ）
暗号要素生成部２３２は、数１３９に示すように、処理装置により暗号文ｃｔｘ→の要素である要素ｃ０を生成する。
【数１３９】
数１３９は、数１３５と同様に、基底Ｂ０の基底ベクトルｂ０，１の係数として−ωを設定し、基底ベクトルｂ０，２の係数として０を設定し、基底ベクトルｂ０，３の係数としてζを設定し、基底ベクトルｂ０，４の係数として０を設定し、基底ベクトルｂ０，５の係数としてη０を設定することを意味する。
【００６２】
（Ｓ１２５：要素Ｃ生成ステップ）
暗号要素生成部２３２は、数１４０に示すように、処理装置により暗号文ｃｔｘ→の要素である要素Ｃ１，ｊと要素Ｃ２，ｊとを生成する。
【数１４０】
【００６３】
（Ｓ１２６：要素ｃ３生成ステップ）
暗号要素生成部２３２は、数１４１に示すように、処理装置により暗号文ｃｔｘ→の要素である要素ｃ３を生成する。
【数１４１】
【００６４】
（Ｓ１２７：データ送信ステップ）
データ送信部２４０は、Ｓ１２２で入力したベクトルｘ→と、Ｓ１２４で生成した要素ｃ０と、Ｓ１２５で生成した要素Ｃ１，ｊ，Ｃ２，ｊと、Ｓ１２６で生成した要素ｃ３とを要素とする暗号文ｃｔｘ→を、例えば通信装置によりネットワークを介して復号装置３００へ送信する。もちろん、暗号文ｃｔｘ→は、他の方法により復号装置３００へ送信されてもよい。
【００６５】
つまり、Ｓ１２１からＳ１２６において、暗号化装置２００は、数１４２に示すＥｎｃアルゴリズムを実行して、暗号文ｃｔｘ→を生成する。そして、Ｓ１２７において、暗号化装置２００は、生成された暗号文ｃｔｘ→を復号装置３００へ送信する。
【数１４２】
【００６６】
復号装置３００について説明する。
図５に示すように、復号装置３００は、復号鍵取得部３１０、データ受信部３２０、ペアリング演算部３３０、メッセージ計算部３４０を備える。
【００６７】
図９に基づき、Ｄｅｃアルゴリズムの処理について説明する。
（Ｓ１３１：復号鍵取得ステップ）
復号鍵取得部３１０は、例えば、通信装置によりネットワークを介して、鍵生成装置１００から配布されたｓｋｖ→を取得する。
また、復号鍵取得部３１０は、鍵生成装置１００が生成した公開パラメータｐｋを取得する。
【００６８】
（Ｓ１３２：データ受信ステップ）
データ受信部３２０は、例えば、通信装置によりネットワークを介して、暗号化装置２００が送信した暗号文ｃｔｘ→を受信する。
【００６９】
（Ｓ１３３：値Ｄ＊ｊ計算ステップ）
ペアリング演算部３３０は、数１４３に示すように、処理装置により値Ｄ＊ｊを計算する。
【数１４３】
ここで、要素ｋ＊１は、（Ｋ＊１，．．．，Ｋ＊４ｎ）∈Ｇ４ｎの４ｎ組に分解される。
【００７０】
（Ｓ１３４：ペアリング演算ステップ）
ペアリング演算部３３０は、数１４４に示すように、処理装置によりペアリング演算を実行して、値Ｆを計算する。
【数１４４】
【００７１】
（Ｓ１３５：メッセージ計算ステップ）
メッセージ計算部３４０は、数１４５に示すように、処理装置によりメッセージｍ’を計算する。
【数１４５】
【００７２】
つまり、Ｓ１３１からＳ１３５において、復号装置３００は、数１４６に示すＤｅｃアルゴリズムを実行して、メッセージｍ’を計算する。
【数１４６】
【００７３】
なお、数１３３からＢ１：＝（ｂ１，１，．．．，ｂ１，４ｎ）は、｛Ｂｉ，ｊ，Ｂ’ｉ，ｊ，Ｌ｝ｉ，ｊ＝１，．．．，４；Ｌ＝１，．．．，ｎによって特定される。また、Ｓｅｔｕｐアルゴリズムの出力に含まれる｛Ｂｉ，ｊ，Ｂ’ｉ，ｊ，Ｌ｝ｉ＝１，４；ｊ＝１，．．．，４；Ｌ＝１，．．．，ｎは、Ｂ＾１：＝（ｂ１，１，．．．，ｂ１，ｎ，ｂ１，３ｎ＋１，．．．，ｂ１，４ｎ）によって特定される。
そして、Ｄｅｃアルゴリズムは、数１４７に示すＤｅｃ’アルゴリズムのように記述することができる。
【数１４７】
【００７４】
数１４８に示すように、Ｄｅｃ'アルゴリズムを用いた場合、ｘ→・ｖ→≠０であれば、Ｆ＝ｇζＴが得られる。そのため、ｃ３＝ｇζＴｍをＦで除することにより、メッセージｍ’（＝ｍ）が得られる。
【数１４８】
【００７５】
実施の形態２で説明した非零内積暗号方式では、暗号文ｃｔｘ→は、数１３９に示す要素ｃ０で５個と、数１４０に示す、ｊ＝１，．．．，４の各整数ｊについての要素Ｃ１，ｊ及び要素Ｃ２，ｊで８個との合計１３個のＧの要素を含む。また、数１４１に示す要素ｃ３で１個のＧＴの要素を含む。つまり、暗号文ｃｔｘ→は、ｎについて定数サイズである。
【００７６】
また、実施の形態２で説明した非零内積暗号方式では、復号処理（Ｄｅｃアルゴリズム）は、数１４４に示すｅ（ｃ０，ｋ＊０）で５個と、Πｊ＝１４（ｅ（Ｃ１，ｊ，Ｄ＊ｊ）・ｅ（Ｃ２，ｊ，Ｋ＊ｊｎ））で８個との合計１３個のみペアリング演算を実行する。つまり、復号処理は、少ない数のペアリング演算のみ必要となる。
【００７７】
実施の形態３．
実施の形態３では、秘密鍵のサイズを定数サイズとした非零内積暗号方式について説明する。
【００７８】
鍵生成装置１００、暗号化装置２００、復号装置３００の構成は、それぞれ図３、図４、図５に示す実施の形態２に係る鍵生成装置１００、暗号化装置２００、復号装置３００の構成と同一である。
図１０と図１１とは、実施の形態３に係る鍵生成装置１００の動作を示すフローチャートである。なお、図１０は、実施の形態３に係るＳｅｔｕｐアルゴリズムの処理を示すフローチャートであり、図１１は、実施の形態３に係るＫｅｙＧｅｎアルゴリズムの処理を示すフローチャートである。図１２は、実施の形態３に係る暗号化装置２００の動作を示すフローチャートであり、実施の形態３に係るＥｎｃアルゴリズムの処理を示すフローチャートである。図１３は、実施の形態３に係る復号装置３００の動作を示すフローチャートであり、実施の形態３に係るＤｅｃアルゴリズムの処理を示すフローチャートである。
【００７９】
なお、以下の説明において、入力されるベクトルｖ→：＝（ｖ１，．．．，ｖｎ）は、Ｌ＝１，．．．，ｎ−１の各整数ＬについてｖＬ≠０であり、入力されるベクトルｘ→：＝（ｘ１，．．．，ｘｎ）は、ｘｎ≠０であるとする。
【００８０】
鍵生成装置１００について説明する。
図１０に基づき、Ｓｅｔｕｐアルゴリズムの処理について説明する。
Ｓ２０１からＳ２０２までの処理は、図６に示すＳ１０１からＳ１０２までの処理と同じである。
【００８１】
（Ｓ２０３：基底Ｂ生成ステップ）
基底生成部１１３は、実施の形態２における基底Ｂ０と変数Ｂｉ，ｊと同様に、数１４９に示すように、処理装置により基底Ｄ０と変数Ｄｉ，ｊと変数Ｄ’ｉ，ｊ，Ｌとを生成する。
【数１４９】
また、基底生成部１１３は、実施の形態２における基底Ｂ＊０と基底Ｂ＊１と同様に、数１５０に示すように、処理装置により基底Ｄ＊０と基底Ｄ＊１とを生成する。
【数１５０】
そして、基底生成部１１３は、基底Ｄ＊０を基底Ｂ０とし、基底Ｄ０を基底Ｂ＊０とし、基底Ｄ＊１を基底Ｂ１とする。また、基底生成部１１３は、ｉ，ｊ＝１，．．．，４の各整数ｉ，ｊと、Ｌ＝１，．．．，ｎの各整数Ｌとについて、変数Ｄｉ，ｊを変数Ｂ＊ｉ，ｊとし、変数Ｄ’ｉ，ｊ，Ｌを変数Ｂ’＊ｉ，ｊ，Ｌとする。
【００８２】
（Ｓ２０４：基底Ｂ＾生成ステップ）
鍵生成部１１４は、数１５１に示すように、処理装置により基底Ｂ＾０と、基底Ｂ＾１と、基底Ｂ＾＊０とを生成する。
【数１５１】
【００８３】
（Ｓ２０５：マスター鍵生成ステップ）
鍵生成部１１４は、処理装置により公開パラメータｐｋ：＝（１λ，ｐａｒａｍｎ，｛Ｂ＾ｔ｝ｔ＝０，１）とし、マスター秘密鍵ｓｋ：＝Ｂ＾＊０，｛Ｂ＊ｉ，ｊ，Ｂ’＊ｉ，ｊ，Ｌ｝ｉ＝１，３；ｊ＝１，．．．，４；Ｌ＝１，．．．，ｎとする。そして、鍵生成部１１４は、公開パラメータｐｋと、マスター秘密鍵ｓｋとをマスター鍵記憶部１２０に記憶する。
なお、ｐａｒａｍｎ：＝（｛ｐａｒａｍＶｔ｝ｔ＝０，１，ｇＴ）である。
【００８４】
つまり、Ｓ２０１からＳ２０５において、鍵生成装置１００は、数１５２に示すアルゴリズムＧ（２）ｏｂを用いた、数１５３に示すＳｅｔｕｐアルゴリズムを実行して、公開パラメータｐｋとマスター秘密鍵ｓｋとを生成する。ここで、数１５２に示すように、アルゴリズムＧ（２）ｏｂは、数１３１に示すアルゴリズムＧ（１）ｏｂを用いる。
【数１５２】
【数１５３】
なお、公開パラメータは、例えば、ネットワークを介して公開され、暗号化装置２００や復号装置３００が取得可能な状態にされる。
【００８５】
図１１に基づき、ＫｅｙＧｅｎアルゴリズムの処理について説明する。
Ｓ２１１からＳ２１３までの処理は、図７に示すＳ１１１からＳ１１３までの処理と同じである。
【００８６】
（Ｓ２１４：要素Ｋ＊生成ステップ）
鍵要素生成部１４２は、数１５４に示すように、処理装置により復号鍵ｓｋｖ→の要素である要素Ｋ＊１，ｊと要素Ｋ＊２，ｊとを生成する。
【数１５４】
【００８７】
（Ｓ２１５：鍵配布ステップ）
鍵配布部１５０は、Ｓ２１１で入力したベクトルｖ→と、Ｓ２１３で生成した要素ｋ＊０と、Ｓ２１４で生成した要素Ｋ＊１，ｊ，Ｋ＊２，ｊとを要素とする復号鍵ｓｋｖ→を、例えば通信装置によりネットワークを介して秘密裡に復号装置３００へ配布する。もちろん、復号鍵ｓｋｖ→は、他の方法により復号装置３００へ配布されてもよい。
【００８８】
つまり、Ｓ２１１からＳ２１４において、鍵生成装置１００は、数１５５に示すＫｅｙＧｅｎアルゴリズムを実行して、復号鍵ｓｋｖ→を生成する。そして、Ｓ２１５において、鍵生成装置１００は、生成された復号鍵ｓｋｖ→を復号装置３００へ配布する。
【数１５５】
【００８９】
暗号化装置２００について説明する。
図１２に基づき、Ｅｎｃアルゴリズムの処理について説明する。
Ｓ２２１からＳ２２４までの処理は、図８に示すＳ１２１からＳ１２４までの処理と同じである。
【００９０】
（Ｓ２２５：要素ｃ１生成ステップ）
暗号要素生成部２３２は、数１５６に示すように、処理装置により暗号文ｃｔｘ→の要素である要素ｃ１を生成する。
【数１５６】
数１５６は、数１３５と同様に、基底Ｂ１の基底ベクトルｂ＊１，１，．．．，ｂ＊１，ｎの係数としてωｘ１，．．．，ωｘｎを設定し、基底ベクトルｂ＊１，ｎ＋１，．．．，ｂ＊１，３ｎの係数として０を設定し、基底ベクトルｂ＊１，３ｎ＋１，．．．，ｂ＊１，４ｎの係数としてη１ｘ１，．．．，η１ｘｎを設定することを意味する。
【００９１】
Ｓ２２６の処理は、図８に示すＳ１２６の処理と同じである。
【００９２】
（Ｓ２２７：データ送信ステップ）
データ送信部２４０は、Ｓ２２２で入力したベクトルｘ→と、Ｓ２２４で生成した要素ｃ０と、Ｓ２２５で生成した要素ｃ１と、Ｓ２２６で生成した要素ｃ３とを要素とする暗号文ｃｔｘ→を、例えば通信装置によりネットワークを介して復号装置３００へ送信する。もちろん、暗号文ｃｔｘ→は、他の方法により復号装置３００へ送信されてもよい。
【００９３】
つまり、Ｓ２２１からＳ２２６において、暗号化装置２００は、数１５７に示すＥｎｃアルゴリズムを実行して、暗号文ｃｔｘ→を生成する。そして、Ｓ２２７において、暗号化装置２００は、生成された暗号文ｃｔｘ→を復号装置３００へ送信する。
【数１５７】
【００９４】
復号装置３００について説明する。
図１３に基づき、Ｄｅｃアルゴリズムの処理について説明する。
Ｓ２３１からＳ２３２までの処理は、図９に示すＳ１３１からＳ１３２までの処理と同じである。
【００９５】
（Ｓ２３３：値Ｄｊ計算ステップ）
ペアリング演算部３３０は、数１５８に示すように、処理装置により値Ｄｊを計算する。
【数１５８】
ここで、要素ｃ１は、（Ｃ１，．．．，Ｃ４ｎ）∈Ｇ４ｎの４ｎ組に分解される。
【００９６】
（Ｓ２３４：ペアリング演算ステップ）
ペアリング演算部３３０は、数１５９に示すように、処理装置によりペアリング演算を実行して、値Ｆを計算する。
【数１５９】
【００９７】
Ｓ２３５の処理は、図９に示すＳ１３５の処理と同じである。
【００９８】
つまり、Ｓ２３１からＳ２３５において、復号装置３００は、数１６０に示すＤｅｃアルゴリズムを実行して、メッセージｍ’を計算する。
【数１６０】
【００９９】
なお、Ｂ＊１：＝（ｂ＊１，１，．．．，ｂ＊１，４ｎ）は、｛Ｂ＊ｉ，ｊ，Ｂ’＊ｉ，ｊ，Ｌ｝ｉ，ｊ＝１，．．．，４；Ｌ＝１，．．．，ｎによって特定される。また、Ｓｅｔｕｐアルゴリズムの出力に含まれる｛Ｂ＊ｉ，ｊ，Ｂ’＊ｉ，ｊ，Ｌ｝ｉ＝１，３；ｊ＝１，．．．，４；Ｌ＝１，．．．，ｎは、Ｂ＾＊１：＝（ｂ＊１，１，．．．，ｂ＊１，ｎ，ｂ＊１，２ｎ＋１，．．．，ｂ＊１，３ｎ）によって特定される。
そして、Ｄｅｃアルゴリズムは、数１６１に示すＤｅｃ’アルゴリズムのように記述することができる。
【数１６１】
【０１００】
実施の形態３で説明した非零内積暗号方式では、復号鍵ｓｋｖ→は、数１３５に示す要素ｋ＊０で５個と、数１５４に示す、ｊ＝１，．．．，４の各整数ｊについての要素Ｋ＊１，ｊ及び要素Ｋ＊２，ｊで８個との合計１３個のＧの要素を含む。つまり、復号鍵ｓｋｖ→は、ｎについて定数サイズである。
【０１０１】
また、実施の形態３で説明した非零内積暗号方式では、復号処理（Ｄｅｃアルゴリズム）は、数１５９に示すｅ（ｃ０，ｋ＊０）で５個と、Πｊ＝１４（ｅ（Ｄｊ，Ｋ＊１，ｊ）・ｅ（Ｃｊｎ，Ｋ＊２，ｊ））で８個との合計１３個のみペアリング演算を実行する。つまり、復号処理は、少ない数のペアリング演算のみ必要となる。
【０１０２】
実施の形態４．
実施の形態４では、暗号文のサイズを定数サイズとした零内積暗号方式について説明する。
【０１０３】
鍵生成装置１００、暗号化装置２００、復号装置３００の構成は、それぞれ図３、図４、図５に示す実施の形態２に係る鍵生成装置１００、暗号化装置２００、復号装置３００の構成と同一である。
図１４と図１５とは、実施の形態４に係る鍵生成装置１００の動作を示すフローチャートである。なお、図１４は、実施の形態４に係るＳｅｔｕｐアルゴリズムの処理を示すフローチャートであり、図１５は、実施の形態４に係るＫｅｙＧｅｎアルゴリズムの処理を示すフローチャートである。図１６は、実施の形態４に係る暗号化装置２００の動作を示すフローチャートであり、実施の形態４に係るＥｎｃアルゴリズムの処理を示すフローチャートである。図１７は、実施の形態４に係る復号装置３００の動作を示すフローチャートであり、実施の形態４に係るＤｅｃアルゴリズムの処理を示すフローチャートである。
【０１０４】
なお、以下の説明において、入力されるベクトルｘ→：＝（ｘ１，．．．，ｘｎ）は、Ｌ＝１，．．．，ｎ−１の各整数ＬについてｘＬ≠０であり、入力されるベクトルｖ→：＝（ｖ１，．．．，ｖｎ）は、ｖｎ≠０であるとする。
【０１０５】
鍵生成装置１００について説明する。
図１４に基づき、Ｓｅｔｕｐアルゴリズムの処理について説明する。
（Ｓ３０１：空間生成ステップ）
空間生成部１１１は、セキュリティパラメータ１λを入力として、処理装置によりＧｂｐｇを実行して、対称双線形ペアリング群のパラメータｐａｒａｍＧ：＝（ｑ，Ｇ，ＧＴ，ｇ，ｅ）を生成する。
さらに、空間生成部１１１は、Ｎ：＝４ｎ＋１を設定する。そして、空間生成部１１１は、セキュリティパラメータ１λと、Ｎと、対称双線形ペアリング群のパラメータｐａｒａｍＧとを入力として、処理装置によりＧｄｐｖｓを実行して、双対ペアリングベクトル空間のパラメータｐａｒａｍＶｔ：＝（ｑ，Ｖ，ＧＴ，Ａ，ｅ）を生成する。
【０１０６】
（Ｓ３０２：線形変換生成ステップ）
行列生成部１１２は、数１６２に示すように、処理装置により線形変換Ｘを生成する。
【数１６２】
数１６２におけるＬ’（Ｎ，Ｆｑ）は、数１６３に示す通りである。
【数１６３】
なお、以下、｛χ０，０，χ０，ｊ，χｉ，０，Ｌ，μｉ，ｊ，μ’ｉ，ｊ，Ｌ｝ｉ，ｊ＝１，．．．，４；Ｌ＝１，．．．，ｎは、線形変換Ｘにおける定数値０以外の要素を示す。
【０１０７】
（Ｓ３０３：基底Ｂ生成ステップ）
基底生成部１１３は、数１６４に示すように、処理装置により変数Ｂ０，０と変数Ｂ０，ｊと変数Ｂｉ，０，Ｌと変数Ｂｉ，ｊと変数Ｂ’ｉ，ｊ，Ｌとを生成する。
【数１６４】
また、基底生成部１１３は、数１６５に示すように、処理装置により基底Ｂ＊を生成する。
【数１６５】
【０１０８】
（Ｓ３０４：基底Ｂ＾生成ステップ）
鍵生成部１１４は、数１６６に示すように、処理装置により基底Ｂ＾＊を生成する。
【数１６６】
【０１０９】
（Ｓ３０５：マスター鍵生成ステップ）
鍵生成部１１４は、処理装置により公開パラメータｐｋ：＝（１λ，ｐａｒａｍｎ，Ｂ＾０，｛Ｂ０，０，Ｂ０，ｊ，Ｂｉ，０，Ｌ，Ｂｉ，ｊ，Ｂ’ｉ，ｊ，Ｌ｝ｉ＝１，４；ｊ＝１，．．．，４；Ｌ＝１，．．．，ｎ）とし、マスター秘密鍵ｓｋ：＝Ｂ＾＊とする。そして、鍵生成部１１４は、公開パラメータｐｋと、マスター秘密鍵ｓｋとをマスター鍵記憶部１２０に記憶する。
なお、ｐａｒａｍｎ：＝（ｐａｒａｍＶ，ｇＴ）である。
【０１１０】
つまり、Ｓ３０１からＳ３０５において、鍵生成装置１００は、数１６７に示すアルゴリズムＧ（３）ｏｂを用いた、数１６８に示すＳｅｔｕｐアルゴリズムを実行して、公開パラメータｐｋとマスター秘密鍵ｓｋとを生成する。
【数１６７】
【数１６８】
なお、公開パラメータは、例えば、ネットワークを介して公開され、暗号化装置２００や復号装置３００が取得可能な状態にされる。
【０１１１】
図１５に基づき、ＫｅｙＧｅｎアルゴリズムの処理について説明する。
Ｓ３１１の処理は、図７に示すＳ１１１の処理と同じである。
【０１１２】
（Ｓ３１２：乱数生成ステップ）
乱数生成部１４１は、数１６９に示すように、処理装置により乱数を生成する。
【数１６９】
【０１１３】
（Ｓ３１３：要素ｋ＊生成ステップ）
鍵要素生成部１４２は、数１７０に示すように、処理装置により復号鍵ｓｋｖ→の要素である要素ｋ＊を生成する。
【数１７０】
数１７０は、数１３５と同様に、基底Ｂ＊の基底ベクトルｂ＊０の係数として１を設定し、基底ベクトルｂ＊１，．．．，ｂ＊ｎの係数としてδｖ１，．．．，δｖｎを設定し、基底ベクトルｂ＊ｎ＋１，．．．，ｂ＊２ｎの係数として０を設定し、基底ベクトルｂ＊２ｎ＋１，．．．，ｂ＊３ｎの係数としてφｖ１，．．．，φｖｎを設定し、基底ベクトルｂ＊３ｎ＋１，．．．，ｂ＊４ｎの係数として０を設定することを意味する。
【０１１４】
（Ｓ３１４：鍵配布ステップ）
鍵配布部１５０は、Ｓ３１３で生成した要素ｋ＊を要素とする復号鍵ｓｋｖ→を、例えば通信装置によりネットワークを介して秘密裡に復号装置３００へ配布する。もちろん、復号鍵ｓｋｖ→は、他の方法により復号装置３００へ配布されてもよい。
【０１１５】
つまり、Ｓ３１１からＳ３１３において、鍵生成装置１００は、数１７１に示すＫｅｙＧｅｎアルゴリズムを実行して、復号鍵ｓｋｖ→を生成する。そして、Ｓ３１４において、鍵生成装置１００は、生成された復号鍵ｓｋｖ→を復号装置３００へ配布する。
【数１７１】
【０１１６】
暗号化装置２００について説明する。
図１６に基づき、Ｅｎｃアルゴリズムの処理について説明する。
Ｓ３２１からＳ３２２までの処理は、図８に示すＳ１２１からＳ１２２までの処理と同じである。
【０１１７】
（Ｓ３２３：乱数生成ステップ）
乱数生成部２３１は、数１７２に示すように、処理装置により乱数を生成する。
【数１７２】
【０１１８】
（Ｓ３２４：要素Ｃ生成ステップ）
暗号要素生成部２３２は、数１７３に示すように、処理装置により暗号文ｃｔｘ→の要素である要素Ｃ０と要素Ｃ１，ｊと要素Ｃ２，ｊとを生成する。
【数１７３】
【０１１９】
Ｓ３２５の処理は、図８に示すＳ１２６の処理と同じである。
【０１２０】
（Ｓ３２６：データ送信ステップ）
データ送信部２４０は、Ｓ３２２で入力したベクトルｘ→と、Ｓ３２４で生成した要素Ｃ０，Ｃ１，ｊ，Ｃ２，ｊと、Ｓ３２５で生成した要素ｃ３とを要素とする暗号文ｃｔｘ→を、例えば通信装置によりネットワークを介して復号装置３００へ送信する。もちろん、暗号文ｃｔｘ→は、他の方法により復号装置３００へ送信されてもよい。
【０１２１】
つまり、Ｓ３２１からＳ３２５において、暗号化装置２００は、数１７４に示すＥｎｃアルゴリズムを実行して、暗号文ｃｔｘ→を生成する。そして、Ｓ３２６において、暗号化装置２００は、生成された暗号文ｃｔｘ→を復号装置３００へ送信する。
【数１７４】
【０１２２】
復号装置３００について説明する。
図１７に基づき、Ｄｅｃアルゴリズムの処理について説明する。
Ｓ３３１からＳ３３２までの処理は、図９に示すＳ１３１からＳ１３２までの処理と同じである。
【０１２３】
（Ｓ３３３：値Ｄ＊ｊ計算ステップ）
ペアリング演算部３３０は、数１７５に示すように、処理装置により値Ｄ＊ｊを計算する。
【数１７５】
ここで、要素ｋ＊は、（Ｋ＊０，．．．，Ｋ＊４ｎ）∈Ｇ４ｎ＋１の（４ｎ＋１）組に分解される。
【０１２４】
（Ｓ３３４：ペアリング演算ステップ）
ペアリング演算部３３０は、数１７６に示すように、処理装置によりペアリング演算を実行して、値Ｆを計算する。
【数１７６】
【０１２５】
Ｓ３３５の処理は、図９に示すＳ１３５の処理と同じである。
【０１２６】
つまり、Ｓ３３１からＳ３３５において、復号装置３００は、数１７７に示すＤｅｃアルゴリズムを実行して、メッセージｍ’を計算する。
【数１７７】
【０１２７】
なお、Ｂ：＝（ｂ０，．．．，ｂ４ｎ）は、｛Ｂ０，０，Ｂ０，ｊ，Ｂｉ，０，Ｌ，Ｂｉ，ｊ，Ｂ’ｉ，ｊ，Ｌ｝ｉ，ｊ＝１，．．．，４；Ｌ＝１，．．．，ｎによって特定される。また、Ｓｅｔｕｐアルゴリズムの出力に含まれる｛Ｂ０，０，Ｂ０，ｊ，Ｂｉ，０，Ｌ，Ｂｉ，ｊ，Ｂ’ｉ，ｊ，Ｌ｝ｉ＝１，４；ｊ＝１，．．．，４；Ｌ＝１，．．．，ｎは、Ｂ＾：＝（ｂ０，．．．，ｂｎ，ｂ３ｎ＋１，．．．，ｂ４ｎ）によって特定される。
そして、Ｄｅｃアルゴリズムは、数１７８に示すＤｅｃ’アルゴリズムのように記述することができる。
【数１７８】
【０１２８】
数１７９に示すように、Ｄｅｃ'アルゴリズムを用いた場合、ｘ→・ｖ→＝０であれば、Ｆ＝ｇζＴが得られる。そのため、ｃ３＝ｇζＴｍをＦで除することにより、メッセージｍ’（＝ｍ）が得られる。
【数１７９】
【０１２９】
実施の形態４で説明した零内積暗号方式では、暗号文ｃｔｘ→は、数１７３に示す要素Ｃ０で１個と、ｊ＝１，．．．，４の各整数ｊについての要素Ｃ１，ｊ及び要素Ｃ２，ｊで８個との合計９個のＧの要素を含む。また、要素ｃ３で１個のＧＴの要素を含む。つまり、暗号文ｃｔｘ→は、ｎについて定数サイズである。
【０１３０】
また、実施の形態４で説明した零内積暗号方式では、復号処理（Ｄｅｃアルゴリズム）は、数１７６に示すｅ（Ｃ０，Ｋ＊０）で１個と、Πｊ＝１４（ｅ（Ｃ１，ｊ，Ｄ＊ｊ）・ｅ（Ｃ２，ｊ，Ｋ＊ｊｎ））で８個との合計９個のみペアリング演算を実行する。つまり、復号処理は、少ない数のペアリング演算のみ必要となる。
【０１３１】
実施の形態５．
実施の形態５では、秘密鍵のサイズを定数サイズとした零内積暗号方式について説明する。
【０１３２】
鍵生成装置１００、暗号化装置２００、復号装置３００の構成は、それぞれ図３、図４、図５に示す実施の形態２に係る鍵生成装置１００、暗号化装置２００、復号装置３００の構成と同一である。
図１８と図１９とは、実施の形態５に係る鍵生成装置１００の動作を示すフローチャートである。なお、図１８は、実施の形態５に係るＳｅｔｕｐアルゴリズムの処理を示すフローチャートであり、図１９は、実施の形態５に係るＫｅｙＧｅｎアルゴリズムの処理を示すフローチャートである。図２０は、実施の形態５に係る暗号化装置２００の動作を示すフローチャートであり、実施の形態５に係るＥｎｃアルゴリズムの処理を示すフローチャートである。図２１は、実施の形態５に係る復号装置３００の動作を示すフローチャートであり、実施の形態５に係るＤｅｃアルゴリズムの処理を示すフローチャートである。
【０１３３】
なお、以下の説明において、入力されるベクトルｖ→：＝（ｖ１，．．．，ｖｎ）は、Ｌ＝１，．．．，ｎ−１の各整数ＬについてｖＬ≠０であり、入力されるベクトルｘ→：＝（ｘ１，．．．，ｘｎ）は、ｘｎ≠０であるとする。
【０１３４】
鍵生成装置１００について説明する。
図１８に基づき、Ｓｅｔｕｐアルゴリズムの処理について説明する。
Ｓ４０１からＳ４０２までの処理は、図１４に示すＳ３０１からＳ３０２までの処理と同じである。
【０１３５】
（Ｓ４０３：基底Ｂ生成ステップ）
基底生成部１１３は、実施の形態４における変数Ｂ０，０と変数Ｂ０，ｊと変数Ｂｉ，０，Ｌと変数Ｂｉ，ｊと変数Ｂ’ｉ，ｊ，Ｌと同様に、数１８０に示すように、処理装置により変数Ｄ０，０と変数Ｄ０，ｊと変数Ｄｉ，０，Ｌと変数Ｄｉ，ｊと変数Ｄ’ｉ，ｊ，Ｌとを生成する。
【数１８０】
また、基底生成部１１３は、実施の形態４における基底Ｂ＊と同様に、数１８１に示すように、処理装置により基底Ｄ＊を生成する。
【数１８１】
そして、基底生成部１１３は、基底Ｄ＊を基底Ｂとする。また、基底生成部１１３は、ｉ，ｊ＝１，．．．，４の各整数ｉ，ｊと、Ｌ＝１，．．．，ｎの各整数Ｌとについて、変数Ｄ０，０を変数Ｂ＊０，０とし、変数Ｄ０，ｊを変数Ｂ＊０，ｊとし、変数Ｄｉ，０，Ｌを変数Ｂ＊ｉ，０，Ｌとし、変数Ｄｉ，ｊを変数Ｂ＊ｉ，ｊとし、変数Ｄ’ｉ，ｊ，Ｌを変数Ｂ’＊ｉ，ｊ，Ｌとする。
【０１３６】
（Ｓ４０４：基底Ｂ＾生成ステップ）
鍵生成部１１４は、数１８２に示すように、処理装置により基底Ｂ＾を生成する。
【数１８２】
【０１３７】
（Ｓ４０５：マスター鍵生成ステップ）
鍵生成部１１４は、処理装置により公開パラメータｐｋ：＝（１λ，ｐａｒａｍｎ，Ｂ＾）とし、マスター秘密鍵ｓｋ：＝（｛Ｂ＊０，０，Ｂ＊０，ｊ，Ｂ＊ｉ，０，Ｌ，Ｂ＊ｉ，ｊ，Ｂ’＊ｉ，ｊ，Ｌ｝ｉ＝１，３；ｊ＝１，．．．，４；Ｌ＝１，．．．，ｎ）とする。そして、鍵生成部１１４は、公開パラメータｐｋと、マスター秘密鍵ｓｋとをマスター鍵記憶部１２０に記憶する。
なお、ｐａｒａｍｎ：＝（ｐａｒａｍＶ，ｇＴ）である。
【０１３８】
つまり、Ｓ４０１からＳ４０５において、鍵生成装置１００は、数１８３に示すアルゴリズムＧ（４）ｏｂを用いた、数１８４に示すＳｅｔｕｐアルゴリズムを実行して、公開パラメータｐｋとマスター秘密鍵ｓｋとを生成する。ここで、数１８３に示すように、アルゴリズムＧ（４）ｏｂは、数１６７に示すアルゴリズムＧ（３）ｏｂを用いる。
【数１８３】
【数１８４】
なお、公開パラメータは、例えば、ネットワークを介して公開され、暗号化装置２００や復号装置３００が取得可能な状態にされる。
【０１３９】
図１９に基づき、ＫｅｙＧｅｎアルゴリズムの処理について説明する。
Ｓ４１１からＳ４１２までの処理は、図１５に示すＳ３１１からＳ３１２までの処理と同じである。
【０１４０】
（Ｓ４１３：要素Ｋ＊生成ステップ）
鍵要素生成部１４２は、数１８５に示すように、処理装置により復号鍵ｓｋｖ→の要素である要素Ｋ＊０と要素Ｋ＊１，ｊと要素Ｋ＊２，ｊとを生成する。
【数１８５】
【０１４１】
（Ｓ４１４：鍵配布ステップ）
鍵配布部１５０は、Ｓ４１１で入力したベクトルｖ→と、Ｓ３１３で生成した要素Ｋ＊０，Ｋ＊１，ｊ，Ｋ＊２，ｊとを要素とする復号鍵ｓｋｖ→を、例えば通信装置によりネットワークを介して秘密裡に復号装置３００へ配布する。もちろん、復号鍵ｓｋｖ→は、他の方法により復号装置３００へ配布されてもよい。
【０１４２】
つまり、Ｓ４１１からＳ４１３において、鍵生成装置１００は、数１８６に示すＫｅｙＧｅｎアルゴリズムを実行して、復号鍵ｓｋｖ→を生成する。そして、Ｓ４１４において、鍵生成装置１００は、生成された復号鍵ｓｋｖ→を復号装置３００へ配布する。
【数１８６】
【０１４３】
暗号化装置２００について説明する。
図２０に基づき、Ｅｎｃアルゴリズムの処理について説明する。
Ｓ４２１からＳ４２３までの処理は、図１６に示すＳ３２１からＳ３２３までの処理と同じである。
【０１４４】
（Ｓ４２４：要素ｃ生成ステップ）
暗号要素生成部２３２は、数１８７に示すように、処理装置により暗号文ｃｔｘ→の要素である要素ｃを生成する。
【数１８７】
数１８７は、数１３５と同様に、基底Ｂの基底ベクトルｂ０の係数としてζを設定し、基底ベクトルｂ１，．．．，ｂｎの係数としてωｘ１，．．．，ωｘｎを設定し、基底ベクトルｂｎ＋１，．．．，ｂ３ｎの係数として０を設定し、基底ベクトルｂ３ｎ＋１，．．．，ｂ４ｎの係数としてηｘ１，．．．，ηｘｎを設定することを意味する。
【０１４５】
Ｓ４２５の処理は、図１６に示すＳ３２５の処理と同じである。
【０１４６】
（Ｓ４２６：データ送信ステップ）
データ送信部２４０は、Ｓ４２２で入力したベクトルｘ→と、Ｓ４２４で生成した要素ｃと、Ｓ４２５で生成した要素ｃ３とを要素とする暗号文ｃｔｘ→を、例えば通信装置によりネットワークを介して復号装置３００へ送信する。もちろん、暗号文ｃｔｘ→は、他の方法により復号装置３００へ送信されてもよい。
【０１４７】
つまり、Ｓ４２１からＳ４２５において、暗号化装置２００は、数１８８に示すＥｎｃアルゴリズムを実行して、暗号文ｃｔｘ→を生成する。そして、Ｓ４２６において、暗号化装置２００は、生成された暗号文ｃｔｘ→を復号装置３００へ送信する。
【数１８８】
【０１４８】
復号装置３００について説明する。
図２１に基づき、Ｄｅｃアルゴリズムの処理について説明する。
Ｓ４３１からＳ４３２までの処理は、図１７に示すＳ３３１からＳ３３２までの処理と同じである。
【０１４９】
（Ｓ４３３：値Ｄｊ計算ステップ）
ペアリング演算部３３０は、数１８９に示すように、処理装置により値Ｄｊを計算する。
【数１８９】
ここで、要素ｃは、（Ｃ＊０，．．．，Ｃ＊４ｎ）∈Ｇ４ｎ＋１の（４ｎ＋１）組に分解される。
【０１５０】
（Ｓ４３４：ペアリング演算ステップ）
ペアリング演算部３３０は、数１９０に示すように、処理装置によりペアリング演算を実行して、値Ｆを計算する。
【数１９０】
【０１５１】
Ｓ４３５の処理は、図１７に示すＳ３３５の処理と同じである。
【０１５２】
つまり、Ｓ４３１からＳ４３５において、復号装置３００は、数１９１に示すＤｅｃアルゴリズムを実行して、メッセージｍ’を計算する。
【数１９１】
【０１５３】
なお、Ｂ＊：＝（ｂ＊０，．．．，ｂ＊４ｎ）は、｛Ｂ＊０，０，Ｂ＊０，ｊ，Ｂ＊ｉ，０，Ｌ，Ｂ＊ｉ，ｊ，Ｂ’＊ｉ，ｊ，Ｌ｝ｉ，ｊ＝１，．．．，４；Ｌ＝１，．．．，ｎによって特定される。また、Ｓｅｔｕｐアルゴリズムの出力に含まれる｛Ｂ＊０，０，Ｂ＊０，ｊ，Ｂ＊ｉ，０，Ｌ，Ｂ＊ｉ，ｊ，Ｂ’＊ｉ，ｊ，Ｌ｝ｉ＝１，３；ｊ＝１，．．．，４；Ｌ＝１，．．．，ｎは、Ｂ＾＊：＝（ｂ＊０，．．．，ｂ＊ｎ，ｂ＊２ｎ＋１，．．．，ｂ＊３ｎ）によって特定される。
そして、Ｄｅｃアルゴリズムは、数１９２に示すＤｅｃ’アルゴリズムのように記述することができる。
【数１９２】
【０１５４】
実施の形態５で説明した零内積暗号方式では、復号鍵ｓｋｖ→は、数１８５に示す要素Ｋ＊０で１個と、ｊ＝１，．．．，４の各整数ｊについての要素Ｋ＊１，ｊ及び要素Ｋ＊２，ｊで８個との合計９個のＧの要素を含む。つまり、復号鍵ｓｋｖ→は、ｎについて定数サイズである。
【０１５５】
また、実施の形態５で説明した零内積暗号方式では、復号処理（Ｄｅｃアルゴリズム）は、数１９０に示すｅ（Ｃ０，Ｋ＊０）で１個と、Πｊ＝１４（ｅ（Ｄｊ，Ｋ＊１，ｊ）・ｅ（Ｃｊｎ，Ｋ＊２，ｊ））で８個との合計９個のみペアリング演算を実行する。つまり、復号処理は、少ない数のペアリング演算のみ必要となる。
【０１５６】
なお、以上の実施の形態では、図２（ｂ）に示す線形変換Ｘを用いた。しかし、線形変換Ｘは、図２（ｂ）に示すものに限らない。例えば、図２（ｂ）における斜線が入れられた四角が示す部分をそれぞれ異なる値としてもよい。また、図２（ｂ）では、Ｎ列における全ての成分を定数値０以外の乱数としたが、Ｎ列ではなく、他のいずれか少なくとも１列における全ての成分を定数値０以外の乱数としてもよい。
より一般的には、線形変換Ｘは、各行各列に少なくとも１つは定数値０以外の値を有する疎行列であればよい。さらに、線形変換Ｘは、ｎ行ｎ列の行列である場合、定数値０以外の値として、少なくともｎ個の異なる値を有しているとよい。さらに、線形変換Ｘは、少なくとも１つの列における全ての成分が定数値０以外の値であるとよい。さらに、線形変換Ｘは、対角成分と、少なくとも１つの列における全ての成分が定数値０以外の値であるとよい。さらに、線形変換Ｘは、全ての成分が定数値０以外の値である列を除き、対角成分の値が同一であるとよい。
このような線形変換Ｘを用いた場合であっても、従来の線形変換Ｘを用いた場合に比べ、公開パラメータと秘密鍵とのサイズは小さくなる。また、ユーザ鍵の生成や暗号化の処理の処理時間も短くなる。
但し、線形変換Ｘの形式によっては、ペアリング演算の数を減らすことができない場合もある。
【０１５７】
以上の実施の形態では、ベクトル空間は、符号化部と、秘匿部と、秘密鍵ランダム化部と、暗号文ランダム化部とのための４つの直交する部分空間で構成した。そして、これに対応するため、数１２４に示すように、線形変換Ｘを、ｎ行ｎ列の行列Ｘｉ，ｊ（ｉ，ｊ＝１，．．．，４）を用いて構成した。線形変換Ｘのこの構成は、秘匿部と秘密鍵ランダム化部と暗号文ランダム化部との部分空間が、符号化部の部分空間と同じｎ次元であることを前提としている。
しかし、秘匿部と秘密鍵ランダム化部と暗号文ランダム化部との部分空間は、符号化部の部分空間と同じｎ次元でなくてもよい。例えば、秘匿部の部分空間はｎ×ｕ次元、秘密鍵ランダム化部の部分空間はｎ×ｗ次元、暗号文ランダム化部の部分空間はｎ×ｚ次元（ｕ，ｗ，ｚは０以上の整数）であってもよい。この場合、数１９３に示すように、線形変換Ｘを、ｎ行ｎ列の行列Ｘｉ，ｊ（ｉ，ｊ＝１，．．．，１＋ｕ＋ｗ＋ｚ）を用いて構成すればよい。
【数１９３】
【０１５８】
関数型暗号の一種として、ＩＤベースレボケーション（Ｉｄｅｎｔｉｔｙ−Ｂａｓｅｄ Ｒｅｖｏｃａｔｉｏｎ，ＩＢＲ）やＩＤベースブロードキャスト暗号（Ｉｄｅｎｔｉｔｙ−Ｂａｓｅｄ Ｂｒｏａｄｃａｓｔ Ｅｎｃｒｙｐｔｉｏｎ，ＩＢＢＥ）がある（非特許文献１，５，６，８，１９，１２参照）。
ＩＤベースレボケーションでは、暗号文は識別子の集合Ｓ＝（ＩＤ１，．．．，ＩＤｎ）に対して暗号化され、ＩＤ∈ＳでないＩＤと関連付けられた秘密鍵によって暗号文は復号される。つまり、復号には、ＩＤ∈Ｓでない場合に限り、ＲＩＢＲ（ＩＤ，Ｓ）＝１であることが必要である。
ＩＤベースブロードキャスト暗号では、暗号文は識別子の集合Ｓ＝（ＩＤ１，．．．，ＩＤｎ）に対して暗号化され、ＩＤ∈ＳであるＩＤと関連付けられた秘密鍵によって暗号文は復号される。つまり、復号には、ＩＤ∈Ｓである場合に限り、ＲＩＢＢＥ（ＩＤ，Ｓ）＝１であることが必要である。
【０１５９】
Ｓ：＝｛ＩＤ１，．．．，ＩＤｎ｝である場合に、Ｓ（Ｘ）：＝Σｉ＝０ｎｖｉＸｉ：＝Πｉ＝１ｎ（Ｘ−ＩＤｉ）とする。そして、ベクトルｖ→：＝（ｖ０，ｖ１，．．．，ｖｎ）とし、ベクトルｘ→：＝（１，ＩＤ，．．．，ＩＤｎ）とする。
すると、実施の形態２，３で説明した非零内積暗号方式は、ＩＤベースレボケーション方式となり、実施の形態４，５で説明した零内積暗号方式は、ＩＤベースブロードキャスト暗号方式となる。
つまり、以上の実施の形態で説明した内積暗号方式により、ＩＤベースレボケーション方式及びＩＤベースブロードキャスト暗号方式を実現できる。この場合においても、暗号文又は復号鍵をｎについての定数サイズとすることができ、少ない数のペアリング演算で復号することができる。
【０１６０】
実施の形態２−４で説明した具体的な暗号方式以外にも、非特許文献１３、１５、１６、１７等で説明されている暗号方式に、上述した線形変換Ｘを適用することで、公開パラメータと秘密鍵とのサイズは小さくなる。また、ユーザ鍵の生成や暗号化の処理の処理時間も短くなる。
【０１６１】
図２２は、実施の形態２−４で説明した非零内積暗号方式及び零内積暗号方式と、非特許文献２に記載された非零内積暗号方式及び零内積暗号方式とを比較した図である。
なお、図２２において、｜Ｇ｜、｜ＧＴ｜、｜Ｆｑ｜、Ｐ、Ｍは、それぞれＧのサイズ、ＧＴのサイズ、Ｆｑのサイズ、ペアリング演算、Ｇにおけるスカラー積演算を示している。また、ＣＴ、ＳＫ、ＩＰ、ＤＢＤＨは、それぞれ暗号文、秘密鍵（復号鍵）、内積、決定的双線形Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎを示している。
【０１６２】
実施の形態６．
以上の実施の形態では、双対ベクトル空間において暗号処理を実現する方法について説明した。実施の形態６では、双対加群において暗号処理を実現する方法について説明する。
【０１６３】
つまり、以上の実施の形態では、素数位数ｑの巡回群において暗号処理を実現した。しかし、合成数Ｍを用いて数１９４のように環Ｒを表した場合、環Ｒを係数とする加群においても、上記実施の形態で説明した暗号処理を適用することができる。
【数１９４】
【０１６４】
以上の実施の形態で説明したアルゴリズムにおけるＦｑをＲに変更すれば、双対加群における暗号処理を実現することができる。
【０１６５】
次に、実施の形態における暗号処理システム１０（鍵生成装置１００、暗号化装置２００、復号装置３００）のハードウェア構成について説明する。
図２３は、鍵生成装置１００、暗号化装置２００、復号装置３００、鍵委譲装置４００のハードウェア構成の一例を示す図である。
図２３に示すように、鍵生成装置１００、暗号化装置２００、復号装置３００、鍵委譲装置４００は、プログラムを実行するＣＰＵ９１１（Ｃｅｎｔｒａｌ・Ｐｒｏｃｅｓｓｉｎｇ・Ｕｎｉｔ、中央処理装置、処理装置、演算装置、マイクロプロセッサ、マイクロコンピュータ、プロセッサともいう）を備えている。ＣＰＵ９１１は、バス９１２を介してＲＯＭ９１３、ＲＡＭ９１４、ＬＣＤ９０１（Ｌｉｑｕｉｄ Ｃｒｙｓｔａｌ Ｄｉｓｐｌａｙ）、キーボード９０２（Ｋ／Ｂ）、通信ボード９１５、磁気ディスク装置９２０と接続され、これらのハードウェアデバイスを制御する。磁気ディスク装置９２０（固定ディスク装置）の代わりに、光ディスク装置、メモリカード読み書き装置などの記憶装置でもよい。磁気ディスク装置９２０は、所定の固定ディスクインタフェースを介して接続される。
【０１６６】
ＲＯＭ９１３、磁気ディスク装置９２０は、不揮発性メモリの一例である。ＲＡＭ９１４は、揮発性メモリの一例である。ＲＯＭ９１３とＲＡＭ９１４と磁気ディスク装置９２０とは、記憶装置（メモリ）の一例である。また、キーボード９０２、通信ボード９１５は、入力装置の一例である。また、通信ボード９１５は、通信装置の一例である。さらに、ＬＣＤ９０１は、表示装置の一例である。
【０１６７】
磁気ディスク装置９２０又はＲＯＭ９１３などには、オペレーティングシステム９２１（ＯＳ）、ウィンドウシステム９２２、プログラム群９２３、ファイル群９２４が記憶されている。プログラム群９２３のプログラムは、ＣＰＵ９１１、オペレーティングシステム９２１、ウィンドウシステム９２２により実行される。
【０１６８】
プログラム群９２３には、上記の説明において「マスター鍵生成部１１０」、「マスター鍵記憶部１２０」、「情報入力部１３０」、「復号鍵生成部１４０」、「鍵配布部１５０」、「公開パラメータ取得部２１０」、「情報入力部２２０」、「暗号文生成部２３０」、「データ送信部２４０」、「復号鍵取得部３１０」、「データ受信部３２０」、「ペアリング演算部３３０」、「メッセージ計算部３４０」等として説明した機能を実行するソフトウェアやプログラムやその他のプログラムが記憶されている。プログラムは、ＣＰＵ９１１により読み出され実行される。
ファイル群９２４には、上記の説明において「公開パラメータｐｋ」、「マスター秘密鍵ｓｋ」、「復号鍵ｓｋｖ→」、「暗号文ｃｔｘ→」等の情報やデータや信号値や変数値やパラメータが、「ファイル」や「データベース」の各項目として記憶される。「ファイル」や「データベース」は、ディスクやメモリなどの記録媒体に記憶される。ディスクやメモリなどの記憶媒体に記憶された情報やデータや信号値や変数値やパラメータは、読み書き回路を介してＣＰＵ９１１によりメインメモリやキャッシュメモリに読み出され、抽出・検索・参照・比較・演算・計算・処理・出力・印刷・表示などのＣＰＵ９１１の動作に用いられる。抽出・検索・参照・比較・演算・計算・処理・出力・印刷・表示のＣＰＵ９１１の動作の間、情報やデータや信号値や変数値やパラメータは、メインメモリやキャッシュメモリやバッファメモリに一時的に記憶される。
【０１６９】
また、上記の説明におけるフローチャートの矢印の部分は主としてデータや信号の入出力を示し、データや信号値は、ＲＡＭ９１４のメモリ、その他光ディスク等の記録媒体やＩＣチップに記録される。また、データや信号は、バス９１２や信号線やケーブルその他の伝送媒体や電波によりオンライン伝送される。
また、上記の説明において「〜部」として説明するものは、「〜回路」、「〜装置」、「〜機器」、「〜手段」、「〜機能」であってもよく、また、「〜ステップ」、「〜手順」、「〜処理」であってもよい。また、「〜装置」として説明するものは、「〜回路」、「〜機器」、「〜手段」、「〜機能」であってもよく、また、「〜ステップ」、「〜手順」、「〜処理」であってもよい。さらに、「〜処理」として説明するものは「〜ステップ」であっても構わない。すなわち、「〜部」として説明するものは、ＲＯＭ９１３に記憶されたファームウェアで実現されていても構わない。或いは、ソフトウェアのみ、或いは、素子・デバイス・基板・配線などのハードウェアのみ、或いは、ソフトウェアとハードウェアとの組み合わせ、さらには、ファームウェアとの組み合わせで実施されても構わない。ファームウェアとソフトウェアは、プログラムとして、ＲＯＭ９１３等の記録媒体に記憶される。プログラムはＣＰＵ９１１により読み出され、ＣＰＵ９１１により実行される。すなわち、プログラムは、上記で述べた「〜部」としてコンピュータ等を機能させるものである。あるいは、上記で述べた「〜部」の手順や方法をコンピュータ等に実行させるものである。
【符号の説明】
【０１７０】
１０ 暗号処理システム、１００ 鍵生成装置、１１０ マスター鍵生成部、１１１ 空間生成部、１１２ 行列生成部、１１３ 基底生成部、１１４ 鍵生成部、１２０ マスター鍵記憶部、１３０ 情報入力部、１４０ 復号鍵生成部、１４１ 乱数生成部、１４２ 鍵要素生成部、１５０ 鍵配布部、２００ 暗号化装置、２１０ 公開パラメータ取得部、２２０ 情報入力部、２３０ 暗号文生成部、２３１ 乱数生成部、２３２ 暗号要素生成部、２４０ データ送信部、３００ 復号装置、３１０ 復号鍵取得部、３２０ データ受信部、３３０ ペアリング演算部、３４０ メッセージ計算部。
【技術分野】
【０００１】
この発明は、内積暗号（Ｉｎｎｅｒ−Ｐｒｏｄｕｃｔ Ｅｎｃｒｙｐｔｉｏｎ，ＩＰＥ）に関するものである。
【背景技術】
【０００２】
非特許文献１３，１６，１７には内積暗号についての記載がある。
非特許文献１３，１６，１７に記載された内積暗号では、公開パラメータやマスター秘密鍵は、ベクトル空間の基底で与えられる。
【先行技術文献】
【非特許文献】
【０００３】
【非特許文献１】Ａｂｄａｌｌａ，Ｍ．， Ｋｉｌｔｚ， Ｅ．， Ｎｅｖｅｎ，Ｇ．： Ｇｅｎｅｒａｌｉｚｅｄ ｋｅｙ ｄｅｌｅｇａｔｉｏｎ ｆｏｒ ｈｉｅｒａｒｃｈｉｃａｌ ｉｄｅｎｔｉｔｙ−ｂａｓｅｄ ｅｎｃｒｙｐｔｉｏｎ． ＥＳＯＲＩＣＳ’０７， ＬＮＣＳ ４７３４， ｐｐ． １３９−１５４． Ｓｐｒｉｎｇｅｒ， （２００７）
【非特許文献２】Ａｔｔｒａｐａｄｕｎｇ， Ｎ．， Ｌｉｂｅｒｔ， Ｂ．： Ｆｕｎｃｔｉｏｎａｌ ｅｎｃｒｙｐｔｉｏｎ ｆｏｒ ｉｎｎｅｒ ｐｒｏｄｕｃｔ： Ａｃｈｉｅｖｉｎｇ ｃｏｎｓｔａｎｔ−ｓｉｚｅ ｃｉｐｈｅｒｔｅｘｔｓ ｗｉｔｈ ａｄａｐｔｉｖｅ ｓｅｃｕｒｉｔｙ ｏｒ ｓｕｐｐｏｒｔ ｆｏｒ ｎｅｇａｔｉｏｎ． ＰＫＣ ２０１０． ＬＮＣＳ， ｖｏｌ． ６０５６， ｐｐ． ３８４−４０２． Ｓｐｒｉｎｇｅｒ Ｈｅｉｄｅｌｂｅｒｇ （２０１０）
【非特許文献３】Ａｔｔｒａｐａｄｕｎｇ， Ｎ．， Ｌｉｂｅｒｔ， Ｂ．， Ｄｅ Ｐａｎａｆｉｅｕ， Ｅ．： Ｅｘｐｒｅｓｓｉｖｅ ｋｅｙ−ｐｏｌｉｃｙ ａｔｔｒｉｂｕｔｅ−ｂａｓｅｄ ｅｎｃｒｙｐｔｉｏｎ ｗｉｔｈ ｃｏｎｓｔａｎｔ−ｓｉｚｅ ｃｉｐｈｅｒｔｅｘｔｓ． ＰＫＣ ２０１１． ＬＮＣＳ， ｖｏｌ． ６５７１， ｐｐ． ９０−１０８． Ｓｐｒｉｎｇｅｒ Ｈｅｉｄｅｌｂｅｒｇ （２０１１）
【非特許文献４】Ｂｅｔｈｅｎｃｏｕｒｔ， Ｊ．， Ｓａｈａｉ， Ａ．，Ｗａｔｅｒｓ， Ｂ．： Ｃｉｐｈｅｒｔｅｘｔ−ｐｏｌｉｃｙ ａｔｔｒｉｂｕｔｅ−ｂａｓｅｄ ｅｎｃｒｙｐｔｉｏｎ． Ｉｎ：２００７ ＩＥＥＥ Ｓｙｍｐｏｓｉｕｍ ｏｎ Ｓｅｃｕｒｉｔｙ ａｎｄ Ｐｒｉｖａｃｙ， ｐｐ． ３２１−３３４． ＩＥＥＥ Ｐｒｅｓｓ （２００７）
【非特許文献５】Ｂｏｎｅｈ， Ｄ．， Ｈａｍｂｕｒｇ， Ｍ．： Ｇｅｎｅｒａｌｉｚｅｄ ｉｄｅｎｔｉｔｙ ｂａｓｅｄ ａｎｄ ｂｒｏａｄｃａｓｔ ｅｎｃｒｙｐｔｉｏｎ ｓｃｈｅｍｅ． Ｉｎ：Ｐｉｅｐｒｚｙｋ， Ｊ． （ｅｄ．） ＡＳＩＡＣＲＹＰＴ ２００８． ＬＮＣＳ， ｖｏｌ． ５３５０， ｐｐ． ４５５−４７０． Ｓｐｒｉｎｇｅｒ Ｈｅｉｄｅｌｂｅｒｇ （２００８）
【非特許文献６】Ｄｅｌｅｒａｂｌｅｅ， Ｃ．： Ｉｄｅｎｔｉｔｙ−ｂａｓｅｄ ｂｒｏａｄｃａｓｔ ｅｎｃｒｙｐｔｉｏｎ ｗｉｔｈ ｃｏｎｓｔａｎｔ ｓｉｚｅ ｃｉｐｈｅｒｔｅｘｔｓ ａｎｄ ｐｒｉｖａｔｅ ｋｅｙｓ． Ｉｎ： ＡＳＩＡＣＲＹＰＴ ２００７， ＬＮＣＳ， ｐｐ． ２００−２１５． Ｓｐｒｉｎｇｅｒ−Ｖｅｒｌａｇ （２００７）
【非特許文献７】Ｅｍｕｒａ， Ｋ．， Ｍｉｙａｊｉ， Ａ．， Ｎｏｍｕｒａ， Ａ．， Ｏｍｏｔｅ， Ｋ．， Ｓｏｓｈｉ， Ｍ．： Ａ ｃｉｐｈｅｒｔｅｘｔ−ｐｏｌｉｃｙ ａｔｔｒｉｂｕｔｅ−ｂａｓｅｄ ｅｎｃｒｙｐｔｉｏｎ ｓｃｈｅｍｅ ｗｉｔｈ ｃｏｎｓｔａｎｔ ｃｉｐｈｅｒｔｅｘｔ ｌｅｎｇｔｈ． Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ＩＳＰＥＣ ２００９， ＬＮＣＳ， ｐｐ． １３−２３． Ｓｐｒｉｎｇｅｒ−Ｖｅｒｌａｇ （２００９）
【非特許文献８】Ｇｅｎｔｒｙ， Ｃ．， Ｗａｔｅｒｓ， Ｂ．： Ａｄａｐｔｉｖｅ ｓｅｃｕｒｉｔｙ ｉｎ ｂｒｏａｄｃａｓｔ ｅｎｃｒｙｐｔｉｏｎ ｓｙｓｔｅｍｓ （ｗｉｔｈ ｓｈｏｒｔ ｃｉｐｈｅｒｔｅｘｔｓ）． Ｉｎ： Ｊｏｕｘ， Ａ． （ｅｄ．） ＥＵＲＯＣＲＹＰＴ ２００９． ＬＮＣＳ， ｖｏｌ． ５４７９， ｐｐ． １７１−１８８． Ｓｐｒｉｎｇｅｒ Ｈｅｉｄｅｌｂｅｒｇ （２００９）
【非特許文献９】Ｇｏｙａｌ， Ｖ．， Ｐａｎｄｅｙ， Ｏ．， Ｓａｈａｉ， Ａ．， Ｗａｔｅｒｓ， Ｂ．： Ａｔｔｒｉｂｕｔｅ−ｂａｓｅｄ ｅｎｃｒｙｐｔｉｏｎ ｆｏｒ ｆｉｎｅ−ｇｒａｉｎｅｄ ａｃｃｅｓｓ ｃｏｎｔｒｏｌ ｏｆ ｅｎｃｒｙｐｔｅｄ ｄａｔａ． Ｉｎ： ＡＣＭ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｃｏｍｐｕｔｅｒ ａｎｄ Ｃｏｍｍｕｎｉｃａｔｉｏｎ Ｓｅｃｕｒｉｔｙ ２００６， ｐｐ． ８９−９８， ＡＣＭ （２００６）
【非特許文献１０】Ｈｅｒｒａｎｚ， Ｊ．， Ｌａｇｕｉｌｌａｕｍｉｅ， Ｆ．， Ｒａｆｏｌｓ， Ｃ．： Ｃｏｎｓｔａｎｔ ｓｉｚｅ ｃｉｐｈｅｒｔｅｘｔｓ ｉｎ ｔｈｅｒｅｓｈｏｌｄ ａｔｔｒｉｂｕｔｅ−ｂａｓｅｄ ｅｎｃｒｙｐｔｉｏｎ， Ｉｎ Ｎｇｕｙｅｎ， Ｐ．Ｑ．， Ｐｏｉｎｔｃｈｅｖａｌ， Ｄ． （ｅｄｓ．） ＰＫＣ ２０１０． ＬＮＣＳ， ｖｏｌ． ６０５６， ｐｐ． １９−３４． Ｓｐｒｉｎｇｅｒ Ｈｅｉｄｅｌｂｅｒｇ （２０１０）
【非特許文献１１】Ｋａｔｚ， Ｊ．， Ｓａｈａｉ， Ａ．， Ｗａｔｅｒｓ， Ｂ．： Ｐｒｅｄｉｃａｔｅ ｅｎｃｒｙｐｔｉｏｎ ｓｕｐｐｏｒｔｉｎｇ ｄｉｓｊｕｎｃｔｉｏｎｓ， ｐｏｌｙｎｏｍｉａｌ ｅｑｕａｔｉｏｎｓ， ａｎｄ ｉｎｎｅｒ ｐｒｏｄｕｃｔｓ． Ｉｎ： Ｓｍａｒｔ， Ｎ．Ｐ． （ｅｄ．） ＥＵＲＯＣＲＹＰＴ ２００８． ＬＮＣＳ， ｖｏｌ． ４９６５， ｐｐ． １４６−１６２． Ｓｐｒｉｎｇｅｒ Ｈｅｉｄｅｌｂｅｒｇ （２００８）
【非特許文献１２】Ｌｅｗｋｏ， Ａ．， Ｓａｈａｉ， Ａ．， Ｗａｔｅｒｓ， Ｂ．： Ｒｅｖｏｃａｔｉｏｎ ｓｙｓｔｅｍｓ ｗｉｔｈ ｖｅｒｙ ｓｍａｌｌ ｐｒｉｖａｔｅ ｋｅｙｓ， Ｉｎ ＩＥＥＥ Ｓｙｍｐｏｓｉｕｍ ｏｎ Ｓｅｃｕｒｉｔｙ ａｎｄ Ｐｒｉｖａｃｙ ２０１０ （２０１０）
【非特許文献１３】Ｌｅｗｋｏ， Ａ．， Ｏｋａｍｏｔｏ， Ｔ．， Ｓａｈａｉ， Ａ．， Ｔａｋａｓｈｉｍａ， Ｋ．， Ｗａｔｅｒｓ， Ｂ．： Ｆｕｌｌｙ ｓｅｃｕｒｅ ｆｕｎｃｔｉｏｎａｌ ｅｎｃｒｙｐｔｉｏｎ： Ａｔｔｒｉｂｕｔｅ−ｂａｓｅｄ ｅｎｃｒｙｐｔｉｏｎ ａｎｄ （ｈｉｅｒａｒｃｈｉｃａｌ） ｉｎｎｅｒ ｐｒｏｄｕｃｔ ｅｎｃｒｙｐｔｉｏｎ， ＥＵＲＯＣＲＹＰＴ ２０１０． ＬＮＣＳ， Ｓｐｒｉｎｇｅｒ Ｈｅｉｄｅｌｂｅｒｇ （２０１０） Ｆｕｌｌ ｖｅｒｓｉｏｎ ｉｓ ａｖａｉｌａｂｌｅ ａｔ ｈｔｔｐ：／／ｅｐｒｉｎｔ．ｉａｃｒ．ｏｒｇ／２０１０／１１０
【非特許文献１４】Ｌｅｗｋｏ， Ａ．Ｂ．， Ｗａｔｅｒｓ， Ｂ．： Ｎｅｗ ｔｅｃｈｎｉｑｕｅｓ ｆｏｒ ｄｕａｌ ｓｙｓｔｅｍ ｅｎｃｒｙｐｔｉｏｎ ａｎｄ ｆｕｌｌｙ ｓｅｃｕｒｅ ＨＩＢＥ ｗｉｔｈ ｓｈｏｒｔ ｃｉｐｈｅｒｔｅｘｔｓ． Ｉｎ： Ｍｉｃｃｉａｎｃｉｏ， Ｄ． （ｅｄ．） ＴＣＣ ２０１０． ＬＮＣＳ， ｖｏｌ． ５９７８， ｐｐ． ４５５−４７９． Ｓｐｒｉｎｇｅｒ Ｈｅｉｄｅｌｂｅｒｇ （２０１０）
【非特許文献１５】Ｏｋａｍｏｔｏ， Ｔ．， Ｔａｋａｓｈｉｍａ， Ｋ．： Ｈｏｍｏｍｏｒｐｈｉｃ ｅｎｃｒｙｐｔｉｏｎ ａｎｄ ｓｉｇｎａｔｕｒｅｓ ｆｒｏｍ ｖｅｃｔｏｒ ｄｅｃｏｍｐｏｓｉｔｉｏｎ． Ｉｎ： Ｇａｌｂｒａｉｔｈ， Ｓ．Ｄ．， Ｐａｔｅｒｓｏｎ， Ｋ．Ｇ． （ｅｄｓ．） Ｐａｉｒｉｎｇ ２００８． ＬＮＣＳ， ｖｏｌ． ５２０９， ｐｐ． ５７−７４， Ｓｐｒｉｎｇｅｒ Ｈｅｉｄｅｌｂｅｒｇ （２００８）
【非特許文献１６】Ｏｋａｍｏｔｏ， Ｔ．， Ｔａｋａｓｈｉｍａ， Ｋ．： Ｈｉｅｒａｒｃｈｉｃａｌ ｐｒｅｄｉｃａｔｅ ｅｎｃｒｙｐｔｉｏｎ ｆｏｒ ｉｎｎｅｒ−ｐｒｏｄｕｃｔｓ， Ｉｎ： Ｍａｔｓｕｉ， Ｍ． （ｅｄ．） ＡＳＩＡＣＲＹＰＴ ２００９． ＬＮＣＳ， ｖｏｌ． ５９１２， ｐｐ． ２１４−２３１． Ｓｐｒｉｎｇｅｒ Ｈｅｉｄｅｌｂｅｒｇ （２００９）
【非特許文献１７】Ｏｋａｍｏｔｏ， Ｔ．， Ｔａｋａｓｈｉｍａ， Ｋ．： Ｆｕｌｌｙ ｓｅｃｕｒｅ ｆｕｎｃｔｉｏｎａｌ ｅｎｃｒｙｐｔｉｏｎ ｗｉｔｈ ｇｅｎｅｒａｌ ｒｅｌａｔｉｏｎｓ ｆｒｏｍ ｔｈｅ ｄｅｃｉｓｉｏｎａｌ ｌｉｎｅａｒ ａｓｓｕｍｐｔｉｏｎ． Ｉｎ： Ｒａｂｉｎ， Ｔ． （ｅｄ．） ＣＲＹＰＴＯ ２０１０． ＬＮＣＳ， ｖｏｌ． ６２２３， ｐｐ． １９１−２０８． Ｓｐｒｉｎｇｅｒ Ｈｅｉｄｅｌｂｅｒｇ （２０１０）． Ｆｕｌｌ ｖｅｒｓｉｏｎ ｉｓ ａｖａｉｌａｂｌｅ ａｔ ｈｔｔｐ：／／ｅｐｒｉｎｔ．ｉａｃｒ．ｏｒｇ／２０１０／５６３
【非特許文献１８】Ｓａｈａｉ， Ａ．， Ｗａｔｅｒｓ， Ｂ．： Ｆｕｚｚｙ ｉｄｅｎｔｉｔｙ−ｂａｓｅｄ ｅｎｃｒｙｐｔｉｏｎ． Ｉｎ： Ｃｒａｍｅｒ， Ｒ． （ｅｄ．） ＥＵＲＯＣＲＹＰＴ ２００５． ＬＮＣＳ， ｖｏｌ． ３４９４， ｐｐ． ４５７−４７３． Ｓｐｒｉｎｇｅｒ Ｈｅｉｄｅｌｂｅｒｇ （２００５）
【非特許文献１９】Ｓａｋａｉ， Ｒ．， Ｆｕｒｕｋａｗａ， Ｊ．： Ｉｄｅｎｔｉｔｙ−ｂａｓｅｄ ｂｒｏａｄｃａｓｔ ｅｎｃｒｙｐｔｉｏｎ， ＩＡＣＲ ｅＰｒｉｎｔ Ａｒｃｈｉｖｅ： Ｒｅｐｏｒｔ ２００７／２１７ ｈｔｔｐ：／／ｅｐｒｉｎｔ．ｉａｃｒ．ｏｒｇ／２００７／２１７ （２００７）．
【非特許文献２０】Ｗａｔｅｒｓ， Ｂ．： Ｄｕａｌ ｓｙｓｔｅｍ ｅｎｃｒｙｐｔｉｏｎ： ｒｅａｌｉｚｉｎｇ ｆｕｌｌｙ ｓｅｃｕｒｅ ＩＢＥ ａｎｄ ＨＩＢＥ ｕｎｄｅｒ ｓｉｍｐｌｅ ａｓｓｕｍｐｔｉｏｎｓ． Ｉｎ： Ｈａｌｅｖｉ， Ｓ． （ｅｄ．） ＣＲＹＰＴＯ ２００９． ＬＮＣＳ， ｖｏｌ． ５６７７， ｐｐ． ６１９−６３６． Ｓｐｒｉｎｇｅｒ Ｈｅｉｄｅｌｂｅｒｇ （２００９）
【発明の概要】
【発明が解決しようとする課題】
【０００４】
非特許文献１３，１６，１７に記載された内積暗号では、内積暗号に用いるベクトルの長さをＮとすると、公開パラメータやマスター秘密鍵のサイズはＮ２に比例し、ユーザへ与える秘密鍵の生成や暗号化の処理にＮ２に比例する時間がかかる。
この発明は、公開パラメータやマスター秘密鍵のサイズを小さくするとともに、ユーザへ与える秘密鍵の生成の処理や暗号化の処理にかかる時間を短くすることを目的とする。
【課題を解決するための手段】
【０００５】
この発明に係る暗号処理システムは、
各行各列に少なくとも１つは０以外の値を有する疎行列を用いて所定の基底Ａを変形して生成された基底Ｂと基底Ｂ＊を利用し、暗号処理を行う暗号処理システムであり、
前記基底Ｂにおけるベクトルであって、所定の情報を埋め込んだベクトルを暗号ベクトルとして生成する暗号化装置と、
前記基底Ｂ＊における所定のベクトルを鍵ベクトルとして、前記暗号化装置が生成した暗号ベクトルと前記鍵ベクトルとについて、ペアリング演算を行い前記暗号ベクトルを復号して前記所定の情報に関する情報を抽出する復号装置と
を備えることを特徴とする。
【発明の効果】
【０００６】
この発明に係る暗号処理システムでは、公開パラメータやマスター秘密鍵となる基底Ｂと基底Ｂ＊とを生成するために用いる行列に疎行列を用いる。これにより、公開パラメータやマスター秘密鍵のサイズが小さくなるとともに、ユーザへ与える秘密鍵の生成の処理や暗号化の処理にかかる時間が短くなる。
【図面の簡単な説明】
【０００７】
【図１】零内積暗号方式と非零内積暗号方式とを実行する暗号処理システム１０の構成図。
【図２】ランダムな線形変換Ｘの特別な形式の説明図。
【図３】実施の形態２に係る鍵生成装置１００の構成図。
【図４】実施の形態２に係る暗号化装置２００の構成図。
【図５】実施の形態２に係る復号装置３００の構成図。
【図６】実施の形態２に係るＳｅｔｕｐアルゴリズムの処理を示すフローチャート。
【図７】実施の形態２に係るＫｅｙＧｅｎアルゴリズムの処理を示すフローチャート。
【図８】実施の形態２に係るＥｎｃアルゴリズムの処理を示すフローチャート。
【図９】実施の形態２に係るＤｅｃアルゴリズムの処理を示すフローチャート。
【図１０】実施の形態３に係るＳｅｔｕｐアルゴリズムの処理を示すフローチャート。
【図１１】実施の形態３に係るＫｅｙＧｅｎアルゴリズムの処理を示すフローチャート。
【図１２】実施の形態３に係るＥｎｃアルゴリズムの処理を示すフローチャート。
【図１３】実施の形態３に係るＤｅｃアルゴリズムの処理を示すフローチャート。
【図１４】実施の形態４に係るＳｅｔｕｐアルゴリズムの処理を示すフローチャート。
【図１５】実施の形態４に係るＫｅｙＧｅｎアルゴリズムの処理を示すフローチャート。
【図１６】実施の形態４に係るＥｎｃアルゴリズムの処理を示すフローチャート。
【図１７】実施の形態４に係るＤｅｃアルゴリズムの処理を示すフローチャート。
【図１８】実施の形態５に係るＳｅｔｕｐアルゴリズムの処理を示すフローチャート。
【図１９】実施の形態５に係るＫｅｙＧｅｎアルゴリズムの処理を示すフローチャート。
【図２０】実施の形態５に係るＥｎｃアルゴリズムの処理を示すフローチャート。
【図２１】実施の形態５に係るＤｅｃアルゴリズムの処理を示すフローチャート。
【図２２】実施の形態２−４で説明した非零内積暗号方式及び零内積暗号方式と、非特許文献２に記載された非零内積暗号方式及び零内積暗号方式とを比較した図。
【図２３】鍵生成装置１００、暗号化装置２００、復号装置３００、鍵委譲装置４００のハードウェア構成の一例を示す図。
【発明を実施するための形態】
【０００８】
以下、図に基づき、発明の実施の形態を説明する。
以下の説明において、処理装置は後述するＣＰＵ９１１等である。記憶装置は後述するＲＯＭ９１３、ＲＡＭ９１４、磁気ディスク９２０等である。通信装置は後述する通信ボード９１５等である。入力装置は後述するキーボード９０２、通信ボード９１５等である。出力装置は後述するＲＡＭ９１４、磁気ディスク９２０、通信ボード９１５、ＬＣＤ９０１等である。つまり、処理装置、記憶装置、通信装置、入力装置、出力装置はハードウェアである。
【０００９】
以下の説明における記法について説明する。
Ａがランダムな変数または分布であるとき、数１０１は、Ａの分布に従いＡからｙをランダムに選択することを表す。つまり、数１０１において、ｙは乱数である。
【数１０１】
Ａが集合であるとき、数１０２は、Ａからｙを一様に選択することを表す。つまり、数１０２において、ｙは一様乱数である。
【数１０２】
ベクトル表記は、位数ｑの有限体Ｆｑにおけるベクトル表示を表す。例えば、数１０３である。
【数１０３】
数１０４は、数１０５に示す２つのベクトルｘ→とｖ→との数１０６に示す内積を表す。
【数１０４】
【数１０５】
【数１０６】
ＸＴは、行列Ｘの転置行列を表す。
ｂｉ（ｉ＝１，．．．，ｎ）が空間Ｖのベクトルの要素であるとき、つまり、数１０７であるとき、数１０８は、数１０９によって生成される部分空間を表す。
【数１０７】
【数１０８】
【数１０９】
数１１０に示す基底Ｂと基底Ｂ＊とに対して、数１１１である。
【数１１０】
【数１１１】
ｊ＝１，．．．，ｎのｎ個のベクトルに対して、ｅ→ｊは、数１１２に示す標準基底ベクトルを示す。
【数１１２】
ＧＬ（ｎ，Ｆｑ）は、有限体Ｆｑにおける次数ｎの一般線形群を表す。
【００１０】
また、以下の説明において、ベクトルを意味する“→”が下付き文字又は上付き文字に付されている場合、この“→”は下付き文字又は上付き文字に上付きで付されていることを意味する。同様に、基底Ｂ＊における“＊”が下付き文字又は上付き文字に付されている場合、この“＊”は下付き文字又は上付き文字に上付きで付されていることを意味する。また、同様に、空間Ｖｔにおけるｔが下付き文字又は上付き文字に付されている場合、この“ｔ”は下付き文字又は上付き文字に下付きで付されていることを意味する。
【００１１】
また、以下の説明において、暗号処理とは、暗号化処理、復号処理、鍵生成処理を含むものである。
【００１２】
実施の形態１．
この実施の形態では、内積暗号を実現する基礎となる概念と、内積暗号の構成とについて説明する。
第１に、内積暗号の概念を説明する。
第２に、内積暗号を実現するための空間である双対ペアリングベクトル空間（Ｄｕａｌ Ｐａｉｒｉｎｇ Ｖｅｃｔｏｒ Ｓｐａｃｅｓ，ＤＰＶＳ）を説明する。
第３に、以下の実施の形態で説明する内積暗号方式の基本構成を説明する。
第４に、以下の実施の形態で説明する内積暗号方式を実行する暗号処理システム１０の基本構成を説明する。
第５に、以下の実施の形態で説明する内積暗号方式の基本的な考え方を説明する。
【００１３】
＜第１．内積暗号の概念＞
まず、関数型暗号（Ｆｕｎｃｔｉｏｎａｌ Ｅｎｃｒｙｐｔｉｏｎ）について説明する。
関数型暗号は、進歩した暗号の概念である。また、関数型暗号は、公開鍵暗号（Ｐｕｂｌｉｃ−Ｋｅｙ Ｅｎｃｒｙｐｔｉｏｎ，ＰＫＥ）やＩＤベース暗号（Ｉｄｅｎｔｉｔｙ−Ｂａｓｅｄ Ｅｎｃｒｙｐｔｉｏｎ，ＩＢＥ）の一般化である。関数型暗号システムでは、暗号文を特定するパラメータｙにパラメータｘが適切に関連付けられているなら、受信者はパラメータｘに対応する秘密鍵を用いて暗号文を復号できる。つまり、復号には、ある関係Ｒ（（ｘ，ｙ）に対して成立する関係Ｒ）に対してＲ（ｘ，ｙ）＝１ことが必要である。
【００１４】
内積暗号は、関数型暗号の一種である。
内積暗号には、零内積暗号（Ｚｅｒｏ Ｉｎｎｅｒ Ｐｒｏｄｕｃｔ Ｅｎｃｒｙｐｔｉｏｎ，ＺＩＰＥ）と、非零内積暗号（Ｎｏｎ−ｚｅｒｏ Ｉｎｎｅｒ Ｐｒｏｄｕｃｔ Ｅｎｃｒｙｐｔｉｏｎ，ＮＩＰＥ）とがある。
【００１５】
零内積暗号では、ベクトルｘ→に対して暗号化された暗号文は、ｘ→・ｙ→＝０であるベクトルｙ→と関連付けられた秘密鍵で復号することができる。つまり、ｘ→・ｙ→＝０である場合に限り、ＲＺＩＰＥ（ｘ→，ｙ→）＝１であることが必要である。
【００１６】
非零内積暗号では、ベクトルｘ→に対して暗号化された暗号文は、ｘ→・ｙ→≠０であるベクトルｙ→と関連付けられた秘密鍵で復号することができる。つまり、ｘ→・ｙ→≠０である場合に限り、ＲＮＩＰＥ（ｘ→，ｙ→）＝１であることが必要である。
【００１７】
＜第２．双対ペアリングベクトル空間＞
まず、対称双線形ペアリング群（Ｓｙｍｍｅｔｒｉｃ Ｂｉｌｉｎｅａｒ Ｐａｉｒｉｎｇ Ｇｒｏｕｐｓ）について説明する。
対称双線形ペアリング群（ｑ，Ｇ，ＧＴ，ｇ，ｅ）は、素数ｑと、位数ｑの巡回加法群Ｇと、位数ｑの巡回乗法群ＧＴと、要素ｇ≠０∈Ｇと、多項式時間で計算可能な非退化双線形ペアリング（Ｎｏｎｄｅｇｅｎｅｒａｔｅ Ｂｉｌｉｎｅａｒ Ｐａｉｒｉｎｇ）ｅ：Ｇ×Ｇ→ＧＴとの組である。非退化双線形ペアリングは、ｅ（ｓｇ，ｔｇ）＝ｅ（ｇ，ｇ）ｓｔであり、ｅ（ｇ，ｇ）≠１である。
以下の説明において、Ｇｂｐｇを、１λを入力として、セキュリティパラメータをλとする双線形ペアリング群のパラメータｐａｒａｍＧ：＝（ｑ，Ｇ，ＧＴ，ｇ，ｅ）の値を出力するアルゴリズムとする。
【００１８】
次に、双対ペアリングベクトル空間について説明する。
双対ペアリングベクトル空間（ｑ，Ｖ，ＧＴ，Ａ，ｅ）は、対称双線形ペアリング群（ｐａｒａｍＧ：＝（ｑ，Ｇ，ＧＴ，ｇ，ｅ））の直積によって構成することができる。双対ペアリングベクトル空間（ｑ，Ｖ，ＧＴ，Ａ，ｅ）は、素数ｑ、数１１３に示す有限体Ｆｑ上のＮ次元ベクトル空間Ｖ、位数ｑの巡回群ＧＴ、空間Ｖの標準基底Ａ：＝（ａ１，．．．，ａＮ）の組であり、以下の演算（１）（２）を有する。ここで、ａｉは、数１１４に示す通りである。
【数１１３】
【数１１４】
【００１９】
演算（１）：非退化双線形ペアリング
空間Ｖにおけるペアリングは、数１１５によって定義される。
【数１１５】
これは、非退化双線形である。つまり、ｅ（ｓｘ，ｔｙ）＝ｅ（ｘ，ｙ）ｓｔであり、全てのｙ∈Ｖに対して、ｅ（ｘ，ｙ）＝１の場合、ｘ＝０である。また、全てのｉとｊとに対して、ｅ（ａｉ，ａｊ）＝ｅ（ｇ，ｇ）δｉ，ｊである（このδｉ，ｊはδｉ，ｊを意味する）。ここで、ｉ＝ｊであれば、δｉ，ｊ＝１であり、ｉ≠ｊであれば、δｉ，ｊ＝０である。また、ｅ（ｇ，ｇ）≠１∈ＧＴである。
【００２０】
演算（２）：標準写像
数１１６に示す空間Ｖにおける線形変換φｉ，ｊは、数１１７によって容易に実現することができる。
【数１１６】
【数１１７】
ここで、線形変換φｉ，ｊを標準写像と呼ぶ。
【００２１】
以下の説明において、Ｇｄｐｖｓを、１λ（λ∈自然数）、Ｎ∈自然数を入力として、セキュリティパラメータがλであり、Ｎ次元の空間Ｖとする双対ペアリングベクトル空間のパラメータｐａｒａｍＶ：＝（ｑ，Ｖ，ＧＴ，Ａ，ｅ）の値を出力するアルゴリズムとする。
【００２２】
なお、ここでは、上述した対称双線形ペアリング群により、双対ペアリングベクトル空間を構成した場合について説明する。非対称双線形ペアリング群により双対ペアリングベクトル空間を構成することも可能である。以下の説明を、非対称双線形ペアリング群により双対ペアリングベクトル空間を構成した場合に応用することは容易である。
【００２３】
＜第３．内積暗号方式の基本構成＞
まず、零内積暗号方式について説明する。
零内積暗号方式における関係ＲＺＩＰＥは、ベクトルｘ→∈Ｆｎｑ＼｛０→｝と、ベクトルｖ→∈Ｆｎｑ＼｛０→｝とにおいて定義される。そして、ｘ→・ｖ→＝０である場合に限り、関係ＲＺＩＰＥ（ｘ→，ｖ→）：＝１である。
同様に、非零内積暗号方式における関係ＲＮＩＰＥは、ベクトルｘ→∈Ｆｎｑ＼｛０→｝と、ベクトルｖ→∈Ｆｎｑ＼｛０→｝とにおいて定義される。そして、ｘ→・ｖ→≠０である場合に限り、関係ＲＮＩＰＥ（ｘ→，ｖ→）：＝１である。
【００２４】
零内積暗号方式と非零内積暗号方式とは、Ｓｅｔｕｐ、ＫｅｙＧｅｎ、Ｅｎｃ、Ｄｅｃの４つのアルゴリズムを備える。
（Ｓｅｔｕｐ）
Ｓｅｔｕｐアルゴリズムは、セキュリティパラメータλが入力され、公開パラメータｐｋと、マスター秘密鍵ｓｋとを出力する確率的アルゴリズムである。
（ＫｅｙＧｅｎ）
ＫｅｙＧｅｎアルゴリズムは、ベクトルｖ→と、公開パラメータｐｋと、マスター秘密鍵ｓｋとを入力として、復号鍵ｓｋｖ→を出力する確率的アルゴリズムである。
（Ｅｎｃ）
Ｅｎｃアルゴリズムは、メッセージｍと、ベクトルｘ→と、公開パラメータｐｋとを入力として、暗号文ｃｔｘ→を出力する確率的アルゴリズムである。
（Ｄｅｃ）
Ｄｅｃアルゴリズムは、ベクトルｘ→の下で暗号化された暗号文ｃｔｘ→と、ベクトルｖ→に対する復号鍵ｓｋｖ→と、公開パラメータｐｋとを入力として、メッセージｍ、又は、識別情報⊥を出力するアルゴリズムである。識別情報⊥は、復号できなかったことを示す情報である。
【００２５】
＜第４．暗号処理システム１０の基本構成＞
図１は、零内積暗号方式と非零内積暗号方式とを実行する暗号処理システム１０の構成図である。
鍵生成装置１００は、セキュリティパラメータλを入力としてＳｅｔｕｐアルゴリズムを実行して、公開パラメータｐｋとマスター秘密鍵ｓｋとを生成する。そして、鍵生成装置１００は、生成した公開パラメータｐｋを公開する。また、鍵生成装置１００は、ベクトルｖ→を入力としてＫｅｙＧｅｎアルゴリズムを実行して、復号鍵ｓｋｖ→を生成して復号装置３００へ秘密裡に配布する。
暗号化装置２００は、メッセージｍと、ベクトルｘ→と、公開パラメータｐｋとを入力としてＥｎｃアルゴリズムを実行して、暗号文ｃｔｘ→を生成する。暗号化装置２００は、生成した暗号文ｃｔｘ→を復号装置３００へ送信する。
復号装置３００は、公開パラメータｐｋと、復号鍵ｓｋｖ→と、暗号文ｃｔｘ→とを入力としてＤｅｃアルゴリズムを実行して、メッセージｍ’（＝ｍ）又は識別情報⊥を出力する。
【００２６】
＜第５．暗号方式の基本的な考え方＞
双対ペアリングベクトル空間を暗号処理に適用した典型的なアプリケーションでは、双対基底（又は正規直交基底）のペアである基底Ｂと基底Ｂ＊とが生成される。基底Ｂと基底Ｂ＊とは、ＧＬ（Ｎ，Ｆｑ）から一様に選択された、完全にランダムな線形変換Ｘ（基底変換行列）を用いて生成される。特に、基底Ｂと基底Ｂ＊とは、それぞれ、線形変換Ｘと、（Ｘ−１）Ｔとにより、標準基底Ａを変換して生成される。なお、Ｎは、ｓｐａｎ＜Ｂ＞とｓｐａｎ＜Ｂ＊＞との次元数である。
そして、双対ペアリングベクトル空間を暗号処理に適用した典型的なアプリケーションでは、基底Ｂの一部（Ｂ＾という）が公開パラメータとして用いられ、これに対応する基底Ｂ＊の一部（Ｂ＾＊という）が秘密鍵又はトラップドアとして用いられる。
【００２７】
以下の実施の形態で説明する内積暗号では、上述した完全にランダムな線形変換Ｘに代えて、Ｘ∈ＧＬ（Ｎ，Ｆｑ）であるランダムな線形変換Ｘの特別な形式を用いる。この特別な形式の線形変換Ｘにより、暗号文又は秘密鍵のサイズを小さくすることができるとともに、処理に時間のかかるペアリング演算の数を減らすことができる。
【００２８】
図２は、特別な形式の線形変換Ｘの説明図である。
図２（ａ）は、完全にランダムな線形変換Ｘを示し、図２（ｂ）は、特別な形式の線形変換Ｘを示す。図２（ａ）（ｂ）において、四角が示す部分は成分の値が０以外の乱数であることを示し、図２（ｂ）において、空白部分は成分の値が０であることを示している。また、図２（ｂ）において、斜線が入れられた四角が示す部分は成分の値が同じ値であることを示す。なお、ここでは、Ｎ＝５としている。
図２（ａ）に示すように、従来の線形変換Ｘは、Ｎ２（ここでは、５２＝２５）のサイズであった。これに対して、図２（ｂ）に示すように、以下の実施の形態で説明する内積暗号で用いる線形変換Ｘ（以下、新しい線形変換Ｘ）は、Ｎ＋１（ここでは、５＋１＝６）のサイズである。
【００２９】
上述したように、基底Ｂと基底Ｂ＊とは、線形変換Ｘを用いて標準基底Ａを変換して生成される。そのため、基底Ｂと基底Ｂ＊とのサイズは、線形変換Ｘのサイズに比例する。また、上述したように、基底Ｂと基底Ｂ＊とは、その一部が公開パラメータと秘密鍵にされる。したがって、公開パラメータと秘密鍵とのサイズは、線形変換Ｘのサイズに比例する。つまり、従来の線形変換Ｘを用いた場合、公開パラメータと秘密鍵とのサイズは、Ｎ２に比例する。これに対して、新しい線形変換Ｘを用いた場合、公開パラメータと秘密鍵とのサイズは、Ｎ＋１に比例する。
その結果、従来の線形変換Ｘを用いた場合、ユーザ鍵の生成の処理や暗号化の処理にＮ２に比例した時間がかかっていた。これに対して、新しい線形変換Ｘを用いた場合、ユーザ鍵の生成の処理や暗号化の処理にＮ＋１に比例した時間になる。つまり、新しい線形変換Ｘを用いた場合、計算時間が、Ｎのオーダーになる。
【００３０】
次に、非零内積暗号方式を例として、定数サイズの暗号文と効率的な復号を実現する具体的な方法について説明する。
なお、暗号文のサイズを説明する場合、ベクトルの記述は暗号文の一部に含めないものとする。復号鍵のサイズを説明する場合も同様に、ベクトルの記述は暗号文の一部に含めないものとする。
【００３１】
以下の実施の形態で説明する非零内積暗号方式を簡略化したものを用いて説明する。
簡略化した非零内積暗号方式における暗号文は、２つのベクトル要素（ｃ０，ｃ１）∈Ｇ５×Ｇｎと、ｃ３∈ＧＴとからなる。秘密鍵は、２つのベクトル要素ｋ＊０，ｋ＊１∈Ｇ５×Ｇｎからなる。なお、（ｃ０，ｃ１）∈Ｇ５×Ｇｎとは、ｃ０がＧの５個の要素であり、ｃ１がＧのｎ個の要素であることを意味する。同様に、ｋ＊０，ｋ＊１∈Ｇ５×Ｇｎとは、ｋ＊０がＧの５個の要素であり、ｋ＊１がＧのｎ個の要素であることを意味する。
そのため、暗号文のサイズを定数サイズにするには、ｃ１∈Ｇｎをｎについての定数サイズに圧縮する必要がある。
【００３２】
数１１８に示す特別な線形変換Ｘを用いる。
【数１１８】
ここで、μ，μ’１，．．．，μ’ｎは有限体Ｆｑから一様に選択された値であり、線形変換Ｘにおける空白は定数値０∈Ｆｑであることを示す。定数値０とは、値が０に固定されていることを意味する。つまり、μ，μ’１，．．．，μ’ｎは０も取り得る一様乱数であるのに対して、線形変換Ｘにおける空白は値が０に固定されている。また、Ｈ（ｎ，Ｆｑ）とは、有限体Ｆｑを要素とするｎ次元の行列の集合を意味する。
【００３３】
システムパラメータ又はＤＰＶＳの公開基底は、数１１９に示す基底Ｂである。
【数１１９】
【００３４】
ｘ→：＝（ｘ１，．．．，ｘｎ）に関連付けられた暗号文を、数１２０に示す暗号文ｃ１とする。
【数１２０】
ここで、ωは有限体Ｆｑから一様に選択された値である。
【００３５】
すると、暗号文ｃ１は、数１２１に示す２つのグループの要素Ｃ１，Ｃ２と、ベクトルｘ→とに圧縮できる。
【数１２１】
暗号文ｃ１は、（ｘ１Ｃ１，．．．，ｘｎ−１Ｃ１，Ｃ２）によって得られるためである。なお、ｉ＝１，．．．，ｎ−１の各ｉについて、ｘｉＣ１＝ｘｉωμｇである。
したがって、暗号文（ベクトルｘ→を除いた部分）は、２つのグループの要素とすることができ、ｎについての定数サイズとなる。
【００３６】
Ｂ＊：＝（ｂ＊ｉ）を、Ｂ：＝（ｂｉ）の双対正規直交基底とし、基底Ｂ＊を、簡略化した非零内積暗号方式におけるマスター秘密鍵であるとする。（ｃ０，ｋ＊０，ｃ３）を、ｅ（ｃ０，ｋ＊０）＝ｇＴζ・ｇＴωδであり、ｃ３：＝ｇＴζｍ∈ＧＴであると規定する。また、ベクトルｖ→に対する秘密鍵を、ｋ＊１：＝（δｖ→）Ｂ＊＝δ（ｖ１ｂ＊１＋・・・＋ｖｎｂ＊ｎ）のように設定する。
基底Ｂと基底Ｂ＊との双対正規直交性により、ｅ（ｃ１，ｋ＊１）＝ｇＴωδ（ｘ→・ｖ→）が成立する。そのため、復号者は、ｘ→・ｖ→≠０である場合に限り、ｇＴωδを計算できる。つまり、復号者は、数１２２によりメッセージｍを得ることができる。
【数１２２】
【００３７】
暗号文ｃ１は、（ｘ１Ｃ１，．．．，ｘｎ−１Ｃ１，Ｃ２）∈Ｇｎとして表され、秘密鍵ｋ＊１は、（Ｋ１，．．．，Ｋｎ）のｎ組に分解される。そのため、ｅ（ｃ１，ｋ＊１）の値は、数１２３である。
【数１２３】
【００３８】
つまり、ｅ（ｃ１，ｋ＊１）を計算するには、Ｇにおけるｎ−１個のスカラー乗法と、２つのペアリング演算とで十分である。すなわち、復号には、少ない数（定数）のペアリング演算だけが必要となる。一般に、ペアリング演算は、処理時間がかかる演算であるため、ペアリング演算の数を減らすことにより、処理全体としての処理時間を短くすることができる。
【００３９】
なお、簡略化した非零内積暗号方式では、暗号文ｃ１はベクトルｘ→が設定される基底ベクトル（実際の符号化部）のみを備え、秘密鍵ｋ＊１はベクトルｖ→が設定される基底ベクトル（実際の符号化部）のみを備えた。
以下の実施の形態で説明する非零内積暗号方式では、安全性を高めるため、暗号文ｃ１と秘密鍵ｋ＊１とに、実際の符号化部に加え、秘匿部と、秘密鍵ランダム化部と、暗号文ランダム化部とのための基底ベクトルを加える。
そのため、線形変換Ｘを数１２４のように拡張する。
【数１２４】
ここで、各Ｘｉ，ｊは、数１１８に示すＸ∈Ｈ（ｎ，Ｆｑ）である。そして、ベクトル空間は、４つの直交する部分空間で構成される。つまり、ベクトル空間は、符号化部と、秘匿部と、秘密鍵ランダム化部と、暗号文ランダム化部とのための４つの直交する部分空間で構成される。
【００４０】
実施の形態２．
実施の形態２では、暗号文のサイズを定数サイズとした非零内積暗号方式について説明する。
【００４１】
図３は、実施の形態２に係る鍵生成装置１００の構成図である。図４は、実施の形態２に係る暗号化装置２００の構成図である。図５は、実施の形態２に係る復号装置３００の構成図である。
図６と図７とは、実施の形態２に係る鍵生成装置１００の動作を示すフローチャートである。なお、図６は、実施の形態２に係るＳｅｔｕｐアルゴリズムの処理を示すフローチャートであり、図７は、実施の形態２に係るＫｅｙＧｅｎアルゴリズムの処理を示すフローチャートである。図８は、実施の形態２に係る暗号化装置２００の動作を示すフローチャートであり、実施の形態２に係るＥｎｃアルゴリズムの処理を示すフローチャートである。図９は、実施の形態２に係る復号装置３００の動作を示すフローチャートであり、実施の形態２に係るＤｅｃアルゴリズムの処理を示すフローチャートである。
【００４２】
なお、以下の説明において、入力されるベクトルｘ→：＝（ｘ１，．．．，ｘｎ）は、Ｌ＝１，．．．，ｎ−１の各整数ＬについてｘＬ≠０であり、入力されるベクトルｖ→：＝（ｖ１，．．．，ｖｎ）は、ｖｎ≠０であるとする。
【００４３】
鍵生成装置１００について説明する。
図３に示すように、鍵生成装置１００は、マスター鍵生成部１１０、マスター鍵記憶部１２０、情報入力部１３０、復号鍵生成部１４０、鍵配布部１５０を備える。マスター鍵生成部１１０は、空間生成部１１１、行列生成部１１２、基底生成部１１３、鍵生成部１１４を備える。復号鍵生成部１４０は、乱数生成部１４１、鍵要素生成部１４２を備える。
【００４４】
図６に基づき、Ｓｅｔｕｐアルゴリズムの処理について説明する。
（Ｓ１０１：空間生成ステップ）
空間生成部１１１は、セキュリティパラメータ１λを入力として、処理装置によりＧｂｐｇを実行して、対称双線形ペアリング群のパラメータｐａｒａｍＧ：＝（ｑ，Ｇ，ＧＴ，ｇ，ｅ）を生成する。
さらに、空間生成部１１１は、Ｎ０：＝５、Ｎ１：＝４ｎを設定する。そして、空間生成部１１１は、ｔ＝０，１の各ｔについて、セキュリティパラメータ１λと、Ｎｔと、対称双線形ペアリング群のパラメータｐａｒａｍＧとを入力として、処理装置によりＧｄｐｖｓを実行して、双対ペアリングベクトル空間のパラメータｐａｒａｍＶｔ：＝（ｑ，Ｖｔ，ＧＴ，Ａｔ，ｅ）を生成する。
【００４５】
（Ｓ１０２：線形変換生成ステップ）
行列生成部１１２は、数１２５に示すように、処理装置により線形変換Ｘ０を生成する。
【数１２５】
なお、数１２５における（χ０，ｉ，ｊ）ｉ，ｊ＝１，．．．，５は、行列χ０，ｉ，ｊの添え字ｉ，ｊに関する行列という意味という意味である。
また、行列生成部１１２は、数１２６に示すように、処理装置により線形変換Ｘ１を生成する。
【数１２６】
数１２６におけるＬ（Ｎ，Ｆｑ）は、数１２７に示す通りである。
【数１２７】
なお、以下、｛μｉ，ｊ，μ’ｉ，ｊ，Ｌ｝ｉ，ｊ＝１，．．．，４；Ｌ＝１，．．．，ｎは、線形変換Ｘ１における定数値０以外の要素を示す。
【００４６】
（Ｓ１０３：基底Ｂ生成ステップ）
基底生成部１１３は、数１２８に示すように、処理装置により基底Ｂ０と変数Ｂｉ，ｊと変数Ｂ’ｉ，ｊ，Ｌとを生成する。
【数１２８】
また、基底生成部１１３は、数１２９に示すように、処理装置により基底Ｂ＊０と基底Ｂ＊１とを生成する。
【数１２９】
【００４７】
（Ｓ１０４：基底Ｂ＾生成ステップ）
鍵生成部１１４は、数１３０に示すように、処理装置により基底Ｂ＾０と、基底Ｂ＾＊０と、基底Ｂ＾＊１とを生成する。
【数１３０】
【００４８】
（Ｓ１０５：マスター鍵生成ステップ）
鍵生成部１１４は、処理装置により公開パラメータｐｋ：＝（１λ，ｐａｒａｍｎ，Ｂ＾０，｛Ｂｉ，ｊ，Ｂ’ｉ，ｊ，Ｌ｝ｉ＝１，４；ｊ＝１，．．．，４；Ｌ＝１，．．．，ｎ）とし、マスター秘密鍵ｓｋ：＝｛Ｂ＾＊ｔ｝ｔ＝０，１とする。そして、鍵生成部１１４は、公開パラメータｐｋと、マスター秘密鍵ｓｋとをマスター鍵記憶部１２０に記憶する。
なお、ｐａｒａｍｎ：＝（｛ｐａｒａｍＶｔ｝ｔ＝０，１，ｇＴ）である。
【００４９】
つまり、Ｓ１０１からＳ１０５において、鍵生成装置１００は、数１３１に示すアルゴリズムＧ（１）ｏｂを用いた、数１３２に示すＳｅｔｕｐアルゴリズムを実行して、公開パラメータｐｋとマスター秘密鍵ｓｋとを生成する。
【数１３１】
【数１３２】
なお、公開パラメータは、例えば、ネットワークを介して公開され、暗号化装置２００や復号装置３００が取得可能な状態にされる。
【００５０】
Ｓ１０３では、基底Ｂ１を生成せず、代わりに変数Ｂｉ，ｊを生成した。基底Ｂ１を生成するのであれば、数１３３のようになる。
【数１３３】
数１３３の行列における空白部分は成分の値が０∈Ｇであることを示している。基底Ｂ１は、基底Ｂ＊１の正規直交基底である。つまり、ｅ（ｂ１，ｉ，ｂ＊１，ｊ）＝ｇＴであり、１≦ｉ≠ｊ≦４ｎの整数ｉ，ｊに対して、ｅ（ｂ１，ｉ，ｂ＊１，ｊ）＝１である。
【００５１】
図７に基づき、ＫｅｙＧｅｎアルゴリズムの処理について説明する。
（Ｓ１１１：情報入力ステップ）
情報入力部１３０は、ベクトルｖ→を入力装置により入力する。
【００５２】
（Ｓ１１２：乱数生成ステップ）
乱数生成部１４１は、数１３４に示すように、処理装置により乱数を生成する。
【数１３４】
【００５３】
（Ｓ１１３：要素ｋ＊０生成ステップ）
鍵要素生成部１４２は、数１３５に示すように、処理装置により復号鍵ｓｋｖ→の要素である要素ｋ＊０を生成する。
【数１３５】
なお、上述したように、数１１０に示す基底Ｂと基底Ｂ＊とに対して、数１１１である。したがって、数１３５は、基底Ｂ＊０の基底ベクトルｂ＊０，１の係数としてδを設定し、基底ベクトルｂ＊０，２の係数として０を設定し、基底ベクトルｂ＊０，３の係数として１を設定し、基底ベクトルｂ＊０，４の係数としてφ０を設定し、基底ベクトルｂ＊０，５の係数として０を設定することを意味する。
【００５４】
（Ｓ１１４：要素ｋ＊１生成ステップ）
鍵要素生成部１４２は、数１３６に示すように、処理装置により復号鍵ｓｋｖ→の要素である要素ｋ＊１を生成する。
【数１３６】
数１３６は、数１３５と同様に、基底Ｂ＊１の基底ベクトルｂ＊１，１，．．．，ｂ＊１，ｎの係数としてδｖ１，．．．，δｖｎを設定し、基底ベクトルｂ＊１，ｎ＋１，．．．，ｂ＊１，２ｎの係数として０を設定し、基底ベクトルｂ＊１，２ｎ＋１，．．．，ｂ＊１，３ｎの係数としてφ１ｖ１，．．．，φ１ｖｎを設定し、基底ベクトルｂ＊１，３ｎ＋１，．．．，ｂ＊１，４ｎの係数として０を設定することを意味する。
【００５５】
（Ｓ１１５：鍵配布ステップ）
鍵配布部１５０は、Ｓ１１１で入力したベクトルｖ→と、Ｓ１１３で生成した要素ｋ＊０と、Ｓ１１４で生成した要素ｋ＊１とを要素とする復号鍵ｓｋｖ→を、例えば通信装置によりネットワークを介して秘密裡に復号装置３００へ配布する。もちろん、復号鍵ｓｋｖ→は、他の方法により復号装置３００へ配布されてもよい。
【００５６】
つまり、Ｓ１１１からＳ１１４において、鍵生成装置１００は、数１３７に示すＫｅｙＧｅｎアルゴリズムを実行して、復号鍵ｓｋｖ→を生成する。そして、Ｓ１１５において、鍵生成装置１００は、生成された復号鍵ｓｋｖ→を復号装置３００へ配布する。
【数１３７】
【００５７】
暗号化装置２００について説明する。
図４に示すように、暗号化装置２００は、公開パラメータ取得部２１０、情報入力部２２０、暗号文生成部２３０、データ送信部２４０を備える。暗号文生成部２３０は、乱数生成部２３１、暗号要素生成部２３２を備える。
【００５８】
図８に基づき、Ｅｎｃアルゴリズムの処理について説明する。
（Ｓ１２１：公開パラメータ取得ステップ）
公開パラメータ取得部２１０は、例えば、通信装置によりネットワークを介して、鍵生成装置１００が生成した公開パラメータｐｋを取得する。
【００５９】
（Ｓ１２２：情報入力ステップ）
情報入力部２２０は、ベクトルｘ→を入力装置により入力する。
また、情報入力部２２０は、メッセージｍを入力装置により入力する。
【００６０】
（Ｓ１２３：乱数生成ステップ）
乱数生成部２３１は、数１３８に示すように、処理装置により乱数を生成する。
【数１３８】
【００６１】
（Ｓ１２４：要素ｃ０生成ステップ）
暗号要素生成部２３２は、数１３９に示すように、処理装置により暗号文ｃｔｘ→の要素である要素ｃ０を生成する。
【数１３９】
数１３９は、数１３５と同様に、基底Ｂ０の基底ベクトルｂ０，１の係数として−ωを設定し、基底ベクトルｂ０，２の係数として０を設定し、基底ベクトルｂ０，３の係数としてζを設定し、基底ベクトルｂ０，４の係数として０を設定し、基底ベクトルｂ０，５の係数としてη０を設定することを意味する。
【００６２】
（Ｓ１２５：要素Ｃ生成ステップ）
暗号要素生成部２３２は、数１４０に示すように、処理装置により暗号文ｃｔｘ→の要素である要素Ｃ１，ｊと要素Ｃ２，ｊとを生成する。
【数１４０】
【００６３】
（Ｓ１２６：要素ｃ３生成ステップ）
暗号要素生成部２３２は、数１４１に示すように、処理装置により暗号文ｃｔｘ→の要素である要素ｃ３を生成する。
【数１４１】
【００６４】
（Ｓ１２７：データ送信ステップ）
データ送信部２４０は、Ｓ１２２で入力したベクトルｘ→と、Ｓ１２４で生成した要素ｃ０と、Ｓ１２５で生成した要素Ｃ１，ｊ，Ｃ２，ｊと、Ｓ１２６で生成した要素ｃ３とを要素とする暗号文ｃｔｘ→を、例えば通信装置によりネットワークを介して復号装置３００へ送信する。もちろん、暗号文ｃｔｘ→は、他の方法により復号装置３００へ送信されてもよい。
【００６５】
つまり、Ｓ１２１からＳ１２６において、暗号化装置２００は、数１４２に示すＥｎｃアルゴリズムを実行して、暗号文ｃｔｘ→を生成する。そして、Ｓ１２７において、暗号化装置２００は、生成された暗号文ｃｔｘ→を復号装置３００へ送信する。
【数１４２】
【００６６】
復号装置３００について説明する。
図５に示すように、復号装置３００は、復号鍵取得部３１０、データ受信部３２０、ペアリング演算部３３０、メッセージ計算部３４０を備える。
【００６７】
図９に基づき、Ｄｅｃアルゴリズムの処理について説明する。
（Ｓ１３１：復号鍵取得ステップ）
復号鍵取得部３１０は、例えば、通信装置によりネットワークを介して、鍵生成装置１００から配布されたｓｋｖ→を取得する。
また、復号鍵取得部３１０は、鍵生成装置１００が生成した公開パラメータｐｋを取得する。
【００６８】
（Ｓ１３２：データ受信ステップ）
データ受信部３２０は、例えば、通信装置によりネットワークを介して、暗号化装置２００が送信した暗号文ｃｔｘ→を受信する。
【００６９】
（Ｓ１３３：値Ｄ＊ｊ計算ステップ）
ペアリング演算部３３０は、数１４３に示すように、処理装置により値Ｄ＊ｊを計算する。
【数１４３】
ここで、要素ｋ＊１は、（Ｋ＊１，．．．，Ｋ＊４ｎ）∈Ｇ４ｎの４ｎ組に分解される。
【００７０】
（Ｓ１３４：ペアリング演算ステップ）
ペアリング演算部３３０は、数１４４に示すように、処理装置によりペアリング演算を実行して、値Ｆを計算する。
【数１４４】
【００７１】
（Ｓ１３５：メッセージ計算ステップ）
メッセージ計算部３４０は、数１４５に示すように、処理装置によりメッセージｍ’を計算する。
【数１４５】
【００７２】
つまり、Ｓ１３１からＳ１３５において、復号装置３００は、数１４６に示すＤｅｃアルゴリズムを実行して、メッセージｍ’を計算する。
【数１４６】
【００７３】
なお、数１３３からＢ１：＝（ｂ１，１，．．．，ｂ１，４ｎ）は、｛Ｂｉ，ｊ，Ｂ’ｉ，ｊ，Ｌ｝ｉ，ｊ＝１，．．．，４；Ｌ＝１，．．．，ｎによって特定される。また、Ｓｅｔｕｐアルゴリズムの出力に含まれる｛Ｂｉ，ｊ，Ｂ’ｉ，ｊ，Ｌ｝ｉ＝１，４；ｊ＝１，．．．，４；Ｌ＝１，．．．，ｎは、Ｂ＾１：＝（ｂ１，１，．．．，ｂ１，ｎ，ｂ１，３ｎ＋１，．．．，ｂ１，４ｎ）によって特定される。
そして、Ｄｅｃアルゴリズムは、数１４７に示すＤｅｃ’アルゴリズムのように記述することができる。
【数１４７】
【００７４】
数１４８に示すように、Ｄｅｃ'アルゴリズムを用いた場合、ｘ→・ｖ→≠０であれば、Ｆ＝ｇζＴが得られる。そのため、ｃ３＝ｇζＴｍをＦで除することにより、メッセージｍ’（＝ｍ）が得られる。
【数１４８】
【００７５】
実施の形態２で説明した非零内積暗号方式では、暗号文ｃｔｘ→は、数１３９に示す要素ｃ０で５個と、数１４０に示す、ｊ＝１，．．．，４の各整数ｊについての要素Ｃ１，ｊ及び要素Ｃ２，ｊで８個との合計１３個のＧの要素を含む。また、数１４１に示す要素ｃ３で１個のＧＴの要素を含む。つまり、暗号文ｃｔｘ→は、ｎについて定数サイズである。
【００７６】
また、実施の形態２で説明した非零内積暗号方式では、復号処理（Ｄｅｃアルゴリズム）は、数１４４に示すｅ（ｃ０，ｋ＊０）で５個と、Πｊ＝１４（ｅ（Ｃ１，ｊ，Ｄ＊ｊ）・ｅ（Ｃ２，ｊ，Ｋ＊ｊｎ））で８個との合計１３個のみペアリング演算を実行する。つまり、復号処理は、少ない数のペアリング演算のみ必要となる。
【００７７】
実施の形態３．
実施の形態３では、秘密鍵のサイズを定数サイズとした非零内積暗号方式について説明する。
【００７８】
鍵生成装置１００、暗号化装置２００、復号装置３００の構成は、それぞれ図３、図４、図５に示す実施の形態２に係る鍵生成装置１００、暗号化装置２００、復号装置３００の構成と同一である。
図１０と図１１とは、実施の形態３に係る鍵生成装置１００の動作を示すフローチャートである。なお、図１０は、実施の形態３に係るＳｅｔｕｐアルゴリズムの処理を示すフローチャートであり、図１１は、実施の形態３に係るＫｅｙＧｅｎアルゴリズムの処理を示すフローチャートである。図１２は、実施の形態３に係る暗号化装置２００の動作を示すフローチャートであり、実施の形態３に係るＥｎｃアルゴリズムの処理を示すフローチャートである。図１３は、実施の形態３に係る復号装置３００の動作を示すフローチャートであり、実施の形態３に係るＤｅｃアルゴリズムの処理を示すフローチャートである。
【００７９】
なお、以下の説明において、入力されるベクトルｖ→：＝（ｖ１，．．．，ｖｎ）は、Ｌ＝１，．．．，ｎ−１の各整数ＬについてｖＬ≠０であり、入力されるベクトルｘ→：＝（ｘ１，．．．，ｘｎ）は、ｘｎ≠０であるとする。
【００８０】
鍵生成装置１００について説明する。
図１０に基づき、Ｓｅｔｕｐアルゴリズムの処理について説明する。
Ｓ２０１からＳ２０２までの処理は、図６に示すＳ１０１からＳ１０２までの処理と同じである。
【００８１】
（Ｓ２０３：基底Ｂ生成ステップ）
基底生成部１１３は、実施の形態２における基底Ｂ０と変数Ｂｉ，ｊと同様に、数１４９に示すように、処理装置により基底Ｄ０と変数Ｄｉ，ｊと変数Ｄ’ｉ，ｊ，Ｌとを生成する。
【数１４９】
また、基底生成部１１３は、実施の形態２における基底Ｂ＊０と基底Ｂ＊１と同様に、数１５０に示すように、処理装置により基底Ｄ＊０と基底Ｄ＊１とを生成する。
【数１５０】
そして、基底生成部１１３は、基底Ｄ＊０を基底Ｂ０とし、基底Ｄ０を基底Ｂ＊０とし、基底Ｄ＊１を基底Ｂ１とする。また、基底生成部１１３は、ｉ，ｊ＝１，．．．，４の各整数ｉ，ｊと、Ｌ＝１，．．．，ｎの各整数Ｌとについて、変数Ｄｉ，ｊを変数Ｂ＊ｉ，ｊとし、変数Ｄ’ｉ，ｊ，Ｌを変数Ｂ’＊ｉ，ｊ，Ｌとする。
【００８２】
（Ｓ２０４：基底Ｂ＾生成ステップ）
鍵生成部１１４は、数１５１に示すように、処理装置により基底Ｂ＾０と、基底Ｂ＾１と、基底Ｂ＾＊０とを生成する。
【数１５１】
【００８３】
（Ｓ２０５：マスター鍵生成ステップ）
鍵生成部１１４は、処理装置により公開パラメータｐｋ：＝（１λ，ｐａｒａｍｎ，｛Ｂ＾ｔ｝ｔ＝０，１）とし、マスター秘密鍵ｓｋ：＝Ｂ＾＊０，｛Ｂ＊ｉ，ｊ，Ｂ’＊ｉ，ｊ，Ｌ｝ｉ＝１，３；ｊ＝１，．．．，４；Ｌ＝１，．．．，ｎとする。そして、鍵生成部１１４は、公開パラメータｐｋと、マスター秘密鍵ｓｋとをマスター鍵記憶部１２０に記憶する。
なお、ｐａｒａｍｎ：＝（｛ｐａｒａｍＶｔ｝ｔ＝０，１，ｇＴ）である。
【００８４】
つまり、Ｓ２０１からＳ２０５において、鍵生成装置１００は、数１５２に示すアルゴリズムＧ（２）ｏｂを用いた、数１５３に示すＳｅｔｕｐアルゴリズムを実行して、公開パラメータｐｋとマスター秘密鍵ｓｋとを生成する。ここで、数１５２に示すように、アルゴリズムＧ（２）ｏｂは、数１３１に示すアルゴリズムＧ（１）ｏｂを用いる。
【数１５２】
【数１５３】
なお、公開パラメータは、例えば、ネットワークを介して公開され、暗号化装置２００や復号装置３００が取得可能な状態にされる。
【００８５】
図１１に基づき、ＫｅｙＧｅｎアルゴリズムの処理について説明する。
Ｓ２１１からＳ２１３までの処理は、図７に示すＳ１１１からＳ１１３までの処理と同じである。
【００８６】
（Ｓ２１４：要素Ｋ＊生成ステップ）
鍵要素生成部１４２は、数１５４に示すように、処理装置により復号鍵ｓｋｖ→の要素である要素Ｋ＊１，ｊと要素Ｋ＊２，ｊとを生成する。
【数１５４】
【００８７】
（Ｓ２１５：鍵配布ステップ）
鍵配布部１５０は、Ｓ２１１で入力したベクトルｖ→と、Ｓ２１３で生成した要素ｋ＊０と、Ｓ２１４で生成した要素Ｋ＊１，ｊ，Ｋ＊２，ｊとを要素とする復号鍵ｓｋｖ→を、例えば通信装置によりネットワークを介して秘密裡に復号装置３００へ配布する。もちろん、復号鍵ｓｋｖ→は、他の方法により復号装置３００へ配布されてもよい。
【００８８】
つまり、Ｓ２１１からＳ２１４において、鍵生成装置１００は、数１５５に示すＫｅｙＧｅｎアルゴリズムを実行して、復号鍵ｓｋｖ→を生成する。そして、Ｓ２１５において、鍵生成装置１００は、生成された復号鍵ｓｋｖ→を復号装置３００へ配布する。
【数１５５】
【００８９】
暗号化装置２００について説明する。
図１２に基づき、Ｅｎｃアルゴリズムの処理について説明する。
Ｓ２２１からＳ２２４までの処理は、図８に示すＳ１２１からＳ１２４までの処理と同じである。
【００９０】
（Ｓ２２５：要素ｃ１生成ステップ）
暗号要素生成部２３２は、数１５６に示すように、処理装置により暗号文ｃｔｘ→の要素である要素ｃ１を生成する。
【数１５６】
数１５６は、数１３５と同様に、基底Ｂ１の基底ベクトルｂ＊１，１，．．．，ｂ＊１，ｎの係数としてωｘ１，．．．，ωｘｎを設定し、基底ベクトルｂ＊１，ｎ＋１，．．．，ｂ＊１，３ｎの係数として０を設定し、基底ベクトルｂ＊１，３ｎ＋１，．．．，ｂ＊１，４ｎの係数としてη１ｘ１，．．．，η１ｘｎを設定することを意味する。
【００９１】
Ｓ２２６の処理は、図８に示すＳ１２６の処理と同じである。
【００９２】
（Ｓ２２７：データ送信ステップ）
データ送信部２４０は、Ｓ２２２で入力したベクトルｘ→と、Ｓ２２４で生成した要素ｃ０と、Ｓ２２５で生成した要素ｃ１と、Ｓ２２６で生成した要素ｃ３とを要素とする暗号文ｃｔｘ→を、例えば通信装置によりネットワークを介して復号装置３００へ送信する。もちろん、暗号文ｃｔｘ→は、他の方法により復号装置３００へ送信されてもよい。
【００９３】
つまり、Ｓ２２１からＳ２２６において、暗号化装置２００は、数１５７に示すＥｎｃアルゴリズムを実行して、暗号文ｃｔｘ→を生成する。そして、Ｓ２２７において、暗号化装置２００は、生成された暗号文ｃｔｘ→を復号装置３００へ送信する。
【数１５７】
【００９４】
復号装置３００について説明する。
図１３に基づき、Ｄｅｃアルゴリズムの処理について説明する。
Ｓ２３１からＳ２３２までの処理は、図９に示すＳ１３１からＳ１３２までの処理と同じである。
【００９５】
（Ｓ２３３：値Ｄｊ計算ステップ）
ペアリング演算部３３０は、数１５８に示すように、処理装置により値Ｄｊを計算する。
【数１５８】
ここで、要素ｃ１は、（Ｃ１，．．．，Ｃ４ｎ）∈Ｇ４ｎの４ｎ組に分解される。
【００９６】
（Ｓ２３４：ペアリング演算ステップ）
ペアリング演算部３３０は、数１５９に示すように、処理装置によりペアリング演算を実行して、値Ｆを計算する。
【数１５９】
【００９７】
Ｓ２３５の処理は、図９に示すＳ１３５の処理と同じである。
【００９８】
つまり、Ｓ２３１からＳ２３５において、復号装置３００は、数１６０に示すＤｅｃアルゴリズムを実行して、メッセージｍ’を計算する。
【数１６０】
【００９９】
なお、Ｂ＊１：＝（ｂ＊１，１，．．．，ｂ＊１，４ｎ）は、｛Ｂ＊ｉ，ｊ，Ｂ’＊ｉ，ｊ，Ｌ｝ｉ，ｊ＝１，．．．，４；Ｌ＝１，．．．，ｎによって特定される。また、Ｓｅｔｕｐアルゴリズムの出力に含まれる｛Ｂ＊ｉ，ｊ，Ｂ’＊ｉ，ｊ，Ｌ｝ｉ＝１，３；ｊ＝１，．．．，４；Ｌ＝１，．．．，ｎは、Ｂ＾＊１：＝（ｂ＊１，１，．．．，ｂ＊１，ｎ，ｂ＊１，２ｎ＋１，．．．，ｂ＊１，３ｎ）によって特定される。
そして、Ｄｅｃアルゴリズムは、数１６１に示すＤｅｃ’アルゴリズムのように記述することができる。
【数１６１】
【０１００】
実施の形態３で説明した非零内積暗号方式では、復号鍵ｓｋｖ→は、数１３５に示す要素ｋ＊０で５個と、数１５４に示す、ｊ＝１，．．．，４の各整数ｊについての要素Ｋ＊１，ｊ及び要素Ｋ＊２，ｊで８個との合計１３個のＧの要素を含む。つまり、復号鍵ｓｋｖ→は、ｎについて定数サイズである。
【０１０１】
また、実施の形態３で説明した非零内積暗号方式では、復号処理（Ｄｅｃアルゴリズム）は、数１５９に示すｅ（ｃ０，ｋ＊０）で５個と、Πｊ＝１４（ｅ（Ｄｊ，Ｋ＊１，ｊ）・ｅ（Ｃｊｎ，Ｋ＊２，ｊ））で８個との合計１３個のみペアリング演算を実行する。つまり、復号処理は、少ない数のペアリング演算のみ必要となる。
【０１０２】
実施の形態４．
実施の形態４では、暗号文のサイズを定数サイズとした零内積暗号方式について説明する。
【０１０３】
鍵生成装置１００、暗号化装置２００、復号装置３００の構成は、それぞれ図３、図４、図５に示す実施の形態２に係る鍵生成装置１００、暗号化装置２００、復号装置３００の構成と同一である。
図１４と図１５とは、実施の形態４に係る鍵生成装置１００の動作を示すフローチャートである。なお、図１４は、実施の形態４に係るＳｅｔｕｐアルゴリズムの処理を示すフローチャートであり、図１５は、実施の形態４に係るＫｅｙＧｅｎアルゴリズムの処理を示すフローチャートである。図１６は、実施の形態４に係る暗号化装置２００の動作を示すフローチャートであり、実施の形態４に係るＥｎｃアルゴリズムの処理を示すフローチャートである。図１７は、実施の形態４に係る復号装置３００の動作を示すフローチャートであり、実施の形態４に係るＤｅｃアルゴリズムの処理を示すフローチャートである。
【０１０４】
なお、以下の説明において、入力されるベクトルｘ→：＝（ｘ１，．．．，ｘｎ）は、Ｌ＝１，．．．，ｎ−１の各整数ＬについてｘＬ≠０であり、入力されるベクトルｖ→：＝（ｖ１，．．．，ｖｎ）は、ｖｎ≠０であるとする。
【０１０５】
鍵生成装置１００について説明する。
図１４に基づき、Ｓｅｔｕｐアルゴリズムの処理について説明する。
（Ｓ３０１：空間生成ステップ）
空間生成部１１１は、セキュリティパラメータ１λを入力として、処理装置によりＧｂｐｇを実行して、対称双線形ペアリング群のパラメータｐａｒａｍＧ：＝（ｑ，Ｇ，ＧＴ，ｇ，ｅ）を生成する。
さらに、空間生成部１１１は、Ｎ：＝４ｎ＋１を設定する。そして、空間生成部１１１は、セキュリティパラメータ１λと、Ｎと、対称双線形ペアリング群のパラメータｐａｒａｍＧとを入力として、処理装置によりＧｄｐｖｓを実行して、双対ペアリングベクトル空間のパラメータｐａｒａｍＶｔ：＝（ｑ，Ｖ，ＧＴ，Ａ，ｅ）を生成する。
【０１０６】
（Ｓ３０２：線形変換生成ステップ）
行列生成部１１２は、数１６２に示すように、処理装置により線形変換Ｘを生成する。
【数１６２】
数１６２におけるＬ’（Ｎ，Ｆｑ）は、数１６３に示す通りである。
【数１６３】
なお、以下、｛χ０，０，χ０，ｊ，χｉ，０，Ｌ，μｉ，ｊ，μ’ｉ，ｊ，Ｌ｝ｉ，ｊ＝１，．．．，４；Ｌ＝１，．．．，ｎは、線形変換Ｘにおける定数値０以外の要素を示す。
【０１０７】
（Ｓ３０３：基底Ｂ生成ステップ）
基底生成部１１３は、数１６４に示すように、処理装置により変数Ｂ０，０と変数Ｂ０，ｊと変数Ｂｉ，０，Ｌと変数Ｂｉ，ｊと変数Ｂ’ｉ，ｊ，Ｌとを生成する。
【数１６４】
また、基底生成部１１３は、数１６５に示すように、処理装置により基底Ｂ＊を生成する。
【数１６５】
【０１０８】
（Ｓ３０４：基底Ｂ＾生成ステップ）
鍵生成部１１４は、数１６６に示すように、処理装置により基底Ｂ＾＊を生成する。
【数１６６】
【０１０９】
（Ｓ３０５：マスター鍵生成ステップ）
鍵生成部１１４は、処理装置により公開パラメータｐｋ：＝（１λ，ｐａｒａｍｎ，Ｂ＾０，｛Ｂ０，０，Ｂ０，ｊ，Ｂｉ，０，Ｌ，Ｂｉ，ｊ，Ｂ’ｉ，ｊ，Ｌ｝ｉ＝１，４；ｊ＝１，．．．，４；Ｌ＝１，．．．，ｎ）とし、マスター秘密鍵ｓｋ：＝Ｂ＾＊とする。そして、鍵生成部１１４は、公開パラメータｐｋと、マスター秘密鍵ｓｋとをマスター鍵記憶部１２０に記憶する。
なお、ｐａｒａｍｎ：＝（ｐａｒａｍＶ，ｇＴ）である。
【０１１０】
つまり、Ｓ３０１からＳ３０５において、鍵生成装置１００は、数１６７に示すアルゴリズムＧ（３）ｏｂを用いた、数１６８に示すＳｅｔｕｐアルゴリズムを実行して、公開パラメータｐｋとマスター秘密鍵ｓｋとを生成する。
【数１６７】
【数１６８】
なお、公開パラメータは、例えば、ネットワークを介して公開され、暗号化装置２００や復号装置３００が取得可能な状態にされる。
【０１１１】
図１５に基づき、ＫｅｙＧｅｎアルゴリズムの処理について説明する。
Ｓ３１１の処理は、図７に示すＳ１１１の処理と同じである。
【０１１２】
（Ｓ３１２：乱数生成ステップ）
乱数生成部１４１は、数１６９に示すように、処理装置により乱数を生成する。
【数１６９】
【０１１３】
（Ｓ３１３：要素ｋ＊生成ステップ）
鍵要素生成部１４２は、数１７０に示すように、処理装置により復号鍵ｓｋｖ→の要素である要素ｋ＊を生成する。
【数１７０】
数１７０は、数１３５と同様に、基底Ｂ＊の基底ベクトルｂ＊０の係数として１を設定し、基底ベクトルｂ＊１，．．．，ｂ＊ｎの係数としてδｖ１，．．．，δｖｎを設定し、基底ベクトルｂ＊ｎ＋１，．．．，ｂ＊２ｎの係数として０を設定し、基底ベクトルｂ＊２ｎ＋１，．．．，ｂ＊３ｎの係数としてφｖ１，．．．，φｖｎを設定し、基底ベクトルｂ＊３ｎ＋１，．．．，ｂ＊４ｎの係数として０を設定することを意味する。
【０１１４】
（Ｓ３１４：鍵配布ステップ）
鍵配布部１５０は、Ｓ３１３で生成した要素ｋ＊を要素とする復号鍵ｓｋｖ→を、例えば通信装置によりネットワークを介して秘密裡に復号装置３００へ配布する。もちろん、復号鍵ｓｋｖ→は、他の方法により復号装置３００へ配布されてもよい。
【０１１５】
つまり、Ｓ３１１からＳ３１３において、鍵生成装置１００は、数１７１に示すＫｅｙＧｅｎアルゴリズムを実行して、復号鍵ｓｋｖ→を生成する。そして、Ｓ３１４において、鍵生成装置１００は、生成された復号鍵ｓｋｖ→を復号装置３００へ配布する。
【数１７１】
【０１１６】
暗号化装置２００について説明する。
図１６に基づき、Ｅｎｃアルゴリズムの処理について説明する。
Ｓ３２１からＳ３２２までの処理は、図８に示すＳ１２１からＳ１２２までの処理と同じである。
【０１１７】
（Ｓ３２３：乱数生成ステップ）
乱数生成部２３１は、数１７２に示すように、処理装置により乱数を生成する。
【数１７２】
【０１１８】
（Ｓ３２４：要素Ｃ生成ステップ）
暗号要素生成部２３２は、数１７３に示すように、処理装置により暗号文ｃｔｘ→の要素である要素Ｃ０と要素Ｃ１，ｊと要素Ｃ２，ｊとを生成する。
【数１７３】
【０１１９】
Ｓ３２５の処理は、図８に示すＳ１２６の処理と同じである。
【０１２０】
（Ｓ３２６：データ送信ステップ）
データ送信部２４０は、Ｓ３２２で入力したベクトルｘ→と、Ｓ３２４で生成した要素Ｃ０，Ｃ１，ｊ，Ｃ２，ｊと、Ｓ３２５で生成した要素ｃ３とを要素とする暗号文ｃｔｘ→を、例えば通信装置によりネットワークを介して復号装置３００へ送信する。もちろん、暗号文ｃｔｘ→は、他の方法により復号装置３００へ送信されてもよい。
【０１２１】
つまり、Ｓ３２１からＳ３２５において、暗号化装置２００は、数１７４に示すＥｎｃアルゴリズムを実行して、暗号文ｃｔｘ→を生成する。そして、Ｓ３２６において、暗号化装置２００は、生成された暗号文ｃｔｘ→を復号装置３００へ送信する。
【数１７４】
【０１２２】
復号装置３００について説明する。
図１７に基づき、Ｄｅｃアルゴリズムの処理について説明する。
Ｓ３３１からＳ３３２までの処理は、図９に示すＳ１３１からＳ１３２までの処理と同じである。
【０１２３】
（Ｓ３３３：値Ｄ＊ｊ計算ステップ）
ペアリング演算部３３０は、数１７５に示すように、処理装置により値Ｄ＊ｊを計算する。
【数１７５】
ここで、要素ｋ＊は、（Ｋ＊０，．．．，Ｋ＊４ｎ）∈Ｇ４ｎ＋１の（４ｎ＋１）組に分解される。
【０１２４】
（Ｓ３３４：ペアリング演算ステップ）
ペアリング演算部３３０は、数１７６に示すように、処理装置によりペアリング演算を実行して、値Ｆを計算する。
【数１７６】
【０１２５】
Ｓ３３５の処理は、図９に示すＳ１３５の処理と同じである。
【０１２６】
つまり、Ｓ３３１からＳ３３５において、復号装置３００は、数１７７に示すＤｅｃアルゴリズムを実行して、メッセージｍ’を計算する。
【数１７７】
【０１２７】
なお、Ｂ：＝（ｂ０，．．．，ｂ４ｎ）は、｛Ｂ０，０，Ｂ０，ｊ，Ｂｉ，０，Ｌ，Ｂｉ，ｊ，Ｂ’ｉ，ｊ，Ｌ｝ｉ，ｊ＝１，．．．，４；Ｌ＝１，．．．，ｎによって特定される。また、Ｓｅｔｕｐアルゴリズムの出力に含まれる｛Ｂ０，０，Ｂ０，ｊ，Ｂｉ，０，Ｌ，Ｂｉ，ｊ，Ｂ’ｉ，ｊ，Ｌ｝ｉ＝１，４；ｊ＝１，．．．，４；Ｌ＝１，．．．，ｎは、Ｂ＾：＝（ｂ０，．．．，ｂｎ，ｂ３ｎ＋１，．．．，ｂ４ｎ）によって特定される。
そして、Ｄｅｃアルゴリズムは、数１７８に示すＤｅｃ’アルゴリズムのように記述することができる。
【数１７８】
【０１２８】
数１７９に示すように、Ｄｅｃ'アルゴリズムを用いた場合、ｘ→・ｖ→＝０であれば、Ｆ＝ｇζＴが得られる。そのため、ｃ３＝ｇζＴｍをＦで除することにより、メッセージｍ’（＝ｍ）が得られる。
【数１７９】
【０１２９】
実施の形態４で説明した零内積暗号方式では、暗号文ｃｔｘ→は、数１７３に示す要素Ｃ０で１個と、ｊ＝１，．．．，４の各整数ｊについての要素Ｃ１，ｊ及び要素Ｃ２，ｊで８個との合計９個のＧの要素を含む。また、要素ｃ３で１個のＧＴの要素を含む。つまり、暗号文ｃｔｘ→は、ｎについて定数サイズである。
【０１３０】
また、実施の形態４で説明した零内積暗号方式では、復号処理（Ｄｅｃアルゴリズム）は、数１７６に示すｅ（Ｃ０，Ｋ＊０）で１個と、Πｊ＝１４（ｅ（Ｃ１，ｊ，Ｄ＊ｊ）・ｅ（Ｃ２，ｊ，Ｋ＊ｊｎ））で８個との合計９個のみペアリング演算を実行する。つまり、復号処理は、少ない数のペアリング演算のみ必要となる。
【０１３１】
実施の形態５．
実施の形態５では、秘密鍵のサイズを定数サイズとした零内積暗号方式について説明する。
【０１３２】
鍵生成装置１００、暗号化装置２００、復号装置３００の構成は、それぞれ図３、図４、図５に示す実施の形態２に係る鍵生成装置１００、暗号化装置２００、復号装置３００の構成と同一である。
図１８と図１９とは、実施の形態５に係る鍵生成装置１００の動作を示すフローチャートである。なお、図１８は、実施の形態５に係るＳｅｔｕｐアルゴリズムの処理を示すフローチャートであり、図１９は、実施の形態５に係るＫｅｙＧｅｎアルゴリズムの処理を示すフローチャートである。図２０は、実施の形態５に係る暗号化装置２００の動作を示すフローチャートであり、実施の形態５に係るＥｎｃアルゴリズムの処理を示すフローチャートである。図２１は、実施の形態５に係る復号装置３００の動作を示すフローチャートであり、実施の形態５に係るＤｅｃアルゴリズムの処理を示すフローチャートである。
【０１３３】
なお、以下の説明において、入力されるベクトルｖ→：＝（ｖ１，．．．，ｖｎ）は、Ｌ＝１，．．．，ｎ−１の各整数ＬについてｖＬ≠０であり、入力されるベクトルｘ→：＝（ｘ１，．．．，ｘｎ）は、ｘｎ≠０であるとする。
【０１３４】
鍵生成装置１００について説明する。
図１８に基づき、Ｓｅｔｕｐアルゴリズムの処理について説明する。
Ｓ４０１からＳ４０２までの処理は、図１４に示すＳ３０１からＳ３０２までの処理と同じである。
【０１３５】
（Ｓ４０３：基底Ｂ生成ステップ）
基底生成部１１３は、実施の形態４における変数Ｂ０，０と変数Ｂ０，ｊと変数Ｂｉ，０，Ｌと変数Ｂｉ，ｊと変数Ｂ’ｉ，ｊ，Ｌと同様に、数１８０に示すように、処理装置により変数Ｄ０，０と変数Ｄ０，ｊと変数Ｄｉ，０，Ｌと変数Ｄｉ，ｊと変数Ｄ’ｉ，ｊ，Ｌとを生成する。
【数１８０】
また、基底生成部１１３は、実施の形態４における基底Ｂ＊と同様に、数１８１に示すように、処理装置により基底Ｄ＊を生成する。
【数１８１】
そして、基底生成部１１３は、基底Ｄ＊を基底Ｂとする。また、基底生成部１１３は、ｉ，ｊ＝１，．．．，４の各整数ｉ，ｊと、Ｌ＝１，．．．，ｎの各整数Ｌとについて、変数Ｄ０，０を変数Ｂ＊０，０とし、変数Ｄ０，ｊを変数Ｂ＊０，ｊとし、変数Ｄｉ，０，Ｌを変数Ｂ＊ｉ，０，Ｌとし、変数Ｄｉ，ｊを変数Ｂ＊ｉ，ｊとし、変数Ｄ’ｉ，ｊ，Ｌを変数Ｂ’＊ｉ，ｊ，Ｌとする。
【０１３６】
（Ｓ４０４：基底Ｂ＾生成ステップ）
鍵生成部１１４は、数１８２に示すように、処理装置により基底Ｂ＾を生成する。
【数１８２】
【０１３７】
（Ｓ４０５：マスター鍵生成ステップ）
鍵生成部１１４は、処理装置により公開パラメータｐｋ：＝（１λ，ｐａｒａｍｎ，Ｂ＾）とし、マスター秘密鍵ｓｋ：＝（｛Ｂ＊０，０，Ｂ＊０，ｊ，Ｂ＊ｉ，０，Ｌ，Ｂ＊ｉ，ｊ，Ｂ’＊ｉ，ｊ，Ｌ｝ｉ＝１，３；ｊ＝１，．．．，４；Ｌ＝１，．．．，ｎ）とする。そして、鍵生成部１１４は、公開パラメータｐｋと、マスター秘密鍵ｓｋとをマスター鍵記憶部１２０に記憶する。
なお、ｐａｒａｍｎ：＝（ｐａｒａｍＶ，ｇＴ）である。
【０１３８】
つまり、Ｓ４０１からＳ４０５において、鍵生成装置１００は、数１８３に示すアルゴリズムＧ（４）ｏｂを用いた、数１８４に示すＳｅｔｕｐアルゴリズムを実行して、公開パラメータｐｋとマスター秘密鍵ｓｋとを生成する。ここで、数１８３に示すように、アルゴリズムＧ（４）ｏｂは、数１６７に示すアルゴリズムＧ（３）ｏｂを用いる。
【数１８３】
【数１８４】
なお、公開パラメータは、例えば、ネットワークを介して公開され、暗号化装置２００や復号装置３００が取得可能な状態にされる。
【０１３９】
図１９に基づき、ＫｅｙＧｅｎアルゴリズムの処理について説明する。
Ｓ４１１からＳ４１２までの処理は、図１５に示すＳ３１１からＳ３１２までの処理と同じである。
【０１４０】
（Ｓ４１３：要素Ｋ＊生成ステップ）
鍵要素生成部１４２は、数１８５に示すように、処理装置により復号鍵ｓｋｖ→の要素である要素Ｋ＊０と要素Ｋ＊１，ｊと要素Ｋ＊２，ｊとを生成する。
【数１８５】
【０１４１】
（Ｓ４１４：鍵配布ステップ）
鍵配布部１５０は、Ｓ４１１で入力したベクトルｖ→と、Ｓ３１３で生成した要素Ｋ＊０，Ｋ＊１，ｊ，Ｋ＊２，ｊとを要素とする復号鍵ｓｋｖ→を、例えば通信装置によりネットワークを介して秘密裡に復号装置３００へ配布する。もちろん、復号鍵ｓｋｖ→は、他の方法により復号装置３００へ配布されてもよい。
【０１４２】
つまり、Ｓ４１１からＳ４１３において、鍵生成装置１００は、数１８６に示すＫｅｙＧｅｎアルゴリズムを実行して、復号鍵ｓｋｖ→を生成する。そして、Ｓ４１４において、鍵生成装置１００は、生成された復号鍵ｓｋｖ→を復号装置３００へ配布する。
【数１８６】
【０１４３】
暗号化装置２００について説明する。
図２０に基づき、Ｅｎｃアルゴリズムの処理について説明する。
Ｓ４２１からＳ４２３までの処理は、図１６に示すＳ３２１からＳ３２３までの処理と同じである。
【０１４４】
（Ｓ４２４：要素ｃ生成ステップ）
暗号要素生成部２３２は、数１８７に示すように、処理装置により暗号文ｃｔｘ→の要素である要素ｃを生成する。
【数１８７】
数１８７は、数１３５と同様に、基底Ｂの基底ベクトルｂ０の係数としてζを設定し、基底ベクトルｂ１，．．．，ｂｎの係数としてωｘ１，．．．，ωｘｎを設定し、基底ベクトルｂｎ＋１，．．．，ｂ３ｎの係数として０を設定し、基底ベクトルｂ３ｎ＋１，．．．，ｂ４ｎの係数としてηｘ１，．．．，ηｘｎを設定することを意味する。
【０１４５】
Ｓ４２５の処理は、図１６に示すＳ３２５の処理と同じである。
【０１４６】
（Ｓ４２６：データ送信ステップ）
データ送信部２４０は、Ｓ４２２で入力したベクトルｘ→と、Ｓ４２４で生成した要素ｃと、Ｓ４２５で生成した要素ｃ３とを要素とする暗号文ｃｔｘ→を、例えば通信装置によりネットワークを介して復号装置３００へ送信する。もちろん、暗号文ｃｔｘ→は、他の方法により復号装置３００へ送信されてもよい。
【０１４７】
つまり、Ｓ４２１からＳ４２５において、暗号化装置２００は、数１８８に示すＥｎｃアルゴリズムを実行して、暗号文ｃｔｘ→を生成する。そして、Ｓ４２６において、暗号化装置２００は、生成された暗号文ｃｔｘ→を復号装置３００へ送信する。
【数１８８】
【０１４８】
復号装置３００について説明する。
図２１に基づき、Ｄｅｃアルゴリズムの処理について説明する。
Ｓ４３１からＳ４３２までの処理は、図１７に示すＳ３３１からＳ３３２までの処理と同じである。
【０１４９】
（Ｓ４３３：値Ｄｊ計算ステップ）
ペアリング演算部３３０は、数１８９に示すように、処理装置により値Ｄｊを計算する。
【数１８９】
ここで、要素ｃは、（Ｃ＊０，．．．，Ｃ＊４ｎ）∈Ｇ４ｎ＋１の（４ｎ＋１）組に分解される。
【０１５０】
（Ｓ４３４：ペアリング演算ステップ）
ペアリング演算部３３０は、数１９０に示すように、処理装置によりペアリング演算を実行して、値Ｆを計算する。
【数１９０】
【０１５１】
Ｓ４３５の処理は、図１７に示すＳ３３５の処理と同じである。
【０１５２】
つまり、Ｓ４３１からＳ４３５において、復号装置３００は、数１９１に示すＤｅｃアルゴリズムを実行して、メッセージｍ’を計算する。
【数１９１】
【０１５３】
なお、Ｂ＊：＝（ｂ＊０，．．．，ｂ＊４ｎ）は、｛Ｂ＊０，０，Ｂ＊０，ｊ，Ｂ＊ｉ，０，Ｌ，Ｂ＊ｉ，ｊ，Ｂ’＊ｉ，ｊ，Ｌ｝ｉ，ｊ＝１，．．．，４；Ｌ＝１，．．．，ｎによって特定される。また、Ｓｅｔｕｐアルゴリズムの出力に含まれる｛Ｂ＊０，０，Ｂ＊０，ｊ，Ｂ＊ｉ，０，Ｌ，Ｂ＊ｉ，ｊ，Ｂ’＊ｉ，ｊ，Ｌ｝ｉ＝１，３；ｊ＝１，．．．，４；Ｌ＝１，．．．，ｎは、Ｂ＾＊：＝（ｂ＊０，．．．，ｂ＊ｎ，ｂ＊２ｎ＋１，．．．，ｂ＊３ｎ）によって特定される。
そして、Ｄｅｃアルゴリズムは、数１９２に示すＤｅｃ’アルゴリズムのように記述することができる。
【数１９２】
【０１５４】
実施の形態５で説明した零内積暗号方式では、復号鍵ｓｋｖ→は、数１８５に示す要素Ｋ＊０で１個と、ｊ＝１，．．．，４の各整数ｊについての要素Ｋ＊１，ｊ及び要素Ｋ＊２，ｊで８個との合計９個のＧの要素を含む。つまり、復号鍵ｓｋｖ→は、ｎについて定数サイズである。
【０１５５】
また、実施の形態５で説明した零内積暗号方式では、復号処理（Ｄｅｃアルゴリズム）は、数１９０に示すｅ（Ｃ０，Ｋ＊０）で１個と、Πｊ＝１４（ｅ（Ｄｊ，Ｋ＊１，ｊ）・ｅ（Ｃｊｎ，Ｋ＊２，ｊ））で８個との合計９個のみペアリング演算を実行する。つまり、復号処理は、少ない数のペアリング演算のみ必要となる。
【０１５６】
なお、以上の実施の形態では、図２（ｂ）に示す線形変換Ｘを用いた。しかし、線形変換Ｘは、図２（ｂ）に示すものに限らない。例えば、図２（ｂ）における斜線が入れられた四角が示す部分をそれぞれ異なる値としてもよい。また、図２（ｂ）では、Ｎ列における全ての成分を定数値０以外の乱数としたが、Ｎ列ではなく、他のいずれか少なくとも１列における全ての成分を定数値０以外の乱数としてもよい。
より一般的には、線形変換Ｘは、各行各列に少なくとも１つは定数値０以外の値を有する疎行列であればよい。さらに、線形変換Ｘは、ｎ行ｎ列の行列である場合、定数値０以外の値として、少なくともｎ個の異なる値を有しているとよい。さらに、線形変換Ｘは、少なくとも１つの列における全ての成分が定数値０以外の値であるとよい。さらに、線形変換Ｘは、対角成分と、少なくとも１つの列における全ての成分が定数値０以外の値であるとよい。さらに、線形変換Ｘは、全ての成分が定数値０以外の値である列を除き、対角成分の値が同一であるとよい。
このような線形変換Ｘを用いた場合であっても、従来の線形変換Ｘを用いた場合に比べ、公開パラメータと秘密鍵とのサイズは小さくなる。また、ユーザ鍵の生成や暗号化の処理の処理時間も短くなる。
但し、線形変換Ｘの形式によっては、ペアリング演算の数を減らすことができない場合もある。
【０１５７】
以上の実施の形態では、ベクトル空間は、符号化部と、秘匿部と、秘密鍵ランダム化部と、暗号文ランダム化部とのための４つの直交する部分空間で構成した。そして、これに対応するため、数１２４に示すように、線形変換Ｘを、ｎ行ｎ列の行列Ｘｉ，ｊ（ｉ，ｊ＝１，．．．，４）を用いて構成した。線形変換Ｘのこの構成は、秘匿部と秘密鍵ランダム化部と暗号文ランダム化部との部分空間が、符号化部の部分空間と同じｎ次元であることを前提としている。
しかし、秘匿部と秘密鍵ランダム化部と暗号文ランダム化部との部分空間は、符号化部の部分空間と同じｎ次元でなくてもよい。例えば、秘匿部の部分空間はｎ×ｕ次元、秘密鍵ランダム化部の部分空間はｎ×ｗ次元、暗号文ランダム化部の部分空間はｎ×ｚ次元（ｕ，ｗ，ｚは０以上の整数）であってもよい。この場合、数１９３に示すように、線形変換Ｘを、ｎ行ｎ列の行列Ｘｉ，ｊ（ｉ，ｊ＝１，．．．，１＋ｕ＋ｗ＋ｚ）を用いて構成すればよい。
【数１９３】
【０１５８】
関数型暗号の一種として、ＩＤベースレボケーション（Ｉｄｅｎｔｉｔｙ−Ｂａｓｅｄ Ｒｅｖｏｃａｔｉｏｎ，ＩＢＲ）やＩＤベースブロードキャスト暗号（Ｉｄｅｎｔｉｔｙ−Ｂａｓｅｄ Ｂｒｏａｄｃａｓｔ Ｅｎｃｒｙｐｔｉｏｎ，ＩＢＢＥ）がある（非特許文献１，５，６，８，１９，１２参照）。
ＩＤベースレボケーションでは、暗号文は識別子の集合Ｓ＝（ＩＤ１，．．．，ＩＤｎ）に対して暗号化され、ＩＤ∈ＳでないＩＤと関連付けられた秘密鍵によって暗号文は復号される。つまり、復号には、ＩＤ∈Ｓでない場合に限り、ＲＩＢＲ（ＩＤ，Ｓ）＝１であることが必要である。
ＩＤベースブロードキャスト暗号では、暗号文は識別子の集合Ｓ＝（ＩＤ１，．．．，ＩＤｎ）に対して暗号化され、ＩＤ∈ＳであるＩＤと関連付けられた秘密鍵によって暗号文は復号される。つまり、復号には、ＩＤ∈Ｓである場合に限り、ＲＩＢＢＥ（ＩＤ，Ｓ）＝１であることが必要である。
【０１５９】
Ｓ：＝｛ＩＤ１，．．．，ＩＤｎ｝である場合に、Ｓ（Ｘ）：＝Σｉ＝０ｎｖｉＸｉ：＝Πｉ＝１ｎ（Ｘ−ＩＤｉ）とする。そして、ベクトルｖ→：＝（ｖ０，ｖ１，．．．，ｖｎ）とし、ベクトルｘ→：＝（１，ＩＤ，．．．，ＩＤｎ）とする。
すると、実施の形態２，３で説明した非零内積暗号方式は、ＩＤベースレボケーション方式となり、実施の形態４，５で説明した零内積暗号方式は、ＩＤベースブロードキャスト暗号方式となる。
つまり、以上の実施の形態で説明した内積暗号方式により、ＩＤベースレボケーション方式及びＩＤベースブロードキャスト暗号方式を実現できる。この場合においても、暗号文又は復号鍵をｎについての定数サイズとすることができ、少ない数のペアリング演算で復号することができる。
【０１６０】
実施の形態２−４で説明した具体的な暗号方式以外にも、非特許文献１３、１５、１６、１７等で説明されている暗号方式に、上述した線形変換Ｘを適用することで、公開パラメータと秘密鍵とのサイズは小さくなる。また、ユーザ鍵の生成や暗号化の処理の処理時間も短くなる。
【０１６１】
図２２は、実施の形態２−４で説明した非零内積暗号方式及び零内積暗号方式と、非特許文献２に記載された非零内積暗号方式及び零内積暗号方式とを比較した図である。
なお、図２２において、｜Ｇ｜、｜ＧＴ｜、｜Ｆｑ｜、Ｐ、Ｍは、それぞれＧのサイズ、ＧＴのサイズ、Ｆｑのサイズ、ペアリング演算、Ｇにおけるスカラー積演算を示している。また、ＣＴ、ＳＫ、ＩＰ、ＤＢＤＨは、それぞれ暗号文、秘密鍵（復号鍵）、内積、決定的双線形Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎを示している。
【０１６２】
実施の形態６．
以上の実施の形態では、双対ベクトル空間において暗号処理を実現する方法について説明した。実施の形態６では、双対加群において暗号処理を実現する方法について説明する。
【０１６３】
つまり、以上の実施の形態では、素数位数ｑの巡回群において暗号処理を実現した。しかし、合成数Ｍを用いて数１９４のように環Ｒを表した場合、環Ｒを係数とする加群においても、上記実施の形態で説明した暗号処理を適用することができる。
【数１９４】
【０１６４】
以上の実施の形態で説明したアルゴリズムにおけるＦｑをＲに変更すれば、双対加群における暗号処理を実現することができる。
【０１６５】
次に、実施の形態における暗号処理システム１０（鍵生成装置１００、暗号化装置２００、復号装置３００）のハードウェア構成について説明する。
図２３は、鍵生成装置１００、暗号化装置２００、復号装置３００、鍵委譲装置４００のハードウェア構成の一例を示す図である。
図２３に示すように、鍵生成装置１００、暗号化装置２００、復号装置３００、鍵委譲装置４００は、プログラムを実行するＣＰＵ９１１（Ｃｅｎｔｒａｌ・Ｐｒｏｃｅｓｓｉｎｇ・Ｕｎｉｔ、中央処理装置、処理装置、演算装置、マイクロプロセッサ、マイクロコンピュータ、プロセッサともいう）を備えている。ＣＰＵ９１１は、バス９１２を介してＲＯＭ９１３、ＲＡＭ９１４、ＬＣＤ９０１（Ｌｉｑｕｉｄ Ｃｒｙｓｔａｌ Ｄｉｓｐｌａｙ）、キーボード９０２（Ｋ／Ｂ）、通信ボード９１５、磁気ディスク装置９２０と接続され、これらのハードウェアデバイスを制御する。磁気ディスク装置９２０（固定ディスク装置）の代わりに、光ディスク装置、メモリカード読み書き装置などの記憶装置でもよい。磁気ディスク装置９２０は、所定の固定ディスクインタフェースを介して接続される。
【０１６６】
ＲＯＭ９１３、磁気ディスク装置９２０は、不揮発性メモリの一例である。ＲＡＭ９１４は、揮発性メモリの一例である。ＲＯＭ９１３とＲＡＭ９１４と磁気ディスク装置９２０とは、記憶装置（メモリ）の一例である。また、キーボード９０２、通信ボード９１５は、入力装置の一例である。また、通信ボード９１５は、通信装置の一例である。さらに、ＬＣＤ９０１は、表示装置の一例である。
【０１６７】
磁気ディスク装置９２０又はＲＯＭ９１３などには、オペレーティングシステム９２１（ＯＳ）、ウィンドウシステム９２２、プログラム群９２３、ファイル群９２４が記憶されている。プログラム群９２３のプログラムは、ＣＰＵ９１１、オペレーティングシステム９２１、ウィンドウシステム９２２により実行される。
【０１６８】
プログラム群９２３には、上記の説明において「マスター鍵生成部１１０」、「マスター鍵記憶部１２０」、「情報入力部１３０」、「復号鍵生成部１４０」、「鍵配布部１５０」、「公開パラメータ取得部２１０」、「情報入力部２２０」、「暗号文生成部２３０」、「データ送信部２４０」、「復号鍵取得部３１０」、「データ受信部３２０」、「ペアリング演算部３３０」、「メッセージ計算部３４０」等として説明した機能を実行するソフトウェアやプログラムやその他のプログラムが記憶されている。プログラムは、ＣＰＵ９１１により読み出され実行される。
ファイル群９２４には、上記の説明において「公開パラメータｐｋ」、「マスター秘密鍵ｓｋ」、「復号鍵ｓｋｖ→」、「暗号文ｃｔｘ→」等の情報やデータや信号値や変数値やパラメータが、「ファイル」や「データベース」の各項目として記憶される。「ファイル」や「データベース」は、ディスクやメモリなどの記録媒体に記憶される。ディスクやメモリなどの記憶媒体に記憶された情報やデータや信号値や変数値やパラメータは、読み書き回路を介してＣＰＵ９１１によりメインメモリやキャッシュメモリに読み出され、抽出・検索・参照・比較・演算・計算・処理・出力・印刷・表示などのＣＰＵ９１１の動作に用いられる。抽出・検索・参照・比較・演算・計算・処理・出力・印刷・表示のＣＰＵ９１１の動作の間、情報やデータや信号値や変数値やパラメータは、メインメモリやキャッシュメモリやバッファメモリに一時的に記憶される。
【０１６９】
また、上記の説明におけるフローチャートの矢印の部分は主としてデータや信号の入出力を示し、データや信号値は、ＲＡＭ９１４のメモリ、その他光ディスク等の記録媒体やＩＣチップに記録される。また、データや信号は、バス９１２や信号線やケーブルその他の伝送媒体や電波によりオンライン伝送される。
また、上記の説明において「〜部」として説明するものは、「〜回路」、「〜装置」、「〜機器」、「〜手段」、「〜機能」であってもよく、また、「〜ステップ」、「〜手順」、「〜処理」であってもよい。また、「〜装置」として説明するものは、「〜回路」、「〜機器」、「〜手段」、「〜機能」であってもよく、また、「〜ステップ」、「〜手順」、「〜処理」であってもよい。さらに、「〜処理」として説明するものは「〜ステップ」であっても構わない。すなわち、「〜部」として説明するものは、ＲＯＭ９１３に記憶されたファームウェアで実現されていても構わない。或いは、ソフトウェアのみ、或いは、素子・デバイス・基板・配線などのハードウェアのみ、或いは、ソフトウェアとハードウェアとの組み合わせ、さらには、ファームウェアとの組み合わせで実施されても構わない。ファームウェアとソフトウェアは、プログラムとして、ＲＯＭ９１３等の記録媒体に記憶される。プログラムはＣＰＵ９１１により読み出され、ＣＰＵ９１１により実行される。すなわち、プログラムは、上記で述べた「〜部」としてコンピュータ等を機能させるものである。あるいは、上記で述べた「〜部」の手順や方法をコンピュータ等に実行させるものである。
【符号の説明】
【０１７０】
１０ 暗号処理システム、１００ 鍵生成装置、１１０ マスター鍵生成部、１１１ 空間生成部、１１２ 行列生成部、１１３ 基底生成部、１１４ 鍵生成部、１２０ マスター鍵記憶部、１３０ 情報入力部、１４０ 復号鍵生成部、１４１ 乱数生成部、１４２ 鍵要素生成部、１５０ 鍵配布部、２００ 暗号化装置、２１０ 公開パラメータ取得部、２２０ 情報入力部、２３０ 暗号文生成部、２３１ 乱数生成部、２３２ 暗号要素生成部、２４０ データ送信部、３００ 復号装置、３１０ 復号鍵取得部、３２０ データ受信部、３３０ ペアリング演算部、３４０ メッセージ計算部。
【特許請求の範囲】
【請求項１】
各行各列に少なくとも１つは定数値０以外の値を有する疎行列を用いて所定の基底Ａを変形して生成された基底Ｂと基底Ｂ＊を利用し、暗号処理を行う暗号処理システムであり、
前記基底Ｂにおけるベクトルであって、所定の情報を埋め込んだベクトルを暗号ベクトルとして生成する暗号化装置と、
前記基底Ｂ＊における所定のベクトルを鍵ベクトルとして、前記暗号化装置が生成した暗号ベクトルと前記鍵ベクトルとについて、ペアリング演算を行い前記暗号ベクトルを復号して前記所定の情報に関する情報を抽出する復号装置と
を備えることを特徴とする暗号処理システム。
【請求項２】
前記疎行列は、ｎ行ｎ列（ｎは２以上の整数）の行列であり、定数値０以外の値として、少なくともｎ個の異なる値を有する
ことを特徴とする請求項１に記載の暗号処理システム。
【請求項３】
前記疎行列は、少なくとも１つの列における全ての成分が定数値０以外の値である
ことを特徴とする請求項２に記載の暗号処理システム。
【請求項４】
前記疎行列は、対角成分と、少なくとも１つの列における全ての成分が定数値０以外の値である
ことを特徴とする請求項３に記載の暗号処理システム。
【請求項５】
前記疎行列は、全ての成分が定数値０以外の値である列を除き、対角成分の値が同一である
ことを特徴とする請求項４に記載の暗号処理システム。
【請求項６】
前記疎行列は、数１に示す行列である
ことを特徴とする請求項５に記載の暗号処理システム。
【数１】
【請求項７】
前記暗号処理システムは、１行１列からｎ行ｎ列までの値が数２に示す疎行列であるＮ行Ｎ列（Ｎはｎ以上の整数）の線形変換Ｘを用いて、数３に示すように前記基底Ａから生成された基底Ｂと基底Ｂ＊とを用い、
前記暗号化装置は、数４を含むベクトルを前記暗号ベクトルとして生成し、
前記復号装置は、数５を含むベクトルｋ＊を前記鍵ベクトルとして、前記暗号ベクトルを復号する
ことを特徴とする請求項１に記載の暗号処理システム。
【数２】
【数３】
【数４】
【数５】
【請求項８】
前記数２に示す疎行列の値Ｂｉ（ｉ＝１，．．．，ｎ−１）の値は同一の値Ｂであり、
前記暗号化装置は、数６を含むベクトルＣ１と数７を含むベクトルＣ２とを含むベクトルを前記暗号ベクトルとして生成し、
前記復号装置は、数８に示すＤ＊を計算して、数９に示すペアリング演算を行う
ことを特徴とする請求項７に記載の暗号処理システム。
【数６】
【数７】
【数８】
【数９】
【請求項９】
前記数２に示す疎行列の値Ｂｉ（ｉ＝１，．．．，ｎ−１）の値は同一の値Ｂであり、
前記暗号化装置は、数１０を含むベクトルＣ１と数１１を含むベクトルＣ２とを含むベクトルを前記暗号ベクトルとして生成し、
前記復号装置は、数１２に示すＤ＊を計算して、数１３に示すペアリング演算を行う
ことを特徴とする請求項７に記載の暗号処理システム。
【数１０】
【数１１】
【数１２】
【数１３】
【請求項１０】
前記暗号処理システムは、１行１列からｎ行ｎ列までの値が数１４に示す疎行列であるＮ行Ｎ列（Ｎはｎ以上の整数）の線形変換Ｘを用いて、数１５に示すように前記基底Ａから生成された基底Ｂと基底Ｂ＊とを用い、
前記暗号化装置は、数１６を含むベクトルｃを前記暗号ベクトルとして生成し、
前記復号装置は、数１７を含むベクトルを前記鍵ベクトルとして、前記暗号ベクトルを復号する
ことを特徴とする請求項１に記載の暗号処理システム。
【数１４】
【数１５】
【数１６】
【数１７】
【請求項１１】
前記数１４に示す疎行列の値Ｂｉ（ｉ＝１，．．．，ｎ−１）の値は同一の値Ｂであり、
前記復号装置は、数１８を含むベクトルＫ＊１と数１９を含むベクトルＫ＊２とを含むベクトルを前記鍵ベクトルとして、数２０に示すＤを計算して、数２１に示すペアリング演算を行う
ことを特徴とする請求項１０に記載の暗号処理システム。
【数１８】
【数１９】
【数２０】
【数２１】
【請求項１２】
前記数１４に示す疎行列の値Ｂｉ（ｉ＝１，．．．，ｎ−１）の値は同一の値Ｂであり、
前記復号装置は、数２２を含むベクトルＫ＊１と数２３を含むベクトルＫ＊２とを含むベクトルを前記鍵ベクトルとして、数２４に示すＤを計算して、数２５に示すペアリング演算を行う
ことを特徴とする請求項１０に記載の暗号処理システム。
【数２２】
【数２３】
【数２４】
【数２５】
【請求項１３】
各行各列に少なくとも１つは０以外の値を有する疎行列を用いて所定の基底Ａを変形して生成された基底Ｂと基底Ｂ＊を利用し、暗号処理を行う暗号処理方法であり、
暗号化装置が、前記基底Ｂにおけるベクトルであって、所定の情報を埋め込んだベクトルを暗号ベクトルとして生成し、
復号装置が、前記基底Ｂ＊における所定のベクトルを鍵ベクトルとして、前記暗号化装置が生成した暗号ベクトルと前記鍵ベクトルとについて、ペアリング演算を行い前記暗号ベクトルを復号して前記所定の情報に関する情報を抽出する
ことを特徴とする暗号処理方法。
【請求項１４】
各行各列に少なくとも１つは０以外の値を有する疎行列を用いて所定の基底Ａを変形して生成された基底Ｂと基底Ｂ＊を利用し、暗号処理を行う暗号処理プログラムであり、
前記基底Ｂにおけるベクトルであって、所定の情報を埋め込んだベクトルを暗号ベクトルとして生成する暗号化処理と、
前記基底Ｂ＊における所定のベクトルを鍵ベクトルとして、前記暗号化処理で生成した暗号ベクトルと前記鍵ベクトルとについて、ペアリング演算を行い前記暗号ベクトルを復号して前記所定の情報に関する情報を抽出する復号処理と
をコンピュータに実行させることを特徴とする暗号処理プログラム。
【請求項１５】
公開鍵暗号における公開パラメータと秘密鍵とを生成する鍵生成装置であり、
各行各列に少なくとも１つは０以外の値を有する疎行列を含む線形変換Ｘを生成する行列生成部と、
前記行列生成部が生成した線形変換Ｘを用いて、所定の基底Ａから数２６に示すように基底Ｄと基底Ｄ＊とを生成する基底生成部と、
前記基底生成部が生成した前記基底Ｄと前記基底Ｄ＊との一方の基底の少なくとも一部の基底ベクトルを公開パラメータとし、他方の基底の少なくとも一部の基底ベクトルを秘密鍵として生成するマスター鍵生成部と
を備えることを特徴とする鍵生成装置。
【数２６】
【請求項１】
各行各列に少なくとも１つは定数値０以外の値を有する疎行列を用いて所定の基底Ａを変形して生成された基底Ｂと基底Ｂ＊を利用し、暗号処理を行う暗号処理システムであり、
前記基底Ｂにおけるベクトルであって、所定の情報を埋め込んだベクトルを暗号ベクトルとして生成する暗号化装置と、
前記基底Ｂ＊における所定のベクトルを鍵ベクトルとして、前記暗号化装置が生成した暗号ベクトルと前記鍵ベクトルとについて、ペアリング演算を行い前記暗号ベクトルを復号して前記所定の情報に関する情報を抽出する復号装置と
を備えることを特徴とする暗号処理システム。
【請求項２】
前記疎行列は、ｎ行ｎ列（ｎは２以上の整数）の行列であり、定数値０以外の値として、少なくともｎ個の異なる値を有する
ことを特徴とする請求項１に記載の暗号処理システム。
【請求項３】
前記疎行列は、少なくとも１つの列における全ての成分が定数値０以外の値である
ことを特徴とする請求項２に記載の暗号処理システム。
【請求項４】
前記疎行列は、対角成分と、少なくとも１つの列における全ての成分が定数値０以外の値である
ことを特徴とする請求項３に記載の暗号処理システム。
【請求項５】
前記疎行列は、全ての成分が定数値０以外の値である列を除き、対角成分の値が同一である
ことを特徴とする請求項４に記載の暗号処理システム。
【請求項６】
前記疎行列は、数１に示す行列である
ことを特徴とする請求項５に記載の暗号処理システム。
【数１】
【請求項７】
前記暗号処理システムは、１行１列からｎ行ｎ列までの値が数２に示す疎行列であるＮ行Ｎ列（Ｎはｎ以上の整数）の線形変換Ｘを用いて、数３に示すように前記基底Ａから生成された基底Ｂと基底Ｂ＊とを用い、
前記暗号化装置は、数４を含むベクトルを前記暗号ベクトルとして生成し、
前記復号装置は、数５を含むベクトルｋ＊を前記鍵ベクトルとして、前記暗号ベクトルを復号する
ことを特徴とする請求項１に記載の暗号処理システム。
【数２】
【数３】
【数４】
【数５】
【請求項８】
前記数２に示す疎行列の値Ｂｉ（ｉ＝１，．．．，ｎ−１）の値は同一の値Ｂであり、
前記暗号化装置は、数６を含むベクトルＣ１と数７を含むベクトルＣ２とを含むベクトルを前記暗号ベクトルとして生成し、
前記復号装置は、数８に示すＤ＊を計算して、数９に示すペアリング演算を行う
ことを特徴とする請求項７に記載の暗号処理システム。
【数６】
【数７】
【数８】
【数９】
【請求項９】
前記数２に示す疎行列の値Ｂｉ（ｉ＝１，．．．，ｎ−１）の値は同一の値Ｂであり、
前記暗号化装置は、数１０を含むベクトルＣ１と数１１を含むベクトルＣ２とを含むベクトルを前記暗号ベクトルとして生成し、
前記復号装置は、数１２に示すＤ＊を計算して、数１３に示すペアリング演算を行う
ことを特徴とする請求項７に記載の暗号処理システム。
【数１０】
【数１１】
【数１２】
【数１３】
【請求項１０】
前記暗号処理システムは、１行１列からｎ行ｎ列までの値が数１４に示す疎行列であるＮ行Ｎ列（Ｎはｎ以上の整数）の線形変換Ｘを用いて、数１５に示すように前記基底Ａから生成された基底Ｂと基底Ｂ＊とを用い、
前記暗号化装置は、数１６を含むベクトルｃを前記暗号ベクトルとして生成し、
前記復号装置は、数１７を含むベクトルを前記鍵ベクトルとして、前記暗号ベクトルを復号する
ことを特徴とする請求項１に記載の暗号処理システム。
【数１４】
【数１５】
【数１６】
【数１７】
【請求項１１】
前記数１４に示す疎行列の値Ｂｉ（ｉ＝１，．．．，ｎ−１）の値は同一の値Ｂであり、
前記復号装置は、数１８を含むベクトルＫ＊１と数１９を含むベクトルＫ＊２とを含むベクトルを前記鍵ベクトルとして、数２０に示すＤを計算して、数２１に示すペアリング演算を行う
ことを特徴とする請求項１０に記載の暗号処理システム。
【数１８】
【数１９】
【数２０】
【数２１】
【請求項１２】
前記数１４に示す疎行列の値Ｂｉ（ｉ＝１，．．．，ｎ−１）の値は同一の値Ｂであり、
前記復号装置は、数２２を含むベクトルＫ＊１と数２３を含むベクトルＫ＊２とを含むベクトルを前記鍵ベクトルとして、数２４に示すＤを計算して、数２５に示すペアリング演算を行う
ことを特徴とする請求項１０に記載の暗号処理システム。
【数２２】
【数２３】
【数２４】
【数２５】
【請求項１３】
各行各列に少なくとも１つは０以外の値を有する疎行列を用いて所定の基底Ａを変形して生成された基底Ｂと基底Ｂ＊を利用し、暗号処理を行う暗号処理方法であり、
暗号化装置が、前記基底Ｂにおけるベクトルであって、所定の情報を埋め込んだベクトルを暗号ベクトルとして生成し、
復号装置が、前記基底Ｂ＊における所定のベクトルを鍵ベクトルとして、前記暗号化装置が生成した暗号ベクトルと前記鍵ベクトルとについて、ペアリング演算を行い前記暗号ベクトルを復号して前記所定の情報に関する情報を抽出する
ことを特徴とする暗号処理方法。
【請求項１４】
各行各列に少なくとも１つは０以外の値を有する疎行列を用いて所定の基底Ａを変形して生成された基底Ｂと基底Ｂ＊を利用し、暗号処理を行う暗号処理プログラムであり、
前記基底Ｂにおけるベクトルであって、所定の情報を埋め込んだベクトルを暗号ベクトルとして生成する暗号化処理と、
前記基底Ｂ＊における所定のベクトルを鍵ベクトルとして、前記暗号化処理で生成した暗号ベクトルと前記鍵ベクトルとについて、ペアリング演算を行い前記暗号ベクトルを復号して前記所定の情報に関する情報を抽出する復号処理と
をコンピュータに実行させることを特徴とする暗号処理プログラム。
【請求項１５】
公開鍵暗号における公開パラメータと秘密鍵とを生成する鍵生成装置であり、
各行各列に少なくとも１つは０以外の値を有する疎行列を含む線形変換Ｘを生成する行列生成部と、
前記行列生成部が生成した線形変換Ｘを用いて、所定の基底Ａから数２６に示すように基底Ｄと基底Ｄ＊とを生成する基底生成部と、
前記基底生成部が生成した前記基底Ｄと前記基底Ｄ＊との一方の基底の少なくとも一部の基底ベクトルを公開パラメータとし、他方の基底の少なくとも一部の基底ベクトルを秘密鍵として生成するマスター鍵生成部と
を備えることを特徴とする鍵生成装置。
【数２６】
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図１９】
【図２０】
【図２１】
【図２２】
【図２３】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図１９】
【図２０】
【図２１】
【図２２】
【図２３】
【公開番号】特開２０１３−１０９０４８（Ｐ２０１３−１０９０４８Ａ）
【公開日】平成２５年６月６日（２０１３．６．６）
【国際特許分類】
【出願番号】特願２０１１−２５２２４４（Ｐ２０１１−２５２２４４）
【出願日】平成２３年１１月１８日（２０１１．１１．１８）
【出願人】（０００００６０１３）三菱電機株式会社 (33,312)
【出願人】（０００００４２２６）日本電信電話株式会社 (13,992)
【Ｆターム（参考）】
【公開日】平成２５年６月６日（２０１３．６．６）
【国際特許分類】
【出願日】平成２３年１１月１８日（２０１１．１１．１８）
【出願人】（０００００６０１３）三菱電機株式会社 (33,312)
【出願人】（０００００４２２６）日本電信電話株式会社 (13,992)
【Ｆターム（参考）】
[ Back to top ]