(57)【特許請求の範囲】
【請求項１】
端末装置Ｕ１，…，Ｕｎと鍵配送管理装置とを有し、ｎが３以上の整数であり、ｉ＝１，…，ｎであり、ｖ＝２，…，ｎであり、正整数αに対して−１ ｍｏｄ α＝α−１であり、
端末装置Ｕｉは、
格子暗号またはコードベース暗号である公開鍵暗号方式の耐量子計算機暗号に則った鍵カプセル復号鍵ｓｋｉを格納する第ｉ記憶部と、
前記鍵カプセル復号鍵ｓｋｉに対応する鍵暗号化鍵ｐｋｉを出力する第ｉ出力部と、
前記耐量子計算機暗号に則った鍵暗号化鍵ｐｋ（ｉ ｍｏｄ ｎ）＋１を受け付ける第ｉ入力部と、
乱数ｋｉを設定する第ｉ乱数設定部と、
前記鍵暗号化鍵ｐｋ（ｉ ｍｏｄ ｎ）＋１を用い、二者間共有鍵Ｒｉ，（ｉ ｍｏｄ ｎ）＋１および前記二者間共有鍵Ｒｉ，（ｉ ｍｏｄ ｎ）＋１の暗号文である鍵カプセルＣｉ，（ｉ ｍｏｄ ｎ）＋１を得る第ｉ二者間共有鍵生成部と、
前記鍵カプセルＣｉ，（ｉ ｍｏｄ ｎ）＋１を出力する前記第ｉ出力部と、を含み、
前記第ｉ入力部は、鍵カプセルＣ（ｉ−２ ｍｏｄ ｎ）＋１，ｉを受け付け、
端末装置Ｕ１は、
鍵カプセル復号鍵ｓｋ１を用いて鍵カプセルＣｎ，１を復号して二者間共有鍵Ｒｎ，１を得る第１復号部と、
前記二者間共有鍵Ｒｎ，１の関数値Ｋ１（Ｌ）を得、二者間共有鍵Ｒ１，２の関数値Ｋ１（Ｒ）を得る第１関数演算部と、
前記関数値Ｋ１（Ｌ）と前記関数値Ｋ１（Ｒ）との排他的論理和Ｔ１を得、乱数ｋ１の関数値と前記関数値Ｋ１（Ｌ）との排他的論理和Ｔ’を得る第１排他的論理和部と、
前記排他的論理和Ｔ１およびＴ’を出力する第１出力部と、を含み、
端末装置Ｕｖは、
鍵カプセル復号鍵ｓｋｖを用いて鍵カプセルＣ（ｖ−２ ｍｏｄ ｎ）＋１，ｖを復号して二者間共有鍵Ｒ（ｖ−２ ｍｏｄ ｎ）＋１，ｖを得る第ｖ復号部と、
前記二者間共有鍵Ｒ（ｖ−２ ｍｏｄ ｎ）＋１，ｖの関数値Ｋｖ（Ｌ）を得、二者間共有鍵Ｒｖ，（ｖ ｍｏｄ ｎ）＋１の関数値Ｋｖ（Ｒ）を得る第ｖ関数演算部と、
前記関数値Ｋｖ（Ｌ）と前記関数値Ｋｖ（Ｒ）との排他的論理和Ｔｖを得る第ｖ排他的論理和部と、
乱数ｋｖおよび前記排他的論理和Ｔｖを出力する第ｖ出力部と、を含み、
前記鍵配送管理装置は、
前記乱数ｋ２，…，ｋｎを含む複数の値の排他的論理和ｋ’を得て出力し、排他的論理和Ｔ１，…，Ｔｖ‐１の排他的論理和Ｔｖ’を得て出力する排他的論理和部を含み、
前記端末装置Ｕ１は、
前記排他的論理和ｋ’と前記乱数ｋ１との排他的論理和の関数値を共有鍵ＳＫとして得る第１共有鍵生成部を含み、
前記端末装置Ｕｖは、
前記排他的論理和Ｔｖ’と前記関数値Ｋｖ（Ｌ）との排他的論理和によって前記関数値Ｋ１（Ｌ）を得る第ｖ関数値復元部と、
前記排他的論理和Ｔ’と前記関数値Ｋ１（Ｌ）との排他的論理和によって前記乱数ｋ１の関数値を得る第ｖ乱数復元部と、
前記排他的論理和ｋ’と前記乱数ｋ１の関数値から得られる前記乱数ｋ１との排他的論理和の関数値を前記共有鍵ＳＫとして得る第ｖ共有鍵生成部と、を含む鍵交換システム。
【請求項２】
端末装置Ｕ１，…，Ｕｎ＋１と鍵配送管理装置とを有し、ｎが３以上の整数であり、ｉ＝１，…，ｎであり、ｖ＝２，…，ｎであり、ｗ＝２，…，ｎ＋１であり、ｚ＝２，…，ｎ−１であり、ρ＝１，…，ｎ−１であり、正整数αに対して−１ ｍｏｄ α＝α−１であり、
端末装置Ｕｉは関数値ｒを格納する第ｉ記憶部を含み、
端末装置Ｕ１は、
格子暗号またはコードベース暗号である公開鍵暗号方式の耐量子計算機暗号に則った鍵カプセル復号鍵ｓｋ１を格納する第１記憶部と、
前記鍵カプセル復号鍵ｓｋ１に対応する鍵暗号化鍵ｐｋ１を出力する第１出力部と、を含み、
端末装置Ｕｎ＋１は、
前記耐量子計算機暗号に則った鍵カプセル復号鍵ｓｋｎ＋１を格納する第（ｎ＋１）記憶部と、
前記鍵カプセル復号鍵ｓｋｎ＋１に対応する鍵暗号化鍵ｐｋｎ＋１を出力する第（ｎ＋１）出力部と、を含み、
端末装置Ｕｎは、
前記鍵暗号化鍵ｐｋｎ＋１を受け付ける第ｎ入力部を含み、
乱数ｋｎを設定する第ｎ乱数設定部と、
前記鍵暗号化鍵ｐｋｎ＋１を用い、二者間共有鍵Ｒｎ，ｎ＋１および前記二者間共有鍵Ｒｎ，ｎ＋１の暗号文である鍵カプセルＣｎ，ｎ＋１を得る第ｎ二者間共有鍵生成部と、
前記鍵カプセルＣｎ，ｎ＋１を出力する第ｎ出力部と、を含み、
前記端末装置Ｕｎ＋１は、
前記鍵暗号化鍵ｐｋ１を受け付ける第（ｎ＋１）入力部と、
乱数ｋｎ＋１を設定する第（ｎ＋１）乱数設定部と、
前記鍵暗号化鍵ｐｋ１を用い、二者間共有鍵Ｒｎ＋１，１および前記二者間共有鍵Ｒｎ＋１，１の暗号文である鍵カプセルＣｎ＋１，１を得る第（ｎ＋１）二者間共有鍵生成部と、
前記鍵カプセルＣｎ＋１，１を出力する前記第（ｎ＋１）出力部と、
前記鍵カプセルＣｎ，ｎ＋１を受け付ける前記第（ｎ＋１）入力部と、を含み、
前記端末装置Ｕρは、乱数ｋρを設定する第ρ乱数設定部を含み、
前記端末装置Ｕ１は、
前記鍵カプセルＣｎ＋１，１を受け付ける第１入力部と、
前記鍵カプセル復号鍵ｓｋ１を用いて前記鍵カプセルＣｎ＋１，１を復号して前記二者間共有鍵Ｒｎ＋１，１を得る第１復号部と、
前記二者間共有鍵Ｒｎ＋１，１の関数値Ｋ１（Ｌ）を得、前記関数値ｒの関数値Ｋ１（Ｒ）を得る第１関数演算部と、
前記関数値Ｋ１（Ｌ）と前記関数値Ｋ１（Ｒ）との排他的論理和Ｔ１を得、乱数ｋ１の関数値と前記関数値Ｋ１（Ｌ）との排他的論理和Ｔ’を得る第１排他的論理和部と、
前記排他的論理和Ｔ１およびＴ’を出力する前記第１出力部と、を含み、
前記端末装置Ｕｎは、
前記関数値ｒの関数値Ｋｎ（Ｌ）を得、前記二者間共有鍵Ｒｎ，ｎ＋１の関数値Ｋｎ（Ｒ）を得る第ｎ関数演算部と、
前記関数値Ｋｎ（Ｌ）と前記関数値Ｋｎ（Ｒ）との排他的論理和Ｔｎを得る第ｎ排他的論理和部と、
乱数ｋｎおよび前記排他的論理和Ｔｎを出力する前記第ｎ出力部と、を含み、
前記端末装置Ｕｎ＋１は、
鍵カプセル復号鍵ｓｋｎ＋１を用いて前記鍵カプセルＣｎ，ｎ＋１を復号して前記二者間共有鍵Ｒｎ，ｎ＋１を得る第（ｎ＋１）復号部と、
前記二者間共有鍵Ｒｎ，ｎ＋１の関数値Ｋｎ＋１（Ｌ）を得、前記二者間共有鍵Ｒｎ＋１，１の関数値Ｋｎ＋１（Ｒ）を得る第（ｎ＋１）関数演算部と、
前記関数値Ｋｎ＋１（Ｌ）と前記関数値Ｋｎ＋１（Ｒ）との排他的論理和Ｔｎ＋１を得る第（ｎ＋１）排他的論理和部と、
乱数ｋｎ＋１および前記排他的論理和Ｔｎ＋１を出力する前記第（ｎ＋１）出力部と、を含み、
端末装置Ｕｚは、
乱数ｋｚを出力する第ｚ出力部を含み、
前記鍵配送管理装置は、
前記乱数ｋ２，…，ｋｎ＋１を含む複数の値の排他的論理和ｋ’を得て出力し、排他的論理和Ｔ２，…，Ｔｎ‐１を空とした排他的論理和Ｔ１，…，Ｔｗ‐１の排他的論理和Ｔｗ’を得て出力する排他的論理和部を含み、
前記端末装置Ｕ１は、
前記排他的論理和ｋ’と前記乱数ｋ１との排他的論理和の関数値を共有鍵ＳＫとして得る第１共有鍵生成部を含み、
前記端末装置Ｕｎは、
排他的論理和Ｔｎ’と関数値Ｋｎ（Ｌ）との排他的論理和によって前記関数値Ｋ１（Ｌ）を得る第ｎ関数値復元部と、
前記排他的論理和Ｔ’と前記関数値Ｋ１（Ｌ）との排他的論理和によって前記乱数ｋ１の関数値を得る第ｎ乱数復元部と、
前記排他的論理和ｋ’と前記乱数ｋ１の関数値から得られる前記乱数ｋ１との排他的論理和の関数値を前記共有鍵ＳＫとして得る第ｎ共有鍵生成部と、を含み、
前記端末装置Ｕｎ＋１は、
排他的論理和Ｔｎ＋１’と関数値Ｋｎ＋１（Ｌ）との排他的論理和によって前記関数値Ｋ１（Ｌ）を得る第（ｎ＋１）関数値復元部と、
前記排他的論理和Ｔ’と前記関数値Ｋ１（Ｌ）との排他的論理和によって前記乱数ｋ１の関数値を得る第（ｎ＋１）乱数復元部と、
前記排他的論理和ｋ’と前記乱数ｋ１との排他的論理和の関数値を前記共有鍵ＳＫとして得る第（ｎ＋１）共有鍵生成部と、を含み、
前記端末装置Ｕρは、
排他的論理和Ｔρ’と前記関数値ｒの関数値Ｋ１（Ｒ）との排他的論理和によって前記関数値Ｋ１（Ｌ）を得る第ρ関数値復元部と、
前記排他的論理和Ｔ’と前記関数値Ｋ１（Ｌ）との排他的論理和によって前記乱数ｋ１の関数値を得る第ρ乱数復元部と、
前記排他的論理和ｋ’と前記乱数ｋ１との排他的論理和の関数値を前記共有鍵ＳＫとして得る第ρ共有鍵生成部と、を含む、鍵交換システム。
【請求項３】
端末装置Ｕ１，…，Ｕｎと鍵配送管理装置とを有し、ｎが３以上の整数であり、ｉ＝１，…，ｎであり、ｊが１以上ｎ以下の整数であり、ｙ＝１，…，ｎかつｙ≠ｊかつｙ≠（ｊ−２ ｍｏｄ ｎ）＋１であり、ｘ＝１，…，ｎかつｘ≠ｊかつｘ≠（ｊ−２ ｍｏｄ ｎ）＋１かつｘ≠（ｊ ｍｏｄ ｎ）＋１であり、正整数αに対して−１ ｍｏｄ α＝α−１であり、
端末装置Ｕｉは、
二者間共有鍵Ｈｉ（Ｌ）＝Ｒ（ｉ−２ ｍｏｄ ｎ）＋１，ｉおよびＨｉ（Ｒ）＝Ｒｉ，（ｉ ｍｏｄ ｎ）＋１を格納する第ｉ記憶部を含み、
端末装置Ｕ（ｊ ｍｏｄ ｎ）＋１は、
格子暗号またはコードベース暗号である公開鍵暗号方式の耐量子計算機暗号に則った鍵カプセル復号鍵ｓｋ（ｊ ｍｏｄ ｎ）＋１を格納する第（ｊ＋１）記憶部と、
前記鍵カプセル復号鍵ｓｋ（ｊ ｍｏｄ ｎ）＋１に対応する鍵暗号化鍵ｐｋ（ｊ ｍｏｄ ｎ）＋１を出力する第（ｊ＋１）出力部と、を含み、
端末装置Ｕ（ｊ−２ ｍｏｄ ｎ）＋１は、
前記鍵暗号化鍵ｐｋ（ｊ ｍｏｄ ｎ）＋１を受け付ける第（ｊ−１）入力部と、
乱数ｋ（ｊ−２ ｍｏｄ ｎ）＋１を設定する第（ｊ−１）乱数設定部と、
前記鍵暗号化鍵ｐｋ（ｊ ｍｏｄ ｎ）＋１を用い、二者間共有鍵Ｒ（ｊ−２ ｍｏｄ ｎ）＋１，（ｊ ｍｏｄ ｎ）＋１および前記二者間共有鍵Ｒ（ｊ−２ ｍｏｄ ｎ）＋１，（ｊ ｍｏｄ ｎ）＋１の暗号文である鍵カプセルＣ（ｊ−２ ｍｏｄ ｎ）＋１，（ｊ ｍｏｄ ｎ）＋１を得る第（ｊ−１）二者間共有鍵生成部と、
前記鍵カプセルＣ（ｊ−２ ｍｏｄ ｎ）＋１，（ｊ ｍｏｄ ｎ）＋１を出力する第（ｊ−１）出力部と、を含み、
端末装置Ｕｙは、
乱数ｋｙを設定する第ｙ乱数設定部を含み、
前記端末装置Ｕ（ｊ ｍｏｄ ｎ）＋１は、
前記鍵カプセルＣ（ｊ−２ ｍｏｄ ｎ）＋１，（ｊ ｍｏｄ ｎ）＋１を受け付ける第（ｊ＋１）入力部を含み、
前記端末装置Ｕ（ｊ−２ ｍｏｄ ｎ）＋１は、
二者間共有鍵Ｈ（ｊ−２ ｍｏｄ ｎ）＋１（Ｌ）の関数値Ｋ（ｊ−２ ｍｏｄ ｎ）＋１（Ｌ）を得、前記二者間共有鍵Ｒ（ｊ−２ ｍｏｄ ｎ）＋１，（ｊ ｍｏｄ ｎ）＋１の関数値Ｋ（ｊ−２ ｍｏｄ ｎ）＋１（Ｒ）を得る第（ｊ−１）関数演算部と、
前記関数値Ｋ（ｊ−２ ｍｏｄ ｎ）＋１（Ｌ）と前記関数値Ｋ（ｊ−２ ｍｏｄ ｎ）＋１（Ｒ）との排他的論理和Ｔ（ｊ−２ ｍｏｄ ｎ）＋１を得、乱数ｋ（ｊ−２ ｍｏｄ ｎ）＋１の関数値と前記関数値Ｋ（ｊ−２ ｍｏｄ ｎ）＋１（Ｌ）との排他的論理和Ｔ’を得る第（ｊ−１）排他的論理和部と、
前記排他的論理和Ｔ（ｊ−２ ｍｏｄ ｎ）＋１および前記排他的論理和Ｔ’を出力する前記第（ｊ−１）出力部と、を含み、
前記端末装置Ｕ（ｊ ｍｏｄ ｎ）＋１は、
鍵カプセル復号鍵ｓｋ（ｊ ｍｏｄ ｎ）＋１を用いて前記鍵カプセルＣ（ｊ−２ ｍｏｄ ｎ）＋１，（ｊ ｍｏｄ ｎ）＋１を復号して前記二者間共有鍵Ｒ（ｊ−２ ｍｏｄ ｎ）＋１，（ｊ ｍｏｄ ｎ）＋１を得る第（ｊ＋１）復号部と、
前記二者間共有鍵Ｒ（ｊ−２ ｍｏｄ ｎ）＋１，（ｊ ｍｏｄ ｎ）＋１の関数値Ｋ（ｊ ｍｏｄ ｎ）＋１（Ｌ）を得、二者間共有鍵Ｈ（ｊ ｍｏｄ ｎ）＋１（Ｒ）の関数値Ｋ（ｊ ｍｏｄ ｎ）＋１（Ｒ）を得る第（ｊ＋１）関数演算部と、
前記関数値Ｋ（ｊ ｍｏｄ ｎ）＋１（Ｌ）と前記関数値Ｋ（ｊ ｍｏｄ ｎ）＋１（Ｒ）との排他的論理和Ｔ（ｊ ｍｏｄ ｎ）＋１を得る第（ｊ＋１）排他的論理和部と、
乱数ｋ（ｊ ｍｏｄ ｎ）＋１および前記排他的論理和Ｔ（ｊ ｍｏｄ ｎ）＋１を出力する前記第（ｊ＋１）出力部と、を含み、
前記端末装置Ｕｘは、
二者間共有鍵Ｈｘ（Ｌ）の関数値Ｋｘ（Ｌ）を得、二者間共有鍵Ｈｘ（Ｒ）の関数値Ｋｘ（Ｒ）を得る第ｘ関数演算部と、
前記関数値Ｋｘ（Ｌ）と前記関数値Ｋｘ（Ｒ）との排他的論理和Ｔｘを得る第ｘ排他的論理和部と、
乱数ｋｘおよび前記排他的論理和Ｔｘを出力する第ｘ出力部と、を含み、
前記鍵配送管理装置は、
前記乱数ｋ１，…，ｋｎ（ただし、ｋｊ，ｋｊ＋１を除く）を含む複数の値の排他的論理和ｋ’を得て出力するｋ’生成部と、
ｙ＜ｊ−１のときに排他的論理和Ｔ１，…，Ｔｙ‐１，Ｔｊ‐１，…，Ｔｎの排他的論理和Ｔｙ’を得て出力し、ｊ＋１≦ｉのときに排他的論理和Ｔｊ‐１，…，Ｔｙ‐１の排他的論理和Ｔｙ’を得て出力する排他的論理和部と、を含み、
前記端末装置Ｕｙは、
排他的論理和Ｔｙ’と関数値Ｋｙ（Ｌ）との排他的論理和によって前記関数値Ｋ（ｊ−２ ｍｏｄ ｎ）＋１（Ｌ）を得る第ｙ関数値復元部と、
前記排他的論理和Ｔ’と前記関数値Ｋ（ｊ−２ ｍｏｄ ｎ）＋１（Ｌ）との排他的論理和によって前記乱数ｋ（ｊ−２ ｍｏｄ ｎ）＋１の関数値を得る第ｙ乱数復元部と、
前記排他的論理和ｋ’と前記乱数ｋ（ｊ−２ ｍｏｄ ｎ）＋１の関数値から得られる前記乱数ｋ（ｊ−２ ｍｏｄ ｎ）＋１との排他的論理和の関数値を共有鍵ＳＫとして得る第ｙ共有鍵生成部と、を含み、
前記端末装置Ｕｊ−１は、
前記排他的論理和ｋ’と前記乱数ｋ（ｊ−２ ｍｏｄ ｎ）＋１との排他的論理和の関数値を前記共有鍵ＳＫとして得る第（ｊ−１）共有鍵生成部を含む、鍵交換システム。
【請求項４】
請求項１から３のいずれかの鍵交換システムであって、
κ１（ν）およびκ２（ν）が正整数であり、Ａνがκ１（ν）×κ２（ν）の基底行列であり、νおよびμが正整数であり、ｅνがκ２（ν）個の要素からなるベクトルであり、
鍵カプセル復号鍵ｓｋνがκ１（ν）個の整数からなるベクトルｓνであり、
鍵暗号化鍵ｐｋνがｂν＝Ａνｓν＋ｅνであり、
鍵カプセルＣν，（ν ｍｏｄ μ）＋１が｛γν，ξν’｝であり、二者間共有鍵Ｒν，（ν ｍｏｄ μ）＋１がＲＯＵＮＤ（２ξν−／ｑ）であり、
γν＝Ａνｓν’＋ｅν’であり、ξν’がｆｌｏｏｒ（４ξν−／ｑ） ｍｏｄ ２であり、ｓν’がκ１（ν）個の整数からなるベクトルであり、ｅν’およびｅν”がκ２（ν）個の要素からなるベクトルであり、ξν＝ｂ（ν ｍｏｄ μ）＋１ｓν’＋ｅν”であり、ξν−がξνのランダム関数値であり、ｑが２以上の整数であり、ｆｌｏｏｒが床関数であり、ＲＯＵＮＤが四捨五入関数である、鍵交換システム。
【請求項５】
請求項１の前記鍵交換システムが有する前記端末装置Ｕｉ。
【請求項６】
請求項２の前記鍵交換システムが有する前記端末装置Ｕｉ。
【請求項７】
請求項３の前記鍵交換システムが有する前記端末装置Ｕｉ。
【請求項８】
鍵交換システムの鍵交換方法であって、
端末装置Ｕ１，…，Ｕｎと鍵配送管理装置とを有し、ｎが３以上の整数であり、ｉ＝１，…，ｎであり、ｖ＝２，…，ｎであり、正整数αに対して−１ ｍｏｄ α＝α−１であり、
端末装置Ｕｉの第ｉ記憶部に、格子暗号またはコードベース暗号である公開鍵暗号方式の耐量子計算機暗号に則った鍵カプセル復号鍵ｓｋｉが格納されており、
前記端末装置Ｕｉの第ｉ出力部が前記鍵カプセル復号鍵ｓｋｉに対応する鍵暗号化鍵ｐｋｉを出力するステップと、
前記端末装置Ｕｉの第ｉ入力部が前記耐量子計算機暗号に則った鍵暗号化鍵ｐｋ（ｉ ｍｏｄ ｎ）＋１を受け付けるステップと、
前記端末装置Ｕｉの第ｉ乱数設定部が乱数ｋｉを設定するステップと、
前記端末装置Ｕｉの第ｉ二者間共有鍵生成部が前記鍵暗号化鍵ｐｋ（ｉ ｍｏｄ ｎ）＋１を用い、二者間共有鍵Ｒｉ，（ｉ ｍｏｄ ｎ）＋１および前記二者間共有鍵Ｒｉ，（ｉ ｍｏｄ ｎ）＋１の暗号文である鍵カプセルＣｉ，（ｉ ｍｏｄ ｎ）＋１を得るステップと、
前記端末装置Ｕｉの前記第ｉ出力部が前記鍵カプセルＣｉ，（ｉ ｍｏｄ ｎ）＋１を出力するステップと、
前記端末装置Ｕｉの前記第ｉ入力部が鍵カプセルＣ（ｉ−２ ｍｏｄ ｎ）＋１，ｉを受け付けるステップと、
端末装置Ｕ１の第１復号部が鍵カプセル復号鍵ｓｋ１を用いて鍵カプセルＣｎ，１を復号して二者間共有鍵Ｒｎ，１を得るステップと、
前記端末装置Ｕ１の第１関数演算部が前記二者間共有鍵Ｒｎ，１の関数値Ｋ１（Ｌ）を得、二者間共有鍵Ｒ１，２の関数値Ｋ１（Ｒ）を得るステップと、
前記端末装置Ｕ１の第１排他的論理和部が前記関数値Ｋ１（Ｌ）と前記関数値Ｋ１（Ｒ）との排他的論理和Ｔ１を得、乱数ｋ１の関数値と前記関数値Ｋ１（Ｌ）との排他的論理和Ｔ’を得るステップと、
前記端末装置Ｕ１の第１出力部が前記排他的論理和Ｔ１およびＴ’を出力するステップと、
端末装置Ｕｖの第ｖ復号部が鍵カプセル復号鍵ｓｋｖを用いて鍵カプセルＣ（ｖ−２ ｍｏｄ ｎ）＋１，ｖを復号して二者間共有鍵Ｒ（ｖ−２ ｍｏｄ ｎ）＋１，ｖを得るステップと、
前記端末装置Ｕｖの第ｖ関数演算部が前記二者間共有鍵Ｒ（ｖ−２ ｍｏｄ ｎ）＋１，ｖの関数値Ｋｖ（Ｌ）を得、二者間共有鍵Ｒｖ，（ｖ ｍｏｄ ｎ）＋１の関数値Ｋｖ（Ｒ）を得るステップと、
前記端末装置Ｕｖの第ｖ排他的論理和部が前記関数値Ｋｖ（Ｌ）と前記関数値Ｋｖ（Ｒ）との排他的論理和Ｔｖを得るステップと、
前記端末装置Ｕｖの第ｖ出力部が乱数ｋｖおよび前記排他的論理和Ｔｖを出力するステップと、
前記鍵配送管理装置の排他的論理和部が前記乱数ｋ２，…，ｋｎを含む複数の値の排他的論理和ｋ’を得て出力し、排他的論理和Ｔ１，…，Ｔｖ‐１の排他的論理和Ｔｖ’を得て出力するステップと、
前記端末装置Ｕ１の第１共有鍵生成部が前記排他的論理和ｋ’と前記乱数ｋ１との排他的論理和の関数値を共有鍵ＳＫとして得るステップと、
前記端末装置Ｕｖの第ｖ関数値復元部が前記排他的論理和Ｔｖ’と前記関数値Ｋｖ（Ｌ）との排他的論理和によって前記関数値Ｋ１（Ｌ）を得るステップと、
前記端末装置Ｕｖの第ｖ乱数復元部が前記排他的論理和Ｔ’と前記関数値Ｋ１（Ｌ）との排他的論理和によって前記乱数ｋ１の関数値を得るステップと、
前記端末装置Ｕｖの第ｖ共有鍵生成部が前記排他的論理和ｋ’と前記乱数ｋ１の関数値から得られる前記乱数ｋ１との排他的論理和の関数値を前記共有鍵ＳＫとして得るステップと
を有する鍵交換方法。
【請求項９】
鍵交換システムの鍵交換方法であって、
端末装置Ｕ１，…，Ｕｎ＋１と鍵配送管理装置とを有し、ｎが３以上の整数であり、ｉ＝１，…，ｎであり、ｖ＝２，…，ｎであり、ｗ＝２，…，ｎ＋１であり、ｚ＝２，…，ｎ−１であり、ρ＝１，…，ｎ−１であり、正整数αに対して−１ ｍｏｄ α＝α−１であり、
端末装置Ｕｉの第ｉ記憶部に、関数値ｒが格納されており、
端末装置Ｕ１の第１記憶部に、格子暗号またはコードベース暗号である公開鍵暗号方式の耐量子計算機暗号に則った鍵カプセル復号鍵ｓｋ１が格納されており、
端末装置Ｕｎ＋１の第（ｎ＋１）記憶部に、前記耐量子計算機暗号に則った鍵カプセル復号鍵ｓｋｎ＋１が格納されており、
前記端末装置Ｕ１の第１出力部が前記鍵カプセル復号鍵ｓｋ１に対応する鍵暗号化鍵ｐｋ１を出力するステップと、
前記端末装置Ｕｎ＋１の第（ｎ＋１）出力部が前記鍵カプセル復号鍵ｓｋｎ＋１に対応する鍵暗号化鍵ｐｋｎ＋１を出力するステップと、
端末装置Ｕｎの第ｎ入力部が前記鍵暗号化鍵ｐｋｎ＋１を受け付けるステップと、
前記端末装置Ｕｎの第ｎ乱数設定部が乱数ｋｎを設定するステップと、
前記端末装置Ｕｎの第ｎ二者間共有鍵生成部が前記鍵暗号化鍵ｐｋｎ＋１を用い、二者間共有鍵Ｒｎ，ｎ＋１および前記二者間共有鍵Ｒｎ，ｎ＋１の暗号文である鍵カプセルＣｎ，ｎ＋１を得るステップと、
前記端末装置Ｕｎの第ｎ出力部が前記鍵カプセルＣｎ，ｎ＋１を出力するステップと、
前記端末装置Ｕｎ＋１の第（ｎ＋１）入力部が前記鍵暗号化鍵ｐｋ１を受け付けるステップと、
前記端末装置Ｕｎ＋１の第（ｎ＋１）乱数設定部が乱数ｋｎ＋１を設定するステップと、
前記端末装置Ｕｎ＋１の第（ｎ＋１）二者間共有鍵生成部が前記鍵暗号化鍵ｐｋ１を用い、二者間共有鍵Ｒｎ＋１，１および前記二者間共有鍵Ｒｎ＋１，１の暗号文である鍵カプセルＣｎ＋１，１を得るステップと、
前記端末装置Ｕｎ＋１の前記第（ｎ＋１）出力部が前記鍵カプセルＣｎ＋１，１を出力するステップと、
前記端末装置Ｕｎ＋１の前記第（ｎ＋１）入力部が前記鍵カプセルＣｎ，ｎ＋１を受け付けるステップと、
前記端末装置Ｕρの第ρ乱数設定部が乱数ｋρを設定するステップと、
前記端末装置Ｕ１の第１入力部が前記鍵カプセルＣｎ＋１，１を受け付けるステップと、
前記端末装置Ｕ１の第１復号部が前記鍵カプセル復号鍵ｓｋ１を用いて前記鍵カプセルＣｎ＋１，１を復号して前記二者間共有鍵Ｒｎ＋１，１を得るステップと、
前記端末装置Ｕ１の第１関数演算部が前記二者間共有鍵Ｒｎ＋１，１の関数値Ｋ１（Ｌ）を得、前記関数値ｒの関数値Ｋ１（Ｒ）を得るステップと、
前記端末装置Ｕ１の第１排他的論理和部が前記関数値Ｋ１（Ｌ）と前記関数値Ｋ１（Ｒ）との排他的論理和Ｔ１を得、乱数ｋ１の関数値と前記関数値Ｋ１（Ｌ）との排他的論理和Ｔ’を得るステップと、
前記端末装置Ｕ１の前記第１出力部が前記排他的論理和Ｔ１およびＴ’を出力すると、
前記端末装置Ｕｎの第ｎ関数演算部が前記関数値ｒの関数値Ｋｎ（Ｌ）を得、前記二者間共有鍵Ｒｎ，ｎ＋１の関数値Ｋｎ（Ｒ）を得るステップと、
前記端末装置Ｕｎの第ｎ排他的論理和部が前記関数値Ｋｎ（Ｌ）と前記関数値Ｋｎ（Ｒ）との排他的論理和Ｔｎを得るステップと、
前記端末装置Ｕｎの前記第ｎ出力部が乱数ｋｎおよび前記排他的論理和Ｔｎを出力するステップと、
前記端末装置Ｕｎ＋１の第（ｎ＋１）復号部が鍵カプセル復号鍵ｓｋｎ＋１を用いて前記鍵カプセルＣｎ，ｎ＋１を復号して前記二者間共有鍵Ｒｎ，ｎ＋１を得るステップと、
前記端末装置Ｕｎ＋１の第（ｎ＋１）関数演算部が前記二者間共有鍵Ｒｎ，ｎ＋１の関数値Ｋｎ＋１（Ｌ）を得、前記二者間共有鍵Ｒｎ＋１，１の関数値Ｋｎ＋１（Ｒ）を得るステップと、
前記端末装置Ｕｎ＋１の第（ｎ＋１）排他的論理和部が前記関数値Ｋｎ＋１（Ｌ）と前記関数値Ｋｎ＋１（Ｒ）との排他的論理和Ｔｎ＋１を得るステップと、
前記端末装置Ｕｎ＋１の前記第（ｎ＋１）出力部が乱数ｋｎ＋１および前記排他的論理和Ｔｎ＋１を出力するステップと、
端末装置Ｕｚの第ｚ出力部が乱数ｋｚを出力するステップと、
前記鍵配送管理装置の排他的論理和部が前記乱数ｋ２，…，ｋｎ＋１を含む複数の値の排他的論理和ｋ’を得て出力し、排他的論理和Ｔ２，…，Ｔｎ‐１を空とした排他的論理和Ｔ１，…，Ｔｗ‐１の排他的論理和Ｔｗ’を得て出力するステップと、
前記端末装置Ｕ１の第１共有鍵生成部が前記排他的論理和ｋ’と前記乱数ｋ１との排他的論理和の関数値を共有鍵ＳＫとして得るステップと、
前記端末装置Ｕｎの第ｎ関数値復元部が排他的論理和Ｔｎ’と関数値Ｋｎ（Ｌ）との排他的論理和によって前記関数値Ｋ１（Ｌ）を得るステップと、
前記端末装置Ｕｎの第ｎ乱数復元部が前記排他的論理和Ｔ’と前記関数値Ｋ１（Ｌ）との排他的論理和によって前記乱数ｋ１の関数値を得るステップと、
前記端末装置Ｕｎの第ｎ共有鍵生成部が前記排他的論理和ｋ’と前記乱数ｋ１の関数値から得られる前記乱数ｋ１との排他的論理和の関数値を前記共有鍵ＳＫとして得るステップと、
前記端末装置Ｕｎ＋１の第（ｎ＋１）関数値復元部が排他的論理和Ｔｎ＋１’と関数値Ｋｎ＋１（Ｌ）との排他的論理和によって前記関数値Ｋ１（Ｌ）を得るステップと、
前記端末装置Ｕｎ＋１の第（ｎ＋１）乱数復元部が前記排他的論理和Ｔ’と前記関数値Ｋ１（Ｌ）との排他的論理和によって前記乱数ｋ１の関数値を得るステップと、
前記端末装置Ｕｎ＋１の第（ｎ＋１）共有鍵生成部が前記排他的論理和ｋ’と前記乱数ｋ１との排他的論理和の関数値を前記共有鍵ＳＫとして得るステップと、を含み、
前記端末装置Ｕρの第ρ関数値復元部が排他的論理和Ｔρ’と前記関数値ｒの関数値Ｋ１（Ｒ）との排他的論理和によって前記関数値Ｋ１（Ｌ）を得るステップと、
前記端末装置Ｕρの第ρ乱数復元部が前記排他的論理和Ｔ’と前記関数値Ｋ１（Ｌ）との排他的論理和によって前記乱数ｋ１の関数値を得るステップと、
前記端末装置Ｕρの第ρ共有鍵生成部が前記排他的論理和ｋ’と前記乱数ｋ１との排他的論理和の関数値を前記共有鍵ＳＫとして得るステップと
を有する鍵交換方法。
【請求項１０】
鍵交換システムの鍵交換方法であって、
端末装置Ｕ１，…，Ｕｎと鍵配送管理装置とを有し、ｎが３以上の整数であり、ｉ＝１，…，ｎであり、ｊが１以上ｎ以下の整数であり、ｙ＝１，…，ｎかつｙ≠ｊかつｙ≠（ｊ−２ ｍｏｄ ｎ）＋１であり、ｘ＝１，…，ｎかつｘ≠ｊかつｘ≠（ｊ−２ ｍｏｄ ｎ）＋１かつｘ≠（ｊ ｍｏｄ ｎ）＋１であり、正整数αに対して−１ ｍｏｄ α＝α−１であり、
端末装置Ｕｉの第ｉ記憶部に、二者間共有鍵Ｈｉ（Ｌ）＝Ｒ（ｉ−２ ｍｏｄ ｎ）＋１，ｉおよびＨｉ（Ｒ）＝Ｒｉ，（ｉ ｍｏｄ ｎ）＋１が格納されており、
端末装置Ｕ（ｊ ｍｏｄ ｎ）＋１の第（ｊ＋１）記憶部に、格子暗号またはコードベース暗号である公開鍵暗号方式の耐量子計算機暗号に則った鍵カプセル復号鍵ｓｋ（ｊ ｍｏｄ ｎ）＋１が格納されており、
端末装置Ｕｉの第（ｊ＋１）出力部が前記鍵カプセル復号鍵ｓｋ（ｊ ｍｏｄ ｎ）＋１に対応する鍵暗号化鍵ｐｋ（ｊ ｍｏｄ ｎ）＋１を出力するステップと、
端末装置Ｕ（ｊ−２ ｍｏｄ ｎ）＋１の第（ｊ−１）入力部が前記鍵暗号化鍵ｐｋ（ｊ ｍｏｄ ｎ）＋１を受け付けるステップと、
前記端末装置Ｕ（ｊ−２ ｍｏｄ ｎ）＋１の第（ｊ−１）乱数設定部が乱数ｋ（ｊ−２ ｍｏｄ ｎ）＋１を設定するステップと、
前記端末装置Ｕ（ｊ−２ ｍｏｄ ｎ）＋１の第（ｊ−１）二者間共有鍵生成部が前記鍵暗号化鍵ｐｋ（ｊ ｍｏｄ ｎ）＋１を用い、二者間共有鍵Ｒ（ｊ−２ ｍｏｄ ｎ）＋１，（ｊ ｍｏｄ ｎ）＋１および前記二者間共有鍵Ｒ（ｊ−２ ｍｏｄ ｎ）＋１，（ｊ ｍｏｄ ｎ）＋１の暗号文である鍵カプセルＣ（ｊ−２ ｍｏｄ ｎ）＋１，（ｊ ｍｏｄ ｎ）＋１を得るステップと、
前記端末装置Ｕ（ｊ−２ ｍｏｄ ｎ）＋１の第（ｊ−１）出力部が前記鍵カプセルＣ（ｊ−２ ｍｏｄ ｎ）＋１，（ｊ ｍｏｄ ｎ）＋１を出力するステップと、を含み、
端末装置Ｕｙの第ｙ乱数設定部が乱数ｋｙを設定するステップと、
前記端末装置Ｕ（ｊ ｍｏｄ ｎ）＋１の第（ｊ＋１）入力部が前記鍵カプセルＣ（ｊ−２ ｍｏｄ ｎ）＋１，（ｊ ｍｏｄ ｎ）＋１を受け付けるステップと、
前記端末装置Ｕ（ｊ−２ ｍｏｄ ｎ）＋１の第（ｊ−１）関数演算部が二者間共有鍵Ｈ（ｊ−２ ｍｏｄ ｎ）＋１（Ｌ）の関数値Ｋ（ｊ−２ ｍｏｄ ｎ）＋１（Ｌ）を得、前記二者間共有鍵Ｒ（ｊ−２ ｍｏｄ ｎ）＋１，（ｊ ｍｏｄ ｎ）＋１の関数値Ｋ（ｊ−２ ｍｏｄ ｎ）＋１（Ｒ）を得るステップと、
前記端末装置Ｕ（ｊ−２ ｍｏｄ ｎ）＋１の第（ｊ−１）排他的論理和部が前記関数値Ｋ（ｊ−２ ｍｏｄ ｎ）＋１（Ｌ）と前記関数値Ｋ（ｊ−２ ｍｏｄ ｎ）＋１（Ｒ）との排他的論理和Ｔ（ｊ−２ ｍｏｄ ｎ）＋１を得、乱数ｋ（ｊ−２ ｍｏｄ ｎ）＋１の関数値と前記関数値Ｋ（ｊ−２ ｍｏｄ ｎ）＋１（Ｌ）との排他的論理和Ｔ’を得るステップと、
前記端末装置Ｕ（ｊ−２ ｍｏｄ ｎ）＋１の前記第（ｊ−１）出力部が前記排他的論理和Ｔ（ｊ−２ ｍｏｄ ｎ）＋１および前記排他的論理和Ｔ’を出力するステップと、
前記端末装置Ｕ（ｊ ｍｏｄ ｎ）＋１の第（ｊ＋１）復号部が鍵カプセル復号鍵ｓｋ（ｊ ｍｏｄ ｎ）＋１を用いて前記鍵カプセルＣ（ｊ−２ ｍｏｄ ｎ）＋１，（ｊ ｍｏｄ ｎ）＋１を復号して前記二者間共有鍵Ｒ（ｊ−２ ｍｏｄ ｎ）＋１，（ｊ ｍｏｄ ｎ）＋１を得るステップと、
前記端末装置Ｕ（ｊ ｍｏｄ ｎ）＋１の第（ｊ＋１）関数演算部が前記二者間共有鍵Ｒ（ｊ−２ ｍｏｄ ｎ）＋１，（ｊ ｍｏｄ ｎ）＋１の関数値Ｋ（ｊ ｍｏｄ ｎ）＋１（Ｌ）を得、二者間共有鍵Ｈ（ｊ ｍｏｄ ｎ）＋１（Ｒ）の関数値Ｋ（ｊ ｍｏｄ ｎ）＋１（Ｒ）を得るステップと、
前記端末装置Ｕ（ｊ ｍｏｄ ｎ）＋１の第（ｊ＋１）排他的論理和部が前記関数値Ｋ（ｊ ｍｏｄ ｎ）＋１（Ｌ）と前記関数値Ｋ（ｊ ｍｏｄ ｎ）＋１（Ｒ）との排他的論理和Ｔ（ｊ ｍｏｄ ｎ）＋１を得るステップと、
前記端末装置Ｕ（ｊ ｍｏｄ ｎ）＋１の前記第（ｊ＋１）出力部が乱数ｋ（ｊ ｍｏｄ ｎ）＋１および前記排他的論理和Ｔ（ｊ ｍｏｄ ｎ）＋１を出力するステップと、
前記端末装置Ｕｘの第ｘ関数演算部が二者間共有鍵Ｈｘ（Ｌ）の関数値Ｋｘ（Ｌ）を得、二者間共有鍵Ｈｘ（Ｒ）の関数値Ｋｘ（Ｒ）を得るステップと、
前記端末装置Ｕｘの第ｘ排他的論理和部が前記関数値Ｋｘ（Ｌ）と前記関数値Ｋｘ（Ｒ）との排他的論理和Ｔｘを得るステップと、
前記端末装置Ｕｘの第ｘ出力部が乱数ｋｘおよび前記排他的論理和Ｔｘを出力するステップと、を含み、
前記鍵配送管理装置のｋ’生成部が前記乱数ｋ１，…，ｋｎ（ただし、ｋｊ，ｋｊ＋１を除く）を含む複数の値の排他的論理和ｋ’を得て出力するステップと、
前記鍵配送管理装置の排他的論理和部がｙ＜ｊ−１のときに排他的論理和Ｔ１，…，Ｔｙ‐１，Ｔｊ‐１，…，Ｔｎの排他的論理和Ｔｙ’を得て出力し、ｊ＋１≦ｉのときに排他的論理和Ｔｊ‐１，…，Ｔｙ‐１の排他的論理和Ｔｙ’を得て出力するステップと、
前記端末装置Ｕｙの第ｙ関数値復元部が排他的論理和Ｔｙ’と関数値Ｋｙ（Ｌ）との排他的論理和によって前記関数値Ｋ（ｊ−２ ｍｏｄ ｎ）＋１（Ｌ）を得るステップと、
前記端末装置Ｕｙの第ｙ乱数復元部が前記排他的論理和Ｔ’と前記関数値Ｋ（ｊ−２ ｍｏｄ ｎ）＋１（Ｌ）との排他的論理和によって前記乱数ｋ（ｊ−２ ｍｏｄ ｎ）＋１の関数値を得るステップと、
前記端末装置Ｕｙの第ｙ共有鍵生成部が前記排他的論理和ｋ’と前記乱数ｋ（ｊ−２ ｍｏｄ ｎ）＋１の関数値から得られる前記乱数ｋ（ｊ−２ ｍｏｄ ｎ）＋１との排他的論理和の関数値を共有鍵ＳＫとして得るステップと、
前記端末装置Ｕｊ−１の第（ｊ−１）共有鍵生成部が前記排他的論理和ｋ’と前記乱数ｋ（ｊ−２ ｍｏｄ ｎ）＋１との排他的論理和の関数値を前記共有鍵ＳＫとして得るステップと
を有する鍵交換方法。
【請求項１１】
請求項５の端末装置としてコンピュータを機能させるためのプログラム。
【請求項１２】
請求項６の端末装置としてコンピュータを機能させるためのプログラム。
【請求項１３】
請求項７の端末装置としてコンピュータを機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、暗号技術に関し、特に多者間鍵交換技術に関する。
【背景技術】
【０００２】
多者間鍵交換技術にはｍｅｓｈ型の鍵交換であるＧＫＥ(Group Key Exchange)とｓｔａｒ型の鍵交換であるＭＫＤ(Multi Key Distribution)がある。これらの鍵交換は参加人数に比例して通信コストが上がる、鍵配送管理装置に共有鍵を伝達してしまう等の課題があった。これらの課題を解決したのがＤＭＫＤ(Dynamic Multi-Cast Key Distribution: Scalable, Dynamic and Provably Secure Construction)である（例えば、特許文献１および非特許文献１等参照）。この方式では、人数に依らず定数Roundで鍵交換を行うことができ、鍵配送管理装置にも共有鍵を秘匿できる。
【０００３】
近年量子コンピュータの研究開発は急激に進んでおり、暗号の安全性を脅かすものとなっている。それに伴い、量子コンピュータの解読にも耐え得る暗号方式の検討が進められている。量子コンピュータによる解読に耐え得る暗号のことを「耐量子安全」である暗号という。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特開２０１６−１３４８２６号公報
【非特許文献】
【０００５】
【非特許文献１】Kazuki Yoneyama, Reo Yoshida, Yuto Kawahara, Tetsutaro Kobayashi, Hitoshi Fuji, Tomohide Yamamoto, "Multi-Cast Key Distribution: Scalable, Dynamic and Provably Secure Construction," International Conference on Provable Security (ProvSec 2016), LNCS10005, pp.207-226, Nov. 2016.
【発明の概要】
【発明が解決しようとする課題】
【０００６】
ＤＭＫＤは多者間の鍵交換を効率よく安全に行うことができるが、耐量子安全でない。そのため、今後、十分な計算量を持った量子コンピュータが実用化すると、安全性が担保されない。またＤＭＫＤは耐量子性を持たせることが困難なＤＨ（Diffie-Hellman）型の二者間鍵交換に基づいており、ＤＭＫＤを耐量子安全な方式に変更することも容易ではない。【０００７】
本発明はこのような点に鑑みてなされたものであり、耐量子性を持つ多者間鍵交換技術を提供することを目的とする。
【課題を解決するための手段】
【０００８】
端末装置Ｕｉは、公開鍵暗号方式の耐量子計算機暗号に則った鍵カプセル復号鍵ｓｋｉを格納し、鍵カプセル復号鍵ｓｋｉに対応する鍵暗号化鍵ｐｋｉを出力する。ただし、ｎが３以上の整数であり、ｉ＝１，…，ｎである。【０００９】
端末装置Ｕｉは、耐量子計算機暗号に則った鍵暗号化鍵ｐｋ（ｉ ｍｏｄ ｎ）＋１を受け付け、乱数ｋｉを設定し、鍵暗号化鍵ｐｋ（ｉ ｍｏｄ ｎ）＋１を用い、二者間共有鍵Ｒｉ，（ｉ ｍｏｄ ｎ）＋１および二者間共有鍵Ｒｉ，（ｉ ｍｏｄ ｎ）＋１の暗号文である鍵カプセルＣｉ，（ｉ ｍｏｄ ｎ）＋１を得、鍵カプセルＣｉ，（ｉ ｍｏｄ ｎ）＋１を出力し、鍵カプセルＣ（ｉ−２ ｍｏｄ ｎ）＋１，ｉを受け付ける。ただし、正整数αに対して−１ ｍｏｄ α＝α−１である。【００１０】
端末装置Ｕ１は、鍵カプセル復号鍵ｓｋ１を用いて鍵カプセルＣｎ，１を復号して二者間共有鍵Ｒｎ，１を得、二者間共有鍵Ｒｎ，１の関数値Ｋ１（Ｌ）を得、二者間共有鍵Ｒ１，２の関数値Ｋ１（Ｒ）を得、関数値Ｋ１（Ｌ）と関数値Ｋ１（Ｒ）との排他的論理和Ｔ１を得、乱数ｋ１の関数値と関数値Ｋ１（Ｌ）との排他的論理和Ｔ’を得、排他的論理和Ｔ１およびＴ’を出力する。端末装置Ｕｖは、鍵カプセル復号鍵ｓｋｖを用いて鍵カプセルＣ（ｖ−２ ｍｏｄ ｎ）＋１，ｖを復号して二者間共有鍵Ｒ（ｖ−２ ｍｏｄ ｎ）＋１，ｖを得、二者間共有鍵Ｒ（ｖ−２ ｍｏｄ ｎ）＋１，ｖの関数値Ｋｖ（Ｌ）を得、二者間共有鍵Ｒｖ，（ｖ ｍｏｄ ｎ）＋１の関数値Ｋｖ（Ｒ）を得、関数値Ｋｖ（Ｌ）と関数値Ｋｖ（Ｒ）との排他的論理和Ｔｖを得、乱数ｋｖおよび排他的論理和Ｔｖを出力する。ただし、ｖ＝２，…，ｎである。【００１１】
鍵配送管理装置は、乱数ｋ２，…，ｋｎを含む複数の値の排他的論理和ｋ’を得て出力し、排他的論理和Ｔ１，…，Ｔｖ‐１の排他的論理和Ｔｖ’を得て出力する。【００１２】
端末装置Ｕ１は、排他的論理和ｋ’と乱数ｋ１との排他的論理和の関数値を共有鍵ＳＫとして得る。端末装置Ｕｖは、排他的論理和Ｔｖ’と関数値Ｋｖ（Ｌ）との排他的論理和によって関数値Ｋ１（Ｌ）を得、排他的論理和Ｔ’と関数値Ｋ１（Ｌ）との排他的論理和によって乱数ｋ１の関数値を得、排他的論理和ｋ’と乱数ｋ１の関数値から得られる乱数ｋ１との排他的論理和の関数値を共有鍵ＳＫとして得る。
【発明の効果】
【００１３】
以上により、耐量子性を持つ多者間鍵交換を実現できる。
【図面の簡単な説明】
【００１４】
［図１］図１は第１実施形態の鍵交換システムの構成を例示したブロック図である。
［図２］図２は実施形態の端末装置の構成を例示したブロック図である。
［図３］図３は実施形態の鍵配送管理装置の構成を例示したブロック図である。
［図４］図４は実施形態の鍵交換方法（Round1）を説明するための図である。
［図５］図５は実施形態の鍵交換方法（Round2）を説明するための図である。
［図６］図６は実施形態の鍵交換方法（Round3）を説明するための図である。
［図７］図７は実施形態の鍵交換方法（共有鍵生成）を説明するための図である。
［図８］図８は第２実施形態の鍵交換システムの構成を例示したブロック図である。
［図９］図９は実施形態の端末装置の構成を例示したブロック図である。
［図１０］図１０は端末装置が追加された際に行われる実施形態の鍵交換方法（Roun
d1）を説明するための図である。
［図１１］図１１は端末装置が追加された際に行われる実施形態の鍵交換方法（Roun
d2）を説明するための図である。
［図１２］図１２は端末装置が追加された際に行われる実施形態の鍵交換方法（Roun
d3）を説明するための図である。
［図１３］図１３は端末装置が追加された際に行われる実施形態の鍵交換方法（共有
鍵生成）を説明するための図である。
［図１４］図１４は第３実施形態の鍵交換システムの構成を例示したブロック図であ
る。
［図１５］図１５は端末装置が除外された際に行われる実施形態の鍵交換方法（Roun
d1）を説明するための図である。
［図１６］図１６は端末装置が除外された際に行われる実施形態の鍵交換方法（Roun
d2）を説明するための図である。
［図１７］図１７は端末装置が除外された際に行われる実施形態の鍵交換方法（Roun
d3）を説明するための図である。
［図１８］図１８は端末装置が除外された際に行われる実施形態の鍵交換方法（共有
鍵生成）を説明するための図である。
【発明を実施するための形態】
【００１５】
以下、図面を参照して本発明の実施形態を説明する。
［第１実施形態］
第１実施形態を説明する。第１実施形態では複数の端末装置の間で共有鍵を共有する処理を説明する。
＜構成＞
図１に例示するように、本形態の鍵交換システム１は、ｎ個の端末装置１００−１〜１００−ｎ（端末装置Ｕ１，…，Ｕｎ）と鍵配送管理装置１５０とを有する。ｎは３以上の整数である。各端末装置１００−ｉ（端末装置Ｕｉ）（ただし、ｉ＝１，…，ｎ）は、インターネット等を通じて鍵配送管理装置１５０と通信可能に構成されている。
【００１６】
図２に例示するように、端末装置１００−ｉは、入力部１０１−ｉ、出力部１０２−ｉ、記憶部１０３−ｉ、制御部１０４−ｉ、鍵ペア生成部１０５−ｉ、乱数設定部１０６−ｉ、二者間共有鍵生成部１０７−ｉ、復号部１０８−ｉ、関数演算部１０９−ｉ、排他的論理和部１１０−ｉ、関数値復元部１１１−ｉ、乱数復元部１１３−ｉ、および共有鍵生成部１１２−ｉを有する。端末装置１００−ｉは、制御部１０４−ｉの制御の下で各処理を実行する。当該処理で得られたデータは記憶部１０３−ｉに格納され、必要に応じて記憶部１０３−ｉから読み出されて他の処理に用いられる。
【００１７】
図３に例示するように、鍵配送管理装置１５０は、入力部１５１、出力部１５２、演算部１５３、制御部１５４、ＳＩＤ設定部１５５、排他的論理和部１５６、および記憶部１５７を有する。鍵配送管理装置１５０は、制御部１５４の制御の下で各処理を実行する。当該処理で得られたデータは記憶部１５７に格納され、必要に応じて記憶部１５７から読み出されて他の処理に用いられる。
【００１８】
＜処理＞
次に、本形態の鍵交換処理を説明する。本形態の鍵交換処理は、Ｒｏｕｎｄ１〜３および共有鍵生成を含む。
≪Ｒｏｕｎｄ１（図４）≫
端末装置１００−ｉ（図２）の鍵ペア生成部１０５−ｉ（ただし、ｉ＝１，…，ｎ）は、公開鍵暗号方式の耐量子計算機暗号に則った鍵カプセル復号鍵ｓｋｉおよび当該鍵カプセル復号鍵ｓｋｉに対応する鍵暗号化鍵ｐｋｉからなる鍵ペア（ｐｋｉ，ｓｋｉ）を生成する。例えば、鍵ペア生成部１０５−ｉは、乱数ｒｉを生成し、これを鍵カプセル化アルゴリズムの鍵生成アルゴリズムに適用して鍵ペア（ｐｋｉ，ｓｋｉ）を生成して出力する。乱数は疑似乱数であってもよいし、真正乱数であってもよい（以下、同様）。公開鍵暗号方式の耐量子計算機暗号としては、例えば、格子暗号、コードベース暗号などを例示できる。鍵カプセル化アルゴリズムとしては、例えば、以下のものを用いることができる。
参考文献１：Chris Peikert, Lattice Cryptography for the Internet, PQCrypto 2014, LNCS 8772, pp. 197-219, 2014.
生成された鍵カプセル復号鍵ｓｋｉおよび鍵暗号化鍵ｐｋｉは各端末装置１００−ｉの記憶部１０３−ｉに格納される。また、鍵暗号化鍵ｐｋｉは出力部１０２−ｉから出力され、鍵配送管理装置１５０に送信される。
【００１９】
鍵暗号化鍵ｐｋｉは鍵配送管理装置１５０（図３）の入力部１５１に入力される（受け付けられる）。鍵暗号化鍵ｐｋｉが入力部１５１に入力され次第、制御部１５４は当該鍵暗号化鍵ｐｋｉを出力部１５２に送り、出力部１５２は当該鍵暗号化鍵ｐｋｉを端末装置１００−（（ｉ−２ ｍｏｄ ｎ）＋１）に送信する。なお、正整数αに対して−１ ｍｏｄ α＝α−１を満たす。
【００２０】
≪Ｒｏｕｎｄ２（図５）≫
端末装置１００−ｉ（図２）の入力部１０１−ｉは鍵暗号化鍵ｐｋ（ｉ ｍｏｄ ｎ）＋１を受信し（受け付け）、鍵暗号化鍵ｐｋ（ｉ ｍｏｄ ｎ）＋１を記憶部１０３−ｉに格納する。
【００２１】
端末装置１００−ｉの乱数設定部１０６−ｉは乱数ｋｉを設定して出力する。乱数ｋｉは記憶部１０３−ｉに格納される。
【００２２】
端末装置１００−ｉの二者間共有鍵生成部１０７−ｉは、鍵暗号化鍵ｐｋ（ｉ ｍｏｄ ｎ）＋１を用い、二者間共有鍵Ｒｉ，（ｉ ｍｏｄ ｎ）＋１および当該二者間共有鍵Ｒｉ，（ｉ ｍｏｄ ｎ）＋１の暗号文である鍵カプセルＣｉ，（ｉ ｍｏｄ ｎ）＋１を得て出力する。例えば、二者間共有鍵生成部１０７−ｉは参考文献１に記載された方法で二者間共有鍵Ｒｉ，（ｉ ｍｏｄ ｎ）＋１および鍵カプセルＣｉ，（ｉ ｍｏｄ ｎ）＋１を生成して出力する。二者間共有鍵Ｒｉ，（ｉ ｍｏｄ ｎ）＋１は記憶部１０３−ｉに格納される。鍵カプセルＣｉ，（ｉ ｍｏｄ ｎ）＋１は出力部１０２−ｉから出力され、鍵配送管理装置１５０に送信される。
【００２３】
鍵配送管理装置１５０（図３）の入力部１５１は、各端末装置１００−ｉ（ただし、ｉ＝１，…，ｎ）から送信された鍵カプセルＣｉ，（ｉ ｍｏｄ ｎ）＋１を受信する。ＳＩＤ設定部１５５はｓｉｄ（セッションＩＤ）を生成し、代表端末装置として端末装置１００−１を選択する。演算部１５３は（ｓｉｄ，Ｃｉ，（ｉ ｍｏｄ ｎ）＋１）を生成する。（ｓｉｄ，Ｃｉ，（ｉ ｍｏｄ ｎ）＋１）は出力部１５２から出力され、端末装置１００−（（ｉ ｍｏｄ ｎ）＋１）に送信される。すなわち、出力部１５２は（ｓｉｄ，Ｃ（ｉ−２ ｍｏｄ ｎ）＋１，ｉ）を端末装置１００−ｉに送信する。また、出力部１５２は、端末装置１００−１に対し、端末装置１００−１が代表端末装置として選択された旨を表す情報（代表通知）を送信する。
【００２４】
≪Ｒｏｕｎｄ３（図６）≫
本形態のＲｏｕｎｄ３の処理は、端末装置１００−１（端末装置Ｕ１）とそれ以外の端末装置１００−ｖ（端末装置Ｕｖ）とで相違する。ただし、ｖ＝２，…，ｎである。
【００２５】
端末装置１００−１（端末装置Ｕ１）：
（ｓｉｄ，Ｃｎ，１）および代表通知は、端末装置１００−１の入力部１０１−１に入力される（受け付けられる）。代表通知が受信された場合、制御部１０４−１は以下の制御を行う。
【００２６】
復号部１０８−１は、記憶部１０３−１から読み出した鍵カプセル復号鍵ｓｋ１を用い、鍵カプセルＣｎ，１を復号して二者間共有鍵Ｒｎ，１を得て出力する。例えば、復号部１０８−１は、参考文献１に記載された方法で二者間共有鍵Ｒｎ，１を得て出力する。二者間共有鍵Ｒｎ，１は記憶部１０３−１に格納される。
【００２７】
次に、関数演算部１０９−１は、二者間共有鍵Ｒｎ，１の関数値Ｋ１（Ｌ）を得て出力する。関数値Ｋ１（Ｌ）は二者間共有鍵Ｒｎ，１のみに依存する値であってもよいし、二者間共有鍵Ｒｎ，１と他の付加情報とに依存する値であってもよい。「α３のみに依存する値」はα３そのものであってもよいし、α３に対応する値であってもよい。ただし、後述のＫｎ（Ｒ）に対してＫ１（Ｌ）＝Ｋｎ（Ｒ）を満たさなければならない。例えば、関数演算部１０９−１は、二者間共有鍵Ｒｎ，１とｓｉｄとに依存する関数値Ｋ１（Ｌ）＝Ｆ（ｓｉｄ，Ｒｎ，１）
を得て出力する。Ｆ（α１，α２）の例は、α１とα２とのビット連結値α１｜α２の関数値である。Ｆの例は一方向性関数である。一方向性関数の例は、ハッシュ関数（例えば、暗号学的なハッシュ関数）である。関数値Ｋ１（Ｌ）は記憶部１０３−１に格納される。
【００２８】
また、関数演算部１０９−１は、記憶部１０３−１から二者間共有鍵Ｒ１，２を読み出し、当該二者間共有鍵Ｒ１，２の関数値Ｋ１（Ｒ）を得て出力する。関数値Ｋ１（Ｒ）は二者間共有鍵Ｒ１，２のみに依存する値であってもよいし、二者間共有鍵Ｒ１，２と他の付加情報とに依存する値であってもよい。ただし、後述のＫ２（Ｌ）に対してＫ１（Ｒ）＝Ｋ２（Ｌ）を満たさなければならない。例えば、関数演算部１０９−１は、二者間共有鍵Ｒ１，２とｓｉｄとに依存する関数値
Ｋ１（Ｒ）＝Ｆ（ｓｉｄ，Ｒ１，２）
を得て出力する。関数値Ｋ１（Ｒ）は記憶部１０３−１に格納される。
【００２９】
関数値Ｋ１（Ｌ）と関数値Ｋ１（Ｒ）とは排他的論理和部１１０−１に入力される。排他的論理和部１１０−１は、関数値Ｋ１（Ｌ）と関数値Ｋ１（Ｒ）との排他的論理和
Ｔ１＝Ｋ１（Ｌ）（＋）Ｋ１（Ｒ）
を得て出力する。α１（＋）α２はα１とα２との排他的論理和を表す。α１およびα２の少なくとも一方がビット列でない場合、α１とα２との排他的論理和とは、ビット列で表現されたα１およびα２の排他的論理和を表す。
【００３０】
排他的論理和部１１０−１には、さらに記憶部１０３−１から読み込まれた乱数ｋ１が入力される。排他的論理和部１１０−１は、乱数ｋ１の関数値Ｂ（ｋ１）と関数値Ｋ１（Ｌ）との排他的論理和
Ｔ’＝Ｂ（ｋ１）（＋）Ｋ１（Ｌ）
を得て出力する。関数値Ｂ（ｋ１）は乱数ｋ１のみに依存する値であってもよいし、乱数ｋ１と他の付加情報とに依存する値であってもよい。ただし、関数値Ｂ（ｋ１）から容易に乱数ｋ１を抽出できなければならない。関数値Ｂ（ｋ１）の例は乱数ｋ１と他の付加情報βとのビット連結ｋ１｜βである。
【００３１】
排他的論理和Ｔ１およびＴ’は出力部１０２−１から出力され、鍵配送管理装置１５０に送信される。
【００３２】
端末装置１００−ｖ（端末装置Ｕｖ）：
（ｓｉｄ，Ｃ（ｖ−２ ｍｏｄ ｎ）＋１，ｖ）は、端末装置１００−ｖ（ただし、ｖ＝２，…，ｎ）の入力部１０１−ｖに入力される（受け付けられる）。代表通知が受信されなかった場合、制御部１０４−ｖは以下の制御を行う。
【００３３】
復号部１０８−ｖは、記憶部１０３−ｖから読み出した鍵カプセル復号鍵ｓｋｖを用い、鍵カプセルＣ（ｖ−２ ｍｏｄ ｎ）＋１，ｖを復号して二者間共有鍵Ｒ（ｖ−２ ｍｏｄ ｎ）＋１，ｖを得て出力する。例えば、復号部１０８−ｖは、参考文献１に記載された方法で二者間共有鍵Ｒ（ｖ−２ ｍｏｄ ｎ）＋１，ｖを得て出力する。二者間共有鍵Ｒ（ｖ−２ ｍｏｄ ｎ）＋１，ｖは記憶部１０３−ｖに格納される。
【００３４】
関数演算部１０９−ｖは、二者間共有鍵Ｒ（ｖ−２ ｍｏｄ ｎ）＋１，ｖの関数値Ｋｖ（Ｌ）を得て出力する。関数値Ｋｖ（Ｌ）は二者間共有鍵Ｒ（ｖ−２ ｍｏｄ ｎ）＋１，ｖのみに依存する値であってもよいし、二者間共有鍵Ｒ（ｖ−２ ｍｏｄ ｎ）＋１，ｖと他の付加情報とに依存する値であってもよい。ただし、後述のＫ（ｖ−２ ｍｏｄ ｎ）＋１（Ｒ）に対してＫｖ（Ｌ）＝Ｋ（ｖ−２ ｍｏｄ ｎ）＋１（Ｒ）を満たさなければならない。例えば、関数演算部１０９−ｖは、二者間共有鍵Ｒ（ｖ−２ ｍｏｄ ｎ）＋１，ｖとｓｉｄとに依存する関数値
Ｋｖ（Ｌ）＝Ｆ（ｓｉｄ，Ｒ（ｖ−２ ｍｏｄ ｎ）＋１，ｖ）
を得て出力する。関数値Ｋｖ（Ｌ）は記憶部１０３−ｖに格納される。
【００３５】
関数演算部１０９−ｖは、記憶部１０３−ｖから二者間共有鍵Ｒｖ，（ｖ ｍｏｄ ｎ）＋１を読み出し、当該二者間共有鍵Ｒｖ，（ｖ ｍｏｄ ｎ）＋１の関数値Ｋｖ（Ｒ）を得て出力する。関数値Ｋｖ（Ｒ）は二者間共有鍵Ｒｖ，（ｖ ｍｏｄ ｎ）＋１のみに依存する値であってもよいし、二者間共有鍵Ｒｖ，（ｖ ｍｏｄ ｎ）＋１と他の付加情報とに依存する値であってもよい。ただし、Ｋｖ（Ｒ）＝Ｋ（ｖ ｍｏｄ ｎ）＋１（Ｌ）を満たさなければならない。例えば、関数演算部１０９−ｖは、二者間共有鍵Ｒｖ，（ｖ ｍｏｄ ｎ）＋１とｓｉｄとに依存する関数値
Ｋｖ（Ｒ）＝Ｆ（ｓｉｄ，Ｒｖ，（ｖ ｍｏｄ ｎ）＋１）
を得て出力する。関数値Ｋｖ（Ｒ）は記憶部１０３−ｖに格納される。
【００３６】
関数値Ｋｖ（Ｌ）と関数値Ｋｖ（Ｒ）とは排他的論理和部１１０−ｖに入力される。排他的論理和部１１０−ｖは、関数値Ｋｖ（Ｌ）と関数値Ｋｖ（Ｒ）との排他的論理和
Ｔｖ＝Ｋｖ（Ｌ）（＋）Ｋｖ（Ｒ）
を得て出力する。
【００３７】
乱数ｋｖおよび排他的論理和Ｔｖは出力部１０２−ｖから出力され、鍵配送管理装置１５０に送信される。
【００３８】
排他的論理和Ｔ１，…，Ｔｎ、Ｔ’、および乱数ｋ２，…，ｋｎは、鍵配送管理装置１５０（図３）の入力部１５１に入力され、記憶部１５７に格納される。排他的論理和部１５６は、記憶部１５７から読み込んだ乱数ｋ２，…，ｋｎを含む複数の値の排他的論理和ｋ’を得て出力する。乱数ｋ２，…，ｋｎを含む複数の値の排他的論理和ｋ’は、乱数ｋ２，…，ｋｎの排他的論理和であってもよいし、乱数ｋ２，…，ｋｎと他の付加値との排他的論理和であってもよい。例えば、演算部１５３が乱数ｋｓを生成し、排他的論理和部１５６が乱数ｋ２，…，ｋｎ，ｋｓの排他的論理和
ｋ’＝ｋ２（＋）…（＋）ｋｎ（＋）ｋｓ
を得て出力する。
【００３９】
また排他的論理和部１５６は、ｖ＝２，…，ｎについて、記憶部１５７から排他的論理和Ｔ１，…，Ｔｖ‐１を読み込み、排他的論理和Ｔ１，…，Ｔｖ‐１の排他的論理和
Ｔｖ’＝Ｔ１（＋）…（＋）Ｔｖ‐１
を得て出力する。
【００４０】
出力部１５２は、排他的論理和ｋ’を端末装置１００−１に対して送信し、排他的論理和Ｔ’，ｋ’，Ｔｖ’を端末装置１００−ｖ（ただし、ｖ＝２，…，ｎ）に対して送信する。
【００４１】
≪共有鍵生成（図７）≫
共有鍵生成の処理は、端末装置１００−１（端末装置Ｕ１）とそれ以外の端末装置１００−ｖ（端末装置Ｕｖ）とで相違する。
【００４２】
端末装置１００−１（端末装置Ｕ１）：
排他的論理和ｋ’は、端末装置１００−１の入力部１０１−１に入力される（受け付けられる）。共有鍵生成部１１２−１は、当該排他的論理和ｋ’と記憶部１０３−１から読み出した乱数ｋ１との排他的論理和ｋ’（＋）ｋ１の関数値を共有鍵
ＳＫ＝Ｆ’（ｋ’（＋）ｋ１）
として得て出力する。Ｆ’の例は一方向性関数である。共有鍵ＳＫは、ｋ’（＋）ｋ１のみに依存する値であってもよいし、ｋ’（＋）ｋ１と他の付加情報とに依存する値であってもよい。当該他の付加情報の例はｓｉｄや他の暗号方式（例えば、属性ベース暗号）に基づいて得られた鍵などである。
参考文献２（属性ベース暗号）：Yongtao Wang, "Lattice Ciphertext Policy Attribute-based Encryption in the Standard Model," International Journal of Network Security, Vol.16, No.6, PP.444-451, Nov. 2014.
【００４３】
端末装置１００−ｖ（端末装置Ｕｖ）：
排他的論理和Ｔ’，ｋ’，Ｔｖ’は、端末装置１００−ｖの入力部１０１−ｖに入力される（受け付けられる）。関数値復元部１１１−ｖは、当該排他的論理和Ｔｖ’と記憶部１０３−ｖから読み出した関数値Ｋｖ（Ｌ）との排他的論理和によって関数値Ｋ１（Ｌ）を得て出力する。関数値Ｋ１（Ｌ）が得られる理由は以下の通りである。
Ｔｖ’（＋）Ｋｖ（Ｌ）
＝Ｔ１（＋）…（＋）Ｔｖ‐１（＋）Ｋｖ（Ｌ）
＝Ｋ１（Ｌ）（＋）Ｋ１（Ｒ）（＋）Ｋ２（Ｌ）（＋）Ｋ２（Ｒ）（＋）・・・（＋）Ｋｖ−１（Ｌ）（＋）Ｋｖ−１（Ｒ）（＋）Ｋｖ（Ｌ）
＝Ｋ１（Ｌ）
【００４４】
乱数復元部１１３−ｖは、当該排他的論理和Ｔ’と当該関数値Ｋ１（Ｌ）との排他的論理和によって乱数ｋ１の関数値Ｂ（ｋ１）を得て出力する。関数値Ｂ（ｋ１）が得られる理由は以下の通りである。
Ｔ’（＋）Ｋ１（Ｌ）
＝Ｂ（ｋ１）（＋）Ｋ１（Ｌ）（＋）Ｋ１（Ｌ）
＝Ｂ（ｋ１）
【００４５】
共有鍵生成部１１２−ｖは、関数値Ｂ（ｋ１）（例えば、Ｂ（ｋ１）＝ｋ１｜β）から乱数ｋ１を抽出し、排他的論理和ｋ’と関数値Ｂ（ｋ１）から得られた乱数ｋ１との排他的論理和ｋ’（＋）ｋ１の関数値を共有鍵
ＳＫ＝Ｆ’（ｋ’（＋）ｋ１）
として得て出力する。
【００４６】
各端末装置１００−ｉ（端末装置Ｕｉ）の記憶部１０３−ｉ（ただし、ｉ＝１，…，ｎ）には、共有鍵ＳＫを用いて更新された関数値ｒ＝Ｆ”（ＳＫ）および二者間共有鍵Ｈｉ（Ｌ）＝Ｒ（ｉ−２ ｍｏｄ ｎ）＋１，ｉおよびＨｉ（Ｒ）＝Ｒｉ，（ｉ ｍｏｄ ｎ）＋１が格納される。
【００４７】
＜本形態の特徴＞
本形態では、鍵カプセル型の二者間鍵交換を採用したため、公開鍵暗号方式の耐量子計算機暗号に則った二者間鍵交換が可能になり、これを利用することで耐量子安全な多者間鍵交換システムを構成できる。すなわち、Ｒｏｕｎｄ１で各端末装置が隣の端末装置に対して耐量子計算機暗号に則った鍵暗号化鍵を送信し、Ｒｏｕｎｄ２で各端末装置が受け取った鍵暗号化鍵を用いて二者間共有鍵の鍵カプセルを生成して鍵暗号化鍵の送信元の端末装置に返信し、Ｒｏｕｎｄ３で各端末装置が二者間共有鍵に基づく情報を生成して鍵配送管理装置に送信し、鍵配送管理装置がそれらの情報に基づいて得られる情報を各端末装置に配送する。各端末装置は配送された情報に基づいて共有鍵を計算できる。一方で鍵配送管理装置は各端末装置から送られた情報から共有鍵を知ることはできない。二者間共有鍵を共有する処理は耐量子安全であり、これに基づく多者間鍵交換も耐量子安全である。
【００４８】
［第２実施形態］
第２実施形態を説明する。第２実施形態では、第１実施形態の処理が行われた後、新たな端末装置１００−（ｎ＋１）（端末装置Ｕｎ＋１）が追加され、ｎ＋１個の端末装置１００−１〜１００−（ｎ＋１）（端末装置Ｕ１，…，Ｕｎ＋１）で共有鍵ＳＫの共有を行う。
【００４９】
＜構成＞
図８に例示するように、本形態の鍵交換システム２は、ｎ個の端末装置１００−１〜１００−ｎ（端末装置Ｕ１，…，Ｕｎ）と新たに追加される端末装置１００−（ｎ＋１）（端末装置Ｕｉ＋１）と鍵配送管理装置１５０とを有する。各端末装置１００−ｉ（端末装置Ｕｉ）（ただし、ｉ＝１，…，ｎ）および端末装置１００−（ｎ＋１）は、インターネット等を通じて鍵配送管理装置１５０と通信可能に構成されている。
【００５０】
図９に例示するように、端末装置１００−（ｎ＋１）は、入力部１０１−（ｎ＋１）、出力部１０２−（ｎ＋１）、記憶部１０３−（ｎ＋１）、制御部１０４−（ｎ＋１）、鍵ペア生成部１０５−（ｎ＋１）、乱数設定部１０６−（ｎ＋１）、二者間共有鍵生成部１０７−（ｎ＋１）、復号部１０８−（ｎ＋１）、関数演算部１０９−（ｎ＋１）、排他的論理和部１１０−（ｎ＋１）、関数値復元部１１１−（ｎ＋１）、乱数復元部１１３−（ｎ＋１）、および共有鍵生成部１１２−（ｎ＋１）を有する。端末装置１００−（ｎ＋１）は、制御部１０４−（ｎ＋１）の制御の下で各処理を実行する。当該処理で得られたデータは記憶部１０３−（ｎ＋１）に格納され、必要に応じて記憶部１０３−（ｎ＋１）から読み出されて他の処理に用いられる。
【００５１】
＜処理＞
次に、端末装置１００−（ｎ＋１）が追加された後の鍵交換処理を説明する。本形態の鍵交換処理は、Ｒｏｕｎｄ１〜３および共有鍵生成を含む。前提として、各端末装置１００−ｉ（端末装置Ｕｉ）（図２）の記憶部１０３−ｉ（ただし、ｉ＝1，…，ｎ）には、第１実施形態の処理で得られた共有鍵ＳＫの関数値ｒ＝Ｆ”（ＳＫ）、二者間共有鍵Ｈｉ（Ｌ）＝Ｒ（ｉ−２ ｍｏｄ ｎ）＋１，ｉおよびＨｉ（Ｒ）＝Ｒｉ，（ｉ ｍｏｄ ｎ）＋１が格納されていることにする。
【００５２】
≪Ｒｏｕｎｄ１（図１０）≫
端末装置１００−１（端末装置Ｕ１）：
端末装置１００−１（図２）の鍵ペア生成部１０５−１は、公開鍵暗号方式の耐量子計算機暗号に則った鍵カプセル復号鍵ｓｋ１および当該鍵カプセル復号鍵ｓｋ１に対応する鍵暗号化鍵ｐｋ１からなる鍵ペア（ｐｋ１，ｓｋ１）を生成する。生成された鍵カプセル復号鍵ｓｋ１および鍵暗号化鍵ｐｋ１は記憶部１０３−１に格納される。また、鍵暗号化鍵ｐｋ１は出力部１０２−１から出力され、鍵配送管理装置１５０に送信される。
【００５３】
端末装置１００−（ｎ＋１）（端末装置Ｕｎ＋１）：
端末装置１００−（ｎ＋１）（図９）の鍵ペア生成部１０５−（ｎ＋１）は、公開鍵暗号方式の耐量子計算機暗号に則った鍵カプセル復号鍵ｓｋｎ＋１および当該鍵カプセル復号鍵ｓｋｎ＋１に対応する鍵暗号化鍵ｐｋｎ＋１からなる鍵ペア（ｐｋｎ＋１，ｓｋｎ＋１）を生成する。生成された鍵カプセル復号鍵ｓｋｎ＋１および鍵暗号化鍵ｐｋｎ＋１は記憶部１０３−（ｎ＋１）に格納される。また、鍵暗号化鍵ｐｋｎ＋１は出力部１０２−（ｎ＋１）から出力され、鍵配送管理装置１５０に送信される。
【００５４】
鍵暗号化鍵ｐｋ１，ｐｋｎ＋１は鍵配送管理装置１５０（図３）の入力部１５１に入力される。鍵暗号化鍵ｐｋ１が入力部１５１に入力され次第、制御部１５４は当該鍵暗号化鍵ｐｋ１を出力部１５２に送り、出力部１５２は当該鍵暗号化鍵ｐｋ１を端末装置１００−（ｎ＋１）に送信する。鍵暗号化鍵ｐｋｎ＋１が入力部１５１に入力され次第、制御部１５４は当該鍵暗号化鍵ｐｋｎ＋１を出力部１５２に送り、出力部１５２は当該鍵暗号化鍵ｐｋｎ＋１を端末装置１００−ｎに送信する。
【００５５】
≪Ｒｏｕｎｄ２（図１１）≫
端末装置１００−ｎ（端末装置Ｕｎ）：
端末装置１００−ｎ（図２）の入力部１０１−ｎは鍵暗号化鍵ｐｋｎ＋１を受信し、鍵暗号化鍵ｐｋｎ＋１を記憶部１０３−ｎに格納する。
【００５６】
端末装置１００−ｎの乱数設定部１０６−ｎは乱数ｋｎを設定して出力する。乱数ｋｎは記憶部１０３−ｎに格納される。
【００５７】
二者間共有鍵生成部１０７−ｎは、鍵暗号化鍵ｐｋｎ＋１を用い、二者間共有鍵Ｒｎ，ｎ＋１および当該二者間共有鍵Ｒｎ，ｎ＋１の暗号文である鍵カプセルＣｎ，ｎ＋１を得て出力する（例えば、参考文献１等参照）。二者間共有鍵Ｒｎ，ｎ＋１は記憶部１０３−ｎに格納される。鍵カプセルＣｎ，ｎ＋１は出力部１０２−ｎから出力され、鍵配送管理装置１５０に送信される。
【００５８】
端末装置１００−（ｎ＋１）（端末装置Ｕｎ＋１）：
端末装置１００−（ｎ＋１）（図９）の入力部１０１−（ｎ＋１）は鍵暗号化鍵ｐｋ１を受信し（受け付け）、鍵暗号化鍵ｐｋ１を記憶部１０３−（ｎ＋１）に格納する。
【００５９】
端末装置１００−（ｎ＋１）の乱数設定部１０６−（ｎ＋１）は乱数ｋｎ＋１を設定して出力する。乱数ｋｎ＋１は記憶部１０３−（ｎ＋１）に格納される。
【００６０】
二者間共有鍵生成部１０７−（ｎ＋１）は、鍵暗号化鍵ｐｋ１を用い、二者間共有鍵Ｒｎ＋１，１および当該二者間共有鍵Ｒｎ＋１，１の暗号文である鍵カプセルＣｎ＋１，１を得て出力する（例えば、参考文献１等参照）。二者間共有鍵Ｒｎ＋１，１は記憶部１０３−（ｎ＋１）に格納される。鍵カプセルＣｎ＋１，１は出力部１０２−（ｎ＋１）から出力され、鍵配送管理装置１５０に送信される。
【００６１】
端末装置１００−ρ（端末装置Ｕρ）：
端末装置１００−ρ（ただし、ρ＝１，…，ｎ‐１）の乱数設定部１０６−ρは乱数ｋρを設定して出力する。乱数ｋρは記憶部１０３−ρに格納される。
【００６２】
鍵配送管理装置１５０（図３）の入力部１５１は、端末装置１００−ｎから送信された鍵カプセルＣｎ，ｎ＋１、および端末装置１００−（ｎ＋１）から送信された鍵カプセルＣｎ＋１，１を受信する。ＳＩＤ設定部１５５はｓｉｄを新たに生成し、代表端末装置として端末装置１００−１を選択する。演算部１５３は（ｓｉｄ，Ｃｎ，ｎ＋１）および（ｓｉｄ，Ｃｎ＋１，１）を生成する。（ｓｉｄ，Ｃｎ，ｎ＋１）は出力部１５２から出力され、端末装置１００−（ｎ＋１）に送信される。（ｓｉｄ，Ｃｎ＋１，１）は出力部１５２から出力され、端末装置１００−１に送信される。出力部１５２は、端末装置１００−１に対し、端末装置１００−１が代表端末装置として選択された旨を表す情報（代表通知）を送信する。さらにｓｉｄが出力部１５２から出力され、端末装置１００−ｖ（ただし、ｖ＝２，…，ｎ）に対して送信される。
【００６３】
≪Ｒｏｕｎｄ３（図１２）≫
本形態のＲｏｕｎｄ３の処理は、端末装置１００−１（端末装置Ｕ１）と端末装置１００−ｎ（端末装置Ｕｎ）と端末装置１００−（ｎ＋１）（端末装置Ｕｎ＋１）とそれら以外の端末装置１００−ｚ（端末装置Ｕｚ）とで相違する。ただし、ｚ＝２，…，ｎ−１である。
【００６４】
端末装置１００−１（端末装置Ｕ１）：
（ｓｉｄ，Ｃｎ＋１，１）および代表通知は、端末装置１００−１の入力部１０１−１に入力される。代表通知が受信された場合、制御部１０４−１は以下の制御を行う。
【００６５】
復号部１０８−１は、記憶部１０３−１から読み出した鍵カプセル復号鍵ｓｋ１を用い、鍵カプセルＣｎ＋１，１を復号して二者間共有鍵Ｒｎ＋１，１を得て出力する。二者間共有鍵Ｒｎ＋１，１は記憶部１０３−１に格納される。
【００６６】
次に、関数演算部１０９−１は、二者間共有鍵Ｒｎ＋１，１の関数値Ｋ１（Ｌ）を得て出力する。関数値Ｋ１（Ｌ）は二者間共有鍵Ｒｎ＋１，１のみに依存する値であってもよいし、二者間共有鍵Ｒｎ＋１，１と他の付加情報とに依存する値であってもよい。ただし、後述のＫｎ＋１（Ｒ）に対してＫ１（Ｌ）＝Ｋｎ＋１（Ｒ）を満たさなければならない。例えば、関数演算部１０９−１は、二者間共有鍵Ｒｎ＋１，１とｓｉｄとに依存する関数値
Ｋ１（Ｌ）＝Ｆ（ｓｉｄ，Ｒｎ＋１，１）
を得て出力する。関数値Ｋ１（Ｌ）は記憶部１０３−１に格納される。
【００６７】
また、関数演算部１０９−１は、記憶部１０３−１から関数値ｒを読み出し、当該関数値ｒの関数値Ｋ１（Ｒ）を得て出力する。関数値Ｋ１（Ｒ）は関数値ｒのみに依存する値であってもよいし、関数値ｒと他の付加情報とに依存する値であってもよい。ただし、Ｋ１（Ｒ）＝Ｋｎ（Ｌ）を満たさなければならない。例えば、関数演算部１０９−１は、関数値ｒとｓｉｄとに依存する関数値
Ｋ１（Ｒ）＝Ｆ（ｓｉｄ，ｒ）
を得て出力する。関数値Ｋ１（Ｒ）は記憶部１０３−１に格納される。
【００６８】
関数値Ｋ１（Ｌ）と関数値Ｋ１（Ｒ）とは排他的論理和部１１０−１に入力される。排他的論理和部１１０−１は、関数値Ｋ１（Ｌ）と関数値Ｋ１（Ｒ）との排他的論理和
Ｔ１＝Ｋ１（Ｌ）（＋）Ｋ１（Ｒ）
を得て出力する。
【００６９】
排他的論理和部１１０−１には、さらに記憶部１０３−１から読み込まれた乱数ｋ１が入力される。排他的論理和部１１０−１は、乱数ｋ１の関数値Ｂ（ｋ１）と関数値Ｋ１（Ｌ）との排他的論理和
Ｔ’＝Ｂ（ｋ１）（＋）Ｋ１（Ｌ）
を得て出力する。前述のように、関数値Ｂ（ｋ１）の例は乱数ｋ１と他の付加情報βとのビット連結ｋ１｜βである。
【００７０】
排他的論理和Ｔ１およびＴ’は出力部１０２−１から出力され、鍵配送管理装置１５０に送信される。
【００７１】
端末装置１００−ｎ（端末装置Ｕｎ）：
関数演算部１０９−ｎは、記憶部１０３−ｎから関数値ｒを読み出し、当該関数値ｒの関数値Ｋｎ（Ｌ）を得て出力する。関数値Ｋｎ（Ｌ）は関数値ｒのみに依存する値であってもよいし、関数値ｒと他の付加情報とに依存する値であってもよい。ただし、Ｋｎ（Ｌ）＝Ｋ１（Ｒ）を満たさなければならない。例えば、関数演算部１０９−ｎは、関数値ｒとｓｉｄとに依存する関数値
Ｋｎ（Ｌ）＝Ｆ（ｓｉｄ，ｒ）
を得て出力する。関数値Ｋｎ（Ｌ）は記憶部１０３−ｎに格納される。
【００７２】
関数演算部１０９−ｎは、記憶部１０３−ｎから二者間共有鍵Ｒｎ，ｎ＋１を読み出し、当該二者間共有鍵Ｒｎ，ｎ＋１の関数値Ｋｎ（Ｒ）を得て出力する。関数値Ｋｎ（Ｒ）は二者間共有鍵Ｒｎ，ｎ＋１のみに依存する値であってもよいし、二者間共有鍵Ｒｎ，ｎ＋１と他の付加情報とに依存する値であってもよい。ただし、Ｋｎ（Ｒ）＝Ｋｎ＋１（Ｌ）を満たさなければならない。例えば、関数演算部１０９−ｎは、二者間共有鍵Ｒｎ，ｎ＋１とｓｉｄとに依存する関数値
Ｋｎ（Ｒ）＝Ｆ（ｓｉｄ，Ｒｎ，ｎ＋１）
を得て出力する。関数値Ｋｎ（Ｒ）は記憶部１０３−ｎに格納される。
【００７３】
関数値Ｋｎ（Ｌ）と関数値Ｋｎ（Ｒ）とは排他的論理和部１１０−ｎに入力される。排他的論理和部１１０−ｎは、関数値Ｋｎ（Ｌ）と関数値Ｋｎ（Ｒ）との排他的論理和
Ｔｎ＝Ｋｎ（Ｌ）（＋）Ｋｎ（Ｒ）
を得て出力する。
【００７４】
記憶部１０３−ｎから読み出された乱数ｋｎおよび排他的論理和Ｔｎは出力部１０２−ｎから出力され、鍵配送管理装置１５０に送信される。
【００７５】
端末装置１００−（ｎ＋１）（端末装置Ｕｎ＋１）：
（ｓｉｄ，Ｃｎ，ｎ＋１）は、端末装置１００−（ｎ＋１）の入力部１０１−（ｎ＋１）に入力される。
【００７６】
復号部１０８−（ｎ＋１）は、記憶部１０３−（ｎ＋１）から読み出した鍵カプセル復号鍵ｓｋｎ＋１を用い、鍵カプセルＣｎ，ｎ＋１を復号して二者間共有鍵Ｒｎ，ｎ＋１を得て出力する。二者間共有鍵Ｒｎ，ｎ＋１は記憶部１０３−（ｎ＋１）に格納される。
【００７７】
次に、関数演算部１０９−（ｎ＋１）は、二者間共有鍵Ｒｎ，ｎ＋１の関数値Ｋｎ＋１（Ｌ）を得て出力する。関数値Ｋｎ＋１（Ｌ）は二者間共有鍵Ｒｎ，ｎ＋１のみに依存する値であってもよいし、二者間共有鍵Ｒｎ，ｎ＋１と他の付加情報とに依存する値であってもよい。ただし、Ｋｎ＋１（Ｌ）＝Ｋｎ（Ｒ）を満たさなければならない。例えば、関数演算部１０９−（ｎ＋１）は、二者間共有鍵Ｒｎ，ｎ＋１とｓｉｄとに依存する関数値
Ｋｎ＋１（Ｌ）＝Ｆ（ｓｉｄ，Ｒｎ，ｎ＋１）
を得て出力する。関数値Ｋｎ＋１（Ｌ）は記憶部１０３−（ｎ＋１）に格納される。
【００７８】
関数演算部１０９−（ｎ＋１）は、記憶部１０３−（ｎ＋１）から二者間共有鍵Ｒｎ＋１，１を読み出し、当該二者間共有鍵Ｒｎ＋１，１の関数値Ｋｎ＋１（Ｒ）を得て出力する。関数値Ｋｎ＋１（Ｒ）は二者間共有鍵Ｒｎ＋１，１のみに依存する値であってもよいし、二者間共有鍵Ｒｎ＋１，１と他の付加情報とに依存する値であってもよい。ただし、Ｋｎ＋１，１（Ｒ）＝Ｋ１（Ｌ）を満たさなければならない。例えば、関数演算部１０９−（ｎ＋１）は、二者間共有鍵Ｒｎ＋１，１とｓｉｄとに依存する関数値
Ｋｎ＋１（Ｒ）＝Ｆ（ｓｉｄ，Ｒｎ＋１，１）
を得て出力する。関数値Ｋｎ＋１（Ｒ）は記憶部１０３−（ｎ＋１）に格納される。
【００７９】
関数値Ｋｎ＋１（Ｌ）と関数値Ｋｎ＋１（Ｒ）とは排他的論理和部１１０−（ｎ＋１）に入力される。排他的論理和部１１０−（ｎ＋１）は、関数値Ｋｎ＋１（Ｌ）と関数値Ｋｎ＋１（Ｒ）との排他的論理和
Ｔｎ＋１＝Ｋｎ＋１（Ｌ）（＋）Ｋｎ＋１（Ｒ）
を得て出力する。
【００８０】
記憶部１０３−（ｎ＋１）から読み出された乱数ｋｎ＋１および排他的論理和Ｔｎ＋１は出力部１０２−（ｎ＋１）から出力され、鍵配送管理装置１５０に送信される。
【００８１】
端末装置１００−ｚ（端末装置Ｕｚ）（ｚ＝２，…，ｎ−１）：
記憶部１０３−ｚから読み出された乱数ｋｚが出力部１０２−ｚから出力され、鍵配送管理装置１５０に送信される。
【００８２】
排他的論理和Ｔ１，Ｔｎ，Ｔｎ＋１、Ｔ’、および乱数ｋ２，…，ｋｎ＋１は、鍵配送管理装置１５０（図３）の入力部１５１に入力され、記憶部１５７に格納される。排他的論理和部１５６は、記憶部１５７から読み込んだ乱数ｋ２，…，ｋｎ＋１を含む複数の値の排他的論理和ｋ’を得て出力する。乱数ｋ２，…，ｋｎ＋１を含む複数の値の排他的論理和ｋ’は、乱数ｋ２，…，ｋｎ＋１の排他的論理和であってもよいし、乱数ｋ２，…，ｋｎ＋１と他の付加値との排他的論理和であってもよい。例えば、演算部１５３が乱数ｋｓを生成し、排他的論理和部１５６が乱数ｋ２，…，ｋｎ＋１，ｋｓの排他的論理和
ｋ’＝ｋ２（＋）…（＋）ｋｎ＋１（＋）ｋｓ
を得て出力する。
【００８３】
また排他的論理和部１５６は、ｗ＝２，…，ｎ＋１について、記憶部１５７から排他的論理和Ｔ１，…，Ｔｗ‐１を読み込み、排他的論理和Ｔ２，…，Ｔｎ‐１を空とした排他的論理和Ｔ１，…，Ｔｗ‐１の排他的論理和
Ｔｗ’＝Ｔ１（＋）…（＋）Ｔｗ‐１
を得て出力する。すなわち、２≦ｗ≦ｎではＴｗ’＝Ｔ１であり、ｗ＝ｎ＋１ではＴｗ’＝Ｔ１（＋）Ｔｎである。
【００８４】
出力部１５２は、排他的論理和ｋ’を端末装置１００−１に対して送信し、排他的論理和Ｔ’，ｋ’，Ｔｗ’を端末装置１００−ｗ（ただし、ｗ＝２，…，ｎ＋１）に対して送信する。
【００８５】
≪共有鍵生成（図１３）≫
共有鍵生成の処理は、端末装置１００−１（端末装置Ｕ１）と端末装置１００−ｎ（端末装置Ｕｎ）と端末装置１００−（ｎ＋１）（端末装置Ｕｎ＋１）とそれら以外の端末装置１００−ρ（端末装置Ｕρ）とで相違する。
【００８６】
端末装置１００−１（端末装置Ｕ１）：
排他的論理和ｋ’は、端末装置１００−１の入力部１０１−１に入力される。共有鍵生成部１１２−１は、当該排他的論理和ｋ’と記憶部１０３−１から読み出した乱数ｋ１との排他的論理和ｋ’（＋）ｋ１の関数値を共有鍵
ＳＫ＝Ｆ’（ｋ’（＋）ｋ１）
として得て出力する。
【００８７】
端末装置１００−ｎ（端末装置Ｕｎ）：
排他的論理和Ｔ’，ｋ’，Ｔｎ’は、端末装置１００−ｎの入力部１０１−ｎに入力される。関数値復元部１１１−ｎは、当該排他的論理和Ｔｎ’と記憶部１０３−ｎから読み出した関数値Ｋｎ（Ｌ）との排他的論理和によって関数値Ｋ１（Ｌ）を得て出力する。関数値Ｋ１（Ｌ）が得られる理由は以下の通りである（排他的論理和Ｔ２，…，Ｔｎ‐１は空であり、Ｋ１（Ｒ）＝Ｋｎ（Ｌ））。
Ｔｎ’（＋）Ｋｎ（Ｌ）
＝Ｔ１（＋）…（＋）Ｔｎ‐１（＋）Ｋｎ（Ｌ）
＝Ｔ１（＋）Ｋｎ（Ｌ）
＝Ｋ１（Ｌ）（＋）Ｋ１（Ｒ）（＋）Ｋｎ（Ｌ）
＝Ｋ１（Ｌ）
【００８８】
乱数復元部１１３−ｎは、当該排他的論理和Ｔ’と当該関数値Ｋ１（Ｌ）との排他的論理和によって乱数ｋ１の関数値Ｂ（ｋ１）を得て出力する。関数値Ｂ（ｋ１）が得られる理由は前述の通りである。
【００８９】
共有鍵生成部１１２−ｎは、関数値Ｂ（ｋ１）（例えば、Ｂ（ｋ１）＝ｋ１｜β）から乱数ｋ１を抽出し、排他的論理和ｋ’と関数値Ｂ（ｋ１）から得られた乱数ｋ１との排他的論理和ｋ’（＋）ｋ１の関数値を共有鍵
ＳＫ＝Ｆ’（ｋ’（＋）ｋ１）
として得て出力する。
【００９０】
端末装置１００−（ｎ＋１）（端末装置Ｕｎ＋１）：
排他的論理和Ｔ’，ｋ’，Ｔｎ＋１’は、端末装置１００−（ｎ＋１）の入力部１０１−（ｎ＋１）に入力される。関数値復元部１１１−（ｎ＋１）は、当該排他的論理和Ｔｎ＋１’と記憶部１０３−（ｎ＋１）から読み出した関数値Ｋｎ＋１（Ｌ）との排他的論理和によって関数値Ｋ１（Ｌ）を得て出力する。なお、関数値Ｋ１（Ｌ）が得られる理由は以下の通りである（排他的論理和Ｔ２，…，Ｔｎ‐１は空であり、Ｋ１（Ｒ）＝Ｋｎ（Ｌ）かつＫｎ（Ｒ）＝Ｋｎ＋１（Ｌ））。
Ｔｎ＋１’（＋）Ｋｎ＋１（Ｌ）
＝Ｔ１（＋）…（＋）Ｔｎ（＋）Ｋｎ＋１（Ｌ）
＝Ｔ１（＋）Ｔｎ（＋）Ｋｎ＋１（Ｌ）
＝Ｋ１（Ｌ）（＋）Ｋ１（Ｒ）（＋）Ｋｎ（Ｌ）（＋）Ｋｎ（Ｒ）（＋）Ｋｎ＋１（Ｌ）
＝Ｋ１（Ｌ）
【００９１】
乱数復元部１１３−（ｎ＋１）は、当該排他的論理和Ｔ’と当該関数値Ｋ１（Ｌ）との排他的論理和によって乱数ｋ１の関数値Ｂ（ｋ１）を得て出力する。
【００９２】
共有鍵生成部１１２−（ｎ＋１）は、関数値Ｂ（ｋ１）（例えば、Ｂ（ｋ１）＝ｋ１｜β）から乱数ｋ１を抽出し、排他的論理和ｋ’と関数値Ｂ（ｋ１）から得られた乱数ｋ１との排他的論理和ｋ’（＋）ｋ１の関数値を共有鍵
ＳＫ＝Ｆ’（ｋ’（＋）ｋ１）
として得て出力する。
【００９３】
端末装置１００−ρ（端末装置Ｕρ）（ρ＝１，…，ｎ−１）：
排他的論理和Ｔ’，ｋ’，Ｔρ’は、端末装置１００−ρの入力部１０１−ρに入力される。関数値復元部１１１−ρは、当該排他的論理和Ｔρ’と記憶部１０３−ρから読み出した関数値ｒの関数値（＝Ｋ１（Ｒ））との排他的論理和によって関数値Ｋ１（Ｌ）を得て出力する。
【００９４】
乱数復元部１１３−ρは、当該排他的論理和Ｔ’と当該関数値Ｋ１（Ｌ）との排他的論理和によって乱数ｋ１の関数値Ｂ（ｋ１）を得て出力する。
【００９５】
共有鍵生成部１１２−ρは、関数値Ｂ（ｋ１）（例えば、Ｂ（ｋ１）＝ｋ１｜β）から乱数ｋ１を抽出し、排他的論理和ｋ’と関数値Ｂ（ｋ１）から得られた乱数ｋ１との排他的論理和ｋ’（＋）ｋ１の関数値を共有鍵
ＳＫ＝Ｆ’（ｋ’（＋）ｋ１）
として得て出力する。
【００９６】
各端末装置１００−ｉ”（端末装置Ｕｉ”）の記憶部１０３−ｉ”（ただし、ｉ”＝１，…，ｎ＋１）には、新たな共有鍵ＳＫを用いて更新された関数値ｒ＝Ｆ”（ＳＫ）および二者間共有鍵Ｈｉ”（Ｌ）＝Ｒ（ｉ”−２ ｍｏｄ ｎ）＋１，ｉ”およびＨｉ”（Ｒ）＝Ｒｉ”，（ｉ” ｍｏｄ ｎ）＋１が格納される。
【００９７】
＜本形態の特徴＞
本形態では、鍵カプセル型の二者間鍵交換を採用したため、公開鍵暗号方式の耐量子計算機暗号に則った二者間鍵交換が可能になり、これを利用して上述の処理を行うことで、追加された新たな端末装置との間で耐量子安全な多者間鍵交換を行うことができる。
【００９８】
［第３実施形態］
第３実施形態を説明する。第３実施形態では、第１実施形態の処理が行われた後、何れかの端末装置１００−ｊ（端末装置Ｕｊ）（ｊは１以上ｎ以下の整数）がシステムから離脱し、残りのｎ−１個の端末装置１００−１〜１００−（ｊ−１），１００−（ｊ＋１）〜１００−ｎ（端末装置Ｕ１，…，Ｕｊ−１，Ｕｊ＋１，…，Ｕｎ）で新たな共有鍵ＳＫを共有する。
【００９９】
＜構成＞
図１４に例示するように、本形態の鍵交換システム３は、ｎ個の端末装置１００−１〜１００−ｎ（端末装置Ｕ１，…，Ｕｎ）と鍵配送管理装置１５０とを有する。各端末装置１００−ｉ（端末装置Ｕｉ）（ただし、ｉ＝１，…，ｎ）は、インターネット等を通じて鍵配送管理装置１５０と通信可能に構成されている。
【０１００】
＜処理＞
次に、端末装置１００−ｊが鍵交換システム３から離脱した後の鍵交換処理を説明する。本形態の鍵交換処理は、Ｒｏｕｎｄ１〜３および共有鍵生成を含む。前提として、各端末装置１００−ｉ（端末装置Ｕｉ）（図２）の記憶部１０３−ｉ（ただし、ｉ＝１，…，ｎ）には、第１実施形態の処理で得られた二者間共有鍵Ｈｉ（Ｌ）＝Ｒ（ｉ−２ ｍｏｄ ｎ）＋１，ｉおよびＨｉ（Ｒ）＝Ｒｉ，（ｉ ｍｏｄ ｎ）＋１が格納されていることにする。
【０１０１】
≪Ｒｏｕｎｄ１（図１５）≫
端末装置１００−（（ｊ ｍｏｄ ｎ）＋１）（端末装置Ｕ（ｊ ｍｏｄ ｎ）＋１）：
端末装置１００−（（ｊ ｍｏｄ ｎ）＋１）（図２）の鍵ペア生成部１０５−（（ｊ ｍｏｄ ｎ）＋１）は、公開鍵暗号方式の耐量子計算機暗号に則った鍵カプセル復号鍵ｓｋ（ｊ ｍｏｄ ｎ）＋１および当該鍵カプセル復号鍵ｓｋ（ｊ ｍｏｄ ｎ）＋１に対応する鍵暗号化鍵ｐｋ（ｊ ｍｏｄ ｎ）＋１からなる鍵ペア（ｐｋ（ｊ ｍｏｄ ｎ）＋１，ｓｋ（ｊ ｍｏｄ ｎ）＋１）を生成する。生成された鍵カプセル復号鍵ｓｋ（ｊ ｍｏｄ ｎ）＋１および鍵暗号化鍵ｐｋ（ｊ ｍｏｄ ｎ）＋１は記憶部１０３−（（ｊ ｍｏｄ ｎ）＋１）に格納される。また、鍵暗号化鍵ｐｋ（ｊ ｍｏｄ ｎ）＋１は出力部１０２−（（ｊ ｍｏｄ ｎ）＋１）から出力され、鍵配送管理装置１５０に送信される。
【０１０２】
鍵暗号化鍵ｐｋ（ｊ ｍｏｄ ｎ）＋１は鍵配送管理装置１５０（図３）の入力部１５１に入力される。鍵暗号化鍵ｐｋ（ｊ ｍｏｄ ｎ）＋１が入力部１５１に入力され次第、制御部１５４は当該鍵暗号化鍵ｐｋ（ｊ ｍｏｄ ｎ）＋１を出力部１５２に送り、出力部１５２は当該鍵暗号化鍵ｐｋ（ｊ ｍｏｄ ｎ）＋１を端末装置１００−（（ｊ−２ ｍｏｄ ｎ）＋１）に送信する。
【０１０３】
≪Ｒｏｕｎｄ２（図１６）≫
端末装置１００−（（ｊ−２ ｍｏｄ ｎ）＋１）（端末装置Ｕ（ｊ−２ ｍｏｄ ｎ）＋１）：
端末装置１００−（（ｊ−２ ｍｏｄ ｎ）＋１）（図２）の入力部１０１−（（ｊ−２ ｍｏｄ ｎ）＋１）は鍵暗号化鍵ｐｋ（ｊ ｍｏｄ ｎ）＋１を受信し、鍵暗号化鍵ｐｋ（ｊ ｍｏｄ ｎ）＋１を記憶部１０３−（（ｊ−２ ｍｏｄ ｎ）＋１）に格納する。
【０１０４】
端末装置１００−（（ｊ−２ ｍｏｄ ｎ）＋１）の乱数設定部１０６−（（ｊ−２ ｍｏｄ ｎ）＋１）は乱数ｋ（ｊ−２ ｍｏｄ ｎ）＋１を設定して出力する。乱数ｋ（ｊ−２ ｍｏｄ ｎ）＋１は記憶部１０３−（（ｊ−２ ｍｏｄ ｎ）＋１）に格納される。
【０１０５】
二者間共有鍵生成部１０７−（（ｊ−２ ｍｏｄ ｎ）＋１）は、鍵暗号化鍵ｐｋ（ｊ ｍｏｄ ｎ）＋１を用い、二者間共有鍵Ｒ（ｊ−２ ｍｏｄ ｎ）＋１，（ｊ ｍｏｄ ｎ）＋１および当該二者間共有鍵Ｒ（ｊ−２ ｍｏｄ ｎ）＋１，（ｊ ｍｏｄ ｎ）＋１の暗号文である鍵カプセルＣ（ｊ−２ ｍｏｄ ｎ）＋１，（ｊ ｍｏｄ ｎ）＋１を得て出力する。二者間共有鍵Ｒ（ｊ−２ ｍｏｄ ｎ）＋１，（ｊ ｍｏｄ ｎ）＋１は記憶部１０３−（（ｊ−２ ｍｏｄ ｎ）＋１）に格納される。鍵カプセルＣ（ｊ−２ｍｏｄ ｎ）＋１，（ｊ ｍｏｄ ｎ）＋１は出力部１０２−（（ｊ−２ ｍｏｄ ｎ）＋１）から出力され、鍵配送管理装置１５０に送信される。
【０１０６】
端末装置１００−ｙ（端末装置Ｕｙ）（ｙ＝１，…，ｎかつｙ≠ｊかつｙ≠（ｊ−２） mod n＋１）：
端末装置１００−ｙの乱数設定部１０６−ｙは乱数ｋｙを設定して出力する。乱数ｋｙは記憶部１０３−ｙに格納される。ただし、ｙ＝１，…，ｎかつｙ≠ｊかつｙ≠（ｊ−２） mod n＋１である。
【０１０７】
鍵配送管理装置１５０（図３）の入力部１５１は、端末装置１００−（（ｊ−２ ｍｏｄ ｎ）＋１）から送信された鍵カプセルＣ（ｊ−２ ｍｏｄ ｎ）＋１，（ｊ ｍｏｄ ｎ）＋１を受信する。ＳＩＤ設定部１５５はｓｉｄを新たに生成し、代表端末装置として端末装置１００−（（ｊ−２ ｍｏｄ ｎ）＋１）を選択する。演算部１５３は（ｓｉｄ，Ｃ（ｊ−２ ｍｏｄ ｎ）＋１，（ｊ ｍｏｄ ｎ）＋１）を生成する。（ｓｉｄ，Ｃ（ｊ−２ ｍｏｄ ｎ）＋１，（ｊ ｍｏｄ ｎ）＋１）は出力部１５２から出力され、端末装置１００−（（ｊ−２ ｍｏｄ ｎ）＋１）に送信される。出力部１５２は、端末装置１００−（（ｊ−２ ｍｏｄ ｎ）＋１）に対し、端末装置１００−（（ｊ−２ ｍｏｄ ｎ）＋１）が代表端末装置として選択された旨を表す情報（代表通知）を送信する。さらにｓｉｄが出力部１５２から出力され、端末装置１００−φに対して送信される。ただし、φ＝１，…，ｎかつφ≠ｊかつｘ≠（φ ｍｏｄｎ）＋１である。
【０１０８】
≪Ｒｏｕｎｄ３（図１７）≫
本形態のＲｏｕｎｄ３の処理は、端末装置１００−（ｊ−１）（端末装置Ｕｊ−１）と端末装置１００−（ｊ＋１）（端末装置Ｕｊ＋１）と端末装置１００−ｘ（端末装置Ｕｘ）とで相違する。ただし、ｘ＝１，…，ｎかつｘ≠ｊかつｘ≠（ｊ−２ mod n）＋１かつｘ≠（ｊ mod n）＋１である。
【０１０９】
端末装置１００−（（ｊ−２ ｍｏｄ ｎ）＋１）（端末装置Ｕ（ｊ−２ ｍｏｄ ｎ）＋１）：
関数演算部１０９−（（ｊ−２ ｍｏｄ ｎ）＋１）は、記憶部１０３−（（ｊ−２ ｍｏｄ ｎ）＋１）から二者間共有鍵Ｈ（ｊ−２ ｍｏｄ ｎ）＋１（Ｌ）＝Ｒ（ｊ−３ ｍｏｄ ｎ）＋１，（ｊ−２ ｍｏｄ ｎ）＋１を読み出し、当該二者間共有鍵Ｈ（ｊ−２ ｍｏｄ ｎ）＋１（Ｌ）の関数値Ｋ（ｊ−２ ｍｏｄ ｎ）＋１（Ｌ）を得て出力する。関数値Ｋ（ｊ−２ ｍｏｄ ｎ）＋１（Ｌ）は二者間共有鍵Ｈ（ｊ−２ ｍｏｄ ｎ）＋１（Ｌ）のみに依存する値であってもよいし、二者間共有鍵Ｈ（ｊ−２ ｍｏｄ ｎ）＋１（Ｌ）と他の付加情報とに依存する値であってもよい。ただし、Ｋ（ｊ−２ ｍｏｄ ｎ）＋１（Ｌ）＝Ｋ（ｊ−３ ｍｏｄ ｎ）＋１（Ｒ）を満たさなければならない。例えば、関数演算部１０９−ｎは、二者間共有鍵Ｈ（ｊ−２ ｍｏｄ ｎ）＋１（Ｌ）＝Ｒ（ｊ−３ ｍｏｄ ｎ）＋１，（ｊ−２ ｍｏｄ ｎ）＋１とｓｉｄとに依存する関数値
Ｋ（ｊ−２ ｍｏｄ ｎ）＋１（Ｌ）
＝Ｆ（ｓｉｄ，Ｈ（ｊ−２ ｍｏｄ ｎ）＋１（Ｌ））
＝Ｆ（ｓｉｄ，Ｒ（ｊ−３ ｍｏｄ ｎ）＋１，（ｊ−２ ｍｏｄ ｎ）＋１）
を得て出力する。関数値Ｋ（ｊ−２ ｍｏｄ ｎ）＋１（Ｌ）は記憶部１０３−（（ｊ−２ｍｏｄｎ）＋１）に格納される。
【０１１０】
関数演算部１０９−（（ｊ−２ ｍｏｄ ｎ）＋１）は、記憶部１０３−（（ｊ−２ ｍｏｄ ｎ）＋１）から二者間共有鍵Ｒ（ｊ−２ ｍｏｄ ｎ）＋１，（ｊ ｍｏｄ ｎ）＋１を読み出し、当該二者間共有鍵Ｒ（ｊ−２ ｍｏｄ ｎ）＋１，（ｊ ｍｏｄ ｎ）＋１の関数値Ｋ（ｊ−２ ｍｏｄ ｎ）＋１（Ｒ）を得て出力する。関数値Ｋ（ｊ−２ ｍｏｄ ｎ）＋１（Ｒ）は二者間共有鍵Ｒ（ｊ−２ ｍｏｄ ｎ）＋１，（ｊ ｍｏｄ ｎ）＋１のみに依存する値であってもよいし、二者間共有鍵Ｒ（ｊ−２ ｍｏｄ ｎ）＋１，（ｊ ｍｏｄ ｎ）＋１と他の付加情報とに依存する値であってもよい。ただし、Ｋ（ｊ−２ ｍｏｄ ｎ）＋１（Ｒ）＝Ｋ（ｊ ｍｏｄ ｎ）＋１（Ｌ）を満たさなければならない。例えば、関数演算部１０９−（（ｊ−２ ｍｏｄ ｎ）＋１）は、二者間共有鍵Ｒ（ｊ−２ ｍｏｄ ｎ）＋１，（ｊ ｍｏｄ ｎ）＋１とｓｉｄとに依存する関数値
Ｋ（ｊ−２ ｍｏｄ ｎ）＋１（Ｒ）＝Ｆ（ｓｉｄ，Ｒ（ｊ−２ ｍｏｄ ｎ）＋１，（ｊ ｍｏｄ ｎ）＋１）
を得て出力する。関数値Ｋ（ｊ−２ ｍｏｄ ｎ）＋１（Ｒ）は記憶部１０３−（（ｊ−２ｍｏｄｎ）＋１）に格納される。
【０１１１】
関数値Ｋ（ｊ−２ ｍｏｄ ｎ）＋１（Ｌ）と関数値Ｋ（ｊ−２ ｍｏｄ ｎ）＋１（Ｒ）とは排他的論理和部１１０−（（ｊ−２ ｍｏｄ ｎ）＋１）に入力される。排他的論理和部１１０−（（ｊ−２ ｍｏｄ ｎ）＋１）は、関数値Ｋ（ｊ−２ ｍｏｄ ｎ）＋１（Ｌ）と関数値Ｋ（ｊ−２ ｍｏｄ ｎ）＋１（Ｒ）との排他的論理和
Ｔ（ｊ−２ ｍｏｄ ｎ）＋１＝Ｋ（ｊ−２ ｍｏｄ ｎ）＋１（Ｌ）（＋）Ｋ（ｊ−２ ｍｏｄ ｎ）＋１（Ｒ）
を得て出力する。
【０１１２】
排他的論理和部１１０−（（ｊ−２ ｍｏｄ ｎ）＋１）には、さらに記憶部１０３−（（ｊ−２ ｍｏｄ ｎ）＋１）から読み込まれた乱数ｋ（ｊ−２ ｍｏｄ ｎ）＋１が入力される。排他的論理和部１１０−（（ｊ−２ ｍｏｄ ｎ）＋１）は、乱数ｋ（ｊ−２ ｍｏｄ ｎ）＋１の関数値Ｂ（ｋ（ｊ−２ ｍｏｄ ｎ）＋１）と関数値Ｋ（ｊ−２ ｍｏｄ ｎ）＋１（Ｌ）との排他的論理和
Ｔ’＝Ｂ（ｋ（ｊ−２ ｍｏｄ ｎ）＋１）（＋）Ｋ（ｊ−２ ｍｏｄ ｎ）＋１（Ｌ）
を得て出力する。関数値Ｂ（ｋ（ｊ−２ ｍｏｄ ｎ）＋１）の例は乱数ｋ（ｊ−２ ｍｏｄ ｎ）＋１と他の付加情報βとのビット連結ｋ（ｊ−２ ｍｏｄ ｎ）＋１｜βである。
【０１１３】
排他的論理和Ｔ（ｊ−２ ｍｏｄ ｎ）＋１および排他的論理和Ｔ’は出力部１０２−（（ｊ−２ ｍｏｄ ｎ）＋１）から出力され、鍵配送管理装置１５０に送信される。
【０１１４】
端末装置１００−（（ｊ ｍｏｄ ｎ）＋１）（端末装置Ｕ（ｊ ｍｏｄ ｎ）＋１）：
（ｓｉｄ，Ｃ（ｊ−２ ｍｏｄ ｎ）＋１，（ｊ ｍｏｄ ｎ）＋１）は、端末装置１００−（（ｊ ｍｏｄ ｎ）＋１）の入力部１０１−（（ｊ ｍｏｄ ｎ）＋１）に入力される。
【０１１５】
復号部１０８−（（ｊ ｍｏｄ ｎ）＋１）は、記憶部１０３−（（ｊ ｍｏｄ ｎ）＋１）から読み出した鍵カプセル復号鍵ｓｋ（ｊ ｍｏｄ ｎ）＋１を用い、鍵カプセルＣ（ｊ−２ ｍｏｄ ｎ）＋１，（ｊ ｍｏｄ ｎ）＋１を復号して二者間共有鍵Ｒ（ｊ−２ ｍｏｄ ｎ）＋１，（ｊ ｍｏｄ ｎ）＋１を得て出力する。二者間共有鍵Ｒ（ｊ−２ ｍｏｄ ｎ）＋１，（ｊ ｍｏｄ ｎ）＋１は記憶部１０３−（（ｊ ｍｏｄ ｎ）＋１）に格納される。
【０１１６】
関数演算部１０９−（（ｊ ｍｏｄ ｎ）＋１）は、二者間共有鍵Ｒ（ｊ−２ ｍｏｄ ｎ）＋１，（ｊ ｍｏｄ ｎ）＋１の関数値Ｋ（ｊ ｍｏｄ ｎ）＋１（Ｌ）を得て出力する。関数値Ｋ（ｊ ｍｏｄ ｎ）＋１（Ｌ）は二者間共有鍵Ｒ（ｊ−２ ｍｏｄ ｎ）＋１，（ｊ ｍｏｄ ｎ）＋１のみに依存する値であってもよいし、二者間共有鍵Ｒ（ｊ−２ ｍｏｄ ｎ）＋１，（ｊ ｍｏｄ ｎ）＋１と他の付加情報とに依存する値であってもよい。ただし、Ｋ（ｊ ｍｏｄ ｎ）＋１（Ｌ）＝Ｋ（ｊ−２ ｍｏｄ ｎ）＋１（Ｒ）を満たさなければならない。例えば、関数演算部１０９−（（ｊ ｍｏｄ ｎ）＋１）は、二者間共有鍵Ｒ（ｊ−２ ｍｏｄ ｎ）＋１，（ｊ ｍｏｄ ｎ）＋１とｓｉｄとに依存する関数値
Ｋ（ｊ ｍｏｄ ｎ）＋１（Ｌ）＝Ｆ（ｓｉｄ，Ｒ（ｊ−２ ｍｏｄ ｎ）＋１，（ｊ ｍｏｄ ｎ）＋１）
を得て出力する。関数値Ｋ（ｊ ｍｏｄ ｎ）＋１（Ｌ）は記憶部１０３−（（ｊ ｍｏｄ ｎ）＋１）に格納される。
【０１１７】
関数演算部１０９−（（ｊ ｍｏｄ ｎ）＋１）は、記憶部１０３−（（ｊ ｍｏｄ ｎ）＋１）から二者間共有鍵Ｈ（ｊ ｍｏｄ ｎ）＋１（Ｒ）＝Ｒ（ｊ ｍｏｄ ｎ）＋１，（ｊ＋１ ｍｏｄ ｎ）＋１を読み出し、当該二者間共有鍵Ｈ（ｊ ｍｏｄ ｎ）＋１（Ｒ）の関数値Ｋ（ｊ ｍｏｄ ｎ）＋１（Ｒ）を得て出力する。関数値Ｋ（ｊ ｍｏｄ ｎ）＋１（Ｒ）は二者間共有鍵Ｈ（ｊ ｍｏｄ ｎ）＋１（Ｒ）のみに依存する値であってもよいし、二者間共有鍵Ｈ（ｊ ｍｏｄ ｎ）＋１（Ｒ）と他の付加情報とに依存する値であってもよい。ただし、Ｋ（ｊ ｍｏｄ ｎ）＋１（Ｒ）＝Ｋ（j＋１ ｍｏｄ ｎ）＋１（Ｌ）を満たさなければならない。例えば、関数演算部１０９−（（ｊ ｍｏｄ ｎ）＋１）は、二者間共有鍵Ｈ（ｊ ｍｏｄ ｎ）＋１（Ｒ）とｓｉｄとに依存する関数値
Ｋ（ｊ ｍｏｄ ｎ）＋１（Ｒ）
＝Ｆ（ｓｉｄ，Ｈ（ｊ ｍｏｄ ｎ）＋１（Ｒ））
＝Ｆ（ｓｉｄ，Ｒ（ｊ ｍｏｄ ｎ）＋１，（ｊ＋１ ｍｏｄ ｎ）＋１）
を得て出力する。関数値Ｋ（ｊ ｍｏｄ ｎ）＋１（Ｒ）は記憶部１０３−（（ｊ ｍｏｄ ｎ）＋１）に格納される。
【０１１８】
関数値Ｋ（ｊ ｍｏｄ ｎ）＋１（Ｌ）と関数値Ｋ（ｊ ｍｏｄ ｎ）＋１（Ｒ）とは排他的論理和部１１０−（（ｊ ｍｏｄ ｎ）＋１）に入力される。排他的論理和部１１０−（（ｊ ｍｏｄ ｎ）＋１）は、関数値Ｋ（ｊ ｍｏｄ ｎ）＋１（Ｌ）と関数値Ｋ（ｊ ｍｏｄ ｎ）＋１（Ｒ）との排他的論理和
Ｔ（ｊ ｍｏｄ ｎ）＋１＝Ｋ（ｊ ｍｏｄ ｎ）＋１（Ｌ）（＋）Ｋ（ｊ ｍｏｄ ｎ）＋１（Ｒ）
を得て出力する。
【０１１９】
乱数ｋ（ｊ ｍｏｄ ｎ）＋１および排他的論理和Ｔ（ｊ ｍｏｄ ｎ）＋１は出力部１０２−（（ｊ ｍｏｄ ｎ）＋１）から出力され、鍵配送管理装置１５０に送信される。
【０１２０】
端末装置１００−ｘ（端末装置Ｕｘ）（ｘ＝１，…，ｎかつｘ≠ｊかつｘ≠（ｊ−２ ｍｏｄ ｎ）＋１かつｘ≠（ｊ ｍｏｄ ｎ）＋１）：
関数演算部１０９−ｘは、記憶部１０３−ｘから二者間共有鍵Ｈｘ（Ｌ）＝Ｒ（ｘ−２ ｍｏｄ ｎ）＋１，ｘを読み出し、当該二者間共有鍵Ｈｘ（Ｌ）の関数値Ｋｘ（Ｌ）を得て出力する。関数値Ｋｘ（Ｌ）は二者間共有鍵Ｈｘ（Ｌ）のみに依存する値であってもよいし、二者間共有鍵Ｈｘ（Ｌ）と他の付加情報とに依存する値であってもよい。ただし、Ｋｘ（Ｌ）＝Ｋ（ｘ−２ ｍｏｄ ｎ）＋１（Ｒ）を満たさなければならない。例えば、関数演算部１０９−ｘは、二者間共有鍵Ｈｘ（Ｌ）とｓｉｄとに依存する関数値
Ｋｘ（Ｌ）＝Ｆ（ｓｉｄ，Ｈｘ（Ｌ））＝Ｆ（ｓｉｄ，Ｒ（ｘ−２ ｍｏｄ ｎ）＋１，ｘ）
を得て出力する。関数値Ｋｘ（Ｌ）は記憶部１０３−ｘに格納される。
【０１２１】
関数演算部１０９−ｘは、記憶部１０３−ｘから二者間共有鍵Ｈｘ（Ｒ）＝Ｒｘ，（ｘ ｍｏｄ ｎ）＋１を読み出し、当該二者間共有鍵Ｈｘ（Ｒ）の関数値Ｋｘ（Ｒ）を得て出力する。関数値Ｋｘ（Ｒ）は二者間共有鍵Ｈｘ（Ｒ）のみに依存する値であってもよいし、二者間共有鍵Ｈｘ（Ｒ）と他の付加情報とに依存する値であってもよい。ただし、Ｋｘ（Ｒ）＝Ｋ（ｘ ｍｏｄ ｎ）＋１（Ｌ）を満たさなければならない。例えば、関数演算部１０９−ｘは、二者間共有鍵Ｈｘ（Ｒ）とｓｉｄとに依存する関数値
Ｋｘ（Ｒ）＝Ｆ（ｓｉｄ，Ｈｘ（Ｒ））＝Ｆ（ｓｉｄ，Ｒｘ，（ｘ ｍｏｄ ｎ）＋１）
を得て出力する。関数値Ｋｘ（Ｒ）は記憶部１０３−ｘに格納される。
【０１２２】
関数値Ｋｘ（Ｌ）と関数値Ｋｘ（Ｒ）とは排他的論理和部１１０−ｘに入力される。排他的論理和部１１０−ｘは、関数値Ｋｘ（Ｌ）と関数値Ｋｘ（Ｒ）との排他的論理和
Ｔｘ＝Ｋｘ（Ｌ）（＋）Ｋｘ（Ｒ）
を得て出力する。
【０１２３】
記憶部１０３−ｘから読み出された乱数ｋｘおよび排他的論理和Ｔｘは出力部１０２−ｘから出力され、鍵配送管理装置１５０に送信される。
【０１２４】
排他的論理和Ｔ１，…，Ｔｎ＋１（ただし、Ｔｊを除く）、Ｔ’、および乱数ｋ１，…，ｋｎ（ただし、ｋｊ，ｋｊ＋１を除く）は、鍵配送管理装置１５０（図３）の入力部１５１に入力され、記憶部１５７に格納される。排他的論理和部１５６は、記憶部１５７から読み込んだ乱数ｋ１，…，ｋｎ（ただし、ｋｊ，ｋｊ＋１を除く）を含む複数の値の排他的論理和ｋ’を得て出力する。この排他的論理和ｋ’は、乱数ｋ１，…，ｋｎ（ただし、ｋｊ，ｋｊ＋１を除く）の排他的論理和であってもよいし、乱数ｋ１，…，ｋｎ（ただし、ｋｊ，ｋｊ＋１を除く）と他の付加値との排他的論理和であってもよい。例えば、演算部１５３が乱数ｋｓを生成し、排他的論理和部１５６が乱数ｋ１，…，ｋｎ（ただし、ｋｊ，ｋｊ＋１を除く），ｋｓの排他的論理和
ｋ’＝ｋ１（＋）…（＋）ｋｊ‐１（＋）ｋｊ＋２（＋）…（＋）ｋｎ（＋）ｋｓ
を得て出力する。
【０１２５】
また排他的論理和部１５６は、ｙ＝１，…，ｎ（ただし、ｙ≠ｊかつｙ≠（ｊ−２ ｍｏｄ ｎ）＋１）について、ｙ＜ｊ−１のときに排他的論理和Ｔ１，…，Ｔｙ‐１，Ｔｊ‐１，…，Ｔｎの排他的論理和Ｔｙ’を得て出力し、ｊ＋１≦ｙのときに排他的論理和Ｔｊ‐１，…，Ｔｙ‐１の排他的論理和Ｔｙ’を得て出力する。
ｙ＜ｊ−１のとき：Ｔｙ’＝Ｔ１（＋）…（＋）Ｔｙ‐１（＋）Ｔｊ‐１（＋）…（＋）Ｔｎ
ｊ＋１≦ｙのとき：Ｔｙ’＝Ｔｊ‐１（＋）…（＋）Ｔｙ‐１
【０１２６】
出力部１５２は、排他的論理和ｋ’を端末装置１００−（（ｊ−２ ｍｏｄ ｎ）＋１）に対して送信し、排他的論理和Ｔ’，ｋ’，Ｔｙ’を端末装置１００−ｙ（ただし、ｙ≠ｊかつｙ≠（ｊ−２） ｍｏｄ ｎ＋１）に対して送信する。
【０１２７】
≪共有鍵生成（図１８）≫
共有鍵生成の処理は、端末装置１００−（ｊ−１）（端末装置Ｕｊ−１）と端末装置１００−ｙ（端末装置Ｕｙ）（ただし、ｙ≠ｊかつｙ≠（ｊ−２ ｍｏｄ ｎ）＋１）とで相違する。離脱した端末装置１００−ｊ（端末装置Ｕｊ）では共有鍵生成が行われない。
【０１２８】
端末装置１００−ｙ（端末装置Ｕｙ）：
排他的論理和Ｔ’，ｋ’，Ｔｙ’は、端末装置１００−ｙの入力部１０１−ｙに入力される。関数値復元部１１１−ｙは、当該排他的論理和Ｔｙ’と記憶部１０３−ｙから読み出した関数値Ｋｙ（Ｌ）との排他的論理和によって関数値Ｋ（ｊ−２ ｍｏｄ ｎ）＋１（Ｌ）を得て出力する。
【０１２９】
乱数復元部１１３−ｙは、当該排他的論理和Ｔ’と当該関数値Ｋ（ｊ−２ ｍｏｄ ｎ）＋１（Ｌ）との排他的論理和によって乱数ｋ（ｊ−２ ｍｏｄ ｎ）＋１の関数値Ｂ（ｋ（ｊ−２ ｍｏｄ ｎ）＋１）を得て出力する。関数値Ｂ（ｋ（ｊ−２ ｍｏｄ ｎ）＋１）が得られる理由は以下の通りである。
Ｔ’（＋）Ｋ（ｊ−２ ｍｏｄ ｎ）＋１（Ｌ）
＝Ｂ（ｋ（ｊ−２ ｍｏｄ ｎ）＋１）（＋）Ｋ（ｊ−２ ｍｏｄ ｎ）＋１（Ｌ）（＋）Ｋ（ｊ−２ ｍｏｄ ｎ）＋１（Ｌ）
＝Ｂ（ｋ（ｊ−２ ｍｏｄ ｎ）＋１）
【０１３０】
共有鍵生成部１１２−ｙは、関数値Ｂ（ｋ（ｊ−２ ｍｏｄ ｎ）＋１）（例えば、Ｂ（ｋ（ｊ−２ ｍｏｄ ｎ）＋１）＝ｋ（ｊ−２ ｍｏｄ ｎ）＋１｜β）から乱数ｋ（ｊ−２ ｍｏｄ ｎ）＋１を抽出し、排他的論理和ｋ’と関数値Ｂ（ｋ（ｊ−２ ｍｏｄ ｎ）＋１）から得られた乱数ｋ（ｊ−２ ｍｏｄ ｎ）＋１との排他的論理和ｋ’（＋）ｋ（ｊ−２ ｍｏｄ ｎ）＋１の関数値を共有鍵
ＳＫ＝Ｆ’（ｋ’）（＋）ｋ（ｊ−２ ｍｏｄ ｎ）＋１
として得て出力する。
【０１３１】
端末装置１００−（ｊ−１）（端末装置Ｕｊ−１）：
排他的論理和ｋ’は、端末装置１００−（ｊ−１）の入力部１０１−（ｊ−１）に入力される。共有鍵生成部１１２−（ｊ−１）は、当該排他的論理和ｋ’と記憶部１０３−（ｊ−１）から読み出した乱数ｋ（ｊ−２ ｍｏｄ ｎ）＋１との排他的論理和ｋ’（＋）ｋ（ｊ−２ ｍｏｄ ｎ）＋１の関数値を共有鍵
ＳＫ＝Ｆ’（ｋ’）（＋）ｋ（ｊ−２ ｍｏｄ ｎ）＋１
として得て出力する。
【０１３２】
各端末装置１００−ｉ（端末装置Ｕｉ）の記憶部１０３−ｉ（ただし、ｉ＝１，…，ｎ、ｉ≠ｊ）には、新たな共有鍵ＳＫを用いて更新された関数値ｒ＝Ｆ”（ＳＫ）および二者間共有鍵Ｈｉ（Ｌ）＝Ｒ（ｉ−２ ｍｏｄ ｎ）＋１，ｉおよびＨｉ（Ｒ）＝Ｒｉ，（ｉ ｍｏｄ ｎ）＋１が格納される。
【０１３３】
＜本形態の特徴＞
本形態では、鍵カプセル型の二者間鍵交換を採用したため、公開鍵暗号方式の耐量子計算機暗号に則った二者間鍵交換が可能になる。これを利用して上述の処理を行うことで、任意の端末装置がシステムから離脱した後に、残りの端末装置の間で耐量子安全な多者間鍵交換を行うことができる。また、第１実施形態の処理で得られた二者間共有鍵Ｈｉ（Ｌ）＝Ｒ（ｉ−２ ｍｏｄ ｎ）＋１，ｉおよびＨｉ（Ｒ）＝Ｒｉ，（ｉ  ｍｏｄ ｎ）＋１を再利用することで演算量および通信量を削減できる。
【０１３４】
［実施例］
耐量子計算機暗号として格子暗号を用いる場合、各実施形態で説明した鍵カプセル復号鍵ｓｋνはκ１（ν）個の整数からなるベクトルｓνであり、鍵暗号化鍵ｐｋνはｂν＝Ａνｓν＋ｅνである。また、鍵カプセルＣν，（νｍｏｄ μ）＋１は｛γν，ξν’｝であり、二者間共有鍵Ｒν，（νｍｏｄ μ）＋１はＲＯＵＮＤ（２ξν−／ｑ）である。ただし、Ａνはκ１（ν）×κ２（ν）の基底行列であり、κ１（ν）およびκ２（ν）は正整数であり、νおよびμは正整数であり、ｅνはκ２（ν）個の要素からなるベクトルである。γν＝Ａνｓν’＋ｅν’であり、ξν’はｆｌｏｏｒ（４ξν−／ｑ）ｍｏｄ２である。ｓν’はκ１（ν）個の整数からなるベクトル（例えば、正規分布に従ってランダムに選択されたベクトル）であり、ｅν’およびｅν”はκ２（ν）個の要素からなるベクトル（例えば、正規分布に従ってランダムに選択されたベクトル）である。ξν＝ｂ（νｍｏｄ μ）＋１ｓν’＋ｅν”であり、ξν−はξνのランダム関数値（ξνをランダム関数に適用して得られる値）である。ｑは２以上の整数であり、ｆｌｏｏｒは床関数であり、ＲＯＵＮＤは四捨五入関数である。
【０１３５】
各端末装置が公知のコミットメントアルゴリズム（例えば、参考文献３）を用い、乱数ｋｉにコミットメントとでコミットメントを生成し、二者間共有鍵の鍵カプセルとともに出力してもよい。ｓｉｄが各端末装置から出力されたコミットメントの関数値であってもよい。各端末装置が各情報の認証子を生成して出力し、他の端末装置または鍵配送管理装置で認証子の検証が行われてもよい。共有鍵ＳＫがさらにｓｉｄに依存する関数値であってもよい。共有鍵ＳＫがさらに属性ベースアルゴリズム（参考文献２）に基づいて得られた暗号文の復号値に依存する関数値であってもよい。ｓｉｄが省略されてもよい。
参考文献３（コミットメントアルゴリズム）：Fabrice Benhamouda, Stephan Krenn, Vadim Lyubashevsky, Krzysztof Pietrzak, "Efficient Zero-Knowledge Proofs for Commitments from Learning With Errors over Rings," In: ESORICS: European Symposium on Research in Computer Security, September 21-25, 2015.
【０１３６】
［その他の変形例］
なお、本発明は上述の実施形態に限定されるものではない。例えば、上述の各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。その他、本発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。
【０１３７】
上記の各装置は、例えば、ＣＰＵ（central processing unit）等のプロセッサ（ハードウェア・プロセッサ）およびＲＡＭ（random-access memory）・ＲＯＭ（read-only memory）等のメモリ等を備える汎用または専用のコンピュータが所定のプログラムを実行することで構成される。このコンピュータは１個のプロセッサやメモリを備えていてもよいし、複数個のプロセッサやメモリを備えていてもよい。このプログラムはコンピュータにインストールされてもよいし、予めＲＯＭ等に記録されていてもよい。また、ＣＰＵのようにプログラムが読み込まれることで機能構成を実現する電子回路（circuitry）ではなく、プログラムを用いることなく処理機能を実現する電子回路を用いて一部またはすべての処理部が構成されてもよい。１個の装置を構成する電子回路が複数のＣＰＵを含んでいてもよい。
【０１３８】
上述の構成をコンピュータによって実現する場合、各装置が有すべき機能の処理内容はプログラムによって記述される。このプログラムをコンピュータで実行することにより、上記処理機能がコンピュータ上で実現される。この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体の例は、非一時的な（non-transitory）記録媒体である。このような記録媒体の例は、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等である。
【０１３９】
このプログラムの流通は、例えば、そのプログラムを記録したＤＶＤ、ＣＤ−ＲＯＭ等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。
【０１４０】
このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。処理の実行時、このコンピュータは、自己の記憶装置に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるＡＳＰ（Application Service Provider）型のサービスによって、上述の処理を実行する構成としてもよい。
【０１４１】
コンピュータ上で所定のプログラムを実行させて本装置の処理機能が実現されるのではなく、これらの処理機能の少なくとも一部がハードウェアで実現されてもよい。
【産業上の利用可能性】
【０１４２】
本発明の多者間鍵交換技術は、例えば、暗号技術を用いたアプリケーションに利用できる。例えば、本発明の多者間鍵交換技術は、複数人がアクセス可能なデータの暗号化、多者間通信でやり取りされるデータの暗号化、多者間での電子署名および署名検証、電子投票、または電子マネーなどの様々な実用的なアプリケーションで用いられる共有鍵の交換（共有）処理に利用できる。
【符号の説明】
【０１４３】
１〜３  鍵交換システム
１００−１〜（ｎ＋１）  端末装置
【図１】
0006988912.tif 000002
【図２】
0006988912.tif 000003
【図３】
0006988912.tif 000004
【図４】
0006988912.tif 000005
【図５】
0006988912.tif 000006
【図６】
0006988912.tif 000007
【図７】
0006988912.tif 000008
【図８】
0006988912.tif 000009
【図９】
0006988912.tif 000010
【図１０】
0006988912.tif 000011
【図１１】
0006988912.tif 000012
【図１２】
0006988912.tif 000013
【図１３】
0006988912.tif 000014
【図１４】
0006988912.tif 000015
【図１５】
0006988912.tif 000016
【図１６】
0006988912.tif 000017
【図１７】
0006988912.tif 000018
【図１８】
0006988912.tif 000019