JP3927419B2 - Information registration method, terminal device, information registration server, information registration system - Google Patents

Description

【００１５】
【数２】

【００１６】
【数３】

【００１７】
【数４】

【００１８】
このとき、例えば（５）式を満たすような多項式ａ（ｘ）を短い多項式と呼ぶ。
【００１９】
【数５】

【００２０】
すなわち、短い多項式とは、そのセンターノルムが、多項式の次数Ｎの増加に伴って増加するように（例えば、Ｎの平方根に比例するように）あらかじめ定められたしきい値よりも小さくなるような多項式である。
【００２１】
また、（２）式で表される多項式ａ（ｘ）と（６）式で表される多項式ｂ（ｘ）とを用いた演算式ａ（ｘ）・ｂ（ｘ）（ｍｏｄ ｘ^N−１）をａ＊ｂで表す。
【００２２】
【数６】

【００２３】
ここで、ｃ（ｘ）＝ａ＊ｂ（（７）式参照）をベクトルｃ（（８）式参照）とみなすと、ベクトルａ（（３）式参照）とベクトルｂ（（９）式参照）とベクトルｃ（（８）式参照）とは、（１０）式の関係を満たす。
【００２４】
【数７】

【００２５】
【数８】

【００２６】
【数９】

【００２７】
【数１０】

【００２８】
［準備］
適当な自然数Ｎ（例えば１００〜５００の値）に対して、大きなモジュラス値ｑ（例えばＮの半分程度の値）と小さなモジュラス値ｐ（例えば２，３などの値）とを、ｘ^N−１，ｐ，ｑが互いに素であるように定める。また、Ｒ_p，Ｒ_qをそれぞれ、Ｚ_p，Ｚ_qの元を係数とするＮ−１次多項式の集合とする。
【００２９】
［鍵生成］
短い多項式ｆ，ｇを任意に定め、これらを秘密鍵とする。この多項式ｆに関し、（１１）式を満たすＦ_p、及び（１２）式を満たすＦ_qを計算した後、（１３）式により公開鍵ｈを計算する。
【００３０】
【数１１】

【００３１】
【数１２】

【００３２】
【数１３】

【００３３】
［暗号化］
メッセージｍの属するメッセージ空間Ｌ_mを（１４）式のように定義する。ここで、メッセージｍに対してランダムな短い多項式ｒを定め、（１５）式を用いて暗号文ｅを生成する。
【００３４】
【数１４】

【００３５】
【数１５】

【００３６】
［復号化］
秘密鍵ｆと暗号文ｅとから（１６）式を用いてａを計算し、さらに（１７）式を用いてｂを計算し、このｂと秘密鍵ｆのＲ_pでの逆元Ｆ_pとから、（１８）式を用いてメッセージｍを復号することができる。
【００３７】
【数１６】

【００３８】
【数１７】

【００３９】
【数１８】

【００４０】
［ＮＴＲＵ仮定］
ＮＴＲＵ公開鍵暗号方式は、Ｒ_qに属する多項式ｈが与えられたときに、（１９）式を満たす短い多項式ｆ，ｇを求めることは困難であるとの仮定に基づいている。
【００４１】
【数１９】

【００４２】
これは、ｄｅｇ ｈ＝Ｎ−１のとき、秘密鍵ｆ，ｇを求めるための最も効率的な方法は、２Ｎ次元ラティス上の短いベクトルを探す問題を解くことと考えられるからである。
【００４３】
続いて、本発明の実施形態にかかる情報登録システムの説明に用いる定義について説明しておく。まず、２つの集合Ｓ₁，Ｓ₂をそれぞれ（２０）式、（２１）式のように定義する。
【００４４】
【数２０】

【００４５】
【数２１】

【００４６】
すなわち、集合Ｓ₂は短い多項式の集合であり、Ｓ₁はさらに短い多項式の集合である。ここで、さらに短い多項式とは、そのセンターノルムが、多項式の次数Ｎによらないあらかじめ定められたしきい値よりも小さくなるような多項式である。従って、多項式の次数Ｎが大きい（例えば１００〜５００）場合、さらに短い多項式のセンターノルムは、短い多項式のセンターノルムと比較して十分小さい。
【００４７】
上記定義のもとで、集合Ｌα，Ｌφ，Ｌ_c，Ｌ_x，Ｌ_rはそれぞれ、（２２）式を満たすものとする。
【００４８】
【数２２】

【００４９】
すなわち、集合Ｌα，Ｌφ，Ｌ_x，Ｌ_rそれぞれは、短い多項式の集合であり、集合Ｌ_cは、さらに短い多項式の集合である。
【００５０】
ここで、αが集合Ｌαの要素であり、φが集合Ｌφの要素であり、ｃが集合Ｌ_cの要素であり、ξが集合Ｌξの要素であり、ψが集合Ｌψの要素であるならば、（２３）式、（２４）式、（２５）式を満たすような集合Ｌξ，Ｌψを定める。
【００５１】
【数２３】

【００５２】
【数２４】

【００５３】
【数２５】

【００５４】
例えば、集合Ｌα，Ｌφ，Ｌ_c，Ｌ_x，Ｌ_rがそれぞれ、（２６）〜（３０）式で表される場合、集合Ｌξ，Ｌψはそれぞれ、（３１）式、（３２）式で定義できる。
【００５５】
【数２６】

【００５６】
【数２７】

【００５７】
【数２８】

【００５８】
【数２９】

【００５９】
【数３０】

【００６０】
【数３１】

【００６１】
【数３２】

【００６２】
以下では、集合Ｌα，Ｌφ，Ｌ_c，Ｌξ，Ｌψ，Ｌ_x，Ｌ_rのサンプル空間をそれぞれ、（３３）〜（３９）式のように定義する。尚、集合Ｌ^* _cfは、（４０）式によって与えられる。
【００６３】
【数３３】

【００６４】
【数３４】

【００６５】
【数３５】

【００６６】
【数３６】

【００６７】
【数３７】

【００６８】
【数３８】

【００６９】
【数３９】

【００７０】
【数４０】

【００７１】
続いて、本発明の実施形態にかかる情報登録システムについて図面を参照して説明する。尚、本実施形態にかかる情報登録システムは、本発明の実施形態にかかる端末装置および情報登録サーバを含んでいる。
【００７２】
まず、本実施形態にかかる情報登録システムの構成について説明する。図１は、本実施形態にかかる情報登録システムの構成図である。本実施形態にかかる情報登録システム１０は、移動通信端末１２（端末装置）と情報登録サーバ１４とを備え、移動通信端末１２から送信される情報（例えば秘密情報）を情報登録サーバ１４に登録する情報登録システムである。
【００７３】
ここで、移動通信端末１２と情報登録サーバ１４は、移動体通信網などのネットワーク１６を介して接続されており、互いにデータの送受信ができるようになっている。また、移動通信端末１２と情報登録サーバ１４とのそれぞれは、ネットワーク１６を介して鍵生成サーバ１８に接続されており、鍵生成サーバ１８から送信される公開鍵などのデータを受信することができるようになっている。
【００７４】
移動通信端末１２は、物理的には、ＣＰＵ、メモリ、ディスプレイ、入力キー、データ送受信回路などを備えた携帯電話として構成される。移動通信端末１２は、機能的な構成要素として、第１暗号文生成部２０（第１の暗号文生成手段）と、第１暗号文送信部２２（第１の暗号文送信手段）と、第２暗号文生成部２４（第２の暗号文生成手段）と、第２暗号文送信部２６（第２の暗号文送信手段）と、チャレンジ受信部２８（チャレンジ受信手段）と、レスポンス生成部３０（レスポンス生成手段）と、レスポンス送信部３２（レスポンス送信手段）とを備えて構成される。
【００７５】
情報登録サーバ１４は、物理的には、ＣＰＵ、メモリ、ディスプレイ、磁気ディスク装置や光ディスク装置などの格納装置、キーボードやマウスなどの入力装置、モデムやデジタル通信ユニットなどのデータ送受信装置などを備えたコンピュータシステムとして構成される。情報登録サーバ１４は、機能的な構成要素として、第１暗号文受信部３６（第１の暗号文受信手段）と、第２暗号文受信部３８（第２の暗号文受信手段）と、チャレンジ送信部４０（チャレンジ送信手段）と、レスポンス受信部４２（レスポンス受信手段）と、検証部４４（検証手段）と、情報登録部４６（情報登録手段）とを備えて構成される。以下、各構成要素について詳細に説明する。
【００７６】
移動通信端末１２の第１暗号文生成部２０は、上述のＮＴＲＵ公開鍵暗号方式により、短い多項式φと公開鍵ｈと小さいモジュラス値ｐと大きいモジュラス値ｑとを用いて、（４１）式に従い、短い多項式で表現された平文α（移動通信端末１２の利用者が情報登録センタ１４に登録したい情報の平文）の暗号文ｅを生成する。
【００７７】
【数４１】

【００７８】
ここで、公開鍵ｈと小さいモジュラス値ｐと大きいモジュラス値ｑとは、あらかじめ鍵生成サーバ１８によって生成され、鍵生成サーバ１８から移動通信端末１２に対して送信されている。平文αは、（３３）式に示す集合Ｌαの要素であり、移動通信端末１２のユーザによって入力される。また、短い多項式φは、（３４）式に示す集合Ｌφの要素であり、移動通信端末１２のユーザによって入力されても良いし、第１暗号文生成部２０によってランダムに生成されてもよい。
【００７９】
第１暗号文送信部２２は、第１暗号文生成部２０によって生成された暗号文ｅを、情報登録サーバ１４に対して送信する。
【００８０】
第２暗号文生成部２４は、上述のＮＴＲＵ公開鍵暗号方式により、短い多項式ψと上記公開鍵ｈと上記小さいモジュラス値ｐと上記大きいモジュラス値ｑとを用いて、（４２）式に従い、短い多項式ξの暗号文ａを生成する。
【００８１】
【数４２】

【００８２】
ここで、短い多項式ψは、（３７）式に示す集合Ｌψの要素であり、移動通信端末１２のユーザによって入力されても良いし、第２暗号文生成部２４によってランダムに生成されてもよい。また、短い多項式ξは、（３６）式に示す集合Ｌξの要素であり、移動通信端末１２のユーザによって入力されても良いし、第２暗号文生成部２４によってランダムに生成されてもよい。
【００８３】
第２暗号文送信部２６は、第２暗号文生成部２４によって生成された暗号文ａを、情報登録サーバ１４に対して送信する。
【００８４】
チャレンジ受信部２８は、情報登録サーバ１４から送信される、上記平文αと上記短い多項式ψとの双方と比較してさらに短い多項式ｃ（チャレンジ）を受信する。ここで、さらに短い多項式ｃは、（３５）式に示す集合Ｌ_cの要素である。
【００８５】
レスポンス生成部３０は、上記平文αと上記短い多項式φと上記短い多項式ψと上記短い多項式ξと上記チャレンジ受信部２８によって受信した上記さらに短い多項式ｃとを用いて、（４３）式、（４４）式に従い、多項式ｘと多項式ｒ（レスポンス）を生成する。
【００８６】
【数４３】

【００８７】
【数４４】

【００８８】
レスポンス送信部３２は、レスポンス生成部３４によって生成された上記多項式ｘと上記多項式ｒ（レスポンス）を、情報登録サーバ１４に対して送信する。
【００８９】
情報登録サーバ１４の第１暗号文受信部３６は、移動通信端末１２から送信される上記暗号文ｅを受信する。また、第２暗号文受信部３８は、移動通信端末１２から送信される上記暗号文ａを受信する。
【００９０】
チャレンジ送信部４０は、上記平文αと上記短い多項式ψとの双方と比較してさらに短い多項式ｃ（チャレンジ）を移動通信端末１２に対して送信する。ここで、上記さらに短い多項式ｃは、情報登録サーバ１４のユーザによって入力されても良いし、チャレンジ送信部４０によって生成されてもよい。
【００９１】
レスポンス受信部４２は、移動通信端末１２から送信される多項式ｘと多項式ｒ（レスポンス）を受信する。
【００９２】
検証部４４は、▲１▼レスポンス受信部４２によって受信した上記多項式ｘと上記多項式ｒとがともに短い多項式であることを検証し（すなわち、多項式ｘが（３８）式に示す集合Ｌ_xの要素であり、かつ、多項式ｒが（３９）式に示す集合Ｌ_rの要素であることを検証し）、かつ、▲２▼上記暗号文ｅと上記暗号文ａと上記公開鍵ｈと上記小さいモジュラス値ｐと上記大きいモジュラス値ｑと上記さらに短い多項式ｃと上記多項式ｘと上記多項式ｒとが、（４５）式を満たすことを検証する。
【００９３】
【数４５】

【００９４】
ここで、公開鍵ｈと小さいモジュラス値ｐと大きいモジュラス値ｑとは、あらかじめ鍵生成サーバ１８によって生成され、鍵生成サーバ１８から移動通信端末１２に対して送信されている。
【００９５】
上記▲１▼と▲２▼との双方が検証された場合、検証部４４は、情報登録サーバ１４から送信された暗号文ｅに対応する平文αを当該移動通信端末１２の利用者が知っていることが検証されたものとする。一方、上記▲１▼と▲２▼との少なくとも一方が検証されなかった場合、検証部４４は、移動通信端末１２から送信された暗号文ｅに対応する平文αを当該移動通信端末１２の利用者が知っていることが検証されなかったものとする。
【００９６】
情報登録部４６は、移動通信端末１２から送信される暗号文ｅに対応する平文αを当該移動通信端末１２の利用者が知っていることが検証部４４によって検証された場合に、当該平文αの暗号文ｅを登録する。暗号文ｅの登録は、情報登録サーバ１４に備えられた格納装置の所定の領域に、移動通信端末１２を識別する情報と関連づけられて暗号文ｅが格納されることによって行われる。
【００９７】
ここで、上記多項式ｘ，ｒとがともに短い多項式である（すなわち、多項式ｘが（３８）式に示す集合Ｌ_xの要素であり、かつ、多項式ｒが（３９）式に示す集合Ｌ_rの要素である）ことを検証し、（４５）式が満たされることを検証することによって検証可暗号方式が実現することを、以下の３つの補題を証明することによって証明する。
【００９８】
［補題１］証明者（移動通信端末１２）が正しければ、上記検証により、受理される。
【００９９】
ｘが（４６）式で表され、ｒが（４７）式で表されるとき、ξ，ψ，ｃ，α，φはそれぞれ（４８）式を満たすことから、ｘ，ｒは（４９）式を満たす。
【０１００】
【数４６】

【０１０１】
【数４７】

【０１０２】
【数４８】

【０１０３】
【数４９】

【０１０４】
また、上述の（４１）式は、Ｒの要素である任意の多項式Ｅを用いて、（５０）式のように表される。
【０１０５】
【数５０】

【０１０６】
同様に、上述の（４２）式は、Ｒの要素である任意の多項式Ａを用いて、（５１）式のように表される。
【０１０７】
【数５１】

【０１０８】
ここで、（４６）式、（４７）式、（５０）式、（５１）式を用いると、（５２）式が導かれる。
【０１０９】
【数５２】

（５２）式に対してｍｏｄ ｑの演算を施すことで、（５３）式が導かれる。
【０１１０】
【数５３】

（証明終）
【０１１１】
［補題２］証明者が誤っていれば、上記検証により、エラー率ε≧３／♯Ｌ_cで拒否される。
【０１１２】
エラー率ε≧３／♯Ｌ_cであるので、♯Ｌ_c通りの質問に対して、♯Ｌ_cε≧３個のエラーが存在する。つまり、Ｌ_cの中から、検証式を満たす少なくとも３つの異なるｃ，ｃ’，ｃ”を選ぶことができる。
【０１１３】
ここで、フォーキング・レンマより、公開鍵ｈを入力して、（５４）式を満たすｅ，（ｘ，ｒ，ｃ），（ｘ’，ｒ’，ｃ’），（ｘ”，ｒ”，ｃ”）を出力する確率的多項式時間アルゴリズムが存在すると仮定する。
【０１１４】
【数５４】

【０１１５】
このとき、Δｘ₁，Δｘ₂，Δｒ₁，Δｒ₂，Δｃ₁，Δｃ₂をそれぞれ（５５）〜（６０）式のようにおくと、（５４）式から、（６１）式及び（６２）式が導かれる。
【０１１６】
【数５５】

【０１１７】
【数５６】

【０１１８】
【数５７】

【０１１９】
【数５８】

【０１２０】
【数５９】

【０１２１】
【数６０】

【０１２２】
【数６１】

【０１２３】
【数６２】

【０１２４】
続いて、（６１）式、（６２）式のｑ＊Ａ₁，ｑ＊Ａ₂をそれぞれ移項し、両辺にそれぞれΔｃ₂，Δｃ₁を乗ずることにより、（６３）式が導かれる。
【０１２５】
【数６３】

【０１２６】
ここで、ΔＸ，ΔＲをそれぞれ（６４）式、（６５）式のようにおくと、（６３）式から（６６）式が導かれ、その結果、（６７）式が満たされる。
【０１２７】
【数６４】

【０１２８】
【数６５】

【０１２９】
【数６６】

【０１３０】
【数６７】

【０１３１】
｜ΔＸ｜，｜ΔＲ｜は、それぞれ、（６８）式、（６９）式を満たすので、多項式時間でＮＴＲＵラティスを解くことができることを意味する。
【０１３２】
【数６８】

【０１３３】
【数６９】

【０１３４】
これは、ＮＴＲＵラティスを解くことが難しければ、証明者はうそをつけないことを意味する。
（証明終）
【０１３５】
［補題３］上記検証においては、検証者（情報登録サーバ１４）に対して、平文αに関する情報を与えない。
【０１３６】
次のようなシミュレータを作成する。すなわち、与えられたｅに対して、Ｌ_xの要素であるｘ’，Ｌ_rの要素であるｒ’，Ｌ_cの要素であるｃ’をランダムに選択する。そして、（ｈ，ｅ，ｐ＊ｒ’＊ｈ＋ｘ’−ｃ’＊ｅ（ｍｏｄ ｑ））をランダムオラクルに質問する。既に同じ質問がされている確率はきわめて小さいので、ランダムオラクルは、この質問に対する回答をｃ’としてリストに入れる。このときシミュレータの出力によるプルーフは（ｘ’，ｒ’，ｃ’）となる。
【０１３７】
このとき、＃Ｌα，＃Ｌφ，＃Ｌ_c，＃Ｌ_x，＃Ｌ_rは、（７０）〜（７３）式を満たし、極めて小さいので、上記検証可暗号方式で出現する（ｘ，ｒ，ｃ）の系列がシミュレータによって生成される（ｘ’，ｒ’，ｃ’）の系列と統計的識別不可能となる。
【０１３８】
【数７０】

【０１３９】
【数７１】

【０１４０】
【数７２】

【０１４１】
【数７３】

【０１４２】
上記シミュレータは、誰にでも作成できる。このことは、検証者が平文に関する情報を得ないことを意味する。
（証明終）
【０１４３】
続いて、本実施形態にかかる情報登録システムの動作について説明し、併せて、本発明の実施形態にかかる情報登録方法について説明する。
【０１４４】
図２は、本実施形態にかかる情報登録システム１０の動作を示すフローチャートである。情報登録システム１０を構成する移動通信端末１２と情報登録サーバ１４に対しては、鍵生成サーバ１８によって生成された公開鍵ｈと小さいモジュラス値ｐと大きいモジュラス値ｑとが、あらかじめ送信されている。
【０１４５】
移動通信端末１２から情報登録サーバ１４に対して情報の登録を行おうとする場合、まず、移動通信端末１２において、上述の（４１）式に基づき、移動通信端末１２の利用者が情報登録センタ１４に登録したい情報の平文αに対する暗号文ｅが生成され（Ｓ１２）、情報登録サーバ１４に対して送信される（Ｓ１４）。ここで、αは、（３３）式に示す集合Ｌαの要素であり、φ（図２参照）は、（３４）式に示す集合Ｌφの要素である。
【０１４６】
また、移動通信端末１２において、上述の（４２）式に基づき、多項式ξに対する暗号文ａが生成され（Ｓ１６）、情報登録サーバ１４に対して送信される（Ｓ１８）。ここで、ξは、（３６）式に示す集合Ｌξの要素であり、ψ（図２参照）は、（３７）式に示す集合Ｌψの要素である。
【０１４７】
続いて、暗号文ｅ及び暗号文ａを受信した情報登録サーバ１４から、移動通信端末１２に対して、さらに短い多項式ｃ（チャレンジ）が送信される（Ｓ２０）。ここで、さらに短い多項式ｃは、（３５）式に示す集合Ｌ_cの要素である。
【０１４８】
情報登録サーバ１４から送信されたさらに短い多項式ｃ（チャレンジ）が移動通信端末１２によって受信されると、移動通信端末１２において、（４３）式及び（４４）式に従って、多項式ｘと多項式ｒ（レスポンス）が生成され（Ｓ２２）、生成された多項式ｘと多項式ｒ（レスポンス）が情報登録サーバ１４に対して送信される（Ｓ２４）。
【０１４９】
その後、情報登録サーバ１４において、移動通信端末１２から送信された多項式ｘと多項式ｒとがともに短い多項式であること（すなわち、多項式ｘが（３８）式に示す集合Ｌ_xの要素であり、かつ、多項式ｒが（３９）式に示す集合Ｌ_rの要素であること）が検証され（Ｓ２６）、上記暗号文ｅと上記暗号文ａと上記公開鍵ｈと上記小さいモジュラス値ｐと上記大きいモジュラス値ｑと上記さらに短い多項式ｃと上記多項式ｘと上記多項式ｒとが、（４５）式を満たすことが検証される（Ｓ２８）。
【０１５０】
ここで、移動通信端末１２から送信された多項式ｘと多項式ｒとの少なくとも一方が短い多項式ではない場合（すなわち、多項式ｘが（３８）式に示す集合Ｌ_xの要素ではないか、または、多項式ｒが（３９）式に示す集合Ｌ_rの要素ではない場合）、情報登録サーバ１４において、移動通信端末１２から送信される暗号文ｅに対応する平文αを当該移動通信端末１２の利用者が知らないものと判断され、情報登録サーバ１４への情報登録は行われない。また、上記暗号文ｅと上記暗号文ａと上記公開鍵ｈと上記小さいモジュラス値ｐと上記大きいモジュラス値ｑと上記さらに短い多項式ｃと上記多項式ｘと上記多項式ｒとが、（４５）式を満たさない場合も、情報登録サーバ１４において、移動通信端末１２から送信される暗号文ｅに対応する平文αを当該移動通信端末１２の利用者が知らないものと判断され、情報登録サーバ１４への情報登録は行われない。
【０１５１】
一方、移動通信端末１２から送信された多項式ｘと多項式ｒとがともに短い多項式であり（すなわち、多項式ｘが（３８）式に示す集合Ｌの要素であり、かつ、多項式ｒが（３９）式に示す集合Ｌの要素であり）、かつ、上記暗号文ｅと上記暗号文ａと上記公開鍵ｈと上記小さいモジュラス値ｐと上記大きいモジュラス値ｑと上記さらに短い多項式ｃと上記多項式ｘと上記多項式ｒとが、（４５）式を満たす場合、情報登録サーバ１４において、移動通信端末１２から送信される暗号文ｅに対応する平文αを当該移動通信端末１２の利用者が知っているものと判断され、情報登録サーバ１４への情報登録が行われる（Ｓ３０）。より具体的には、移動通信端末１２から送信された暗号文ｅが、情報登録サーバ１４に備えられた格納装置の所定の領域に、移動通信端末１２を識別する情報と関連づけられて格納される。この場合、情報登録サーバ１４が暗号文ｅに対応する平文αを移動通信端末１２からさらに受信し、当該平文αを情報登録サーバ１４に登録するようにしてもよい。
【０１５２】
また、図２を用いて説明した上記フローにおいて、移動通信端末１２から情報登録サーバ１４に対し、暗号文ａが送信されない場合、多項式ｘ，ｒ（レスポンス）が送信されない場合は、それぞれ、その後の処理が中止される。
【０１５３】
また、図２を用いて説明した上記フローを、移動通信端末１２及び情報登録サーバ１４以外の第３者に公開し、移動通信端末１２と情報登録サーバ１４との間の情報の送受信フローが正しいかどうかを外部から確認できるようにしてもよい。図２を用いて説明した上記フローを第３者に公開することで、当該第３者（例えば移動通信端末１２に対してサービスを提供するサービスプロバイダ）は、情報登録サーバ１４に対して何ら問い合わせを行うことなく、移動通信端末１２から情報登録サーバ１４に対して一定の情報の登録があったことを知ることができ、移動通信端末１２との迅速なデータの送受信（例えば迅速なサービスの提供）が可能となる。
【０１５４】
続いて、本実施形態にかかる情報登録システムの作用及び効果について説明する。本実施形態にかかる情報登録システム１０は、ＮＴＲＵ公開鍵暗号方式を用いることにより、素因数分解型の暗号方式を用いる場合や離散対数型の暗号方式を用いる場合と比較して、計算量を少なくすることができる。これは、従来技術にかかる暗号方式が指数演算を主とした暗号方式であったのに対し、ＮＴＲＵ公開鍵暗号方式は、積、和の演算を主とした暗号方式であるからである。また、本実施形態にかかる情報登録システム１０においては、情報登録サーバ１４において、多項式ｘと多項式ｒとがともに短い多項式であることを検証し、かつ、ａ＝ｐ＊ｒ＊ｈ＋ｘ−ｃ＊ｅ（ｍｏｄ ｑ）の関係が満たされることを検証することにより、移動通信端末１２の利用者が暗号文ｅに対応する平文αを知っていることを情報登録サーバ１４において検証できた場合にのみ情報登録を行う。したがって、不正な情報登録を排除することができる。その結果、情報登録サーバ１４に情報を登録するに際し、情報登録の信頼性を損なうことなく、その計算量を削減することができる。
【０１５５】
また、本実施形態にかかる情報登録システム１０は、ＮＴＲＵ公開鍵暗号方式を用いることにより、素因数分解型の暗号方式や離散対数型の暗号方式を利用するための仮定が成立しなくなった場合であっても利用しうる。
【０１５６】
本実施形態にかかる情報登録システム１０は、例えばインターネットなどのネットワーク上における鍵寄託などに好適に利用可能である。また、その計算量の少なさゆえに、携帯電話やＩＣカードなどの携帯型端末に好適に適用可能である。
【０１５７】
【発明の効果】
本発明の情報登録方法及び情報登録システムは、ＮＴＲＵ公開鍵暗号方式を用いることにより、素因数分解型の暗号方式を用いる場合や離散対数型の暗号方式を用いる場合と比較して、計算量を少なくすることができる。また、情報登録サーバにおいて、多項式ｘと多項式ｒとがともに短い多項式であることを検証し、かつ、ａ＝ｐ＊ｒ＊ｈ＋ｘ−ｃ＊ｅ（ｍｏｄ ｑ）の関係が満たされることを検証することにより、端末装置の利用者が暗号文ｅに対応する平文αを知っていることを情報登録サーバにおいて検証できた場合にのみ情報登録を行うことで、不正な情報登録を排除することができる。その結果、情報登録サーバに情報を登録するに際し、情報登録の信頼性を損なうことなく、その計算量を削減することができる。
【図面の簡単な説明】
【図１】情報登録システムの構成図である。
【図２】情報登録システムの動作を示すフローチャートである。
【符号の説明】
１０…情報登録システム、１２…移動通信端末，１４…情報登録サーバ、１６…ネットワーク、１８…鍵生成サーバ、２０…第１暗号文生成部、２２…第１暗号文送信部、２４…第２暗号文生成部、２６…第２暗号文送信部、２８…チャレンジ受信部、３０…レスポンス生成部、３２…レスポンス送信部、３６…第１暗号文受信部、３８…第２暗号文受信部、４０…チャレンジ送信部、４２…レスポンス受信部、４４…検証部、４６…情報登録部[0001]
BACKGROUND OF THE INVENTION
The present invention relates to an information registration method, an information registration system, a terminal device used therefor, and an information registration server.
[0002]
[Prior art]
With the increase in data transmission / reception over the network, security problems cannot be ignored. Therefore, for example, highly confidential information (for example, a secret key) is registered in a fair registration center (information registration server) such as key deposit, and the secret information is used only when certain authentication is performed. Techniques that enable this are known.
[0003]
However, confidential information may be illegally registered in the registration center due to impersonation of a third party. A verifiable encryption method is used to address this problem. The verifiable encryption method is a method in which the ciphertext receiver verifies that the ciphertext sender knows the plaintext corresponding to the ciphertext without obtaining information on the plaintext. That is, the registration center uses the verifiable encryption method to confirm that the person who sent the ciphertext of the secret information to be registered really knows the secret information (that is, the person who has stolen only the ciphertext from another person) ) Without knowing the secret information itself, and as a result, the secret information can be registered safely.
[0004]
As such verifiable encryption methods, for example, a method using a prime factorization type encryption method (for example, E. Fujisaki and T. Okamoto, A Practical and Provably Secure Scheme for Public Verifiable Secret Sharing and Its Application, In Proceedings of EUROCRYPT '98, LNCS 1403, Springer, pp.32-46 (1998), F. Bao, An Efficient verifiable encryption scheme for encryption of discrete logarithm, In Proceeding of CARDIS'98, LNCS 1820, Springer, pp.213-220 ( 2000)), and methods using discrete logarithmic cryptosystems (for example, M. Stadler, Publicly Verifiable Secret Sharing, In Proceedings of EUROCRYPT '96, LNCS 1070, Springer, pp. 190-199 (1996)) are known. Yes.
[0005]
[Problems to be solved by the invention]
However, each of the information registration methods using the verifiable encryption method according to the conventional technique has a problem that the amount of calculation becomes very large. In particular, in mobile communication terminals in which it is difficult to mount a high-speed CPU or a large-capacity memory due to the importance of portability, the verifiable encryption method according to the above-described conventional technique is based on the large amount of calculation. Neither is suitable for practical use.
[0006]
Therefore, an object of the present invention is to solve the above problems and provide an information registration method, an information registration system, a terminal device used for the information registration server, and an information registration server with a small amount of calculation.
[0007]
[Means for Solving the Problems]
In order to solve the above-described problem, an information registration method according to the present invention is an information registration method for registering information transmitted from a terminal device in an information registration server, and the terminal device is short using the NTRU public key cryptosystem. Using the polynomial φ, the public key h, the small modulus value p, and the large modulus value q, a first ciphertext e = p * φ * h + α (mod q) of the information α represented by a short polynomial is generated. A ciphertext generation step; a first ciphertext transmission step in which the terminal device transmits the ciphertext e generated in the first ciphertext generation step to the information registration server; and the terminal device. The ciphertext a = p * ψ * h + ξ of the short polynomial ξ using the short polynomial ψ, the public key h, the small modulus value p, and the large modulus value q according to the NTRU public key cryptosystem. mod q) is generated, and a second ciphertext generation step in which the terminal device transmits the ciphertext a generated in the second ciphertext generation step to the information registration server. A ciphertext transmission step, a challenge transmission step in which the information registration server transmits a polynomial c shorter than both the information α and the short polynomial ψ to the terminal device, and the terminal device includes: Using the information α, the short polynomial φ, the short polynomial ψ, the short polynomial ξ, and the shorter polynomial c transmitted from the information registration server, the polynomial x = ξ + c * α and the polynomial r = ψ + c * φ A response generation step for generating the above-mentioned information, and the terminal device sends the polynomial x and the polynomial r generated in the response generation step to the information registration server. And the information transmission server verifies that both the polynomial x and the polynomial r transmitted from the terminal device are short polynomials, and the ciphertext e and the cipher The sentence a, the public key h, the small modulus value p, the large modulus value q, the shorter polynomial c, the polynomial x, and the polynomial r are a = p * r * h + x−c * e (mod q). A verification step for verifying that the user of the terminal device knows information α corresponding to the ciphertext e transmitted from the terminal device, and the information registration server When the verification step verifies that the user of the terminal device knows the information α corresponding to the ciphertext e transmitted from the terminal device, the information α or Or an information registration step of registering the ciphertext e of the information α.
[0008]
The terminal device of the present invention is a terminal device used in an information registration method for registering information transmitted from a terminal device in an information registration server, and uses a short polynomial φ and a public key h by an NTRU public key cryptosystem. A first ciphertext generating means for generating a ciphertext e = p * φ * h + α (mod q) of the information α expressed by a short polynomial using a small modulus value p and a large modulus value q; First ciphertext transmission means for transmitting the ciphertext e generated by the first ciphertext generation means to the information registration server, and a short polynomial ψ and the public key h by NTRU public key cryptography. And a second ciphertext generating means for generating a ciphertext a = p * ψ * h + ξ (mod q) of a short polynomial ξ using the small modulus value p and the large modulus value q, and the second secret message Both the second ciphertext transmitting means for transmitting the ciphertext a generated by the generating means to the information registration server, and the information α and the short polynomial ψ transmitted from the information registration server. A challenge receiving means for receiving a shorter polynomial c than the information α, the information α, the short polynomial φ, the short polynomial ψ, the short polynomial ξ, and the shorter polynomial c received by the challenge receiving means. Response generating means for generating polynomial x = ξ + c * α and polynomial r = ψ + c * φ, and the polynomial x and polynomial r generated by the response generating means are transmitted to the information registration server. And a response transmission means.
[0009]
The information registration server of the present invention is the information registration server used in the information registration method for registering information transmitted from the terminal device in the information registration server, and uses a short polynomial φ and a public key by the NTRU public key cryptosystem. The ciphertext e = p * φ * h + α of the information α expressed by a short polynomial, which is generated in the terminal device using h, a small modulus value p, and a large modulus value q and transmitted from the terminal device. mod q) is received by the terminal apparatus using the short polynomial ψ, the public key h, the small modulus value p, and the large modulus value q by the NTRU public key cryptosystem. A second ciphertext receiving means for receiving the ciphertext a = p * ψ * h + ξ (mod q) of the short polynomial ξ generated and transmitted from the terminal device; and the information α And a challenge transmitting means for transmitting a polynomial c shorter than both the short polynomial ψ and the short polynomial ψ, the information α, the short polynomial φ, the short polynomial ψ, the short polynomial ξ, and the A response receiving means for receiving a polynomial x = ξ + c * α and a polynomial r = ψ + c * φ, which is generated in the terminal device using the short polynomial c and transmitted from the terminal device, and the response receiving means It is verified that the received polynomial x and polynomial r are both short polynomials, and the ciphertext e, the ciphertext a, the public key h, the small modulus value p, and the large modulus value q By verifying that the shorter polynomial c, the polynomial x, and the polynomial r satisfy the relationship a = p * r * h + x−c * e (mod q). Verifying that the user of the terminal device knows information α corresponding to the ciphertext e transmitted from the terminal device, and the ciphertext e transmitted from the terminal device by the verification device. And information registration means for registering the information α or the ciphertext e of the information α when it is verified that the user of the terminal device knows the information α corresponding to .
[0010]
Furthermore, the information registration system of the present invention is characterized by comprising the above terminal device and the above information registration server.
[0011]
By using the NTRU public key cryptosystem, the amount of calculation can be reduced as compared with the case of using a prime factorization type cryptosystem or the case of using a discrete logarithm type cryptosystem. In the information registration server, it is verified that both the polynomial x and the polynomial r are short polynomials, and that the relationship of a = p * r * h + x−c * e (mod q) is satisfied. By doing so, information registration is performed only when the information registration server can verify that the user of the terminal device knows the plaintext information α corresponding to the ciphertext e, thereby eliminating illegal information registration. Can do. As a result, when registering information in the information registration server, the amount of calculation can be reduced without impairing the reliability of information registration.
[0012]
DETAILED DESCRIPTION OF THE INVENTION
Before describing the information registration system according to the embodiment of the present invention, the NTRU public key cryptosystem used in the present embodiment will be briefly described.
[0013]
[Definition]
A polynomial a (x) (see formula (2)) belonging to the polynomial ring R (see formula (1)) is regarded as a vector a (see formula (3)), and its center norm | a | is shown in formula (4). Define as follows.
[0014]
[Expression 1]

[0015]
[Expression 2]

[0016]
[Equation 3]

[0017]
[Expression 4]

[0018]
At this time, for example, a polynomial a (x) that satisfies the equation (5) is called a short polynomial.
[0019]
[Equation 5]

[0020]
That is, a short polynomial is such that its center norm becomes smaller than a predetermined threshold value so as to increase as the degree N of the polynomial increases (for example, in proportion to the square root of N). It is a polynomial.
[0021]
Further, an arithmetic expression a (x) · b (x) (mod x) using a polynomial a (x) represented by the expression (2) and a polynomial b (x) represented by the expression (6).^N-1) is represented by a * b.
[0022]
[Formula 6]

[0023]
Here, if c (x) = a * b (see equation (7)) is regarded as a vector c (see equation (8)), vector a (see equation (3)) and vector b (see equation (9)) ) And the vector c (see equation (8)) satisfy the relationship of equation (10).
[0024]
[Expression 7]

[0025]
[Equation 8]

[0026]
[Equation 9]

[0027]
[Expression 10]

[0028]
[Preparation]
For an appropriate natural number N (e.g., a value of 100 to 500), a large modulus value q (e.g., a value about half of N) and a small modulus value p (e.g., a value such as 2, 3) are expressed as x.^N−1, p, q are determined to be relatively prime. R_p, R_q, Z_p, Z_qA set of N-1th order polynomials with elements of.
[0029]
[Key generation]
Short polynomials f and g are arbitrarily determined, and these are used as secret keys. For this polynomial f, F satisfying equation (11)_pAnd F satisfying equation (12)_qThen, the public key h is calculated by the equation (13).
[0030]
## EQU11 ##

[0031]
[Expression 12]

[0032]
[Formula 13]

[0033]
[encryption]
Message space L to which message m belongs_mIs defined as in equation (14). Here, a random short polynomial r is defined for the message m, and a ciphertext e is generated using the equation (15).
[0034]
[Expression 14]

[0035]
[Expression 15]

[0036]
[Decryption]
From the secret key f and the ciphertext e, a is calculated using the equation (16), and b is further calculated using the equation (17)._pInverse element F_pThus, the message m can be decrypted using the equation (18).
[0037]
[Expression 16]

[0038]
[Expression 17]

[0039]
[Expression 18]

[0040]
[NTRU assumption]
NTRU public key cryptosystem is R_qThis is based on the assumption that it is difficult to obtain short polynomials f and g satisfying the equation (19) when a polynomial h belonging to is given.
[0041]
[Equation 19]

[0042]
This is because when deg h = N−1, the most efficient method for obtaining the secret keys f and g is considered to solve the problem of searching for a short vector on a 2N-dimensional lattice.
[0043]
Next, definitions used to describe the information registration system according to the embodiment of the present invention will be described. First, two sets S₁, S₂Are defined as shown in equations (20) and (21), respectively.
[0044]
[Expression 20]

[0045]
[Expression 21]

[0046]
That is, the set S₂Is a set of short polynomials and S₁Is a set of even shorter polynomials. Here, the shorter polynomial is a polynomial whose center norm is smaller than a predetermined threshold value not depending on the degree N of the polynomial. Therefore, when the degree N of the polynomial is large (for example, 100 to 500), the center norm of the shorter polynomial is sufficiently smaller than the center norm of the short polynomial.
[0047]
Under the above definition, the set Lα, Lφ, L_c, L_x, L_rEach satisfies the equation (22).
[0048]
[Expression 22]

[0049]
That is, the set Lα, Lφ, L_x, L_rEach is a set of short polynomials and the set L_cIs a set of even shorter polynomials.
[0050]
Here, α is an element of the set Lα, φ is an element of the set Lφ, and c is the set L_cIf ξ is an element of the set Lξ and ψ is an element of the set Lψ, the sets Lξ and Lψ that satisfy the expressions (23), (24), and (25) are determined.
[0051]
[Expression 23]

[0052]
[Expression 24]

[0053]
[Expression 25]

[0054]
For example, the set Lα, Lφ, L_c, L_x, L_rAre respectively expressed by equations (26) to (30), the sets Lξ and Lψ can be defined by equations (31) and (32), respectively.
[0055]
[Equation 26]

[0056]
[Expression 27]

[0057]
[Expression 28]

[0058]
[Expression 29]

[0059]
[30]

[0060]
[31]

[0061]
[Expression 32]

[0062]
In the following, the sets Lα, Lφ, L_c, Lξ, Lψ, L_x, L_rAre defined as shown in equations (33) to (39). Set L^* _cfIs given by equation (40).
[0063]
[Expression 33]

[0064]
[Expression 34]

[0065]
[Expression 35]

[0066]
[Expression 36]

[0067]
[Expression 37]

[0068]
[Formula 38]

[0069]
[39]

[0070]
[Formula 40]

[0071]
Next, an information registration system according to an embodiment of the present invention will be described with reference to the drawings. The information registration system according to the present embodiment includes a terminal device and an information registration server according to the embodiment of the present invention.
[0072]
First, the configuration of the information registration system according to the present embodiment will be described. FIG. 1 is a configuration diagram of an information registration system according to the present embodiment. The information registration system 10 according to the present embodiment includes a mobile communication terminal 12 (terminal device) and an information registration server 14 and registers information (for example, secret information) transmitted from the mobile communication terminal 12 in the information registration server 14. Information registration system.
[0073]
Here, the mobile communication terminal 12 and the information registration server 14 are connected via a network 16 such as a mobile communication network so that data can be transmitted and received between them. Each of the mobile communication terminal 12 and the information registration server 14 is connected to the key generation server 18 via the network 16 and can receive data such as a public key transmitted from the key generation server 18. It is like that.
[0074]
The mobile communication terminal 12 is physically configured as a mobile phone including a CPU, a memory, a display, an input key, a data transmission / reception circuit, and the like. The mobile communication terminal 12 includes, as functional components, a first ciphertext generation unit 20 (first ciphertext generation unit), a first ciphertext transmission unit 22 (first ciphertext transmission unit), 2 ciphertext generator 24 (second ciphertext generator), second ciphertext transmitter 26 (second ciphertext transmitter), challenge receiver 28 (challenge receiver), and response generator 30 (Response generation means) and a response transmission unit 32 (response transmission means).
[0075]
The information registration server 14 physically includes a CPU, a memory, a display, a storage device such as a magnetic disk device and an optical disk device, an input device such as a keyboard and a mouse, and a data transmission / reception device such as a modem and a digital communication unit. Configured as a computer system. The information registration server 14 includes, as functional components, a first ciphertext receiving unit 36 (first ciphertext receiving unit), a second ciphertext receiving unit 38 (second ciphertext receiving unit), a challenge, A transmission unit 40 (challenge transmission unit), a response reception unit 42 (response reception unit), a verification unit 44 (verification unit), and an information registration unit 46 (information registration unit) are configured. Hereinafter, each component will be described in detail.
[0076]
The first ciphertext generation unit 20 of the mobile communication terminal 12 uses the short polynomial φ, the public key h, the small modulus value p, and the large modulus value q according to the above-described NTRU public key cryptosystem, according to the equation (41). Then, a ciphertext e of plaintext α (plaintext of information that the user of the mobile communication terminal 12 wants to register in the information registration center 14) expressed by a short polynomial is generated.
[0077]
[Expression 41]

[0078]
Here, the public key h, the small modulus value p, and the large modulus value q are generated in advance by the key generation server 18 and transmitted from the key generation server 18 to the mobile communication terminal 12. The plain text α is an element of the set Lα shown in the equation (33), and is input by the user of the mobile communication terminal 12. Moreover, the short polynomial φ is an element of the set Lφ shown in the equation (34), and may be input by the user of the mobile communication terminal 12 or may be randomly generated by the first ciphertext generation unit 20.
[0079]
The first ciphertext transmission unit 22 transmits the ciphertext e generated by the first ciphertext generation unit 20 to the information registration server 14.
[0080]
The second ciphertext generation unit 24 uses the short polynomial ψ, the public key h, the small modulus value p, and the large modulus value q by the NTRU public key cryptosystem described above, and is short according to the equation (42). A ciphertext a of the polynomial ξ is generated.
[0081]
[Expression 42]

[0082]
Here, the short polynomial ψ is an element of the set Lψ shown in the equation (37), and may be input by the user of the mobile communication terminal 12 or may be randomly generated by the second ciphertext generation unit 24. . Further, the short polynomial ξ is an element of the set Lξ shown in the equation (36), and may be input by the user of the mobile communication terminal 12 or may be randomly generated by the second ciphertext generation unit 24.
[0083]
The second ciphertext transmission unit 26 transmits the ciphertext a generated by the second ciphertext generation unit 24 to the information registration server 14.
[0084]
The challenge receiver 28 receives a polynomial c (challenge) that is further shorter than both the plaintext α and the short polynomial ψ transmitted from the information registration server 14. Here, the shorter polynomial c is a set L shown in the equation (35)._cElements.
[0085]
The response generation unit 30 uses the plaintext α, the short polynomial φ, the short polynomial ψ, the short polynomial ξ, and the shorter polynomial c received by the challenge receiving unit 28 to obtain the equation (43), (44 ), A polynomial x and a polynomial r (response) are generated.
[0086]
[Expression 43]

[0087]
(44)

[0088]
The response transmission unit 32 transmits the polynomial x and the polynomial r (response) generated by the response generation unit 34 to the information registration server 14.
[0089]
The first ciphertext receiving unit 36 of the information registration server 14 receives the ciphertext e transmitted from the mobile communication terminal 12. The second ciphertext receiving unit 38 receives the ciphertext a transmitted from the mobile communication terminal 12.
[0090]
The challenge transmitter 40 transmits a polynomial c (challenge) that is shorter than both the plaintext α and the short polynomial ψ to the mobile communication terminal 12. Here, the shorter polynomial c may be input by the user of the information registration server 14 or may be generated by the challenge transmission unit 40.
[0091]
The response receiving unit 42 receives the polynomial x and the polynomial r (response) transmitted from the mobile communication terminal 12.
[0092]
The verifying unit 44 verifies that both the polynomial x and the polynomial r received by the response receiving unit 42 are short polynomials (ie, the set L in which the polynomial x is expressed by the equation (38))._xAnd the set r of the polynomial r shown in equation (39)_r2) The ciphertext e, the ciphertext a, the public key h, the small modulus value p, the large modulus value q, the shorter polynomial c, and the polynomial It is verified that x and the polynomial r satisfy the expression (45).
[0093]
[Equation 45]

[0094]
Here, the public key h, the small modulus value p, and the large modulus value q are generated in advance by the key generation server 18 and transmitted from the key generation server 18 to the mobile communication terminal 12.
[0095]
When both the above (1) and (2) are verified, the verification unit 44 knows the plaintext α corresponding to the ciphertext e transmitted from the information registration server 14 by the user of the mobile communication terminal 12. It is verified that On the other hand, when at least one of the above (1) and (2) is not verified, the verification unit 44 uses the plaintext α corresponding to the ciphertext e transmitted from the mobile communication terminal 12 to use the mobile communication terminal 12. It is assumed that what the person knows has not been verified.
[0096]
When the verification unit 44 verifies that the user of the mobile communication terminal 12 knows the plaintext α corresponding to the ciphertext e transmitted from the mobile communication terminal 12, the information registration unit 46 The ciphertext e is registered. Registration of the ciphertext e is performed by storing the ciphertext e in a predetermined area of a storage device provided in the information registration server 14 in association with information for identifying the mobile communication terminal 12.
[0097]
Here, both the polynomials x and r are short polynomials (that is, the set L in which the polynomial x is shown in the equation (38))._xAnd the set r of the polynomial r shown in the equation (39)_rIt is proved by proving the following three lemmas that the verifiable cryptosystem is realized by verifying that the expression (45) is satisfied.
[0098]
[Lemma 1] If the prover (mobile communication terminal 12) is correct, it is accepted by the above verification.
[0099]
When x is expressed by the equation (46) and r is expressed by the equation (47), ξ, ψ, c, α, and φ satisfy the equation (48), so x and r are expressed by the equation (49). Meet.
[0100]
[Equation 46]

[0101]
[Equation 47]

[0102]
[Formula 48]

[0103]
[Equation 49]

[0104]
Further, the above equation (41) is expressed as equation (50) using an arbitrary polynomial E that is an element of R.
[0105]
[Equation 50]

[0106]
Similarly, the above equation (42) is expressed as equation (51) using an arbitrary polynomial A which is an element of R.
[0107]
[Equation 51]

[0108]
Here, using the formulas (46), (47), (50), and (51), the formula (52) is derived.
[0109]
[Formula 52]

By applying mod q to equation (52), equation (53) is derived.
[0110]
[Equation 53]

(End of proof)
[0111]
[Lemma 2] If the prover is wrong, the error rate ε ≧ 3 / # L by the above verification._cRejected.
[0112]
Error rate ε ≧ 3 / # L_c#L_c#L for street questions_cThere are ε ≧ 3 errors. That is, L_cCan select at least three different c, c ', c "satisfying the verification equation.
[0113]
Here, the public key h is inputted from the forking lemma, and e, (x, r, c), (x ′, r ′, c ′), (x ″, r ″ satisfying the expression (54). , C ″) is assumed to exist.
[0114]
[Formula 54]

[0115]
At this time, Δx₁, Δx₂, Δr₁, Δr₂, Δc₁, Δc₂(55) to (60), the equations (61) and (62) are derived from the equation (54).
[0116]
[Expression 55]

[0117]
[Expression 56]

[0118]
[Equation 57]

[0119]
[Formula 58]

[0120]
[Formula 59]

[0121]
[Expression 60]

[0122]
[Equation 61]

[0123]
[62]

[0124]
Subsequently, q * A in the formulas (61) and (62)₁, Q * A₂Respectively, and Δc on each side₂, Δc₁(63) is derived by multiplying by.
[0125]
[Equation 63]

[0126]
Here, if ΔX and ΔR are respectively set as in the expressions (64) and (65), the expression (66) is derived from the expression (63), and as a result, the expression (67) is satisfied.
[0127]
[Expression 64]

[0128]
[Equation 65]

[0129]
[Equation 66]

[0130]
[Expression 67]

[0131]
| ΔX | and | ΔR | satisfy the expressions (68) and (69), respectively, which means that the NTRU lattice can be solved in polynomial time.
[0132]
[Equation 68]

[0133]
[Equation 69]

[0134]
This means that if it is difficult to solve the NTRU lattice, the prover will not lie.
(End of proof)
[0135]
[Lemma 3] In the above verification, information regarding the plaintext α is not given to the verifier (information registration server 14).
[0136]
Create the following simulator. That is, for a given e, L_xX ', L which are elements of_rR ', L which are elements of_cC 'which is an element of is selected at random. Then, (h, e, p * r ′ * h + x′−c ′ * e (mod q)) is queried to the random oracle. Since the probability that the same question has already been asked is very small, Random Oracle will list the answer to this question as c '. At this time, the proof by the output of the simulator is (x ', r', c ').
[0137]
At this time, # Lα, # Lφ, #L_c, #L_x, #L_rSatisfies the expressions (70) to (73) and is extremely small, so that a series of (x, r, c) appearing in the verifiable encryption method is generated by the simulator (x ′, r ′, c ′). Statistically indistinguishable from
[0138]
[Equation 70]

[0139]
[Equation 71]

[0140]
[Equation 72]

[0141]
[Equation 73]

[0142]
Anyone can create the simulator. This means that the verifier does not get information about plaintext.
(End of proof)
[0143]
Subsequently, an operation of the information registration system according to the present embodiment will be described, and an information registration method according to the embodiment of the present invention will be described.
[0144]
FIG. 2 is a flowchart showing the operation of the information registration system 10 according to the present embodiment. The public key h generated by the key generation server 18, the small modulus value p, and the large modulus value q are transmitted in advance to the mobile communication terminal 12 and the information registration server 14 constituting the information registration system 10. .
[0145]
When registering information from the mobile communication terminal 12 to the information registration server 14, first, the user of the mobile communication terminal 12 uses the information registration center 14 in the mobile communication terminal 12 based on the above equation (41). The ciphertext e for the plaintext α of the information desired to be registered is generated (S12) and transmitted to the information registration server 14 (S14). Here, α is an element of the set Lα shown in the equation (33), and φ (see FIG. 2) is an element of the set Lφ shown in the equation (34).
[0146]
In the mobile communication terminal 12, the ciphertext a for the polynomial ξ is generated based on the above equation (42) (S16) and transmitted to the information registration server 14 (S18). Here, ξ is an element of the set Lξ shown in Equation (36), and ψ (see FIG. 2) is an element of the set Lψ shown in Equation (37).
[0147]
Subsequently, a shorter polynomial c (challenge) is transmitted from the information registration server 14 that has received the ciphertext e and the ciphertext a to the mobile communication terminal 12 (S20). Here, the shorter polynomial c is a set L shown in the equation (35)._cElements.
[0148]
When a shorter polynomial c (challenge) transmitted from the information registration server 14 is received by the mobile communication terminal 12, the mobile communication terminal 12 uses the polynomial x and the polynomial r (response) according to the equations (43) and (44). ) Is generated (S22), and the generated polynomial x and polynomial r (response) are transmitted to the information registration server 14 (S24).
[0149]
Thereafter, in the information registration server 14, both the polynomial x and the polynomial r transmitted from the mobile communication terminal 12 are short polynomials (that is, the set L in which the polynomial x is expressed by the equation (38))._xAnd the set r of the polynomial r shown in the equation (39)_r(S26), the ciphertext e, the ciphertext a, the public key h, the small modulus value p, the large modulus value q, the shorter polynomial c, and the polynomial x. It is verified that the polynomial r satisfies the expression (45) (S28).
[0150]
Here, when at least one of the polynomial x and the polynomial r transmitted from the mobile communication terminal 12 is not a short polynomial (that is, the set L in which the polynomial x is expressed by the equation (38))_xOr a set L in which the polynomial r is shown in the equation (39)_rIn the information registration server 14, it is determined that the user of the mobile communication terminal 12 does not know the plaintext α corresponding to the ciphertext e transmitted from the mobile communication terminal 12, and the information registration server 14 Information registration is not performed. The ciphertext e, the ciphertext a, the public key h, the small modulus value p, the large modulus value q, the shorter polynomial c, the polynomial x, and the polynomial r are expressed by the following equation (45). Even if not satisfied, it is determined in the information registration server 14 that the user of the mobile communication terminal 12 does not know the plaintext α corresponding to the ciphertext e transmitted from the mobile communication terminal 12. Information registration is not performed.
[0151]
On the other hand, both the polynomial x and the polynomial r transmitted from the mobile communication terminal 12 are short polynomials (that is, the polynomial x is an element of the set L shown in the equation (38) and the polynomial r is an equation (39). And the ciphertext e, the ciphertext a, the public key h, the small modulus value p, the large modulus value q, the shorter polynomial c, the polynomial x, and the above When the polynomial r satisfies the expression (45), the information registration server 14 knows the plaintext α corresponding to the ciphertext e transmitted from the mobile communication terminal 12 by the user of the mobile communication terminal 12. The information is registered in the information registration server 14 (S30). More specifically, the ciphertext e transmitted from the mobile communication terminal 12 is stored in a predetermined area of the storage device provided in the information registration server 14 in association with information for identifying the mobile communication terminal 12. . In this case, the information registration server 14 may further receive the plaintext α corresponding to the ciphertext e from the mobile communication terminal 12 and register the plaintext α in the information registration server 14.
[0152]
In the above flow described with reference to FIG. 2, when the ciphertext a is not transmitted from the mobile communication terminal 12 to the information registration server 14, and the polynomial x, r (response) is not transmitted, Processing is aborted.
[0153]
Further, the above-described flow described with reference to FIG. 2 is disclosed to a third party other than the mobile communication terminal 12 and the information registration server 14, and the information transmission / reception flow between the mobile communication terminal 12 and the information registration server 14 is correct. It may be possible to confirm whether or not from the outside. By publishing the above flow described with reference to FIG. 2 to a third party, the third party (for example, a service provider providing a service to the mobile communication terminal 12) makes any inquiry to the information registration server 14. The mobile communication terminal 12 can know that a certain amount of information has been registered with the information registration server 14, and can quickly send and receive data to and from the mobile communication terminal 12 (for example, provide a quick service) ) Is possible.
[0154]
Then, the effect | action and effect of the information registration system concerning this embodiment are demonstrated. The information registration system 10 according to the present embodiment uses the NTRU public key cryptosystem, thereby reducing the amount of calculation as compared with the case of using a prime factorization type cryptosystem or the case of using a discrete logarithm cryptosystem. be able to. This is because the NTRU public key cryptosystem is an encryption system mainly for product and sum operations, whereas the encryption system according to the prior art is an encryption system mainly for exponential operations. In the information registration system 10 according to the present embodiment, the information registration server 14 verifies that both the polynomial x and the polynomial r are short polynomials, and a = p * r * h + x−c * e. Information is verified only when the information registration server 14 can verify that the user of the mobile communication terminal 12 knows the plaintext α corresponding to the ciphertext e by verifying that the relationship of (mod q) is satisfied. Register. Therefore, unauthorized information registration can be eliminated. As a result, when registering information in the information registration server 14, the amount of calculation can be reduced without impairing the reliability of information registration.
[0155]
In addition, the information registration system 10 according to the present embodiment is a case where the assumption for using the prime factorization type encryption method or the discrete logarithm type encryption method is no longer established by using the NTRU public key encryption method. Can be used.
[0156]
The information registration system 10 according to the present embodiment can be suitably used for, for example, key deposit on a network such as the Internet. Further, since the calculation amount is small, the present invention can be suitably applied to a portable terminal such as a mobile phone or an IC card.
[0157]
【The invention's effect】
The information registration method and information registration system according to the present invention use the NTRU public key cryptosystem, thereby reducing the amount of calculation compared to using a prime factorization cryptosystem or a discrete logarithm cryptosystem. can do. In the information registration server, it is verified that both the polynomial x and the polynomial r are short polynomials, and that the relationship of a = p * r * h + x−c * e (mod q) is satisfied. Thus, unauthorized information registration can be eliminated by performing information registration only when the information registration server can verify that the user of the terminal device knows the plaintext α corresponding to the ciphertext e. . As a result, when registering information in the information registration server, the amount of calculation can be reduced without impairing the reliability of information registration.
[Brief description of the drawings]
FIG. 1 is a configuration diagram of an information registration system.
FIG. 2 is a flowchart showing the operation of the information registration system.
[Explanation of symbols]
DESCRIPTION OF SYMBOLS 10 ... Information registration system, 12 ... Mobile communication terminal, 14 ... Information registration server, 16 ... Network, 18 ... Key generation server, 20 ... 1st ciphertext generation part, 22 ... 1st ciphertext transmission part, 24 ... 2nd Ciphertext generation unit, 26 ... second ciphertext transmission unit, 28 ... challenge reception unit, 30 ... response generation unit, 32 ... response transmission unit, 36 ... first ciphertext reception unit, 38 ... second ciphertext reception unit, 40 ... Challenge transmission unit, 42 ... Response reception unit, 44 ... Verification unit, 46 ... Information registration unit

Claims (4)

In an information registration method for registering information transmitted from a terminal device in an information registration server,
According to the NTRU public key cryptosystem, the terminal device uses the short polynomial φ, the public key h, the small modulus value p, and the large modulus value q, and the ciphertext e = p * of the information α represented by the short polynomial. a first ciphertext generation step of generating φ * h + α (mod q);
A first ciphertext transmission step in which the terminal device transmits the ciphertext e generated in the first ciphertext generation step to the information registration server;
The terminal device uses a short polynomial ψ, the public key h, the small modulus value p, and the large modulus value q using the NTRU public key cryptosystem, and the ciphertext a = p * ψ * h + ξ of the short polynomial ξ. A second ciphertext generation step of generating (mod q);
A second ciphertext transmission step in which the terminal device transmits the ciphertext a generated in the second ciphertext generation step to the information registration server;
A challenge transmission step in which the information registration server transmits a polynomial c shorter than the information α and the short polynomial ψ to the terminal device;
The terminal device uses the information α, the short polynomial φ, the short polynomial ψ, the short polynomial ξ, and the shorter polynomial c transmitted from the information registration server to generate a polynomial x = ξ + c * α and a polynomial. a response generation step of generating r = ψ + c * φ;
A response transmission step in which the terminal device transmits the polynomial x and the polynomial r generated in the response generation step to the information registration server;
The information registration server verifies that both the polynomial x and the polynomial r transmitted from the terminal device are short polynomials, and the ciphertext e, the ciphertext a, the public key h, and the Verifying that the small modulus value p, the large modulus value q, the shorter polynomial c, the polynomial x, and the polynomial r satisfy the relationship a = p * r * h + x−c * e (mod q). A verification step for verifying that the user of the terminal device knows the information α corresponding to the ciphertext e transmitted from the terminal device;
When the information registration server verifies that the user of the terminal device knows the information α corresponding to the ciphertext e transmitted from the terminal device by the verification step, the information α or the information α An information registration method comprising an information registration step of registering a ciphertext e of information α. In the terminal device used in the information registration method for registering information transmitted from the terminal device in the information registration server,
The ciphertext e = p * φ * h + α (mod of the information α expressed by the short polynomial using the short polynomial φ, the public key h, the small modulus value p, and the large modulus value q by the NTRU public key cryptosystem. first ciphertext generating means for generating q);
First ciphertext transmission means for transmitting the ciphertext e generated by the first ciphertext generation means to the information registration server;
Using the NTRU public key cryptosystem, the short polynomial ψ, the public key h, the small modulus value p, and the large modulus value q are used to convert the ciphertext a = p * ψ * h + ξ (mod q) of the short polynomial ξ. Second ciphertext generating means for generating;
Second ciphertext transmission means for transmitting the ciphertext a generated by the second ciphertext generation means to the information registration server;
Challenge receiving means for receiving a polynomial c shorter than the information α and the short polynomial ψ transmitted from the information registration server;
Using the information α, the short polynomial φ, the short polynomial ψ, the short polynomial ξ, and the shorter polynomial c received by the challenge receiving means, a polynomial x = ξ + c * α and a polynomial r = ψ + c * φ A response generating means for generating
A terminal device comprising: response transmission means for transmitting the polynomial x and the polynomial r generated by the response generation means to the information registration server. In the information registration server used in the information registration method of registering information transmitted from the terminal device in the information registration server,
According to the NTRU public key cryptosystem, the short polynomial φ, the public key h, the small modulus value p, and the large modulus value q are generated in the terminal device and transmitted from the terminal device, and expressed by the short polynomial. First ciphertext receiving means for receiving ciphertext e = p * φ * h + α (mod q) of information α;
According to the NTRU public key cryptosystem, a short polynomial ξ generated by the terminal device using the short polynomial ψ, the public key h, the small modulus value p, and the large modulus value q and transmitted from the terminal device Second ciphertext receiving means for receiving ciphertext a = p * ψ * h + ξ (mod q);
Challenge transmitting means for transmitting a polynomial c shorter than both the information α and the short polynomial ψ to the terminal device;
A polynomial x = ξ + c * α, which is generated in the terminal device using the information α, the short polynomial φ, the short polynomial ψ, the short polynomial ξ, and the shorter polynomial c, and is transmitted from the terminal device, Response receiving means for receiving the polynomial r = ψ + c * φ;
It is verified that both the polynomial x and the polynomial r received by the response receiving means are short polynomials, and the ciphertext e, the ciphertext a, the public key h, the small modulus value p, and the By verifying that the large modulus value q, the shorter polynomial c, the polynomial x, and the polynomial r satisfy the relationship a = p * r * h + x−c * e (mod q), the terminal device Verification means for verifying that the user of the terminal device knows information α corresponding to the transmitted ciphertext e;
When the verification unit verifies that the user of the terminal device knows the information α corresponding to the ciphertext e transmitted from the terminal device, the information α or the ciphertext e of the information α An information registration server comprising: information registration means for registering the information. In an information registration system comprising a terminal device and an information registration server, and registering information transmitted from the terminal device in the information registration server,
The terminal device is the terminal device according to claim 2,
The information registration system according to claim 3, wherein the information registration server is the information registration server according to claim 3.

Images