(57)【要約】【課題】いかなる性能のコンピュータを用いても悪意の第三者が平文に対し意図したような操作が加わるように暗号文を改ざんすることができない、所謂、情報量的安全性を保障し得る暗号の構造を提供する。【解決手段】上記課題は、各ユーザＵｉに対応させてそれぞれ異なるように生成された有限体Ｆｑの元となる乱数ｒｉと、ランダムに生成された上記有限体Ｆｑ上の多項式ｆｉ（ｘ）に上記乱数ｒｉを代入して得られる値ｆ１（ｒｉ）及びｆ２（ｒｉ）を用いて演算された値｛ｆ１（ｒｉ）＋ｍｆ２（ｒｉ）｝との組を有する暗号の構造にて達成される。【選択図】　　　　図２
2004101568.tif 000002
【特許請求の範囲】
【請求項１】
所定のグループに属する複数のユーザのそれぞれＵｉ（ｉ＝１，・・・，ｎ）の端末において生成された有限体Ｆｑの元となる平文ｍに対して付加されるべき暗号の構造において、
上記各ユーザＵｉに対応させてそれぞれ異なるように生成された上記有限体Ｆｑの元となる乱数ｒｉと、
ランダムに生成された上記有限体Ｆｑ上の多項式ｆｉ（ｘ）に上記乱数ｒｉを代入して得られる値ｆ１（ｒｉ）及びｆ２（ｒｉ）を用いて演算された値｛ｆ１（ｒｉ）＋ｍｆ２（ｒｉ）｝との組を有する暗号の構造。
【請求項２】
請求項１記載の暗号の構造において、
上記多項式は、
【数１】
2004101568.tif 000011
（ｉ＝１，２）である暗号の構造。
【請求項３】
所定のグループに属する複数のユーザのそれぞれＵｉ（ｉ＝１，・・・，ｎ）の端末において生成された暗号文が当該所定のグループに所属する何れかのユーザにて生成されたものであることの検証を行う暗号文復号方法において、
所定のセンタにおいて実行される、
上記各ユーザＵｉに対応させてそれぞれ異なる上記有限体Ｆｑの元となる乱数ｒｉを生成するステップと、
上記全ての乱数ｒｉに関し、ｆ２（ｒｉ）≠０となる上記有限体Ｆｑ上の多項式ｆ１（ｘ）及びｆ２（ｘ）をランダムに生成するステップと、
上記乱数ｒｉと、多項式ｆ１（ｘ）及びｆ２（ｘ）とを用いて、第１の値ｆ１（ｒｉ）及び第２の値ｆ２（ｒｉ）を演算するステップと、
上記多項式ｆ１（ｘ）及びｆ２（ｘ）を復号者に発行するステップと、
上記第１の値ｆ１（ｒｉ）及び第２の値ｆ２（ｒｉ）をユーザＵｉに発行するステップと、
を有し、
上記復号者の端末において実行される、
上記ユーザＵｉにおいて生成された、上記有限体Ｆｑの元となる平文ｍに、上記乱数ｒｉと、上記第１の値ｆ１（ｒｉ）及び第２の値ｆ２（ｒｉ）から演算される値ｆ１（ｒｉ）＋ｍｆ２（ｒｉ）との組が付加された暗号文｛ｒｉ，ｆ１（ｒｉ）＋ｍｆ２（ｒｉ）｝を取得するステップと、
上記暗号文｛ｒｉ，ｆ１（ｒｉ）＋ｍｆ２（ｒｉ）｝に含まれる乱数ｒｉと、上記所定のセンタによって発行された多項式ｆ１（ｘ）及びｆ２（ｘ）とを用いて
【数２】
2004101568.tif 000012
の値を演算するステップと、
を有する暗号文復号方法。
【請求項４】
請求項３記載の暗号文復号方法において、
上記多項式ｆ１（ｘ）及びｆ２（ｘ）は、
【数３】
2004101568.tif 000013
（ｉ＝１，２）である暗号文復号方法。
【請求項５】
所定のグループに属する複数のユーザのそれぞれＵｉ（ｉ＝１，・・・，ｎ）の端末において生成された暗号文が当該所定のグループに所属する何れかのユーザにて生成されたものであることの検証を行う暗号文復号システムにおいて、
所定のセンタは、
上記各ユーザＵｉに対応させてそれぞれ異なる上記有限体Ｆｑの元となる乱数ｒｉを生成する手段と、
上記全ての乱数ｒｉに関し、ｆ２（ｒｉ）≠０となる上記有限体Ｆｑ上の多項式ｆ１（ｘ）及びｆ２（ｘ）をランダムに生成する手段と、
上記乱数ｒｉと、多項式ｆ１（ｘ）及びｆ２（ｘ）とを用いて、第１の値ｆ１（ｒｉ）及び第２の値ｆ２（ｒｉ）を演算する手段と、
上記多項式ｆ１（ｘ）及びｆ２（ｘ）を復号者に発行する手段と、
上記第１の値ｆ１（ｒｉ）及び第２の値ｆ２（ｒｉ）をユーザＵｉに発行する手段と、
を有し、
上記復号者の端末は、
上記ユーザＵｉにおいて生成された、上記有限体Ｆｑの元となる平文ｍに、上記乱数ｒｉと、上記第１の値ｆ１（ｒｉ）及び第２の値ｆ２（ｒｉ）から演算される値ｆ１（ｒｉ）＋ｍｆ２（ｒｉ）との組が付加された暗号文｛ｒｉ，ｆ１（ｒｉ）＋ｍｆ２（ｒｉ）｝を取得する手段と、
上記暗号文｛ｒｉ，ｆ１（ｒｉ）＋ｍｆ２（ｒｉ）｝に含まれる乱数ｒｉと、上記所定のセンタによって発行された多項式ｆ１（ｘ）及びｆ２（ｘ）とを用いて
【数４】
2004101568.tif 000014
の値を演算する手段と、
を有する暗号文復号システム。
【請求項６】
請求項５記載の暗号文復号システムにおいて、
上記多項式ｆ１（ｘ）及びｆ２（ｘ）は、
【数５】
2004101568.tif 000015
（ｉ＝１，２）である暗号文復号システム。
【発明の詳細な説明】
【発明の属する技術分野】
本発明は、電子投票や電子アンケート等の情報発信者のプライバシーの確保と長期的な信頼性が要求されるアプリケーション全般に用いることのできる暗号の構造に係り、詳しくは、所定のグループに所属する複数のユーザのそれぞれの端末において生成された暗号の構造に関する。
また、本発明は、所定のグループに属する複数のユーザのそれぞれの端末において生成された暗号文が当該所定のグループに所属する何れかのユーザにて生成されたものであることの検証を行う暗号文検証方法及びシステムに関する。
【従来の技術】
例えば、あるグループに所属するユーザを対象とした電子投票や電子アンケートなどを行うシステムでは、確実にそのグループに所属するユーザの投票や回答であることが保障されることや、投票や回答したユーザが特定できないこと、いわゆる、匿名性が確保されることが要求される場合がある。
このような要求に応える技術として、近年、公開鍵暗号を用いた暗号化方式が提案されている。この技術では、例えば、素因数分解や離散対数問題の計算が計算量的に不可能であるということを前提とした安全性確保（計算量的に安全）の手法がとられている。即ち、現在考えられるどのような高性能のコンピュータでも、現実的な時間内で秘密情報等の解読ができないことを保障している。
しかし、現在、計算量的に安全であることが保障し得ていても、今後、コンピュータの性能向上などにより、その安全性を十分保障し得るものとはならない。
【発明が解決しようとする課題】
そこで、本発明の第１の課題は、いかなる性能のコンピュータを用いても悪意の第三者が平文に対し意図したような操作が加わるように暗号文を改ざんすることができない、所謂、情報量的安全性を保障し得る暗号の構造を提供することである。
また、本発明の第２の課題は、平文の情報に対しそのような暗号を用いた暗号化によって生成される暗号文が所定のグループに所属する正規のユーザから送られる場合に、ユーザを特定することなく、当該暗号文を復号することができる暗号文の復号方法及びシステムを提供することである。
【課題を解決するための手段】
上記第１の課題を解決するため、本発明は請求項１に記載されるように、所定のグループに属する複数のユーザのそれぞれＵｉ（ｉ＝１，・・・，ｎ）の端末において生成された有限体Ｆｑの元となる平文ｍに対して付加されるべき暗号の構造において、上記各ユーザＵｉに対応させてそれぞれ異なるように生成された上記有限体Ｆｑの元となる乱数ｒｉと、ランダムに生成された上記有限体Ｆｑ上の多項式ｆｉ（ｘ）に上記乱数ｒｉを代入して得られる値ｆ１（ｒｉ）及びｆ２（ｒｉ）を用いて演算された値｛ｆ１（ｒｉ）＋ｍｆ２（ｒｉ）｝との組を有する。
このような暗号の構造では、悪意の第三者が平文ｍに対し意図したような操作が加わるように暗号文内の値｛ｆ１（ｒｉ）＋ｍｆ２（ｒｉ）｝を改ざんすることができない。また、上記暗号文には、ユーザに関する情報が含まれていないため、復号者であっても、暗号文を生成したユーザを特定することができない。
また、本発明は請求項２に記載されるように、上記暗号の構造において、上記多項式は、
【数６】
2004101568.tif 000003
（ｉ＝１，２）である。
上記第２の課題を解決するため、本発明は請求項３に記載されるように、所定のグループに属する複数のユーザのそれぞれＵｉ（ｉ＝１，・・・，ｎ）の端末において生成された暗号文が当該所定のグループに所属する何れかのユーザにて生成されたものであることの検証を行う暗号文復号方法において、所定のセンタにおいて実行される、上記各ユーザＵｉに対応させてそれぞれ異なる上記有限体Ｆｑの元となる乱数ｒｉを生成するステップと、上記全ての乱数ｒｉに関し、ｆ２（ｒｉ）≠０となる上記有限体Ｆｑ上の多項式ｆ１（ｘ）及びｆ２（ｘ）をランダムに生成するステップと、上記乱数ｒｉと、多項式ｆ１（ｘ）及びｆ２（ｘ）とを用いて、第１の値ｆ１（ｒｉ）及び第２の値ｆ２（ｒｉ）を演算するステップと、上記多項式ｆ１（ｘ）及びｆ２（ｘ）を復号者に発行するステップと、上記第１の値ｆ１（ｒｉ）及び第２の値ｆ２（ｒｉ）をユーザＵｉに発行するステップとを有し、上記復号者の端末において実行される、上記ユーザＵｉにおいて生成された、上記有限体Ｆｑの元となる平文ｍに、上記乱数ｒｉと、上記第１の値ｆ１（ｒｉ）及び第２の値ｆ２（ｒｉ）から演算される値ｆ１（ｒｉ）＋ｍｆ２（ｒｉ）との組が付加された暗号文｛ｒｉ，ｆ１（ｒｉ）＋ｍｆ２（ｒｉ）｝を取得するステップと、上記暗号文｛ｒｉ，ｆ１（ｒｉ）＋ｍｆ２（ｒｉ）｝に含まれる乱数ｒｉと、上記所定のセンタによって発行された多項式ｆ１（ｘ）及びｆ２（ｘ）とを用いて
【数７】
2004101568.tif 000004
の値を演算するステップとを有する。
このような暗号文復号方法では、復号者は、ユーザから発行された暗号文｛ｒｉ，ｆ１（ｒｉ）＋ｍｆ２（ｒｉ）｝に含まれる乱数ｒｉと、所定のセンタから発行された多項式ｆ１（ｘ）及びｆ２（ｘ）とを用いて、
【数８】
2004101568.tif 000005
により暗号文を復号して平文ｍを得る。この場合、復号者が有する情報のみでは、当該復号者は、暗号文を生成したものが所定のグループに属する何れかのユーザであることは検証できるものの、当該暗号文を生成したユーザを特定することができない。
また、本発明は請求項４に記載されるように、上記暗号文復号方法において、
上記多項式ｆ１（ｘ）及びｆ２（ｘ）は、
【数９】
2004101568.tif 000006
（ｉ＝１，２）である。
請求項３に記載された発明と同様の観点から、本発明は請求項５に記載されるように、所定のグループに属する複数のユーザのそれぞれＵｉ（ｉ＝１，・・・，ｎ）の端末において生成された暗号文が当該所定のグループに所属する何れかのユーザにて生成されたものであることの検証を行う暗号文復号システムにおいて、所定のセンタは、上記各ユーザＵｉに対応させてそれぞれ異なる上記有限体Ｆｑの元となる乱数ｒｉを生成する手段と、上記全ての乱数ｒｉに関し、ｆ２（ｒｉ）≠０となる上記有限体Ｆｑ上の多項式ｆ１（ｘ）及びｆ２（ｘ）をランダムに生成する手段と、上記乱数ｒｉと、多項式ｆ１（ｘ）及びｆ２（ｘ）とを用いて、第１の値ｆ１（ｒｉ）及び第２の値ｆ２（ｒｉ）を演算する手段と、上記多項式ｆ１（ｘ）及びｆ２（ｘ）を復号者に発行する手段と、上記第１の値ｆ１（ｒｉ）及び第２の値ｆ２（ｒｉ）をユーザＵｉに発行する手段とを有し、上記復号者の端末は、上記ユーザＵｉにおいて生成された、上記有限体Ｆｑの元となる平文ｍに、上記乱数ｒｉと、上記第１の値ｆ１（ｒｉ）及び第２の値ｆ２（ｒｉ）から演算される値ｆ１（ｒｉ）＋ｍｆ２（ｒｉ）との組が付加された暗号文｛ｒｉ，ｆ１（ｒｉ）＋ｍｆ２（ｒｉ）｝を取得する手段と、上記暗号文｛ｒｉ，ｆ１（ｒｉ）＋ｍｆ２（ｒｉ）｝に含まれる乱数ｒｉと、上記所定のセンタによって発行された多項式ｆ１（ｘ）及びｆ２（ｘ）とを用いて
【数１０】
2004101568.tif 000007
の値を演算する手段とを有する。
また、本発明は請求項６に記載されるように、上記暗号文復号システムにおいて、上記多項式ｆ１（ｘ）及びｆ２（ｘ）は、
【数１１】
2004101568.tif 000008
（ｉ＝１，２）である。
【発明の実施の形態】
以下、本発明の実施の形態を図面に基づいて説明する。
本発明の実施の一形態に係る暗号文復号方法が適用されるシステムは、例えば、図１に示すように構成される。
図１において、所定のグループに所属するユーザＵｉ（ｉ＝１，・・・，ｎ）が使用すべきユーザ端末１０１〜１０ｎ、検証者Ｖ（Ｖｅｒｉｆｉｅｒ）にて管理される検証者端末２０及び信頼できる第三者（Ｔｒｕｓｔｅｄ　Ａｕｔｈｏｒｉｔｙ）が管理するセンタ１００（コンピュータ）が所定のネットワークＮＷに接続されている。また、上記所定のグループ内またはそのグループ以外のユーザで、例えば、暗号文の復号を依頼する者にて管理されるユーザ端末１０ｊがネットワークＮＷに接続されている。
上記のようなシステムにおいて、例えば、上記所定のグループに所属する複数のユーザＵｉが暗号文の復号を行う場合、図２に示す手順に従って処理が行われる。
図２においてセンタ１００は、所定のグループに属する各ユーザＵｉに対応させて、それぞれ異なる有限体Ｆｑの元となる乱数乱数ｒｉ（ｉ＝１，・・・，ｎ）を生成する（Ｓ１）。
次に、センタ１００は、全ての上記乱数ｒｉに関し、ｆ２（ｒｉ）≠０となる上記有限体Ｆｑ上の多項式ｆ１（ｘ）及びｆ２（ｘ）をランダムに生成する（Ｓ２）。ここで、多項式ｆ１（ｘ）及びｆ２（ｘ）は、具体的には、
【数１２】
2004101568.tif 000009
（ｉ＝１，２）により生成される。更に、センタ１００は、生成した多項式ｆ１（ｘ）及びｆ２（ｘ）を復号者端末２０にネットワークＮＷを介して送付する（Ｓ４）。
次に、センタ１００は、生成した多項式ｆ１（ｘ）に、同じく生成した乱数ｒｉを代入して第１の値ｆ１（ｒｉ）を生成するとともに、生成した多項式ｆ２（ｘ）に、同じく生成した乱数ｒｉを代入して第２の値ｆ２（ｒｉ）を生成する。更に、センタ１００は、これら第１の値ｆ１（ｒｉ）及び第２の値ｆ２（ｒｉ）を上記乱数ｒｉとともに、その乱数ｒｉに対応するユーザＵｉのユーザ端末１０ｉに送付する（Ｓ３）。
ユーザ端末１０ｉは、上記のようにセンタ１００から送付される乱数ｒｉと、第１の値ｆ１（ｒｉ）及び第２の値ｆ２（ｒｉ）とを受領する（Ｓ５）。ユーザＵｉが平文をユーザ端末１０ｉに入力すると、当該ユーザ端末１０ｉは、その平文を有限体Ｆｑの元となる平文ｍに変換する。次に、ユーザ端末１０ｉは、その平文ｍと、上記受領した第１の値ｆ１（ｒｉ）及び第２の値ｆ２（ｒｉ）とを用いて、｛ｆ１（ｒｉ）＋ｍｆ２（ｒｉ）｝を演算する。更に、ユーザ端末１０ｉは、上記受領した乱数ｒｉと、上記演算により得られた値｛ｆ１（ｒｉ）＋ｍｆ２（ｒｉ）｝との組となる暗号文｛ｒｉ，ｆ１（ｒｉ）＋ｍｆ２（ｒｉ）｝を生成する（Ｓ６）。
ユーザ端末１０ｉは、上記のようにして生成した暗号文｛ｒｉ，ｆ１（ｒｉ）＋ｍｆ２（ｒｉ）｝を、暗号文の復号を依頼するユーザが管理するユーザ端末１０ｊに、ネットワークＮＷを介して送付する（Ｓ７）。このように暗号文が送付されると、ユーザ端末１０ｉでの暗号化に関する処理が終了する。
ユーザ端末１０ｊは、ユーザＵｉのユーザ端末１０ｉから上記暗号文｛ｒｉ，ｆ１（ｒｉ）＋ｍｆ２（ｒｉ）｝を受領すると（Ｓ８）、その暗号文｛ｒｉ，ｆ１（ｒｉ）＋ｍｆ２（ｒｉ）｝の復号を行う必要があるか否かを判定する（Ｓ９）。この判定基準は、ユーザ端末１０ｊが任意に定めることができる。例えば、ユーザ端末１０ｊは、復号を行うべき暗号文をランダムに決めることができる。また、ユーザ端末１０ｊは、全ての暗号文を復号するように決めることもできる。
上記受領した暗号文｛ｒｉ，ｆ１（ｒｉ）＋ｍｆ２（ｒｉ）｝の復号を行う必要がないと判定された場合（Ｓ９でＮＯ）、その暗号文｛ｒｉ，ｆ１（ｒｉ）＋ｍｆ２（ｒｉ）｝は、ユーザ端末１０ｊに蓄積される。一方、上記受領した暗号文｛ｒｉ，ｆ１（ｒｉ）＋ｍｆ２（ｒｉ）｝の復号を行う必要があると判定された場合（Ｓ９でＹＥＳ）、ユーザ端末１０ｊは、復号者端末２０に対し、復号の依頼とともに、ユーザ端末１０ｉから受領した暗号文｛ｒｉ，ｆ１（ｒｉ）＋ｍｆ２（ｒｉ）｝を、ネットワークＮＷを介して送付する（Ｓ１０）。
復号者端末２０は、センタ１００から上記多項式ｆ１（ｘ）及びｆ２（ｘ）を受領すると（Ｓ１２）、それらの多項式の組ｆ１（ｘ）及びｆ２（ｘ）を記憶装置に格納する（Ｓ１３）。
また、復号者端末２０は、ユーザ端末１０ｊから復号の依頼と、暗号文｛ｒｉ，ｆ１（ｒｉ）＋ｍｆ２（ｒｉ）｝とを受領する（Ｓ１４）。次に、復号者端末２０は、上記受領した暗号文｛ｒｉ，ｆ１（ｒｉ）＋ｍｆ２（ｒｉ）｝に含まれる乱数ｒｉを抽出する。更に、復号者端末２０は、上記センタ１００から送付され、記憶装置に格納した多項式ｆ１（ｘ）及びｆ２（ｘ）に、上記暗号文｛ｒｉ，ｆ１（ｒｉ）＋ｍｆ２（ｒｉ）｝から抽出した乱数ｒｉを代入して、
【数１３】
2004101568.tif 000010
を演算することにより復号を行い、平文ｍを得る（Ｓ１５）。
更に、復号者端末２０は、上記暗号文｛ｒｉ，ｆ１（ｒｉ）＋ｍｆ２（ｒｉ）｝の復号結果である平文ｍを、復号の依頼元となるユーザ端末１０ｊに送付する（Ｓ１６）。Ｓ１０において、復号の依頼を行ったユーザ端末１０ｊは、ネットワークＮＷを介して、上記復号者端末２０から送付される平文ｍを受領する（Ｓ１１）。
このように、本実施形態の暗号文復号方法が適用されるシステムでは、暗号文｛ｒｉ，ｆ１（ｒｉ）＋ｍｆ２（ｒｉ）｝に含まれる情報のみでは、ユーザ端末１０ｊや復号者端末２０がどのような計算能力を有するコンピュータであっても、その暗号文を生成したユーザを特定することができない。従って、ユーザの匿名性を確保することができる。更に、暗号文｛ｒｉ，ｆ１（ｒｉ）＋ｍｆ２（ｒｉ）｝がグループに属する正規のユーザによって生成されたものであれば、復号者端末２０は、ユーザを特定しなくても、暗号文の復号が可能となる。
また、暗号文｛ｒｉ，ｆ１（ｒｉ）＋ｍｆ２（ｒｉ）｝がユーザ端末１０ｉからユーザ端末１０ｊに送付される際に、不正に悪意の第三者に取得されたとしても、平文ｍの内容を知ることができず、悪意の第三者が意図したような操作が平文ｍに加わるように、当該暗号文｛ｒｉ，ｆ１（ｒｉ）＋ｍｆ２（ｒｉ）｝内の乱数ｒｉ及び値｛ｆ１（ｒｉ）＋ｍｆ２（ｒｉ）｝を改ざんすることができない。
【発明の効果】
以上、説明したように、請求項１及び２記載の本願発明によれば、暗号文｛ｒｉ，ｆ１（ｒｉ）＋ｍｆ２（ｒｉ）｝のみから平文ｍの内容を知ることができない。また、悪意の第三者が平文ｍに意図的な操作が加わるように、暗号文｛ｒｉ，ｆ１（ｒｉ）＋ｍｆ２（ｒｉ）｝内の乱数ｒｉ及び値｛ｆ１（ｒｉ）＋ｍｆ２（ｒｉ）｝を改ざんすることができない。従って、いかなる性能のコンピュータを用いても不正を行うことができない、所謂、情報量的安全性を保障し得る暗号の構造を実現することができる。
また、請求項３乃至６記載の本願発明によれば、暗号文｛ｒｉ，ｆ１（ｒｉ）＋ｍｆ２（ｒｉ）｝には、ユーザに関する情報が含まれていないため、復号者であっても暗号文を生成したユーザを特定することができない。更に、暗号文｛ｒｉ，ｆ１（ｒｉ）＋ｍｆ２（ｒｉ）｝がグループに属する正規のユーザによって生成されたものであれば、ユーザを特定しなくても、暗号文の復号が可能となる復号方法及びシステムを提供することができる。
【図面の簡単な説明】
【図１】本発明の実施の一形態に係る暗号文復号方法が適用されるシステムの構成例を示す図である。
【図２】図１に示すシステムでの処理の流れの例を示すシーケンス図である。
【符号の説明】
１０ｉ、１０ｊ、１０１〜１０ｎ　ユーザ端末
２０　検証者端末
１００　センタ
【図１】
2004101568.tif 000016
【図２】
2004101568.tif 000017