[go: up one dir, main page]

JP6770075B2 - 暗号化メッセージ検索方法、メッセージ送受信システム、端末、プログラム - Google Patents

暗号化メッセージ検索方法、メッセージ送受信システム、端末、プログラム Download PDF

Info

Publication number
JP6770075B2
JP6770075B2 JP2018538376A JP2018538376A JP6770075B2 JP 6770075 B2 JP6770075 B2 JP 6770075B2 JP 2018538376 A JP2018538376 A JP 2018538376A JP 2018538376 A JP2018538376 A JP 2018538376A JP 6770075 B2 JP6770075 B2 JP 6770075B2
Authority
JP
Japan
Prior art keywords
search
message
encrypted
key
private key
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Active
Application number
JP2018538376A
Other languages
English (en)
Other versions
JPWO2018047698A1 (ja
Inventor
裕樹 岡野
裕樹 岡野
麗生 吉田
麗生 吉田
陵 西巻
陵 西巻
鉄太郎 小林
鉄太郎 小林
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
Nippon Telegraph and Telephone Corp
Original Assignee
Nippon Telegraph and Telephone Corp
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by Nippon Telegraph and Telephone Corp filed Critical Nippon Telegraph and Telephone Corp
Publication of JPWO2018047698A1 publication Critical patent/JPWO2018047698A1/ja
Application granted granted Critical
Publication of JP6770075B2 publication Critical patent/JP6770075B2/ja
Active legal-status Critical Current
Anticipated expiration legal-status Critical

Links

Images

Classifications

    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L9/00—Cryptographic mechanisms or cryptographic arrangements for secret or secure communications; Network security protocols
    • H04L9/08—Key distribution or management, e.g. generation, sharing or updating, of cryptographic keys or passwords
    • H04L9/0861—Generation of secret information including derivation or calculation of cryptographic keys or passwords
    • H04L9/0869—Generation of secret information including derivation or calculation of cryptographic keys or passwords involving random numbers or seeds
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L9/00—Cryptographic mechanisms or cryptographic arrangements for secret or secure communications; Network security protocols
    • H04L9/08—Key distribution or management, e.g. generation, sharing or updating, of cryptographic keys or passwords
    • H04L9/0816—Key establishment, i.e. cryptographic processes or cryptographic protocols whereby a shared secret becomes available to two or more parties, for subsequent use
    • H04L9/0819—Key transport or distribution, i.e. key establishment techniques where one party creates or otherwise obtains a secret value, and securely transfers it to the other(s)
    • H04L9/0822—Key transport or distribution, i.e. key establishment techniques where one party creates or otherwise obtains a secret value, and securely transfers it to the other(s) using key encryption key
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING OR COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F16/00—Information retrieval; Database structures therefor; File system structures therefor
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING OR COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F16/00—Information retrieval; Database structures therefor; File system structures therefor
    • G06F16/20—Information retrieval; Database structures therefor; File system structures therefor of structured data, e.g. relational data
    • G06F16/24—Querying
    • G06F16/245—Query processing
    • G—PHYSICS
    • G09—EDUCATION; CRYPTOGRAPHY; DISPLAY; ADVERTISING; SEALS
    • G09C—CIPHERING OR DECIPHERING APPARATUS FOR CRYPTOGRAPHIC OR OTHER PURPOSES INVOLVING THE NEED FOR SECRECY
    • G09C1/00—Apparatus or methods whereby a given sequence of signs, e.g. an intelligible text, is transformed into an unintelligible sequence of signs by transposing the signs or groups of signs or by replacing them by others according to a predetermined system
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L63/00—Network architectures or network communication protocols for network security
    • H04L63/04—Network architectures or network communication protocols for network security for providing a confidential data exchange among entities communicating through data packet networks
    • H04L63/0428—Network architectures or network communication protocols for network security for providing a confidential data exchange among entities communicating through data packet networks wherein the data content is protected, e.g. by encrypting or encapsulating the payload
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L9/00—Cryptographic mechanisms or cryptographic arrangements for secret or secure communications; Network security protocols
    • H04L9/08—Key distribution or management, e.g. generation, sharing or updating, of cryptographic keys or passwords
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L9/00—Cryptographic mechanisms or cryptographic arrangements for secret or secure communications; Network security protocols
    • H04L9/08—Key distribution or management, e.g. generation, sharing or updating, of cryptographic keys or passwords
    • H04L9/0816—Key establishment, i.e. cryptographic processes or cryptographic protocols whereby a shared secret becomes available to two or more parties, for subsequent use
    • H04L9/0819—Key transport or distribution, i.e. key establishment techniques where one party creates or otherwise obtains a secret value, and securely transfers it to the other(s)
    • H04L9/0825—Key transport or distribution, i.e. key establishment techniques where one party creates or otherwise obtains a secret value, and securely transfers it to the other(s) using asymmetric-key encryption or public key infrastructure [PKI], e.g. key signature or public key certificates
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L9/00—Cryptographic mechanisms or cryptographic arrangements for secret or secure communications; Network security protocols
    • H04L9/08—Key distribution or management, e.g. generation, sharing or updating, of cryptographic keys or passwords
    • H04L9/0816—Key establishment, i.e. cryptographic processes or cryptographic protocols whereby a shared secret becomes available to two or more parties, for subsequent use
    • H04L9/085—Secret sharing or secret splitting, e.g. threshold schemes
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L9/00—Cryptographic mechanisms or cryptographic arrangements for secret or secure communications; Network security protocols
    • H04L9/08—Key distribution or management, e.g. generation, sharing or updating, of cryptographic keys or passwords
    • H04L9/0894—Escrow, recovery or storing of secret information, e.g. secret key escrow or cryptographic key storage
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L9/00—Cryptographic mechanisms or cryptographic arrangements for secret or secure communications; Network security protocols
    • H04L9/14—Cryptographic mechanisms or cryptographic arrangements for secret or secure communications; Network security protocols using a plurality of keys or algorithms
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L9/00—Cryptographic mechanisms or cryptographic arrangements for secret or secure communications; Network security protocols
    • H04L9/14—Cryptographic mechanisms or cryptographic arrangements for secret or secure communications; Network security protocols using a plurality of keys or algorithms
    • H04L9/16—Cryptographic mechanisms or cryptographic arrangements for secret or secure communications; Network security protocols using a plurality of keys or algorithms the keys or algorithms being changed during operation

Landscapes

  • Engineering & Computer Science (AREA)
  • Computer Security & Cryptography (AREA)
  • Computer Networks & Wireless Communication (AREA)
  • Signal Processing (AREA)
  • Theoretical Computer Science (AREA)
  • General Engineering & Computer Science (AREA)
  • Physics & Mathematics (AREA)
  • General Physics & Mathematics (AREA)
  • Data Mining & Analysis (AREA)
  • Databases & Information Systems (AREA)
  • Computing Systems (AREA)
  • Computational Linguistics (AREA)
  • Computer Hardware Design (AREA)
  • Information Retrieval, Db Structures And Fs Structures Therefor (AREA)

Description

この発明は情報セキュリティ技術の応用に関し、特に、グループを形成する複数のユーザがメッセージを送受信するメッセージ送受信技術に関する。
ビジネスでの利用を前提とするメッセージ送受信システムの中には、パソコンやスマートフォンなど端末の種別を問わないマルチデバイス対応なもので、ビジネス上の機密情報漏えいを考慮して端末にメッセージを含むデータを残さないような、クラウドベース型のメッセージ送受信システムが存在する。クラウドベース型のメッセージ送受信システムの例として、非特許文献１のような製品がある。
このようなクラウドベース型のメッセージ送受信システムは、通信路を暗号化することにより盗聴を防止する機能や、既に述べたように端末にデータを残さないことにより端末の紛失や不正な持ち出しに起因する情報漏えいを防止する機能を備えている。このように現在のクラウドベース型のメッセージ送受信システムは、通信経路と端末に対する脅威については対応しているが、その一方でメッセージ送受信システムを構成するサーバに対する脅威については必ずしも対応が十分とは言えない状況である。ここでいうサーバに対する脅威には、例えば、サーバに対する外部からの攻撃、サーバ管理者等による内部からの不正アクセスなどがある。
このサーバに対する脅威に対しては、サーバに保存するメッセージを暗号化するという対策が考えられる。しかし、サーバにおいて復号可能である場合は、上述の脅威に対してサーバからメッセージが漏えいする可能性が依然として存在する。したがって、メッセージがサーバに対して秘匿化されている、つまりサーバにおいて盗聴されないようになっていることが重要である。
サーバにおいて盗聴されないようにする1つの方法としては、サーバに対してメッセージを秘匿化しつつ端末においてのみメッセージの復号が可能となるようなエンドツーエンドでの暗号化通信を実現する方法がある。このようなエンドツーエンドでの暗号化通信を実現するためには、端末で用いる共通鍵（以下、セッション鍵ともいう）を端末間でどのように共有するかが問題となる。その解決策として、中央に認証サーバを持つスター型のネットワークにおいて、認証サーバに対していかなる情報ももらさずに利用者間で共通鍵を共有するプロトコルが提案されている（非特許文献２）。非特許文献２のプロトコルにより、サーバに対しメッセージを秘匿化したまま端末間で送受信が可能となる。
しかし、ビジネスでの利用を踏まえると、過去のメッセージのやりとりに関して効率よく処理する方法が必要になる。そのような手段として、メッセージの検索機能が考えられるが、非特許文献２のプロトコルによる利用者間でのセッション鍵共有技術を適用した場合、サーバに保存されているメッセージは暗号化されているため、サーバに保存されたメッセージを秘匿化したまま検索できるようにする必要がある。さらに、検索内容そのものや過去の検索に対する回答の傾向等から秘匿化した内容が推測されにくくすることも必要である。
サーバに保存された暗号化メッセージを含む暗号化データを復号することなく検索する方法として、暗号化データに関する情報についてのハッシュ値をサーバに記録する方法がある（特許文献１）。
"ビジネス向けグループチャットTopicRoom"，［online］，［平成28年8月16日検索］，インターネット<URL: https://www.ntts.co.jp/products/topicroom/index.html> 小林鉄太郎，米山一樹，吉田麗生，川原祐人，冨士仁，山本具英："スケーラブルな動的多者鍵配布プロトコル"，SCIS2016，4E2-3，2016．
特開2015-118603号公報
しかし、特許文献１の検索技術では、同じ情報に対して常に同じハッシュ値が得られるため、一定期間通信路を盗聴することで得られるハッシュ値とレインボーテーブルを用いることにより検索しようとしている情報やその検索結果が推測されてしまうという問題がある。
この発明の目的は、このような点に鑑みて、n台の端末で共有するメッセージを暗号化した暗号化メッセージを記録するサーバにおいて暗号化したままメッセージ検索をする際、検索内容や検索結果が推測されにくい暗号化メッセージ検索技術を提供することである。
本発明の一態様は、nを2以上の整数とし、メッセージを共有するn台の端末と前記メッセージを暗号化した暗号化メッセージを記録するサーバとを含むメッセージ送受信システムにおいて、前記端末がメッセージ検索用文字列を用いて前記暗号化メッセージを検索する暗号化メッセージ検索方法であって、前記n台の端末で共有するメッセージを前記サーバが管理する単位をルーム、その識別子をルーム識別子とし、前記n台の端末の記録部には、前記ルーム識別子と、セッション鍵とが記録されており、前記端末が、ルーム識別子共有後または最初の検索用秘密鍵を共有した後は事前に設定された更新間隔が経過する度、検索用秘密鍵として乱数を生成し、前記セッション鍵を用いて前記検索用秘密鍵から暗号化検索用秘密鍵を生成し、前記暗号化検索用秘密鍵を前記サーバに送信する暗号化検索用秘密鍵送信ステップと、前記端末が、前記ルーム識別子を用いて前記サーバから前記暗号化検索用秘密鍵を取得し、前記セッション鍵を用いて前記暗号化検索用秘密鍵から前記検索用秘密鍵を復号する検索用秘密鍵復号ステップと、前記端末が、メッセージを暗号化した暗号化メッセージを生成し、前記メッセージに関係する情報と、前記検索用秘密鍵のうち最新検索用秘密鍵を用いて、メッセージ検索用のインデックス集合を生成し、前記インデックス集合と前記暗号化メッセージとを前記ルーム識別子とともに前記サーバに送信する暗号化メッセージ送信ステップと、前記端末が、前記メッセージ検索用文字列と、前記検索用秘密鍵のうち１つ以上の検索用秘密鍵を用いて、クエリ集合を生成し、前記クエリ集合を前記ルーム識別子とともに前記サーバに送信するクエリ送信ステップと、前記サーバが、前記ルーム識別子と対応付けて管理しているインデックス集合と暗号化メッセージの中から前記クエリ集合の要素と一致するインデックス集合の要素がある暗号化メッセージを検索し、前記暗号化メッセージを前記端末に送信する暗号化メッセージ返信ステップと、前記端末が、前記暗号化メッセージからメッセージを復号する暗号化メッセージ復号ステップと、を含む。
この発明によれば、n台の端末で共有するメッセージを暗号化した暗号化メッセージを記録するサーバにおいて暗号化したままメッセージ検索をする際、検索内容や検索結果が推測されにくい検索を実現することが可能となる。
メッセージ送受信システムの構成を例示する図である。 第一実施形態のサーバ１００の機能構成を例示する図である。 第一実施形態の端末２００の機能構成を例示する図である。 第一実施形態のメッセージ送受信方法の処理フロー（システムセットアップ）を例示する図である。 第一実施形態のメッセージ送受信方法の処理フロー（検索用秘密鍵の共有）を例示する図である。 第一実施形態のメッセージ送受信方法の処理フロー（暗号化メッセージの送信）を例示する図である。 第一実施形態のメッセージ送受信方法の処理フロー（暗号化メッセージの検索）を例示する図である。 第一実施形態のインデックス生成部２４５の動作の様子を例示する図である。 第一実施形態のメッセージ送受信方法の処理フロー（検索用秘密鍵の更新）を例示する図である。 第二実施形態のサーバ５００の機能構成を例示する図である。 第二実施形態の端末６００の機能構成を例示する図である。 第二実施形態のメッセージ送受信方法の処理フロー（システムセットアップ）を例示する図である。
実施形態の説明に先立って、この明細書における表記方法等について説明する。
＜表記方法＞
_（アンダースコア）は下付き添字を表す。例えば、xy_zはyzがxに対する上付き添字であり、xy_zはyzがxに対する下付き添字であることを表す。
ある集合Setについて、Setから要素mを一様ランダムに選ぶことを、m←U Setと表記する。
ある確率的多項式時間アルゴリズムALGについて、入力xに対してALG(x)を確率変数とみたとき、その確率分布に従ってランダムにy が出力されることを、y←R ALG(x)と表記する。
＜定義＞
Nを正の整数全体の集合とする。
関数CRHFを任意長の文字列を入力とし、固定長の文字列を出力する衝突困難ハッシュ関数とする。出力文字列の長さは固定であるが、その長さについては特に限定しない。
関数Fを２つの任意長の文字列を入力とし、文字列を出力する関数とする。出力文字列の長さについては特に限定しない。関数Fの例として、2つの入力文字列を結合する関数F(m, r)=m||rがある。
なお、以下説明する実施形態では、関数CRHF、関数Fとして任意の関数を用いることができる。ただし、関数Fの第２引数は、後述するように平文空間Mpkまたは鍵空間KEYの元となる。
以下、この発明の実施形態について詳細に説明する。なお、図面中において同じ機能を有する構成部には同じ番号を付し、重複説明を省略する。
＜第一実施形態＞
第一実施形態のメッセージ送受信システムは、公開鍵暗号アルゴリズムを用いる。そこで、まず公開鍵暗号アルゴリズムについて説明する。
kをセキュリティパラメータとする。k1∈Nとし、k1ビット長の鍵空間をKEY1={0, 1}k_1とする。
公開鍵暗号方式は、３つのアルゴリズム(Gen, Enc, Dec)からなる。Genは、セキュリティパラメータkを入力とし、公開鍵pkと秘密鍵skの組(pk, sk)を出力する鍵生成アルゴリズムであり、(pk, sk)←R Gen(1k)と表すことにする。また、このとき平文空間Mpkが定まる。
Encは、公開鍵pkと平文m∈Mpkを入力とし、暗号文Cを出力する暗号化アルゴリズムであり、C←R Enc(pk, m)と表すことにする。
Decは、秘密鍵skと暗号文Cを入力とし、平文m’を出力する復号アルゴリズムであり、m’←R Dec(sk, C)と表すことにする。
また、上記３つのアルゴリズムは、任意のセキュリティパラメータk、任意の鍵ペア(pk,sk)←R Gen(1k)、任意の平文m∈Mpkに対し、Dec(sk,Enc(pk,m))=mを満たす。
次に、平文空間Mpkと鍵空間KEY1={0, 1}k_1の直積Mpk×KEY1を定義域、平文空間Mpkを値域とする関数f: Mpk×KEY1→Mpkに対し、関数g: Mpk×KEY1→Mpkが存在し、任意の(K, K1)∈Mpk×KEY1に対し、次式を満たす場合を考える。
Figure 0006770075
RSA暗号や楕円ElGamal暗号については、上記条件（式(1)）を満たす関数f,gの例を挙げることができる。RSA暗号方式の場合、平文空間Mpkは、鍵生成アルゴリズム実行時に生成した２つの素数p,qの積をn=pqとしたとき、{1,…,n-1}のうち、nと互いに素である整数の集合に、次式で定義される演算・が入った乗法群である。
Figure 0006770075
なお、右辺の×は整数同士の通常の積である。
このとき、KEY1=Mpk、つまり、関数f: Mpk×Mpk→Mpk、関数g: Mpk×Mpk→Mpkであり、任意の(K, K1)∈Mpk×Mpkに対し、式(1)を満たす(f,g)の例として、以下の関数の組が存在する。
Figure 0006770075
なお、演算/は、演算・におけるx2の逆元をx2 -1としたとき、x1/x2= x1・x2 -1と定義される演算である。
また、楕円ElGamal暗号の場合、平文空間Mpkは、鍵生成アルゴリズム実行時に生成する楕円曲線上の点がなす加法群である。このとき、KEY1=Mpk、つまり、関数f: Mpk×Mpk→Mpk、関数g: Mpk×Mpk→Mpkであり、任意の(K, K1)∈Mpk×Mpkに対し、式(1)を満たす(f,g)の例として、以下の関数の組が存在する（ただし、+を上記加法群における加法とする）。
Figure 0006770075
なお、演算-は、演算+におけるx2の逆元を-x2としたとき、x1-x2=x1+(-x2)と定義される演算である。
上記条件を満たす公開鍵暗号方式と関数(f,g)の例として、RSA暗号や楕円ElGamal暗号とそれに付随する関数(f,g)を挙げたが、これらの暗号に限られるものでなく、第一実施形態のメッセージ送受信システムの構成に、上記以外の公開鍵暗号方式とそれに付随する関数(f,g)を用いることができる。
［システム構成］
第一実施形態のメッセージ送受信システムは、図１に例示するように、サーバ１００と、n（≧2）台の端末２００を含む。この実施形態では、サーバ１００および端末２００1、…、端末２００nはそれぞれネットワーク３００へ接続される。ネットワーク３００は、サーバ１００、端末２００1、…、端末２００nがそれぞれ相互に通信可能なように構成されたネットワークであればよい。ネットワーク３００には、例えばインターネットなどを用いることができる。
サーバ１００は、図２に例示するように、記録部１１０と、ルーム生成部１２０と、鍵生成部１３０と、インデックス検索部１４０を含む。端末２００i(1≦i≦n)は、図３に例示するように、記録部２１０と、ルーム生成要求送信部２２０と、検索用秘密鍵生成部２３０と、検索用秘密鍵暗号化部２３３と、暗号化検索用秘密鍵復号部２３５と、メッセージ暗号化部２４０と、メッセージID生成部２４３と、インデックス生成部２４５と、クエリ生成部２５０と、暗号化メッセージ復号部２５５を含む。このサーバ１００および端末２００1、…、端末２００nが、図４から図９に例示する各ステップの処理を行うことにより実施形態のメッセージ送受信方法が実現される。
サーバ１００および端末２００iは、例えば、中央演算処理装置（CPU: Central Processing Unit）、主記憶装置（RAM: Random Access Memory）などを有する公知又は専用のコンピュータに特別なプログラムが読み込まれて構成された特別な装置である。各装置は、例えば、中央演算処理装置の制御のもとで各処理を実行する。各装置に入力されたデータや各処理で得られたデータは、例えば、主記憶装置に格納され、主記憶装置に格納されたデータは必要に応じて中央演算処理装置へ読み出されて他の処理に利用される。各装置が備える各処理部は、少なくとも一部が集積回路等のハードウェアによって構成されていてもよい。
サーバ１００が備える記録部１１０および端末２００iが備える記録部２１０は、例えば、RAM（Random Access Memory）などの主記憶装置、ハードディスクや光ディスクもしくはフラッシュメモリ（Flash Memory）のような半導体メモリ素子により構成される補助記憶装置、またはリレーショナルデータベースやキーバリューストアなどのミドルウェアにより構成することができる。各記録部は秘密情報を記憶するため、（例えば、SIMカードなどのように）耐タンパ性を有する記憶装置であることが望ましい。
［システムセットアップ］
以下、サーバ１００を介してメッセージの送受信をする端末２００1、…、端末２００n（以下、グループともいう）に対して、当該グループで共有するメッセージを管理する単位をルームと呼ぶことにする。具体的には、サーバ１００の記録部１１０に当該グループで共有するメッセージを登録する記録領域（つまり、物理的なルーム）が確保される。このルームを識別するための識別子をルーム識別子という。
ここでは、ルーム識別子roomID、公開鍵pkroomID、秘密鍵skroomID、セッション鍵R1がグループに属する端末２００1、…、端末２００n間で共有される。図４を参照してシステムセットアップのフローについて説明する。
なお、端末２００iとサーバ１００との間は、例えば、TLS通信のように暗号化通信を用いてもよい。また、端末２００iは、パソコンやスマートフォンなどを想定しているが、これらに限られるものでなく、ユーザがメッセージを送受信するのに利用できるものであれば何でもよい。
ルーム生成の要求を出す端末２００iのことを代表端末ということにする。代表端末は端末２００1、…、端末２００nの中から任意に選定してよい。そこで、以下では端末２００1を代表端末とする。また、代表端末２００1以外の端末２００j(2≦j≦n)のことを一般端末２００jということにする。
代表端末２００1のルーム生成要求送信部２２０は、サーバ１００に対してルーム生成要求を送信する（Ｓ４−１０）。サーバ１００が当該要求を受信すると、サーバ１００のルーム生成部１２０は、ルーム識別子roomIDで識別されるルームを生成する（Ｓ４−２０）。その際、サーバ１００の鍵生成部１３０は、鍵生成アルゴリズムにより、roomIDで識別されるルームで暗号化・復号に用いる公開鍵pkroomIDと秘密鍵skroomIDを生成する（Ｓ４−３０）。なお、鍵生成アルゴリズム実行時に同時に平文空間Mpkが定まる。また、公開鍵pkroomIDと秘密鍵skroomIDを生成する公開鍵暗号アルゴリズム(Gen, Enc, Dec)は先述の条件（式(1)）を満たす関数(f,g)が存在すれば任意のアルゴリズムを用いることができる。サーバ１００は、ルーム識別子roomID、公開鍵pkroomID、秘密鍵skroomIDを記録部１１０に記録し、代表端末２００1にこれらのデータを送信する（Ｓ４−４０）。
なお、Ｓ４−１０〜Ｓ４−４０の処理は、次のようなフローで処理してもよい。ルーム生成部１２０がルーム生成要求に従いルームを生成、代表端末２００1にルーム識別子roomIDを送信する。その後、代表端末２００1がルーム識別子roomIDとともに鍵生成要求をサーバ１００に送信、鍵生成部１３０がroomIDで識別されるルーム用の公開鍵pkroomIDと秘密鍵skroomIDを生成、代表端末２００1に公開鍵pkroomIDと秘密鍵skroomIDを送信する。
一般端末２００jは、代表端末２００1からルームへの招待を示すルーム識別子roomIDを受信すると（Ｓ４−５０）、サーバ１００にルーム識別子roomIDを送信し（Ｓ４−５５）、公開鍵pkroomIDと秘密鍵skroomIDを受信する（Ｓ４−６０）。
各端末２００iは、ルーム識別子roomID、公開鍵pkroomID、秘密鍵skroomIDを記録部２１０に記録する。
また、各端末２００iは、セッション鍵R1を共有し、記録部２１０に記録する（Ｓ４−７０）。共有の方法については、例えば、非特許文献２に記載の技術を用いればよい。なお、セッション鍵R1はサーバ１００に対して秘匿化されているものとする。
［検索用秘密鍵の共有］
ここでは、ある端末２００i_0(1≦i0≦n)が生成した検索用秘密鍵SearchKeyがサーバ１００を介してグループに属するすべての端末２００iの間で共有される。図５を参照して検索用秘密鍵SearchKeyの共有のフローについて説明する。
なお、検索用秘密鍵SearchKeyを生成する端末２００i_0は、代表端末２００1であっても一般端末２００jであっても構わない。また、セッション経過に伴い途中で検索用秘密鍵SearchKeyを生成する端末２００i_0がグループから離脱することもありうる。この場合、グループに属するその他の端末２００i_1(i1はi0と異なる1以上n以下の整数)が検索用秘密鍵SearchKeyを生成する役割を引き継ぐものとする。つまり、検索用秘密鍵SearchKeyの生成は、現在グループに参加している端末２００iのいずれかが行うものとする。
端末２００i_0の検索用秘密鍵生成部２３０は、ルーム識別子共有後、ランダムに選択した平文空間Mpkの元rを検索用秘密鍵SearchKeyとして生成する（Ｓ５−１０）。つまり、SearchKey=rとなる。なお、rのことを乱数という。この検索用秘密鍵SearchKeyは、ルーム毎に生成されるものである。端末２００i_0は、検索用秘密鍵SearchKeyを記録部２１０に記録する。
端末２００i_0の検索用秘密鍵暗号化部２３３は、暗号化検索用秘密鍵CipherKey←R Enc(pkroomID, f(SearchKey, R1))を生成し（Ｓ５−２０）、暗号化検索用秘密鍵CipherKeyをルーム識別子roomIDとともにサーバ１００に送信する（Ｓ５−３０）。サーバ１００は、受信した暗号化検索用秘密鍵CipherKeyをルーム識別子roomIDと対応付けて記録部１１０に記録する。
端末２００i_0以外の端末２００i_1は、Ｓ４−５０で受信したルーム識別子roomIDをサーバ１００に送信し（Ｓ５−４０）、サーバ１００から暗号化検索用秘密鍵CipherKeyを受信する（Ｓ５−５０）。
Ｓ５−１０からＳ５−３０の処理は、代表端末２００1がＳ４−５０において一般端末２００jとルーム識別子roomIDを共有した後、いつ実行してもよい。したがって、端末２００i_0以外の端末２００i_1は、Ｓ５−４０の暗号化検索用秘密鍵CipherKeyの取得要求をサーバ１００にいつ送信してもよい。例えば、代表端末２００1からルームへの招待を受けた直後でなく、招待後初めてログインする際でもよい。
端末２００i_1の暗号化検索用秘密鍵復号部２３５は、Temp=Dec(skroomID, CipherKey)を計算、記録部２１０から読み出したセッション鍵R1を用いてSearchKey=g(Temp, R1)を計算、検索用秘密鍵SearchKeyを復号する（Ｓ５−６０）。関数(f,g)が先述の条件（式(1)）を満たすことより、検索用秘密鍵SearchKeyを得ることができる。端末２００i_1は、Ｓ５−６０で得た検索用秘密鍵SearchKeyを記録部２１０に記録する。
端末２００i_0の検索用秘密鍵生成部２３０は、ルーム識別子共有後、検索用秘密鍵生成のため最初の乱数生成（つまり、平文空間Mpkの元rのランダム選択）を実行するが、後ほど詳述するように、以降は検索用秘密鍵更新のため、定期的に乱数を生成し、その都度検索用秘密鍵暗号化部２３３は、検索用秘密鍵から暗号化検索用秘密鍵を生成し、暗号化検索用秘密鍵をサーバ１００に送信する。また、端末２００i_1は更新された暗号化検索用秘密鍵をサーバ１００から適時に取得し、復号することで検索用秘密鍵を取得する。つまり、端末２００iの記録部２１０には、複数の検索用秘密鍵が記録されることになる。以下では、ルーム識別子共有後最初に生成される検索用秘密鍵を第一世代検索用秘密鍵SearchKey1、以降定期的に生成される検索用秘密鍵を順に第二世代検索用秘密鍵SearchKey2、第三世代検索用秘密鍵SearchKey3、…ということにする。また、検索用秘密鍵SearchKeyの中で最も世代が新しいものを最新検索用秘密鍵ということにする。
［暗号化メッセージの送信］
ここでは、端末２００iがルーム識別子roomIDで管理されるルームにメッセージを送信する。その際、メッセージは暗号化される。暗号化したメッセージ（暗号化メッセージ）はルーム識別子roomIDを有するルームと対応付けられてサーバ１００の記録部１１０に記録されるとともに、後ほど暗号化したままで検索ができるよう、検索に用いるインデックスの集合（インデックス集合）とメッセージIDの組も記録される。図６を参照して端末２００iによるメッセージの送信のフローについて説明する。
端末２００iのメッセージ暗号化部２４０は、グループ内で共有したいメッセージm1を暗号化し、暗号化メッセージEnc(m1)を生成する（Ｓ６−１０）。ここで、メッセージの暗号化に用いる鍵は、サーバ１００に秘匿化されている鍵であれば、共通鍵暗号アルゴリズムで生成されるものであっても、公開鍵暗号アルゴリズムで生成されるものであっても構わない。なお、当該鍵はグループ内の端末２００i間で共有されているものとする。また、メッセージを送信する端末２００iは、グループに属する任意の端末である。
メッセージm1を暗号化する際、端末２００iのメッセージID生成部２４３は、暗号化したメッセージEnc(m1)をルーム識別子roomIDで識別されるルーム内で一意に識別するためのメッセージ識別子IDm_1をあわせて生成する（Ｓ６−１５）。サーバ１００に対してメッセージm1を秘匿化したままにする、つまりEnc(m1)をサーバ１００に送信し記録部１１０に記録するので、メッセージ識別子IDm_1を生成する関数は逆像計算が困難である（メッセージ識別子IDm_1からメッセージm1が容易に推測できない）関数であることが好ましい。
更に、メッセージm1を暗号化する際、端末２００iのインデックス生成部２４５は、暗号化したメッセージEnc(m1)を検索するために用いるインデックスをあわせて生成する（Ｓ６−２０）。検索可能な文字列長については上限を設けても、設けなくてもよい。以下では、検索可能な文字列長の上限が定められているものとし、その値をLとし説明する。
以下、インデックスの生成方法について説明する（図７参照）。インデックスの生成では関数Gを用いる。関数Gは、任意長の文字列を入力とし、入力文字列に依存する濃度を有する文字列の集合（文字列集合）を出力する関数とする。なお、関数Gの入力がメッセージm1である場合、関数Gの出力である文字列集合のことをメッセージm1に関係する情報といい、G(m1)={s1, s2,.., sq,..}と表すことにする。このような関数Gの例としては、メッセージm1のメタ情報を出力する関数、メッセージm1内に含まれる文字列を出力する関数、Nグラム・インデキシングを活用したメッセージm1内の連続するN文字からなる文字列すべてを出力する関数などがある。Nグラム・インデキシングについては、参考文献１に詳しい。
（参考文献１：北研二，津田和彦，獅々堀正幹，“情報検索アルゴリズム”，共立出版，2002年）
ここでは、メッセージm1の文字列長をlengthm_1、P=min{L, lengthm_1}とし、i=1,..,Pに対して、次の処理を行い、文字列集合G(m1)を生成する。
インデックス生成部２４５は、メッセージm1内の連続するi個の文字からなる文字列（つまり、長さiの文字列）をすべて列挙する（Ｓ６−２０−１）。これを文字列集合{s1 (1), s2 (1),.., sj (i),..}(ただし、j=1, 2,.., lengthm_1-i+1)とする。文字列集合G(m1)={s1 (1), s2 (1),.., sj (i),..}は、メッセージm1に関係する情報である。
なお、メッセージ全体から当該文字列を列挙してもよいし、メッセージを文節ごとに区切り、各文節から当該文字列を列挙してもよい。また、列挙の方法については、例えば、メッセージや文節の左端からとってきた連続するi個の文字からなる文字列をs1 (i)、左端から右に１つシフトして得た連続するi個の文字からなる文字列をs2 (i)とするとよい。ただし、インデックスを用いたメッセージ検索に影響はないので、どのような列挙方法を用いてもよい。
次に、インデックス生成部２４５は、文字列集合G(m1)={s1 (1), s2 (1),.., sj (i),..}と記録部２１０から読み出した最新検索用秘密鍵SearchKeyを用いて、j=1, 2,.., lengthm_1-i+1に対し、インデックスを次式で計算する（Ｓ６−２０−２）。上述した通り、記録部２１０には一般に複数の検索用秘密鍵が記録されているが、ここで読み出す検索用秘密鍵SearchKeyは、最も新しい検索用秘密鍵、最新検索用秘密鍵であるとする。つまり、最新検索用秘密鍵SearchKeyを用いて各文字列sj (i)に対して、インデックスIndexj (i)を計算する。
Figure 0006770075
なお、インデックス集合の各要素は長さL以下の文字列であるとする。式(2)で得られるP/2(2lengthm_1-P+1)個のインデックスを要素とするインデックス集合Indは次式のようにとなる。
Figure 0006770075
例えば、検索可能な文字列長の上限Lを3以上の整数、メッセージm1を３文字からなるメッセージ“あいう”であるとすると、以下の6個のインデックスが計算される。
Figure 0006770075
なお、一般には、メッセージm1に関係する情報G(m1)={s1, s2,.., sq,..}から、インデックス集合Ind={Index1, Index2,.., Indexq,..}は、各要素を次式で計算して求めることができる。
Figure 0006770075
端末２００iは、暗号化メッセージEnc(m1)とともに、次式で表されるインデックス集合Indの各要素とメッセージ識別子の組をサーバ１００に送信する（Ｓ６−３０）。
Figure 0006770075
サーバ１００は、暗号化メッセージEnc(m1)、各インデックスとメッセージ識別子の組(Index1 (1),.., Indexj (i),.., Indexlengthm_1 (P), IDm_1)を記録部１１０に記録する。
なお、検索可能な文字列長の上限が定めない場合、L=+∞と表現することにすると、P=lengthm_1となり、メッセージm1に対し、上記と同様の方法でインデックス集合Ind
Figure 0006770075
を生成することができる。
［暗号化メッセージの検索］
ここでは、端末２００iがルーム識別子roomIDを有するルームで管理されるメッセージを検索する。検索キーワードとなる文字列（以下、メッセージ検索用文字列という）からクエリを生成し、暗号化したままメッセージの検索を行う。図８を参照して端末２００iによるメッセージ検索のフローについて説明する。
端末２００iがルームに蓄積された暗号化メッセージから、メッセージ検索用文字列m’に合致するメッセージの検索を行うとする。端末２００iのクエリ生成部２５０は、記録部２１０から一般に複数の検索用秘密鍵を読出し、各検索用秘密鍵SearchKeyに対してメッセージ検索に用いるクエリQueryを、Query=CRHF(F(m’, SearchKey))として計算し、これらのクエリを要素とするクエリ集合を生成する（Ｓ７−１０）。T1、T2を検索用秘密鍵の世代を示す１以上の整数とし、T1≦i≦T2なる整数iについて第i世代検索用秘密鍵SearchKey i についてクエリQueryi=CRHF(F(m’, SearchKeyi))を計算し、クエリ集合{QueryT_1,
QueryT_1+1,.., QueryT_2}を生成する。
例えば、現在からある過去の時点の間で送信されたメッセージに対して検索を行う場合、その間で更新された検索用秘密鍵に対してのみクエリを生成すればよい。つまり、必ずしも過去すべての検索用秘密鍵に対するクエリを生成する（T1=1である）必要はない。
なお、検索可能な文字列長の上限Lが定められている場合、最初にメッセージ検索用文字列m’の長さをLと比較し、Lよりも大きければエラーを返すようにしてもよい。このようにすることにより処理の効率化が図れる。
端末２００iのクエリ生成部２５０は、クエリ集合{QueryT_1, QueryT_1+1,.., QueryT_2}をサーバ１００に送信する（Ｓ７−２０）。
サーバ１００のインデックス検索部１４０は、記録部１１０に記録しているインデックス集合の各要素とメッセージ識別子の組(Index1 (1),.., Indexj (i),.., IDm_1)のうち、受信したクエリ集合{QueryT_1, QueryT_1+1,.., QueryT_2}の各要素QueryiとインデックスIndexj (i)が一致するインデックスとメッセージ識別子の組(Indexj (i), IDm_1)をすべて抽出する（Ｓ７−３０）。サーバ１００のインデックス検索部１４０は、端末２００iに抽出したメッセージ識別子IDm_1に対応する暗号化メッセージEnc(m1)を送信する（Ｓ７−４０）。
端末２００iの暗号化メッセージ復号部２５５は、Ｓ７−４０で受信した暗号化メッセージ暗号化メッセージEnc(m1)を復号して、メッセージm1を検索結果として画面に表示する（Ｓ７−５０）。
なお、Ｓ７−４０で抽出したメッセージ識別子IDm_1に対応する暗号化メッセージEnc(m1)を送信する代わりに、メッセージ識別子IDm_1を送信してもよい。この場合、端末２００iは、受信したメッセージ識別子IDm_1をサーバ１００に送信し、当該メッセージ識別子IDm_1に対応する暗号化メッセージEnc(m1)をサーバ１００から取得し、暗号化メッセージ復号部２５５を用いて暗号化メッセージEnc(m1)を復号して、メッセージm1を検索結果として画面に表示することになる。
［検索用秘密鍵の更新］
ここでは、端末２００i_0が検索用秘密鍵SearchKeyを更新する。検索用秘密鍵SearchKeyの更新間隔はサーバ１００の記録部１１０に記録されているインデックスとそれに紐づくメッセージ識別子の個数（分布）からインデックスやメッセージ識別子に対応するメッセージを推測されることを防げる程度の頻度で定期的に行うとよい。例えば、1ヵ月毎、半年毎など考えられるが、更新間隔が短い方がより推測されることを防ぐことができる。図９を参照して端末２００i_0による検索用秘密鍵の更新のフローについて説明する。
端末２００i_0の検索用秘密鍵生成部２３０は、事前に設定された更新間隔が経過したことを検知すると、ランダムに選択した平文空間Mpkの元r’を更新後の検索用秘密鍵として生成する（Ｓ８−１０）。つまり、SearchKey=r’とする。更新した検索用秘密鍵をグループ内の端末２００i_1と共有するため、端末２００i_0の検索用秘密鍵暗号化部２３３は、暗号化検索用秘密鍵CipherKey←REnc(pkroomID,f(SearchKey, R1))を計算し（Ｓ８−２０）、暗号化検索用秘密鍵CipherKeyをサーバ１００に送信する（Ｓ８−３０）。サーバ１００は、受信した暗号化検索用秘密鍵CipherKeyをルーム識別子roomIDと対応付けて記録部１１０に記録する。なお、サーバ１００は以前の暗号化検索用秘密鍵 CipherKeyも記録部１１０に記録しておく。端末２００i_1がサーバ１００から暗号化検索用秘密鍵CipherKeyを取得する場合（Ｓ８−４０）、過去の暗号化検索用秘密鍵{CipherKey1,.. ,CipherKeyi,..}も含め取得する（Ｓ８−５０）。ただし、暗号化検索用秘密鍵CipherKeyiは、第i世代検索用秘密鍵SearchKeyiから生成されたものを表す。
なお、過去の暗号化検索用秘密鍵すべてを取得する代わりに、最新検索用秘密鍵に対応する暗号化検索用秘密鍵のみを取得するようにしてもよい。このようにすることにより処理の効率化を図ることができる。
端末２００i_1が検索用秘密鍵の更新があったことを知るためには、端末２００i_0と更新間隔を共有しておいてもよいし、端末２００i_0が更新したことを端末２００i_1に通知してもよいし、端末２００i_1が自ら定期的に暗号化検索用秘密鍵を取得するようにしてもよい。
端末２００i_1の暗号化検索用秘密鍵復号部２３５は、取得した暗号化検索用秘密鍵Cip
herKey に対してTemp=Dec(skroomID, CipherKey)を計算、記録部２１０から読み出したセッション鍵R1を用いてSearchKey=g(Temp, R1)を生成する（Ｓ８−６０）。この処理は、取得した暗号化検索用秘密鍵の数だけ繰り返される。
本実施形態の説明では、代表端末２００1と一般端末２００jはその役割が異なる。つまりルーム生成要求をサーバ１００に送信する役割を負っているか否かだけであるが、これらの端末の構成については図３に示すように同質なものとして説明した。しかし、必ずしもこのように構成する必要はない。つまり、代表端末２００1は、記録部２１０と、ルーム生成要求送信部２２０と、検索用秘密鍵生成部２３０と、検索用秘密鍵暗号化部２３３と、暗号化検索用秘密鍵復号部２３５と、メッセージ暗号化部２４０と、メッセージID生成部２４３と、インデックス生成部２４５と、クエリ生成部２５０と、暗号化メッセージ復号部２５５を含むものとして構成する一方、一般端末２００jは、記録部２１０と、検索用秘密鍵生成部２３０と、検索用秘密鍵暗号化部２３３と、暗号化検索用秘密鍵復号部２３５と、メッセージ暗号化部２４０と、メッセージID生成部２４３と、インデックス生成部２４５と、クエリ生成部２５０と、暗号化メッセージ復号部２５５を含むものとして構成する。
本実施形態によると、端末２００iは検索キーワードと端末間で共有された検索用秘密鍵から秘匿化されたクエリを生成し、サーバ１００に送信、サーバ１００はメッセージに関係する情報と検索用秘密鍵から生成される、秘匿化されたインデックスと受信したクエリを用いてメッセージを検索する。これによりサーバ１００はメッセージを暗号化したまま検索することができる。また、検索用秘密鍵を定期的に更新することにより、同じ検索キーワードに対して異なるクエリが生成されることになり、検索内容や検索結果が推測されるのを防ぐことができる。
＜第二実施形態＞
第一実施形態のメッセージ送受信システムでは公開鍵暗号方式を用いたが、本実施形態のメッセージ送受信システムは、公開鍵暗号方式を用いない。ただし、ここでは、平文空間Mpkの代わりに鍵空間KEYを定義し、関数f:KEY×KEY1→KEYと関数g:KEY×KEY1→KEYは第一実施形態における関数(f,g)が満たす条件（式(1)）と同一の条件を満たすものとする。
このとき、例えば、KEY1=KEYであり、KEYに乗法群または加法群の構造が入っていれば、任意の(K, K1)∈KEY×KEYに対し、式(1)を満たす(f,g)の例として、以下の関数の組を挙げることができる。
Figure 0006770075
なお、演算/は、鍵空間KEYに乗法群としての構造が入っているときの乗法を・とし、この演算・におけるx2の逆元をx2 -1としたとき、x1/x2=x1・x2 -1と定義される演算である。また、演算-は、鍵空間KEYに加法群としての構造が入っているときの加法を+し、この演算+におけるx2の逆元を-x2としたとき、x1-x2=x1+(-x2)と定義される演算である。
［システム構成］
第二実施形態のメッセージ送受信システムは、第一実施形態のメッセージ送受信システムと同様、サーバ５００と、n（≧2）台の端末６００を含む。また、第一実施形態と同様、サーバ５００および端末６００1、…、端末６００nはそれぞれネットワーク３００へ接続される。
サーバ５００は、図１０に例示するように、記録部１１０と、ルーム生成部１２０と、インデックス検索部１４０を含む。つまり、サーバ５００は、鍵生成部１３０を有しない点でサーバ１００と異なる。端末６００i(1≦i≦n)は、図１１に例示するように、記録部２１０と、ルーム生成要求送信部２２０と、検索用秘密鍵生成部２３０と、検索用秘密鍵暗号化部６３３と、暗号化検索用秘密鍵復号部６３５と、メッセージ暗号化部２４０と、メッセージID生成部２４３と、インデックス生成部２４５と、クエリ生成部２５０と、暗号化メッセージ復号部２５５を含む。つまり、端末６００iは、検索用秘密鍵暗号化部２３３と、暗号化検索用秘密鍵復号部２３５の代わりに、検索用秘密鍵暗号化部６３３と、暗号化検索用秘密鍵復号部６３５を有する点で端末２００iと異なる。
第一実施形態と第二実施形態のメッセージ送受信システムは公開鍵暗号アルゴリズムを用いるか用いないかの点においてのみ異なる。その結果、システムセットアップと検索用秘密鍵の共有のフローに違いが出てくる。そこで、この２つのフローについて以下では説明する。
［システムセットアップ］
ここでは、ルーム識別子roomID、セッション鍵R1がグループに属する端末６００1、…、端末６００n間で共有される。図１２を参照してシステムセットアップのフローについて説明する。
代表端末６００1のルーム生成要求送信部２２０は、サーバ５００に対してルーム生成要求を送信する（Ｓ４−１０）。サーバ５００が当該要求を受信すると、サーバ５００のルーム生成部１２０は、ルーム識別子roomIDで識別されるルームを生成する（Ｓ４−２０）。サーバ５００は、ルーム識別子roomIDを記録部１１０に記録し、代表端末６００1にルーム識別子roomIDを送信する（Ｓ４−４２）。
一般端末６００jは、代表端末６００1からルームへの招待を示すルーム識別子roomIDを受信する（Ｓ４−５０）。
各端末６００iは、ルーム識別子roomIDを記録部２１０に記録する。
また、各端末６００iは、セッション鍵R1を共有し、記録部２１０に記録する（Ｓ４−７０）。なお、セッション鍵R1がサーバ５００に対して秘匿化されているのも、第一実施形態と同様である。
［検索用秘密鍵の共有］
ここでは、第一実施形態と同様、ある端末６００i_0(1≦i0≦n)が生成した検索用秘密鍵SearchKeyがサーバ５００を介してグループに属するすべての端末６００iの間で共有される。図５を参照して検索用秘密鍵SearchKeyの共有のフローについて説明する。
端末６００i_0の検索用秘密鍵生成部２３０は、ルーム識別子共有後、ランダムに選択した鍵空間KEYの元rを検索用秘密鍵SearchKeyとして生成する（Ｓ５−１０）。つまり、SearchKey=rとなる。なお、rのことを乱数という。この検索用秘密鍵SearchKeyは、第一実施形態同様、ルーム毎に生成されるものである。端末６００i_0は、検索用秘密鍵SearchKeyを記録部２１０に記録する。
端末６００i_0の検索用秘密鍵暗号化部６３３は、暗号化検索用秘密鍵CipherKey=f(SearchKey, R1)を生成し（Ｓ５−２０）、暗号化検索用秘密鍵CipherKeyをルーム識別子roomIDとともにサーバ５００に送信する（Ｓ５−３０）。つまり、暗号化検索用秘密鍵の生成に公開鍵を用いない点でのみ端末６００i_0は端末２００i_0と異なる。サーバ５００は、受信した暗号化検索用秘密鍵CipherKeyをルーム識別子roomIDと対応付けて記録部１１０に記録する。
端末６００i_1は、Ｓ４−５０で受信したルーム識別子roomIDをサーバ５００に送信し（Ｓ５−４０）、サーバ５００から暗号化検索用秘密鍵CipherKeyを受信する（Ｓ５−５０）。
端末６００i_1の暗号化検索用秘密鍵復号部６３５は、記録部２１０から読み出したセッション鍵R1を用いてSearchKey=g(CipherKey, R1)を計算、検索用秘密鍵SearchKeyを復号する（Ｓ５−６０）。関数(f,g)が先述の条件（式(1)）を満たすことより、検索用秘密鍵SearchKeyを得ることができる。端末６００i_1はＳ５−６０で得た検索用秘密鍵SearchKeyを記録部２１０に記録する。
なお、検索用秘密鍵の更新においても、検索用秘密鍵暗号化部６３３及び暗号化検索用秘密鍵復号部６３５が公開鍵・秘密鍵を用いないのは、検索用秘密鍵の共有と同じである。つまり、検索用秘密鍵暗号化部６３３は、暗号化検索用秘密鍵をCipherKey=f(SearchKey, R1)として生成し、暗号化検索用秘密鍵復号部６３５は、記録部２１０から読み出したセッション鍵R1を用いてSearchKey=g(CipherKey, R1)を計算、検索用秘密鍵SearchKeyを復号する。
本実施形態によると、第一実施形態と同様、サーバ５００はメッセージを暗号化したまま検索することができる。また、検索用秘密鍵を定期的に更新することにより、同じ検索キーワードに対して異なるクエリが生成されることになり、検索内容や検索結果が推測されることを防ぐことができる。
＜変形例＞
この発明は上述の実施形態に限定されるものではなく、この発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。上記実施形態において説明した各種の処理は、記載の順に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。
＜補記＞
上記実施形態で説明した各装置における各種の処理機能をコンピュータによって実現する場合、各装置が有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、上記各装置における各種の処理機能がコンピュータ上で実現される。
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。
また、このプログラムの流通は、例えば、そのプログラムを記録したDVD、CD-ROM等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。
このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。そして、処理の実行時、このコンピュータは、自己の記憶装置に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。また、このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、
このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。また、サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるASP（Application Service Provider）型のサービスによって、上述の処理を実行する構成としてもよい。なお、本形態におけるプログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるもの（コンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータ等）を含むものとする。
また、この形態では、コンピュータ上で所定のプログラムを実行させることにより、本装置を構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。
上述の本発明の実施形態の記載は、例証と記載の目的で提示されたものである。網羅的であるという意思はなく、開示された厳密な形式に発明を限定する意思もない。変形やバリエーションは上述の教示から可能である。実施形態は、本発明の原理の最も良い例証を提供するために、そして、この分野の当業者が、熟考された実際の使用に適するように本発明を色々な実施形態で、また、色々な変形を付加して利用できるようにするために、選ばれて表現されたものである。すべてのそのような変形やバリエーションは、公正に合法的に公平に与えられる幅にしたがって解釈された添付の請求項によって定められた本発明のスコープ内である。
１００ サーバ
１１０ 記録部
１２０ ルーム生成部
１３０ 鍵生成部
１４０ インデックス検索部
２００ 端末
２１０ 記録部
２２０ ルーム生成要求送信部
２３０ 検索用秘密鍵生成部
２３３ 検索用秘密鍵暗号化部
２３５ 暗号化検索用秘密鍵復号部
２４０ メッセージ暗号化部
２４３ メッセージID生成部
２４５ インデックス生成部
２５０ クエリ生成部
２５５ 暗号化メッセージ復号部
３００ ネットワーク
５００ サーバ
６００ 端末
６３３ 検索用秘密鍵暗号化部
６３５ 暗号化検索用秘密鍵復号部

Claims (7)

  1. nを2以上の整数とし、
    メッセージを共有するn台の端末と前記メッセージを暗号化した暗号化メッセージを記録するサーバとを含むメッセージ送受信システムにおいて、前記端末がメッセージ検索用文字列を用いて前記暗号化メッセージを検索する暗号化メッセージ検索方法であって、
    前記n台の端末で共有するメッセージを前記サーバが管理する単位をルーム、その識別子をルーム識別子とし、
    前記n台の端末の記録部には、前記ルーム識別子と、セッション鍵とが記録されており、
    前記端末が、ルーム識別子共有後または最初の検索用秘密鍵を共有した後は事前に設定された更新間隔が経過する度、検索用秘密鍵として乱数を生成し、前記セッション鍵を用いて前記検索用秘密鍵から暗号化検索用秘密鍵を生成し、前記暗号化検索用秘密鍵を前記サーバに送信する暗号化検索用秘密鍵送信ステップと、
    前記端末が、前記ルーム識別子を用いて前記サーバから前記暗号化検索用秘密鍵を取得し、前記セッション鍵を用いて前記暗号化検索用秘密鍵から前記検索用秘密鍵を復号する検索用秘密鍵復号ステップと、
    前記端末が、メッセージを暗号化した暗号化メッセージを生成し、前記メッセージに関係する情報と、前記検索用秘密鍵のうち最新検索用秘密鍵を用いて、メッセージ検索用のインデックス集合を生成し、前記インデックス集合と前記暗号化メッセージとを前記ルーム識別子とともに前記サーバに送信する暗号化メッセージ送信ステップと、
    前記端末が、前記メッセージ検索用文字列と、前記検索用秘密鍵のうち１つ以上の検索用秘密鍵を用いて、クエリ集合を生成し、前記クエリ集合を前記ルーム識別子とともに前記サーバに送信するクエリ送信ステップと、
    前記サーバが、前記ルーム識別子と対応付けて管理しているインデックス集合と暗号化メッセージの中から前記クエリ集合の要素と一致するインデックス集合の要素がある暗号化メッセージを検索し、前記暗号化メッセージを前記端末に送信する暗号化メッセージ返信ステップと、
    前記端末が、前記暗号化メッセージからメッセージを復号する暗号化メッセージ復号ステップと、
    を含む暗号化メッセージ検索方法。
  2. 請求項１に記載の暗号化メッセージ検索方法であって、
    関数f, gは任意の(K, K1)∈KEY×KEY1に対し次式を満たすものとし、
    Figure 0006770075
    CRHFを任意長の文字列を入力とし、固定長の文字列を出力する衝突困難ハッシュ関数、Fを２つの任意長の文字列を入力とし、文字列を出力する関数とし、
    前記暗号化検索用秘密鍵送信ステップでは、SearchKeyを検索用秘密鍵、R1をセッション鍵として、f(SearchKey, R1)を計算することにより、暗号化検索用秘密鍵CipherKeyを生成し、
    前記検索用秘密鍵復号ステップでは、Temp=f(SearchKey, R1)とし、g(Temp, R1)を計算することにより、前記検索用秘密鍵SearchKeyを復号し、
    前記暗号化メッセージ送信ステップでは、メッセージm1を暗号化するメッセージ、関数Gを任意長の文字列を入力として入力文字列に依存する濃度を有する文字列集合を出力する関数として、前記メッセージに関係する情報をG(m1)={s1, s2,.., sq,..}とし、前記インデックス集合{Index1, Index 2,.., Index q,..}の各要素を次式により計算し、
    Figure 0006770075
    前記クエリ送信ステップでは、前記メッセージ検索用文字列をm’とし、前記クエリ集合{QueryT_1, QueryT_1+1,.., QueryT_2}の各要素をQueryi=CRHF(F(m’, SearchKeyi)) (T1≦i≦T2、ただし、T1、T2は検索用秘密鍵の世代を示す１以上の整数)として計算する暗号化メッセージ検索方法。
  3. 請求項１に記載の暗号化メッセージ検索方法であって、
    前記n台の端末の記録部には、さらに前記サーバが前記ルームごとに生成した公開鍵pkroomIDと秘密鍵skroomIDとが記録されており、
    関数f, gは任意の(K, K1)∈Mpk×KEY1に対し次式を満たすものとし、
    Figure 0006770075
    CRHFを任意長の文字列を入力とし、固定長の文字列を出力する衝突困難ハッシュ関数、Fを２つの任意長の文字列を入力とし、文字列を出力する関数とし、
    前記暗号化検索用秘密鍵送信ステップでは、SearchKeyを検索用秘密鍵、R1をセッション鍵として、暗号化検索用秘密鍵CipherKey=Enc(pkroomID, f(SearchKey, R1))を生成し、
    前記検索用秘密鍵復号ステップでは、g(Dec(skroomID, CipherKey), R1)を計算することにより、前記検索用秘密鍵SearchKeyを復号し、
    前記暗号化メッセージ送信ステップでは、メッセージm1を暗号化するメッセージ、関数Gを任意長の文字列を入力として入力文字列に依存する濃度を有する文字列集合を出力する関数として、前記メッセージに関係する情報をG(m1)={s1, s2,.., sq,..}とし、前記インデックス集合{Index1, Index 2,.., Index q,..}の各要素を次式により計算し、
    Figure 0006770075
    前記クエリ送信ステップでは、前記メッセージ検索用文字列をm’とし、前記クエリ集合{QueryT_1, QueryT_1+1,.., QueryT_2}の各要素をQueryi=CRHF(F(m’, SearchKeyi)) (T1≦i≦T2、ただし、T1、T2は検索用秘密鍵の世代を示す１以上の整数)として計算する暗号化メッセージ検索方法。
  4. 請求項２または３に記載の暗号化メッセージ検索方法であって、
    前記関数Gは、メッセージm1を入力とし、メッセージm1内の連続するi個(i=1,..,P、ただし、P=min{L, lengthm_1}、Lは検索可能な文字列長の上限値、lengthm_1はメッセージm1の文字列長)の文字からなる文字列を列挙することにより生成される集合{s1 (1), s2 (1),.., sj (i),..}(ただし、j=1, 2,.., lengthm_1-i+1)を出力する関数である暗号化メッセージ検索方法。
  5. nを2以上の整数とし、
    メッセージを共有するn台の端末と前記メッセージを暗号化した暗号化メッセージを記録するサーバとを含むメッセージ送受信システムであって、
    前記n台の端末で共有するメッセージを前記サーバが管理する単位をルーム、その識別子をルーム識別子とし、
    前記サーバは、
    前記ルーム識別子と、前記n台の端末が共有する検索用秘密鍵を暗号化した暗号化検索用秘密鍵と、暗号化メッセージと、メッセージ検索用のインデックス集合とを記録する記録部と、
    前記ルーム識別子と対応付けて管理しているインデックス集合と暗号化メッセージの中から前記端末からのクエリ集合の要素と一致するインデックス集合の要素がある暗号化メッセージを検索するインデックス検索部と、
    を含み、
    前記端末は、
    前記ルーム識別子と、前記n台の端末で共有するセッション鍵とを記録する記録部と、
    ルーム識別子共有後または最初の検索用秘密鍵を共有した後は事前に設定された更新間隔が経過する度、乱数を前記検索用秘密鍵として生成する検索用秘密鍵生成部と、
    前記セッション鍵を用いて前記検索用秘密鍵から暗号化検索用秘密鍵を生成する検索用秘密鍵暗号化部と、
    前記ルーム識別子を用いて前記サーバから前記暗号化検索用秘密鍵を取得し、前記セッション鍵を用いて前記暗号化検索用秘密鍵から前記検索用秘密鍵を復号する暗号化検索用秘密鍵復号部と、
    メッセージを暗号化した暗号化メッセージを生成するメッセージ暗号化部と、
    前記メッセージに関係する情報と、前記検索用秘密鍵のうち最新検索用秘密鍵を用いて、メッセージ検索用のインデックス集合を生成するインデックス生成部と、
    メッセージ検索用文字列と、前記検索用秘密鍵のうち１つ以上の検索用秘密鍵を用いて、クエリ集合を生成するクエリ生成部と、
    暗号化メッセージからメッセージを復号する暗号化メッセージ復号部と、
    を含むメッセージ送受信システム。
  6. メッセージを暗号化した暗号化メッセージを記録するサーバを介して他の端末と前記メッセージを共有する端末であって、
    前記n台の端末で共有するメッセージを前記サーバが管理する単位をルーム、その識別子をルーム識別子とし、
    前記ルーム識別子と、前記n台の端末で共有するセッション鍵とを記録する記録部と、
    ルーム識別子共有後または最初の検索用秘密鍵を共有した後は事前に設定された更新間隔が経過する度、乱数を検索用秘密鍵として生成する検索用秘密鍵生成部と、
    前記セッション鍵を用いて前記検索用秘密鍵から暗号化検索用秘密鍵を生成する検索用秘密鍵暗号化部と、
    前記ルーム識別子を用いて前記サーバから暗号化検索用秘密鍵を取得し、前記セッション鍵を用いて前記暗号化検索用秘密鍵から検索用秘密鍵を復号する暗号化検索用秘密鍵復号部と、
    メッセージを暗号化した暗号化メッセージを生成するメッセージ暗号化部と、
    前記メッセージに関係する情報と、前記検索用秘密鍵のうち最新検索用秘密鍵を用いて、メッセージ検索用のインデックス集合を生成するインデックス生成部と、
    メッセージ検索用文字列と、前記検索用秘密鍵のうち１つ以上の検索用秘密鍵を用いて、クエリ集合を生成するクエリ生成部と、
    暗号化メッセージからメッセージを復号する暗号化メッセージ復号部と、
    を含む端末。
  7. 請求項６に記載の端末としてコンピュータを機能させるためのプログラム。
JP2018538376A 2016-09-12 2017-08-30 暗号化メッセージ検索方法、メッセージ送受信システム、端末、プログラム Active JP6770075B2 (ja)

Applications Claiming Priority (3)

Application Number Priority Date Filing Date Title
JP2016177680 2016-09-12
JP2016177680 2016-09-12
PCT/JP2017/031195 WO2018047698A1 (ja) 2016-09-12 2017-08-30 暗号化メッセージ検索方法、メッセージ送受信システム、サーバ、端末、プログラム

Publications (2)

Publication Number Publication Date
JPWO2018047698A1 JPWO2018047698A1 (ja) 2019-06-24
JP6770075B2 true JP6770075B2 (ja) 2020-10-14

Family

ID=61561555

Family Applications (1)

Application Number Title Priority Date Filing Date
JP2018538376A Active JP6770075B2 (ja) 2016-09-12 2017-08-30 暗号化メッセージ検索方法、メッセージ送受信システム、端末、プログラム

Country Status (5)

Country Link
US (1) US11223472B2 (ja)
EP (1) EP3511845B1 (ja)
JP (1) JP6770075B2 (ja)
CN (1) CN109643324B (ja)
WO (1) WO2018047698A1 (ja)

Families Citing this family (6)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US10735384B2 (en) * 2017-02-17 2020-08-04 Whatsapp Inc. Techniques for key ratcheting with multiple step sizes
US11177949B2 (en) * 2017-11-06 2021-11-16 Nippon Telegraph And Telephone Corporation Data sharing method, data sharing system, data sharing server, communication terminal and program
US11212720B2 (en) 2018-10-16 2021-12-28 Mediatek Inc. 5GSM handling on invalid PDU session
CN112632598B (zh) * 2020-12-09 2022-10-18 西安电子科技大学 一种加密数据检索与共享方法、系统、介质、设备及应用
CN113127536B (zh) * 2021-04-14 2023-07-28 上海同态信息科技有限责任公司 一种基于同态构型加密的离线模糊匹配系统
CN117194756A (zh) * 2023-11-02 2023-12-08 北京信安世纪科技股份有限公司 数据处理方法、装置及存储介质

Family Cites Families (16)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JPH07200617A (ja) * 1994-01-10 1995-08-04 Nippon Telegr & Teleph Corp <Ntt> 共有情報参照権限制御方法
JP2003101570A (ja) * 2001-09-21 2003-04-04 Sony Corp 通信処理システム、通信処理方法、およびサーバー装置、並びにコンピュータ・プログラム
US20070269041A1 (en) * 2005-12-22 2007-11-22 Rajat Bhatnagar Method and apparatus for secure messaging
JPWO2009011120A1 (ja) * 2007-07-18 2010-09-16 パナソニック株式会社 アドレス生成方法、アドレス生成システム、通信装置、通信方法、通信システム及び相手先通信装置
JP5441726B2 (ja) * 2010-01-14 2014-03-12 三菱電機株式会社 情報処理システム及び管理装置及びサーバ装置及び情報処理装置
WO2013111284A1 (ja) 2012-01-25 2013-08-01 三菱電機株式会社 データ検索装置、データ検索方法、データ検索プログラム、データ登録装置、データ登録方法、データ登録プログラムおよび情報処理装置
JP5814880B2 (ja) * 2012-07-31 2015-11-17 三菱電機株式会社 暗号システム、暗号方法、暗号プログラム及び復号装置
CN103023637B (zh) * 2012-12-25 2015-07-15 电子科技大学 一种云存储中可撤销的关键字搜索公钥加密及搜索方法
US9047480B2 (en) 2013-08-01 2015-06-02 Bitglass, Inc. Secure application access system
JP2015118603A (ja) 2013-12-19 2015-06-25 日本電信電話株式会社 データベース検索システム及び検索方法
JP6208586B2 (ja) * 2014-01-16 2017-10-04 株式会社日立製作所 検索可能暗号処理システムおよび検索可能暗号処理方法
US10318754B2 (en) * 2014-06-02 2019-06-11 Robert Bosch Gmbh System and method for secure review of audit logs
CN104219051B (zh) * 2014-08-20 2018-04-13 北京奇艺世纪科技有限公司 一种群组内消息的通信方法和系统
DE112014007083T5 (de) * 2014-10-21 2017-07-13 Mitsubishi Electric Corporation Servervorrichtung, Suchsystem, Endgerätevorrichtung, Suchverfahren, Serverprogramm und Endgeräteprogramm
CN105468986B (zh) * 2015-12-02 2018-11-13 深圳大学 一种保密信息检索方法及系统
CN105743888A (zh) * 2016-01-22 2016-07-06 河南理工大学 一种基于关键字搜索的代理重加密方案

Also Published As

Publication number Publication date
CN109643324A (zh) 2019-04-16
CN109643324B (zh) 2023-08-29
EP3511845A1 (en) 2019-07-17
EP3511845A4 (en) 2020-04-15
US11223472B2 (en) 2022-01-11
EP3511845B1 (en) 2021-05-26
WO2018047698A1 (ja) 2018-03-15
JPWO2018047698A1 (ja) 2019-06-24
US20190215158A1 (en) 2019-07-11

Similar Documents

Publication Publication Date Title
CN109981641B (zh) 一种基于区块链技术的安全发布订阅系统及发布订阅方法
JP6770075B2 (ja) 暗号化メッセージ検索方法、メッセージ送受信システム、端末、プログラム
Pasupuleti et al. An efficient and secure privacy-preserving approach for outsourced data of resource constrained mobile devices in cloud computing
JP5562687B2 (ja) 第１のユーザによって第２のユーザに送信される通信の安全化
US20210194670A1 (en) Client-server computer system
WO2016063344A1 (ja) サーバ装置及び検索システム及び端末装置及び検索方法及びサーバプログラム及び端末プログラム
JP2014002365A (ja) プライバシーを保護することができる暗号化データの問い合わせ方法及びシステム
Lu et al. Efficient searchable public key encryption against keyword guessing attacks for cloud-based EMR systems
JP5670365B2 (ja) 暗号文検索システム、検索情報生成装置、検索実行装置、検索要求装置、暗号文検索方法、検索情報生成方法、検索実行方法、検索要求方法、およびプログラム
JP6556955B2 (ja) 通信端末、サーバ装置、プログラム
He et al. Secure encrypted data deduplication based on data popularity
Huang et al. A more efficient public-key authenticated encryption scheme with keyword search
JP6879311B2 (ja) メッセージ送信システム、通信端末、サーバ装置、メッセージ送信方法、およびプログラム
KR101140576B1 (ko) 암호화 문서에 대한 다자간 검색 시스템 및 그 방법
JP2019125956A (ja) 鍵交換方法、鍵交換システム、鍵交換サーバ装置、通信装置、プログラム
Sharma et al. Multiuser searchable encryption with token freshness verification
Yan et al. Secure and efficient big data deduplication in fog computing
JP6840685B2 (ja) データ共有方法、データ共有システム、通信端末、データ共有サーバ、プログラム
CN112637233B (zh) 一种基于多用户数据的安全求均值方法
Hinojosa-Cabello et al. Novel constructions for ciphertext-policy attribute-based searchable encryption
CN111480313A (zh) 通信终端、服务器装置、程序
Shan et al. Fuzzy keyword search over encrypted cloud data with dynamic fine-grained access control
Prakash et al. Secure access of multiple keywords over encrypted data in cloud environment using ECC-PKI and ECC ElGamal
Wang et al. Privacy preserving protocol for service aggregation in cloud computing
Lee et al. A study of practical proxy reencryption with a keyword search scheme considering cloud storage structure

Legal Events

Date Code Title Description
A521 Request for written amendment filed

Free format text: JAPANESE INTERMEDIATE CODE: A523

Effective date: 20190215

A621 Written request for application examination

Free format text: JAPANESE INTERMEDIATE CODE: A621

Effective date: 20190215

A131 Notification of reasons for refusal

Free format text: JAPANESE INTERMEDIATE CODE: A131

Effective date: 20200407

A521 Request for written amendment filed

Free format text: JAPANESE INTERMEDIATE CODE: A523

Effective date: 20200501

TRDD Decision of grant or rejection written
A01 Written decision to grant a patent or to grant a registration (utility model)

Free format text: JAPANESE INTERMEDIATE CODE: A01

Effective date: 20200923

A61 First payment of annual fees (during grant procedure)

Free format text: JAPANESE INTERMEDIATE CODE: A61

Effective date: 20200924

R150 Certificate of patent or registration of utility model

Ref document number: 6770075

Country of ref document: JP

Free format text: JAPANESE INTERMEDIATE CODE: R150