【手続補正書】
【提出日】平成17年9月26日(2005.9.26)
【手続補正１】
【補正対象書類名】明細書
【補正対象項目名】特許請求の範囲
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
送信者は，受信者の公開鍵を用いて送信データを暗号化する公開鍵暗号方法であって，
鍵生成のステップとして，
【数１】
2002215019.tif 000001
なる秘密鍵を作成し，さらに，
【数２】
2002215019.tif 000002
なる公開鍵を作成し（但し，群Gは群G'部分群とし，X1，X2は正整数からなる有限集合で，
【数３】
2002215019.tif 000003
を満たすものとする。また，Mは平文空間とする)，
（１）送信者は，平文m（m∈M）に対して，乱数
α1∈X1，α2∈Ｘ2，r∈Zqを選び，
【数４】
2002215019.tif 000004
計算し（但し，α＝α1||α2），(u1,u2,e,v)を暗号文として前記受信者に送信し，
（２）前記受信者は，自身の該秘密鍵を用いて，該暗号文から，
【数５】
2002215019.tif 000005
なる α'1，α'2，m'（α'1∈X1，α'2∈Ｘ2，m'∈M）を計算し，
【数６】
2002215019.tif 000006
が成立すれば復号化結果を m' とし（但し，α'＝α'1||α'2），成立しなければ該暗号文を拒否する旨を復号化結果として出力する
ことを特徴とする公開鍵暗号方法。
【請求項２】
送信者は，受信者の公開鍵を用いて送信データを暗号化する公開鍵暗号方法であって，
鍵生成のステップとして，
【数７】
2002215019.tif 000007
なる秘密鍵を作成し，さらに，
【数８】
2002215019.tif 000008
なる公開鍵を作成し，
（１）送信者は，平文m（|m|=k3，但し|x|はｘの桁数を表す）に対して，乱数
α=α1||α2（|α1|=k1,|α2|=k2）を作成し，
【数９】
2002215019.tif 000009
を計算し，さらに乱数 r∈Zqを選び，
【数１０】
2002215019.tif 000010
計算し，(u1,u2,e,v)を暗号文として前記受信者に送信し，
（２）前記受信者は，自身の該秘密鍵を用いて，該暗号文から，
【数１１】
2002215019.tif 000011
なる α'1，α'2，m'（|α'1|=k1，|α'2|=k2，|m'|=k3）を計算し，
【数１２】
2002215019.tif 000012
が成立すれば復号化結果を m' とし（但し，α'＝α'1||α'2），成立しなければ該暗号文を拒否する旨を復号化結果として出力する
ことを特徴とする公開鍵暗号方法。
【請求項３】
請求項２において，該送信者は該暗号文を作成するに当たり，予め乱数
α1，α2（|α1|=k1,|α2|=k2），r∈Zqを選び，
【数１３】
2002215019.tif 000013
を前もって計算して保存しておく
ことを特徴とする公開鍵暗号方法。
【請求項５】
送信者は，受信者に対して暗号化されたデータを送信する暗号通信方法であって，
鍵生成のステップとして，
【数１４】
2002215019.tif 000014
なる秘密鍵を作成し，さらに，
【数１５】
2002215019.tif 000015
なる公開鍵を作成し（但し，群Gは群G'の部分群とし， X1，X2は正整数からなる有限集合で，
【数１６】
2002215019.tif 000016
を満たすものとする。また，Mは鍵空間とする)，
（１）送信者は鍵データK（K∈M）に対して，乱数
α1∈X1，α2∈Ｘ2，r∈Zqを選び，
【数１７】
2002215019.tif 000017
計算し（但し，α＝α1||α2），さらに，送信者は，送信データmの暗号文Cを（対称型）暗号化関数Eと鍵データＫを用いて，
【数１８】
2002215019.tif 000018
にて作成し，(u1, u2, e, v, C)を暗号文として前記受信者に送信し，
（２）前記受信者は，自身の該秘密鍵を用いて，該暗号文から，
【数１９】
2002215019.tif 000019
なるα'1，α'2，K'（α'1∈X1，α'2∈Ｘ2，K'∈M）を計算し，
【数２０】
2002215019.tif 000020
が成立すれば（但し，α'＝α'1||α'2），
【数２１】
2002215019.tif 000021
にて復号化を行い，復号化結果を出力し，成立しなければ該暗号文を拒否する旨を復号化結果として出力する
ことを特徴とする暗号通信方法。
【請求項６】
請求項５において，該送信者は，暗号文Cを（対称型）暗号化関数Eと鍵データＫ，および公開された適当な関数fを用いて，
【数２２】
2002215019.tif 000022
にて作成し，該受信者は，
【数２３】
2002215019.tif 000023
が成立することを検査し（但し，ｆはkビットの値を出力するものとし，[x]kはxの上位kビットを表す），検査をパスした場合に
【数２４】
2002215019.tif 000024
により復号化を行う（但し，[x]-k は x の上位kビットを除いたビット列を表す）
ことを特徴とする公開鍵暗号方法。
【請求項７】
送信者は，受信者に対して暗号化されたデータを送信する暗号通信方法であって，
鍵生成のステップとして，
【数２５】
2002215019.tif 000025
なる秘密鍵を作成し，さらに，
【数２６】
2002215019.tif 000026
なる公開鍵を作成し，送信者は鍵データK（|K|=k3，但し|x|はｘの桁数を表す）に対して，乱数
α=α1||α2（|α1|=k1,|α2|=k2）を作成し，
【数２７】
2002215019.tif 000027
を計算し，さらに乱数 r∈Zqを選び，
【数２８】
2002215019.tif 000028
を計算し，さらに，送信者は，送信データmの暗号文Cを（対称型）暗号化関数Eと鍵データＫを用いて，
【数２９】
2002215019.tif 000029
にて作成し，(u1,u2,e,v,C)を暗号文として前記受信者に送信し，前記受信者は，自身の該秘密鍵を用いて，該暗号文から，
【数３０】
2002215019.tif 000030
なる α'1，α'2，K'（|α'1|=k1，|α'2|=k2，|K'|=k3）を計算し，
【数３１】
2002215019.tif 000031
が成立すれば（但し，α'＝α'1||α'2），
【数３２】
2002215019.tif 000032
にて復号化を行い，復号化結果を出力し，成立しなければ該暗号文を拒否する旨を復号化結果として出力する
ことを特徴とする暗号通信方法。
【請求項８】
請求項７において，該送信者は，暗号文Cを（対称型）暗号化関数Eと鍵データＫ，および公開された適当な関数fを用いて，
【数３３】
2002215019.tif 000033
にて作成し，該受信者は，
【数３４】
2002215019.tif 000034
が成立することを検査し（但し，fはkビットの値を出力するものとし，[x]kはxの上位kビットを表す），検査をパスした場合に
【数３５】
2002215019.tif 000035
により復号化を行う（但し，[x]-k は x の上位kビットを除いたビット列を表す）
ことを特徴とする公開鍵暗号方法。
【請求項９】
請求項７または８において，該送信者は該暗号文を作成するに当たり，予め乱数
α1，α2（|α1|=k1,|α2|=k2），r∈Zqを選び，
【数３６】
2002215019.tif 000036
を前もって計算して保存しておく
ことを特徴とする公開鍵暗号方法。
【請求項１０】
送信者は，受信者に対して暗号化されたデータを送信する暗号通信方法であって，
鍵生成のステップとして，
【数３７】
2002215019.tif 000037
なる秘密鍵を作成し，さらに，
【数３８】
2002215019.tif 000038
なる公開鍵を作成し（但し，群Gは群G'の部分群とし，X1，X2は正整数からなる有限集合で，
【数３９】
2002215019.tif 000039
を満たすものとする），
（１）送信者は，乱数α1∈X1，α2∈Ｘ2，r∈Zqを選び，
【数４０】
2002215019.tif 000040
計算し（但し，α＝α1||α2），さらに，送信者は，送信データmの暗号文Cを（対称型）暗号化関数Eを用いて，
【数４１】
2002215019.tif 000041
にて作成し，(u1,u2, ,v,C)を暗号文として前記受信者に送信し，
（２）前記受信者は，自身の該秘密鍵を用いて，
【数４２】
2002215019.tif 000042
を計算し，さらに該暗号文から，
【数４３】
2002215019.tif 000043
なるα'1，α'2（α'1∈X1，α'2∈Ｘ2）を計算し，
【数４４】
2002215019.tif 000044
が成立すれば（但し，α'＝α'1||α'2），m'を復号化結果として出力し，成立しなければ該暗号文を拒否する旨を復号化結果として出力する
ことを特徴とする暗号通信方法。
【請求項１１】
送信者は，受信者に対して暗号化されたデータを送信する暗号通信方法であって，
鍵生成のステップとして，
【数４５】
2002215019.tif 000045
なる秘密鍵を作成し，さらに，
【数４６】
2002215019.tif 000046
なる公開鍵を作成し，
（１）送信者は，乱数α=α1||α2（|α1|=k1,|α2|=k2，但し|x|はｘの桁数を表す）を作成し，さらに乱数 r∈Zqを選び，
【数４７】
2002215019.tif 000047
を計算し，さらに，送信者は，送信データmの暗号文Cを（対称型）暗号化関数を用いて，
【数４８】
2002215019.tif 000048
にて作成し，(u1,u2, ,v,C)を暗号文として前記受信者に送信し，
（２）前記受信者は，自身の該秘密鍵を用いて，
【数４９】
2002215019.tif 000049
を計算し，さらに該暗号文から，
【数５０】
2002215019.tif 000050
なる α'1，α'2（|α'1|=k1，|α'2|=k2）を計算し，
【数５１】
2002215019.tif 000051
が成立すれば（但し，α'＝α'1||α'2），m'を復号化結果として出力し，成立しなければ該暗号文を拒否する旨を復号化結果として出力する
ことを特徴とする暗号通信方法。
【請求項１２】
送信者は，受信者に対して暗号化されたデータを送信する暗号通信方法であって，
鍵生成のステップとして，
【数５２】
2002215019.tif 000052
なる秘密鍵を作成し，さらに，
【数５３】
2002215019.tif 000053
なる公開鍵を作成し（但し，群Gは群G'の部分群とし，X1，X2は正整数からなる有限集合で，
【数５４】
2002215019.tif 000054
を満たすものとする。Mは平文空間），
（１）送信者は，乱数α1∈X1，α2∈Ｘ2，r∈Zqを選び，
【数５５】
2002215019.tif 000055
計算し（但し，α＝α1||α2），さらに，送信者は，送信データmの暗号文Cを（非対称型）暗号化関数Epkを用いて，
【数５６】
2002215019.tif 000056
にて作成し，(u1,u2,e,v)を暗号文として前記受信者に送信し，
（２）前記受信者は，自身の該秘密鍵を用いて，該暗号文から，
【数５７】
2002215019.tif 000057
なるα'1，α'2，ｍ'（α'1∈X1，α'2∈Ｘ2，m'∈Ｍ）を計算し，
【数５８】
2002215019.tif 000058
が成立すれば（但し，
【数５９】
2002215019.tif 000059
とする）m'を復号化結果として出力し，成立しなければ該暗号文を拒否する旨を
復号化結果として出力する
ことを特徴とする暗号通信方法。
【請求項１３】
送信者は，受信者に対して暗号化されたデータを送信する暗号通信方法であって，
鍵生成のステップとして，
【数６０】
2002215019.tif 000060
なる秘密鍵を作成し，さらに，
【数６１】
2002215019.tif 000061
なる公開鍵を作成し，
（１）送信者は，乱数α=α1||α2（|α1|=k1,|α2|=k2，但し|x|はｘの桁数を表す）を作成し，さらに乱数 r∈Zqを選び，
【数６２】
2002215019.tif 000062
を計算し，さらに，送信者は，送信データm（正整数）の暗号文Cを（非対称型）暗号化関数Epkを用いて，
【数６３】
2002215019.tif 000063
にて作成し，(u1,u2,e,v)を暗号文として前記受信者に送信し，
（２）前記受信者は，自身の該秘密鍵を用いて，該暗号文から，
【数６４】
2002215019.tif 000064
なる α'1，α'2，m'（|α'1|=k1，|α'2|=k2，m'は正整数）を計算し，
【数６５】
2002215019.tif 000065
が成立すれば（但し， 
【数６６】
2002215019.tif 000066
とする），m'を復号化結果として出力し，成立しなければ該暗号文を拒否する旨
を復号化結果として出力することを特徴とする暗号通信方法。
【請求項１４】
請求項１２または１３において，
前記公開情報は，前記受信者が生成し，公開するステップを備える
ことを特徴とする公開鍵暗号方法。
【請求項１５】
請求項１２において，該送信者は該暗号文を作成するに当たり，予め乱数
α1，α2（α1∈X1,α2∈X2），r∈Zqを選び，u1,u2,v を前もって計算して保存しておく
ことを特徴とする公開鍵暗号方法。
【請求項１６】
請求項１３において，該送信者は該暗号文を作成するに当たり，予め乱数
α1，α2（|α1|=k1,|α2|=k2），r∈Zqを選び，u1,u2,v を前もって計算して保存しておく
ことを特徴とする公開鍵暗号方法。